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

Введение к работе

Актуальность работы. Задачи упаковки представляют собой важный прикладной раздел комбинаторной оптимизации. К задаче ортогональной упаковки сводятся задачи эффективного размещения объектов, составления расписаний, планирования распределения ресурсов, геометрического проектирования, управления процессами обработки данных и т.д. Оптимизация решения задачи упаковки приводит к повышению эффективности использования ресурсов и оборудования, сокращению временных издержек при проектировании карт размещения.

При планировании современного производства уже на этапе проектирования изделия необходимо стремиться к экономии материальных ресурсов. Как правило, в условиях массового производства даже незначительная экономия материала на одно изделие дает при выпуске большой партии продукции значительный экономический эффект.

При проектировании промышленных производств наиболее часто решаются задачи ортогональной упаковки и прямоугольного раскроя, где в качестве размещаемых объектов выступают прямоугольные объекты и параллелепипеды, а в качестве контейнеров - рулонный материал, прямоугольные заготовки, ортогональные контейнеры различной емкости. В этом случае большую роль играют выбор, оценка и реализация методов решения таких задач.

Сложность решения задачи упаковки обусловлена её принадлежностью к классу NP-полных задач, для которых невозможно применение точных методов в условиях реального производства из-за больших затрат временных ресурсов. В связи с этим, одним из наиболее перспективных направлений исследований является разработка и совершенствование различных приближенных, а также эвристических методов решения задач упаковки. Наиболее эффективными и хорошо зарекомендовавшими себя при решении таких задач являются эволюционные алгоритмы.

Широкий спектр применения решений задачи упаковки в различных сферах экономической деятельности делает задачу совершенствования существующих эвристических алгоритмов оптимизации решения и создания новых эффективных алгоритмов конструирования упаковки актуальной.

Степень разработанности проблемы. Разработке методов решения задач ортогональной упаковки посвящены работы, как отечественных авторов (А.С. Филиппова, А.Ф. Валеева, Ю.Г. Стоян, И.В. Романовский, В.М. Картак, Ю.И. Валиахметова, И.П. Норенков, Р.Р. Ширгазин, А.В. Чиглинцев, В.В. Бухвалова, А.Р. Усманова, М.А. Смагин и др.), так и зарубежных (П. Гилмори, Р. Гомори, И. Терно, Г. Шайтхауэр, Э. Фолкенауэр, А. Бортфельдт, Х. Дикхофф, С. Мартелло, Д. Виго, А. Лоди, Е. Хоппер и др). Значительный вклад в развитие методов решения задач упаковки внесла отечественная научная школа Э.А. Мухачевой. Проблемы эволюционного моделирования в задачах упаковки изучены в работах таких исследователей, как В.М. Курейчик, В.В. Курейчик, В.В. Емельянов, И.П. Норенков,

Д.И. Батищев, Э. Фолкенауэр и других отечественных и зарубежных исследователей.

Давая, безусловно, положительную оценку результатам работы всех вышеперечисленных исследователей, отметим наличие ещё нерешённых проблем, среди которых - выбор эффективной модели представления ортогональных объектов в контейнерах; разработка модели, выполняющей выбор наиболее подходящей области контейнера для каждого размещаемого объекта; разработка унифицированной модели решения задач упаковки произвольной размерности.

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

Для достижения указанной цели в работе поставлены следующие научные задачи:

1. Разработка эффективной модели конструирования упаковки, учитывающей состояние свободных областей контейнера.

2. Разработка унифицированного декодера строки решения для задач ортогональной упаковки различной размерности.

3. Разработка эффективных эвристик размещения ортогональных объектов для реализации мультиметодной технологии.

4. Разработка унифицированной модели решения задач упаковки объектов различной размерности на основе различных эвристических алгоритмов.

5. Разработка специализированного программного обеспечения для реализации и исследования разработанных моделей, алгоритмов и методов решения задач ортогональной упаковки.

6. Анализ эффективности разработанных алгоритмов и программного обеспечения по временным и качественным критериям.

Объектом исследования диссертационной работы являются задачи двухмерной и трёхмерной ортогональной упаковки объектов в контейнеры и задачи двухмерной ортогональной упаковки объектов на полубесконечную полосу заданной ширины.

Предметом исследования диссертационной работы являются алгоритмы оптимального размещения объектов в контейнерах и эвристические алгоритмы оптимизации субоптимальных решений задачи ортогональной упаковки.

Методы исследований. При решении задач, поставленных в работе, были использованы методы системного анализа, дискретной оптимизации и статистической обработки данных.

Научная новизна диссертационной работы заключается в следующих положениях:

6. 1. Разработаны модель «виртуальные объекты» для конструирования ортогональной упаковки и унифицированный декодер строки решения для ортогональных объектов произвольной размерности.

   2. Определен критерий останова эволюционного алгоритма, отслеживающий попадание популяции решений в локальные оптимумы целевой функции.

   3. Разработаны эвристики размещения объектов в контейнерах для мультиметодного генетического алгоритма.

   4. Разработана информационная модель, обеспечивающая унифицированный подход к решению задач упаковки произвольной размерности.

   Основные положения, выносимые на защиту:

   6. 4. 1. Модель «виртуальные объекты» быстрого конструирования ортогональной упаковки и унифицированный для ортогональных объектов различной размерности декодер строки решения.

         2. Результаты тестирования разработанного критерия останова эволюционного алгоритма.

         3. Результаты реализации мультиметодной технологии конструирования упаковки, использующей разработанные эвристики.

         4. Унифицированная модель решения задач упаковки объектов произвольной размерности.

         Практическая ценность диссертационной работы состоит в разработке программного обеспечения, реализующего алгоритмы решения задач ортогональной упаковки различной размерности, а также в разработке унифицированной библиотеки классов задач упаковки.

         Достоверность и обоснованность научных положений, рекомендаций и выводов обеспечиваются корректным использованием математического аппарата. Достоверность результатов работы подтверждается сериями вычислительных экспериментов путем глубокого анализа и сравнения полученных результатов с результатами решений, полученных другими отечественными и зарубежными исследователями.

         Реализация результатов работы. Результаты диссертационной работы внедрены в учебный процесс ГОУ ВПО МГТУ «Станкин» и в настоящее время используются при подготовке бакалавров по направлению 080800.62 «Прикладная информатика», магистрантов по магистерским программам: 220200.68-20 «Человеко-машинные системы управления» и 230100.68-01 «Теоретическая информатика». Материалы диссертационной работы использованы в качестве методологической основы при разработке общеуниверситетских курсов лекций и практических занятий по дисциплинам «Информатика» и специальным дисциплинам магистерской подготовки: «Интеллектуальные системы обработки информации», «Технология программирования в интеллектуальных системах управления».

         Определена целесообразность применения разработанных методик при создании прикладного программного обеспечения в малом инновационном предприятии ООО «Компьютерные системы и технологии» (г. Москва), выполняющем высокотехнологичные разработки, в том числе, для решения задач упаковки и логистики в интеллектуальных транспортных системах, а также - для оптимизации работы аптечного склада многопрофильной клинической больницы (г. Москва).

         Апробация работы. Основные научные и практические результаты работы докладывались на:

         4. научно-практической конференции «Автоматизация и информационные технологии (АИТ)» (Москва, ГОУ ВПО МГТУ «Станкин», 2008, 2009, 2010);

         5. XI научной конференции ГОУ ВПО МГТУ «Станкин» и «Учебно- научного центра математического моделирования МГТУ «Станкин» - ИММ РАН» по математическому моделированию и информатике, (Москва, 2008);

         6. XI международной конференции «ПРОТЭК'08» (Москва, ГОУ ВПО МГТУ «Станкин», 2008);

         7. школе-семинаре «Задачи системного анализа, управления и обработки информации» (Москва, ГОУ ВПО «Московский государственный университет печати», 2008, 2009);

         8. II Всероссийской студенческой научно-технической конференции «Прикладная информатика и математическое моделирование» (Москва, ГОУ ВПО «Московский государственный университет печати», 2008);

         9. III Всероссийской студенческой научно-технической конференции «Прикладная информатика и математическое моделирование» (Москва, ГОУ ВПО «Московский государственный университет печати», 2009);

         10. IV Всероссийской студенческой научно-технической конференции «Прикладная информатика и математическое моделирование» (Москва, ГОУ ВПО «Московский государственный университет печати», 2010);

         11. межвузовской научной конференции молодых ученых и студентов «Инновации в экономике» (Москва, ГОУ ВПО МГТУ «Станкин», 2009);

         12. III Всероссийской конференции студентов, аспирантов и молодых ученых «Искусственный интеллект: философия, методология, инновации» (Москва, ГОУ ВПО МИРЭА, 2009);

         13. VII международной научно-практической конференции «Trans-Mech- Art-Chem» (Москва, ГОУ ВПО МИИТ, 2010);

         14. III научно-образовательной конференции «Машиностроение - традиции и инновации» (Москва, ГОУ ВПО МГТУ «Станкин», 2010).

         В 2008 году проект «Повышение эффективности управления полезным пространством складов на основе эволюционных алгоритмов», включающий некоторые положения диссертационной работы, был удостоен диплома Всероссийской выставки научно-технического творчества молодежи НТТМ- 2008.

         Публикации. По теме диссертации опубликовано 20 научных работ, из них 14 основных, в том числе 3 статьи в изданиях, входящих в Перечень ведущих периодических изданий ВАК Министерства образования и науки РФ и 1 монография.

         Структура и объем диссертации. Диссертационная работа состоит из введения, четырёх глав, списка литературы и трёх приложений. Основной текст содержит 155 страниц. Список литературы состоит из 137 наименований. Приложения выполнены на шести страницах.

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

         Комбинированные алгоритмы решения задачи одномерной упаковкиНаумова Ольга Анатольевна

         

         Итерационные методы и алгоритмы решения задачи сильной отделимостиЕршова, Арина Владимировна

         

         Разработка и исследование нейросетевых алгоритмов решения задач навигации интеллектуальными мобильными агентами в нестационарных средахПриемко Андрей Анатольевич

         

         Разработка и оценки числа шагов алгоритмов решения задач распознавания образов при логико-аксиоматическом подходеКосовская, Татьяна Матвеевна

         

         Исследование и разработка бионических методов и алгоритмов для решения задач транспортного типаПолуян, Анна Юрьевна

         Нейросетевые алгоритмы для решения задач кодирования изображений с использованием технологии CUDAНгуен Виет Хунг

         Разработка эволюционных алгоритмов для решения задач теории расписаний в условиях неопределенностиРодькина, Маргарита Борисовна

         Разработка и исследование моделей и алгоритмов решения Евклидовой задачи Штейнера для трассировки электрических соединенийОрлов Николай Николаевич

         

         Полиномиальные алгоритмы для решения комбинаторных задач размещений прямоугольников Вяткина Кира Вадимовна

         

         Реляционно-ситуационные структуры данных, методы и алгоритмы решения поисково-аналитических задачСоченков Илья Владимирович