Diversity and Diversification in Genetic Algorithms: Some Connections with Tabu Search

Genetic Algorithms (GAs) have been used very successfully to solve a variety of optimisation problems, but despite their successes, there are a number of outstanding problems in their implementation. One of the most pervasive problems is that of premature convergence of the process, usually associated with a loss of diversity in the population of chromosomes.In this paper, we will first review some of the existing solutions to the problem of preserving diversity. These all use the basic GA framework; there are also extreme solutions such as the invariant GA which dispenses with the fundamental selection process altogether.We argue that an underlying (and largely unaddressed) problem is the GA’s lack of memory: it is here that some connections with the concept of Tabu Search (TS) may prove fruitful. In TS the search is characterised in terms of the twin concepts of intensification and diversification. Intensification relates to the ability of the search strategy to focus on a particular area (or particular areas) of the search space in order to find improved solutions. In this sense, a GA as customarily conceived is clearly an intensifying process. Diversification is achieved by the incorporation of memory into its basic structures — that is, structures are devised which can record the history of the search.We will describe these mechanisms in more detail, with particular reference in the context of this paper to their diversifying effects. From this standpoint we will then suggest some ways in which these mechanisms can be adapted so as to offer a systematic and coherent framework for diversification within the Genetic Algorithm paradigm.