Найти

Результаты поиска

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

  В.В. Курейчик , В.В. Бова , А.Ю. Халенков

  2023-12-11

  Аннотация ▼

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