Найти

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

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

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

  2024-08-12

  Аннотация ▼

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