Применение алгоритма оптимизации муравьиной колонии (роевый интеллект) для раскройки полосы металла

Хотя, алгоритмы роевого интеллекта многим покажутся экзотическими, на деле они очень даже востребованы в жизни и бизнесе. Сферы актуальности алгоритма оптимизации муравьиной колонии (ACO), также, как и код реализации простейшего варианта алгоритма на Питоне (Python) приведены здесь. В статье описано применение алгоритма для решения задачи бродячего коммивояжера.

Казалось бы, причём тут бродячий торговец в сегодняшних реалиях?

Очень даже причём. В чём фишка задачи коммивояжера? — В нахождении кратчайшего пути между пунктами (городами), при условии посещения каждого только один раз и возврате в начальную точку.

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

Раскрой полосы металла на детали

Постановка задачи оптимизации раскроя полосы металла

Рассчитать схему оптимальной раскройки полосы металла (или стекла) на произвольные четырехугольники (детали).

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

Как бродячий коммивояжёр поможет оптимально раскроить металл?

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

Причём, оптимальный раскрой предполагает, что угол разреза начала каждой последующей детали должен как можно ближе совпадать с углом конца предыдущей детали. Для минимизации площади обрезков.

А именно это и роднит задачу раскройки полосы металла с задачей о бродячем торговце и алгоритмом оптимизации муравьиной колонии. Последовательность! Только не посещаемых городов, а вырезаемых друг за другом деталей.

К тому же, полоса металла начинается и заканчивается прямым углом (90 градусов), что позволяет начать последовательность вырезки прямоугольником (пусть даже фиктивным) и такой же фигурой закончить. Как и коммивояжёр, мы в конце пути можем вернуться в начальную точку!

Особенности алгоритма раскройки металла по сравнению с решением задачи о бродячем торговце

Простейшая реализация классического алгоритма оптимизации муравьиной колонии (код на Питоне (Python)) приведена здесь.

В чём отличия задачи разреза полосы металла от классики?

Отличия:

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

Следствием этих особенностей является то, что в отличие от классического муравьиного алгоритма, матрица расстояний не будет симметричной относительно диагонали. Если для торговца путь от города А до города Б равен обратному пути, то для фигур это, скорее всего, будет неверно. Ведь если параллелограмм плотно прижимается к трапеции, при перестановке их местами, между ними будет огромный просвет.

Чтобы понять, можно ли применить алгоритм оптимизации муравьиной колонии к задаче схемы раскройки металла, был составлен искусственный

Простейший пример применения алгоритма оптимизации муравьиной колонии для раскройки полосы металла

Был составлен набор из незатейливых фигур: квадрат, прямоугольник, параллелограммы и полутрапеции. Последние две фигуры — с углами наклона в 30 и 60 (120 и 150) градусов. У всех фигур — одинаковые высота и нижняя часть.

Углами наклона определялась длина верхней части. Отдельно трапеции не испытывались — их можно моделировать с помощью двух полутрапеций с противоположными углами наклона.

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

Результат отработки муравьиного алгоритма показан ниже.

Здесь приведены 4 куска одной полосы, друг под другом. Смотреть нужно слева направо.

Можете увидеть, что:

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

Фигуры показаны с пробелами друг между другом потому, что они все занимают свою площадь, не пересекаясь с соседями. Заморачиваться над кодом показа того, как это было бы при плотном приближении, не стал.

Конечно, нулевое расхождение в углах обусловлено только двумя (четырьмя) углами наклона. Хотя, в реальной жизни, таких наклонов, скорее всего, будет больше, но ограниченное число.

Результат был получен практически мгновенно. Всего за 8 итераций.

Для того, чтобы посмотреть, как алгоритм работает при полном хаосе в наклонах, был составлен следующий пример.

Пример применения алгоритма оптимизации муравьиной колонии для раскройки полосы металла на 4хугольники с произвольными углами наклона

Было сгенерировано 100 деталей. Углы наклона определялись случайным образом, в диапазоне 45-135 градусов.

Были получены следующие фигуры.

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

Результат работы алгоритма оптимизации муравьиной колонии на произвольных четырехугольниках

Что заметили?

Нестыковки в углах наклона

Если проследить за стыками соседних фигур, то можно заметить то, что наблюдаются расхождения в углах наклона. Кое-где значительные. Последняя фигура не заканчивается прямым углом.

Все объясняется не плохой работой алгоритма, а составом фигур. Случайный характер их генерации создает преобладание каких-то углов и нехватку других.

Муравьиный алгоритм достаточно быстро даёт вполне удовлетворительные результаты. Уже где-то после 20-50й итерации улучшение составляет доли процента. Думаю, сам случайный состав фигур накладывает свои ограничения на возможности оптимизации. Уверен, что ни полный перебор, ни другой алгоритм не справились бы лучше.

Результаты работы несколько отличаются от прогона к прогону. В данном случае — из-за разного случайного набора фигур.

Расхождения в углах наклона

Для 100 фигур среднее отклонение в углах составляло 3-5 градусов на одну пару деталей. Принимая во внимание формулу площади треугольника (такими получаются обрезки) и форму фигур, получаем, что на отходы пришлось бы 1-5% от площади листа.

Выводы по работе алгоритма оптимизации муравьиной колонии

Код был написан на Питоне (Python). Около 300 строк кода, с учетом визуализации фигур.

Почему-то в печати бытует мнение, что роевые алгоритмы работают медленно. Мой опыт показывает, что все как раз наоборот.

Отработка 100 итераций муравьиного алгоритма заняла около минуты — на не самом мощном 6-ядерном процессоре и 16 Gb памяти. Сравните с минутами и часами работы нейронных сетей, с перемножением многомерных матриц в алгоритмах градиентного спуска и BigData для глубокого обучения. Но и то, и другое — технологии искусственного интеллекта.

Уж на что генетические алгоритмы славятся своей скоростью, для задач, подобной описываемой (с последовательностями действий), роевые алгоритмы предпочтительнее. Хотя и у тех, и у других основа одна — популяция особей (агентов), в роевых алгоритмах особи ведут себя не просто случайным образом, как в генетике, а обмениваются дополнительной информацией, что сказывается на эффективности решения задач.

Сама задача применения муравьиного алгоритма для раскроя возникла из практики — производственник пожаловался, что программа на C# отрабатывает схему разреза металла ОЧЕНЬ медленно. Наверное, делает полный перебор вариантов.

Применение муравьиного алгоритма для задач типа раскроя полос металла или стекла очень перспективно в плане экономии. Ведь если для набора четырехугольников с произвольными углами наклонов и единичными размерами (длина и высота) обрезки не превышали 5%, то в реальных условиях, где:

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

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