Scope and Purpose-Heuristic search procedures that aspire to find global optima usually require some type of diversification strategy in order to overcome their myopic perspective of the solution space. Traditionally, randomization has been used to accomplish this diversification. In this paper, we prt:sent a deterministic approach to diversification that has proved to be much more powerful than silnple randomization. This approach uses the solution method, solution history, and the problem structUJ:e to move the search into unexplored regions of the solution space. We believe that the concepts presented here can form the foundation for effective diversification strategies for many types of optimization problems. Abstract-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 identify their power and limitations. In this paper we develop diversification strategies and apply them to the quadratic assignment problem (QAP). We show that these strategies alone succeed in finding high quality solutions to reasonably large (~AP instances reported in the literature. We also describe how our diversification strategies can be e'isily incorporated within general solution frameworks. Search methods based on local optimization often rely on diversification strategies to increase their effectiveness in exploring the solution space defined by a combinatorial optimization problem. Some of these strategies are designed with the chief purpose of preventing search processes from cycling, i.e., from indefinitely executing the same sequence of moves. Others are introduced to impart additional robustness or vigor to the search. In tabu search (TS), for example, the inclusion of long term memory functions is generally regarded as a way of incorporating diversification. Genetic algorithms use randomization in component processes such as combining population elements and applying crossover (as well as occastional mutation), thus providing some diversifying power. Simulated annealing likewise incorporates randomization to make diversification a function of temperature, whose gradual reduction correspondingly diminishes the directional variation in the objective function trajectory of solutions generated. Diversification in GRASP (Greedy Randomized Adaptive Search Procedures) is achieved by means of controlled random sampling. In these procedures parameters are adjusted to lower the probability that the construction phase generates a solution that has already been used as a starting point, while keeping the set of starting solutions within a desired quality level (in terms of the objective function value).
['James P. Kelly', 'Manuel Laguna', 'Fred Glover']
A study of diversification strategies for the quadratic assignment problem