A Hybrid Genetic Algorithm and Cat Swarm Optimization for Solving the Quadratic Assignment Problem
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.