АНАЛИЗ НЕКОТОРЫХ МЕТАЭВРИСТИЧЕСКИХ МЕТОДОВ ПРИ РЕШЕНИИ ЗАДАЧИ УПАКОВКИ В ПОЛУБЕСКОНЕЧНУЮ ПОЛОСУ

АННОТАЦИЯ

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

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

Формальную постановку задачи упаковки в полубесконечную полосу (1.5dbpp) можно сформулировать следующим образом.

Заданы полубесконечная полоса ширины W, m прямоугольных предметов, длина и ширина которых известны, , и условия, где () – координаты левого нижнего угла прямоугольника на полосе:

- при размещении на полосе никакие два предмета не пересекаются друг с другом, т. е. для

(()

- никакой предмет не пересекает границ полосы для

();

- стороны прямоугольников параллельны граням полосы – условие ортогональности [1].

Необходимо разместить на полосе без перекрытий набор прямоугольных предметов так, чтобы занятая ими часть полосы была минимальна по длине, т.е. надо найти такой набор (), , чтобы . Геометрический смысл переменных W, L, (), (), проиллюстрирован на рисунке 1.

Собрав все вышесказанные параметры можно вывести математическую постановку задачи:

Генетический алгоритм для решения задачи упаковки в полубесконечную полосу – это алгоритм поиска приближенного решения поставленной задачи. В реализованной программе используется следующий алгоритм (t-е поколение популяции обозначается как {}):

1. Создается начальная популяция случайным образом {}.
2. Вычисляется приспособленность каждой особи популяции {}.
3. Производится отбор особей из {} в соответствии с их приспособленностями и применяется генетический оператор скрещивания к отобранным особям для получения потомства – нового поколения {}.
4. Шаги 1, 2 для t = 0, 1, 2, … повторяются до тех пор, пока не выполнится условие окончания поиска – достигается заданный предел числа поколения t [2].

Входными данными для алгоритма являются: количество объектов n, размерность популяции L, количество популяций S, ширина полосы W. Размер популяции остается постоянной в каждой итерации алгоритма. По полученному решению происходит построение карты упаковки для заданного набора прямоугольных объектов.

Метод имитации отжига для решения задачи упаковки в полубесконечную полосу. Входными данными для метода являются: количество объектов n, ширина полосы W, начальная температура T.

В реализованной программе используется следующая схема алгоритма имитации отжига для задач прямоугольной упаковки в полосу (1,5DBP):

Шаг 1. Строится начальное решение.

Шаг 2. Задается начальная температура

Шаг 3. Следующие шаги повторяются k раз, пока не выполнится критерий остановки:

3.1. Выбрать случайным образом соседнее решение из окрестности решения.

3.2. Вычислить.

3.3. Если, то положить.

3.4. Если, то положить с вероятностью.

3.5 Понизить температуру.

Шаг 4. Выдать лучшее найденное решение [4].

Для осуществления перестановок используются операции СДВИГ(i, j) и ЗАМЕНА(i, j), с помощью которых строятся окрестности решений. Операция СДВИГ(i, j) ставит предмет i в позицию предмета j. Операция ЗАМЕНА(i, j) меняет местами в перестановке предметы i и j.

Метод муравьиных колоний для решения задачи упаковки в полубесконечную полосу. Параметры алгоритма: k – размерность популяции; m – количество агентов; α – коэффициент влияния феромона; β – коэффициент влияния эвристической информации; τ_init – начальное значение феромона; τ_max – значение феромона.

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

1. Выбирается компонент и помещается в нижний левый угол полосы. Для каждого из агентов, не завершивших построение выполняем:
2. Следующий компонент добавляется к частично построенному решению. Если |P|=k, то удаляется из популяции решение.
3. Выполняется обновление феромона.
4. Лучшее решение добавляется в популяцию P и выдается результат – лучшее найденное решение [5].

Параметры известных тестовых примеров для задачи упаковки в полубесконечную полосу (1.5DBP) указаны в таблице 1. Результаты эксперимента были сведены в таблицу 2. Сравнивались результаты, полученные на семи категориях входных данных различной размерности в пределах от 16 до 197, под размерностью понимается количество элементов. Каждая категория содержит по три примера. При проведении эксперимента использовались следующие эвристики: генетический алгоритм, алгоритм имитации отжига, алгоритм муравьиных колоний. Процедура упаковки элементов в полосу проходила с помощью декодера «Нижний левый» (Bottom Left).

Таблица 1.

Параметры тестовых наборов данных

Таблица 2.

Сравнение оптимального результата с полученными результатами при применении трех рассмотренных алгоритмов 1.5DBP

На рисунке 1 приведена гистограмма, где проводится сравнение результатов, полученными в ходе эксперимента. Из гистограммы видно, что алгоритм имитации отжига на всех заданных категориях является эффективнее двух других алгоритмов.

Рисунок 1. Гистограмма сравнения оптимальных результатов, полученных в ходе проведения эксперимента

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

1. Подлазова А.В. Генетическкие алгоритмы на примерах решения задач раскроя // Проблемы управления. Информатика и системы управления. – 2008. – №2 –С. 57-63.
2. Валиахметова Ю.И., Филиппова А.С. Теория оптимального использования ресурсов Л.В. Канторовича в задачах раскроя-упаковки: обзор и история развития методов решения / Уфа: Изд-во «Вестник УГАТУ». – 2014. – Т.18 – №1 (62) –С. 186-197.
3. Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы: Учебное пособие. / М.: ФИЗМАТЛИТ. – 2006. – 320 с.
4. А.С. Руднев «Алгоритмы локального поиска для задач двумерной упаковки» [Интернет-ресурс]. Режим доступа: http://math.nsc.ru/LBRT/ k5/Panin/Rudnev_PhD.pdf (дата обращения 31.07.2020 г.).
5. Файзрахманов Р.И. Конструктивный вероятностный алгоритм для задачи размещения кругов и прямоугольников / Уфа: Изд-во «Вестник УГАТУ». – 2010. – №4 (39) –С. 132–138.