A theoretical and empirical study of the trajectories of solutions on the grid of Systolic Genetic Search

Systolic Genetic Search (SGS) is a recently proposed optimization algorithm based on the circulation of solutions through a bidimensional grid of cells and the application of evolutionary operators within the cells to the moving solutions. Until now, the influence of the solutions flow on the results of SGS has only been empirically studied. In this article, we theoretically analyze the trajectories of the solutions along the grid of SGS. This analysis shows that, in the grids used so far, there are cells in which the incoming solutions are descendants of a pair of solutions that have been previously mated. For this reason, we propose a new variant of SGS which uses a grid that guarantees that, given a pair of solutions that coincide in any cell, a pair of ancestors of these two solutions have not been previously mated. The experimental evaluation conducted on three deceptive problems shows that SGS has a better numerical efficiency when it uses grids that limit the mating of descendants of pairs of solutions that have already been mated. It also shows that this property helps to keep a larger diversity in the pairs of solutions that are mated in each cell.