A Hybrid Genetic Algorithm and Cat Swarm Optimization for Solving the Quadratic Assignment Problem
DOI:
https://doi.org/10.30526/39.3.4417Keywords:
Quadratic Assignment Problem, Genetic Algorithm, Cat Swarm Optimization, Hybrid Metaheuristic, Combinatorial OptimizationAbstract
Since the cost function of the Quadratic Assignment Problem (QAP) is quadratic and its solution space expands linearly, this problem is computationally challenging. In other words, any problem that can be solved by an exact method on one medium- to large-scale instance should be practically intractable in general for the robust hybrid optimization algorithm, combining Genetic Algorithm (GA) with Cat Swarm Optimization (CSO), proposed in this study. It has both the characteristics of being aggressive with respect to exploration but conservative once a promising solution region is identified and introducing localized search operations for improving solution quality: A genetic algorithm is utilized to carry out recombination on the population. As for Cat Swarm Optimization, it adopts a two-way search model with the seeking mechanism and tracing mechanism applied. The new alternative structure, delta evaluation, uses permutational expression for the solutions. It can reduce computational complexity. The proposed algorithm was tested by running 30 independent trials on known QAPLIB benchmark instances, and then its results were analyzed using both Wilcoxon signed-rank tests and Friedman ranks. Experimental results confirm that in several cases, the hybrid GA (GA + CSO) framework provides good or even superior solution quality compared to classical metaheuristic methods. Median optimality gaps dropped and robustness increased. But the question of how to judge the overall performance, let alone prove that it’s not just a fluke (something relying on only a few tests), can only be decided after further study. This improvement—it is statistically confirmed at the 0.05 level—is significant. The proposed model is useful for solving large-scale NP-hard permutation-based combinatorial optimization. For similar problems and future research, it provides a flexible and scalable framework.
References
1. Burkard RE, Karisch SE, Rendl F. QAPLIB: a quadratic assignment problem library. J. Glob. Optim. 1997;10(4):391–403. https://doi.org/10.1023/A:1008293323270
2. Anstreicher KM. Recent advances in the solution of quadratic assignment problems. Math. Program. 2003;97(1):27–42. https://doi.org/10.1007/s10107-003-0437-z
3. Marrouche W. An evolutionary algorithm tailored to the quadratic assignment problem, Evol. Intell. 2025;18(6):112. https://doi.org/10.1007/s12065-025-01100-3.
4. Harris M, Berretta R, Inostroza-Ponta M, Moscato P. A memetic algorithm for the quadratic assignment problem with parallel local search. In: Proc IEEE Congr. Evol. Comput. (CEC); 2015: 838–845. https://doi.org/10.1109/CEC.2015.7256978
5. Bouzidi A, Riffi ME, Barkatou M. Cat swarm optimization for solving the open shop scheduling problem. J. Ind. Eng. Int. 2019;15(2):367–378. https://doi.org/10.1007/s40092-018-0297-z
6. Sattar HA, Cheetar A, Tareq I. A new strategy based on GSABAT to solve single objective optimization problem. Int. J. Swarm Intell. Res. 2019;10(3):1–22. http://dx.doi.org/10.4018/ijsir.2019070101
7. Ahmed AM, Rashid TA, Saeed SA. Dynamic cat swarm optimization algorithm for backboard wiring problem. Neural Comput. Appl. 2021;33(20):13981–13997. https://doi.org/10.1007/s00521-021-06041-3
8. Houssein EH, Saeed MK, Hu G, Al-Sayed MM. Metaheuristics for solving global and engineering optimization problems: review, applications, open issues and challenges. Arch. Comput. Methods Eng. 2024;31(8):4485–4519. https://doi.org/10.1007/s11831-024-10168-6
9. Abdulsattar R, Abbas IT. Tabu search algorithm for solving quadratic assignment problem. AIP Conf. Proc. 2024;3097(1).https://doi.org/10.1063/5.0209862
10. Tan Z , Mu Y . Learning solution-aware transformers for efficiently solving quadratic assignment problem. [preprint]. arXiv. 2024:2406.09899. https://doi.org/10.48550/arXiv.2406.09899.
11. Sohrabi M, Fathollahi-Fard AM, Gromov VA, Dulebenets MA. A genetic engineering algorithm for the generalized quadratic assignment problem. Neural Comput. Appl. 2025;37(18):12253–12279. https://doi.org/10.1007/s00521-025-11155-z
12. Elaibi WM, Rahi AK, Majeed RK, Alhasan AA. A branch-and-bound algorithm for non-integer linear programs with fuzzy right-hand side coefficients. Ind. Eng. Manag. Syst. 2025;24(2):225–233. https://doi.org/10.7232/iems.2025.24.2.225.
13. Anka F, Aghayev N. Advances in sand cat swarm optimization: a comprehensive study. Arch. Comput. Methods Eng. 2025;32: 2669–2712. https://doi.org/10.1007/s11831-024-10217-0
14. Christiansen J, Smith-Miles K. Instance space analysis for the quadratic assignment problem. [preprint]. arXiv. 2025:2506.20172. https://doi.org/10.48550/arXiv.2506.20172.
15. Liu Z, Tang J, Jia H, Huo J, Chen J. Dual-population co-evolution for path planning using neuro-fuzzy systems. Memet. Comput. 2026;18(1):14. https://doi.org/10.1007/s12293-025-00492-0
16. Boudjemline A, Chaudhry IA, Rafique AF, Elbadawi IA, Aichouni M, Boujelbene M. Multi-objective flexible job shop scheduling using genetic algorithms. The. Vjesn. 2022;29(5):1706–1713. https://doi.org/10.17559/tv-20211022164333.
17. Burmeister SC, Guericke D, Schryen G. A memetic NSGA-II for the multi-objective flexible job shop scheduling problem with real-time energy tariffs. Flex. Serv. Manuf. J. 2024;36(4):1530–1570. https://doi.org/10.1007/s10696-023-09517-7
18. Wu R, Luo E, Li X, Tang H, Li Y. Hybrid artificial bee colony algorithm with Q-learning for distributed heterogeneous flexible job shop scheduling problem considering machine preventive maintenance. Swarm Evol. Comput. 2025; 98:102134. https://doi.org/10.1016/j.swevo.2025.102134
19. Karacan I, Senvar O, Bulkan S. A Novel parallel simulated annealing methodology to solve the no-wait flow shop scheduling problem with earliness and tardiness objectives. Processes. 2023;11(2):454. https://doi.org/10.3390/pr11020454
20. Petropoulos F, Akkermans H, Aksin OZ, Ali I, Babai MZ, Barbosa-Povoa A. Operations and supply chain management: principles and practice. Int J Prod Res. 2026;64(1):330–513. https://doi.org/10.1080/00207543.2025.2555531.
21. Alkabbani H, Ahmadian A, Zhu Q, Elkamel A. Machine learning and metaheuristic methods for renewable power forecasting: a recent review. Front. Chem. Eng. 2021;3:665415. https://doi.org/10.3389/fceng.2021.665415
22. Panwar K, Rajwar K, Deep K, Cho SB. A swarm intelligence-based hybrid metaheuristic with tabu search for the quadratic assignment problem. J. Supercomput. 2026;82(3):126. https://doi.org/10.1007/s11227-026-08258-2
23. Danach K, Harb H, Hejase HJ, Saker L. A hybrid metaheuristic framework with reinforcement learning–based heuristic selection for large-scale combinatorial optimization. Eur J Pure Appl. Math 2025;18(3):6602. https://doi.org/10.29020/nybg.ejpam.v18i3.6602
24. Omidvar MN. Cooperative co-evolutionary algorithms for large-scale optimization [dissertation]. Melbourne: RMIT University; 2024. https://doi.org/10.25439/rmt.27580074
25. Wang J, Tan Y, Sun C. An improved NSGA-III algorithm for solving high-dimensional many-objective flexible job shop scheduling problem. In: International Conference on Optimization and Learning. Cham: Springer Nature Switz; 2025:150–163.https://doi.org/10.1007/978-3-032-13589-6_11
Downloads
Published
Issue
Section
License
Copyright (c) 2026 Ibn AL-Haitham Journal For Pure and Applied Sciences
This work is licensed under a Creative Commons Attribution 4.0 International License.
licenseTermsHow to Cite
