Comparing Synchronous and Asynchronous Cellular Genetic Algorithms

This paper presents a comparative study of several asynchronous policies for updating the population in a cellular genetic algorithm (cGA). Cellular GA's are regular GA's with the important exception that individuals are placed in a given geographical distribution (usually a 2-d grid). Operators are applied locally on a set made of each individual and the surrounding neighbors, thus promoting intra-neighborhood exploitation and inter-neighborhood exploration of the search space. Here, we analyze the respective advantages and drawbacks of dealing with this decentralized population in the traditional synchronous manner or in several possible asynchronous update policies. Asynchronous behavior has proven to be better in many domains such as cellular automata and distributed GA's, which, in turn, is also the main conclusion of this work. We will undergo a structured analysis on a set of problems with different features in order to get well grounded conclusions.