Particle swarm optimization hybrids for the quadratic assignment problem - Gamot, Ritchie Mae T. (2005)
The Quadratic Assignment Problem (QAPs) is an NP-Hard combinatorial problem concerned with the problem of assigning n facilities to n locations. Heuristic algorithms has to be applied to solve QAP in a reasonable period of time without compromising the quality of the solutions produced. QAP also falls under the discrete case problems category where solutions take the form of permutations. Particle Swarm Optimization (PSO) is a relatively new heuristic algorithm mostly oriented and designed for continuous spaces. Modifications have to be made to the original implementation to be able to adapt to discrete cases. In this work, two PSO hybrids namely: PSO-Simulated Annealing (PSO-SA) and PSO-Tabu Search (PSO-TS), were developed to solve the QAP for nine problem instances of size 12, 18, and 19. An effective way in dealing with the permutation set was introduced to satisfy the requirement of the solution. Comparisons of the performances between pure breed PSO versus some of its local-search heuristic hybrids showed that the PSO Hybrids arrived at the known optical solutions, which the pure breed PSO did not. The results also show that PSO-SA could find the optimal solution significantly faster. Results showed that the PSO hybrids needed smaller population sizes as compared to their pure counterpart in finding the best solution quality. Contrary to previous results, fixed inertia weights performed better as compared to a time variant inertia weight. Cognitive and social experiences were given equal influences and results showed that smaller values perform better. The arrival of the PSO hybrids results at the known optimal solutions, together with an effective discrete conversion of the solutions, showed that it is a promising method for solving QAP.