A Voronoi-based distributed genetic algorithm

Abstract

The use of space for supporting evolution has been previously studied in the context of distributed Genetic Algorithms (DGA), where two standard approaches, island and grid based, are employed to define the population structure and connectivity relationships between individuals. The grid-based approach uses a fixed, regular grid to define the neighbourhood relations between individuals, resulting in Moore or Von Neumann relationships between population individuals. This short paper begins to address the question of the influence of non-fixed spatial relationships between individuals in a distributed genetic algorithm, where the sub-population of each population member is defined by the 1st order Voronoi neighourhood of that individual. Initial results suggest that the irregular nature of the distribution produces an improved performance for the DGA, and that the Voronoi model of neighbours is appropriate for dynamic environments.