ISSN 1999-9429 · EISSN 2311-3103
Язык: ru

Статья: КОМБИНИРОВАННЫЙ ПОИСК ДЛЯ РЕШЕНИЯ ЗАДАЧИ ДВУМЕРНОЙ УПАКОВКИ ГЕОМЕТРИЧЕСКИХ ФИГУР СЛОЖНЫХ ФОРМ (2024)

Читать онлайн

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

Ключевые фразы: ДВУМЕРНАЯ УПАКОВКА, КОМБИНИРОВАННЫЙ ПОИСК, РАЗМЕЩЕНИЕ, ГЕНЕТИЧЕСКИЙ АЛГОРИТМ, БИОИНСПИРИРОВАННАЯ ЛОГИКА, АЛГОРИТМ ПЧЕЛИНОЙ КОЛОНИИ, оптимизация
Автор (ы): Курейчик Владимир Викторович, Халенков Александр Юрьевич
Журнал: ИЗВЕСТИЯ ЮФУ. ТЕХНИЧЕСКИЕ НАУКИ

Идентификаторы и классификаторы

УДК
004.896. Искусственный интеллект в промышленных системах. Интеллектуальные САПР и АСУ. Интеллектуальные роботы
eLIBRARY ID
69156307
Для цитирования:
КУРЕЙЧИК В. В., ХАЛЕНКОВ А. Ю. КОМБИНИРОВАННЫЙ ПОИСК ДЛЯ РЕШЕНИЯ ЗАДАЧИ ДВУМЕРНОЙ УПАКОВКИ ГЕОМЕТРИЧЕСКИХ ФИГУР СЛОЖНЫХ ФОРМ // ИЗВЕСТИЯ ЮФУ. ТЕХНИЧЕСКИЕ НАУКИ. 2024. № 3
Текстовый фрагмент статьи