Hybrid Algorithm for Solving the Quadratic Assignment Problem
Abstract
This article is devoted to solving the quadratic assignment problem using a hybrid algorithm contains both genetic and evolutionary algorithms. The quadratic assignment problem is one of the fundamental problems of combinatorial optimization in the field of mathematical optimization, belonging to the category of object placement problem. The article provides a simple statement of this problem and its more detailed mathematical model. Since the quadratic assignment problem is NP-hard and even small input data can take large computational costs for an accurate algorithm, it is reasonable to use a hybrid heuristic approach to solve this problem. The article describes in detail the construction of a hybrid algorithm, the sequence of its steps, and the flowchart. Further, the article provides a graphical interface with the ability to adjust various parameters of the algorithm, allowing it to be optimally configured. The last part of the article covers a comparative analysis of the effectiveness of the resulting algorithm: comparing the accuracy of the developed hybrid algorithm with a new method of invasive weed optimization algorithm, comparing it with the best-known solutions for modern benchmarks. It was found that the hybrid algorithm shows a strong advantage in accuracy over the invasive weed optimization algorithm. Also, the hybrid algorithm was able to find a solution equal to the best known for the tai12a problem. For the tai15a problem, the algorithm showed a deviation of 0.2% from the best-known solution. For the rest of the considered benchmarks, the algorithm showed a deviation from the best solutions of no more than 4.2%, which proves the high efficiency of the created algorithm in comparison with the world's best solutions. In addition, this algorithm has a high economic value due to the wide application of the solution to the problem in practice, for example, in placement of factories or enterprises in places or in placement of associated electronic components on printed circuit boards or integrated circuits, etc.
References
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.)
This work is licensed under a Creative Commons Attribution 4.0 International License.
Publication policy of the journal is based on traditional ethical principles of the Russian scientific periodicals and is built in terms of ethical norms of editors and publishers work stated in Code of Conduct and Best Practice Guidelines for Journal Editors and Code of Conduct for Journal Publishers, developed by the Committee on Publication Ethics (COPE). In the course of publishing editorial board of the journal is led by international rules for copyright protection, statutory regulations of the Russian Federation as well as international standards of publishing.
Authors publishing articles in this journal agree to the following: They retain copyright and grant the journal right of first publication of the work, which is automatically licensed under the Creative Commons Attribution License (CC BY license). Users can use, reuse and build upon the material published in this journal provided that such uses are fully attributed.
