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

• Автор: Ширгазин, Рамиль Ришатович
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Уфа
• Количество страниц: 108 с. : ил.

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

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

1.1. Задача одномерного раскроя.

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

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

1.4. Задача гильотинного раскроя

1.5. Обзор методов решения задач одно и двухмерного раскрояупаковки

1.5.1. Использование методов математического программирования

1.5.2. Применение методов комбинаторной оптимизации

1.5.3. Приблюсенные и эвристические методы

1.5.4. Вероятностные методы локального поиска оптимума.
1.6. Выводы.
2. Способы кодирования упаковок.
2.1. Прямой способ кодирования
2.2. Кодирование приоритетным списком.
2.3. Схема парных последовательностей.
2.4. Блочная технология кодированиядекодирования упаковок
2.4.1. Блок структуры упаковок и их свойства.
2.4.2. Преимущества блочной технологии кодирования упаковок
2.4.3. Алгоритмы построения упаковки декодеры. Декодер замещения
, следующий подходящий.
2.4.4. Декодер замещения , первый подходящий.
2.4.5. Декодер жадного замещения
2.4.6. Декодер пара списков
2.5. Выводы.
3. Эволюционные методы решения задач упаковки.
3.1. Наивный эволюционный метод iv ,
3.2. Эволюционный алгоритм 11
3.3. Метод последовательного уточнения оценок iv V
i, V
3.4. Генетические методы решения задачи упаковки. Общая характеристика
генетических методов
3.5. Схема жадного генетического алгоритма
3.6. Гибридный генетический алгоритм на базе V и .
3.7. Модификация методов для решения задачи упаковки на
прямоугольные листы.
3.8. Оценка эффективности алгоритмов. Нижние границы
3.8. Выводы.
4. Вычислительный эксперимент.
4.1. Программная реализация алгоритмов
4.2. Решение задач размещения на полосу на примерах
4.3. Исследование эффективности способов кодирования упаковки и
алгоритмов декодеров при использовании генетических алгоритмов
4.4. Исследование эффективности генетического гибридного алгоритма
i . Сравнительный эксперимент с метаэвристическими алгоритмами.
4.5. Решение задач размещения на листы на примерах . и .
4.6. Выводы.
Заключение
Список литературы


Разработать новый эффективный декодер на базе блочных структур, совмещающий высокую производительность простых эвристик с оптимальным использованием материала за счет применения «жадных» стратегий. Модифицировать эволюционные алгоритмы с применением жадного декодера замещения для поиска и исследования эффективных методов решения задачи упаковки. Создать программное обеспечение реализующее модифицированные и новые разработанные методы. Провести анализ эффективности и характеристик разработанных алгоритмов на основе результатов численных экспериментов в сравнении с другими методами, описанными в литературе. Эволюционный «наивный» алгоритм на базе простых эвристик типа «подходящий» и «наивного оператора мутации». Декодер жадного замещения Greedy Sub на базе блочной структуры и его модификации. Генетический алгоритм на базе блочных структур для решения задачи прямоугольной упаковки полубесконечной полосы и на листы. Гибридизация генетического алгоритма с блочным декодером жадного замещения. Программное обеспечение, реализующее разработанные алгоритмы и предназначенное для проведения численных экспериментов. Результаты исследования эффективности предложенных методов на основе проведенного численного эксперимента. Научная новизна работы. Блочный декодер жадного замещения» - создан новый эффективный метод конструирования двухмерной упаковки, который реализует жадную стратегию одновременно в разных направлениях, оперируя несколькими приоритетными списками прямоугольников; декодер может применяться в различных метаэвристиках. Новый метод локального поиска —оптимальной упаковки, представляющий собой генетический алгоритм с жадным блочным декодером. Показано, что такой подход дает лучшие решения и большую экономию материала по сравнению со многими известными в литературе реализациями. Модификация метода последовательного уточнения оценок на случай прямоугольной упаковки блочной структуры. Программное обеспечение реализующее новые методы расчета упаковок - ориентированное на численные эксперименты и промышленные расчеты. Экономический эффект составляет от 1% до % экономии материала. Связь исследования научными проектами: Работа выполнялась при частичной поддержке РФФИ, проект 0. Апробация работы. Международная конференция «Ресурсосберегающие технологии». Санкт-Петербург . Байкальская международная школа-семинар «Математическое программирование», Иркутск, . Международная конференция «Математическое программирование и приложения», Екатеринбург . Международная конференция ESICUP (Европейская специальная группа по раскрою и упаковке) (Germany, г. Семинары института вычислительной математики Дрезденского технологического университета, г. Конференция региональной зимней школы-семинара аспирантов и молодых ученых. Интеллектуальные системы обработки информации и управления», Уфа, г. В - учебном году прошел, по линии ДААД, научную стажировку в институте вычислительной математики Дрезденского технического университета. Результаты работа внедрены в учебный процесс УГЛТУ и в Центр Обработки Информации ОАО «Башнефтегеофизика» г. Уфа. Правовая сторона программного обеспечения защищена в РОСПАТЕНТ «Свидетельством об официальной регистрации программ для ЭВМ» №. Во введении к диссертации обоснована актуальность решаемой научной проблемы; сформулирована цель и задачи исследования; приведены результаты, выносимые на защиту; отмечена их научная новизна и практическая значимость. Приведены сведения об апробации работы и публикациях. В первой главе проведен аналитический обзор моделей и методов решения задач прямоугольной упаковки и раскроя. Во второй главе приводятся различные варианты кодирования -декодирования упаковок. Рассмотрена модель блок - структуры упаковки и описаны различные варианты блочных декодеров. Предложен новый блочный декодер «жадного» замещения. Третья глава посвящена эволюционным методам решения задач упаковки, методам локального поиска. Предложена модификация генетического алгоритма с использованием блочного декодера «жадного» замещения. В четвертой главе приведено описание программного обеспечения и приведены результаты численных экспериментов.