Skip to main content
Springer Nature Link
Log in

A Study on Efficient Asynchronous Parallel Multi-objective Evolutionary Algorithm with Waiting Time Limitation

  • Conference paper
  • First Online:
Theory and Practice of Natural Computing (TPNC 2020)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 12494))

Abstract

This paper attempts a new scheme of a semi-asynchronous parallel evolutionary algorithm (PEA), named time-limitation asynchronous PEA (TLAPEA). TLAPEA takes a balance between the search capability and the computational efficiency of PEA by synchronizing the solution evaluations within a particular waiting time before generating solutions. To reduce the idling time to wait for the slower evaluation of solutions, TLAPEA waits for a while for other solutions after the evaluation of a solution completes. The waiting time is decided from the average evaluation time of solutions and a new asynchrony parameter. This paper conducts an experiment to compare the proposed method with the full synchronous and asynchronous parallel evolutionary algorithm on multi-objective optimization problems. The experiment uses a state-of-the-art indicator-based multi-objective evolutionary algorithm, \(I_{\mathrm {SDE}}+\). Our experiment examines several variances of evaluation time on a parallel computing simulation. The experimental result reveals that TLAPEA with shorter time limitation obtains a high quality of solutions quicker than the synchronous and asynchronous ones regardless of the variance of the evaluation time.

This work was supported by Japan Society for the Promotion of Science Grant-in-Aid for Young Scientists Grant Number JP19K20362.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
CHF34.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

Chapter
CHF 24.95
Price includes VAT (Switzerland)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
CHF 47.00
Price excludes VAT (Switzerland)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
CHF 59.00
Price excludes VAT (Switzerland)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Chang, J.F., Chu, S.C., Roddick, J.F., Pan, J.S.: A parallel particle swarm optimization algorithm with communication strategies. J. Inf. Sci. Eng. 21(4), 809–818 (2005)

    Google Scholar 

  2. Cheng, R., He, C., Jin, Y., Yao, X.: Model-based evolutionary algorithms: a short survey. Complex Intell. Syst. 4(4), 283–292 (2018). https://doi.org/10.1007/s40747-018-0080-1

    Article  Google Scholar 

  3. Chipperfield, A., Fleming, P.: Parallel Genetic Algorithms, pp. 1118–1143. McGraw-Hill, New York (1996)

    Google Scholar 

  4. Deb, K., Agrawal, R.B.: Simulated binary crossover for continuous search space. Complex Syst. 9, 115–148 (1995). citeseer.ist.psu.edu/deb95simulated.html

  5. Deb, K., Goyal, M.: A combined genetic adaptive search (GeneAS) for engineering design. Comput. Sci. Inf. 26, 30–45 (1996)

    Google Scholar 

  6. Durillo, J.J., Zhang, Q., Nebro, A.J., Alba, E.: Distribution of computational effort in parallel MOEA/D. In: Coello, C.A.C. (ed.) LION 2011. LNCS, vol. 6683, pp. 488–502. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25566-3_38

    Chapter  Google Scholar 

  7. Goldberg, D.E.: Genetic Algorithms in Search, Optimization and Machine Learning, 1st edn. Addison-Wesley Longman Publishing Co., Inc., Boston (1989)

    Google Scholar 

  8. Harada, T., Takadama, K.: Asynchronous evaluation based genetic programming: comparison of asynchronous and synchronous evaluation and its analysis. In: Krawiec, K., Moraglio, A., Hu, T., Etaner-Uyar, A.Ş., Hu, B. (eds.) EuroGP 2013. LNCS, vol. 7831, pp. 241–252. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-37207-0_21

    Chapter  Google Scholar 

  9. Harada, T., Takadama, K.: Performance comparison of parallel asynchronous multi-objective evolutionary algorithm with different asynchrony. In: 2017 IEEE Congress on Evolutionary Computation (CEC), pp. 1215–1222, June 2017. https://doi.org/10.1109/CEC.2017.7969444

  10. Harada, T., Takadama, K.: Analysis of semi-asynchronous multi-objective evolutionary algorithm with different asynchronies. Soft Comput. 24(4), 2917–2939 (2020). https://doi.org/10.1007/s00500-019-04071-7

  11. Huband, S., Barone, L., While, L., Hingston, P.: A scalable multi-objective test problem toolkit. In: Coello Coello, C.A., Hernández Aguirre, A., Zitzler, E. (eds.) EMO 2005. LNCS, vol. 3410, pp. 280–295. Springer, Heidelberg (2005). https://doi.org/10.1007/978-3-540-31880-4_20

    Chapter  MATH  Google Scholar 

  12. Jin, Y.: Surrogate-assisted evolutionary computation: recent advances and future challenges. Swarm Evol. Comput. 1(2), 61–70 (2011). https://doi.org/10.1016/j.swevo.2011.05.001, http://www.sciencedirect.com/science/article/pii/S2210650211000198

  13. Koza, J.: Genetic Programming On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge (1992)

    Google Scholar 

  14. Kruskal, W.H., Wallis, W.A.: Use of ranks in one-criterion variance analysis. J. Am. Stat. Assoc. 47(260), 583–621 (1952). https://doi.org/10.2307/2280779

  15. Mann, H.B., Whitney, D.R.: On a test of whether one of two random variables is stochastically larger than the other. Ann. Math. Stat. 18(1), 50–60 (1947). https://doi.org/10.1214/aoms/1177730491

  16. Nebro, A.J., Durillo, J.J., Vergne, M.: Redesigning the jMetal multi-objective optimization framework. In: Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation, pp. 1093–1100. GECCO Companion 2015. ACM, New York (2015). https://doi.org/10.1145/2739482.2768462, https://doi.acm.org/10.1145/2739482.2768462

  17. Pamulapati, T., Mallipeddi, R., Suganthan, P.N.: \(I_{\rm SDE}\) +—an indicator for multi and many-objective optimization. IEEE Trans. Evol. Comput. 23(2), 346–352 (2019). https://doi.org/10.1109/TEVC.2018.2848921

    Article  Google Scholar 

  18. Scott, E.O., De Jong, K.A.: 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. GECCO Companion 2015. ACM, New York (2015). https://doi.org/10.1145/2739482.2768482, https://doi.acm.org/10.1145/2739482.2768482

  19. Scott, E.O., De Jong, K.A.: Understanding simple asynchronous evolutionary algorithms. In: Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII, pp. 85–98. FOGA 2015. ACM, New York (2015). https://doi.org/10.1145/2725494.2725509, https://doi.acm.org/10.1145/2725494.2725509

  20. Tasoulis, D.K., Pavlidis, N.G., Plagianakos, V.P., Vrahatis, M.N.: Parallel differential evolution. In: Proceedings of the 2004 Congress on Evolutionary Computation (IEEE Cat. No. 04TH8753), vol. 2, pp. 2023–2029, June 2004. https://doi.org/10.1109/CEC.2004.1331145

  21. Zitzler, E., Thiele, L.: Multiobjective optimization using evolutionary algorithms—a comparative case study. In: Eiben, A.E., Bäck, T., Schoenauer, M., Schwefel, H.-P. (eds.) PPSN 1998. LNCS, vol. 1498, pp. 292–301. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0056872

    Chapter  Google Scholar 

  22. Zăvoianu, A.C., Lughofer, E., Koppelstätter, W., Weidenholzer, G., Amrhein, W., Klement, E.P.: Performance comparison of generational and steady-state asynchronous multi-objective evolutionary algorithms for computationally-intensive problems. Knowl. Based Syst. 87(C), 47–60 (2015). https://doi.org/10.1016/j.knosys.2015.05.029

Download references

Author information

Authors and Affiliations

  1. Faculty of System Design, Tokyo Metropolitan University, Hino, Japan

    Tomohiro Harada

Authors
  1. Tomohiro Harada
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Tomohiro Harada .

Editor information

Editors and Affiliations

  1. Rovira i Virgili University, Tarragona, Spain

    Carlos Martín-Vide

  2. University of Extremadura, Cáceres, Spain

    Miguel A. Vega-Rodríguez

  3. Chung Yuan Christian University, Taoyuan, Taiwan

    Miin-Shen Yang

Rights and permissions

Reprints and permissions

Copyright information

© 2020 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Harada, T. (2020). A Study on Efficient Asynchronous Parallel Multi-objective Evolutionary Algorithm with Waiting Time Limitation. In: Martín-Vide, C., Vega-Rodríguez, M.A., Yang, MS. (eds) Theory and Practice of Natural Computing. TPNC 2020. Lecture Notes in Computer Science(), vol 12494. Springer, Cham. https://doi.org/10.1007/978-3-030-63000-3_10

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-63000-3_10

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-62999-1

  • Online ISBN: 978-3-030-63000-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation

  NODES
INTERN 1
Note 2