Генетические алгоритмы помогают рассчитать схему разреза полосы металла на произвольные прямоугольники

Проблематика

На производстве часто встают задачи по разрезанию листов металла или стекла на куски. Хорошо, если куски одинакового размера. Тогда можно прикинуть какой лист брать и каким образом его резать. А что делать, если куски могут быть произвольных размеров и их много? Понятно, что при этом разрезать идеально, без обрезков не получится. Но, все-таки, как резать, чтобы площадь отходов была минимальной?

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

Так как основной целью оптимального разреза является минимизация отходов, это — типичная задача оптимизации. В решении таких задач особенно хороши генетические алгоритмы, алгоритмы роевого интеллекта, гибридные подходы. О подходе разреза полосы металла на куски одинаковой высоты я писал здесь. В том случае, хотя разрезаемые куски имели разный угол наклона, самое главное, что они были одинаковой высоты. Это позволило применить так называемый «муравьиный алгоритм» или алгоритм муравьиной колонии. В нем воспроизводится поведение муравьев при поиске кратчайших путей от муравьиной колонии к источникам пищи.

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

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

Разрезание листа (полосы) железа (стекла) на произвольные прямоугольники

Постановка задачи

Имеется полоса железа высотой 1000 мм. Нужно разрезать её на 80 разного размера прямоугольников таким образом, чтобы площадь обрезков была минимальной. Прямоугольники можно поворачивать. Рассчитать какой длины должна быть полоса. Предполагаем, чтобы шириной разреза можно пренебречь.

Моделирование

Для нахождения пути решения были случайным образом сгенерированы 80 прямоугольников с шириной от 100 до 900 мм с шагом в 100 мм и меньшей высотой.

Ниже приведено распределение прямоугольников по ширине. Оно получилось достаточно равномерным.

Высота должна была быть меньше ширины. Если она оказывалась меньше 100 мм, то принималась равной 100мм. Распределение по высоте тоже оказалось достаточно равномерным, кроме пика около минимального размера, куда попало всё, что было меньше.

Распределение высоты от ширины:

Применённый подход

Для решения задачи применялся гибридный подход: генетическое моделирование + алгоритм SkyLine.
Итак, у нас имеются входные данные: 80 прямоугольников разного размера, у всех высота меньше ширины.

Генетический подход означает следующее. Нам нужно выбрать особей популяции.

Популяция, Агенты

Агенты — это Особи популяции — способы/стратегии размещения прямоугольников. При этом учитывается последовательность прямоугольников и их возможный поворот (когда высота становится шириной и наоборот).

Примеры агентов:

Агент 1: [Прямоугольник3 + Прямоугольник18 + Прямоугольник35…] + [Повёрнут + Не повёрнут + Повёрнут …]
Агент 2: [Прямоугольник44 + Прямоугольник28 + Прямоугольник66…] + [Не повёрнут + Не повёрнут + Повёрнут …]
…
Агент 15: [Прямоугольник53 + Прямоугольник43 + Прямоугольник14…] + [Повёрнут + Повёрнут + Не повёрнут …]

Было решено использовать 15 агентов/стратегий.

Поколения

Было решено просчитать 15 поколений популяции. Первое поколение выбирается случайным образом. Для каждого агента рассчитывается его (есть разные названия) выживаемость/приспособляемость. Это расчетная величина. В данном случае она определялась количеством вырезанных прямоугольников и длиной полосы металла — чем она короче, тем компактнее разместились прямоугольники и тем меньше обрезки.

Следующее поколение формируется следующим образом. Определяются по определённым правилам агенты/стратегии с наилучшей выживаемостью (в основном). Из них выбираются агенты для «скрещивания»: их характеристики (гены) случайным образом перемешиваются. Плюс добавляются элементы случайности («мутации»). Лучшие из второго поколения передадут свои гены потомкам. Итак до 15 поколения. В котором мы уже будем знать, что если сначала разместить n-й прямоугольник без поворота, затем k-й c поворотом…), то получим наиболее компактное размещение прямоугольников. Так работают эволюционные (генетические) алгоритмы.

Алгоритм SkyLine

Это алгоритм для классической задачи 2D упаковки. Он — эвристический строительно-геометрический.
Представьте себе линию неба (так переводится его название) или линию горизонта, загроможденную контурами небоскрёбов. Этот алгоритм помещает новое здание в свободный участок неба, который ещё не занят.

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

Этот алгоритм хорош тем, что он гарантирует размещение ВСЕХ прямоугольников: при неограниченной длине листа железа всегда найдётся место правее уже занятого пространства.

Гибрид: Генетический подход + алгоритм SkyLine

В чём сила этого гибридного метода? Генетический подход определяет последовательность размещения прямоугольников и их поворот. SkyLine определяет геометрическое место размещения. Что позволяет вычислить выживаемость агента для определения следующего поколения агентов.

Результат моделирования

Всего было просчитано 15 агентов х 15 поколений = 225 вариантов, в каждом из которых брались данные всех 80 прямоугольников. Заняло это около часа.

На графике ниже показано, как уменьшалась длина полосы (= степень компактности) для всех 80 прямоугольников.

Далее следует схема разреза всей полосы длиной 10 метров. Отходы составили 100 — 89.4 = 10.6%

То же самое, но разрезанное на 4 сегмента и более крупным планом:

Что касается времени расчёта — оно напрямую сильно зависит от количества участвующих элементов. Например, расчёт для 20 прямоугольников занял пару минут.

Качество же схемы разрезов (компактность) и меньшее количество обрезков напрямую зависит от количества вырезаемых фигур: чем их больше, тем меньше процент отходов — чем больше вариантов (Прямоугольник+Поворот) участвует в расчёте, тем выше вероятность, что найдётся ещё более компактная комбинация размещения фигур.