Разработка биоинспирированного алгоритма решения задачи двумерной упаковки 

Резюме: В статье рассмотрены актуальные вопросы и проведен анализ проблем, касающихся задачи упаковки разногабаритных блоков, в метрике двоичного пространства для решения проблемы оптимального размещения двумерных объектов на карте раскроя с целью минимизации расходов на их распил. Для решения такого рода задач, необходимо прибегнуть к практике использования биоинспирированной логики, основанной на поведении стаи серых волков в природе. На данной основе был разработан модифицированный алгоритм, позволяющий эффективно решать задачу двумерной упаковки, после чего были проведены соответствующие эксперименты, доказавшие его эффективность. Основываясь на эффективности данного метода, был разработан и реализован программный продукт, использующий разработанную архитектуру поиска решения и перспективные технологии дополненной виртуальной реальности, который позволяет отображать на актуальных смартфонах результат работы алгоритма. Представлены и подробно описаны основные преимущества применения принципов интеграции технологий виртуальной и дополненной реальности, дается подробный обзор и анализ проблем и перспектив решения задач упаковки, их видам. Поясняется актуальность исследований в этой работе. После чего поясняется основная задача данной работы, которая может быть сформулирована как: нахождение оптимального принципа заполнения двумерного контейнера заданными объектами. Приводятся аргументы о том, что задачи упаковки не абстрактны, а много, где применимы. А именно конкретные примеры того, в каких сферах промышленности данные задачи применяются и кому алгоритмы их решения помогают. Каждому из типов задач упаковки дается пояснение с примерами, после чего дается пояснение перспективным технологиям дополненной и виртуальной реальности. Важнейшим практически значимым результатом исследований обозначенной проблемы является разработанная программно-инструментальная платформа проектирования на современном языке программирования Swift. Данный язык несмотря на недавнюю популярность почти полностью вытеснил своего основного конкурента Objective-C, а возможность поддержки таких плагинов как Vuforia делает его идеальным для разработки приложений. Разработанный программный продукт обладает простым и понятным интерфейсом, максимально оптимизированным под самые слабые аппараты, что позволяет эффективно задавать переменные в задаче и быстро получать решение задачи. Результаты проделанных экспериментальных исследований позволяют с уверенностью заявлять об эффективности программы, полученных теоретических оценок временной сложности и эффективности преложенных подходов и алгоритмов, в том числе генетического алгоритма, который использует предложенный в работе новый механизм кодирования решений.

Ключевые слова: двумерная упаковка, виртуальная реальность, дополненная реальность, генетический алгоритм, биоинспирированный алгоритм, стая серых волков, алгоритм стаи серых волков.

E.V. Kuliev, E.M. Gerasimenko, A.U. Khalenkov, M.M. Semenova, S.V. Ignatieva 

Developme nt of a bioinspired algorithm for solv ing the problem of two -dimensional packing 

Summary: The article discusses topical issues and analyzes the problems related to the problem of packing blocks of different sizes in the metric of binary space to solve the problem of optimal placement of two-dimensional objects on the cutting map in order to minimize the cost of cutting them. To solve this kind of problems, it is necessary to resort to the practice of using bioinspired logic based on the behavior of a pack of gray wolves in nature. On this basis, a modified algorithm was developed that allows one to effectively solve the problem of two-dimensional packing, after which the corresponding experiments were carried out to prove its effectiveness. Based on the effectiveness of this method, a software product was developed and implemented using the developed architecture for finding a solution and promising technologies of augmented virtual reality, which allows the result of the algorithm to be displayed on actual smartphones. The main advantages of applying the principles of integration of virtual and augmented reality technologies are presented and described in detail, a detailed overview and analysis of the problems and prospects for solving packaging problems, their types are given. The relevance of research in this work is explained. After that, the main task of this work is explained, which can be formulated as: finding the optimal principle of filling a two-dimensional container with specified objects. Arguments are made that packing problems are not abstract, but many where applicable. Namely, specific examples of in which areas of industry these problems are applied and to whom the algorithms for their solution help. Each type of packaging problem is explained with examples, followed by an explanation of promising augmented and virtual reality technologies. The most important practically significant result of the research of the indicated problem is the developed software and instrumental design platform in the modern programming language Swift. Despite its recent popularity, this language has almost completely supplanted its main competitor Objective-C, and the ability to support plugins such as Vuforia makes it ideal for application development. The developed software product has a simple and intuitive interface, optimized as much as possible for the weakest devices, which allows you to effectively set the variables in the problem and quickly obtain a solution to the problem. The results of the experimental studies performed allow us to state with confidence about the effectiveness of the program, the obtained theoretical estimates of the time complexity and effectiveness of the proposed approaches and algorithms, including the genetic algorithm, which uses the new solution coding mechanism proposed in the work.

Keywords: two-dimensional packaging, virtual reality, augmented reality, genetic algorithm, bioinspired algorithm, a flock of gray wolves, algorithm of a pack of gray wolves. 

DOI:10.34219/2078-8320-2021-12-3-78-85