TY - GEN

T1 - Landscape mapping by multi-population genetic algorithm

AU - Guo, Yuebin B.

AU - Szeto, Kwok Yip

PY - 2009

Y1 - 2009

N2 - A multi-agent system is divided into groups forming sub-populations of agents. These groups of agents are evolving simultaneously with the aim of searching for all the local extrema of a given function with complex landscape. Mathematically, this multi-agent system is represented by a multi-population genetic algorithm (MPGA). Each population contains a set of agents that are binary coded chromosomes undergoing evolution with mutation and crossover. A migration operator is used to control the exchange of chromosomes between different populations. Since the location of the extrema for the given function f is defined by the condition of vanishing first derivative, we define the fitness of a chromosome as a monotonically decreasing function of the absolute value of the differential df. To evaluate the performance of our multi-agent system in mapping out the landscape, we introduce two measures: the cover degree, which is the percentage of the extrema found, and the precision, which is the average fitness of the last generation among all the groups. A good landscape mapping algorithm will maximize both the cover degree and the precision. Numerical experiments were performed on a set of benchmark functions. We observe a general feature similar to the "uncertainty relation" in physics, in which the cover degree increases and precision decreases as the strength of migration decreases. Our results on benchmark functions show that MPGA provides a good tool for landscape mapping. Application of our method to map out complex landscape of functions that cannot be written down explicitly, such as protein folding, is suggested.

AB - A multi-agent system is divided into groups forming sub-populations of agents. These groups of agents are evolving simultaneously with the aim of searching for all the local extrema of a given function with complex landscape. Mathematically, this multi-agent system is represented by a multi-population genetic algorithm (MPGA). Each population contains a set of agents that are binary coded chromosomes undergoing evolution with mutation and crossover. A migration operator is used to control the exchange of chromosomes between different populations. Since the location of the extrema for the given function f is defined by the condition of vanishing first derivative, we define the fitness of a chromosome as a monotonically decreasing function of the absolute value of the differential df. To evaluate the performance of our multi-agent system in mapping out the landscape, we introduce two measures: the cover degree, which is the percentage of the extrema found, and the precision, which is the average fitness of the last generation among all the groups. A good landscape mapping algorithm will maximize both the cover degree and the precision. Numerical experiments were performed on a set of benchmark functions. We observe a general feature similar to the "uncertainty relation" in physics, in which the cover degree increases and precision decreases as the strength of migration decreases. Our results on benchmark functions show that MPGA provides a good tool for landscape mapping. Application of our method to map out complex landscape of functions that cannot be written down explicitly, such as protein folding, is suggested.

UR - http://www.scopus.com/inward/record.url?scp=70349997687&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=70349997687&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-03211-0_14

DO - 10.1007/978-3-642-03211-0_14

M3 - Conference contribution

AN - SCOPUS:70349997687

SN - 9783642032103

T3 - Studies in Computational Intelligence

SP - 165

EP - 176

BT - Nature Inspired Cooperative Strategies for Optimization (NICSO 2008)

A2 - Natalio, Krasnogor

A2 - Melian Batista, Maria Belen

A2 - Moreno Perez, Jose Andres

A2 - Moreno-Vega, J. Marcos

A2 - Pelta, David Alejandro

ER -