GENETIC ALGORITHMS AND TABU SEARCH - HYBRIDS FOR OPTIMIZATION

Genetic algorithms and tabu search have a number of significant differ ences. They also have some common bonds, often unrecognized. We explor e the nature of the connections between the methods, and show that a v ariety of opportunities exist for creating hybrid approaches to take a dvantage of their complementary features. Tabu search has pioneered th e systematic exploration of memory functions in search processes, whil e genetic algorithms have pioneered the implementation of methods that exploit the idea of combining solutions. There is also another approa ch, related to both of these, that is frequently overlooked. The proce dure called scatter search, whose origins overlap with those of tabu s earch (and roughly coincide with the emergence of genetic algorithms) also proposes mechanisms for combining solutions, with useful features that offer a bridge between tabu search and genetic algorithms. Recen t generalizations of scatter search concepts, embodied in notions of s tructured combinations and path relinking, have produced effective str ategies that provide a further basis for integrating GA and TS approac hes. A prominent TS component called strategic oscillation is suscepti ble to exploitation by GA processes as a means of creating useful degr ees of diversity and of allowing effective transitions between feasibl e and infeasible regions. The independent success of genetic algorithm s and tabu search in a variety of applications suggests that each has features that are valuable for solving complex problems. The thesis of this paper is that the study of methods that may be created from thei r union can provide useful benefits in diverse settings.