IDEAS home Printed from https://ideas.repec.org/a/spr/jglopt/v66y2016i3d10.1007_s10898-016-0407-7.html
   My bibliography  Save this article

SOP: parallel surrogate global optimization with Pareto center selection for computationally expensive single objective problems

Author

Listed:
  • Tipaluck Krityakierne

    (University of Bern)

  • Taimoor Akhtar

    (Cornell University
    National University of Singapore)

  • Christine A. Shoemaker

    (Cornell University
    National University of Singapore
    National University of Singapore)

Abstract

This paper presents a parallel surrogate-based global optimization method for computationally expensive objective functions that is more effective for larger numbers of processors. To reach this goal, we integrated concepts from multi-objective optimization and tabu search into, single objective, surrogate optimization. Our proposed derivative-free algorithm, called SOP, uses non-dominated sorting of points for which the expensive function has been previously evaluated. The two objectives are the expensive function value of the point and the minimum distance of the point to previously evaluated points. Based on the results of non-dominated sorting, P points from the sorted fronts are selected as centers from which many candidate points are generated by random perturbations. Based on surrogate approximation, the best candidate point is subsequently selected for expensive evaluation for each of the P centers, with simultaneous computation on P processors. Centers that previously did not generate good solutions are tabu with a given tenure. We show almost sure convergence of this algorithm under some conditions. The performance of SOP is compared with two RBF based methods. The test results show that SOP is an efficient method that can reduce time required to find a good near optimal solution. In a number of cases the efficiency of SOP is so good that SOP with 8 processors found an accurate answer in less wall-clock time than the other algorithms did with 32 processors.

Suggested Citation

  • Tipaluck Krityakierne & Taimoor Akhtar & Christine A. Shoemaker, 2016. "SOP: parallel surrogate global optimization with Pareto center selection for computationally expensive single objective problems," Journal of Global Optimization, Springer, vol. 66(3), pages 417-437, November.
    • Handle: RePEc:spr:jglopt:v:66:y:2016:i:3:d:10.1007_s10898-016-0407-7
    DOI: 10.1007/s10898-016-0407-7
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10898-016-0407-7
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10898-016-0407-7?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. Felipe Viana & Raphael Haftka & Layne Watson, 2013. "Efficient global optimization algorithm assisted by multiple surrogate techniques," Journal of Global Optimization, Springer, vol. 56(2), pages 669-689, June.
    2. Regis, Rommel G. & Shoemaker, Christine A., 2007. "Parallel radial basis function methods for the global optimization of expensive functions," European Journal of Operational Research, Elsevier, vol. 182(2), pages 514-535, October.
    3. Rommel G. Regis & Christine A. Shoemaker, 2007. "A Stochastic Radial Basis Function Method for the Global Optimization of Expensive Functions," INFORMS Journal on Computing, INFORMS, vol. 19(4), pages 497-509, November.
    4. D. Huang & T. Allen & W. Notz & N. Zeng, 2006. "Global Optimization of Stochastic Black-Box Systems via Sequential Kriging Meta-Models," Journal of Global Optimization, Springer, vol. 34(3), pages 441-466, March.
    5. Juliane Müller & Christine Shoemaker, 2014. "Influence of ensemble surrogate models and sampling strategy on the solution quality of algorithms for computationally expensive black-box global optimization problems," Journal of Global Optimization, Springer, vol. 60(2), pages 123-144, October.
    6. Rommel G. Regis & Christine A. Shoemaker, 2009. "Parallel Stochastic Global Optimization Using Radial Basis Functions," INFORMS Journal on Computing, INFORMS, vol. 21(3), pages 411-426, August.
    7. Haitao Liu & Shengli Xu & Ying Ma & Xiaofang Wang, 2015. "Global optimization of expensive black box functions using potential Lipschitz constants and response surfaces," Journal of Global Optimization, Springer, vol. 63(2), pages 229-251, October.
    8. Remigijus Paulavičius & Yaroslav Sergeyev & Dmitri Kvasov & Julius Žilinskas, 2014. "Globally-biased Disimpl algorithm for expensive global optimization," Journal of Global Optimization, Springer, vol. 59(2), pages 545-567, July.
    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. Marco Quartulli & Amaia Gil & Ane Miren Florez-Tapia & Pablo Cereijo & Elixabete Ayerbe & Igor G. Olaizola, 2021. "Ensemble Surrogate Models for Fast LIB Performance Predictions," Energies, MDPI, vol. 14(14), pages 1-17, July.
    2. Mickaël Binois & David Ginsbourger & Olivier Roustant, 2020. "On the choice of the low-dimensional domain for global optimization via random embeddings," Journal of Global Optimization, Springer, vol. 76(1), pages 69-90, January.
    3. Krityakierne, Tipaluck & Baowan, Duangkamon, 2020. "Aggregated GP-based Optimization for Contaminant Source Localization," Operations Research Perspectives, Elsevier, vol. 7(C).

    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. Juliane Müller & Christine Shoemaker, 2014. "Influence of ensemble surrogate models and sampling strategy on the solution quality of algorithms for computationally expensive black-box global optimization problems," Journal of Global Optimization, Springer, vol. 60(2), pages 123-144, October.
    2. Dawei Zhan & Jiachang Qian & Yuansheng Cheng, 2017. "Pseudo expected improvement criterion for parallel EGO algorithm," Journal of Global Optimization, Springer, vol. 68(3), pages 641-662, July.
    3. Fani Boukouvala & M. M. Faruque Hasan & Christodoulos A. Floudas, 2017. "Global optimization of general constrained grey-box models: new method and its application to constrained PDEs for pressure swing adsorption," Journal of Global Optimization, Springer, vol. 67(1), pages 3-42, January.
    4. Boukouvala, Fani & Misener, Ruth & Floudas, Christodoulos A., 2016. "Global optimization advances in Mixed-Integer Nonlinear Programming, MINLP, and Constrained Derivative-Free Optimization, CDFO," European Journal of Operational Research, Elsevier, vol. 252(3), pages 701-727.
    5. Zhe Zhou & Fusheng Bai, 2018. "An adaptive framework for costly black-box global optimization based on radial basis function interpolation," Journal of Global Optimization, Springer, vol. 70(4), pages 757-781, April.
    6. Taimoor Akhtar & Christine Shoemaker, 2016. "Multi objective optimization of computationally expensive multi-modal functions with RBF surrogates and multi-rule selection," Journal of Global Optimization, Springer, vol. 64(1), pages 17-32, January.
    7. Hau T. Mai & Jaewook Lee & Joowon Kang & H. Nguyen-Xuan & Jaehong Lee, 2022. "An Improved Blind Kriging Surrogate Model for Design Optimization Problems," Mathematics, MDPI, vol. 10(16), pages 1-19, August.
    8. Juliane Müller, 2017. "SOCEMO: Surrogate Optimization of Computationally Expensive Multiobjective Problems," INFORMS Journal on Computing, INFORMS, vol. 29(4), pages 581-596, November.
    9. Juliane Müller & Joshua D. Woodbury, 2017. "GOSAC: global optimization with surrogate approximation of constraints," Journal of Global Optimization, Springer, vol. 69(1), pages 117-136, September.
    10. Wu, Xin & Zheng, Yi & Wu, Bin & Tian, Yong & Han, Feng & Zheng, Chunmiao, 2016. "Optimizing conjunctive use of surface water and groundwater for irrigation to address human-nature water conflicts: A surrogate modeling approach," Agricultural Water Management, Elsevier, vol. 163(C), pages 380-392.
    11. M Laguna & J Molina & F Pérez & R Caballero & A G Hernández-Díaz, 2010. "The challenge of optimizing expensive black boxes: a scatter search/rough set theory approach," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(1), pages 53-67, January.
    12. Rommel Regis & Christine Shoemaker, 2013. "A quasi-multistart framework for global optimization of expensive functions using response surface models," Journal of Global Optimization, Springer, vol. 56(4), pages 1719-1753, August.
    13. Komarudin & Tim De Feyter & Marie-Anne Guerry & Greet Vanden Berghe, 2020. "The extended roster quality staffing problem: addressing roster quality variation within a staffing planning period," Journal of Scheduling, Springer, vol. 23(2), pages 253-264, April.
    14. Juliane Müller & Marcus Day, 2019. "Surrogate Optimization of Computationally Expensive Black-Box Problems with Hidden Constraints," INFORMS Journal on Computing, INFORMS, vol. 31(4), pages 689-702, October.
    15. Mehdad, E. & Kleijnen, Jack P.C., 2014. "Global Optimization for Black-box Simulation via Sequential Intrinsic Kriging," Other publications TiSEM 8fa8d96f-a086-4c4b-88ab-9, Tilburg University, School of Economics and Management.
    16. Dawei Zhan & Jiachang Qian & Yuansheng Cheng, 2017. "Balancing global and local search in parallel efficient global optimization algorithms," Journal of Global Optimization, Springer, vol. 67(4), pages 873-892, April.
    17. Liu, Haoxiang & Wang, David Z.W., 2017. "Locating multiple types of charging facilities for battery electric vehicles," Transportation Research Part B: Methodological, Elsevier, vol. 103(C), pages 30-55.
    18. Nicolau Andrés-Thió & Mario Andrés Muñoz & Kate Smith-Miles, 2022. "Bifidelity Surrogate Modelling: Showcasing the Need for New Test Instances," INFORMS Journal on Computing, INFORMS, vol. 34(6), pages 3007-3022, November.
    19. Krityakierne, Tipaluck & Baowan, Duangkamon, 2020. "Aggregated GP-based Optimization for Contaminant Source Localization," Operations Research Perspectives, Elsevier, vol. 7(C).
    20. Dawei Zhan & Huanlai Xing, 2020. "Expected improvement for expensive optimization: a review," Journal of Global Optimization, Springer, vol. 78(3), pages 507-544, November.

    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:66:y:2016:i:3:d:10.1007_s10898-016-0407-7. 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.