Разработка и исследование бионических методов упаковки

• Автор: Потарусов, Роман Валерьевич
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Таганрог
• Количество страниц: 149 с. : ил.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ
1. ОБЗОР И АНАЛИЗ АЛГОРИТМОВ И МЕТОДОВ ОПТИМИЗАЦИИ УПАКОВКИ ОДНОМЕРНЫХ ЭЛЕМЕНТОВ В БЛОКИ

1.1. Математическая формулировка задачи упаковки блоков

1.2. Приближенные алгоритмы

1.3. Редукционная процедура С. Мартслло и П. Тота

1.4. Точные алгоритмы

1.5. Мстаэвристические методы решения задачи упаковки блоков

1.6. Эвристики, осноианные на минимальной остаточной вместимости блока

1.7. Процедура повышения качества решения А.Алвима и Ф. Гловера

1.8. Алгоритм моделирования отжига.

1.9. Алгоритм поиска при переменном соседстве
1 Выводы.
2. РАЗРАБОТКА АРХИТЕКТУРЫ ГИБРИДНОГО ГЕНЕТИЧЕСКОГО ПОИСКА.
2.1. Разработка архи тектуры гибридного генетического поиска для задачи упаковки блоков
2.2. Разработка методов гибридного генетического поиска, основанных на моделях эволюции.
2.3. Выводы
3. РАЗРАБОТКА КОМПЛЕКСА ГИБРИДНЫХ АЛГОРИТМОВ.
3.1. Распараллеливание эволюционных вычислений в алгоритмах упаковки
3.2. Целевая функция.
3.3. Кодирование решений.
3.4. Создание начальной популяции
3.5. Гибридный параллельный генетический алгоритм решения задачи упаковки блоков
3.6. Общая процедура гибридного параллельного генетического алгоритма .
3.7. Разработка и анализ модифицированных генетических операторов, ориентированных на решение задачи упаковки блоков
3.8. Разработка алгоритмов локального поиска, ориентированных на
решение задачи упаковки блоков.
3.9.7еорстические оценки временной и пространственной сложности разработанных алгоритмов.
3 Выводы.
4. ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ РАЗРАБОТАННОГО
КОМПЛЕКСА ГИБРИДНЫХ АЛГОРИТМОВ.
4.1. Требования к программным продуктам, реализующим генетические алгоритмы
4.2. Основные характеристики программного комплекса ВРРЬуСА
4.3. Структура программного комплекса ВРРЬуСА
4.4. Цель экспериментального исследования
4.5. Планирование эксперимента.
4.6. Результаты экспериментальных исследований.
4.7. Область применения разработанных алгоритмов.
4.8. Выводы
ЗАКЛЮЧЕНИЕ.
ЛИТЕРАТУРА


В первой главе приведена постановка задачи упаковки одномерных элементов в блоки, а также ее математическая формулировка. Произведен сравнительный анализ существующих методов и алгоритмов упаковки в блоки. Показано, что для решения реальных практических задач эффективным является применение гибридных генетических алгоритмов. Во второй главе предложена архитектура гибридного генетического поиска, основанная на стратегии «эволюция - локальный поиск». Разработаны методы гибридного генетического поиска на основе моделей эволюции Г. Фриза и Ж. Ламарка, позволяющие создавать различные по качеству решения рассматриваемой задачи, частично решая проблему преждевременной сходимости поиска к локально оптимальному решению. В третьей главе проведено исследование и сделаны выводы относительно эффективности распараллеливания эволюционных вычислений в алгоритмах упаковки. Обоснован выбор целевой функции, используемой генетическим алгоритмом для решения задачи упаковки блоков. Выбранная целевая функция позволяет производить оценку не только альтернативного решения в целом, но и получать необходимую информацию о. Описано кодирование альтернативного решения задачи упаковки блоков. Альтернативное решение кодируется одной хромосомой, где каждому гену соответствует один блок, содержащий упакованные в него элементы. Введено понятие функциональной части альтернативного решения, состоящей из. Разработан гибридный параллельный генетический алгоритм упаковки блоков, позволивший достигнуть квазиоптимальных и оптимальных решений на большинстве контрольных (тестовых) задач, доступных в литературе. Указанные операторы работают с групповой и функциональной частью альтернативных решений, отличаются от существующих генетических операторов возможностью получать допустимые альтернативные решения задачи. Алгоритмы локального поиска, предлагаемые в данной работе, позволяют повысить качество решений, получаемых при помощи методов гибридного генетического поиска. Сделаны выводы о научной новизне и практической ценности предлагаемых методов и алгоритмов. Четвертая глава посвящена разработке и тестированию программного комплекса, реализующего комплекс гибридных алгоритмов упаковки блоков в целом и гибридный параллельный генетический алгоритм, в частности. Программный комплекс реализован на языке C++ в среде Microsoft Visual Studio. NET. Разработанный комплекс не требователен к ресурсам, может быть запущен на любом ПК с установленной ОС Windows и выше. Пользователю предлагается удобная система с возможностью модификации параметров алгоритмов и просмотром результатов упаковки. Сделаны выводы об оптимальном размере популяции решений для гибридного параллельного генетического алгоритма упаковки блоков. Исследована эффективность работы комплекса алгоритмов при разных методах генерации начальной популяции альтернативных решений рассматриваемой задачи. Проведены серии экспериментов, выполнена статистическая обработка экспериментальных данных. Тестирование выполнено для контрольных задач, на каждой из которых параллельный алгоритм запускался раз. Интернет. Достоинством разработанного комплекса алгоритмов, помимо его эффективности, является способность ускорять получение оптимального (или близкого к нему) решения за счет распараллеливания процесса поиска, методов гибридного генетического поиска на основе известных моделей эволюций, эффективных алгоритмов локального поиска, применения проблемно-ориентированных генетических опера торов. В заключении изложены основные выводы и результаты, полученные в диссертационной работе. В приложении представлены копии актов о внедрении и актов об использовании в учебном процессе результатов представленной работы. Задача упаковки блоков описывается следующим образом. Упакуем каждый элемент в один блок так, чтобы общий вес элементов в каждом блоке не превышал с, а число использованных блоков было минимально. Будем полагать, что , с - положительные целые, < с для у е N. Классификация методов и алгоритмов упаковки одномерных элементов в блоки приведена на рис. Рассмотрим различные методы и алгоритмы упаковки блоков, наиболее полно освященные в литературе. Рис.