The Multipopulation Genetic Algorithm: Local Selection and Migration

Hartmut Pohlheim
Systems Technology Research, Daimler Benz AG
Alt-Moabit 96a, D-10559 Berlin,

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].

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


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.