МНОГОСТАДИЙНЫЙ МУРАВЬИНЫЙ АЛГОРИТМ ОДНОМЕРНОЙ УПАКОВКИ НА БАЗЕ ЭФФЕКТИВНЫХ МЕТОДОВ КОДИРОВАНИЯ РЕШЕНИЙ, И ДВУХУРОВНЕВОЙ ЭВОЛЮЦИОННОЙ ПАМЯТИ
Аннотация
Целью работы является разработка и исследование методов биоинспирированного поиска для решения задач одномерной упаковки в одинаковые контейнеры на базе эффективных алгоритмов кодирования и декодирования решений, композитного критерия и двухуровневой структуры эволюционной памяти. В работе предложена структура упорядоченного кода упаковки одномерных элементов в одинаковые контейнеры главное достоинство которого заключается в том, что одному решению упаковки соответствует один код и наоборот. Поисковая процедура базируется на модифицированной метаэвристике муравьиного алгоритма. На каждой итерации алгоритм одномерной упаковки имеет многостадийную структуру. Стадии выполняются последовательно одна за другой, начиная с первой. Каждая стадия Сk включает процедуры, выполняемые агентом zk. Число стадий равно числу агентов в популяции плюс заключительная стадия итерации. Основная задача, решаемая конструктивным алгоритмом на стадии Сk, заключается в построении кода Rk упаковки множества элементов X в одинаковые контейнеры. Стадия делится на периоды по числу формируемых агентом zk списков Xjк. Период делится на этапы. На каждом периоде последовательно по этапам решаются следующие задачи: агент zk конструктивным алгоритмом формирует набор Rk упорядоченных списков Xjк одномерной упаковки в одинаковые контейнеры; рассчитываются оценки fjk упаковки каждого контейнера Oj элементами списка <Xjк>; рассчитывается количество λjk феромона, пропорциональное оценке fjk; рассчитывается оценка Wk=∑i(fjk) одномерной упаковки множества элементов X в H одинаковых контейнеров; производится отложение феромона на ребрах графа G, соответствующих списку Xjк в ячейки накопительной матрицы памяти E второго уровня. После формирования всеми агентами zk популяции Z упорядоченных списков Rk, накопленный феромон добавляется в основную матрицу памяти Φ первого уровня. Для каждого Rk рассчитывается общий показатель Fk качества упаковки множества элементов X. Заключительная операция на итерации ‒ испарение феромона на ребрах графа G и фиксация zk c лучшим Fk. Проведены экспериментальные исследования заключающиеся в выяснении качества работы метода на тестовых наборах большой размерности. Для сравнения разработанного алгоритма с известными методами и с приближенными алгоритмами авторами было выбрано несколько групп бенчмарок из различных источников
Список литературы
1. Kormen T.L. Algoritmy. Postroenie i analiz [Algorithms. Construction and analysis]. Moscow: Vil'yams, 2007, 196 p.
2. Bischoff E.E. Cutting and packing, European Journal of Operational Research, 1995, pp. 503-505.
3. Lebedev B.K., Lebedev O.B., Ganzhur M.A. Odnomernaya upakovka modifitsirovannym metodom mu-rav'inoy kolonii [One-dimensional packing by a modified ant colony method], Tr. kongressa po intel-lektual'nym sistemam i informatsionnym tekhnologiyam «IS– IT’23» [Proceedings of the Congress on Intelligent Systems and Information Technologies «IS-IT'23»]. Scientific publication. Taganrog: Izd-vo YuFU, 2023, Vol. 1, pp. 153-161.
4. Kureychik V.M., Potarusov R.V. Problema odnomernoy upakovki elementov [The problem of one-dimensional packing of elements], Izvestiya TRTU [Izvestiya TSURE], 2006, No. 8, pp. 88-93.
5. Karpenko A.P. Sovremennye algoritmy poiskovoy optimizatsii. Algoritmy, vdokhnovlennye prirodoy: ucheb. posobie [Modern algorithms of search engine optimization. Algorithms inspired by nature: a tuto-rial]. Moscow: Izd-vo MGTU im. N.E. Baumana, 2021, 448 p.
6. Kureychik V.M., Lebedev B.K., Lebedev O.B. Poiskovaya adaptatsiya: teoriya i praktika [Search adapta-tion: theory and practice]. Moscow: Fizmatlit, 2006, 272 p.
7. Ross P.G., Marin-Blazquez J.G., Schulenburg S.A. Learning a Procedure That Can Solve Hard Bin-Packing Problems: A New GA-Based Approach to Hyper-heurstics, Proceeding of the Genetic and Evolutionary Computation Conference. Chicargo: GECCO, 2003, pp. 1295-1306.
8. Gupta J.N., Ho J.C. A New Heuristic Algorithm for the One-dimensional Bin-packing Problem, Pro-duction Planning & Control, 2009, Vol. 10, pp. 598-603.
9. Levine J.M., Ducatelle F.C. Ant Colony Optimization and Local Search for Bin Packing and Cutting Stock Problems, Centre for Intelligent Systems and their Applications. Edinburgh: University of Edin-burgh, 2003, pp. 50-64.
10. Lebedev B.K., Lebedev O.B. Raspredelenie resursov na osnove gibridnykh modeley roevogo intellekta [Resource allocation based on hybrid models of swarm intelligence], Nauchno-tekhnicheskiy vestnik in-formatsionnykh tekhnologiy, mekhaniki i optiki [Scientific and technical bulletin of information technolo-gies, mechanics and optics], 2017, Vol. 17, No. 6, pp. 1063-1073.
11. Engelbrecht A.P. Fundamentals of Computational Swarm Intelligence. Chichester: John Wiley & Sons, 2005, 114 р.
12. Lebedev B.K., Lebedev O.B., Lebedeva E.O. Roevoy algoritm planirovaniya raboty mnogoprotses-sornykh vychislitel'nykh sistem [Swarm algorithm for scheduling the work of multiprocessor computing systems], Elektronnyy nauchnyy zhurnal «Inzhenernyy vestnik Dona» [Electronic scientific journal «En-gineering Bulletin of the Don»], No. 3, 2017.
13. Lebedev O.B. Modeli adaptivnogo povedeniya murav'inoy kolonii v zadachakh proektirovaniya [Models of adaptive behavior of an ant colony in design problems]. Taganrog. Izd-vo YuFU, 2013, 199 p.
14. Dorigo M.A., Stutzle T.M. Ant colony optimization. Cambridge: MIT Press, 2004, 151 p.
15. Falkenauer E.I. A hybrid grouping genetic algorithm for bin packing, Journal of Heuristics, 1996, Vol. 2, pp. 5-30.
16. Scholl A.D., Klein R.B., Jurgens C.F. BISON: A fast hybrid procedure for exactly solving the one-dimensional bin packing problem, Computers and Operations Research, 1997, pp. 627-645.
17. Martello S.K., Toth P.M. Bin-packing problem, Algorithms and Computer Implementations, 2002,
pp. 221-245.
18. Raidl G.R. A Unified View On Hybrid Metaheuristics, In: Lecture Notes In Computer Science. Spring-er, Verlag, 2006. – P. 1-12.
19. Cong J., Romesis M., Xie M. Optimality, Scalability and Stability Study of Partitioning and Placement Algorithms, Proc. of the International Symposium on Physical Design. Monterey, CA, 2004, pp. 88-94.
20. Lebedev B.K., Lebedev O.B., Ganzhur M.A. Bioinspirirovannyy algoritm raspredeleniya blokov po kon-teyneram [Bioinspired algorithm for distributing blocks among containers], Izvestiya YuFU. Tekhniches-kie nauki [Izvestiya SFedU. Engineering Sciences], 2024, No. 4, pp. 14-30.
