A Rule Based Evolutionary Optimization Approach for the Traveling Salesman Problem
- 1 Systems Engineering Department, Donaghey College of Engineering & Information Technology, University of Arkansas at Little Rock, Little Rock, AR, USA
- 2 Axalta Coating Systems, Front Royal, VA, USA
- 3 Systems Engineering Department, Donaghey College of Engineering & Information Technology, University of Arkansas at Little Rock, Little Rock, AR, USA
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.
- Dantzig, G.B., Fulkerson, D.R. and Johnson, S.M. (1954) Solution of a Large-Scale Traveling Salesman Problem. Operations Research, 2, 393. https://doi.org/10.1287/opre.2.4.393
- Balas, E. and Toth, P. (1985) Branch and Bound Methods. In: Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G. and Shmoys, D.B., Eds., The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, John Wiley & Sons, New York, 80-147.
- Lo, C.C. and Hus, C.C. (1998) Annealing Framework with Learning Memory. IEEE Transactions on System, Man, Cybernetics, Part A: Systems and Humans, 28, 1-13.
- Pepper, J.W., Golden, B.L. and Wasil, E.A. (2002) Solving the Traveling Salesman Problem with Annealing-Based Heuristics: A Computational Study. IEEE Transactions on System, Man, Cybernetics, Part A: Systems and Humans, 32, 72-77. https://doi.org/10.1109/3468.995530
- Glover, F. Tabu Search—Parts I and II. ORSA J. Computing, Vol. 1, 190-206, 1989 and Vol. 2, 4-32, 1990.
- Tsai, C.F. and Tsai, C.W. (2002) A New Approach for Solving Large Traveling Salesman Problem Using Evolutionary Ant Rules. Neural Networks, 2002 IJCNN ’02 Proceedings of the 2002 International Joint Conference, 2, 1540-1545.
- Modares, A., Somhom, S. and Enkawa, T. (1999) A Self-organizing Approach for Multiple Traveling Salesman and Vehicle Routing Problems. International Transactions in Operations Research, 5, 591-606. https://doi.org/10.1111/j.1475-3995.1999.tb00175.x
- Julstrom, B.A. (1995) Very Greedy Crossover in a Genetic Algorithm for the Traveling Salesman Problem. SAIC ’95: Proceedings of the 1995 ACM Symposium on Applied Computing, Nashville, Tennessee, 26-28 February 1995, 324-328. https://doi.org/10.1145/315891.316009
- Wang, L.Y., Zhang, J. and Li, H. (2007) An Improved Genetic Algorithm for TSP. Machine Learning and Cybernetics, 2007 International Conference, 2, 925-928. https://doi.org/10.1109/icmlc.2007.4370274
- Kindervater, G.A.P. and Lenstra, J.K. (1985) Parallel Algorithms. In: O’hEigeartaigh, M., Lenstra, J.K. and Rinnooy, A.G., Eds., Combinatorial Optimization: Annotated Bibliographies, Wiley, Chichester, 106-128.
- Osman, I. and Kelly, J. (1996) Meta-Heuristics: An Overview. In: Osman, I. and Kelly, J., Eds., Meta-Heuristics: Theory and Applications, Kluwer, Boston, 1-21.
- Katayama, K., Hirabayashi, H. and Narihisa, H. (1998) Performance Analysis of a New Genetic Crossover for the Traveling Salesman Problem. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E81-A, 738-750.