Comparing synchronous and asynchronous cellular genetic algorithms

Abstract. This paper presents a comparative study of several asyn-chronous policies for updating the population in a cellular genetic al-gorithm (cGA). Cellular GA's are regular GA's with the important ex-ception 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 draw-backs 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 di®erent features in order to get well grounded conclusions.