Модифицированные эволюционные алгоритмы и программные решения задачи ортогональной упаковки объектов

• Автор: Чеканин, Владислав Александрович
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Москва
• Количество страниц: 161 с. : ил.

ОГЛАВЛЕНИЕ.

СПИСОК УСЛОВНЫХ ОБОЗНАЧЕНИЙ И СОКРАЩЕНИЙ.

ВВЕДЕНИЕ.

ГЛАВА 1. ОБЗОР ЗАДАЧ УПАКОВКИ И МЕТОДОВ ИХ РЕШЕНИЯ. ПОСТАНОВКА ЗАДАЧИ ИССЛЕДОВАНИЯ

1.1. Классификация задач упаковки, проведенная Н. Иускш

1.2. Современная классификация задач упаковки.

1.3. Задача ортогональной упаковки

1.3.1. Задача двухмерной ортогональной упаковки на листы

1.3.2. Задача двухмерной ортогональной упаковки на полубесконечную полосу.

1.4. Методы решения задач упаковки

1.4.1. Методы математического программирования

1.4.2. Методы комбинаторной оптимизации.
1.4.3. Эвристические методы.
1.4.4. Вероятностные и эволюционные методы
1.5. Постановка задачи исследовательской работы.
ГЛАВА 2. АЛГОРИТМЫ КОНСТРУИРОВАНИЯ УПАКОВКИ.
2.1. Представление контейнеров
2.2. Представление размещаемых объектов.
2.2.1. Представление на основе многомерного массива.
2.2.2. Узловая модель.
2.2.3. Модель виртуальные объекты.
2.2.4. Блочная модель представления объектов
2.2.5. Тестирование моделей
2.3. Кодирование размещаемых объектов
2.3.1. Создание групп геометрически одинаковых объектов
2.3.2. Алгоритм формирования строки решения
2.3.3. Алгоритм декодирования строки решения.
2.4. Размещение упаковываемых объектов.
2.4.1. Формирование узлов
2.4.2. Декодер строки решения .
2.4.3. Организация набора узлов
2.4.4. Проверка возможности присоединения объекту к узлу.
2.4.5. Оценка ресурсной эффективности разработанных алгоритмов
2.4.6. Исключительные ситуации при размещении объектов.
2.5. Выводы по главе 2.
ГЛАВА 3. ЭВОЛЮЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ УПАКОВКИ.
3.1. Алгоритм получения решения оптимизационной задачи.
3.1.1. Формирование начального множества решений.
3.1.2. Локальный оптимум решения.
3.1.3. Критерии останова поиска эволюционного алгоритма
3.2. Методы поиска оптимального решения
3.3. Эволюционные алгоритмы
3.3.1. Алгоритм отжига.
3.3.2. Генетический алгоритм.
3.3.3. Комбинированный генетический алгоритм.
3.3.4. Генетические операторы
3.3.5. Выбор параметров генетического алгоритма
3.3.6. Мультиметодный генетический алгоритм
3.3.7. Выбор алгоритма оптимизации конечного решения.
3.4. Выводы по главе
ГЛАВА 4. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМОВ И ВЫЧИСЛИТЕЛЬНЫЕ ЭКСПЕРИМЕНТЫ.
4.1. Программная реализация алгоритмов решения задач многомерной упаковки.
4.1.1. Структуры данных
4.1.2. Особенности разработанной библиотеки классов задач упаковки.
4.1.4. Реализация интерфейса пользователя в программном решении
4.1.5. Решение задач двухмерной и одномерной упаковки
4.2. Вычислительные эксперименты
4.2.1. Методы оценки качества алгоритмов решения задачи
4.2.2. Решение задачи двухмерной упаковки объектов.
4.2.3. Решение задачи трхмерной упаковки объектов.
4.3. Выводы по главе
ЗАКЛЮЧЕНИЕ
БИБЛИОГРАФИЧЕСКИЙ СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ
ПРИЛОЖЕНИЕ А. АКТЫ О ВНЕДРЕНИИ
ПРИЛОЖЕНИЕ Б. РЕЗУЛЬТАТЫ ТЕСТИРОВАНИЯ ЭВРИСТИК НА ТЕСТОВЫХ ЗАДАЧАХ УПАКОВКИ НА ЛИСТЫ
ПРИЛОЖЕНИЕ В. РЕЗУЛЬТАТЫ ТЕСТИРОВАНИЯ АЛГОРИТМА НА ТЕСТОВЫХ ЗАДАЧАХ УПАКОВКИ НА ПОЛОСУ
Список условных обозначений и сокращений
1.5 класс задач двухмерной контейнерной упаковки на полубесконечную полосу 1.5 ii i i
2 класс задач двухмерной контейнерной упаковки на листы
2 ii i i
3 класс задач трхмерной контейнерной упаковки на листы
3 ii i i
эвристика лучший подходящий i
эвристика нижний левый
класс задач контейнерной упаковки i i
эвристика первый подходящий i i
I эвристика усовершенствованный нижний левый Iv
МВВ метод ветвей и границ
задача паллетирования i i эвристика следующий подходящий x i
класс неполиномиально сложных задач iii i унифицированный язык моделирования ii i
алгоритм отжига
ГА генетический алгоритм
КГ А комбинированный генетический алгоритм
МГА мультиметодный генетический алгоритм
ЦФ целевая функция.
Введение
Актуальность


Результаты реализации мультиметодпой технологии конструирования упаковки, использующей разработанные эвристики. Унифицированная модель решения задач упаковки объектов произвольной размерности. Практическая ценность диссертационной работы состоит в разработке программного обеспечения, реализующего алгоритмы решения задач ортогональной упаковки различной размерности, а также в разработке унифицированной библиотеки классов задач упаковки. Достоверность и обоснованность научных положений, рекомендаций и выводов обеспечиваются корректным использованием математического аппарата. Достоверность результатов работы подтверждается сериями вычислительных экспериментов путем глубокого анализа и сравнения полученных результатов с результатами решений, полученных другими отечественными и зарубежными исследователями. Реализация результатов работы. Результаты диссертационной работы внедрены в учебный процесс ГОУ ВПО МГТУ Станкин и в настоящее время используются при подготовке бакалавров по направлению . Прикладная информатика, магистрантов по магистерским программам . Человекомашинные системы управления и . Теоретическая информатика. Информатика и специальным дисциплинам магистерской подготовки Интеллектуальные системы обработки информации, Технология программирования в интеллектуальных системах управления. Определена целесообразность применения разработанных методик при создании прикладного программного обеспечения в малом инновационном предприятии ООО Компьютерные системы и технологии г. Москва, выполняющем высокотехнологичные разработки, в том числе, для решения задач упаковки и логистики в интеллектуальных транспортных системах, а также для оптимизации работы аптечного склада многопрофильной клинической больницы г. Москва. Апробация работы. Москва, ГОУ ВПО МГТУ Станкин, . В году проект Повышение эффективности управления полезным пространством складов на основе эволюционных алгоритмов, включающий некоторые положения представленной к защите работы, был удостоен диплома Всероссийской выставки научнотехнического творчества молодежи НТТМ. Публикации. По теме диссертации опубликовано научных работ, из них основных, в том числе 3 статьи в изданиях, входящих в Перечень ведущих периодических изданий ВАК Министерства образования и науки РФ и 1 монофафия. Структура и объем диссертации. Диссертационная работа состоит из введения, четырх глав, списка литературы и трх приложений. Список литературы состоит из 7 наименований. Приложения выполнены на шести страницах. Во введении обосновывается актуальность темы диссертационной работы формулируются цели и задачи исследований представляются основные выносимые на защит положения работы определяются новизна, практическая значимость полученных результатов приводится краткая характеристика основных разделов диссертации. В первой главе представлен обзор существующих задач раскрояупаковки и методов их решения. Приведена классификация задач раскрояупаковки, проведенная . Приведена постановка полной оптимизационной задачи раскрояупаковки. Сформулированы задачи ортогональной упаковки объектов на листы и на полубесконечную полосу. Приведены основные методы решения задачи упаковки. Описаны методы комбинаторной оптимизации эвристические, вероятностные и эволюционные методы, применяемые для решения задач раскроя и упаковки. Выделены основные факторы, влияютцие на качество конечной упаковки модель представления объектов в контейнерах, схемы кодирования и декодирования строки решения, алгоритмы оптимизации получаемого решения. Выделены области эффективного применения решения задач раскрояупаковки, а также классы наиболее распространенных на практике задач, которые решаются в диссертационной работе. В конце главы формулируются задачи диссертационной работы. Вторая глава посвящена исследованию алгоритмов конструирования ортогональной упаковки. Рассмотрены следующие модели представления объектов в контейнерах модель на основе многомерного массива, узловая модель, блочная модель. Предложена модель виртуальные объекты, которая является производной от узловой модели.