Improving the Performance of Constructive Multi-Start Search Using Record Keeping
MetadataShow full metadata
Constructive multi-start search algorithms are commonly used to address combinatorial optimization problems such as the traveling salesman problem (TSP). Multi-start algorithms recover from local optima by restarting, which can lead to redundant configurations when search paths converge. Record keeping mechanisms can be used to minimize this redundancy, enabling a time/space tradeoff. This thesis investigates the utility of several restart algorithms and record keeping mechanisms in the context of iterative hill climbing (IHC) in the TSP domain. Restart algorithms including GRASP, greedy enumeration, random restart, Clarke-Wright, and nearest neighbor as well as record keeping mechanisms including unbounded memory, dedicated memory, cache memory, and Bloom filters are investigated. Experiments performed using TSPLIB benchmarks and near-optimal solutions to random TSP instances show that under the above-mentioned mechanisms, IHC produces competitive results, in most cases within 1.5 percent of optimal. The study concludes that GRASP and greedy enumeration significantly outperform other restart mechanisms. Furthermore, the research shows that record keeping can considerably improve both the time performance of IHC and the quality of solutions produced. The cache and Bloom filter record keeping mechanisms reduced the total running time by 90.8 percent when fixing the total number of climbs, resulting in a speed-up factor or 10.9. Unbounded memory experiments confirmed this figure as the upper bound. Additionally, both mechanisms achieved a solution quality improvement of 0.518 percent when fixing the total number of steps, which was again confirmed as the upper bound.