Skip to main content
SpringerLink
Log in

Stopping and restarting strategy for stochastic sequential search in global optimization

  • Published:
Journal of Global Optimization Aims and scope Submit manuscript

Abstract

Two common questions when one uses a stochastic global optimization algorithm, e.g., simulated annealing, are when to stop a single run of the algorithm, and whether to restart with a new run or terminate the entire algorithm. In this paper, we develop a stopping and restarting strategy that considers tradeoffs between the computational effort and the probability of obtaining the global optimum. The analysis is based on a stochastic process called Hesitant Adaptive Search with Power-Law Improvement Distribution (HASPLID). HASPLID models the behavior of stochastic optimization algorithms, and motivates an implementable framework, Dynamic Multistart Sequential Search (DMSS). We demonstrate here the practicality of DMSS by using it to govern the application of a simple local search heuristic on three test problems from the global optimization literature.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Abramowitz M., Stegun I.: Handbook of Mathematical Functions with Formulas, Graphs and Mathematical Tables. Dover, New York (1964)

    Google Scholar 

  2. Ali M.M., Khompatraporn C., Zabinsky Z.B.: A numerical evaluation of several global optimization algorithms on selected benchmark test problems. J. Glob. Optim. 31, 635–672 (2005)

    Article  Google Scholar 

  3. Atkinson A.: A segmented algorithm for simulated annealing. Stat. Comput. 2, 221–230 (1992)

    Article  Google Scholar 

  4. Betrò B., Schoen F.: Sequential stopping rules for the multistart algorithm in global optimisation. Math. Program. 38, 271–286 (1987)

    Article  Google Scholar 

  5. Boender C., Rinnooy Kan A.: Bayesian stopping rules for multistart global optimization methods. Math. Program. 37, 59–80 (1987)

    Article  Google Scholar 

  6. Boender C.G.E., Romeijn H.E.: Stochastic methods. In: Horst, R., Pardalos, P. (eds) Handbook of Global Optimization, pp. 829–869. Kluwer, The Netherlands (1995)

    Google Scholar 

  7. Bulger D.W., Wood G.R.: Hesitant adaptive search for global optimisation. Math. Program. 81, 89–102 (1998)

    Google Scholar 

  8. Dekkers A., Aarts E.: Global optimization and simulated annealing. Math. Program. 50, 367–393 (1991)

    Article  Google Scholar 

  9. Dür M., Khompatraporn C., Zabinsky Z.B.: Solving fractional problems with dynamic multistart improving Hit-and-Run. Ann. Oper. Res. 156, 25–44 (2007)

    Article  Google Scholar 

  10. Glidewell, M., Ng, K., Hensel, E.: A combinatorial optimization approach as a pre-processor for impedance tomography. In: Proceedings of the Annual Conference of the IEEE/Engineering in Medicine and Biology Society, pp. 1–2 (1991)

  11. Hajek B.: Cooling schedules for optimal annealing. Math. Oper. Res. 18, 311–329 (1988)

    Article  Google Scholar 

  12. Khompatraporn, C.: Analysis and Development of Stopping Criteria for Stochastic Global Optimization Algorithms. Ph.D. Dissertation, University of Washington, Washington (2004)

  13. Li, H., Lim, A.: A Metaheuristic for the Pickup and Delivery Problem with Time Windows. In: Proceedings of the 13th IEEE International Conference on Tools with Artificial Intelligence, pp. 160–167 (2001)

  14. Locatelli M.: Convergence of a simulated annealing algorithm for continuous global optimization. J. Glob. Optim. 18, 219–234 (2000)

    Article  Google Scholar 

  15. Lundy M., Mees A.: Convergence of an annealing algorithm. Math. Program. 34, 111–124 (1986)

    Article  Google Scholar 

  16. Muselli M.: A theoretical approach to restart in global optimization. J. Glob. Optim. 10, 1–16 (1997)

    Article  Google Scholar 

  17. Romeijn H.E., Smith R.L.: Simulated annealing and adaptive search in global optimization. Probab. Eng. Inf. Sci. 8, 571–590 (1994)

    Article  Google Scholar 

  18. Treadgold N., Gedeon T.: Simulated annealing and weight decay in adaptive learning: the SARPROP algorithm. IEEE Trans. Neural Netw. 9, 662–668 (1998)

    Article  Google Scholar 

  19. Theodosopoulos T.V.: Some remarks on the optimal level of randomization in global optimization. In: Pardalos, P., Rajasekaran, S., Rolim, J. (eds) Randomization Methods in Algorithm Design, DIMACS Series 43., pp. 303–318. American Mathematical Society, RI (1999)

    Google Scholar 

  20. Wales D.J., Doye J.P.K.: Global optimization by basin-hopping and the lowest energy structures of Lennard–Jones clusters containing up to 110 atoms. J. Phys. Chem. A 101, 5111–5116 (1997)

    Article  Google Scholar 

  21. Wood G.R., Zabinsky Z.B., Kristinsdóttir B.P.: Hesitant adaptive search: the distribution of the number of iterations to convergence. Math. Program. A 89, 479–486 (2001)

    Article  Google Scholar 

  22. Zabinsky Z.B.: Stochastic Adaptive Search for Global Optimization. Kluwer, The Netherlands (2003)

    Google Scholar 

  23. Zabinsky Z.B., Smith R.L.: Pure adaptive search in global optimization. Math. Program. 53, 323–338 (1992)

    Article  Google Scholar 

  24. Zabinsky Z.B., Smith R.L., McDonald J.F., Romeijn H.E., Kaufman D.E.: Improving Hit-and-Run for global optimization. J. Glob. Optim. 3, 171–192 (1993)

    Article  Google Scholar 

  25. Zielinski R.: A statistical estimate of the structure of multiextremal problems. Math. Program. 21, 348–356 (1981)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Industrial Engineering, University of Washington, Seattle, WA, 98195-2650, USA

    Zelda B. Zabinsky

  2. Department of Statistics, Macquarie University, Sydney, NSW, 2109, Australia

    David Bulger

  3. Department of Production Engineering, King Mongkut’s University of Technology Thonburi, 126 Pracha-utit Rd., Thungkru, Bangkok, 10140, Thailand

    Charoenchai Khompatraporn

Authors
  1. Zelda B. Zabinsky
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. David Bulger
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Charoenchai Khompatraporn
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to David Bulger.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Zabinsky, Z.B., Bulger, D. & Khompatraporn, C. Stopping and restarting strategy for stochastic sequential search in global optimization. J Glob Optim 46, 273–286 (2010). https://doi.org/10.1007/s10898-009-9425-z

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-009-9425-z

Keywords

Search

Navigation