The grid-to-neighbourhood relationship in cellular GAs: from design to solving complex problems

Cellular genetic algorithms (cGAs) are a class of evolutionary algorithms in which the population is structured as a grid and interactions between individuals are restricted to the neighbourhood. Like any other optimisation algorithm, the cGA’s efficiency lies in its ability to find an adequate balance between its exploratory and exploitive capabilities. The search selection pressure represents a good indicator of the state of that balance. From that point of view, it has been shown that the cGA’s grid-to-neighbourhood relationship can be used to reflect this property. Until today, not much has been done in that area of research and many questions still surround this grid-to-neighbourhood effect. This paper describes a systematic study on the effects of that ratio on the efficiency of the cGA. This is done by proposing a dynamic cGA that adapts its ratio through evolving its grid structure using some strategy. The study is conducted using a wide range of dynamic and static ratio-control policies and, for the first time, by considering both synchronous and asynchronous cGAs. As a validation problem, we have opted for a real-world complex problem in advanced cellular networks: the users’ mobility management. A wide set of differently sized and realistic instances of this problem have been used, and several comparisons have been conducted against other top-ranked solvers. The experiments showed that the ratio strategy rules the cGA’s convergence, efficiency and scalability. Its effectiveness is correlated with the ratio-adaptation policy and the replacement synchronism being used. Indeed, our proposals that are based on deterministic and dynamic strategies with an asynchronous replacement were able to outperform most of the state-of-the-art algorithms.