Genetic Algorithms for the Travelling Salesman Problem: A Review of Representations and Operators

• Ackley, D. H. (1987). A Connectionist Machine for Genetic Hillclimbing. Kluwer Academic Publishers.

• Ambati, B. K., Ambati, J. & Mokhtar, M.M. (1991). Heuristic Combinatorial Optimization by Simulated Darwinian Evolution: A Polynomial Time Algorithm for the Traveling Salesman Problem. Biological Cybernetics 65: 31-35.

  Google Scholar 

• Banzhaf, W. (1990). The “Molecular” Traveling Salesman. Biological Cybernetics 64: 7-14.

  Google Scholar 

• Beyer, H. G. (1992). Some Aspects of the 'Evolution Strategy' for Solving TSP-Like Optimization Problems Appearing at the Design Studies of the 0.5 TeVe ⁺ e ⁻-Linear Collider. In Männer, R. & Manderick, B. (eds.) Parallel Problem Solving from Nature 2, 361-370. Amsterdam: North-Holland.

  Google Scholar 

• Brady, R.M. (1985). Optimization Strategies Gleaned from Biological Evolution. Nature 317: 804-806.

  Google Scholar 

• Bremermann, H. J., Rogson, M. & Salaff, S. (1965). Search by Evolution. In Maxfield, M., Callahan A. & Fogel, L. J. (eds.) Biophysics and Cyberntic Systems, 157-167. Washington: Spartan Books.

  Google Scholar 

• Davis, L. (1985). Applying Adaptive Algorithms to Epistatic Domains. Proceedings of the International Joint Conference on Artificial Intelligence, 162-164.

• Davis, L. (ed.) (1991). Handbook of Genetic Algorithms. New York: Van Nostrand Reinhold.

  Google Scholar 

• Fogel, L. J. (1962). Atonomous Automata. Ind. Res. 4: 14-19.

  Google Scholar 

• Fogel, D. B. (1988). An Evolutionary Approach to the Traveling Salesman Problem. Biological Cybernetics 60: 139-144.

  Google Scholar 

• Fogel, D. B. (1990). A Parallel Processing Approach to a Multiple Traveling Salesman Problem Using Evolutionary Programming. In Canter, L. (ed.) Proceedings on the Fourth Annual Parallel Processing Symposium, 318-326. Fullterton, CA.

• Fogel, D. B. (1993). Applying Evolutionary Programming to Selected Traveling Salesman Problems. Cybernetics and Systems 24: 27-36.

  Google Scholar 

• Fox, M. S. & McMahon, M. B. (1987). Genetic Operators for Sequencing Problems. In Rawlings, G. (ed.) Foundations of Genetic Algorithms: First Workshop on the Foundations of Genetic Algorithms and Classifier Systems, 284-300. Los Altos, CA: Morgan Kaufmann Publishers.

  Google Scholar 

• Gunnels, J., Cull, P. & Holloway, J. L. (1994). Genetic Algorithms and Simulated Annealing for Gene Mapping. In Grefenstette, J. J. (ed.) Proceedings of the First IEEE Conference on Evolutionary Computation, 385-390. Florida: IEEE.

  Google Scholar 

• Goldberg, D. E. & Lingle, Jr., R. (1985). Alleles, Loci and the TSP. In Grefenstette, J. J. (ed.) Proceedings of the First International Conference on Genetic Algorithms and Their Applications, 154-159. Hillsdale, New Jersey: Lawrence Erlbaum.

  Google Scholar 

• Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Reading, MA: Addison-Wesley.

  Google Scholar 

• Gorges-Schleuter, M. (1989). ASPARAGOS An Asynchronous Parallel Genetic Optimization Strategy. In Schaffer, J. (ed.) Proceedings on the Third International Conference on Genetic Algorithms, 422-427. Los Altos, CA: Morgan Kaufmann Publishers.

  Google Scholar 

• Grefenstette, J., Gopal, R., Rosmaita, B. & Van Gucht, D. (1985). Genetic Algorithms for the TSP. In Grefenstette, J. J. (ed.) Proceedings of the First International Conference on Genetic Algorithms and Their Applications, 160-165. Hillsdale, New Jersey: Lawrence Erlbaum.

  Google Scholar 

• Grefenstette, J. J. (ed.) (1987a). Genetic Algorithms and Their Applications: Proceedings of the Second International Conference. Hillsdale, New Jersey: Lawrence Erlbaum.

  Google Scholar 

• Grefenstette, J. J. (1987b). Incorporating Problem Specific Knowledge into Genetic Algorithms. In Davis, L. (ed.) Genetic Algorithms and Simulated Annealing, 42-60. Los Altos, CA: Morgan Kaufmann.

  Google Scholar 

• Holland, J. (1975). Adaptation in Natural and Artificial Systems. Ann Arbor: University of Michigan Press.

  Google Scholar 

• Homaifar, A. & Guan, S. (1991). A New Approach on the Traveling Salesman Problem by Genetic Algorithm. Technical Report, North Carolina A&T State University.

• Homaifar, A., Guan, S. & Liepins, G. E. (1993). A New Approach on the Traveling Salesman Problem by Genetic Algorithms. In Forrest, S. (ed.) Proceedings of the Fifth International Conference on Genetic Algorithms, 460-466.

• Jog, P., Suh, J. Y. & Van Gucht, D. (1989). The Effects of Population Size, Heuristic Crossover and Local Improvement on a Genetic Algorithm for the Traveling Salesman Problem. In Schaffer, J. (ed.) Proceedings on the Third International Conference on Genetic Algorithms, 110-115. Los Altos, CA: Morgan Kaufmann Publishers.

  Google Scholar 

• Johnson, D. S. (1990). Local Optimization and the Traveling Salesman Problem. Proc. 17th Colloq. Automata, Languages and Programming. Springer-Verlag.

• Kirkpatrick, S., Gelatt, C. D. & Vecchi, M. P. (1983). Optimization by Simulated Annealing. Science 220: 671-680.

  Google Scholar 

• Koza, J. R. (1992). Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press.

• Larrañaga, P., Kuijpers, C. M. H., Poza, M. & Murga, R. H. (1996a) Decomposing Bayesian Networks: Triangulation of the Moral Graph with Genetic Algorithms. Statistics and Computing (to be published).

• Larrañaga, P., Kuijpers, C. M. H., Murga, R. H. & Yurramendi, Y. (1996b). Searching for the Best Ordering in the Structure Learning of Bayesian Networks. IEEE Transactions on Systems, Man and Cybernetics 26(4): 487-493.

  Google Scholar 

• Larrañaga, P., Inza, I., Kuijpers, C. M. H., Graña, M. & Lozano, J. A. (1996c). Algoritmos Genéticos en el Problema del Viajante de Comercio. Informatica y Automatica (submitted).

• Lauritzen, S. L. & Spiegelhalter, D. J. (1988). Local Computations with Probabilities on Graphic Structures and Their Application on Expert Systems. Journal of the Royal Statistical Society, Series B 50(2): 157-224.

  Google Scholar 

• Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A. H. G. & Shmoys, D. B. (eds.) (1985). The Travelling Salesman Problem: A Guided Tour of Combinatorial Optimization. Chichester: Wiley.

  Google Scholar 

• Lidd, M. L. (1991). The Travelling Salesman Problem Domain Application of a Fundamentally New Approach to Utilizing Genetic Algorithms. Technical Report, MITRE Corporation.

• Liepins, G. E., Hilliard, M. R., Palmer, M. & Morrow, M. (1987). Greedy Genetics. In Grefenstette, J. J. (ed.) Genetic Algorithms and Their Applications: Proceedings of the Second International Conference, 90-99. Hillsdale, New Jersey: Lawrence Erlbaum.

  Google Scholar 

• Lin, S. (1965). Computer Solutions on the Travelling Salesman Problem. Bell Systems Techn. J. 44: 2245-2269.

  Google Scholar 

• Lin, S. & Kernighan, B. W. (1973). An Effective Heuristic Algorithm for the Traveling Salesman Problem. Operations Research 21: 498-516.

  Google Scholar 

• Lin, F.-T., Kao, C.-Y. & Hsu, C.-C. (1993). Applying the Genetic Approach to Simulated Annealing in Solving NP-Hard Problems. IEEE Transactions on Systems, Man, and Cybernetics 23(6): 1752-1767.

  Google Scholar 

• Lozano, J. A., Larrañaga, P. & Graña, M. (1996). Partitional Cluster Analysis with Genetic Algorithms: Searching for the Number of Clusters. Fifth Conference of International Federation of Classification Societies, 251-252. Kobe, Japan.

• Matthews, R. A. J. (1993). The Use of Genetic Algorithms in Cryptanalysis. Cryptologia XVII(2): 187-201.

  Google Scholar 

• Michalewicz, Z. (1992). Genetic Algorithms + Data Structures = Evolution Programs. Berlin Heidelberg: Springer Verlag.

  Google Scholar 

• Mühlenbein, H., Gorges-Schleuter, M. & Krämer, O. (1987). New Solutions to the Mapping Problem of Parallel Systems: The Evolution Approach. Parallel Computing 4: 269-279.

  Google Scholar 

• Mühlenbein, H., Gorges-Schleuter, M. & Krämer, O. (1988). Evolution Algorithms in Combinatorial Optimization. Parallel Computing 7: 65-85.

  Google Scholar 

• Mühlenbein, H. (1989). Parallel Genetic Algorithms, Population Genetics and Combinatorial Optimization. In Schaffer, J. (ed.) Proceedings on the Third International Conference on Genetic Algorithms, 416-421. Los Altos, CA: Morgan Kaufmann Publishers.

  Google Scholar 

• Mühlenbein, H. & Kindermann, J. (1989). The Dynamics of Evolution and Learning — Towards Genetic Neural Networks. In Pfeiffer, J. (ed.) Connectionism in Perspectives.

• Mühlenbein, H. (1991). Evolution in Time and Space — The Parallel Genetic Algorithm. In Rawlins, G. (ed.) Foundations of Genetic Algorithms. Los Altos, CA: Morgan Kaufmann.

  Google Scholar 

• Oliver, I. M., Smith, D. J. & Holland, J. R. C. (1987). A Study of Permutation Crossover Operators on the TSP. In Grefenstette, J. J. (ed.) Genetic Algorithms and Their Applications: Proceedings of the Second International Conference, 224-230. Hillsdale, New Jersey: Lawrence Erlbaum.

  Google Scholar 

• Or, I. (1976). Travelling Salesman-Type Combinatorial Problems and Their Relation to the Logistics of Regional Blood Banking. PhD Thesis, Northwestern University.

• Prinetto, P., Rebaudengo, M. & Sonza Reorda, M. (1993). Hybrid Genetic Algorithms for the Traveling Salesman Problem. In Albrecht, R. F., Reeves, C. R. & Steele, N. C. (eds.) Artificial Neural Nets and Genetic Algorithms, 559-566. Wien: Springer-Verlag.

  Google Scholar 

• Rechenberg, I. (1973). Optimierung Technischer Systeme Nach Prinzipien der Biologischen Information. Stuttgart: Frommann Verlag.

  Google Scholar 

• Reinelt, G. (1991). TSPLIB — A Traveling Salesman Library. ORSA Journal on Computing 3(4): 376-384.

  Google Scholar 

• Schaffer, J. (ed.) (1989). Proceedings on the Third International Conference on Genetic Algorithms. Los Altos, CA: Morgan Kaufmann Publishers.

  Google Scholar 

• Schwefel, H.P. (1975). Evolutionsstrategie und Numerische Optimierung. Doctoral Thesis Diss. D 83, TU Berlin.

• Seniw, D. (1991). A Genetic Algorithm for the Traveling Salesman Problem. MSc Thesis, University of North Carolina at Charlotte.

• Spillman, R., Janssen, M., Nelsonn B. & Kepner, M. (1993). Use of a Genetic Algorithm in the Cryptanalysis Simple Substitution Ciphers. Cryptologia XVII(1): 31-44.

  Google Scholar 

• SPSS-X, User's Guide (1988). 3rd Edition.

• Starkweather, T., McDaniel, S., Mathias, K., Whitley, C. & Whitley, D. (1991). A Comparison of Genetic Sequencing Operators. In Belew, R. & Booker, L. (eds.) Proceedings on the Fourth International Conference on Genetic Algorithms, 69-76. Los Altos, CA: Morgan Kaufmann Publishers.

  Google Scholar 

• Suh, J. Y. & Van Gucht, D. (1987). Incorporating Heuristic Information into Genetic Search. In Grefenstette, J. J. (ed.) Genetic Algorithms and Their Applications: Proceedings of the Second International Conference, 100-107. Hillsdale, New Jersey: Lawrence Erlbaum.

  Google Scholar 

• Syswerda, G. (1991). Schedule Optimization Using Genetic Algorithms. In Davis, L. (ed.) Handbook of Genetic Algorithms, 332-349. New York: Van Nostrand Reinhold.

  Google Scholar 

• Ulder, N. L. J., Aarts, E. H. L., Bandelt, H.-J., Van Laarhoven, P. J. M. & Pesch, E. (1990). Genetic Local Search Algorithms for the Traveling Salesman Problem. In Parallel Problem Solving from Nature, 106-116. Berlin Heidelberg: Springer-Verlag.

  Google Scholar 

• Whitley, D., Starkweather, T. & D'Ann Fuquay (1989). Scheduling Problems and Travelling Salesman: The Genetic Edge Recombination Operator. In Schaffer, J. (ed.) Proceedings on the Third International Conference on Genetic Algorithms, 133-140. Los Altos, CA: Morgan Kaufmann Publishers.

  Google Scholar 

• Whitley, D., Starkweather, T. & Shaner, D. (1991). The Traveling Salesman and Sequence Scheduling: Quality Solutions Using Genetic Edge Recombination. In Davis, L. (ed.) Handbook of Genetic Algorithms, 350-372. New York: Van Nostrand Reinhold.

  Google Scholar 

Download references