Recentering and restarting a genetic algorithm using a generative representation for an ordered gene problem 1

Abstract

Recentering-Restarting Genetic Algorithms have been used successfully to evolve multiple epidemic networks and perform DNA error correction. This work studies variations of the Recentering-Restarting Genetic Algorithm for the purpose of evaluating its effectiveness for ordered gene problems. These variations use multiple seeds and two adaptive representations which use generating sets to produce local search.

These algorithm variations are applied to what many considered the quintessential ordered gene problem, the Travelling Salesman Problem. Two distinct sets of experimental analysis was performed: first, using large problem instances to determine the effectiveness of the Recentering-Restarting Genetic Algorithm in comparison to benchmarks and second, studying many small problem instances ranging from 12 to 20 cities to determine if any one of the algorithm variations always outperforms the others.

These algorithm variations were comparable to highly competitive optimization algorithms submitted to the DIMACS TSP implementation challenge. In studying the small problem instances, it was observed that no one algorithm always dominates on all problem instances within a domain. This study demonstrates how the Recentering-Restarting Genetic Algorithm is a useful tool for improving upon results generated by other powerful heuristics.