[Previous] [Top] [Next]

2 The Multipopulation Genetic Algorithm

Genetic algorithms differ from gradient search methods mainly in the manner in which variables are changed. Whereas gradient methods change the variables according to deterministic rules, genetic algorithms are based on random transition rules.

Genetic algorithms model natural processes, such as selection, recombination, mutation, migration, locality and neighbourhood. Figure 1 shows the structure of a simple genetic algorithm. Genetic algorithms work on populations of individuals instead of single solutions. In this way the search is performed in a parallel manner.

Fig 1: Structure of a single population genetic algorithm

At the beginning of the computation a number of individuals (the population) are randomly initialised. The objective function is then evaluated for these individuals. The first/initial generation is produced.

If the optimization criteria are not met the creation of a new generation starts. Individuals are selected according to their fitness for the production of offspring. Parents are recombined to produce offspring. All offspring will be mutated with a certain probability. The fitness of the offspring is then computed. The offspring are inserted into the population replacing the parents, producing a new generation. This cycle is performed until the optimization criteria are reached.

Such a single population genetic algorithm is powerful and performs well on a broad class of problems. However, better results can be obtained by introducing many populations, called subpopulations. Every subpopulation evolves for a few generations isolated (like the single population genetic algorithm) before one or more individuals are exchanged between the subpopulations. The Multipopulation genetic algorithm models the evolution of a species in a way more similar to nature than the single population genetic algorithm.

2.1 Selection

Selection determines, which individuals are chosen for mating (recombination) and how many offspring each selected individual produces. The first step is fitness assignment by:

Rank-based fitness assignment behaves in a more robust manner than proportional fitness assignment and, thus, is the method of choice.

The actual selection is performed in the next step. Parents are selected according to their fitness by means of one of the following algorithms:

2.2 Recombination

Recombination produces new individuals in combining the information contained in the parents (parents - mating population). The Multipopulation genetic algorithm can use one of the following algorithms:

2.3 Mutation

After recombination every offspring undergoes mutation. Offspring variables are mutated by small perturbations (size of the mutation step), with low probability. The Multipopulation genetic algorithm uses the mutation operator of the breeder genetic algorithm [14].

2.4 Reinsertion

If less offspring are produced than the size of the original population the offspring have to be reinserted into the old population. Similarly, if not all offspring are to be used at each generation or if more offspring are generated than needed a reinsertion scheme must be used to determine which individuals should be inserted into the new population.

Different schemes of reinsertion exist:

The Multipopulation genetic algorithm can perform all these reinsertion schemes. However, elitist reinsertion is recommended.

[Previous] [Top] [Next]