МНОГОУРОВНЕВЫЙ ПОДХОД ДЛЯ РЕШЕНИЯ ЗАДАЧИ ДВУМЕРНОЙ УПАКОВКИ ГЕОМЕТРИЧЕСКИХ ФИГУР СЛОЖНЫХ ФОРМ

Аннотация

Рассмотрена одна из важных комбинаторных задач оптимизации – задача двумер- ной упаковки геометрических фигур сложных форм. Она относится к классу NP- сложных и трудных оптимизационных задач. В работе приведена и описана постановка задачи дву- мерной упаковки, введена комбинированная целевая функция, учитывающая все ограниче- ния. В связи со сложностью данной задачи предлагается многоуровневый подход, заклю- чающийся в разделение задачи двумерной упаковки на 4 подзадачb и решения каждой под- задачи последовательно в строгом порядке. При этом для каждой из подзадач определен уникальный набор объектов, не повторяющихся в остальных подзадачах. Для реализации многоуровневого подхода авторами разработан комбинированный биоинспирированный алгоритм, основанный методах генетического поиска и биоинспирированной оптимизации. Такой подход позволяет значительно сократить время получения результата, частично решить проблему предварительной сходимости алгоритмов и получить наборы квазиоти- мальных решений за полиномиальное время. Разработан программный комплекс и реализо- ваны на ЭВМ алгоритмы автоматизированной двухмерной упаковки на основе комбиниро- ванного биоинспирированного алгоритма. Проведен вычислительный эксперимент на тес- товых примерах (бенчмарках). Качество упаковки, полученное, на основе разработанного комбинированного биоинспирированного алгоритма, в среднем на 2 % превосходит резуль- таты упаковки, полученные с использованием известных алгоритмов при сопоставимом времени решения, что говорит об эффективности предложенного подхода. Проведенные серии тестов и экспериментов позволили уточнить теоретические оценки временной сложности алгоритмов упаковки. В лучшем случае временная сложность алгоритмов O(n2), в худшем случае - O(n3).