Comparing genetic algorithm and guided local search methods by symmetric TSP instances
Mehrdad Nojoumian, Divya K. Nair · 2008
This paper aims at comparing Genetic Algorithm (GA) and Guided Local Search (GLS) methods so as to scrutinize their behaviors. Authors apply the GLS program with the Fast Local Search (FLS), developed at University of Essex, and implement a genetic algorithm with partially-mapped and order crossovers, reciprocal and inversion mutations, and rank and tournament selections in order to experiment with various Travelling Salesman Problems. The paper then ends up with two prominent conclusions regarding the performance of these meta-heuristic techniques over wide range of symmetric-TSP instances. First, the GLS-FLS strategy on the s-TSP instances yields the most promising performance in terms of the near-optimality and the mean CPU time. Second, the GA results are comparable to GLS-FLS outcomes on the same s-TSP instances. In the other word, the GA is able to generate near optimal solutions with some compromise in the CPU time.