Эволюционные алгоритмы на базе блочных технологий для решения задач упаковки контейнера

• Автор: Сурначев, Максим Юрьевич
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Уфа
• Количество страниц: 97 с. : ил.

Оглавление
Введение

1. Задачи раскрояупаковки аналитический обзор моделей и методов их решения.

1.1 Задача одномерного раскрояупаковки

1.1.1 Методы, использующие математическое программирование

1.1.2 Комбинаторные методы.

1.1.3 Приближенные и эвристические методы

1.1.4 Методы локального поиска оптимума

1.1.5 Заключение по задаче одномерного раскрояунаковки.

1.2 Задача прямоугольного раскрояупаковки.

1.2.1 Методы, использующие математическое программирование

1.2.2 Комбинаторные методы.
1.1.3 Приближенные и эвристические методы
1.2.4 Методы локального поиска оптимума
1.3 Задача упаковки трехмерного контейнера и ее постановки.
1.3.1 Технологические ограничения в задаче упаковки контейнера
1.3.2 Комбинаторные методы.
1.3.3 Эвристики и методы локального поиска оптимума
1.3.4 Выводы по задаче контейнерного раскрояупаковки.
1.4 Выводы.
2. Математическая модель контейнерной упаковки и однопроходные методы ее решения
2.1 Математическая модель задачи контейнерной упаковки.
2.2. Блочная структура трехмерной упаковки и се свойства.
2.2.1 Блокструктуры прямоугольной упаковки
2.2.2 Задачи прямоугольноориентированного линейного раскроя
2.2.3 Блокструктура Ш, адаптированная для контейнерной упаковки.
2.3 Блочный декодер
2.4 Учет технологических ограничений в блочном декодере
2.4 Выводы по второй главе.
3. Методы локального поиска оптимума с использованием блочного декодера
3.1 Метод случайных перестановок приоритетного списка
3.2 Генетические методы. Классический генетический алгоритм
3.3 Генетический алгоритм с блочным декодером
3.4 Эволюционный алгоритм 11
3.5 Нижние границы для задач раскроя упаковки
3.5 Выводы по третьей главе
4. Численные эксперименты.
4.1 Реализация программного обеспечения
4.2 Выбор целевой функции для численных экспериментов
4.2 Выбор параметров алгоритмов
4.3 Численные эксперименты.
4.3.1 Эксперимент на случайно сгенерированных примерах
4.3.2 Сравнительный эксперимент с другими методами решения поставленной задачи.
4.4 Выводы по четвертой главе
Заключение
Литература


Это объясняется сложностью задач и высокой трудоемкостью их решения. Поэтому является актуальной разработка, эффективных алгоритмов решения задач раскроя-упаковки параллелепипедов. Задача раскроя-упаковки принадлежит к классу 'НР-трудных проблем, то есть для ее точного решения не известно алгоритма полиномиальной сложности. Более того, рассматриваемая задача является ИР-трудной в сильном смысле, так как содержит ИР-трудную задачу в качестве подзадачи. До сих пор не разработано эффективных и достаточно точных способов расчета нижних границ для данной задачи, позволяющих определить достижение оптимума. Таким образом, точные алгоритмы сводятся к полному перебору вариантов. В связи с этим, использование точных методов для решения задачи раскроя-упаковки часто оказывается нецелесообразным и невозможным по причине больших затрат времени. Поэтому большое значение уделяется разработке и исследованию эвристических методов оптимизации. Одним из перспективных направлений является разработка метаэвристических алгоритмов, основанных на известных метаэвристических стратегиях, с успехом используемых для решения многих задач дискретной оптимизации. Для большинства метаэвристик доказана их асимптотическая сходимость, что является важным доводом в пользу их активного использования. Целью работы является разработка и исследование моделей и методов решения задач контейнерной упаковки на базе блочной технологии и реализация комплекса программ, ориентированных на достижение рационального решения в ограниченное время. Разработать блочный способ моделирования трехмерных упаковок. Разработать блочный декодер конструирования трехмерных упаковок на базе применения простых стратегий. Провести численный эксперимент с целыо исследования эффективности предложенных алгоритмов. Блочный способ кодирования трехмерных упаковок. Блочный декодер» - алгоритм конструирования блочной структуры упаковки по приоритетному списку (перестановке параллелепипедов). Эволюционные методы, работающие с блочным декодером для решения поставленной задачи. Компьютерная программа, реализующая разработанные методы и алгоритмы. Анализ эффективности предложенных методов на основе результатов численного эксперимента. Блочный способ кодирования контейнерных упаковок. Он является методом кодирования и моделирования упаковок. Его преимуществами являются: а) взаимнооднозначное представление упаковка-кодировка; б) легкая модифицируемость; в) учет пустых пространств; г) возможность адаптации для любых постановок задач и ограничений; д) возможность использования для разнообразных методов локального поиска. Блочный декодер конструирования упаковки, использующий блочный способ кодирования на базе простых стратегий следующий подходящий (АТ7) и первый подходящий (ГР). Декодер универсален и может применяться в составе различных методов локального поиска оптимума. Модификация гибридного группирующего генетического алгоритма для решения задачи прямоугольно-ориентированного линейного раскроя в составе алгоритма построения ЗЭ-упаковок и использование его в качестве оценки нижней границы. Адаптация эволюционных алгоритмов — метода случайных перестановок, (1+1)-ЕА и генетического алгоритма для задач упаковки контейнера на базе блочного декодера. Практическая ценност ь работы. Разработанное про! Важным аспектом практического применения разработанных методов является учет технологических ограничений. В диссертации представлены методики учета таких ограничений в рамках разработанных алгоритмов. Работа выполнялась при частичной поддержке грантов Российского Фонда фундаментальных исследований (РФФИ), проекты и . Апробация работы. Международная научная конференция “Моделирование, вычисления, проектирование в условиях неопределенности-” (Уфа, ). Вторая Всероссийская научно-техническая конференция «Мехатроника, автоматизация, управление - » (Уфа, ). Семинары кафедры вычислительной математики и кибернетики Уфимского государственного авиационного технического университета. По теме диссертации опубликовано работ: 6 статей и 4 трудов конференций.