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

the states encountered so far [6, 7]. It differs from Tabu in that the objective of short
term Tabu memory (e.g., a cache) is to explore the solution space more intelligently
rather than to speed the search [7]. The goal of long-term Tabu is to enable revisiting
explored search states in order to attempt to find a better local optimum [6, 7].
In [4], we analyzed the performance of a cache as a means for record keeping. In
[8], we investigated several other record keeping mechanisms such as dedicated
memory, and Bloom filters [9]. In this paper, we investigate the performance of
record keeping multi-start COP algorithms using various restart algorithms where the
record keeping mechanism is a cache. We investigate these in the context of the
travelling salesman problem (TSP), using iterative hill climbing (IHC) heuristic
search algorithm as the multi-start heuristic procedure [2, 3, 10]. The TSP is chosen
since it is a classic, well-understood COP with many practical applications [10].
In this paper, we investigate the performance of six construction (restart)
algorithms used in the context of IHC with randomly generated and benchmark TSP
problems. The performance of the restart algorithms is empirically determined and
the algorithms are compared for performance and solution quality.
The second contribution of this paper is to determine the amount of redundancy
associated with various construction algorithms, and utilize record keeping techniques
to reduce duplicate path exploration. We show empirically that a good choice of
construction algorithm and record keeping mechanism provides improved
convergence time. The evaluation of construction algorithms and the use of record
keeping have been studied in previous work [4, 8]. Our work differs from that work in
that we consider a larger group of construction algorithms, we provide a more in-
depth study of the effects of different cache configurations, and we provide a
comparison of cache performance to unbounded memory record keeping.
2 Construction Algorithms
In the case of the TSP, IHC can be implemented as a constructive multi-start search ,
in which multiple solutions are computed by constructing solutions from an initial
solution. At each step, the concept of a neighborhood is used in which a
neighborhood of a solution ݏ is defined as the set of solutions ܵ that are generated by
making a minor modification, denoted a move, to ݏ [11, 12]. For example, a TSP tour
can be adjusted by an operation such as 2-opt which results in exchanging the
visitation order of two cities [2]. The IHC algorithm proceeds by choosing the best
ݏԢאܵ as the next step. The move ݏ is then assigned ݏԢ and the process is repeated
until no improvements to ݏ can be made. This solution is referred to as the locally
optimal solution. In general, the algorithm repeatedly restarts with a new starting
configuration until a sufficiently good solution is reached, or a set running time has
expired. The goal of this paper is to determine the performance of various restart
algorithms in generating solutions to the TSP in the context of iterative hill climbing
and record keeping. The restart algorithms evaluated, described in details in ref. [8],
are: 1) Greedy Enumeration , 2) Greedy Jump , 3) GRASP [12], 4) Nearest Neighbor
[2], 5) Clarke-Wright [2], and 6) Random . Identical neighborhood generating
algorithms are used for all implementations.