Improving the Performance of Multi-start Search on the Traveling Salesman Problem - Developing Concepts in Applied Intelligence - page 76

Improving the Performance of Multi-start Search
on the Traveling Salesman Problem
Charles R. King, Mark McKenney, and Dan E. Tamir
Texas State University
Department of Computer Science
{charles.king,mckenney,dt19}@txstate.edu
Abstract. Constructive multi-start search algorithms are commonly used to
address combinatorial optimization problems. Multi-start algorithms recover
from local optima by restarting, which can lead to redundant configurations
when search paths converge. In this paper, we investigate ways to minimize
redundancy using record keeping and analyze several restart algorithms in the
context of iterative hill climbing with applications to the traveling salesman
problem. Experimental results identify the best performing restart algorithms.
Keywords: Combinatorial optimization, traveling salesman problem, iterative
hill climbing, multi-start algorithms.
1 Introduction
Intuitively, combinatorial optimization problems (COPs) compute the “most
favorable” outcome to a problem from a set of possible outcomes. A most favorable
outcome may be the outcome with the highest profit, lowest cost, shortest distance,
etc., depending on the problem being solved. For example, shipping companies have
used COPs to find delivery routes that minimize left turns; by eliminating left turns,
drivers spend less time in traffic waiting to turn, and use less fuel, resulting in
monetary savings for the company. Clearly, COPs have great practical importance.
Many COPs are NP complete and characterized by exponential growth [1-3]; i.e.,
as the size of problem parameters grows, the number of potential solutions grows
exponentially, causing an exhaustive search of outcomes to be impractical.
A heuristic search technique is often used in order to assign weights to outcomes, or
partial outcomes, such that partial solutions that appear to be leading to poor solutions
are not considered, thus, drastically reducing the search space of outcomes.
A drawback to heuristic techniques is that the optimal solution may not be found, but
often a very good solution can be guaranteed. Therefore, heuristic techniques are
applicable only when a sub-optimal solution is acceptable, or when the faster
computation times of heuristic algorithms for COPs are required.
It is well known that many heuristic algorithms explore the same partial solution
(i.e., a state in the state space) more than one time, thereby wasting computational
resources. Several researchers have proposed record keeping mechanisms as a
solution to this problem [4, 5], which we further investigate in this paper. In this
sense, record keeping resembles Tabu search where the Tabu list includes a subset of