IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v55y2007i3p549-568.html
   My bibliography  Save this article

A Model Reference Adaptive Search Method for Global Optimization

Author

Listed:
  • Jiaqiao Hu

    (Department of Applied Mathematics and Statistics, State University of New York at Stony Brook, Stony Brook, New York 11794)

  • Michael C. Fu

    (Robert H. Smith School of Business, and Institute for Systems Research, University of Maryland, College Park, Maryland 20742)

  • Steven I. Marcus

    (Department of Electrical and Computer Engineering, and Institute for Systems Research, University of Maryland, College Park, Maryland 20742)

Abstract

Model reference adaptive search (MRAS) for solving global optimization problems works with a parameterized probabilistic model on the solution space and generates at each iteration a group of candidate solutions. These candidate solutions are then used to update the parameters associated with the probabilistic model in such a way that the future search will be biased toward the region containing high-quality solutions. The parameter updating procedure in MRAS is guided by a sequence of implicit probabilistic models we call reference models. We provide a particular algorithm instantiation of the MRAS method, where the sequence of reference models can be viewed as the generalized probability distribution models for estimation of distribution algorithms (EDAs) with proportional selection scheme. In addition, we show that the model reference framework can also be used to describe the recently proposed cross-entropy (CE) method for optimization and to study its properties. Hence, this paper can also be seen as a study on the effectiveness of combining CE and EDAs. We prove global convergence of the proposed algorithm in both continuous and combinatorial domains, and we carry out numerical studies to illustrate the performance of the algorithm.

Suggested Citation

  • Jiaqiao Hu & Michael C. Fu & Steven I. Marcus, 2007. "A Model Reference Adaptive Search Method for Global Optimization," Operations Research, INFORMS, vol. 55(3), pages 549-568, June.
    • Handle: RePEc:inm:oropre:v:55:y:2007:i:3:p:549-568
    DOI: 10.1287/opre.1060.0367
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.1060.0367
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.1060.0367?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
    ---><---

    References listed on IDEAS

    as
    1. 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.
    2. Rubinstein, Reuven Y., 1997. "Optimization of computer simulation models with rare events," European Journal of Operational Research, Elsevier, vol. 99(1), pages 89-112, May.
    3. Mark Zlochin & Mauro Birattari & Nicolas Meuleau & Marco Dorigo, 2004. "Model-Based Search for Combinatorial Optimization: A Critical Survey," Annals of Operations Research, Springer, vol. 131(1), pages 373-395, October.
    4. Fred Glover, 1990. "Tabu Search: A Tutorial," Interfaces, INFORMS, vol. 20(4), pages 74-94, August.
    5. Leyuan Shi & Sigurdur Ólafsson, 2000. "Nested Partitions Method for Global Optimization," Operations Research, INFORMS, vol. 48(3), pages 390-407, June.
    6. 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.
    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.
    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. Xi Chen & Enlu Zhou, 2015. "Population model-based optimization," Journal of Global Optimization, Springer, vol. 63(1), pages 125-148, September.
    2. Kun Lin & Steven I. Marcus, 2016. "Cumulative weighting optimization," Journal of Global Optimization, Springer, vol. 65(3), pages 487-512, July.
    3. Joshua Q. Hale & Enlu Zhou & Jiming Peng, 2017. "A Lagrangian search method for the P-median problem," Journal of Global Optimization, Springer, vol. 69(1), pages 137-156, September.
    4. Lan, Yingjie & Ball, Michael O. & Karaesmen, Itir Z. & Zhang, Jean X. & Liu, Gloria X., 2015. "Analysis of seat allocation and overbooking decisions with hybrid information," European Journal of Operational Research, Elsevier, vol. 240(2), pages 493-504.
    5. Trond Steihaug & Sara Suleiman, 2013. "Global convergence and the Powell singular function," Journal of Global Optimization, Springer, vol. 56(3), pages 845-853, July.
    6. Enlu Zhou & Shalabh Bhatnagar, 2018. "Gradient-Based Adaptive Stochastic Search for Simulation Optimization Over Continuous Space," INFORMS Journal on Computing, INFORMS, vol. 30(1), pages 154-167, February.
    7. Kabirian, Alireza & Ólafsson, Sigurdur, 2011. "Continuous optimization via simulation using Golden Region search," European Journal of Operational Research, Elsevier, vol. 208(1), pages 19-27, January.
    8. Jiaqiao Hu & Hyeong Chang & Michael Fu & Steven Marcus, 2011. "Dynamic sample budget allocation in model-based optimization," Journal of Global Optimization, Springer, vol. 50(4), pages 575-596, August.
    9. Liujia Hu & Sigrún Andradóttir, 2019. "An Asymptotically Optimal Set Approach for Simulation Optimization," INFORMS Journal on Computing, INFORMS, vol. 31(1), pages 21-39, February.
    10. Fan, Qi & Tan, Ken Seng & Zhang, Jinggong, 2023. "Empirical tail risk management with model-based annealing random search," Insurance: Mathematics and Economics, Elsevier, vol. 110(C), pages 106-124.
    11. Heath, Jeffrey W. & Fu, Michael C. & Jank, Wolfgang, 2009. "New global optimization algorithms for model-based clustering," Computational Statistics & Data Analysis, Elsevier, vol. 53(12), pages 3999-4017, October.
    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. Qi Zhang & Jiaqiao Hu, 2019. "Simulation Optimization Using Multi-Time-Scale Adaptive Random Search," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 36(06), pages 1-34, December.
    14. Shi Pu & Alfredo Garcia, 2018. "A Flocking-Based Approach for Distributed Stochastic Optimization," Operations Research, INFORMS, vol. 66(1), pages 267-281, January.
    15. Joshua Q. Hale & Helin Zhu & Enlu Zhou, 2020. "Domination Measure: A New Metric for Solving Multiobjective Optimization," INFORMS Journal on Computing, INFORMS, vol. 32(3), pages 565-581, July.
    16. Johannes Royset, 2013. "On sample size control in sample average approximations for solving smooth stochastic programs," Computational Optimization and Applications, Springer, vol. 55(2), pages 265-309, June.
    17. Jie Xu & Barry L. Nelson & L. Jeff Hong, 2013. "An Adaptive Hyperbox Algorithm for High-Dimensional Discrete Optimization via Simulation Problems," INFORMS Journal on Computing, INFORMS, vol. 25(1), pages 133-146, February.
    18. 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.
    19. Andrea Cassioli & Fabio Schoen, 2013. "Global optimization of expensive black box problems with a known lower bound," Journal of Global Optimization, Springer, vol. 57(1), pages 177-190, September.
    20. Yue Sun & Alfredo Garcia, 2017. "Interactive model-based search with reactive resource allocation," Journal of Global Optimization, Springer, vol. 67(1), pages 135-149, January.
    21. Scott, Alexandre & Metzler, Adam, 2015. "A general importance sampling algorithm for estimating portfolio loss probabilities in linear factor models," Insurance: Mathematics and Economics, Elsevier, vol. 64(C), pages 279-293.
    22. Helin Zhu & Joshua Hale & Enlu Zhou, 2018. "Simulation optimization of risk measures with adaptive risk levels," Journal of Global Optimization, Springer, vol. 70(4), pages 783-809, April.
    23. 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.

    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. 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.
    2. Xi Chen & Enlu Zhou, 2015. "Population model-based optimization," Journal of Global Optimization, Springer, vol. 63(1), pages 125-148, September.
    3. 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.
    4. Enlu Zhou & Shalabh Bhatnagar, 2018. "Gradient-Based Adaptive Stochastic Search for Simulation Optimization Over Continuous Space," INFORMS Journal on Computing, INFORMS, vol. 30(1), pages 154-167, February.
    5. 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.
    6. Jiaqiao Hu & Hyeong Chang & Michael Fu & Steven Marcus, 2011. "Dynamic sample budget allocation in model-based optimization," Journal of Global Optimization, Springer, vol. 50(4), pages 575-596, August.
    7. 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).
    8. Hao Su & Qun Niu & Zhile Yang, 2023. "Optimal Power Flow Using Improved Cross-Entropy Method," Energies, MDPI, vol. 16(14), pages 1-33, July.
    9. Ferdinand Bollwein & Stephan Westphal, 2022. "Oblique decision tree induction by cross-entropy optimization based on the von Mises–Fisher distribution," Computational Statistics, Springer, vol. 37(5), pages 2203-2229, November.
    10. Dirk P. Kroese & Sergey Porotsky & Reuven Y. Rubinstein, 2006. "The Cross-Entropy Method for Continuous Multi-Extremal Optimization," Methodology and Computing in Applied Probability, Springer, vol. 8(3), pages 383-407, September.
    11. Reuven Rubinstein, 2008. "Semi-Iterative Minimum Cross-Entropy Algorithms for Rare-Events, Counting, Combinatorial and Integer Programming," Methodology and Computing in Applied Probability, Springer, vol. 10(2), pages 121-178, June.
    12. 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.
    13. Kin-Ping Hui, 2011. "Cooperative Cross-Entropy method for generating entangled networks," Annals of Operations Research, Springer, vol. 189(1), pages 205-214, September.
    14. Mathieu Balesdent & Jérôme Morio & Loïc Brevault, 2016. "Rare Event Probability Estimation in the Presence of Epistemic Uncertainty on Input Probability Distribution Parameters," Methodology and Computing in Applied Probability, Springer, vol. 18(1), pages 197-216, March.
    15. David R. Morrison & Jason J. Sauppe & Wenda Zhang & Sheldon H. Jacobson & Edward C. Sewell, 2017. "Cyclic best first search: Using contours to guide branch‐and‐bound algorithms," Naval Research Logistics (NRL), John Wiley & Sons, vol. 64(1), pages 64-82, February.
    16. K.-P. Hui & N. Bean & M. Kraetzl & Dirk Kroese, 2005. "The Cross-Entropy Method for Network Reliability Estimation," Annals of Operations Research, Springer, vol. 134(1), pages 101-118, February.
    17. Fahimnia, Behnam & Sarkis, Joseph & Eshragh, Ali, 2015. "A tradeoff model for green supply chain planning:A leanness-versus-greenness analysis," Omega, Elsevier, vol. 54(C), pages 173-190.
    18. Joshua C. C. Chan & Liana Jacobi & Dan Zhu, 2022. "An automated prior robustness analysis in Bayesian model comparison," Journal of Applied Econometrics, John Wiley & Sons, Ltd., vol. 37(3), pages 583-602, April.
    19. 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.
    20. 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.

    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:inm:oropre:v:55:y:2007:i:3:p:549-568. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.