A Rule Based Evolutionary Optimization Approach for the Traveling Salesman Problem
Open Access
- 1 January 2017
- journal article
- Published by Scientific Research Publishing, Inc. in Intelligent Information Management
- Vol. 09 (04), 115-132
- https://doi.org/10.4236/iim.2017.94006
Abstract
The traveling salesman problem has long been regarded as a challenging application for existing optimization methods as well as a benchmark application for the development of new optimization methods. As with many existing algorithms, a traditional genetic algorithm will have limited success with this problem class, particularly as the problem size increases. A rule based genetic algorithm is proposed and demonstrated on sets of traveling salesman problems of increasing size. The solution character as well as the solution efficiency is compared against a simulated annealing technique as well as a standard genetic algorithm. The rule based genetic algorithm is shown to provide superior performance for all problem sizes considered. Furthermore, a post optimal analysis provides insight into which rules were successfully applied during the solution process which allows for rule modification to further enhance performance.Keywords
This publication has 1 reference indexed in Scilit:
- Large-step markov chains for the TSP incorporating local search heuristicsOperations Research Letters, 1992