Содержание к диссертации
Введение
1. Задачи раскроя-упаковки: аналитический обзор моделей и методов их решения 9
1.1 Задача одномерного раскроя-упаковки 10
1.1.1 Методы, использующие математическое программирование 13
1.1.2 Комбинаторные методы 14
1.1.3 Приближенные и эвристические методы 14
1.1.4 Методы локального поиска оптимума 15
1.1.5 Заключение по задаче одномерного раскроя-упаковки: 16
1.2 Задача прямоугольного раскроя-упаковки 16
1.2.1 Методы, использующие математическое программирование 17
1.2.2 Комбинаторные методы 18
1.1.1 Приближенные и эвристические методы 19
1.2.1 Методы локального поиска оптимума 19
1.3 Задача упаковки трехмерного контейнера и ее постановки 20
1.3.1 Технологические ограничения в задаче упаковки контейнера 22
1.3.2 Комбинаторные методы 23
1.3.3 Эвристики и методы локального поиска оптимума 23
1.3.4 Выводы по задаче контейнерного раскроя-упаковки: 27
1.4 Выводы 28
2. Математическая модель контейнерной упаковки и однопроходные методы ее решения 29
2.1 Математическая модель задачи контейнерной упаковки 29
2.2. Блочная структура трехмерной упаковки и ее свойства 32
2.2.1 Блок-структуры прямоугольной упаковки. 34
2.2.2 Задачи прямоугольно-ориентированного линейного раскроя 39
2.2.3 Блок-структура RP, адаптированная для контейнерной упаковки 47
2.3 Блочный декодер 50
2.4 Учет технологических ограничений в блочном декодере 57
2.4 Выводы по второй главе 59
3. Методы локального поиска оптимума с использованием блочного декодера 60
3.1 Метод случайных перестановок приоритетного списка 60
3.2 Генетические методы. Классический генетический алгоритм 61
3.3 Генетический алгоритм с блочным декодером 63
3.4 Эволюционный алгоритм (1+1) 64
3.5 Нижние границы для задач раскроя упаковки 66
3.5 Выводы по третьей главе 71
4. Численные эксперименты 72
4.1 Реализация программного обеспечения 72
4.2 Выбор целевой функции для численных экспериментов 75
4.2 Выбор параметров алгоритмов 76
4.3 Численные эксперименты 78
4.3.1 Эксперимент на случайно сгенерированных примерах 78
4.3.2 Сравнительный эксперимент с другими методами решения поставленной задачи 82
4.4 Выводы по четвертой главе 86
Заключение 87
Литература
- Методы, использующие математическое программирование
- Блочная структура трехмерной упаковки и ее свойства
- Генетические методы. Классический генетический алгоритм
- Выбор целевой функции для численных экспериментов
Введение к работе
Диссертационная работа посвящена моделированию и разработке методов расчета для задачи трехмерной упаковки контейнера, использующих блочный декодер; программной реализации разработанных методов и численному исследованию их эффективности.
Актуальность проблемы. В научной и производственной деятельности часто встречаются ситуации раскроя и упаковки встречаются очень часто: это задачи раскроя материала на заготовки различных форм и размеров, и задачи размещения совокупности предметов на ограниченной площади или в ограниченном пространстве. Многие другие проблемы также сводятся к ситуациям раскроя и упаковки. Среди многообразия постановок задач раскроя и упаковки самостоятельный интерес представляют задачи упаковки параллелепипедов (30ВРР). К таким задачам относятся, например, оптимизация перевозки и складирования грузов, планирование помещений, проектирование систем, конструктивно выполненных в виде набора блоков, компоновка деталей. К рассматриваемым проблемам сводится таюке и ряд задач планирования и распределения ресурсов. Несмотря на конкретное практическое применение, круг работ по решению задач параллелепипедной упаковки невелик. Это объясняется сложностью задач и высокой трудоемкостью их решения. Поэтому является актуальной разработка эффективных алгоритмов решения задач раскроя-упаковки параллелепипедов.
Задача раскроя-упаковки принадлежит к классу NP-трудных проблем, то есть для ее точного решения не известно алгоритма полиномиальной сложности. Более того, рассматриваемая задача является NP-трудной в сильном смысле, так как содержит NP-трудную задачу в качестве подзадачи. До сих пор не разработано эффективных и достаточно точных способов расчета нижних границ для данной задачи, позволяющих определить достижение оптимума.
Таким образом, точные алгоритмы сводятся к полному перебору вариантов. В связи с этим, использование точных методов для решения задачи раскроя-упаковки часто оказывается нецелесообразным и невозможным по причине больших затрат времени. Поэтому большое значение уделяется разработке и исследованию эвристических методов оптимизации. Одним из перспективных направлений является разработка метаэвристических алгоритмов, основанных на известных метаэвристических стратегиях, с успехом используемых для решения многих задач дискретной оптимизации. Для большинства метаэвристик доказана их асимптотическая сходимость, что является важным доводом в пользу их активного использования.
Целью работы является разработка и исследование моделей и методов решения задач контейнерной упаковки на базе блочной технологии и реализация комплекса программ, ориентированных на достижение рационального решения в ограниченное время.
Задачи, поставленные для достижения цели работы:
Рассмотреть постановки основных задач трехмерной упаковки, описать их математические модели;
Разработать блочный способ моделирования трехмерных упаковок. Сформулировать его основные свойства и установить связь с другими способами кодирования;
Разработать блочный декодер конструирования трехмерных упаковок на базе применения простых стратегий.
Выбрать эволюционные алгоритмы для локального поиска оптимальных упаковок и осуществить их адаптацию к решению задачи с блочным декодером конструирования упаковок;
Разработать программное обеспечение, реализующее предложенные методы и алгоритмы;
6. Провести численный эксперимент с целью исследования эффективности предложенных алгоритмов. На защиту выносятся:
Блочный способ кодирования трехмерных упаковок. «Блочный декодер» - алгоритм конструирования блочной структуры упаковки по приоритетному списку (перестановке параллелепипедов).
Эволюционные методы, работающие с блочным декодером для решения поставленной задачи.
Компьютерная программа, реализующая разработанные методы и алгоритмы.
Анализ эффективности предложенных методов на основе результатов численного эксперимента.
Научная новизна работы заключается в следующем: {.Блочный способ кодирования контейнерных упаковок. Он является методом кодирования и моделирования упаковок. Его преимуществами являются: а) взаимнооднозначное представление упаковка-кодировка; б) легкая модифицируемость; в) учет пустых пространств; г) возможность адаптации для любых постановок задач и ограничений; д) возможность использования для разнообразных методов локального поиска.
2, Блочный декодер конструирования упаковки, использующий блочный способ кодирования на базе простых стратегий следующий подходящий (NF) и первый подходящий (FF). Декодер универсален и может применяться в составе различных методов локального поиска оптимума.
3. Модификация гибридного группирующего генетического алгоритмадля решения задачи прямоугольно-ориентированного линейного раскроя в составе алгоритма построения ЗБ-упаковок и использование его в качестве оценки нижней границы.
4. Адаптация эволюционных алгоритмов — метода случайных перестановок, (1+JJ-EA и генетического алгоритма для задач упаковки контейнера на базе блочного декодера.
Практическая ценность работы. Разработанное программное обеспечение решает задачу, имеющую многочисленное практическое применение, в том числе упаковка грузов при их транспортировке, планирование размещения подземных сооружений, разрезание губчатой резины. Важным аспектом практического применения разработанных методов является учет технологических ограничений. В диссертации представлены методики учета таких ограничений в рамках разработанных алгоритмов.
Работа выполнялась при частичной поддержке грантов Российского Фонда фундаментальных исследований (РФФИ), проекты 99-01-000937 и 01-01-000510.
Апробация работы. Результаты работы докладывались и обсуждались на следующих конференциях и семинарах:
Международная научная конференция "Моделирование, вычисления, проектирование в условиях неопределенности-2000" (Уфа, 2000).
Студенческая научно-теоретическая конференция 2001 (Уфа, 2001)
Всероссийская научно-практическая конференция "Ресурсосберегающие технологии-, математическое обеспечение оптимизационных задач в системах автоматизированного проектирования" ОПТИМ-2001 (Санкт-Петербург, 2001); CSIT'2001: Computer Science and Informational Technologies (Уфа, 2001);
Вторая Всероссийская научно-техническая конференция «Мехатроника, автоматизация, управление - 2005» (Уфа, 2005).
Семинары кафедры вычислительной математики и кибернетики Уфимского государственного авиационного технического университета.
По теме диссертации опубликовано 10 работ: 6 статей и 4 трудов конференций.
8 Содержание диссертации.
Во введении к диссертации обоснована актуальность решаемой научной проблемы; сформулирована цель и задачи исследования; приведены результаты, выносимые на защиту; отмечена их научная новизна. Приведены сведения об апробации работы и публикациях.
В первой главе проведен аналитический обзор моделей и методов решения задач раскроя-упаковки.
Во второй главе приводятся математические постановки задач упаковки контейнера. Предложена блочная модель кодирования трехмерной упаковки и разработанный на ее основе блочный декодер.
Третья глава посвящена методам локального поиска, использующим блочный декодер. Предложен метод случайных перестановок, вариант классического генетического метода и эволюционный алгоритм.
В четвертой главе описывается реализация ПО и порядок проведения численного эксперимента.
Выражаю глубокую благодарность своему научному руководителю Э.А. Мухачевой за ее вклад в определение направления диссертационной работы, советы и помощь при написании текста диссертации и проведении эксперимента, а также А.С. Филипповой за помощь при использовании общей технологии блочных структур.
Методы, использующие математическое программирование
Как уже было сказано, можно получить с помощью линейного программирования непрерывное решение задачи CSP. G.Scheithauer & J.Terno, использовали полученный непрерывный оптимум для построения целочисленного решения [75]. С этой целью после округления снизу непрерывного решения, формируется малая остаточная задача. Последняя решается с помощью эвристик до достижения нижней границы или процесс останавливается на лучшем из полученных решений.
Задачи ВРР - классические представители NP-трудных проблем и для их решения, в частности, применяются методы полного перебора с отсечением неперспективных вариантов. Еще в 1973 г. И.В.Романовский и Н.П.Христова предложили для решения дискретных минимаксных задач метод дихотомии [30], который получил развитие и для решения задач ВРР в работе С.В.Кацева [11]. В 1977 г. И.В .Романовским представлена общая идея переборного метода для решения экспериментальной задачи, и предложена его конкретизация в виде метода «ветвей и границ» (Method Branch and Bound, MBB) для решения задач упаковки [28]. В дальнейшем метод получает развитие за счет введения процедур сокращения перебора в работах Э.А.Мухачевой и В.М.Картака [24], [70]. Независимо за рубежом выходит серия статей S.Martello & P.Toth, посвященная разработке улучшенных версий МВБ, называемых методами МТР, для решения ШВРР [66]. Размерность задач, разрешимая этими алгоритмами, не велика ( 200).
Существует большое разнообразие эвристических, приближенных алгоритмов, которые позволяют решать задачи большой размерности за небольшое время. Недостатком данных методов является то, что они не всегда способны найти оптимум. Эвристики условно можно разделить на несколько групп: 1. Однопроходные эвристики. Такие как первый подходящий (First Fit, FF), лучший подходящий (Best Fit, BF) и др. Для широкого класса задач они зачастую дают оптимум. Жадные алгоритмы. Например, методы, использующие динамическое программирование [3]. Они позволяют достаточно быстро получать близкие к оптимальному решения, но в силу жадности нередко застревают в локальных оптимумах.
Все эти методы показывают неплохие результаты, но у каждого из них есть классы задач, в которых алгоритмы находят решения, значительно отличающиеся от оптимума. Бурное развитие вероятностных методов локального поиска оптимума началось 10-15 лет назад с появлением метаэвристик для решения NP-трудных задач, систематическое обоснование и характеристика которых приведены в 1996 г. в книге под редакцией E.Aurts, J.Lenstra [42], В России обзор вероятностных методов локального поиска оптимума для NP-трудных задач сделан в 2001 г. Ю.А. Кочетовым [14]. В обзоре обсуждаются общие схемы алгоритмов поиска с запретами, имитация отжига и генетических алгоритмов. Показано, что эти разные по своей структуре алгоритмы используют общую математическую конструкцию конечных цепей Маркова. Это свойство гарантирует сходимость по вероятности наилучшего найденного решения к оптимальному решению задачи. Алгоритмы локального поиска оптимума являются основным объектом исследователей в области раскроя-упаковки, и в частности данная диссертация также представляет один из таких алгоритмов. Идея методов локального поиска в построении на каждом проходе решения, и выборе наилучших, К ним, в частности, относится, разработанный в школе Э.А. Мухачевой, алгоритм последовательного уточнения оценок (Sequentative Value Correction, SVC) [70] и метод динамического перебора [3].
Хотя точного полиномиального алгоритма для ее решения пока не найдено, существует большой контингент методов, дающих оптимальные и близкие к оптимуму решения за короткое время. Также с ростом современной вычислительной техники возвращается интерес к точным методам, которые становятся работоспособны и на достаточно больших размерностях задач.
В отличие от задачи 1DBPP задача прямоугольной упаковки имеет несколько постановок: раскрой-упаковка полубесконечной полосы (1.5ВРР), упаковка на листы (2ВРР), упаковка в угол.
Термин 1.5-размерной задачи ввел в 1980г. A.Hinxman [57]. Пусть имеются прямоугольная полоса заданной ширины W и неограниченной длины и набор из т прямоугольных предметов заданных размеров (w,JJ, і=1,...,т,гдє w,- -ширина, 1Г длина стороны, параллельной неограниченной грани полосы. Требуется ортогонально упаковать предметы в полосу без перекрытий. Если длина L занятой части полосы достигает минимума, то прямоугольная упаковка (RP) - оптимальная упаковка. Часто, особенно в зарубежной литературе, в качестве критерия оптимальности в 1.5DBP используется площадь огибающего RP прямоугольника. Модель 1.5DBP применяется в основном при теоретических разработках, как подзадача проблемы упаковки в листы и непосредственно при раскрое или упаковке рулона.
В случае с 2DBPP кроме ширины W известна и длина L раскраиваемого листа. Обычно исходная информация о заготовках такова, что одного листа для их размещения оказывается недостаточно и на множестве допустимых упаковок требуется найти минимальное количество занятых листов.
Прямоугольная упаковка в угол наиболее абстрактна. Необходимо построить упаковку в открытый квадрат, площадь которой W t минимальна. В основном находит применение при разработке микросхем.
Блочная структура трехмерной упаковки и ее свойства
Блочная структура (BS) трехмерной упаковки представляет собой способ кодирования расположения ящиков в контейнере. Данный подход базируется на разбиении контейнера на двумерные, а затем на одномерные блоки.
Условие (2.1) означает раздвинутость прямоугольников по оси Ох, условие (2.2) - раздвинутость по оси Оу. Раздвинутость по оси Ох или по оси Оу означает непересечение прямоугольников между собой. Выполнение условий ((2.1) или (2.2)) и (2.3) означает допустимость упаковки. Если длина L занятой части допустимой упаковки полосы достигает минимума, то RP называется оптимальной упаковкой и является решением 1.5DBP. Исходную информацию для 1.5DBP принято задавать вектором (W, т, w, Ї), w=(w,,w2,...,wm), /=(/р/2,...,/ш). Решение задачи определяет упаковка RP, заданная координатами (х у i-l,m, прямоугольников. Таким образом, последовательность юго-западных углов (х,; yt) прямоугольников Р,-представляет прямую схему кодирования упаковки. Очевидно, область решений такой кодировочной схемы - бесконечное множество. Заметим, что каждый код не имеет соответствующей допустимой упаковки. Вместе с тем, если известны координаты (x yj), отвечающие упаковке RP, то изобразить ее эскиз не составляет никакого труда. Поэтому представляют интерес способы кодирования, на базе которых можно перейти к прямой схеме (х(.;_у.), / = 1,т.
Пусть имеется прямоугольная упаковка RP. Проведем через правые стороны прямоугольников вертикальные резы, они разбивают RP на прямоугольные вертикальные блоки одной и той же ширины W и различной длины. Пусть длина RP равна N. Проведем через верхние стороны прямоугольников горизонтальные линии. Тогда RP разобьется на горизонтальные блоки одной и той же длины ./V и различной ширины цп причем J]j W. Таким образом, мы получаем две блок-структуры для RP, j вертикальную и горизонтальную. Каждому блоку,/ сопоставим кортеоїс (запись номеров прямоугольников, пересекающих блок) и длину X} вертикального, ширину г]j - горизонтального блока.
Доказательство. Пусть блок-структуры (S, N) и (S,N) удовлетворяют свойствам 1, 2, 5 и условию (3 или 4). Условие 1 обеспечивает неразрывность прямоугольников по вертикали, условие 2 - продолженность (неразрывность) прямоугольников по горизонтали. Таким образом, 1, 2 гарантируют целостность прямоугольников в блок-структурах. Выполнение 3 или 4 означает непересечение прямоугольников между собой ((2.1.) или (2.2.)), а выполнение 5 - непересечение с гранями полосы ((2.3.)). Тогда блок-структурам соответствует допустимая упаковка по определению. Очевидно, что координаты (Xf\yf) прямоугольников Ph i-l m, удовлетворяют условиям (2.5).
Краткая характеристика метода FF для решения задачи прямоугольно-ориентированного линейного раскроя. За основу работы декодера FF удобно принять схему, имитирующую действия мастера в раскройном цехе. Представим процесе в виде выполнения последовательности тактов, на каждом из которых разрезается на заготовки очередной стержень. Предположим, что известен приоритетный список я, в котором каким-то образом упорядочены заготовки. В начале у -го такта от целого стержня отрезается первая из ж возможная заготовка с номером г, длина Я/ которой не превышает длины Z стержня. Потребность bj в этой заготовке корректируется, полагая Ъ.к :- Ъ{ — \. Если Z ,=0, то элемент і удаляется из списка ж. От полученного остатка длины Z:=Z Xi вновь отрезается первая из п возможная заготовка. Если таковой нет, то такт закончен и полученный шаблону характеризуется кортежем (1(/% 2(/), ...), интенсивность Xj применение шаблона (кортежа) определяется как: min bj{j). Следующий такт начинается с раскроя целого стержня.
Модификация FF для прямоугольно-ориентированного линейного раскроя состоит в следующих процедурах: 1. Заготовка i(f) включается в кортежу только один раз. Тогда все элементы каждого кортежа различные. 2. Каждый очередной такту начинается с включения в кортеж заготовки і є І ,-_і, для которой bj ФО.
Генетические методы. Классический генетический алгоритм
Генетические методы построены по аналогии с эволюционным процессом в живой природе. Моделируя такие процессы, как скрещивание, мутация, естественный отбор, генетические алгоритмы позволяют асимптотически приближаться к оптимальному решению.
Базовыми понятиями генетического алгоритма являются ген, хромосома, популяция. Хромосома представляет собой одно из возможных допустимых решений, закодированных определенным образом. Хромосома состоит из более мелких элементов - генов. Каждый ген может принимать некоторый набор значений проектных параметров, называемых аллелями. Множество хромосом занятых в эволюционном процессе называется популяцией.
Эффективность генетического метода кроется в направленном переборе решений (эволюции). Этот процесс осуществляется с помощью операторов пересечения, мутации, естественного отбора. Первым шагом работы генетического алгоритма является формирование популяции. Этот выбор не влияет на сходимость процесса в асимптотике, но изначально хорошая популяция способна ускорить нахождение оптимума.
После формирования начальной популяции начинается итерационный эволюционный процесс. На каждой итерации производится выбор некоторых хромосом для пересечения. Появившиеся потомки дополняют популяцию. Естественным отбором служит удаление лишних хромосом, с худшей функцией цели. Для внесения небольших случайных изменений над некоторыми хромосомами применяется оператор мутации.
Работа оператора мутации заключается в обмене двух случайных элементов в каждом новом PL с небольшой вероятностью pp.. Оператор естественного отбора удаляет хромосомы с наихудшей функцией цели. В частности для задач 3DBPP, функцией цели является Н упаковки. Естественный отбор удалит упаковки с наибольшими Н.
Выбор второй родительской хромосомы у производиться случайно, но чем выше целевая функция у хромосомы, тем больше у нее шансов быть выбранной.
В отличие от метода случайных перестановок приоритетного списка генетический алгоритм позволяет осуществлять направленный перебор решений, и для него доказана асимптотическая сходимость к оптимуму.
Эволюционные алгоритмы (ЭА) - это обобщенный термин, применяемый для описания вычислительных методов, использующих модели эволюционных процессов. Основой всех эволюционных алгоритмов является имитация эволюции индивидуальных структур через процессы отбора, мутации и воспроизведения. ЭА рассматривают популяции структур, развивающиеся путем мутаций и воспроизведения согласно правилам отбора. Отбор происходит по критериям соответствия структуры условиям внешней среды. ЭА достаточно широко используются при решении задач многопараметрической оптимизации.
Генетические методы являются одной из разновидностей эволюционных алгоритмов. Они максимально приближенны к реальным эволюционным процессам живой природы. Но существуют и более простые ЭА. В частности, к таким относиться и эволюционный алгоритм 1+1. Схема его работы строится на следующем подходе:
Имеется одно закодированное решение (хромосома), которое является родителем. На каждой итерации с помощью модификации этой родительской хромосомы получается потомок. Модификация представляет собой мутацию. В случае, если целевая функция потомка достигает лучшего значения, он заменяет родителя.
Впервые алгоритм (1+1) формализовано описывается у I. Rehtenberg. В статье [73] описываются общие принципы ряда эволюционных алгоритмов. П. Борисовским доказано, что, если оператор мутации обладает свойством монотонности, то алгоритм (1+1)-ЕА является оптимальной стратегией поиска среди различных ЭА. Для операторов мутации применяемых в среде задач раскроя-упаковки, свойство монотонности мутации пока не доказано.
Отличия ЭА (1+1) от генетического алгоритма: 1. В ЭА отсутствует понятие популяции. Если в генетических алгоритмах все операции выполняются над множеством закодированных решений (хромосом), то в предложенном эволюционном алгоритме имеется только одна особь. 2. В ЭА (1+1) не применяется оператор скрещивания. На каждой итерации алгоритм работает только с одной особью. И единственным оператором, который к ней применим, является мутация, работающая с PL.
Как и для генетического алгоритма, в ЭА 1+1 в качестве хромосом выступают приоритетные списки и мутации подвергаются именно они.
Мутация будет представлять собой случайную перестановку элементов внутри приоритетного списка. Но если в классическом генетическом алгоритме мутация заключалась в случайном выборе одной пары генов для обмена, то для ЭА предлагается в процессе мутации выбирать несколько таких пар.
Для работы любого приближенного и эвристического метода важное значение имеет нахождение нижней границы. Она служит как условие останова и как критерий перспективности дальнейшего построения решения. В первом случае, по достижению нижней границы работа алгоритма останавливается. Второй же используется в комбинаторных методах. Так в методе ветвей и границ нижняя граница позволяет отбросить неперспективные ветви решений существенно сокращая область перебора.
Для задач 1DBPP имеется возможность найти очень точную нижнюю границу. В 1981 г. S.Baum & Jr.Trotter отметили, что в большинстве случаев разрыв между оптимальными значениями непрерывной релаксации и целочисленной задачей не превышает 1, т.е. округленное решение оптимально [43]. В 1985 г. O.Marcotte сформулировал важные свойства целочисленного оптимального решения для задачи линейного раскроя [62]: целочисленное свойство (IR), если целочисленный оптимум z(x) совпадает с оптимальным решением с(х) задачи непрерывной релаксации; свойство округления до целого вверх (Integer Round-Up Property, IRUP), если z(x)= c(x)\; модифицированное свойство округления до целого вверх (Modified Integer Round-up Property, MIRUP), если z(x) не превосходит Qc(x)\+l). Относительно этих свойств высказано следующее предположение: стандартная одномерная задача раскроя обладает свойством MIRUP. Это предположение не опровергнуто, но и не доказано. В свою очередь, базируясь на этом факте, построены схемы точного решения в работах G.Scheithauer & J.Terno [74].
Выбор целевой функции для численных экспериментов
Как показано в математической модели, для задачи упаковки в контейнер с незафиксированной высотой минимизируется высота упаковки. Однако, при сравнительном эксперименте такой показатель не является информативным, потому что он зависит в первую очередь от количества ящиков, а уже затем от качества полученного решения.
Оценка качества производилась по среднему значению целевой функции. Оно оказалось наивысшим у вероятности р = 0,05. Было выдвинуто предположение, что с уменьшением р качество решения возрастает. Поэтому был проведен дополнительный эксперимент для р = 0,02 и р = 0,03. Однако, предположение не подтвердилось. Средние значения целевой функции для этих вероятностей уступали значению при/? = 0,05.
В итоге тестов в программе выставлено значение/? = 0,05. Генетический алгоритм. Определение размера популяции С тем же тестовым набором из 20 задач были проведены тесты для различного количества хромосом. Время было ограничено уже 5 минутами (300 секунд).
Значительного преимущества, для какого-либо из значений исследуемого параметра, получено не было. Поэтому был дополнительно проведен эксперимент внутри отдельного класса задач. В ходе проделанных экспериментов был сделан вывод о том, что наилучший размер популяции для отдельной задачи не зависит от класса и варьируется в широких пределах. Наиболее высокие значения целевой функции были достигнуты для 20, 32 и 40 хромосом. Однако четкой рекомендации дать не возможно.
В эволюционном методе работа оператора мутации заключается в случайном выборе двух генов, которые обмениваются своими позициями. Эта процедура выполняется к раз, до запуска блочного декодера. Определение эффективных к позволит ускорить сходимость метода. При небольших к наблюдается очень медленная сходимость алгоритма.
В классе, где ящики имели средние размерности, хорошо проявил себя блочный алгоритм с перебором. Он был лучшим в 4 «средних» классах из 6. В целом предложенные методы были лучшими в 14 из 18 классов, что позволяет высказать предположение о высокой эффективности разработанных алгоритмов при т=30.
Описаны особенности разработки программного обеспечения и подбор параметров предложенных алгоритмов. Программное обеспечение выполнено в соответствии с концепцией объектно-ориентированного программирования, что позволило упростить включение в программный комплекс новых методов верхнего уровня.
Был проведен численный эксперимент. Он показал: 1. Большую эффективность при небольшом количестве ящиков (т 40) у эволюционного алгоритма и алгоритма случайных перестановок. И увеличение эффективности работы генетического алгоритма при количестве ящиков больше 40; 2. Лучшие результаты у разработанных алгоритмов при т=30 в сравнении с другими методами.
Было сделано предположение, что с ростом количества ящиков, эффективность декодера будет падать, поскольку простые стратегии, обладая асимптотической сходимостью, медленней сходятся. Поэтому имеет смысл внесения в декодер элементов жадности. Заключение
Задаче контейнерной упаковке отводиться наименьшее внимание в сфере исследований задач раскроя-упаковки. Это объясняется ее более высокой сложностью и проблемами при создании методов. Однако, в представленной диссертационной работе показано, что решение задач 3DBPP можно свести к более простым подзадачам двумерного и одномерного раскроя-упаковки, для которых уже существует множество методов и алгоритмов. Поэтому одним из главных направлений работы являлась демонстрация эффективности перехода от 3DBPP к 2DBPP, а затем к ШВРР. Было показано удобство предлагаемого подхода. Все методы и алгоритмы получили программную реализацию и доказали свою эффективность.
Задачи упаковки контейнера часто встречаются на практике, и эффективное их решение позволяет получать экономическую выгоду. При этом существенными являются два критерия: качество решения и время его поиска. Предложенные алгоритмы в равной степени удовлетворяют обоим условием и с успехом могут применяться для реальных задач.
Основные результаты диссертационной работы: 1. Рассмотрены различные постановки задачи трехмерной упаковки контейнера, и описаны их математические модели. Они являются NP-трудными проблемами комбинаторной оптимизации. Показано, что для их решения имеет смысл использовать приближенные и эвристические методы. 2. Впервые разработана блок-структура контейнерной упаковки, представляющая собой ее блочную модель. Сформулированы и доказаны ее основные свойства. На этой основе показано, что блок-структура позволяет сводить поиск оптимума контейнерной упаковки к решению задачи одномерного раскроя. 3. Предложен алгоритм блочного декодера, строящего блок-структуру и координаты размещения ящиков на основе приоритетного списка. Показано, что декодер обладает универсальностью и может быть использован в составе различных методов локального поиска. 4. Адаптированы для условий работы блочного декодера эволюционные алгоритмы (метод случайных перестановок, классический генетический алгоритм и (1+1)-ЕА). Показано, что алгоритмы могут применяться для решения реальных задач упаковки. Выявлены возможность по их адаптации для различных постановок задачи трехмерной упаковки и различных технологических ограничений.
