An Analysis of the Effects of Neighborhood Size and Shape on Local Selection Algorithms

. The increasing availability of finely-grained parallel architectures has resulted in a variety of evolutionary algorithms (EAs) in which the population is spatially distributed and local selection algorithms operate in parallel on small, overlapping neighborhoods. The effects of design choices regarding the particular type of local selection algorithm as well as the size and shape of the neighborhood are not particularly well understood and are generally tested empirically. In this paper we extend the techniques used to more formally analyze selection methods for sequential EAs and apply them to local neighborhood models, resulting in a much clearer understanding of the effects of neighborhood size and shape. 1 Introduction Adapting evolutionary algorithms to exploit the power of finely-grained parallel architectures poses a number of interesting design issues. A standard approach is to use spatially structured populations in which local selection algorithms operate in parallel on s..