Abstract
In this paper we investigate the usefulness of a new operator, inver-over, for an evolutionary algorithm for the TSP. Inver-over is based on simple inversion, however, knowledge taken from other individuals in the population influences its action. Thus, on one hand, the proposed operator is unary, since the inversion is applied to a segment of a single individual, however, the selection of a segment to be inverted is population driven, thus the operator displays some characterictics of recombination.
This operator outperforms all other ‘genetic’ operators, whether unary or binary, which have been proposed in the past for the TSP in connection with evolutionary systems and the resulting evolutionary algorithm is very fast. For test cases, where the number of cities is around 100, the algorithm reaches the optimum in every execution in a couple of seconds. For larger instances (e.g., 10,000 cities) the results stay within 3% from the estimated optimum.
Preview
Unable to display preview. Download preview PDF.
References
Applegate, D. Bixby, R.E., Chvatal, V., and Cook, W., Finding cuts in the TSP: a preliminary report. Report 95-05, DIMACS, Rutgers University, NJ.
Braun, H., On solving traveling salesman problems by genetic algorithms. In Proc. PPSN'90, pp.129–133.
Davis, L., (Editor), Genetic Algorithms and Simulated Annealing, Morgan Kaufmann Publishers, San Mateo, CA, 1987.
Davis, L., Handbook of Genetic Algorithms, Van Nostrand Reinhold, NY, 1991.
Eshelman, L., The CHC adaptive search algorithm: How to have safe search when engaging in nontraditional genetic recombination. In Proc. FOGA'90, pp.265–283.
Fogel, D.B., An evolutionay approach to the traveling salesman problem. Biol. Cybern., Vol.60, pp.139–144, 1988.
Gorges-Schleuter, M., ASPARAGOS: An asynchronous parallel genetic optimization strategy. In Proc. ICGA'91, pp.422–427.
Grefenstette, J.J., Incorporating Problem Specific Knowledge into Genetic Algorithms. In [3], pp.42–60.
Herdy, M., Application of the Evolution Strategy to Discrete Optimization Problems. In Proc. PPSN'90, pp.188–192.
Johnson, D.S., The Traveling Salesman Problem: A Case Study. In Local Search in Combinatorial Optimization, E. Aarts and J.K. Lenstra (Editors), John Wiley, 1996, pp.215–310.
Johnson, D.S., McGeoch, L.A., and Rothberg, E.E., Asymptotic experimental analysis for the Held-Karp traveling salesman bound. Proc. Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, and SIAM, Philadelphia, PA, pp. 341–350.
Karp, R.M., Probabilistic Analysis of Partitioning Algorithm for the Traveling Salesman Problem in the Plane. Mathematics of Operations Research, Vol.2, No.3, 1977, pp.209–224.
Lidd, M.L., Traveling Salesman Problem Domain Application of a Fundamentally New Approach to Utilizing Genetic Algorithms. Tech. Rep., MITRE Corp., 1991.
Lin, S. and Kerninghan, B.W., An Effective Heuristic Algorithm for the Traveling Salesman Problem. Operations Research, pp.498–516, 1972.
Maekawa, K., Mori, N.,Tamaki, H., Kita, H. and Nishikawa, Y., A genetic solution for the traveling salesman problem by means of a thermodynamical selection rule. Proc. IEEE ICEC '96.
Matias, K. and D. Whitley, Genetic operators, the fitness landscape and the traveling salesman problem. In Proc. PPSN'92, pp.219–228.
Merz, P. and B. Freisleben, Genetic local search for the TSP: New results. Proc. IEEE ICEC '97.
Michalewicz, Z., Genetic Algorithms + Data Structures = Evolution Programs, Springer-Verlag, 3rd edition, 1996.
Mühlenbein, H., Evolution in time and space — The parallel genetic algorithm. In Proc. FOGA'90, pp.316–337.
Nagata, Y. and Kobayashi, S., Edge assembly crossover: A high-power genetic algorithm for the traveling salesman problem. Proc. ICGA '97.
Number, H.-T. and Beyer, H.-G., The dynamics of Evolution Strategies in the optimization of traveling salesman problem, Proc. of EP'97.
Reinelt, G., TSPLIB — A Traveling Salesman Problem Library. ORSA Journal on Computing, Vol.3, No.4, pp.376–384, 1991.
Starkweather, T., McDaniel, S., Mathias, K., Whitley, C., and Whitley, D., A Comparison of Genetic Sequencing Operators. In Proc. ICGA'91, pp.69–76.
Tao, G. and Michalewicz, Z., Evolutionary Algorithms for the TSP. In preparation.
Ulder, N.L.J., Aarts, E.H.L., Bandelt, H.-J., van Laarhoven, P.J.M., Pesch, E., Genetic Local Search Algorithms for the Traveling Salesman Problem. In Proc. PPSN'90, pp.109–116.
Valenzuela, Ch.L. and Willians, L.P., Improving Simple Heuristic Algorithms for the Travelling Salesman Problem using a Genetic Algorithm. In Proc. ICGA'97, pp.458–464.
Whitley, D., Starkweather, T., and Fuquay, D'A., Scheduling Problems and Traveling Salesman: The Genetic Edge Recombination Operator. In Proc. ICGA'89, pp. 133–140.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Tao, G., Michalewicz, Z. (1998). Inver-over operator for the TSP. In: Eiben, A.E., Bäck, T., Schoenauer, M., Schwefel, HP. (eds) Parallel Problem Solving from Nature — PPSN V. PPSN 1998. Lecture Notes in Computer Science, vol 1498. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0056922
Download citation
DOI: https://doi.org/10.1007/BFb0056922
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-65078-2
Online ISBN: 978-3-540-49672-4
eBook Packages: Springer Book Archive