An analysis of decentralized and spatially distributed genetic algorithms
Jayshree Sarma, Kenneth Alan De Jong · 1998
A number of interesting design issues arise when one wants to implement and use decentralized and spatially distributed genetic algorithms (GAs). The implications of these design decisions are not well understood and have only been tested empirically. The objective of this research is to understand and characterize the behavior of the decentralized and spatially distributed GAs with overlapping neighborhoods. To do so the control structure of the GA must be decentralized which alters the semantics of the selection algorithm used. This in turn usually produces changes in the GA's problem solving behavior. First, the implications of the various decentralized selection algorithms are analyzed by studying the changes produced on the characteristics of the selection pressure they induce on the entire population. This analysis shows that the emergent global selection pressure of a particular local selection algorithm is qualitatively similar to its centralized counterpart, but quantitatively weaker. Next, the techniques to formally analyze the selection methods in centralized sequential GAs are extended and applied to the local neighborhood GAs to understand the effects of the neighborhood sizes and shapes. This results in a quantitative model in which the coefficient of the growth rate of the best individual in the population is expressed as a function of the ratio of the neighborhood radius to the grid radius. This quantitative model is used to predict the expected behavior of the spatially distributed GAs. These predictions are empirically validated using the domain of function optimization. These validations help us gain valuable insights into the behavior of these GAs. Furthermore, it is also demonstrated how the selection pressure in a local neighborhood GA can be adjusted based on the analytical model. Finally, the analytical model is used to design effective spatially distributed GAs for solving problems in complex and dynamic environments. The analytical model is also capable of explaining (in some cases conflicting) previously published empirical results. In addition, a developer can now make more effective choices when designing and implementing spatially distributed GAs.