A heuristic algorithm for the quadratic assignment problem

In this paper we describe a new evolutionary algorithm for the Quadratic Assignment Problem. This method can be divided into three stages: a preparatory and two local search stages. The first stage improves the quality of the initial population. The second stage improves the quality of the solutions with a local search procedure while periodically generating new solutions. In the third stage the algorithm continues the application of the local search procedure and replaces the weakest solutions with new ones. We tested our algorithm on all the benchmark problems of QAPLIB. The algorithm managed to find solutions which are either best known or within 1% of the best known solutions for 98% of all tasks.