Article
Journal/Revue :
Soft Computing
ISSN : 1432-7643
Publisher :
Informations
Période : June 2020
Volume : 24 Numéro : 5
Pages : 3569-3589
Détails
The grid-to-neighbourhood relationship in cellular GAs: from design to solving complex problems
Zakaria Abdelmoiz Dahi Enrique Alba
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.
Réf. de citation :
misc-lab-333
DOI :
10.1007/s00500-019-04125-w
Lien :
Texte intégral
ACM :
Z. A. Dahi and E. Alba. 2020. The grid-to-neighbourhood relationship in cellular GAs: from design to solving complex problems. Soft Computing, 24, 5 (June 2020), Springer, 3569-3589. DOI: https://doi.org/10.1007/s00500-019-04125-w.
APA :
Dahi, Z. A. & Alba, E. (2020, June). The grid-to-neighbourhood relationship in cellular GAs: from design to solving complex problems. Soft Computing, 24(5), Springer, 3569-3589. DOI: https://doi.org/10.1007/s00500-019-04125-w
IEEE :
Z. A. Dahi and E. Alba, "The grid-to-neighbourhood relationship in cellular GAs: from design to solving complex problems". Soft Computing, vol. 24, no. 5, Springer, pp. 3569-3589, June, 2020. DOI: https://doi.org/10.1007/s00500-019-04125-w.
BibTeX :
@article{misc-lab-333,
author = {Dahi, Zakaria Abdelmoiz and Alba, Enrique},
title = {The grid-to-neighbourhood relationship in cellular GAs: from design to solving complex problems},
journal = {Soft Computing},
volume = {24},
number = {5},
issn = {1432-7643},
pages = {3569--3589},
publisher = {Springer},
year = {2020},
month = {June},
doi = {10.1007/s00500-019-04125-w},
url = {https://doi.org/10.1007/s00500-019-04125-w}
}
RIS :
TI  - The grid-to-neighbourhood relationship in cellular GAs: from design to solving complex problems
AU - Z. A. Dahi
AU - E. Alba
PY - 2020
SN - 1432-7643
JO - Soft Computing
VL - 24
IS - 5
SP - 3569
EP - 3589
PB - Springer
AB - 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.
DO - 10.1007/s00500-019-04125-w
UR - https://doi.org/10.1007/s00500-019-04125-w
ID - misc-lab-333
ER -