Содержание к диссертации
Введение
1. Задачи раскроя-упаковки: обзор методов решения 8
1.1. Задачи одно и двумерного раскроя-упаковки 10
1.1.1. Простейшая одномерная задача раскроя иупаковки 10
1.1.2. Задача прямоугольной упаковки в полубесконечную полосу 11
1.1.3. Задача прямоугольной упаковки в листы 12
1.1.4. Задача гильотинного раскроя 12
1.2. Обзор методов решения задач одно и двумерного раскроя-упаковки 13
1.2.1. Использование методов математического программирования 13
1.2.2. Применение методов комбинаторной оптимизации 14
1.2.3. Приближенные и эвристические методы 15
1.2.4. Вероятностные методы локального поиска оптимума 22
1.3. Основные задачи исследования 25
1.4. Выводы 25
2. Моделирование прямоугольных упаковок 27
2.1. Математические модели задач упаковки в полосу и на листы 27
2.2. Блочная модель упаковки 29
2.3. Способы кодирования упаковок 33
2.4. Алгоритмы декодеры. Блочный декодер 37
2.5. Свойство декодеров «реставрация» 43
2.6. Выводы 48
3. Генетические методы решения задачи упаковки 49
3.1. Общая характеристика генетических методов 49
3.2. Генетический блочный алгоритм 51
3.3. Оценка эффективности алгоритмов. Нижние границы 55
3.4. Выводы 58
4. Задача гильотинного раскроя 59
4.1. Математическая модель задачи раскроя полосы 59
4.2. Использование мультиметодной технологии. Гильотинный генетический алгоритм 60
4.3. Метод дискриминации простых эвристик 66
4.4. Выводы 67
5. Вычислительный эксперимент 68
5.1. Программная реализация алгоритмов 68
5.2. Исследование эффективности способов кодирования упаковки и алгоритмов декодеров при использовании генетических алгоритмов 70
5.3. Исследование декодеров. Проверка на наличие свойства «реставрации» 72
5.4. Исследование эффективности генетического блочного алгоритма. Сравнительный эксперимент с метаэвристическими алгоритмами 73
5.5. Исследование эффективности генетического гильотинного алгоритма с применением дискриминации эвристик 74
5.6. Выводы 77
Заключение 78
Список литературы 80
- Использование методов математического программирования
- Алгоритмы декодеры. Блочный декодер
- Оценка эффективности алгоритмов. Нижние границы
- Исследование эффективности способов кодирования упаковки и алгоритмов декодеров при использовании генетических алгоритмов
Введение к работе
Актуальность проблемы. Задачи раскроя-упаковки представляют собой важный раздел задач дискретной оптимизации, исследования операций и их приложений. Актуальность проблемы создания эффективных алгоритмов для решения задачи раскроя-упаковки двумерного прямоугольного ресурса обусловлена как широким практическим применением задач в различных отраслях производства, так и трудностью создания адекватных математических моделей и методов их решения.
Сложность решения задачи раскроя-упаковки обусловлена ее принадлежностью к классу NP-трудных задач комбинаторной оптимизации. Исследуемая задача является NP-трудной в сильном смысле, так как содержит в качестве подзадачи также NP-трудную задачу. Во многих случаях применение точных методов для ее решения невозможно из-за больших затрат вычислительного времени. В связи с этим большое значение приобретает разработка и исследование эвристических методов оптимизации, в том числе метаэвристик. В их числе широкое применение получили генетические алгоритмы. Известна асимптотическая сходимость таких методов. Однако практически оптимум достигается не всегда. Кроме того, до сих пор не известны способы построения нижних границ, позволяющие констатировать достижение оптимума. Вместе с тем на практике метаэвристики очень хорошо себя зарекомендовали. Качество полученного решения зависит не только от выбранного метода расчета раскроя-упаковки. Важную роль выполняют и способы кодирования и дешифровки упаковок.
Исходя из вышеизложенного, представляет интерес разработка и применение новых генетических алгоритмов для решения задачи раскроя-упаковки прямоугольных предметов на базе эффективных принципов кодирования упаковок. Важным является создание программной реализации, которая позволила бы решать производственные задачи за приемлемое время. Разработанное алгоритмическое и программное обеспечение становится конкурентоспособным в ряду точных и эвристических подходов. В этом состоит актуальность данной разработки.
Целью работы является разработка и исследование моделей и методов решения задачи прямоугольной упаковки и раскроя на базе блочной и мультиметодной технологий.
Для ее достижения были поставлены и решены следующие задачи:
Анализ вероятностных методов локального поиска оптимального решения для задач раскроя и упаковки;
Постановка задач прямоугольного раскроя и разработка моделей блочной структуры;
3. Разработка и исследование эффективности
тзкйОйГ
««метім 1
алгоритма для решения задачи прямоугольной упаковки;
Создание способа кодирования упаковок, удобного для применения разработанных методов оптимизации к решению исследуемой задачи;
Разработка алгоритмов-декодеров, формирующих упаковку на основе заданного кода;
Применение мультиметодной технологии дискретной оптимизации И.П. Норенкова для решения задачи прямоугольного гильотинного раскроя и исследование эффективности данного подхода;
Разработка программного обеспечения на базе предложенных методов. Анализ эффективности и характеристик разработанных алгоритмов на основе результатов численных экспериментов и сравнение эффективности методов с другими, описанными в литературе.
На защиту выносятся:
1. Блочный способ кодирования упаковки;
Генетический блочный алгоритм для решения задачи прямоугольной упаковки полубесконечной полосы;
Применение генетического блочного алгоритма для решения задач прямоугольной упаковки листов;
Алгоритм конструирования упаковки - «блочный декодер»;
Генетический алгоритм гильотинного раскроя на базе мультиметодной технологии дискретной оптимизации И.П. Норенкова с дискриминацией эвристик;
6. Компьютерная программа, реализующая разработанные алгоритмы;
7. Исследование эффективности предложенных методов на основе
результатов вычислительного эксперимента.
Научная новизна работы. Новыми в работе являются:
Блочный способ кодирования, основывающийся на блочной модели упаковки, который позволил применить для решения задачи новый тип алгоритмов декодирования. Предложенный способ является эффективным методом моделирования упаковки по ряду параметров: однозначность представления упаковки, простота модификации кода, учет всех пустых областей непосредственно в коде, возможность использования в других методах локального поиска оптимума;
«Блочный декодер» - новый алгоритм конструирования упаковки; для него доказано наличие свойства «реставрации»; может применяться в других метаэвристиках;
3. Генетический блочный алгоритм для задачи прямоугольнойупаковки;
Модифицирована идентификация элементов генетического метода: генов, аллелей, хромосом и процедур над ними; создан новый генетический алгоритм, показано, что его эффективность лучше по сравнению с
известными в литературе реализациями; 4. Применение принципов мультиметодной технологии дискретной оптимизации ИМ. Норенкова к задаче гильотинного раскроя. Введение дискриминации простых эвристик позволило увеличить эффективность алгоритма.
Практическая значимость работы: программная реализация генетического блочного алгоритма показала значительные преимущества перед известными классическими способами применения эвристических методов к задачам упаковки на достаточно широком классе задач. Это позволяет использовать разработанные алгоритмы при практических расчетах. Программное обеспечение зарегистрировано в РОСПАТЕНТ свидетельство № 2002610945; результаты работы внедрены в ОАО АСКОН, г. Москва и учебный процесс УГАТУ
Апробация работы. Работа выполнялась в рамках заданий РФФИ, проекты 99-01-00937, 01-01-00510. За цикл работ «Новые генетические алгоритмы решения задач двумерного раскроя и упаковки» присуждена Медаль РАН. За лучшую научную студенческую работу автор награжден медалью Министерства Образования РФ. Во время учебы в аспирантуре был удостоен стипендии Президента РФ и стипендии Правительства РФ. Результаты работы и отдельные ее разделы докладывались и обсуждались на следующих конференциях и семинарах:
Международная молодежная научно-техническая конференция «Интеллектуальные системы управления и обработки информации» (Уфа, 1999г.);
Республиканская научно-техническая конференция «Интеллектуальное управление в сложных системах» (Уфа, 1999г.);
Международная научная конференция «Моделирование, вычисления, проектирование в условиях неопределенности» (Уфа, 2000г.);
Международная конференция «Дискретный анализ и исследование операций» (Новосибирск, 2000г.);
Международная конференция INFORMS (USA, San Antonio, 2000г.);
Всероссийская научно-практическая конференция "Ресурсосберегающие технологии: математическое обеспечение оптимизационных задач в системах автоматизированного проектирования" ОПТИМ-2001 (Санкт-Петербург, 2001г.);
Международная конференция IFORS 2002 (UK, Edinburgh, 2002г.);
Международные конференции CSIT'2001, CSIT'2003 (Уфа, 2001г., 2003г.);
Международная конференция ESICUP (Европейская специальная группа по раскрою и упаковке) (Germany, 2004г.);
10. Семинары кафедры вычислительной математики и кибернетики
Уфимского государственного авиационного технического университета.
По теме диссертации опубликовано 16 работ, в том числе в центральной печати 7 статей.
Структура и объем работы
Использование методов математического программирования
Различаются задачи прямоугольной упаковки и гильотинного раскроя. В том и другом случаях требуется разделить большой прямоугольник на малые так, чтобы стороны прямоугольников были параллельны сторонам большого прямоугольника и выбранная функция цели достигала минимума. Задачи упаковки и гильотинного раскроя различаются технологией разделения. Гильотинность предполагает возможность только сквозных резов, параллельных кромкам раскраиваемого материала. Задачи гильотинного раскроя берут свое начало от одномерного случая и рассматривались как обобщение последней в первых работах Л.В. Канторовича, В.А. Залгаллера и P. Gilmore, R. Gomory. Методы, алгоритмы и технологии, разработанные для задач 1DCS адаптированы на случай гильотинного (2- и 3- мерного) раскроя. Подробно эта задача в условиях массового и серийного производства описана в работах Э.А. Мухачевой [26], [28] в России и J. Terao, R. Lindeman & G. Scheithauer [81] в Германии. Метод склейки И.В.Романовского, разработанный вначале для задач линейного раскроя, также был обобщен на случай гильотинного раскроя [36]. Для решения основной задачи используются методы линейного и динамического целочисленного программирования. Проблема генерации раскроя сводится к решению задачи о загрузке рюкзака. В 2002 г. подход реанимирован совместными усилиями германских и российских ученых [42].
Методы, основанные на линейном целочисленном программировании, оказались приемлемыми для решения задач линейного и гильотинного раскроя. Что касается классов задач негильотинной упаковки, то алгоритмы LP вряд ли можно считать подходящими для их решения и успешных прецедентов в отечественной и зарубежной литературе мы не встречали. Задачи ВР являются классическими представителями NP-трудных проблем и для их решения, как правило, применяются методы полного перебора с отсечением неперспективных вариантов. Еще в 1973 г. D.Johnson представил близкие к оптимальным алгоритмы одномерной упаковки. И.В.Романовский и Н.П.Христова предложили для решения дискретных минимаксных задач метод дихотомии [37], который получил развитие и для решения задач ВР в работе С.В.Кацева [15]. В 1977 г. И.В.Романовским представлена общая идея переборного метода для решения общей экспоненциальной задачи и предложена его конкретизация в виде метода «ветвей и границ» (Method Branch and Bound, MBB) для решения задач упаковки [35]. В дальнейшем метод получает развитие за счет введения процедур сокращения перебора в работах В.М.Картака и Э.А.Мухачевой [30], [76]. Независимо за рубежом выходит серия статей S.Martello & P.Toth, посвященная разработке улучшенных версий МВВ, для решения 1DBP [71]. Размерность задач, разрешимая этими алгоритмами, не велика ( 200).
Большинство существующих комбинаторных методов решения задач прямоугольного негильотинного раскроя, 1.5DBP и 2DBP, и размещения объектов сложных форм сводятся к перебору всего множества допустимых решений. Методы улучшенного перебора объединены и для этих задач под названием «метода ветвей и границ». В 1986 г. Ю.Г.Стоян и С.В.Яковлев описали общую схему метода и привели основные алгоритмы [38]. Другой подход к переборным методам решения 1.5DBP и 2DBP разработан в середине 80-х годов А.И. Липовецким [18]. На основе понятия «зоны» доказывается, что для любой упаковки прямоугольников можно указать такой их порядок, при котором каждый следующий прямоугольник не пересекается ни с одной из зон предыдущих (топологическая сортировка). Метод зон реализован в 1988 г., усовершенствован и исследован в 2001 г. В.В. Бухваловой (С.Петербург) [4]. Несколько точных алгоритмов, базирующихся на МВВ, предложено S. Martello & D. Vigo [72].
Несмотря на многообразие различных подходов к созданию комбинаторных алгоритмов, размерность решаемых задач редко превосходит т=20. ЭТО связано с тем, что пока не найдено способа определения эффективной нижней границы и для доказательства оптимальности приходится перебирать все возможные варианты. Новые нижние границы и их связь с методом «ветвей и границ» установлены P.Schwerin & G.Waescher [79]. M.Boschetti в 2002 г. предложил несколько новых методик подсчета нижней границы [45]. Это позволило значительно расширить размерность задач (в отдельных случаях до 100).
При изучении задач С&Р и разработке методов их решения особая роль отводится обобщенной проблеме загрузке рюкзака, подробно описанной S. Martello & P.Toth еще в 1990г [71]. Бинарная, ограниченная, неограниченная,двумерная задача рюкзака находят свое применение в составе алгоритмов для решения задач раскроя и упаковки.
В работе Е. Coffman, M.Garrey & D.Jonson, опубликованной в 1984г., приведен обзор приближенных однопроходных методов упаковки контейнеров [48]. Ими описан принцип самого худшего случая для он-лайн и офф-лайн вариантов однопроходных эвристик. Асимптотическое отношение наихудшего представления алгоритмов первый подходящий (First Fit, FF) и лучший подходящий (Best Fit, BF) не превосходит 1,22. Лучший из алгоритмов дает отношение не более чем 1,15. Результаты такого рода можно перечислять и далее. Например, этой проблеме посвящена статья D.Jhonson, A. Demers and all [64]. Ими установлены гарантированные оценки относительной погрешности в наихудшем случае. Обзор эвристических методов для решения задач прямоугольной упаковки представлен в статьях A.Lodi, S.Martello & D.Vigo в 2002г. [67], [68]. Там приведены известные детерминированные эвристики: следующий по убыванию длины (NFDL); первый по убыванию подходящей длины (FFDL); лучший подходящий по убыванию длины (BFDL) (см. рис. 1.3).
Алгоритмы декодеры. Блочный декодер
Внесение в детерминированный алгоритм элементов случайности повышает его результативность. Так, например, повысилась эффективность упомянутых выше алгоритмов SVC и DS после внесения в них элементов стохастики [32], [24]. А применение А.Р.Усмановой недетерминированных простых эвристик в простой вероятностной схеме превзошло все ожидания [39]. Бурное развитие вероятностных методов локального поиска оптимума началось 20 лет назад с появлением метаэвристик для решения NP-трудных задач, систематическое обоснование и характеристика которых приведены в 1996 г. в книге под редакцией E.Aurts, J.Lenstra [40]. В России обзор вероятностных методов локального поиска оптимума для NP-трудных задач сделан в 2001 г. Ю.А. Кочетовым [17]. В обзоре обсуждаются общие схемы алгоритмов поиска с запретами, имитация отжига и генетических алгоритмов. Показано, что эти разные по своей структуре алгоритмы используют общую математическую конструкцию конечных цепей Маркова. Это свойство гарантирует сходимость по вероятности наилучшего найденного решения к оптимальному решению задачи.
Первыми среди метаэвристик для задач раскроя-упаковки стали применяться генетические алгоритмы. В этой связи хорошо зарекомендовали себя работы 1992-2000 гг., например, Е. Folkenaur [54], [55]. Он ввел процедуру группирования в классическую схему. Для решения задач 1DBP эффективность генетического (группового) алгоритма до сих пор остается непревзойденной. Основные генетические структуры (ген, аллели, хромосома) и операции (кроссовер и мутация) определены многими авторами, в том числе в России, Д.И. Батищевым [2]. Возможны различные способы кодирования и приемы идентификации простейших структур. Это порождает различные классы генетических алгоритмов. Классический генетический алгоритм для решения задач 1.5DBP и 2DBP представлен, например, в работах D. Liu & H.Teng [65]; Н Cehring & A.Bortfeld [58]; А.С. Мухачевой, А.В. Чиглинцевым и М.А. Смагиным [23]. Они различаются деталями и программной реализацией. Эффективность классического алгоритма зависит от используемого декодера. Исследован алгоритм D. Liu & H.Teng с родным декодером, нижний-левый, блочным, парных списков, замещения и некоторыми другими. Худшие результаты во всех случаях показал усовершенствованный D. Liu & H.Teng декодер нижний-левый (IBL). Генетический блочный GBA алгоритм и его модификации разработаны Э.А. Мухачевой, А.С. Мухачевой, А.В, Чиглинцевым в 1999 г. [22]. В этом алгоритме генами являются блоки -прямоугольные фрагменты упаковки. И.П. Норенков в 1999г. предлагает использовать в качестве генов простые эвристики [34]. Результаты тестирования оказались сопоставимы с блочным алгоритмом при количестве прямоугольников т 250 и превосходят все другие тестируемые алгоритмы при 250 m 1000. Эта технология использовалась А.С. Мухачевой и А.В. Чиглинцевым в 2000г. для задач гильотинного раскроя [22]. Генетические алгоритмы успешно разрабатываются и для решения задач нестинга [56]. Генетические алгоритмы представляют основной предмет настоящей диссертации.
В работах, посвященных применению метаэвристик к решению задач С&Р, обычно описываются несколько алгоритмов, но как правило, с одним и тем же декодером или в сочетании с несколькими однопроходными эвристиками. Так, P. Chen & Y. Chen описывают генетический алгоритм и метод имитации отжига с декодером парных последовательностей [46]. Приведенные там результаты эксперимента указывают на существенное преимущество генетического алгоритма по сравнению с методом имитации отжига. В статье Е. Hopper, В. Turton представлены три метаэвристики: имитация отжига, генетический и наивный эволюционный алгоритм [62]. Все они используют декодер нижний-левый. Лучшие результаты были получены методом имитации отжига. Однако противоречия в работах указанных авторов, здесь нет. Предпочтение генетического алгоритма в одной работе и имитации отжига в другой объясняются применением разных декодеров, различной областью экспериментальных данных, а также различной стратегией построения окрестности. В работах А.С. Мухачевой, А.В. Чиглинцева, М.А. Смагина показано влияние декодеров на эффективность упаковок в рамках классического генетического алгоритма [23]. Феномен генетического алгоритма И.П. Норенкова, который работает без декодера, нашел подтверждение в статье О. Faroe, D. Pisinger & М. Zachariasen [53] и других работах.
Среди эволюционных алгоритмов особое место занимает специальная блочная технология конструирования алгоритмов локального поиска оптимума в задачах 1.5D и 2DBP. Эта технология развита в работах А.С. Мухачевой [19], [20], [21], [22], [31]. Начало в этом направлении положено Э.А. Мухачевой, А.С. Мухачевой, А.В. Чиглинцевым [33]. Там используется только одна, вертикальная блок-структура. С 2002 г для конструирования алгоритмов А.С. Мухачевой и В.М. Картаком предлагается схема парных списков, которая базируется на двух структурах: вертикальной и горизонтальной. А.С. Мухачева использует язык блок-структур для конструирования алгоритмов локального оптимума [21], а В.М. Картак - связных матриц для алгоритма типа ветвей и границ [14].
Основной задачей исследования в рамках настоящей работы является разработка вероятностных методов решения задач раскроя-упаковки 1.5DBP и 2DBP, в частности генетических алгоритмов, включая разработку основных процедур «скрещивание» и «мутация». Применение мультиметоднои технологии решения задач дискретной оптимизации И. П. Норенкова для решения задачи прямоугольного гильотинного раскроя. Создание способов кодирования и расшифровки упаковок. Исследование эффективности применения разработанных методов к различным классам задач: разработка программного обеспечения; проведение численного эксперимента; построение нижних границ; оценка отклонения от нижней границы.
Оценка эффективности алгоритмов. Нижние границы
Идея генетического алгоритма по аналогии с живой природой состоит в организации эволюционного процесса, целью которого является получение оптимального решения. При этом необходимо идентифицировать законы эволюции так, чтобы быстрее достичь оптимальное или близкое к нему, решение. Основным понятиям и методам конструирования генетических алгоритмов посвящена работа Батищева Д.И. [2]. Генетический алгоритм упаковки работает с цифровыми строками (кодами). Базовыми понятиями алгоритма являются ген, хромосома, популяция. Хромосома (запись, фрейм) -это одно из возможных решений, закодированное определённым образом. Хромосомы состоят из более мелких элементов - генов (полей, слотов). Хромосомы преобразовываются за счёт модификации генов {аллелей). Операции производятся не над одной хромосомой, а над целым набором хромосом. Этот набор называется популяцией. Аллелями, то есть значениями генов, как правило, являются значения проектных параметров.
Направленный перебор решений осуществляется с помощью генетических операторов кроссовера, мутации, селекции. Сначала формируется случайным образом исходное поколение, состоящее из к хромосом (объектов).
Выбор начальной популяции не влияет на сходимость процесса в асимптотике. Однако формирование хорошей начальной хромосомы, а вслед за ней начальной популяции сокращает время достижения оптимума.
На каждом шаге эволюции с помощью оператора селекции выбираются два решения (родители). Оператор скрещивания (кроссовер) строит новое решение, которое добавляется в популяцию, а решение с наихудшей оценкой удаляется из нее. Если оценка меняется мало или по истечении заданного количества итераций, текущее решение подвергается небольшим случайным изменениям, мутации.
Для решения задач 1.5DBP и 2DBP в литературе представлен классический генетический алгоритм, например, в работах D. Liu & H.Teng [66]; Н Cehring & A.Bortfeld [58]. Здесь і[я], i=l,m- индексы прямоугольников. Они идентифицируются как гены. Перестановка - последовательность, в которой прямоугольники расположены на полосе в соответствии с определенными правилами. Мы предполагаем, что і [л] имеет знак, который показывает направление размещения прямоугольника і[7і] (проектное решение). Аллели генов (+i[7t]) и ( і[7ф. Каждая родительская пара создает двух новых потомков с помощью оператора скрещивания (кроссовер). Процесс создания заключается в следующем: Пусть лт, щ - два приоритетных списка, соответствующих паре родителей и nrnew, 7cjnew - два новых PL, созданные скрещиванием. Сначала выбираются два случайных числа g и q, l g, q n. Начиная со случайной позиции g скрещивающий оператор копирует q элементов из ш в Ttrnew. Потом оставшиеся позиции в Ttmew заполняются другими элементами из ту в той же последовательности, в которой они встречаются в этом списке. Аналогично заполняется Ttjnew. Пример. По данным PL родителей на основе оператора скрещивания получить потомков: PL1: яг = {1, -2, 3, 4, -5, 6}, PL2: TCJ = {-6, 4, 2, 5, -3, 1}, и если g = 2, q = 3, тогда: 1 [mriew] = g[7cr] = 2 [тег ] = -2, 2[7crnew] = (g+l)[rcr] = 3, 3[:irnew] = (g+2)[7tr] = 4, 4[:rmew] = l[7tj] = -6, 5[7rrnew] = 4[nj] = 5, 6[7trnew] = Таким образом, in-new = {-2, 3, 4, -6, 5, 1}. Используя этот же метод находим Ttjnew = {4, 2, 5, 1, 3, 6}. Оператор мутации, использованный в данном алгоритме, состоит из двух частей. Первая часть обменивает два случайных элемента или блока каждой новой перестановки с небольшой вероятностью р . Другая часть меняет знак каждого элемента в новых перестановках, т.е. поворачивает каждый прямоугольник на 90, с небольшой вероятностью рИ2 Разработан генетический блочный алгоритм (Genetic Block Algorithm, GBA). Пусть задана исходная информация для решения задачи 1.5DBP. На ее основании формируется задача линейного раскроя CSP. Решая эту задачу с учетом ограничений 1 (разнородность) и 2 (продолженность) (см. п. 2.2 работы), получаем d.ROLC и значение Л функции цели. Плану линейного раскроя отвечает блок-структура, вообще говоря, не являющаяся упаковкой (см. рис, 3.1). Там прямоугольники 5 и 7 оказываются разорванными. Назовем ее псевдоупаковкой. Длина псевдоупаковки Л совпадает с квазиграницей RP.
Как уже отмечалось, что если направления прямоугольников не фиксированы, то в CSP также возможны два случая: Al=wi;bj=l/ или Х] -1.; bt = wt. Два альтернативных (взаимноперпендикулярных) направления рассматриваются в качестве аллелей гена, отвечающего за і-й прямоугольник. Решая задачу CSP с применением генетических процедур, мы получим не только блок-структуру псевдоупаковки с квазиграницей Л, а и рекомендуемое направление для каждого прямоугольника і = 1, т .
Генетический алгоритм решения задачи 1.5DBP интерпретируется как эволюционный процесс, связанный с перестановкой элементов в блоках с целью отыскания глобального минимума для L [23], [33].
Каждой допустимой упаковке RP соответствует блочный код. Блоки расположены в установленном v=l,2,... порядке и связаны друг с другом. Это позволяет интерпретировать их как гены. Тогда блочный код, соответствующий d.ROLC, можно интерпретировать хромосомой, содержащей сцепленные между собой гены (блоки), которые расположены «слева-направо». Согласно хромосомной теории наследственности передача качественных принципов, закодированных в генах, будет осуществляться через хромосомы от «родителей» к «потомкам».
Исследование эффективности способов кодирования упаковки и алгоритмов декодеров при использовании генетических алгоритмов
В качестве критерия эффективности упаковки применяется «коэффициент раскроя» (Cutting Coefficient, СС) равный отношению полезной площади ко всей затраченной. Для безотходной упаковки СС=100%. Среди генетических алгоритмов лидируют «блочный генетический» и «мультиметодный генетический» алгоритмы.
Целью эксперимента является исследование зависимости эффективности генетического алгоритма, разработанного на основе мультиметодной технологии И.П. Норенкова, с учетом применения метода дискриминации простых эвристик.
Необходимо найти соотношение вероятностей для простых эвристик, которое обеспечит наилучшую эффективность для генетического алгоритма. В данной работе используется метод оптимального пассивного поиска.
Вероятности ph удовлетворяют следующим условиям, pi 0, і = \,К и Выделим из области допустимых значений пробные точки, для которых будет оценена эффективность алгоритма. Для этого возьмем все возможные комбинации р/ с шагом 0.1. Второе условие сильно сужает область допустимых значение/?,. Так для шага 0.05 количество допустимых точек 1771, для 0.1 - 286 точек, для 0.2 всего 56 точек. Для каждой выбранной точки производятся тесты, заключающиеся многократном прогоне генетического гильотинного алгоритма с вероятностями эвристик соответствующими точке, в качестве результата принимается среднее значение.
Рассмотрим класс задач с набором предметов различных размеров от малых 5% до 95% ширины полосы. Верхнее и нижнее ограничение по ширине и по длине прямоугольников равны 0.05 и 0.95 соответственно. Количество прямоугольников 100. Результаты представлены в таблице 3.
Первая строка соответствует оригинальной методике И.П. Норенкова, здесь все эвристики «равноправны», их вероятности равны. В последующих строках представлены соотношения эвристик, обеспечивающие наилучшие значения коэффициента раскроя, более 96%. В последней строке приведены усредненные значения вероятностей, для такого соотношения результат стабильно укладывается в пределы (96,23%;96,78%). Применение дискриминации эвристик позволило улучшить результативность алгоритма более чем на 2%, без увеличения времени вычисления. Для разных классов задач соотношения эвристик получаются различными. Особым образом ведут себя эвристики на следующем классе задач.
Рассмотрим класс сложных задач (триплеты) v/=0.3, v2=0.4, w/=0.3, w2=0A. Результаты представлены в таблице 4.
Выявляется проблема с использованием «жадной» эвристики GR. Это объясняется возникновением большого перебора при решении задачи загрузки рюкзака и соответственно большими временными затратами. А так как оцениваются результаты достигаемые за одинаковое время, то большая вероятность соответствующая GR приносит плохие результаты. Однако полное отсутствие эвристики сразу ухудшает результат в среднем на 1 - 2%.
Вычислительные эксперименты также показали отсутствие значимой зависимости между соотношением вероятностей эвристик и количеством прямоугольников. Поэтому подготовка рекомендаций по интенсивности применения эвристик может быть осуществлена для небольшого количества m различных заготовок. Далее полученное соотношение может быть использовано на больших примерах, относящихся к схожему классу задач по типоразмерам прямоугольников. 5.6. Выводы
Для выявления преимуществ, предложенных в работе методик, проведено значительное количество вычислительных экспериментов. Здесь приведены результаты ключевых экспериментов, наиболее полно дающие представление об эффективности новых разработок. Заключение
Задачи прямоугольной упаковки и прямоугольного гильотинного раскроя представляет собой важный раздел задач дискретной оптимизации и исследования операций. От качества полученного решения зависит, во-первых, эффективность использования ресурсов; во-вторых, продуктивность использования оборудования; в-третьих, время проектирования и, соответственно, производительность труда.
Развитие генетических алгоритмов для решения задач 1.5DBP и 2DBP проведено на базе блочной модели упаковки, а задачи гильотинного раскроя 1.5DCSP на базе технологии И.П. Норенкова с использованием простых эвристик. В первом направлении разработан генетический блочный алгоритм GBA с блочном декодером IBD, он показал лучшие результаты при сравнительном эксперименте. Совершенствование генетического алгоритма для задачи упаковки реализовалось за счет новой идентификации элементов генетического метода: генов, аллелей, хромосом и процедур над ними. Во втором направлении совершенствование известной методики достигнуто за счет применения дискриминации простых эвристик.
Основные результаты работы и выводы 1. Разработана блок-структура упаковки, представляющая ее блочную модель. Показано, что блочная модель ориентирована на создание новых эффективных алгоритмов локального поиска оптимума; 2. Разработан генетический блочный алгоритм, показавший лучшую эффективность по сравнению с известными генетическими алгоритмами и другими методами локального поиска на многих классах задач; 3. Предложен блочный способ кодирования упаковок, он применен при разработке генетического блочного алгоритма и может быть использован в других разработках в связи с его инвариантностью. 4. Разработан новый алгоритм «блочный декодер», доказано наличие свойства «реставрации»; 5. Предложен способ применения мультиметодной технологии дискретной оптимизации И. П. Норенкова к задаче прямоугольного гильотинного раскроя; дискриминация простых эвристик значительно повысила эффективность метода; 6. Разработано алгоритмическое и программное обеспечение. Проведены вычисленные эксперименты. Их результаты позволяют сделать заключение об эффективности предложенных методов.
