Doctoral Dissertations
Abstract
"The Traveling Salesman Problem (TSP) is one of the most widely studied problems in the computer science literature. As a member of the class of NP-complete problems, practical approaches to the TSP require heuristics and approximation techniques. Computational Intelligence approaches have traditionally performed very poorly on combinatorial optimization problems such as the TSP, when compared to results in Operations Research. This dissertation explores two different Computational Intelligence techniques and combines them with the latest Operations Research local search heuristics to develop new heuristics that expand the capabilities of existing techniques. The first approach combines an Adaptive Resonance Theory (ART) neural network with the iterated Lin-Kernighan algorithm to divide and conquer extremely large TSPs. This new algorithm provides significant advantages in scaling and memory usage. The second approach uses an Evolutionary Algorithm to parallelize the iterated LinKernighan algorithm and explore the search space more thoroughly. This hybrid approach converges more slowly on the standard randomly distributed problems, but improves the search capability as compared to the standard approach on "hard" TSP instances from the TSPLIB. Overall, these two new heuristics demonstrate that Computational Intelligence does have something to add to the field of combinatorial optimization and provide direction for future research. In addition, a library of TSP algorithms was developed. Availability of these algorithms in an easy to modify form should open the door to future TSP research. Current versions will be made available at www.traveling-salesman.org"--Abstract, page iii.
Advisor(s)
Wunsch, Donald C.
Committee Member(s)
St. Clair, Daniel C.
McMillin, Bruce M.
Tauritz, Daniel R.
Venayagamoorthy, Ganesh K.
Department(s)
Computer Science
Degree Name
Ph. D. in Computer Science
Publisher
University of Missouri--Rolla
Publication Date
Summer 2004
Pagination
ix, 77 pages; CD-ROM
Note about bibliography
Includes bibliographical references (pages 73-76).
Rights
© 2004 Samuel Aaron Mulder, All rights reserved.
Document Type
Dissertation - Restricted Access
File Type
text
Language
English
Subject Headings
Traveling-salesman problemHeuristic programmingCombinatorial optimization
Thesis Number
T 8560
Print OCLC #
61895974
Recommended Citation
Mulder, Samuel A., "Computational intelligence and the traveling salesman" (2004). Doctoral Dissertations. 1559.
https://scholarsmine.mst.edu/doctoral_dissertations/1559
Share My Dissertation If you are the author of this work and would like to grant permission to make it openly accessible to all, please click the button above.
Comments
System requirements: C++ Compiler required. Microsoft Visual Studio.NET using the Intel C++ Compiler 8.0 recommended.