Источник: Сучасна інформаційна Україна: інформатика, економіка, філософія / Матеріали V міжнародної науково-практичної конференції молодих учених, аспірантів,  студентів – 12-13 травня 2011р., Донецьк, ДУІіШІ. – 2011. – Том 1 – с. 97-101

Кишинский Владимир Викторович

Курило Елена Васильевна

Государственный университет информатики и искусственного интеллекта

Разработка генетического алгоритма оптимального двумерного раскроя материала

С развитием промышленности и увеличением объем производства продукции рациональное использование материала становится все более актуальным.
Задача двумерного раскроя материала состоит в  необходимости оптимального расположения множества прямоугольных объектов (деталей) на листе материала заданного размера, то есть, размещение максимального их количества и обеспечения минимального объема остатков.

Двумерный раскрой применяется на различных производствах для раскроя листов металла, стекла, различных пластиковых и древесных плит, тканей и т.п. Задача относится к классу NP-трудных задач и при использовании метода полного перебора результат может быть получен за экспоненциальное время. Так как на производстве обычно используются листы большого размера, количество деталей велико и время ограниченно, то возникает необходимость в использовании эвристических методов. Критериями оценки работы системы раскроя выступают коэффициент раскроя и время работы алгоритма. Для решения данного типа задач наиболее оптимальными являются генетические алгоритмы.

Работа генетического алгоритма заключается в случайном формировании множества вариантов размещения прямоугольников и выбора из них наилучших по заданному критерию. На следующей итерации строится новое множество решений на основе лучших решений предыдущей итерации. При этом к ним применяются операции селекции, скрещивания и мутации. Важную роль играет декодер, строящий карту раскроя из полученных в итоге вариантов размещения. От него во многом зависит результат работы алгоритма.
Применяют следующие схемы кодирования способов расположения прямоугольников на листе.

1. Прямая схема кодирования. Положение каждого прямоугольника задается координатами (x, y), которые должны быть минимальны.
2. Кодирование приоритетным списком. Данные о расположении прямоугольников представлены в виде последовательности их номеров. Правила укладки задаются внутри декодера.
3. Кодирование парой последовательностей. Решение представлено парой перестановок. Относительные местоположения для каждой пары i и j прямоугольников строится следующим образом: если i располагается перед j в обеих перестановках, то i размещается левее j; если i располагается перед j в первой последовательности и после j во второй, i помещается выше j.
4. Декодер «Нижний левый». Первый прямоугольник из хромосомы помещается в левый нижний угол. Последующие располагаются максимально влево, затем максимально вниз, затем снова влево и вниз до тех пор, пока прямоугольник нельзя будет никуда сдвинуть.
5. Блочный декодер. В качестве начального блока принимается полоса бесконечной длины. По мере упаковки прямоугольников согласно хромосоме формируются и модифицируются блоки. Для добавления в блочную структуру очередного прямоугольника необходимо знать размеры остающихся пустых участков.

Все рассмотренные методы обладают рядом недостатков: существуют наборы прямоугольников, оптимальное размещение которых сложно автоматизируются; на практике в большинстве случаев детали имеют сложную форму, а не прямоугольную; раскрой деталей с кривыми и окружностями не оптимален; не используется место, имеющееся внутри детали, при наличии внутреннего выреза в таковой.

Цель данной работы: разработка алгоритма обеспечивающего оптимальный двумерный раскрой материала.

В качестве схемы кодирования была разработана схема «Привязки к углу». На доступном к размещению деталей поле все углы нумеруются. Ген хромосомы включает в себя два числа: номер прямоугольника и номер угла, в котором он будет размещен. В ходе просчета прямоугольник привязывается к определенному углу. Это позволяет осуществлять более сложную компоновку деталей, в некоторых случаях недоступную при использовании других методов. В качестве операции селекции используется метод «колеса рулетки». Так как основная хромосома (номер прямоугольника) имеет порядковый вид, в качестве метода скрещивания был выбран частично-упорядоченный. Мутация представлена двумя видами: перестановка местами номеров прямоугольников и изменение номеров углов, к которому они привязаны.

При использовании в алгоритме разработанной схемы возможны такие проблемы.

1. За счет использования двойной хромосомы и дополнительных параметров увеличивается сложность и потребность в ресурсах.
2. После добавления нового прямоугольника на поле, количество углов увеличивается, и номера углов сбиваются. Для устранения сбоя номеров углов проводится пересчет угловых привязок.
3. Прямоугольник может оказаться привязанным к углу, места в котором недостаточно для его размещения. В этом случае производится перемещение его в другой угол.

В дальнейшей работе над разработкой планируется реализовать:

• возможность раскроя деталей сложной формы и использования для раскроя листов сложной формы;
• учет оставшегося после раскроя материала для дальнейшего его использования, в случае если появятся детали допустимых размеров;
• метод объединения нескольких деталей в одну, в случае если процент отходов внутри этой группы очень мал.

Выводы: в рамках работы была спроектирован основной генетический алгоритм и схема кодирования раскроя системы. Исследование разработанных алгоритмов позволило выявить ряд проблем, препятствующих достижению оптимального результата. Наиболее существенные из них устранены. Реализация планируемых элементов системы позволит полностью использовать преимущества изначально заложенной архитектуры.

Список использованных источников

1. Э.А. Мухачева, А.С. Мухачева, Л.В. Канторович. Задачи раскроя и упаковки: новые подходы для решения комбинаторных задач линейного раскроя и прямоугольной упаковки, Записки научных семинаров ПОМИ 2004, т. 312, с. 239-255.
2. Л.В. Канторович, В.А.Залгаллер, Рациональный раскрой промышленных материалов, Наука СО, Новосибирск, 1971.
3. А.С.Мухачева, А.В.Чиглинцев, М.А.Смагин, Э.А.Мухачева. Задачи двумерной упаковки: развитие генетических алгоритмов на базе смешанных процедур локального поиска оптимального решения. Информа-ционные технологии. 2001 №9. Приложение. 24с.