Гибридный алгоритм решения квадратичной задачи о назначениях
Аннотация
Данная работа посвящена решению квадратичной задачи о назначениях с помощью гибридного алгоритма, который использует принципы генетического и эволюционного алгоритмов. Квадратичная задача о назначениях – одна из фундаментальных задач комбинаторной оптимизации в области математической оптимизации, принадлежащая к категории задач размещения объектов. В статье приводится простая постановка данной задачи и её более подробная математическая модель. Так как квадратичная задача о назначениях является NP-трудной и даже небольшие входные данные могут потребовать больших вычислительных затрат для точного алгоритма, разумно применить гибридный эвристический подход в решении данной проблемы. В статье подробно освещено построение гибридного алгоритма, последовательность его шагов, блок-схема. Далее в статье приводятся графический интерфейс с возможностью регулировки различных параметров алгоритма, позволяющий оптимально их настроить. В последней части статьи освещается сравнительный анализ эффективности работы полученного алгоритма: сравнение точности разработанного гибридного алгоритма с новым методом оптимизации сорной травой, сравнение с лучшими известными решениями для современных бенчмарков. Удалось установить, что гибридный алгоритм показывает уверенное преимущество в точности над алгоритмом сорной травы. Также гибридный алгоритм смог найти решение равное лучшему известному для задачи tai12a. Для задачи tai15a алгоритм показал отклонение 0,2% от лучшего известного решения. Для остальных рассматриваемых бенчмарков алгоритм показал отклонение от лучших решений не более чем 4,2%, что доказывает высокую эффективность созданного алгоритма в сравнение с лучшими мировыми решениями. Кроме того, данный алгоритм имеет высокую экономическую ценность ввиду широкого применения решения рассматриваемой задачи на практике, например в размещении фабрик или предприятий по местам, размещении связанных электронных компонентов на печатных платах или в интегральных схемах и т.д.
Литература
2. Nigodin E.A., Polupanova Е.Е., Polyakov А.S. Geneticheskij algoritm reshenija zadachi o naznachenijah [Genetic algorithm for solving the assignment problem]. Proceedings of the International Conference on Applied Mathematics of the XXI Century: Modern Problems of Mathematics, Computer Science and Modeling. Issue 1, part 4. Krasnodar; 2019. p. 246-252. Available at: https://www.elibrary.ru/item.asp?id=38189427 (accessed 11.04.2021). (In Russ.)
3. Karpenko A.P. Sovremennye algoritmy poiskovoj optimizacii. Algoritmy, vdohnovlennye prirodoj [Modern search optimization algorithms. Nature-inspired algorithms]. BMSTU, Moscow; 2014. 448 p. (In Russ.)
4. Garey M.R., Johnson D.S. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., USA; 1979. 338 p. (In Eng.)
5. Omidbakhsh M., Seifbarghy M. Solving Quadratic Assignment Problem (QAP) Using Invasive Weed Optimization Algorithm. Journal of Industrial Engineering. 2011; 45(626033):113-125. Available at: https://aie.ut.ac.ir/article_23331.html (accessed 11.04.2021). (In Eng.)
6. Črepinšek M., Liu S.-H., Mernik M. Replication and comparison of computational experiments in applied evolutionary computing: Common pitfalls and guidelines to avoid them. Applied Soft Computing. 2014; 19:161-170. (In Eng.) DOI: https://doi.org/10.1016/j.asoc.2014.02.009
7. Eiben A.E., Smith J.E. Introduction to Evolutionary Computing. Natural Computing Series. Springer, Berlin, Heidelberg; 2003. 300 p. (In Eng.) DOI: https://doi.org/10.1007/978-3-662-05094-1
8. Nguyen T.T., Xin Yao. Benchmarking and solving dynamic constrained problems. 2009 IEEE Congress on Evolutionary Computation. IEEE Press, Trondheim, Norway; 2009. p. 690-697. (In Eng.) DOI: https://doi.org/10.1109/CEC.2009.4983012
9. Schütze O., et al. EVOLVE – A Bridge between Probability, Set Oriented Numerics, and Evolutionary Computation II. In: Ed. by O. Schütze et al. Advances in Intelligent Systems and Computing, vol. 175. Springer, Berlin, Heidelberg; 2013. 508 p. (In Eng.) DOI: https://doi.org/10.1007/978-3-642-31519-0
10. Villela Tinoco J.C., Coello Coello C.A. hypDE: A Hyper-Heuristic Based on Differential Evolution for Solving Constrained Optimization Problems. In: Ed. by O. Schütze, et al. EVOLVE – A Bridge between Probability, Set Oriented Numerics, and Evolutionary Computation II. Advances in Intelligent Systems and Computing, vol. 175. Springer, Berlin, Heidelberg; 2013. p. 267-282. (In Eng.) DOI: https://doi.org/10.1007/978-3-642-31519-0_17
11. Simon D. Evolutionary Optimization Algorithms. John Wiley & Sons, Inc.; 2013. 784 p. (In Eng.)
12. Kureychik V.V., Bova V.V., Kureychik V.V. Bioinspired algorithm for design and optimization problems. In: Ed. by E. L. Gloriozov. Proceedings of the International Conference on Information technologies in science, education and management. Gurzuf; 2015. p. 427-432. Available at: https://www.elibrary.ru/item.asp?id=23519161 (accessed 11.04.2021). (In Russ., abstract in Eng.)
13. Kureychik V.V., Kureychik L.V. Summary of some hybrid approach to solving combinatorically logical tasks on graphs. Proceedings of the International Scientific and Technical Congress on Intelligent Systems and Information Technologies ‒ 2020 (IS&IT-2020). Publ. house of Stupin S.A., Divnomorskoye; 2020. p. 102-108. Available at: https://www.elibrary.ru/item.asp?id=45435484&pff=1 (accessed 11.04.2021). (In Russ., abstract in Eng.)
14. Kureychik V.V., Kursitys I.O., Kuliev E.V., Gerasimenko E.M. Application of bioinspired algorithms for solving transcomputational tasks. Journal of Physics: Conference Series. 2020; 1703:012021. (In Eng.) DOI: https://doi.org/10.1088/1742-6596/1703/1/012021
15. Kureychik V., Zaruba D., Kureychik V. Hybrid Approach for Graph Partitioning. In: Ed. by R. Silhavy et al. Artificial Intelligence Trends in Intelligent Systems. CSOC 2017. Advances in Intelligent Systems and Computing. 2017; 573:64-73. Springer, Cham. (In Eng.) DOI: https://doi.org/10.1007/978-3-319-57261-1_7
16. Achary T., et al. A performance study of meta-heuristic approaches for quadratic assignment problem. Concurrency and Computation: Practice and Experience. 2021; 33(17):e6321. (In Eng.) DOI: https://doi.org/10.1002/cpe.6321
17. Silva A., Coelho L.C., Darvish M. Quadratic assignment problem variants: A survey and an effective parallel memetic iterated tabu search. European Journal of Operational Research. 2021; 292(3):1066-1084. (In Eng.) DOI: https://doi.org/10.1016/j.ejor.2020.11.035
18. Wu X.B., Lu J., Wu S., Zhou X.S. Synchronizing time-dependent transportation services: Reformulation and solution algorithm using quadratic assignment problem. Transportation Research Part B: Methodological. 2021; 152:140-179. (In Eng.) DOI: https://doi.org/10.1016/j.trb.2021.08.008
19. Alza J., Bartlett M., Ceberio J., McCall J. Towards the landscape rotation as a perturbation strategy on the quadratic assignment problem. Proceedings of the Genetic and Evolutionary Computation Conference Companion. Association for Computing Machinery, New York, NY, USA; 2021. p. 1405-1413. (In Eng.) DOI: https://doi.org/10.1145/3449726.3463139
20. Benavides X., Ceberio J., Hernando L. On the symmetry of the quadratic assignment problem through elementary landscape decomposition. Proceedings of the Genetic and Evolutionary Computation Conference Companion. Association for Computing Machinery, New York, NY, USA; 2021. p. 1414-1422. (In Eng.) DOI: https://doi.org/10.1145/3449726.3463191
21. Gunawan A., Ng K.M., Poh K.L., Lau H.C. Hybrid metaheuristics for solving the quadratic assignment problem and the generalized quadratic assignment problem. 2014 IEEE International Conference on Automation Science and Engineering (CASE). IEEE Press, New Taipei, Taiwan; 2014. p. 119-124. (In Eng.) DOI: https://doi.org/10.1109/CoASE.2014.6899314
22. Benjaafar S. Modeling and Analysis of Congestion in the Design of Facility Layouts. Management Science. 2002; 48(5):679-704. (In Eng.) DOI: https://doi.org/10.1287/mnsc.48.5.679.7800
23. Misevičius A. An improved hybrid optimization algorithm for the quadratic assignment problem. Mathematical Modelling and Analysis. 2004; 9(2):149-168. (In Eng.) DOI: https://doi.org/10.3846/13926292.2004.9637249
24. Lim M.H., Yuan Y., Omatu S. Extensive Testing of a Hybrid Genetic Algorithm for Solving Quadratic Assignment Problems. Computational Optimization and Applications. 2002; 23:47-64. (In Eng.) DOI: https://doi.org/10.1023/A:1019972523847
25. Drezner Z. Heuristic Algorithms for the Solution of the Quadratic Assignment Problem. Journal of Applied Mathematics and Decision Sciences. 2002; 6:163-173. (In Eng.)
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Редакционная политика журнала основывается на традиционных этических принципах российской научной периодики и строится с учетом этических норм работы редакторов и издателей, закрепленных в Кодексе поведения и руководящих принципах наилучшей практики для редактора журнала (Code of Conduct and Best Practice Guidelines for Journal Editors) и Кодексе поведения для издателя журнала (Code of Conduct for Journal Publishers), разработанных Комитетом по публикационной этике - Committee on Publication Ethics (COPE). В процессе издательской деятельности редколлегия журнала руководствуется международными правилами охраны авторского права, нормами действующего законодательства РФ, международными издательскими стандартами и обязательной ссылке на первоисточник.
Журнал позволяет авторам сохранять авторское право без ограничений. Журнал позволяет авторам сохранить права на публикацию без ограничений.
Издательская политика в области авторского права и архивирования определяются «зеленым цветом» в базе данных SHERPA/RoMEO.
Все статьи распространяются на условиях лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная, которая позволяет другим использовать, распространять, дополнять эту работу с обязательной ссылкой на оригинальную работу и публикацию в этом журналe.
