[en] This paper investigates dynamic and partially connected ring topologies for cellular Evolutionary Algorithms (cEA). We hypothesize that these structures maintain population diversity at a higher level and reduce the risk of premature convergence to local optima on deceptive, multimodal and NP-hard fitness landscapes. A general framework for modelling partially connected topologies is proposed and three different schemes are tested. The results show that the structures improve the rate of convergence to global optima when compared to cEAs with standard topologies (ring, rectangular and square) on quasi-deceptive, deceptive and NP-hard problems. Optimal population size tests demonstrate that the proposed topologies require smaller populations when compared to traditional cEAs.
Disciplines :
Computer science
Author, co-author :
Fernandes, Carlos; University of Lisbon
JIMENEZ LAREDO, Juan Luis ; University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC)
Merelo, Juan Julian; Universidad de Granada (España) = University of Granada (Spain) - UGR
Cotta, Carlos; University of Malaga
Rosa, Agostinho; University of Lisbon
Language :
English
Title :
Dynamic and Partially Connected Ring Topologies for Evolutionary Algorithms with Structured Populations
Publication date :
2014
Event name :
EvoApplications
Event date :
23-25 April 2014
Main work title :
The European Conference on the Applications of Evolutionary Computation
Alba, E., Dorronsoro, B.: The exploration/exploitation tradeoff in dynamic cellular genetic algorithms. IEEE Transactions Evolutionary Computation 9, 126-142 (2005)
Fernandes, C.M., Laredo, J.L.L., Merelo, J.J., Cotta, C., Rosa, A.C.: Towards a 2-dimensional Framework for Structured Population-based Metaheuristics. In: Proceedings of IEEE International Conference on Complex Systems, pp. 1-6 (2012)
Fernandes, C.M., Laredo, J.L.L., Merelo, J.J., Cotta, C., Rosa, A.C.: A Study on Time-Varying Partially Connected Topologies for the Particle Swarm. In: Proceedings of the IEEE Congress on Evolutionary Computation, pp. 2450-2456. IEEE (2013)
Gordon, V., Whitley, L.: Serial and Parallel Genetic Algorithms as Function Optimizers. In: Proceedings 5th ICGA, pp. 177-183 (1993)
Ilachinski, A.: Cellular Automata: A Discrete Universe. World Scientific (2001)
Kennedy, J., Eberhart, R.C.: Swarm Intelligence. Morgan Kaufmann, San Francisco (2001)
Laredo, J.L.J., Castillo, P.A., Mora, A.M., Merelo, J.J., Fernandes, C.M.: Resilience to churn of a peer-to-peer evolutionary algorithm. International Journal of High Performance Systems Architecture 1(4), 260-268 (2008)
Payne, J.L., Eppstein, M.J.: Emergent mating topologies in spatially structured genetic algorithms. In: Proc. 8th GECCO, pp. 207-214 (2006)
Sastry, K.: Evaluation-relaxation schemes for Genetic and Evolutionary Algorithms. Msc Thesis, University of Illinois, Urbana, IL, USA (2001)
Steinmetz, R., Wehrle, K. (eds.): Peer-to-Peer Systems and Applications. LNCS, vol. 3485. Springer, Heidelberg (2005)
