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

The mean and variance of GRASP and GE are almost identical and close to the mean and
variance obtained by Concorde. Since GRASP has slightly better redundancy we used it as
the subject for the next experiment.
3.3 Experiments with Record Keeping
Under the IHC algorithm, the generation of a tour that has been previously considered
results in generating tours that have also been previously considered, and eventually
leads to a local maximal tour that has been previously computed. Therefore, the
obvious solution is to record all computed tours so that duplicates can be detected. In
general, this is not feasible for large TSP instances, so we employ a cache mechanism
to limit the size of memory used by the IHC algorithm. However, we first use
unbounded memory record keeping on 50 random Euclidean graphs, of 100 vertices
each, in order to determine an experimental upper bound on IHC speedup using
record keeping. For IHC runs of 100,000 iterations, the average speedup using
unbounded memory record keeping was 10.9. The same speedup is obtained with a
64,000 blocks cache (cache of 896KB). Figure 2 shows the speedup obtained with
different cache configurations [2, 8, 13]. It is apparent that even with a small cache
size 16KB, we still achieve a speedup of 6.7.
Fig. 2. Speedup obtained with different cache configurations.
4 Conclusion
In this paper, we evaluated the use of six different construction algorithms with the
IHC method of solving the TSP. Our experimental results show that the greedy,
greedy-jump, and GRASP construction algorithms all perform well. The greedy-
jump construction algorithm also generates significantly fewer duplicate tours than
the other algorithms, indicating that it may be more robust in situations where many
local minima occur. Furthermore, we show that utilizing a record keeping mechanism
modeled on cache memory is effective at improving IHC efficiency and can provide a
speed up of up to 10.9x in the given configuration. Moreover, even when the memory
is only large enough to hold a small percentage of duplicate tours generated, cache