Title :
Locality in genetic algorithms
Author :
Gordon, V. Scott
Author_Institution :
Dept. of Comput. Sci., Colorado State Univ., Fort Collins, CO, USA
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;
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
DOI :
10.1109/ICEC.1994.349912
