КОМБИНИРОВАННЫЙ ПОИСК ДЛЯ РЕШЕНИЯ ЗАДАЧИ ДВУМЕРНОЙ УПАКОВКИ ГЕОМЕТРИЧЕСКИХ ФИГУР СЛОЖНЫХ ФОРМ
Аннотация
Рассмотрена задача двумерной упаковки геометрических фигур сложных форм. Задачи дан-
ного класса отнесены к классу NP-трудных проблем комбинаторной оптимизации. Помимо этого,
упаковка фигур сложных геометрических форм, является одним из наиболее сложных подтипов
задачи двумерной упаковки. В связи с этим необходима разработка эффективных эвристических
подходов к решению данной задачи. В статье дана постановка задачи, описаны ее основные осо-
бенности, приведены ограничения и условия характерные для данного подтипа задачи двумерной
упаковки. Описан критерий для подсчета эффективности решения. Для решения данной задачи в
статье предлагается архитектура комбинированного поиска, состоящая из двух метаэвристиче-
ских вычислительных алгоритмов. В данной архитектуре в качестве оптимизационных методов
были реализованы модифицированный генетический и роевой мультиагентный биоинспирирован ный алгоритм, основанный на поведении пчелиной колонии. Данные алгоритмы позволяют полу-
чать наборы квазиоптимальных решений за полиномиальное время. Приведены преимущества от
использования предлагаемого подхода. Для проверки эффективности предложенного подхода был
разработан программный продукт, который использует предложенную архитектуру и метаэври-
стические вычислительные алгоритмы при решении поставленной задачи. Разработка программ-
ного продукта велась на языке программирования C++ и написана в среде разработки Microsoft
Visual Studio Code. Проведен вычислительный эксперимент на наборе тестовых примеров-
бенчмарок. По результатам экспериментальных исследований сделан вывод об эффективности
предложенного комбинированного поиска при решении задачи двумерной упаковки геометрических
фигур сложных форм в сравнении с решениями, базирующимися на классических алгоритмах
Литература
design: textbook]. Moscow: Izd-vo MGTU imeni N.E. Baumana, 2006, 336 p.
2. Kormen, T. Leyzerson I., Rivest R. Algoritmy. Postroenie i analiz [Algorithms. Construction and analysis].
Moscow: MTSMO, 2000.
3. Kureichik V.V., Kureichik V.M. Genetic Search-Based Control, Automation and Remote Control, 2001,
Vol. 62, 10, pp. 1698-1710.
4. Karpenko A.P. Sovremennye algoritmy poiskovoy optimizatsii. Algoritmy, vdokhnovlennye prirodoy:
ucheb. posobie [Modern search engine optimization algorithms. Algorithms inspired by nature: textbook.
Allowance]. Moscow: Izd-vo MGTU im. N.E. Baumana, 2014.
5. Rodzin S.I., Kureychik V.V. Teoreticheskie voprosy i sovremennye problemy razvitiya kognitivnykh
bioinspirirovannykh algoritmov optimizatsii (obzor) [Theoretical issues and modern problems in the development
of cognitive bioinspired optimization algorithms (review)], Kibernetika i programmirovanie
[Cybernetics and Programming], 2017, No. 3, pp. 51-79.
6. Abraham A., Ramos V., Grosan G. Swarm Intelligence in Data Mining. Berlin. Heidelberg: Springer
Verlag, 2007, 267 p.
7. Hassanien E. Emary E. Swarm Intelligence: Principles Advances, and Applications. CRC Press,
2015, 228 p.
8. Mourelle M., Nedjah L. De Swarm intelligent systems. Berlin: Heidelberg: Springer Verlag, 2006, 217 p.
9. Mukhacheva E.A., Verkhoturov M.A, Martynov V.V. Modeli i metody rascheta raskroya – upakovki
geometricheskikh ob"ektov [Models and methods for calculating cutting - packaging of geometric objects].
Ufa: UGATU, 1998, 216 p.
10. Levin M.Sh. Upakovka v konteynery (perspektivnye modeli, primery) [Packaging in containers (promising
models, examples)], Informatsionnye protsessy [Information processes], 2017, No. 1, pp. 43-60.
11. Kuliev E.V., Gerasimenko E.M., Khalenkov A.Yu, Semenova M.M., Ignat'eva S.V. Razrabotka
bioinspirirovannogo algoritma resheniya zadachi dvumernoy upakovki [Development of a bioinspired
algorithm for solving the two-dimensional packaging problem], Informatizatsiya i svyaz'
[Informatization and Communication], 2021, No. 3, pp. 78-85.
12. Vanidovskiy V.A., Lebedev O.B., Pantelyuk E.A., Kulieva N.V. Dvumernaya upakovka v
poluogranichennuyu polosu na osnove modelirovaniya adaptivnogo povedeniya murav'inoy kolonii
[Two-dimensional packing in a semi-limited strip based on modeling the adaptive behavior of an ant
colony], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2014, No. 9,
pp. 21-27.
13. Orlov A.N., Kureychik V.V., Glushchenko A.E. Kombinirovannyy geneticheskiy algoritm resheniya
zadachi raskroya [Combined genetic algorithm for solving the cutting problem], Izvestiya YuFU.
Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2016, No. 6 (179), pp. 5-13.
14. Kureychik V.V., Bova V.V., Kureychik V.V. Kombinirovannyy poisk pri proektirovanii [Combined
search in design], Obrazovatel'nye resursy i tekhnologii [Educational resources and technologies],
2014, No. 2 (5), pp. 90-94.
15. Lawrence Davis. Handbook of Genetic Algorithms, Ed. by Lawrence Davis. USA: Van Nostrand
Reinhold, New York, 1991, 100 p.
16. Holland John H. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Application
to Biology, Control, and Artificial Intelligence. USA: University of Michigan, 1975, 183 p.
17. Goldberg David E. Genetic Algorithm in Search, Optimization and Machine Learning. USA: Addison-
Wesley Publishing Company. Ind., 1989, 196 p.
18. Karaboga D. An idea based on honey bee swarm for numerical optimization. Erciyes University, Engineering
Faculty, Computer Engineering Department, 2005, 110 p.
19. Xiuqin P, Yun W, Yong L, Na S. Improved artificial bee colony algorithm based on two-dimensional
queue structure for complex optimization problems, Alexandria Engineering Journal, 2024, Vol. 86,
pp. 669-679.
20. Kureychik V.V., Polupanova E.E. Evolyutsionnaya optimizatsiya na osnove algoritma kolonii pchel
[Evolutionary optimization based on the bee colony algorithm], Izvestiya YuFU. Tekhnicheskie nauki
[Izvestiya SFedU. Engineering Sciences], 2009, No. 12 (101), pp. 41-46.
21. Pham D.T., Castellani M. The Bees Algorithm – Modelling Foraging Behaviour to Solve Continuous
Optimization Problems, Proc. ImechE, Part C, 2009, 223 (12), pp. 2919-2938.
22. Weiss M.A. Data Structures and Algorithm Analysis in C++. Boston: Pearson Education, 2014, 656 p.
