Multi-Population Genetic Algorithm for Locating Multi-Optima in Noisy Complex Landscape

Abstract

A multi-population genetic algorithm (MPGA) is introduced to search for as many as possible of the local optima of a complex function in a noisy environment. By considering a multi-agent system consisting of sub-populations of agents that evolve simultaneously as a group of chromosomes in a genetic algorithm, we perform a spatial allocation of resources by the partitioning of the search space into many subspaces. A migration operator is used to control the exchange of chromosomes between different sub-populations. This spatial allocation of computational resources has the advantage of exhaustive search which avoids duplicate effort, and combines it with the parallel nature of the search for the solution in disjoint subspaces by genetic algorithms. The division of the solution space is performed intelligently using loci statistics of the chromosomes in past generations. The benchmark function used is a 2-D function with the x-y coordinates represented by a binary coded chromosome. Unlike traditional GAs, the exact differential df is used as the fitness for the chromosomes. For noisy environment, the derivatives used in calculating exact differentials are obtained through second order polynomial fitting. Two measurements are employed to evaluate the performance of this algorithm: precision (Pr), which is the average fitness of all the local optima at the end of the evolution, and cover degree (CD), which is the percentage of the local optima obtained at the end of evolution, among the total number of optima. The variance of the noise affects both CD and Pr, while the quality of the local optima decreases with increasing noise, the degree of coverage (CD) is rather insensitive to noise. The effects of the parameters of MPGA on performance are discussed, and applications to the mapping of complex landscape suggested.

Keywords:

• Landscape mapping
• Multi-agent system
• Parallel genetic algorithm
• Population dynamics

Mathematics Subject Classification:

• 65C50
• 68Wxx

Acknowledgment

K. Y. Szeto acknowledges the support of CERG grant 602507.