[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

HAS-EA: a fast parallel surrogate-assisted evolutionary algorithm

  • Regular research paper
  • Published:
Memetic Computing Aims and scope Submit manuscript

Abstract

Many real-world phenomena are modeled as expensive optimization problems (EOPs) that are not readily solvable without extensive computational cost. Surrogate-assisted mechanisms and parallel computing techniques are effective approaches to improving the search performance of evolutionary algorithms for these EOPs. However, the search efficiency of existing methods are limited by a combination of synchronization barriers and a failure to use heterogeneous computing resources fully. Therefore, we propose an efficient heterogeneous asynchronous parallel surrogate-assisted evolutionary algorithm (HAS-EA). The proposed HAS-EA incorporates an improved asynchronous parallel evolutionary algorithm module on the CPU, a surrogate module on the GPU, and an improved asynchronous recommendation module on the CPU. By performing these operations in parallel on heterogeneous computing resources, the search performance can be accelerated. Test results of our proposed method with several benchmark problems and a real-world model calibration problem demonstrate that HAS-EA offers better performance than other recently published methods in solving EOPs.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Notes

  1. The data sets generated during and/or analysed during the current study are available from the corresponding author on reasonable request.

References

  1. Song Z, Wang H, Xu H (2021) A framework for expensive many-objective optimization with pareto-based bi-indicator infill sampling criterion. Memet Comput 14:179–191

    Article  Google Scholar 

  2. Lu C, Gao L, Li X, Hu C, Yan X, Gong W (2020) Chaotic-based grey wolf optimizer for numerical and engineering optimization problems. Memet Comput 12(4):371–398

    Article  Google Scholar 

  3. Strofylas GA, Porfyri KN, Nikolos IK, Delis AI, Papageorgiou M (2018) Using synchronous and asynchronous parallel differential evolution for calibrating a second-order traffic flow model. Adv Eng Softw 125:1–18

    Article  Google Scholar 

  4. Zhong J-H, Shen M, Zhang J, Chung HS-H, Shi Y-H, Li Y (2012) A differential evolution algorithm with dual populations for solving periodic railway timetable scheduling problem. IEEE Trans Evol Comput 17(4):512–527

    Article  Google Scholar 

  5. Pizzuti C (2017) Evolutionary computation for community detection in networks: a review. IEEE Trans Evol Comput 22(3):464–483

    Article  MathSciNet  Google Scholar 

  6. Gabardo AC, Berretta R, Moscato P (2020) M-link: a link clustering memetic algorithm for overlapping community detection. Memet Comput 12(2):87–99

    Article  Google Scholar 

  7. Jian J-R, Chen Z-G, Zhan Z-H, Zhang J (2021) Region encoding helps evolutionary computation evolve faster: a new solution encoding scheme in particle swarm for large-scale optimization. IEEE Trans Evol Comput 25(4):779–793

    Article  Google Scholar 

  8. Scott EO, De Jong KA (2015) Evaluation-time bias in asynchronous evolutionary algorithms. In: Proceedings of the companion publication of the 2015 annual conference on genetic and evolutionary computation, pp 1209–1212

  9. Churchill AW, Husbands P, Philippides A (2013) Tool sequence optimization using synchronous and asynchronous parallel multi-objective evolutionary algorithms with heterogeneous evaluations. In: 2013 IEEE congress on evolutionary computation. IEEE, pp 2924–2931

  10. Wang H (2016) Uncertainty in surrogate models. In: GECCO (Companion), p 1279

  11. Cao Z, Lin C, Zhou M, Zhang J (2020) Surrogate-assisted symbiotic organisms search algorithm for parallel batch processor scheduling. IEEE/ASME Trans Mechatron 25(5):2155–2166

    Article  Google Scholar 

  12. Berveglieri N, Derbel B, Liefooghe A, Aguirre H, Zhang Q, Tanaka K (2020) Designing parallelism in surrogate-assisted multiobjective optimization based on decomposition. In: Proceedings of the 2020 genetic and evolutionary computation conference, pp 462–470

  13. Briffoteaux G, Ragonnet R, Mezmaz M, Melab N, Tuyttens D (2020) Evolution control for parallel ann-assisted simulation-based optimization application to tuberculosis transmission control. Future Gener Comput Syst 113:454–467

    Article  Google Scholar 

  14. Jones DR, Schonlau M, Welch WJ (1998) Efficient global optimization of expensive black-box functions. J Glob Optim 13(4):455–492

    Article  MathSciNet  MATH  Google Scholar 

  15. Knowles J (2006) Parego: a hybrid algorithm with on-line landscape approximation for expensive multiobjective optimization problems. IEEE Trans Evol Comput 10(1):50–66

    Article  Google Scholar 

  16. Kan G, Lei T, Liang K, Li J, Ding L, He X, Yu H, Zhang D, Zuo D, Bao Z et al (2016) A multi-core cpu and many-core gpu based fast parallel shuffled complex evolution global optimization approach. IEEE Trans Parallel Distrib Syst 28(2):332–344

    Google Scholar 

  17. Pleiss G, Gardner J, Weinberger K, Wilson AG (2018) Constant-time predictive distributions for gaussian processes. In: International conference on machine learning. PMLR, pp 4114–4123

  18. Sanderson C, Curtin R (2016) Armadillo: a template-based c++ library for linear algebra. J Open Source Softw 1(2):26

    Article  Google Scholar 

  19. Sanderson C, Curtin R (2018) A user-friendly hybrid sparse matrix class in c++. In: International congress on mathematical software. Springer, pp 422–430

  20. Haftka RT, Villanueva D, Chaudhuri A (2016) Parallel surrogate-assisted global optimization with expensive functions-a survey. Struct Multidiscip Optim 54(1):3–13

    Article  MathSciNet  Google Scholar 

  21. Rehbach F, Zaefferer M, Stork J, Bartz-Beielstein T (2018) Comparison of parallel surrogate-assisted optimization approaches. In: Proceedings of the genetic and evolutionary computation conference, pp 1348–1355

  22. Zhou Z, Ong YS, Nair PB, Keane AJ, Lum KY (2006) Combining global and local surrogate models to accelerate evolutionary optimization. IEEE Trans Syst Man Cybern Part C (Appl Rev) 37(1):66–76

    Article  Google Scholar 

  23. Tasoulis DK, Pavlidis NG, Plagianakos VP, Vrahatis MN (2004) Parallel differential evolution. In: Congress on evolutionary computation

  24. Cantu-Paz E, Goldberg DE (2000) Efficient parallel genetic algorithms: theory and practice. Comput Methods Appl Mech Eng 186(2–4):221–238

    Article  MathSciNet  MATH  Google Scholar 

  25. Ying D, Khon E, Liang Y, Lim T, Ng JW, Yin L (2014) Gpu implementation of gaussian processes. In: Academy of marketing science conference

  26. Djolonga J, Krause A, Cevher V (2013) High-dimensional gaussian process bandits. In: Neural information processing systems

  27. Pleiss G, Jankowiak M, Eriksson D, Damle A, Gardner JR (2020) Fast matrix square roots with applications to gaussian processes and bayesian optimization. arXiv:2006.11267

  28. Wang K, Pleiss G, Gardner J, Tyree S, Weinberger KQ, Wilson AG (2019) Exact gaussian processes on a million data points. Adv Neural Inf Process Syst 32:14648–14659

    Google Scholar 

  29. Sun C, Jin Y, Zeng J, Yu Y (2015) A two-layer surrogate-assisted particle swarm optimization algorithm. Soft Comput 19(6):1461–1475

    Article  Google Scholar 

  30. Regis RG (2013) Evolutionary programming for high-dimensional constrained expensive black-box optimization using radial basis functions. IEEE Trans Evol Comput 18(3):326–347

    Article  Google Scholar 

  31. Loshchilov I, Schoenauer M, Sebag M (2010) Comparison-based optimizers need comparison-based surrogates. In: International conference on parallel problem solving from nature. Springer, pp 364–373

  32. Scott EO, De Jong KA (2015) Understanding simple asynchronous evolutionary algorithms. In: Proceedings of the 2015 ACM conference on foundations of genetic algorithms XIII, pp 85–98

  33. Zeng R, Huang Z, Chen Y, Zhong J, Feng L (2020) Comparison of different computing platforms for implementing parallel genetic programming. In: 2020 IEEE congress on evolutionary computation (CEC). IEEE, pp 1–8

  34. Dang X, Gong D, Yao X, Tian T, Liu H (2022) Enhancement of mutation testing via fuzzy clustering and multi-population genetic algorithm. IEEE Trans Softw Eng 48(6):2141–2156. https://doi.org/10.1109/TSE.2021.3052987. Accessed 1 June 2022

  35. Wang H, Jin Y, Doherty J (2017) Committee-based active learning for surrogate-assisted particle swarm optimization of expensive problems. IEEE Trans Cybern 47(9):2664–2677. https://doi.org/10.1109/tcyb.2017.2710978

    Article  Google Scholar 

  36. Luong TV, Melab N, Talbi E-G (2010) Gpu-based island model for evolutionary algorithms. In: Proceedings of the 12th annual conference on genetic and evolutionary computation, pp 1089–1096

  37. Benkhider S, Baba-Ali AR, Drias H (2007) A new generationless parallel evolutionary algorithm for combinatorial optimization. In: 2007 IEEE congress on evolutionary computation. IEEE, pp 4691–4697

  38. Bertels AR, Tauritz DR (2016) Why asynchronous parallel evolution is the future of hyper-heuristics: a cdcl sat solver case study. In: Proceedings of the 2016 on genetic and evolutionary computation conference companion, pp 1359–1365

  39. Li K, Chen R (2021) Batched data-driven evolutionary multi-objective optimization based on manifold interpolation. CoRR arXiv:2109.05639

  40. Emmerich M (2005) Single-and multi-objective evolutionary design optimization assisted by gaussian random field metamodels. dissertation, Universität Dortmund

  41. Javanmard A, Montanari A (2018) Debiasing the lasso: optimal sample size for gaussian designs. Ann Stat 46(6A):2593–2622

    Article  MathSciNet  MATH  Google Scholar 

  42. Wang H, Wu Z, Rahnamayan S (2011) Enhanced opposition-based differential evolution for solving high-dimensional continuous optimization problems. Soft Comput 15(11):2127–2140

    Article  Google Scholar 

  43. Qian H, Hu Y-Q, Yu Y (2016) Derivative-free optimization of high-dimensional non-convex functions by sequential random embeddings. In: IJCAI, pp 1946–1952

  44. Helbing D, Farkas I, Vicsek T (2000) Simulating dynamical features of escape panic. Nature 407(6803):487–490

    Article  Google Scholar 

  45. Zhong J, Cai W (2015) Differential evolution with sensitivity analysis and the powell’s method for crowd model calibration. J Comput Sci 9:26–32

    Article  Google Scholar 

  46. Yi W, Zhong J, Tan S, Cai W, Nan H (2018) Surrogate assisted calibration framework for crowd model calibration. In: Simulation conference

  47. Wilcoxon F (1947) Probability tables for individual comparisons by ranking methods. Biometrics 3(3):119

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

This work is supported by the National Natural Science Foundation of China (Grant No. 62076098), the Guangdong Natural Science Foundation Research Team (Grant No. 2018B030312003), Research cooperation project (Grant No. G2022163008L), and the Program for Guangdong Introducing Innovative and Entrepreneurial Teams (Grant No. 2017ZT07X183).

Author information

Authors and Affiliations

  1. School of Computer Science and Engineering, South China University of Technology, Guangzhou, Guangdong, China

    Yixian Li & Jinghui Zhong

Authors
  1. Yixian Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jinghui Zhong
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jinghui Zhong.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Li, Y., Zhong, J. HAS-EA: a fast parallel surrogate-assisted evolutionary algorithm. Memetic Comp. 15, 103–115 (2023). https://doi.org/10.1007/s12293-022-00376-7

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12293-022-00376-7

Keywords

Search

Navigation