Visiting near-optimal solutions using local search algorithms
Sheldon H. Jacobson, Shane N. Hall, Laura A. McLay · 2007
This paper presents results on the analysis of local search algorithms to visit near-optimal solutions. The β-acceptable solution probability is used to capture how effectively an algorithm has performed to date and how effectively an algorithm can be expected to perform in the future. An estimator for the expected number of iterations for local search algorithm to visit a β-acceptable solution is obtained. Computational experiments are reported with a modified simulated annealing algorithm applied to four small travelling salesman problem instances with known optimal solutions.