'

«Построение рациональных планов продольного раскроя рулонных материалов на основе гибридных генетических алгоритмов»

Понравилась презентация – покажи это...





Слайд 0

«Построение рациональных планов продольного раскроя рулонных материалов на основе гибридных генетических алгоритмов» Доклад В. Н. Балабанов, аспирант, ДонНТУ


Слайд 1

Задачи рационального раскроя (РР) Требуется сформировать такой план раскроя, который обеспечит требуемый ассортимент заготовок при минимальном расходе материала. Формальная постановка задачи впервые предложена Канторовичем в 1939 году.


Слайд 2

Уточним терминологию План раскроя — допустимое решение задачи Раскройная карта — отдельный компонент плана раскроя


Слайд 3

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


Слайд 4

Раскройная карта w1 x 2, w2 x 1, w3 x 1, w4 x 0 > (2, 1, 1, 0)


Слайд 5

План раскроя Перечень всех используемых раскройных карт с указанием рулонов: (2, 1, 1, 0) (1, 0, 3, 0) (2, 1, 0, 2) …


Слайд 6

Методы решения задач РР Точные: метод ветвей и границ, метод отсечений, динамическое программирование зачастую основаны на работе с ЦЛП моделью общего вида.


Слайд 7

Методы решения задач РР Эвристические: отложенная генерация столбцов, последовательные эвристические процедуры, конструктивные эвристики Метаэвристические: SA, TS, EA, ACO, PSO и т.д.


Слайд 8

Многокритериальные задачи РР Продольный раскрой выполняется с помощью дисковых ножниц


Слайд 9

Характерные особенности Переналадка дисковых ножниц на новую раскройную карту является трудоемкой операцией. Два критерия: минимизировать потери материала в отход; сократить общее количество раскройных карт в плане (использовать их многократно);


Слайд 10

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


Слайд 11

Структура хромосомы


Слайд 12

Генетический алгоритм Для генерации раскройных карт решается вспомогательная задача рюкзачного типа Используется одноточечный кроссовер Мутация исключает некоторый ген из состава хромосомы Целостность хромосом восстанавливается с помощью упрощенной последовательной эвристической процедуры


Слайд 13

Генетический алгоритм В целевой функции используется линейная «свертка» Эволюционный подход — лишь один из возможных


Слайд 14

В настоящее время Создана программная реализация Проведено предварительное тестирование Подход доказал свою состоятельность


Слайд 15

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


Слайд 16

Спасибо за внимание! В. Н. Балабанов akavrt@gmail.com > Связь:


×

HTML:





Ссылка: