Visiting near-optimal solutions using local search algorithms

Sheldon H. Jacobson (), Shane N. Hall and Laura A. McLay
Additional contact information
Sheldon H. Jacobson: University of Illinois, Simulation and Optimization Laboratory
Shane N. Hall: University of Illinois, Simulation and Optimization Laboratory
Laura A. McLay: University of Illinois, Simulation and Optimization Laboratory

A chapter in Compstat 2006 - Proceedings in Computational Statistics, 2006, pp 471-481 from Springer

Abstract: Abstract 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.

Keywords: Local Search; Performance Analysis (search for similar items in EconPapers)
Date: 2006
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-7908-1709-6_38

Ordering information: This item can be ordered from
http://www.springer.com/9783790817096

DOI: 10.1007/978-3-7908-1709-6_38

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().