УДК 004.023

Исследование эвристических и метаэвристических алгоритмов решения задач раскроя-упаковки

Майрамты Мария Васильевна – аспирант кафедры компьютерного моделирования и автоматизации проектирования Северо-Кавказского горно-металлургического института (Государственного технологического университета

Аннотация: В этой статье рассматриваются вопросы анализа эвристических и метаэвристических методов решения задач раскроя-упаковки. Эффективность применения эвристических и метаэвристических алгоритмов оптимизации решения задач раскроя-упаковки исследуется при решении различных наборов задач упаковки на полубесконечную полосу (рулонного раскроя), а также при решении стандартных тестовых задач упаковки ортогональных объектов.

Ключевые слова: упаковка, генетический алгоритм (ГА), метод имитации отжига, 1.5DBP, полубесконечная полоса, генетические операторы, отжиг.

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

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

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

Представление решения задачи в виде последовательности выбора размещаемых объектов не всегда оказывается эффективным, особенно при увеличении размера задачи (числа размещаемых объектов). Одной из перспективных технологий оптимизации решения NP-трудных задач является мультиметодная технология, в основу которой положена идея кодирования решения задачи в виде последовательности элементарных алгоритмов решения задачи, называемых эвристиками [2].

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

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

Работа алгоритма показана на рисунке 2 и основана на том, что по закону Больцмана вероятность любой конфигурации i атомов есть , где E(i) – энергия, соответствующая конфигурации I, k_b – постоянная Больцмана [3]. При данной температуре вероятны конфигурации с более низкой энергией. В таком случае можно генерировать данные конфигурации случайным образом для получения конфигурации с минимальной энергией.

 

Рисунок 1. Блок-схема алгоритма имитации отжига.

Одним из наиболее перспективных подходов в области применения метаэвристических алгоритмов оптимизации является использование генетического алгоритма (МГА), в котором хромосомы представляют собой последовательности применяемых эвристик.

Генетические алгоритмы анализируют и преобразуют популяцию хромосом на основе механизма натуральной эволюции [4]. Каждая популяция обладает наследственной изменчивостью. Это означает наличие возможностей случайных отклонений от наиболее вероятного среднего значения целевой функции. Отклонения описываются нормальным распределением случайных величин. Наследственные признаки обеспечивают популяции лучшие условия существования и размножения. Для сравнения на рисунке 2 приведены блок-схемы работы простого генетического алгоритма и модифицированного генетического алгоритма:

Рисунок 2. Сравнение блок-схем простого генетического алгоритма и модифицированного генетического алгоритма: а) простой ГА;          б) модифицированный ГА.

Была рассмотрена задача упаковки прямоугольных объектов в полубесконечную полосу (1.5DBP). Для решения задачи были разработаны две эвристики: «Следующий по убыванию длины» (NFDL) и «Нижний левый» (Bottom-Left, BL). Эти эвристики представляют собой способы размещения объектов на полубесконечной полосе.

На рисунках 2 и 3 представлена работа данных эвристик для заданного набора прямоугольных объектов с известными параметрами и заданной шириной полосы упаковки.

Рисунок 3. Работа алгоритма с применением эвристики «Следующий по убыванию длины».

Рисунок 4. Работа алгоритма с применением эвристики «Нижний левый».

Сравнивая результаты работы эвристик, можно увидеть, что «Нижний левый», по сравнению с «Следующий по убыванию длины», находит решение, которое ближе к оптимальному – в первом случае длина занятой части полосы составляет 351, а во втором - 441.

Таким образом, для дальнейшей работы поиска оптимального решения была выбрана эвристика «Нижний левый». Сравнивались решения задач упаковки прямоугольных объектов в полубесконечную полосу (1.5DBP) двумя методами: генетический алгоритм и алгоритм имитации отжига.

Задача решалась на семи категориях входных данных различной размерности в пределах от 16 до 197 (под размерностью понимается количество элементов) [5]. Каждая категория содержит по три примера с уже известными оптимальными результатами размещения объектов для сравнения с полученными результатами при применении двух рассмотренных алгоритмов. Результаты сведены в таблицу 1.

Таблица 1. Сравнение оптимальных результатов с полученными результатами работы двух рассмотренных алгоритмов.

Категория	Пример	Количество элементов	Ширина полосы	Оптимальный результат	Результат, полученные генетическим алгоритмом (Left Bottom)	Результат, полученные методом имитации отжига (Left Bottom)
С1	P1	16	20	20	25	22
	P2	17	20	20	25	21
	P3	16	20	20	25	21
С2	P1	25	40	15	22	17
	P2	25	40	15	26	16
	P3	25	40	15	24	16
С3	P1	28	60	30	39	31
	P2	29	60	30	40	32
	P3	28	60	30	40	32
C4	P1	49	60	60	79	63
	P2	49	60	60	77	66
	P3	49	60	60	78	64
C5	P1	72	60	90	110	92
	P2	72	60	90	120	100
	P3	72	60	90	117	96
C6	P1	97	80	120	157	136
	P2	97	80	120	169	137
	P3	97	80	120	165	135
C7	P1	196	160	240	322	280
	P2	197	160	240	350	308
	P3	196	160	240	348	299

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

Список литературы

1. Валиахметова Ю.И., Филиппова А.С. Теория оптимального использования ресурсов Л.В. Канторовича в задачах раскроя-упаковки: обзор и история развития методов решения // Вестник УГАТУ. 2014. Т. 18, № 1 (62). С. 186-197.
2. Лысенко М.А. Об алгоритмах принятия решений в NP-полных задачах дискретной оптимизации // Вектор науки ТГУ. 2010. № 4 (14).
3. Глушань В.М. Метод имитации отжига // Известия ТРТУ. Тематический выпуск «Интеллектуальные САПР». С. 148-150.
4. Подлазова А.В. Генетические алгоритмы на примерах решения задач раскроя // Проблемы управления. Информатика и системы управления. 2008. № 2. С. 57-63.
5. http://www.bazissoft.ru/products/bazis_package/.