Stochastic Adaptive Search Methods: Theory and Implementation

Zelda B. Zabinsky ()
Additional contact information
Zelda B. Zabinsky: University of Washington

Chapter Chapter 11 in Handbook of Simulation Optimization, 2015, pp 293-318 from Springer

Abstract: Abstract Random search algorithms are very useful for simulation optimization, because they are relatively easy to implement and typically find a “good” solution quickly. One drawback is that strong convergence results to a global optimum require strong assumptions on the structure of the problem. This chapter begins by discussing optimization formulations for simulation optimization that combines expected performance with a measure of variability, or risk. It then summarizes theoretical results for several adaptive random search algorithms (including pure adaptive search, hesitant adaptive search, backtracking adaptive search and annealing adaptive search) that converge in probability to a global optimum on ill-structured problems. More importantly, the complexity of these adaptive random search algorithms is linear in dimension, on average. While it is not possible to exactly implement stochastic adaptive search with the ideal linear performance, this chapter describes several algorithms utilizing a Markov chain Monte Carlo sampler known as hit-and-run that approximate stochastic adaptive search. The first optimization algorithm discussed that uses hit-and-run is called improving hit-and-run, and it has polynomial complexity, on average, for a class of convex problems. Then a simulated annealing algorithm and a population based algorithm, both using hit-and-run as the candidate point generator, are described. A variation to hit-and-run that can handle mixed continuous/integer feasible regions, called pattern hit-and-run, is described. Pattern hit-and-run retains the same convergence results to a target distribution as hit-and-run on continuous domains. This broadly extends the class of the optimization problems for these algorithms to mixed continuous/integer feasible regions.

Keywords: Simulated Annealing; Feasible Region; Random Search; Boltzmann Distribution; Global Optimization Problem (search for similar items in EconPapers)
Date: 2015
References: Add references at CitEc
Citations: View citations in EconPapers (3)

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:isochp:978-1-4939-1384-8_11

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

DOI: 10.1007/978-1-4939-1384-8_11

Access Statistics for this chapter

More chapters in International Series in Operations Research & Management Science from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().