IDEAS home Printed from https://ideas.repec.org/a/spr/jglopt/v55y2013i1p101-124.html
   My bibliography  Save this article

Sequential Monte Carlo simulated annealing

Author

Listed:
  • Enlu Zhou
  • Xi Chen

Abstract

In this paper, we propose a population-based optimization algorithm, Sequential Monte Carlo Simulated Annealing (SMC-SA), for continuous global optimization. SMC-SA incorporates the sequential Monte Carlo method to track the converging sequence of Boltzmann distributions in simulated annealing. We prove an upper bound on the difference between the empirical distribution yielded by SMC-SA and the Boltzmann distribution, which gives guidance on the choice of the temperature cooling schedule and the number of samples used at each iteration. We also prove that SMC-SA is more preferable than the multi-start simulated annealing method when the sample size is sufficiently large. Copyright Springer Science+Business Media, LLC. 2013

Suggested Citation

  • Enlu Zhou & Xi Chen, 2013. "Sequential Monte Carlo simulated annealing," Journal of Global Optimization, Springer, vol. 55(1), pages 101-124, January.
    • Handle: RePEc:spr:jglopt:v:55:y:2013:i:1:p:101-124
    DOI: 10.1007/s10898-011-9838-3
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10898-011-9838-3
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10898-011-9838-3?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Pierre Del Moral & Arnaud Doucet & Ajay Jasra, 2006. "Sequential Monte Carlo samplers," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 68(3), pages 411-436, June.
    2. Reuven Rubinstein, 1999. "The Cross-Entropy Method for Combinatorial and Continuous Optimization," Methodology and Computing in Applied Probability, Springer, vol. 1(2), pages 127-190, September.
    3. Bruce Hajek, 1988. "Cooling Schedules for Optimal Annealing," Mathematics of Operations Research, INFORMS, vol. 13(2), pages 311-329, May.
    4. M. Locatelli, 2000. "Simulated Annealing Algorithms for Continuous Global Optimization: Convergence Conditions," Journal of Optimization Theory and Applications, Springer, vol. 104(1), pages 121-133, January.
    5. Pieter-Tjerk de Boer & Dirk Kroese & Shie Mannor & Reuven Rubinstein, 2005. "A Tutorial on the Cross-Entropy Method," Annals of Operations Research, Springer, vol. 134(1), pages 19-67, February.
    6. R. L. Yang, 2000. "Convergence of the Simulated Annealing Algorithm for Continuous Global Optimization," Journal of Optimization Theory and Applications, Springer, vol. 104(3), pages 691-716, March.
    7. Orcun Molvalioglu & Zelda B. Zabinsky & Wolf Kohn, 2007. "Multi-particle Simulated Annealing," Springer Optimization and Its Applications, in: Aimo Törn & Julius Žilinskas (ed.), Models and Algorithms for Global Optimization, pages 215-222, Springer.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Ng, Kenyon & Turlach, Berwin A. & Murray, Kevin, 2019. "A flexible sequential Monte Carlo algorithm for parametric constrained regression," Computational Statistics & Data Analysis, Elsevier, vol. 138(C), pages 13-26.
    2. John Geweke, 2016. "Sequentially Adaptive Bayesian Learning for a Nonlinear Model of the Secular and Cyclical Behavior of US Real GDP," Econometrics, MDPI, vol. 4(1), pages 1-23, March.
    3. Jinyu Zhang & Kang Gao & Yong Li & Qiaosen Zhang, 2022. "Maximum Likelihood Estimation Methods for Copula Models," Computational Economics, Springer;Society for Computational Economics, vol. 60(1), pages 99-124, June.
    4. Bin Liu, 2017. "Posterior exploration based sequential Monte Carlo for global optimization," Journal of Global Optimization, Springer, vol. 69(4), pages 847-868, December.
    5. Tsionas, Mike G., 2018. "A Bayesian approach to find Pareto optima in multiobjective programming problems using Sequential Monte Carlo algorithms," Omega, Elsevier, vol. 77(C), pages 73-79.
    6. Geweke, John & Durham, Garland, 2019. "Sequentially adaptive Bayesian learning algorithms for inference and optimization," Journal of Econometrics, Elsevier, vol. 210(1), pages 4-25.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Marc Robini & Pierre-Jean Reissman, 2013. "From simulated annealing to stochastic continuation: a new trend in combinatorial optimization," Journal of Global Optimization, Springer, vol. 56(1), pages 185-215, May.
    2. Satyajith Amaran & Nikolaos V. Sahinidis & Bikram Sharda & Scott J. Bury, 2016. "Simulation optimization: a review of algorithms and applications," Annals of Operations Research, Springer, vol. 240(1), pages 351-380, May.
    3. Bin Liu, 2017. "Posterior exploration based sequential Monte Carlo for global optimization," Journal of Global Optimization, Springer, vol. 69(4), pages 847-868, December.
    4. Gerber, Mathieu & Bornn, Luke, 2018. "Convergence results for a class of time-varying simulated annealing algorithms," Stochastic Processes and their Applications, Elsevier, vol. 128(4), pages 1073-1094.
    5. Reuven Y. Rubinstein, 2006. "How Many Needles are in a Haystack, or How to Solve #P-Complete Counting Problems Fast," Methodology and Computing in Applied Probability, Springer, vol. 8(1), pages 5-51, March.
    6. Ad Ridder & Bruno Tuffin, 2012. "Probabilistic Bounded Relative Error Property for Learning Rare Event Simulation Techniques," Tinbergen Institute Discussion Papers 12-103/III, Tinbergen Institute.
    7. Tito Homem-de-Mello, 2007. "A Study on the Cross-Entropy Method for Rare-Event Probability Estimation," INFORMS Journal on Computing, INFORMS, vol. 19(3), pages 381-394, August.
    8. Ali Kadhem, Athraa & Abdul Wahab, Noor Izzri & Aris, Ishak & Jasni, Jasronita & Abdalla, Ahmed N., 2017. "Computational techniques for assessing the reliability and sustainability of electrical power systems: A review," Renewable and Sustainable Energy Reviews, Elsevier, vol. 80(C), pages 1175-1186.
    9. Zheng Peng & Donghua Wu & Quan Zheng, 2013. "A Level-Value Estimation Method and Stochastic Implementation for Global Optimization," Journal of Optimization Theory and Applications, Springer, vol. 156(2), pages 493-523, February.
    10. Alibrandi, Umberto, 2014. "A response surface method for stochastic dynamic analysis," Reliability Engineering and System Safety, Elsevier, vol. 126(C), pages 44-53.
    11. Tai-Yu Ma & Jean-Patrick Lebacque, 2012. "Dynamic System Optimal Routing In Multimodal Transit Network," Working Papers hal-00740347, HAL.
    12. Zheng Peng & Donghua Wu & Wenxing Zhu, 2016. "The robust constant and its applications in random global search for unconstrained global optimization," Journal of Global Optimization, Springer, vol. 64(3), pages 469-482, March.
    13. Ng, Kenyon & Turlach, Berwin A. & Murray, Kevin, 2019. "A flexible sequential Monte Carlo algorithm for parametric constrained regression," Computational Statistics & Data Analysis, Elsevier, vol. 138(C), pages 13-26.
    14. Casas-Ramírez, Martha-Selene & Camacho-Vallejo, José-Fernando & Martínez-Salazar, Iris-Abril, 2018. "Approximating solutions to a bilevel capacitated facility location problem with customer's patronization toward a list of preferences," Applied Mathematics and Computation, Elsevier, vol. 319(C), pages 369-386.
    15. Mattrand, C. & Bourinet, J.-M., 2014. "The cross-entropy method for reliability assessment of cracked structures subjected to random Markovian loads," Reliability Engineering and System Safety, Elsevier, vol. 123(C), pages 171-182.
    16. R. Y. Rubinstein, 2005. "A Stochastic Minimum Cross-Entropy Method for Combinatorial Optimization and Rare-event Estimation," Methodology and Computing in Applied Probability, Springer, vol. 7(1), pages 5-50, March.
    17. M. Bayat & F. Hooshmand & S. A. MirHassani, 2024. "Scenario-based stochastic model and efficient cross-entropy algorithm for the risk-budgeting problem," Annals of Operations Research, Springer, vol. 341(2), pages 731-755, October.
    18. Alan Lockett & Risto Miikkulainen, 2014. "Evolutionary annealing: global optimization in measure spaces," Journal of Global Optimization, Springer, vol. 58(1), pages 75-108, January.
    19. Maldon Goodridge & John Moriarty & Jure Vogrinc & Alessandro Zocca, 2022. "Hopping between distant basins," Journal of Global Optimization, Springer, vol. 84(2), pages 465-489, October.
    20. Nguyen, Hoa T.M. & Chow, Andy H.F. & Ying, Cheng-shuo, 2021. "Pareto routing and scheduling of dynamic urban rail transit services with multi-objective cross entropy method," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 156(C).

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jglopt:v:55:y:2013:i:1:p:101-124. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.