Selection in Massively Parallel Genetic Algorithms

The availability of massively parallel computers makes it possible to apply genetic algorithms to large populations and very complex applications. Among these applications are studies of natural evolution in the emerging eld of artificial life, which place special demands on the genetic algorithm. In this paper, we characterize the difference between panmictic and local selection/mating schemes in terms of diversity of alleles, diversity of genotypes, the inbreeding coefficient, and the speed and robustness of the genetic algorithm. Based on these metrics, local mating appears to not

only be superior to panmictic for artificial evolutionary simulations, but also for more traditional applications of genetic algorithms. In Proceedings of the Fourth International Conference on Genetic Algorithms. Morgan Kaufmann, 1991. 1 1 Introduction The availability of powerful super computers such as the Connection Machine(Hillis1985) means that genetic algorithms are now applied to larger and more difficult optimization problems (e.g. (Collins and Je erson 1991a), where the search space consists of 2 25590 points). Some of our recent arti cial life work (Je erson et al. 1991; Collins and Je erson 1991b; Collins and Je erson 1991c; Collins and Je erson 1991a) has involved massively parallel genetic algorithms characterized by large populations, enormous search spaces, and tness functions that change through time. These simulated evolution applications place special demands on the genetic algorithm. The simulations generally attempt to model the evolution of populations of tens of thousands of artificial organisms in a simulated environment over a period of thousands of generations. The ecosystem in which the tness of each individual is evaluated can potentially include both direct and indirect interactions with other members of the population, members of coevolving populations, the background environment, etc. In addition, the environment and selection criteria may change both during a generation and over a period of many generations (and may be different in different parts of the simulated world). Such applications require a genetic algorithm that is able to simultaneously explore a wide range of genotypes and can maintain enough genetic diversity to respond to changing conditions. Genetic algorithms that use panmictic selection and mating (where any individual can potentially mate with any other typically convergeon a single peak of multi modal functions, even when several solutions of equalqualityexist(Deb and Goldberg 1989). Genetic convergence is a serious problem when the adaptive landscape is constantly changing as it does in both natural and artificial ecosystems. Crowding, sharing, and restrictive mating are modifications to panmictic selection schemes that have been proposed to deal with the problem of convergence, and thus allow the population to simultaneously contain individuals on more than one peak in the adaptive land- scape (De Jong 1975; Goldberg and Richardson 1987; Deb and Goldberg 1989). These modifications are motivated by the natural phenomena of niches, species, and assortative mating, but they make use of global knowledge of the population, phenotypic distance measures, and global selection and mating, and thus are not well suited for parallel implementation. Rather than attempting to directly implement these natural phenomena, we...

Website: reference.kfupm.edu.sa | Filesize: -
No of Page(s): 15
Download Selection in Massively Parallel Genetic Algorithms - Science ....pdf