A study of diversification strategies for the quadratic assignment problem

Diversification strategies can be used to enhance general heuristic search procedures such as tabu search, genetic algorithms, and simulated annealing. These strategies are especially relevant to searches that, starting from a particular point, explore a solution path until new exploitable regions are inaccessible, and a new starting point becomes necessary. To date, no one has studied the effect of applying diversification methods independently of other metastrategic components, to identifying their power and limitations. In this paper the authors develop diversification strategies and apply them to the quadratic assignment problem (QAP). They show that these strategies alone succeed in finding high quality solutions to reasonably large QAP instances reported in the literature. The authors also describe how the present diversification strategies can be easily incorporated within general solution frameworks.