Введение к работе
Актуальность темы. Области применения задачи упаковки одномерных элементов в блоки (далее, задача упаковки блоков) охватывают большое количество сфер деятельности человека. Упаковка блоков является распространенной производственной задачей. Она решается при производстве стали, стекла, бумаги, дизайне СБИС, составлении бюджета, форматировании таблиц, постраничном разбиении и т.д. Задача упаковки блоков является NP-сложной и NP-полной.
Несмотря на высокую изученность задачи, существование огромного количества различных методов ее решения, для ряда контрольных (тестовых) задач оптимальное решение не получено. Более того, на данный момент не существует универсального алгоритма, способного одинаково эффективно решать все тестовые задачи, представленные в литературе. Таким образом, задача упаковки блоков является актуальной задачей оптимизации.
Результатом непрекращающегося поиска наиболее эффективных методов упаковки блоков стало использование бионических алгоритмов, в том числе эволюционных и генетических алгоритмов. Отличительной особенностью генетических алгоритмов является работа не с одним решением, а с набором альтернативных решений. Результаты экспериментальных исследований доказали высокую производительность бионических методов и алгоритмов упаковки блоков, а на отдельных контрольных задачах - их безусловное превосходство над существующими методами решения.
Цель и основные задачи диссертационной работы.
Основной целью диссертации является разработка и исследование комплекса гибридных алгоритмов упаковки одномерных элементов в блоки, способных получать квазиоптимальные и оптимальные решения рассматриваемой задачи. Для достижения поставленной цели были решены следующие задачи:
Разработана архитектура гибридного генетического поиска, основанная на стратегии «эволюция - локальный поиск»;
Построен и исследован гибридный параллельный генетический алгоритм упаковки блоков, позволяющий получать
квазиоптимальные и оптимальные решения рассматриваемой задачи;
Разработаны алгоритмы локального поиска, позволяющие повысить качество решений, получаемых гибридным генетическим алгоритмом;
Построены проблемно-ориентированные модифицированные генетические операторы, позволяющие получать допустимые решения задачи упаковки блоков;
Создан программный комплекс для решения задачи упаковки блоков «ВРР by GA».
Методы исследования
Методы исследования основываются на элементах теории множеств, алгоритмов, эволюционного моделирования, статистике.
Достоверность результатов исследования
Объем численных экспериментов, проведенных при решении различных контрольных (тестовых) задач и вариациях параметров параллельного гибридного генетического алгоритма, составил не менее 104 опытов. Программный комплекс «Одномерная упаковка элементов в блоки методами генетического поиска» («BPPbyGA») на котором осуществлялось автоматизированное проведение экспериментов, прошел официальную регистрацию в Федеральной службе по интеллектуальной собственности, патентам и товарным знакам (ФГУ ФИПС свидетельство №2007613933 (роспатент) от 14.09.2007).
Научная новизна диссертационной работы заключается в следующем:
1 .Разработана архитектура гибридного генетического поиска, основанная на стратегии «эволюция - локальный поиск»;
2.Построен гибридный параллельный генетический алгоритм упаковки блоков, позволяющий получать квазиоптимальные и оптимальные решения рассматриваемой задачи;
3.Разработаны методы гибридного генетического поиска, основанные на моделях эволюции Ж. Ламарка и Г. де Фриза, позволяющие создавать различные по качеству решения рассматриваемой задачи, частично решая проблему преждевременной сходимости поиска к локально оптимальному решению;
4.Разработаны алгоритмы локального поиска, позволяющие повысить качество решений, получаемых при помощи методов гибридного генетического поиска;
5.Предложены проблемно-ориентированные
модифицированные генетические операторы для параллельного гибридного генетического алгоритма упаковки блоков, позволяющие получать допустимые решения рассматриваемой задачи.
К числу наиболее важных научных результатов диссертации относятся:
Гибридный параллельный генетический алгоритм упаковки блоков, позволяющий получать квазиоптимальные и оптимальные решения рассматриваемой задачи;
Методы гибридного генетического поиска, позволяющие создавать различные по качеству альтернативные решения рассматриваемой задачи, частично решая проблему преждевременной сходимости поиска к локальному оптимуму;
Алгоритмы локального поиска, позволяющие повысить качество решений, получаемых при помощи методов гибридного генетического поиска.
Практическая ценность
Разработан программный комплекс, позволяющий находить квазиоптимальные и оптимальные решения задачи упаковки блоков. Одним из возможных применений комплекса является решение задачи форматирования таблиц, а также постраничное разбиение и дизайн СБИС. Программный комплекс разработан для операционной системы Windows, написан на языке C++. Компиляция выполнена в среде объектно-ориентированного программирования Microsoft Visual Studio. NET.
Реализация результатов работы.
Материалы диссертации использованы в учебном процессе на кафедре САПР ТТИ ЮФУ при чтении лекций по курсам: «Методы оптимизации», «Эволюционное моделирование и генетические алгоритмы», «Автоматизация конструкторского и технологического проектирования». Разработанный программный комплекс был успешно протестирован и принят к использованию на кафедре САПР ТТИ ЮФУ при проведении лабораторных и практических занятий по курсам «Методы оптимизации», «Эволюционное
моделирование и генетические алгоритмы», «Автоматизация конструкторского и технологического проектирования».
Апробация работы и публикации.
Основные теоретические и практические результаты работы представлены на международных научно-технических конференциях AIS'06, CAD'06 (пос. Дивноморск, 2006 г.), международных научно-технических конференциях AIS'07, CAD'07 (пос. Дивноморск, 2007 г.), международной научно-практической конференции «Интегрированные модели и мягкие вычисления в искусственном интеллекте» (г. Коломна, 2007).
Результаты диссертации отражены в 7 печатных работах.
Структура и объём диссертационной работы.
Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложения. Работа содержит 145 стр., включая 55 рис., 23 таб., список литературы из 133 наименований, 3 стр. приложений и актов об использовании.
