Markov chain models of parallel genetic algorithms

Implementations of parallel genetic algorithms (GA) with multiple populations are common, but they introduce several parameters whose effect on the quality of the search is not well understood. Parameters such as the number of populations, their size, the topology of communications, and the migratio...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on evolutionary computation 2000-09, Vol.4 (3), p.216-226
Main Author: Cantu-Paz, E.
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Computer science
Contracts
Exact sciences and technology
General topology
Genetic algorithms
Guidelines
Mathematical analysis
Mathematical methods in physics
Mathematical models
Mathematics
Migration
Numerical approximation and analysis
Numerical optimization
Operational research and scientific management
Operational research. Management science
Optimization. Search problems
Physics
Populations
Predictive models
Probability
Sciences and techniques of general use
Scientific computing
Searching
Stochastic processes
Studies
Time measurement
Topology
Topology. Manifolds and cell complexes. Global analysis and analysis on manifolds
Citations: Items that this one cites
Items that cite this one
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Implementations of parallel genetic algorithms (GA) with multiple populations are common, but they introduce several parameters whose effect on the quality of the search is not well understood. Parameters such as the number of populations, their size, the topology of communications, and the migration rate have to be set carefully to reach adequate solutions. This paper presents models that predict the effects of the parallel GA parameters on its search quality. The paper reviews some recent results on the case where each population is connected to all the others and the migration rate is set to the maximum value possible. This bounding case is the simplest to analyze, and it introduces the methodology that is used in the remainder of the paper to analyze parallel GA with arbitrary migration rates and communication topologies. This investigation considers that migration occurs only after each population converges; then, incoming individuals are incorporated into the populations and the algorithm restarts. The models find the probability that each population converges to the correct solution after each restart, and also calculate the long-run chance of success. The accuracy of the models is verified with experiments using one additively decomposable function.
ISSN:1089-778X
1941-0026
DOI:10.1109/4235.873233