Генетический алгоритм как инструмент инженера: практический кейс раскроя полотен / Хабр

Перед вами лист материала и список деталей, которые нужно из него вырезать. Металл, ткань, пластик, стекло — не важно. Задача одна: разместить прямоугольники так, чтобы отходов было минимум.

Ручной подбор вариантов отнимает часы, а полный перебор невозможен. Часто останавливаешься на первом более-менее удачном варианте, хотя чувствуешь — должно быть лучше.

Что если делегировать эту рутину компьютеру? Не просто перебор, а «умный» поиск, похожий на естественный отбор в природе.

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

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

Рис 0. Размещения синих деталей на бирюзовом полотне.

Генетический алгоритм: эволюция решений

Для тех кто не сталкивался с генетическими алгоритмами немного терминологии...

Представьте, что вы подбираете идеальную раскладку деталей на листе фанеры. Генетический алгоритм (ГА) делает то же самое, что и вы, но быстрее и без усталости:

Создаёт 100 случайных вариантов (популяцию ботов) — как будто 100 человек одновременно предложили свои схемы раскроя.
Оценивает каждый вариант — считает площадь обрезков (ошибку). Чем меньше отходы, тем выше «рейтинг» схемы.
Выбирает лучших — берёт 20 самых удачных раскладок (ботов). Остальные 80 отбрасываем.
Смешивает их (скрещиваем) — берёт часть деталей из одного удачного варианта, часть из другого — получает новые варианты раскроя «потомков».
Добавляет случайные изменения (мутации) — например, случайным образом переставляет одну деталь, чтобы проверить, не улучшится ли результат.

В итоге нужно получить снова 100 вариантов (новую популяцию), но уже не случайных схем.

20 удачных у нас уже есть и еще нужно добрать ("насмешивать" из 20 удачных и "намутировать") 80 схем.

Теперь снова считаем для каждого варианта (бота) ошибку и снова выбираем 20 самых удачных - с минимальной ошибкой.

Эти шаги повторяются много раз (эпох). Так генетический алгоритм (ГА) перебирает тысячи комбинаций, но не глупо перебирает всё подряд, а постепенно улучшает уже найденное, как селекционер...

ГА - это просто цикл с тремя правилами: отбор, скрещивание, мутация. Всё, что нужно от нас — правильно закодировать решение и научить алгоритм оценивать его качество. Дальше он работает сам.

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

От производственной задачи — к цифровой модели

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

Возьмём для примера полотно шириной 2060 мм и 12 заказов. Под заказом будем понимать определенное количество прямоугольных изделий. На (рис. 1) в таблице список заказов с размером изделий и их количеством.

Рис 1. Список заказов с размерами и количеством изделий.

Размеры изделий достаточно разнообразны. Это видно на (рис. 2).

Чтобы ГА мог с этим работать, нам нужно перевести физическую задачу на язык, который он понимает — язык чисел. Вот как мы это сделаем:

Создаём виртуальные «полосы» из заказов
Вместо того, чтобы думать об отдельных изделиях, объединим изделия каждого заказа в длинные полосы (см. рис. 3). Например, если нужно 2650 штук изделий размером: 2750 ×1830 мм, создаём виртуальную полосу длиной 2750 × 2650 = 7 287 500 мм и шириной 1830 мм (заказ ID 1). В данном случае ГА проще оперировать целыми блоками - полосами.
Изделия складываются в полосу именно по длине из-за ограничений технологии производства. Этот кейс максимально приближен к реальному производственному процессу и поэтому таких ограничений будет несколько. Все их мы позже учтем в ГА. Понятно, что для каждого конкретного производственного процесса на практике будут свои ограничения, которые необходимо учитывать в алгоритме.
Рис 3. Заказы в виде полос (12 полос)
Дробление заказов.
На (рис. 3) видно насколько разные по длине полосы. Самая большая полоса (заказ) с ID 7 - 14 084 м. А самая короткие полосы (заказы) ID 10 и 11 имеют длину 1 641 м
Если мы разместим длинные полосы на полотне вместе с короткими, то получим гигантскую обрезь (отходы). Поэтому будем делить заказы на "подзаказы". Надо выбрать что взять за длину деления. Самое простое что стоит попробовать - это минимальный заказ (ID 10) длиной 1 641 м.
Будем делить так, чтобы части заказов оказывались близки к длине 1 641 м. На (рис. 4) показаны результаты такого дробления. Красная линия - это значение 1 641 м. Есть полосы больше, есть меньше. Какие-то заказы вообще не дробились. Главное, что теперь длинны всех полос близки по длине к 1 641 м. Такой подход позволяет уменьшить обрезь по длине.
Рис 4. Дроблённые заказы (44 подзаказа = 44 полосы).
В итоге мы получили 44 "подзаказа" (полосы) из 12 заказов.
Как именно дробить, конечно, определяется эмпирическим путем в зависимости от текущих задач и возможностей производства. Например, можно делить еще более дробно, если позволяет технология изготовления, чтобы получать максимально близкие между собой длины полос. Или игнорировать мелкие заказы и дробить по средней длине полос или медиане (самой «типичной» длине ). Или например, есть срочный заказ и тогда имеет смысл дробить по нему (по его длине или ее части), чтобы в первую очередь подобрать для срочного заказа "соседей" по полотну с минимальным обрезями.
Количество полотен.
Теперь определим количество полотен, на которые будем "выкладывать" 44 полосы. Просто возьмем сумму всех полос по ширине и разделим на ширину полотна 2060 мм
23660 мм / 2060 мм = 12 полотен (примерно).
Данные для ГА. Что на входе?
На этом этап подготовки сформируем для ГА основной список, состоящий из 44 списков (подзаказов) вот в таком виде:
[[2750, 1830, 663, 1.0], [2750, 1830, 663, 1.1], ....... , [1080, 370, 1521, 12.6]]
В нём каждый "подсписок", например этот:[2750, 1830, 663, 1.1] это длина, ширина, количество и id подзаказа (полосы). В данном случае 1.1 это "подзаказ" исходного первого заказа после дробления. Такой формат id используем для удобства.
В этом основном списке есть вся необходимая для ГА информация по заказам.
Теперь пора решить, как одной строчкой чисел описать, на какое из 12 полотен положить каждую из 44 полос, то есть в одну строчку закодировать схему раскладки?
Используем простое правило:
Каждой полосе присваивается номер полотна, на которое она укладывается.
Пример такой одной строчки:
[1, 11, 0, 3, 10, 3, 9, ....... 9, 1, 8, 5, 8, 3, 8, 10] - длина списка 44 элемента - ровна количеству полос, значения меняются от 0 до 11 - это индексы 12 полотен.
Это означает:
первая полоса с id 1.0 из основного списка → на полотно 1, то есть полоса [2750, 1830, 663, 1.0] на полотно с индексом 1
вторая полоса с id 1.1 из основного списка → на полотно 11, то есть полоса [2750, 1830, 663, 1.1] на полотно с индексом 11
......................
сорок четвертая полоса с id 12.6 из основного списка → на полотно 10, то есть полоса [1080, 370, 1521, 12.6] на полотно с индексом 10
На (рис 5) для наглядности приведена визуальная схемы распределения.
В этом схеме, например:
на полотне #2 (с индексом 1) попали полосы c id 1.0, 1.3, 8.1
на полотно #12 (с индексом 11) попали полосы c id 1.1, 12.5
на полотно #11 (с индексом 10) попали полосы c id 6.0, 8.0, 11.0, 12.2, 12.6

Рис 5. Пример схемы распределения 44 полос по 12 полотнам.

Теперь у нас есть одна строчка чисел, в которой зашифровано распределение 44 полос по 12 полотнам. Эта строчка - это и есть наш бот.

Бот

Бот (особь, хромосома) - это одно решение задачи, закодированное в виде набора генов. Ген в нашем случае — это элемент в списке: индекс элемента соответствует индексу полосы, а значение — индексу полотна.

Индекс: 0 1 2 3 4 5 6 7 8 9 ...... 41 42 43
Бот:[0, 2, 0, 3, 10, 3, 9, 4, 1, 5, .... , 3, 11, 2]

ГА, изменяя числа в этом списке, фактически перекладывает полосы между виртуальными полотнами, отыскивая комбинацию с минимальной обрезью.

Теперь у нас есть чёткая цифровая модель:

Вход: список чисел (бот)
[0, 2, 0, 3, 10, 3, 9, 4, 1, 5, .... , 3, 11, 2]
Выход: такой же список чисел (бот), но с такими подобранными ГА значениями, которые задают оптимальную схему раскладки полос по полотнам с минимальной обрезью. Зная этот оптимальный вариант раскладки, мы можем сопоставить его с основным списком из 44 списков, в котором содержится вся информация о заказах и однозначно определить, как именно должны быть сгруппированы "подзаказы", чтобы была минимальная обрезь.

Осталось только научить ГА оценивать, насколько каждый такой список «хорош».

Технические ограничения: превращаем правила цеха в код

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

Главная хитрость не в самом алгоритме, а в том, чтобы научить его понимать правила нашего производства. Любое «так нельзя» или «так надо» мы превращаем в понятный компьютеру язык — математический штраф.

Ширина полотна (2060 мм) — величина постоянная. Суммарная ширина полос на полотне не может превышать ширину полотна. На (рис 6) на полотне #10 красная пунктирная линия — это предельная ширина полотна. Нарушение штрафуется.
Минимальная суммарная ширина полос на полотне не может должна быть меньше 1980 мм. Это требование технологического процесса. На (рис 6) на правом полотне #11 коричневая линия - это минимально необходимая суммарной ширины полос. Нарушение штрафуется.
Рис 6. Полотно #10 - "перебор" по ширине. Полотно #11 - "недобор" по ширине
На одном полотне — не больше двух разных длин изделий. Это требование технологического процесса. То есть, если на полотно попали 5 полос, в которых длины изделий: 1200, 1000, 1200, 1200, 1000, то все хорошо - две уникальные длины 1200 и 1000. А если 1200, 1000, 1200, 1200, 1050, то уникальных длин будет уже три варианта: 1200, 1000, 1050. Такой вариант недопустим. Штрафуется.
Изделия одного заказа собираются в полосу по длине. Это технологическое ограничение мы уже учли на этапе подготовки полос.

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

Философия проста: вы не программируете логику раскроя. Вы программируете правила игры, а ГА методом проб и ошибок учится в них выигрывать с минимальной ошибкой (обрезью).

Функция оценки (ошибки) «Насколько этот раскрой плох?»

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

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

Главное: чтобы алгоритм понимал, какой раскрой хороший, а какой плохой, мы не говорим ему «делай красиво». Вместо этого мы задаём чёткую математическую меру качества: меньше число - оптимальнее распределение полос по полотнам.

Работа function_error()

1. Расшифровка бота
Берём бота - список чисел (например, [0, 2, 1, 0...]) и группируем: какие полосы попали на какие полотна (см. рис 6)

2. Ошибка полотна
Для каждого полотна считаем одно число - ошибку для этого полотна.
Она состоит:
+ Площадь обрези (в мм²),
+ Штрафы за нарушение ограничений (тоже в мм²).
То есть штраф - это тоже ошибка, просто намеренно очень большая, чтобы математически показать неприемлемость варианта раскладки. Само понятие штраф здесь используется для удобства, чтобы очевидным образом отделить ошибки связанные с технологическим ограничениями.

Ошибки по длине и ширине (площадь обрези)
Площадь обрези состоит из разницы площади полотна и суммарной площади полос. Но считаем мы ее немного иначе: обрезь по длине + обрезь по ширине.
- Обрезь по длине
  На (рис 7) есть самая длинная, среди других, полоса с id 8.1. Длину полотна принимаем именно по самой длиной полосе. Остальные полосы на сколько-то не дотягивают до самой длинной. То, на сколько остальные полосы не закрывают всю площадь по длине - это и есть площадь (обрезь) по длине.
  Рис 7. Площадь, закрашенная красным - ошибка по длине
- Обрезь по ширине
  На (рис 8) видно площадь, выделенную желтым цветом - это то насколько суммарная ширина полос не перекрывает всю ширину полотна. Это и есть обрезь по ширине.
Рис 8. Площадь, окрашенная желтым - ошибка по ширине
Ошибки по длине и по ширине считаются отдельно, чтобы при необходимости можно было: по-разному их взвешивать и анализировать вклад каждой составляющей.
Штрафы за нарушение ограничений.
- Штраф за превышение ширины полотна:
  Суммируем ширины всех полос на полотне. Если сумма вышла за допустимые границы 2060 мм — даём огромный штраф (например, 1e16 мм2).
- Штраф за "недобор" суммарной ширины полос до минимального значения:
  Складываем ширину всех полос на полотне. Если сумма не дошла до минимально допустимой границы 1980 мм — даём огромный штраф (например, 1e16 мм2).
- Штраф за уникальные длины:
  Если на полотне больше двух уникальных длин изделий — снова огромный штраф (например, 1e16 мм2).
- Штраф за пустое полотно.
  Это ко��да ни одна полоса на попала на полотно. Здесь тоже большой штраф.

Ошибки и штраф суммируются для каждого полотна. Получаем ошибки каждого из 12 полотен.

3. Ошибка бота
Складываем ошибки всех 12 полотен. Полученное число и есть итоговая «плохость» этого варианта раскроя - этого бота.

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

Другие варианты — оцениваем не всё сразу

Описанный подход в функции ошибки оценивает сразу все 12 полотен. Их ошибки складываются и являются ошибкой бота. Есть другой вариант более гибкий - оценивать не всё сразу.

Если сразу суммировать ошибки по всем полотнам в нашем случае по 12, алгоритму может быть сложно найти направление для улучшения. Поэтому мы используем параметр lp - это количество лучших полотен среди 12. Берем например, 3 полотна с минимальными ошибками среди всех полотен. Суммируем только эти три ошибки и это есть ошибка бота.

Это помогает алгоритму быстрее подбирать 3 лучших полотна, не обращая внимания на остальные 9. Так алгоритм будет стараться сначала получить хорошие раскладки на трех полотнах.

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

При таком подходе мы оцениваем не всю раскладку целиком, а только её часть. Это создаёт риск преждевременно «забрать» лучшие варианты (полотна) из выборки полос, тем самым обеднив оставшуюся часть и существенно снизив шанс получить приемлемые решения для остальных полос.

Стратегия работы с выборкой полос сильно зависит от задач и ограничений конкретного производства. Иногда может оказаться целесообразной неочевидная или «странная» стратегия — здесь нужно экспериментировать. При этом важно предусмотреть такие регулируемые параметры, как lp для тонкой настройки.

Например, если задать lp = 9 при общем числе полотен 12, алгоритм будет стремиться оптимизировать именно эти 9 полотен, практически игнорируя оставшиеся 3. При этом вместо трех "хороших" есть шанс получить 5 - 7 "не плохих" раскладок по полотнам.

Еще вариант брать не сколько-то самых лучших, а определенное количество самых худших полотен, то есть сделать так, чтобы ГА намеренно фокусировался на группе полотнах с максимальной ошибкой. Такой приём смещает оптимизацию в сторону стабильности результата.

Выводы по функции ошибки function_error()

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

Псевдокод функции ошибки function_error()

ФУНКЦИЯ function_error():

  Вход:
    бот — описание, на каком полотне лежит каждая полоса

  Шаг 1. Группировка
    Разделить полосы по полотнам

  Шаг 2. Оценка каждого полотна
    Для каждого полотна:
      Если полос нет:
        ошибка = MAX

      Иначе:
        W = сумма ширин полос
        L = максимальная длина полосы
        S = суммарная площадь полос

        Если W вне допустимых границ:
          ошибка = MAX
        Иначе:
          обрезь_ширина = (ширина полотна − W) × L
          обрезь_длина = (W × L) − S

          Если используется > 2 длин:
            штраф = MAX
          Иначе:
            штраф = 0

          ошибка = обрезь_ширина + обрезь_длина + штраф

  Шаг 3. Агрегация
    Отсортировать ошибки полотен
    Сложить ошибки lp лучших полотен

  Выход:
    итоговая ошибка бота

Примечание:
Полный код этой функции и всего генетического алгоритма с примером можно скачать с Github. Код сделан в виде юпитер ноутбука для быстрого старта.

Как происходит обучение: один цикл эволюции

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

На начальном этапе создаем случайных ботов (вариантов раскроя). Например, 100 ботов. Это и есть одно поколение.

Шаг 1. Оценка (измеряем «плохость»)
Для каждого бота мы запускаем функцию ошибки (function_error), которая возвращает число — площадь обрези. Чем число меньше, тем лучше раскро��.

У нас получается своего рода таблица результатов:

Бот	Ошибка (обрезь, мм²)
`[0, 2, 1, 0, ...]`	1 250 000
`[9, 0, 11, 2, ...]`	980 000
`[2, 10, 2, 6, ...]`	2 100 000
...	...
`[2, 5, 0, 7, ...]`	1 750 000

Шаг 2. Ранжирование и отбор лучших (естественный отбор)
Сортируем таблицу по ошибке по возрастанию. Затем проводим «естественный отбор»: оставляем для размножения только определённое количество ботов с наименьшей ошибкой.

Допустим, мы решили оставить 40 лучших (nsurv = 40). Эти 40 ботов — наша элита, самые приспособленные решения текущего поколения. Остальные 60 отбраковываются.

Шаг 3. Формирование нового поколения (население должно оставаться постоянным)
Нам нужно вернуть популяцию к исходному размеру в 100 ботов. У нас уже есть 40 элитных. Значит, необходимо создать 60 новых ботов. Они будут рождены от выживших родителей - от элиты.

Шаг 4. Скрещивание (рождение потомков)
Чтобы создать одного нового бота-потомка:

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

Пример:

Родитель 1: [0, 2, 1, 0]
Родитель 2: [1, 0, 0, 2]

Потомок-бот (случайная комбинация): [0, 0, 1, 2] (первый ген от родителя 1, второй от родителя 2, третий от родителя 1, четвёртый от родителя 2).

Комментарии: существуют и другие методы скрещивания (это уже пространство для экспериментов с целью усовершенствования ГА), например:

Одноточечное скрещивание: выбирается случайная точка, и части бота берутся от разных родителей.
Двухточечное скрещивание: выбираются две точки, и средняя часть берется от одного родителя, внешние — от другого.
Симметричное/круговое скрещивание: гены чередуются поочередно от каждого родителя.
Смешанное (blend crossover, для численных значений): ген потомка = случайная комбинация значений родителей (например, среднее с небольшим шумом).

Шаг 5. Мутация (внезапные изменения)
После скрещивания применяем оператор мутации. С небольшой вероятностью (например, 5% — параметр mut) каждый ген потомка-бота может быть случайным образом изменён.

Пример:

Потомок-бот до мутации: [0, 0, 1, 2]
Потомок-бот после мутации: [0,3,1, 2] (второй ген случайно изменился на значение 3).

Мутация критически важна. Она вносит в популяцию новую генетическую информацию и позволяет алгоритму «выпрыгнуть» из локального минимума (из "одинаковости"), исследуя новые области решений.

Комментарии: мутации бывают разные (тоже пространство для экспериментов):

Случайная замена: ген выбирается случайным образом из допустимого диапазона значений. (это наш текущий вариант мутации)
Сдвиг: для числовых генов прибавляется/вычитается небольшое случайное значение.
Инверсия: порядок части хромосомы меняется на обратный.
Двойная мутация: два гена меняются одновременно для более значительных изменений.

Шаг 6. Новая популяция и повтор цикла
Мы добавили 60 новых потомков к 40 выжившим (элите). Теперь у нас снова 100 ботов. Это новое поколение.

Процесс повторяется: мы оцениваем всех 100 ботов нового поколения, снова отбираем лучших, скрещиваем их, применяем мутации и создаём следующее поколение.

Рис 9. Процесс обучения ГА. Графики изменения ошибок по эпохам.

Итог:
Один такой цикл называется эпохой. Алгоритм выполняет сотни или тысячи эпох (epohs = 2500). С каждой эпохой средняя ошибка в популяции стремится уменьшаться (см. рис 9 синий график), а лучший найденный бот становится всё лучше и лучше (см. рис 9 оранжевый график). Обучение завершается, когда достигнуто заданное число эпох или когда улучшения становятся незначительными.

Именно эта простая механика — оценка → отбор → скрещивание → мутация — лежит в основе способности ГА находить неочевидные и эффективные решения сложных задач.

Код генетического алгоритма (с комментариями):

#основной список полос
polosa =[[2750, 1830, 663, 1.0],  [2750, 1830, 663, 1.1],  [2750, 1830, 662, 1.2],  [2750, 1830, 662, 1.3],  [1080, 370, 1570, 2.0],  [1210, 310, 1410, 3.0],  .......  [1080, 370, 1521, 12.4],  [1080, 370, 1521, 12.5],  [1080, 370, 1521, 12.6]] 

# -----------------------------
# Основные параметры алгоритма
# -----------------------------


n = 100          # Общее количество ботов в популяции (размер популяции)
nsurv = 40       # Сколько лучших ботов выживает и переходит в следующую эпоху
nnew = n-nsurv   # Сколько новых ботов будет создано заново
epohs = 2500     # Количество эпох (итераций обучения)

mut = 0.5        # Вероятность мутации гена
# Эпохи, на которых уменьшаем вероятность мутации
eph_change_mut = [500, 1000, 1500, 2000]
# Новые значения вероятности мутации
new_mut = [0.1, 0.05, 0.01, 0.005]

# Длина бота — количество полос: 44 (количество генов),
# порядковый номер гена в списке - номер полосы,
# значение гена - номер полотна на которое распределили эту полосу)
l = len(polosa)

# --------------------------------
# Инициализация популяции
# --------------------------------

popul = []   # Список всех ботов (каждый бот — список генов)
val = []     # Значения функции ошибки для каждого бота

# Списки для построения графиков
plotmeanval = []  # Среднее значение ошибки по популяции
plotminval = []   # Минимальная ошибка (лучший бот)

# --------------------------------
# Создание начальной популяции
# --------------------------------
for i in range(n):

    genes = []  # Будущий бот

    # Для каждого гена выбираем случайное полотно,
    # на которое будет положена соответствующая полоса
    for iii in range(l):
        gen = random.randint(0, kol_listov - 1)
        genes.append(gen)

    print("genes ", genes)
    popul.append(genes)

# --------------------------------
# Основной цикл генетического алгоритма
# --------------------------------
for it in range(epohs):

    # Проверяем, нужно ли изменить вероятность мутации
    if it in eph_change_mut:
        idx = eph_change_mut.index(it)
        mut = new_mut[idx]

    val = []              # Очищаем список ошибок
    kol_pol = kol_listov  # Количество полотен

    # --------------------------------
    # Оценка всех ботов текущей популяции
    # --------------------------------
    for y in range(n):

        bot = popul[y]  # Берём очередного бота

        # Считаем ошибку раскроя для этого бота
        min_value_f, nomer_polotna, polosa = function_error(bot)

        val.append(min_value_f)

    # --------------------------------
    # Отбор лучших ботов
    # --------------------------------

    # Получаем:
    # - новую популяцию из лучших ботов
    # - отсортированный список значений ошибки
    newpopul, sval = getSurvPopul(popul, val, nsurv, 0)

    # Сохраняем статистику для графиков
    plotmeanval.append(sum(val) / len(val))  # среднее по популяции
    plotminval.append(sval[0])               # лучший результат эпохи

    # --------------------------------
    # Создание новых ботов (скрещивание + мутация)
    # --------------------------------
    for s in range(nnew):

        # Выбираем двух родителей из выживших
        botp1, botp2 = getParents(newpopul, nsurv)

        newbot = []  # Новый бот

        # Формируем нового бота по генам
        for j in range(l):

            # Берём ген от одного из родителей
            x = crossPointFrom2Parents(botp1, botp2, j)

            # С вероятностью mut происходит мутация —
            # ген заменяется случайным значением
            if random.random() < mut:
                x = random.randint(0, kol_listov - 1)

            newbot.append(x)

        # Добавляем нового бота в популяцию
        newpopul.append(newbot)

    # Обновляем популяцию
    popul = newpopul

"Усложненные" мутации

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

# Эпохи, на которых уменьшаем вероятность мутации
eph_change_mut = [500, 1000, 1500, 2000]
# Новые значения вероятности мутации
new_mut = [0.1, 0.05, 0.01, 0.005]

Такой поход может дать следующие эффекты:

Плавное снижение вероятности мутации по мере обучения помогает сбалансировать две противоположные задачи алгоритма: исследование и уточнение. В начале (высокая mut= 0.5) ГА активно исследует пространство решений — пробует непредсказуемые комбинации, чтобы быстро найти несколько перспективных областей (новые схемы раскроя, нетривиальные компоновки полос).

По мере накопления «хороших» решений высокая мутация начинает мешать — хорошие схемы постоянно разрушаются. Снижение mut на заранее выбранных эпохах (например, eph_change_mut = [500,1000,1500,2000] с new_mut = [0.1,0.05,0.01,0.005]) переводит алгоритм в режим локальной донастройки: он меньше рискует ломать рабочие решения и аккуратно улучшает их, снижая разброс и ускоряя сходимость к стабильному, воспроизводимому раскрою.

Результат: что мы получили на выходе?

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

Лучший бот — это уже готовое решение

Алгоритм возвращает нам последовательность чисел, например: [0, 2, 1, 0, 0, 1]. Это и есть оптимальный план раскроя в закодированном виде. Каждое число — это прямое указание: "Полосу с таким-то индексом разместить на полотне с таким-то индексом".

"Человекочитаемый" формат

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

Лучший бот:  [3, 6, 2, 4, 2, 2, 8, 0, 8, 5, 0, 4, 2, 7, 11, 11, 3, 3, 5, 11, 7, 3, 3, 0, 9, 9, 10, 10, 0, 8, 8, 2, 5, 11, 4, 10, 0, 10, 10, 3, 9, 9, 8, 9]

Распределение id заказов по полотнам: 
[[4.1, 4.4, 7.0, 7.5, 11.0], 
 [], 
 [1.2, 2.0, 3.0, 5.1, 7.8], 
 [1.0, 6.1, 6.2, 6.6, 6.7, 12.2], 
 [1.3, 5.0, 9.0], 
 [4.3, 6.3, 8.0], 
 [1.1], 
 [5.2, 6.5], 
 [4.0, 4.2, 7.6, 7.7, 12.5], 
 [7.1, 7.2, 12.3, 12.4, 12.6], 
 [7.3, 7.4, 10.0, 12.0, 12.1], 
 [5.3, 6.0, 6.4, 8.1]]

Расределение ошибок по полотнам: 
[88, 
10000000000000000000, 
18205010000000320, 
18232510000000424, 
24128010000001476, 
20200010000000296, 
18232500000000000, 
15687500000000002, 
91, 
89, 
75, 
20200010000000524]

Эти данные можно преобразовать в любой удобный формат, например в такой:

Полосы [4.1, 4.4, 7.0, 7.5, 11.0] - 88м2 обрези (полотно 0, штрафов нет)
Полосы [4.0, 4.2, 7.6, 7.7, 12.5] - 91м2 обрези (полотно 8, штрафов нет)
Полосы [7.1, 7.2, 12.3, 12.4, 12.6] - 89м2 обрези (полотно 9, штрафов нет)
Полосы [7.3, 7.4, 10.0, 12.0, 12.1] - 75м2 обрези (полотно 10, штрафов нет)

Если нас устраивает такой уровень обрези (меньше 100 м2), то список можно отдавать в производство. У нас осталось много полос с большими штрафами и что с ними делать обсудим далее.

Визуализация хороших и плохих результатов

Рассмотрим подробнее результаты на примере хороших и плохих вариантов.

Полотно с индексом 0 (№1)

Индекс полотна:  0 (полотно №1)
id подзаказов:  [4.1, 4.4, 7.0, 7.5, 11.0]
Длина (общая) и ширина подзаказов: [[1641600, 370], [1641600, 370], [1565200, 470], [1565200, 470], [1641600, 370]]
Список длин изделий: [1080, 1080, 1400, 1400, 1080]
Общая иширина полос: 2050 мм
Обрезь: 88 м2
Ошибка: 88 м2

На (рис 10) визуализация для полотна №1 ( индекс 0 ) с ошибкой 88 м2. Здесь нет штрафов и ошибка равна обрези: 88 м2.

Полотно с индексом 11 (№12)

Индекс полотна:  11 (полотно №12)
id подзаказов:  [5.3, 6.0, 6.4, 8.1]
Длина (общая) и ширина подзаказов: [[1562760, 460], [1568750, 350], [1568750, 350], [2020000, 560]]
Список длин изделий: [1080, 1250, 1250, 2020]
Общая иширина полос: 1720 мм
Обрезь: 1213 м2
Ошибка: 20200010000000524 м2

На (рис 11) визуализация для полотна №12 ( индекс 11) с ошибкой 20200010000000524 м2. Здесь два штрафа: больше двух уникальных длин [1080, 1250, 1250, 2020] + "недобор" по суммарной ширине (1720 мм < 1980 мм). Это дает большую суммарную ошибку для полотна. Площадь обрези уже не имеет значения так как вариант неприемлем.

Полотно с индексом 2 (№3)

Индекс полотна:  2 (полотно №3)
id подзаказов::  [1.2, 2.0, 3.0, 5.1, 7.8]
Длина (общая) и ширина подзаказов: [[1820500, 1830], [1695600, 370], [1706100, 310], [1563840, 460], [1563800, 470]] [длина (мм), ширина (мм)]
Список длин изделий: [2750, 1080, 1210, 1080, 1400]
Общая иширина полос: 3440 мм
Обрезь: -2191.9004 м2
Ошибка: 18205010000000320 м2

На (рис 12) визуализация для полотна №3 (индекс 2 ) с ошибкой 18205010000000320 м2. Здесь два штрафа: больше двух уникальных длин [2750, 1080, 1210, 1080, 1400] + "перебор" по суммарной ширине (3440 мм > 2060 мм). Это дает большую суммарную ошибку для полотна. Вариант не приемлем.

Итоги по результатам

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

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

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

Исходные "длины" заказов

Обратите внимание на (рис 13) столбец "График". В нем показаны относительные длины заказов (полос)

Рис 13. Визуальное сравнение длин заказов по столбцу График.

Дробление

Делим, например, по минимальной длине 1 641 600 мм заказа 10. И получаем 44 полосы (см. рис 14)

Рис 14. Разделено на 44 полосы по минимальной полосе 10

Теперь попробуем поделить по средней длине 6 253 200 мм заказа 5. И получаем 15 полос (см. рис 15)

Рис 15. Разделено на 15 полос по средней полосе (заказ 5)

Предположим, нам больше понравился вариант, когда 44 полосы, так как визуально (см. рис 14 столбец "График") они более менее близки по длине. Начнем с этого варианта. Потом можно будет попробовать разделить на 15 полос или любой другой вариант деления и "прогнать" через ГА.

ГА

Итак, у нас 44 полосы. Запускаем их в ГА. Попробуем хорошо заполнить 6 из 12 полотен (lp = 6). То есть и не пытаемся искать сразу 12 хороших заполнений и не слишком концентрируемся на двух - трех полотнах.

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

Первый запуск ГА. Результаты.

На (рис 16) верхняя часть таблица с результатами, на которой видно распределение по 4 полотнам с минимальной обрезью. Обрезь растет от 88 м2 до 107 м2. Дальнейшие варианты раскладки в таблице рассматривать нет смысла - там либо большая обрезь, либо неприемлемые варианты.

Рис 16. Первый запуск. Два хороших полотна.

Например, нас устраивает обрезь до 100 м2. Тогда забираем из нашей исходной выборки (44 полосы) 2 полотна с полосами id 4, 4.3, 4.4, 7.1, 7.4 и 4.1, 4.2, 5.1, 7.2
После этого изъятия у нас в следующем запуске ГА будет участвовать уже 44 - 10 = 34 полосы.

Второй запуск ГА. Результаты.

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

Вот что получилось:

Рис 17. Второй запуск. Одно хорошее полотно.

Алгоритм (см рис 17) подобрал еще одно полотно с обрезью меньше 100 м2. Заберем это полотно из выборки, а на самом деле уберем из 34 полос еще пять: id 7.5, 7.7, 12, 12.1, 12.2 и останется 34 - 5 = 29

Третий запуск. Результат.
Количество лучших полотен 2.

Рис 18. Третий запуск. Одно хорошее полотно.

Алгоритм (см. рис 18) нашел еще одно полотно с обрезью 89м2 и полотно 114м2 . А дальше идут уже проблемные варианты, например обрезь 1598м2. Точно забираем 89м2 и допустим у нас есть право немного нарушить пределы обрези и мы заберем 114м2 из выборки.
Тогда у нас остается не распределенных 29 - 10 = 19 полос

Четвертый запуск. Результаты.

Рис 19. Четвертый запуск. Нет хороших полотен.

На (рис 19) видно, что здесь мы достигли предела. Допустим обрезь 181 м2 мы себе позволить уже не можем.

У нас еще осталось достаточно полос, которые не оптимально распределить. Есть, по крайней мере, следующие варианты что с этим делать:

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

Заключение

Генетический алгоритм — это не абстрактная математика, а практический инструмент, который может экономить время и материалы. Как мы увидели, его суть проста: это «умный перебор», который учится на своих ошибках и постепенно находит всё более эффективные решения.

Важно:

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

Низкий порог входа (освоения алгоритма)

Вам не нужно быть специалистом по ИИ или data science. Достаточно базового Python и чёткого понимания своего производственного процесса. Начать можно с малого — одного типового з��каза, пары ключевых ограничений и нескольких сотен итераций алгоритма.

На Github рабочий юпитер ноутбук, который просто запустить и тестировать. Попробуйте подстроить его под ваши производственные задачи, чтобы оперативно оценить, насколько это может быть полезным для вас. А если что-то не понятно - любая языковая модель объяснит вам. что и как можно "поделать" с алгоритмом на Python.

Универсальность

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

Это может быть:

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

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

Что такое “бот” (решение)?
Что такое ошибка?

Как только определены эти два пункта, становится ясно, что именно нужно минимизировать или максимизировать, и ГА начинает работать одинаково — он перебирает варианты, сравнивает их по функции ошибки и постепенно улучшает решения.

Суть подхода не в конкретной задаче, а в правильной формулировке решения и ошибки.

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

P.s. ГА не решит нам всех проблем, НО

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

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

Код можно скачать с Github

Генетический алгоритм как инструмент инженера: практический кейс раскроя полотен