А. С. Филиппова

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

Рассматриваются NP-трудные задачи прямоугольной упаковки в различных постановках. Для их решения применяются методы локального поиска оптимума: эволюционные стратегии и генетические методы. Модели упаковок и алгоритмы поиска лучших из них основаны на блок-структурах и их свойствах. Сопутствующие проблемы кодирования и декодирования упаковок также опираются на блок-структуры. Это позволяет использовать в качестве генотипов решения одномерных задач упаковки и включать эволюционные процессы на их уровне. Приведены результаты численного эксперимента, подтверждающие высокую эффективность предложенных алгоритмов.




Philippova A. S.

Modeling of Evolution Algorithms for Rectangular Packing Problems Based on Block Structure Technology

Different NP-hard problems of rectangular packing are considered in the paper. To solve them two methods of optimum local search are applied, namely: the evolution strategy and genetic methods. The packing models and search algorithms of the best of them are based on the block-structures and their properties. The packing coding-decoding problems going alongside are also based on the block-structures. This fact makes it possible to use the solutions of one-dimensional rectangular packing problems as genotypes and to include the evolution processes on their level. The results of the numerical experiment proving high efficiency of the suggested algorithms are shown.

ОГЛАВЛЕНИЕ

Введение

1. Математические модели основных задач и способы кодирования упаковки
1.1. Модели основных задач упаковки
1.2. Кодирование схемы упаковки
1.3. Свойства блок-структур
2. Задачи прямоугольно-ориентированного линейного раскроя
3. Эвристические методы конструирования упаковок
3.1. Характеристика уровневых стратегий простых эвристик
3.2. Характеристика безуровневых стратегий
3.3. Характеристика блочных стратегий простых эвристик
3.4. Метод перестройки (Reconstruciion, Rec)
3.5. Метод парных списков локального поиска оптимума (Local Search Dublicity, LCD)
4. Эволюционные методы локального поиска оптимума
4.1. Общие схемы эволюционного алгоритма
4.2. Общие схемы стратегий (1, l)-ЕА и (1 + 1)-ЕА для решения задач 2DSP
4.3. Генетический блочный алгоритм (Genetic Block Algorithm, GBA)
4.4. Генетический алгоритм в задачах двухмерного гильотинного раскроя
5. Численные эксперименты
6. Список литературы