The Multipopulation Genetic Algorithm: Local Selection and Migration

A genetic algorithm with multiple populations (MPGA) is described. Two operators of the algorithm, local selection and the multiple population concept, are discussed in detail.

A new method for fitness assignment by ranking using a non-linear distribution is presented. The use of non-linear ranking permits higher selective pressures than the conventional ranking methods.

The algorithm was implemented in Matlab and is available as part of the Genetic Algorithm Toolbox for Matlab [4].

Keywords:

Genetic Algorithms, Evolutionary Strategies, Parallel Algorithms, Multiple Populations, Non-linear Ranking, Dynamic Optimization, Matlab

Contents

• 1 Introduction
• 2 The Multipopulation Genetic Algorithm
• 2.1 Selection
• 2.2 Recombination
• 2.3 Mutation
• 2.4 Reinsertion
• 3 Non-linear Ranking
• 4 Local Selection
• 5 Multiple Populations
• 6. Concluding Remarks
• 7 References

1 Introduction

Different main schools of evolutionary algorithms evolved during the last 30 years: genetic algorithms, mainly developed in the USA by J. H. Holland [12], evolutionary strategies, developed in Germany by I. Rechenberg [19] and H.-P. Schwefel [21] and evolutionary programming [6]. Each of these constitutes a different approach, however, they are inspired in the same principles of natural evolution. A good introductory survey can be found in [5].

This paper describes the Multipopulation genetic algorithm. In Section 2 a short overview on the structure and basic algorithms of the genetic algorithm is given. Section 3 describes non-linear ranking. In Section 4 the concept of local selection is presented. Section 4 explains the multiple population concept in detail.

[Next]