Найти

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

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

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

  2024-08-12

  Аннотация ▼

  Рассмотрена задача двумерной упаковки геометрических фигур сложных форм. Задачи дан-
  ного класса отнесены к классу NP-трудных проблем комбинаторной оптимизации. Помимо этого,
  упаковка фигур сложных геометрических форм, является одним из наиболее сложных подтипов
  задачи двумерной упаковки. В связи с этим необходима разработка эффективных эвристических
  подходов к решению данной задачи. В статье дана постановка задачи, описаны ее основные осо-
  бенности, приведены ограничения и условия характерные для данного подтипа задачи двумерной
  упаковки. Описан критерий для подсчета эффективности решения. Для решения данной задачи в
  статье предлагается архитектура комбинированного поиска, состоящая из двух метаэвристиче-
  ских вычислительных алгоритмов. В данной архитектуре в качестве оптимизационных методов
  были реализованы модифицированный генетический и роевой мультиагентный биоинспирирован ный алгоритм, основанный на поведении пчелиной колонии. Данные алгоритмы позволяют полу-
  чать наборы квазиоптимальных решений за полиномиальное время. Приведены преимущества от
  использования предлагаемого подхода. Для проверки эффективности предложенного подхода был
  разработан программный продукт, который использует предложенную архитектуру и метаэври-
  стические вычислительные алгоритмы при решении поставленной задачи. Разработка программ-
  ного продукта велась на языке программирования C++ и написана в среде разработки Microsoft
  Visual Studio Code. Проведен вычислительный эксперимент на наборе тестовых примеров-
  бенчмарок. По результатам экспериментальных исследований сделан вывод об эффективности
  предложенного комбинированного поиска при решении задачи двумерной упаковки геометрических
  фигур сложных форм в сравнении с решениями, базирующимися на классических алгоритмах

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

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

  2023-12-11

  Аннотация ▼

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