TY - JOUR
T1 - A framework for analyzing sub-optimal performance of local search algorithms
AU - Nikolaev, Alexander G.
AU - Jacobson, Sheldon H.
AU - Hall, Shane N.
AU - Henderson, Darrall
N1 - Funding Information:
Acknowledgements This research has been supported in part by the Air Force Office of Scientific Research (FA9550-07-1-0232). The authors wish to thank the Associate Editor and two anonymous referees for their helpful comments and suggestions, which has resulted in a significantly improved manuscript. The views expressed in this paper are those of the authors and do not reflect the official policy or position of the United States Air Force, Department of Defense, or the United States Government.
PY - 2011/7
Y1 - 2011/7
N2 - This paper presents a framework for analyzing and comparing sub-optimal performance of local search algorithms for hard discrete optimization problems. The β-acceptable solution probability is introduced that captures how effectively an algorithm has performed to date and how effectively an algorithm can be expected to perform in the future. Using this probability, the necessary conditions for a local search algorithm to converge in probability to β-acceptable solutions are derived. To evaluate and compare the effectiveness of local search algorithms, two estimators for the expected number of iterations to visit a β-acceptable solution are obtained. Computational experiments are reported with simulated annealing and tabu search applied to four small traveling salesman problem instances, and the Lin-Kernighan- Helsgaun algorithm applied to eight medium to large traveling salesman problem instances (all with known optimal solutions), to illustrate the application of these estimators.
AB - This paper presents a framework for analyzing and comparing sub-optimal performance of local search algorithms for hard discrete optimization problems. The β-acceptable solution probability is introduced that captures how effectively an algorithm has performed to date and how effectively an algorithm can be expected to perform in the future. Using this probability, the necessary conditions for a local search algorithm to converge in probability to β-acceptable solutions are derived. To evaluate and compare the effectiveness of local search algorithms, two estimators for the expected number of iterations to visit a β-acceptable solution are obtained. Computational experiments are reported with simulated annealing and tabu search applied to four small traveling salesman problem instances, and the Lin-Kernighan- Helsgaun algorithm applied to eight medium to large traveling salesman problem instances (all with known optimal solutions), to illustrate the application of these estimators.
KW - Convergence
KW - Discrete optimization
KW - Finite-time performance
KW - Heuristics
KW - Lin-Kernighan-Helsgaun algorithm
KW - Local search
KW - Simulated annealing
KW - Tabu search
KW - Traveling salesman problem
UR - http://www.scopus.com/inward/record.url?scp=84856363959&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84856363959&partnerID=8YFLogxK
U2 - 10.1007/s10589-009-9290-1
DO - 10.1007/s10589-009-9290-1
M3 - Article
AN - SCOPUS:84856363959
SN - 0926-6003
VL - 49
SP - 407
EP - 433
JO - Computational Optimization and Applications
JF - Computational Optimization and Applications
IS - 3
ER -