Effect of topology on diversity of spatially-structured evolutionary algorithms

Abstract

The aim of this work is an investigation on the effects of networks topology to spatially-structured evolutionary algorithms’ dynamics. We applied the algorithm on a multi-modal optimization problem and we focused our study on convergence time and diversity of the solutions. Using as algorithms’ underlying structure different network models we studied the relationship between algorithm dynamic, i.e. convergence time, first hitting time and number of distinct optima found during the evolution, and networks’ characteristics. A comparison with a panmictic evolutionary algorithm is made to study the effects of the introduction of a structure in the mating dynamics, resulting in an enhancement of diversity and containing the convergence time and first hitting time overhead. The results on the proposed multi-modal combinatorial optimization problem using regular graphs and Watts-Strogatz networks show that the underlying network characteristics clearly influences algorithm dynamics and diversity of the solutions found.

Publication
Proceedings of the 13th annual conference on Genetic and evolutionary computation, pp. 1579–1586, https://doi.org/http://doi.acm.org/10.1145/2001576.2001789
Date
Links