Information in the Traveling Salesman Problem

Gilad Barach, Hugo Fort, Yoni Mehlman, Fredy Zypman

Facultad de Ciencias, Departamento de Física, Montevideo, Uruguay.
Yeshiva University, Department of Physics, New York, NY 10033, USA.

DOI: 10.4236/am.2012.38138                

Abstract

In the Simulated Annealing algorithm applied to the Traveling Salesman Problem, the total tour length decreases with temperature. Empirical observation shows that the tours become more structured as the temperature decreases. We quantify this fact by proposing the use of the Shannon information content of the probability distribution function of inter–city step lengths. We find that information increases as the Simulated Annealing temperature decreases. We also propose a practical use of this insight to improve the standard algorithm by switching, at the end of the algorithm, the cost function from the total length to information content. In this way, the final tour should not only be shorter, but also smoother.

Keywords

Traveling Salesman Problem; Shannon Entropy

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	W. J. Cook, “In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation,” Princeton University Press, Princeton, 2011.
[2]	H. Fort, M. Kornbluth and F. Zypman, “Traveling Salesman Problem for Finite-Size Cities,” Mathematical Structures in Computer Science, Vol. 20, No. 6, 2010, pp. 1067-1078. doi:10.1017/S096012951000037X
[3]	M. N. Ghosh, “Expected Travel among Random Points,” Calcutta Statistical Association, Vol. 2, 1949, pp. 83-87.
[4]	J. Beardwood, J. H. Halton and J. M. Hammersley, “The Shortest Path through Many Points,” Mathematical Proceedings of the Cambridge Philosophical Society, Vol. 55, No. 4, 1959, pp. 299-327. doi:10.1017/S0305004100034095
[5]	A. G. Percus and O. C. Martin, “Finite Size and Dimensional Dependence of the Euclidean Traveling Salesman Problem,” Physical Review Letters, Vol. 76, 1996, pp. 1188-1191. doi:10.1103/PhysRevLett.76.1188
[6]	L. Brillouin, “The Negentropy Principle of Information,” Journal of Applied Physics, Vol. 24, No. 9, 1953, p. 1152. doi:10.1063/1.1721463
[7]	P. Fleurquin, H. Fort, M. Kornbluth, R. Sandler, M. Segall and F. Zypman, “Negentropy Generation and Fractality in the Dry Friction of Polished Surfaces,” Entropy, Vol. 12, No. 3, 2010, pp. 480-489. doi:10.3390/e12030480
[8]	C. E. Shannon, “A Mathematical Theory of Communication,” Bell System Technical Journal, Vol. 27, 1948, pp. 379-423.
[9]	W. Press, S. A. Teukolsky, W. T. Vetterling and B. P. Flannery, “Numerical Recipes in C,” 2nd Edition, Cambridge University Press, Melboune, New York, 1992.
[10]	S. Kirkpatrick, C. D. Gelatt and M. P. Vecchi, “Optimization by Simulated Annealing,” Science, New Series, Vol. 220, 1983, pp. 671-680.
[11]	M. Held and R. M. Karp, “A Dynamic Programming Approach to Sequencing Problems,” Journal of the Society for Industrial and Applied Mathematics, Vol. 10, No. 1, 1962, pp. 196-210. doi:10.1137/0110015
[12]	S. Lin, “Computer Solutions of the Traveling Salesman Problem,” Bell Systems Technical Journal, Vol. 44, 1965, pp. 2245-2269.
[13]	J. Philip, “The Probability Distribution of the Distance between Two Random Points in a Box,” Technical Report Number TRITA MAT 07 MA 10, 1991. http://www.math.kth.se/~johanph/habc.pdf
[14]	J. A. Wheeler, “Information, Physics, Quantum: The Search for Links,” Proceedings of 3rd International Symposium on the Foundations of Quantum Mechanics, Tokyo, 1989, pp. 354-368.
[15]	H. Hernández-Salda?a, J. Flores and T. H. Seligman, “Semi-Poisson Statistics and Beyond,” Physical Review E, Vol. 60, 1999, pp. 449-452. doi:10.1103/PhysRevE.60.449
[16]	E. Jahnke and F. Emde, “Table of Functions with Formulae and Curves,” Dover Publications, New York, 1943, page 18.
[17]	F. Zypman, “Fast Atomic Force Microscopy,” Encyclopedia of Nanoscience and Nanotechnology, Vol. 3, 2004, p. 307.
[18]	B. M. Gibson, E. A. Wasserman and A. C. Kamil, “Pigeons and People Select Efficient Routes when Solving a One-Way Traveling Salesperson Task,” Journal of Experimental Psychology: Animal Behavior Processes, Vol. 33, No. 3, 2007, pp. 244-261. doi:10.1037/0097-7403.33.3.244
[19]	H. Miyata and K. Fujita, “Route Selection by Pigeons (Columba livia) in ‘Traveling Salesperson’ Navigation Tasks Presented on an LCD Screen,” Journal of Comparative Psychology, Vol. 124, No. 4, 2010, pp. 433-446. doi:10.1037/a0019931