Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 15
Вся эта простыня кода и таблиц бесполезна без сравнения с полным перебором и каким-нибудь "жадным" алгоритмом.
Цель этой статьи не в том, чтобы доказать, что генетический алгоритм «лучше всех». Задача — показать, что он работает в условиях, близких к реальному производству: умеет учитывать технологические ограничения, переводить правила цеха в функцию ошибки и выдавать понятные, применимые на практике схемы раскроя. В этом смысле ГА — полезный инструмент в инженерном арсенале, который расширяет свободу решений для гораздо более сложных задач.
Вот именно, что бы показать что он работает, нужно его с чем то сравнить. Показать, что вот от полного перебора(идеального решения) мы получили всего то N% ошибки, и при этом отработали в M раз быстрее.
Для того, чтобы
показать, что он работает в условиях, близких к реальному производству
нужно было сравнить его с типовым решением. Например vpsolver + какой-то MIP солвер.
Ну или с точным решением, например, методом ветвей и границ.
А можно ли дискретизировать этот ГА, разбив условно говоря всё полотно или ужав в его в какой-нибудь квадрат 256 на 256 и восьмибитной арифметикой устроить ему Game of Life. В любом случае там floating pont с микронной точностью не нужен, важно минимизировать некий функционал. Ну и собственно арифметическими сдвигами добиться нахождение этого экстремума, включая SIMD или GPU.
А MIP применять не пробовали?
Я в подобной задаче применял Gurobi, но он платный и купить в РФ его сейчас непросто. Лицензия у меня была получена через швейцарский офис ЕвроХима.
Gurobi, хорошо справилась? Сколько примерно деталей нужно было разложить?
Gurobi, хорошо справилась?
Каждый день по несколько раз хорошо справляется.
Сколько примерно деталей нужно было разложить?
Я же сказал "подобной", а не "такой же". Объектов несколько сотен, до тысячи. Учитываются не только размеры, а несколько десятков constraints. Так что это скорее задача о рюкзаке (многомерном и мультипликативном), чем о раскрое. Просто задача о раскрое считается частным случаем задачи о рюкзаке и очень часто сводится к ней.
Нет не пробовали. Предположили, что когда деталей будет много - решение MIP сильно усложняется. Кроме того, мы хотели иметь возможность выбирать определённое количество лучших полотен, поэтому остановились на генетическом алгоритме.
Да, не факт, что время расчета задачи MIP будет сильно меньше времени существования вселенной ;).
С другой стороны, сам код MIP обычно получается простой и компактный. Ради интереса накидал логику раскроя листа - прикольно.
Кстати, считается же, что линейное программирование началось с работы Канторовича о фантресте. Там как раз делался раскрой листа фанеры. Но у Канторовича видов заготовок было всего два, так что вопрос о числе возможных вариантов раскроя решался с помощью элементарных рассуждений; содержательная задача была в другом.
Эта задача уже давно решена методами линейного программирования. Всякими целочисленными отсечениями с генерацией столбцов. Можно использовать какой-нибудь из опенсорсных решателей.
Перед вами лист материала и список деталей, которые нужно из него вырезать. Металл, ткань, пластик, стекло — не важно. Задача одна: разместить прямоугольники так, чтобы отходов было минимум.
Там где минимум по раскрою требуется, - редко можно назвать производством. Минимум на реальном производстве с складом остатков - это за месяц, три, полгода, год. Если есть роботизированный склад, или даже просто вменяемый склад остатков (не как у Роскосмоса, где требуется преемственность кладовщиков), то продвинутый алгоритм не особо и нужен. Здравый смысл и простой алгоритм вам дадут единицы процентов отходов. Заморачиваться но еще пол-процента оптимизации не особо имеет смысл, - стоимость оптимизации превысит стоимость сэкономленного.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Генетический алгоритм как инструмент инженера: практический кейс раскроя полотен