A Multi Hybrid Genetic Algorithm for the Quadratic Assignment Problem

Quadratic assignment problem (QAP) is one of the hardest combinatorial optimization problems which can model many real life problems. Because of its theoretical and practical importance, QAP has attracted attention of many researchers. In this paper, a multi hybrid genetic algorithm for solving QAP is proposed. The key feature of our approach is the hybridization of three metaheuristics, tabu search, simulated annealing and ant system with genetic algorithm. These metaheuristics are used to create a good initial population and later to improve individuals in future generations. Our proposed approach is applied to a number of standard test problems and our computational results are compared with those of three metaheuristics when applied on the same problems alone. It is understood that our approach is one of best algorithms which deals with QAP.

Keywords:

Quadratic Assignment Problem , Genetic Algorithm , Tabu Search , Simulated Annealing , Ant System