A STUDY OF DIVERSIFICATION STRATEGIES FOR THE QUADRATIC ASSIGNMENT PROBLEM

Diversification strategies can be used to enhance general heuristic se arch 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 e xploitable regions are inaccessible, and a new starting point becomes necessary. To date, no one has studied the effect of applying diversif ication methods independently of other metastrategic components, to id entify their power and limitations. In this paper we develop diversifi cation strategies and apply them to the quadratic assignment problem ( QAP). We show that these strategies alone succeed in finding high qual ity solutions to reasonably large QAP instances reported in the litera ture. We also describe how our diversification strategies can be easil y incorporated within general solution frameworks.