Abstract
This paper attempts to quantify spatial locality in various genetic algorithms. In particular, the following algorithms are examined: SGA (Goldberg's standard genetic algorithm), 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: percentage of remote references (for parallel machines with a few processors), and 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.