Genetic algorithm with punctuated equilibria analysis of the travelling salesperson problem instance /

by Ignat, Daniel B.

The relatively new field of Genetic Algorithms with Punctuated Equilibria (GAPE) has yet to completely prove itself to the computing community. Due to the length of the running times of the existing software implementations of GAPE, quite a bit of analysis remains to be done in order to assess the value of its contributions to the field of heuristic search. This project attempted to probe further into the analysis of GAPE on the Travelling Salesperson Problem (TSP) by taking an existing sequential GAPE implementation and converting it into a parallel version to be run on a Legion distributed network. This would allow extended experimentation which would not be possible with a sequential implementation due to the computing resources it would require of one machine. The results of our experimentation revealed that a variable number of populations has little effect on GAPE’s performance, at least for the Eilon-Christofides 51-city TSP. However, experimenting with a variable number of epochs revealed that instances with many, small epochs tend to find better solutions more quickly at first, while instances with a few, large epochs tend to be slower at the onset but also tend to find better solutions overall. Furthermore, we experienced a speedup of about two as compared to the previous sequential version during the evolution phase, but we also experienced very significant communication costs during the migration phase, which had the effect of offsetting the aforementioned speedup. This technical report presents the background, methodology, hypotheses, results, and conclusions of this research project, in the hope that future study along these lines will benefit from its existence. viii