next up previous contents
Next: 2 Genetic Programming Distributed Up: 1 Previous Distributed Evolution Previous: 1 Previous Distributed Evolution   Contents

1 Evolutionary and Genetic Algorithm Models

The most common form of island model uses fitness-based probabilistic selection for migration selection and replacement. Breeding and evaluation are typically carried out in isolation on each island. Pettey (1987) designed a distributed model based on the polytypic concept of a species being represented by several types that are capable of mating and producing viable offspring. Every generation, migration sent the best individuals in each population to each neighbour, replacing the worst individuals. Tanese (1987,1989) presented a parallel genetic algorithm implemented on a hypercube structure. Migration occurred periodically, where migrants where selected according to fitness and replaced individuals selected based on fitness in the receiving population. Belding (1995) extended the work of Tanese (1989) where migrants were selected by choosing the first $n$ individuals in the local population according to a predefined ordering, effectively simulating a more random migrant selection strategy.

Whitley et al. (1997) investigated whether the island model has a natural advantage for finding solutions to linearly separable problems. The authors concluded that for problems where an increase in the population size does not yield better results, island models may better search more of the solution space. Also, Whitley et al. noted that migration can be an ``additional selective pressure", which could make the island model ideal when adding this pressure is beneficial to the problem. Cantú-Paz (1999) used the building block schema theory to develop equations to predict deme sizes and topologies for the parallel island model in genetic algorithms. The author concluded that the specific communication topology is probably irrelevant given the degree of connectivity of the topology.

The concept of random migrant selection and replacement was introduced in the first island model for evolutionary algorithms by Cohoon et al. (1987). This island model was based on isolated populations in different geographical locations. Populations had different environments by defining fitness relative to the population and individuals migrated according to a mesh and hyper-cube topology. To be consistent with the biological motivations, it was noted that migration should occur after a period of stasis. However, due to the difficulty of defining stasis or equilibrium, migration occurred after $G$ generations, or an epoch. Unique to this model is that migrant selection is not done probabilistically but randomly to simulate a ``catastrophe", or random environmental change.

Martin, Lienig and Cohoon (2000) described the results of using the island model on a VLSI design problem. They showed that a variable length epoch was slightly better than a fixed length. To implement a variable epoch length, the authors defined the end of the current epoch to be the point when no improvement to the most fit individual occurred for 25 generations. Results also showed that a random migration selection was more effective and that an aggressive selection strategy caused the population to get stuck in a local optima.

The idea that islands should consist of different environments was also seen in later work, often for coevolution. Potter and De Jong (1994) introduced a method for using isolated populations, or species, in a genetic algorithm for cooperation where the species are not ``user-defined". The authors concluded that their algorithm works well on problems with independent variables. Potter and De Jong (2000) later presented an architecture to adaptively co-evolve components in a speciation model. Subpopulations represented separate species, which were required to contribute to the overall fitness to survive. Periods of stagnation suggested an insufficient number of species, resulting in the addition of new subpopulations. Species were tested in the cooperative problem domain and were removed if they failed to contribute sufficiently.

Lin, Punch and Goodman (1994) presented a hybrid of the island model called the injection island genetic algorithm. The injection architecture divided the search space into hierarchical levels. Populations that were trained on more general tasks were injected into populations with more specific tasks. Hu and Goodman (2002) described the hierarchical fair competition model, which defined hierarchical levels with fitness value boundaries. Individuals undergo selection and recombination within these levels and move between them based on their fitness. Higher fitness levels undergo higher selection pressure to simulate added exploitation.

In Pei and Goodman (2001) the cohort algorithm [Holland, 2000] is compared with island genetic algorithms. The cohort genetic algorithm was designed to combat premature convergence, in the form of ``hitchhiking'' by allowing higher fit individuals to reproduce first. Offspring are assigned to cohorts based on their fitness. Adamidis and Petridis (1996) used an island model configuration for recurrent neural network training that varied control parameters in each sub population.

Another form of island models uses the concept of demes. These models are often implemented on grid-like topologies (stepping stone or hypercubes, for instance), where a deme is defined by the size of the neighborhood. Collins (1992) used a form of local breeding, the stepping-stone model, where individuals are placed on a grid, one per node, and can interact with neighbors in a given range. Several metrics measured the difference between breeding: allele diversity, genotype diversity, a panmictic index, and speed and robustness. Results indicated that, for the Partition problem, local mating was superior to panmictic breeding in finding both optimal solutions, maintaining allele and genotype diversity, faster optimisation, and robustness in the proportion of runs that produced an optimal solution.

Several other models have been proposed for various types of problems such as multiobjective optimisation [Zhu and Leung, 2002], multimodal optimisation [Bessaou et al., 2000] and agent-based evolutionary algorithms [Smith and Bonacina, 2003]. As seen in the previous examples, island and distributed models are typically based on the goal of preserving diversity to prevent premature convergence or to allow the isolated evolution of different structures or behaviours. However, the effects of various forms of migration, selection and replacement are not always clear.

next up previous contents
Next: 2 Genetic Programming Distributed Up: 1 Previous Distributed Evolution Previous: 1 Previous Distributed Evolution   Contents
S Gustafson 2004-05-20