A framework for analyzing sub-optimal performance of local search algorithms

作者：Nikolaev Alexander G; Jacobson Sheldon H^*; Hall Shane N; Henderson Darrall

来源：Computational Optimization and Applications, 2011, 49(3): 407-433.

DOI：10.1007/s10589-009-9290-1

• Discrete optimization
• Convergence
• Heuristics
• Local search
• Finite-time performance
• Simulated annealing
• Tabu search
• Lin-Kernighan-Helsgaun algorithm
• Traveling salesman problem

This paper presents a framework for analyzing and comparing sub-optimal performance of local search algorithms for hard discrete optimization problems. The beta-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 beta-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 beta-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.

• 出版日期2011-7
• 单位西北大学