Locality in genetic algorithms

Author

Gordon, V. Scott

Author_Institution

Dept. of Comput. Sci., Colorado State Univ., Fort Collins, CO, USA

fYear

1994

fDate

27-29 Jun 1994

Firstpage

428

Abstract

Quantifies spatial locality in various genetic algorithms. In particular, the following algorithms are examined: Goldberg´s (1989) standard genetic algorithm (SGA), several “island” models, and two cellular algorithms (fixed topology and random walk). The approaches are also applicable to evolution strategies that employ methods such as recombination or parameter averaging. Two different locality metrics are presented: the percentage of remote references (for parallel machines with a few processors), and the traffic per link (for massively parallel machines). We derive expressions for computing locality in this manner, and discuss the utility, implications and limitations of our results

Keywords

algorithm theory; genetic algorithms; parallel algorithms; parallel machines; telecommunication traffic; cellular algorithms; evolution strategies; fixed topology algorithm; genetic algorithms; island models; locality metrics; massively parallel machines; parameter averaging; random walk algorithm; recombination; remote references percentage; spatial locality; standard genetic algorithm; traffic per link; Algorithm design and analysis; Current measurement; Data structures; Genetic algorithms; Hypercubes; Measurement standards; Parallel machines; Parallel processing; Time measurement; Topology;

fLanguage

English

Publisher

ieee

Conference_Titel

Evolutionary Computation, 1994. IEEE World Congress on Computational Intelligence., Proceedings of the First IEEE Conference on

Conference_Location

Orlando, FL

Print_ISBN

0-7803-1899-4

Type

conf

DOI

10.1109/ICEC.1994.349912

Filename

349912