Skip to main content
SpringerLink
Log in

Comparison of Reference- and Hypervolume-Based MOEA on Solving Many-Objective Optimization Problems

  • Conference paper
  • First Online:
Book cover Evolutionary Multi-Criterion Optimization (EMO 2019)

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

Included in the following conference series:

Abstract

Hypervolume-based algorithms are not widely used for solving many-objective optimization problems due to the bottleneck of hypervolume computation. Approximation methods can alleviate the problem and are discussed and tested in this work. Several MOEAs are considered, but after pre-experimental tests, only two variants of SMS-EMOA are considered further. These algorithms are compared to NSGA-III, a reference-based algorithm. The results show that SMS-EMOA with hypervolume approximation is viable for many-objective optimization problems and is faster in convergence towards the Pareto-front.

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

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 84.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 109.99
Price excludes VAT (USA)
  • 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

References

  1. Agrawal, R.B., Deb, K.: Simulated binary crossover for continuous search space. Complex Syst. 9(2), 115–148 (1995)

    MathSciNet  MATH  Google Scholar 

  2. Bader, J., Zitzler, E.: Hype: an algorithm for fast hypervolume-based many-objective optimization. Evol. Comput. 19(1), 45–76 (2011)

    Article  Google Scholar 

  3. Beume, N., Naujoks, B., Emmerich, M.: SMS-EMOA: multiobjective selection based on dominated hypervolume. Eur. J. Oper. Res. 181(3), 1653–1669 (2007)

    Article  Google Scholar 

  4. Biscani, F., Izzo, D.: esa/pagmo2: pagmo 2.8 (2018). https://doi.org/10.5281/zenodo.1311209

  5. Bringmann, K., Friedrich, T.: Approximating the volume of unions and intersections of high-dimensional geometric objects. Comput. Geom. 43(6), 601–610 (2010)

    Article  MathSciNet  Google Scholar 

  6. Bringmann, K., Friedrich, T.: Approximating the least hypervolume contributor: NP-hard in general, but fast in practice. Theor. Comput. Sci. 425, 104–116 (2012)

    Article  MathSciNet  Google Scholar 

  7. Deb, K., Jain, H.: An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: solving problems with box constraints. Trans. Evol. Comput. 18(4), 577–601 (2014)

    Article  Google Scholar 

  8. Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A fast and elitist multiobjective genetic algorithm: NSGA-II. Trans. Evol. Comput. 6(2), 182–197 (2002)

    Article  Google Scholar 

  9. Deb, K., Thiele, L., Laumanns, M., Zitzler, E.: Scalable multi-objective optimization test problems. In: Congress on Evolutionary Computation (CEC), pp. 825–830. IEEE Press, Piscataway (2002)

    Google Scholar 

  10. Emmerich, M., Beume, N., Naujoks, B.: An EMO algorithm using the hypervolume measure as selection criterion. In: Coello Coello, C.A., Hernández Aguirre, A., Zitzler, E. (eds.) EMO 2005. LNCS, vol. 3410, pp. 62–76. Springer, Heidelberg (2005). https://doi.org/10.1007/978-3-540-31880-4_5

    Chapter  MATH  Google Scholar 

  11. Glasmachers, T., Naujoks, B., Rudolph, G.: Start small, grow big? Saving multi-objective function evaluations. In: Bartz-Beielstein, T., Branke, J., Filipič, B., Smith, J. (eds.) PPSN 2014. LNCS, vol. 8672, pp. 579–588. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-10762-2_57

    Chapter  Google Scholar 

  12. Huband, S., Hingston, P., Barone, L., While, L.: A review of multiobjective test problems and a scalable test problem toolkit. Trans. Evol. Comput. 10(5), 477–506 (2006)

    Article  Google Scholar 

  13. Hughes, E.J.: Multiple single objective Pareto sampling. In: Congress on Evolutionary Computation (CEC), vol. 4, pp. 2678–2684. IEEE Press, Piscataway (2003)

    Google Scholar 

  14. Hughes, E.J.: MSOPS-II: a general-purpose many-objective optimiser. In: Congress on Evolutionary Computation (CEC), pp. 3944–3951. IEEE Press, Piscataway (2007)

    Google Scholar 

  15. Igel, C., Hansen, N., Roth, S.: Covariance matrix adaptation for multi-objective optimization. Evol. Comput. 15(1), 1–28 (2007)

    Article  Google Scholar 

  16. Ishibuchi, H., Tsukamoto, N., Nojima, Y.: Evolutionary many-objective optimization: a short review. In: Congress on Evolutionary Computation (CEC), pp. 2419–2426. IEEE Press, Piscataway (2008)

    Google Scholar 

  17. Ishibuchi, H., Tsukamoto, N., Sakane, Y., Nojima, Y.: Indicator-based evolutionary algorithm with hypervolume approximation by achievement scalarizing functions. In: Genetic and Evolutionary Computation (GECCO), pp. 527–534. ACM, New York (2010)

    Google Scholar 

  18. Jain, H., Deb, K.: An improved adaptive approach for elitist nondominated sorting genetic algorithm for many-objective optimization. In: Purshouse, R.C., Fleming, P.J., Fonseca, C.M., Greco, S., Shaw, J. (eds.) EMO 2013. LNCS, vol. 7811, pp. 307–321. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-37140-0_25

    Chapter  Google Scholar 

  19. Kramer, O.: A review of constraint-handling techniques for evolution strategies. Appl. Comput. Intell. Soft Comput. 3:1–3:19 (2010)

    Google Scholar 

  20. Li, M., Yang, S., Liu, X., Shen, R.: A comparative study on evolutionary algorithms for many-objective optimization. In: Purshouse, R.C., Fleming, P.J., Fonseca, C.M., Greco, S., Shaw, J. (eds.) EMO 2013. LNCS, vol. 7811, pp. 261–275. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-37140-0_22

    Chapter  Google Scholar 

  21. Qi, Y., Ma, X., Liu, F., Jiao, L., Sun, J., Wu, J.: MOEA/D with adaptive weight adjustment. Evol. Comput. 22(2), 231–264 (2014)

    Article  Google Scholar 

  22. Tang, W., Liu, H., Chen, L.: A fast approximate hypervolume calculation method by a novel decomposition strategy. In: Huang, D.-S., Bevilacqua, V., Premaratne, P., Gupta, P. (eds.) ICIC 2017. LNCS, vol. 10361, pp. 14–25. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63309-1_2

    Chapter  Google Scholar 

  23. Voß, T., Hansen, N., Igel, C.: Improved step size adaptation for the MO-CMA-ES. In: Genetic and Evolutionary Computation (GECCO), pp. 487–494. ACM, New York (2010)

    Google Scholar 

  24. Wagner, T., Beume, N., Naujoks, B.: Pareto-, aggregation-, and indicator-based methods in many-objective optimization. In: Obayashi, S., Deb, K., Poloni, C., Hiroyasu, T., Murata, T. (eds.) EMO 2007. LNCS, vol. 4403, pp. 742–756. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-70928-2_56

    Chapter  Google Scholar 

  25. Zhang, Q., Li, H.: MOEA/D: a multiobjective evolutionary algorithm based on decomposition. Trans. Evol. Comput. 11(6), 712–731 (2007)

    Article  Google Scholar 

  26. Zitzler, E., Brockhoff, D., Thiele, L.: The hypervolume indicator revisited: on the design of pareto-compliant indicators via weighted integration. In: Obayashi, S., Deb, K., Poloni, C., Hiroyasu, T., Murata, T. (eds.) EMO 2007. LNCS, vol. 4403, pp. 862–876. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-70928-2_64

    Chapter  Google Scholar 

Download references

Acknowledgments

This work is funded by the European Commission’s H2020 programme through the UTOPIAE Marie Curie Innovative Training Network, H2020-MSCA-ITN-2016, under Grant Agreement No. 722734 as well as through the Twinning project SYNERGY under Grant Agreement No. 692286.

Author information

Authors and Affiliations

  1. Institute for Data Science, Engineering and Analytics, TH-Köln - University of Applied Sciences, Cologne, Germany

    Dani Irawan & Boris Naujoks

Authors
  1. Dani Irawan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Boris Naujoks
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Dani Irawan .

Editor information

Editors and Affiliations

  1. Michigan State University, East Lansing, MI, USA

    Kalyanmoy Deb

  2. Michigan State University, East Lansing, MI, USA

    Erik Goodman

  3. CINVESTAV-IPN, Mexico, Mexico

    Carlos A. Coello Coello

  4. University of Wuppertal, Wuppertal, Germany

    Kathrin Klamroth

  5. University of Jyvaskyla, Jyväskylä, Finland

    Kaisa Miettinen

  6. Otto von Guericke University Magdeburg, Magdeburg, Germany

    Sanaz Mostaghim

  7. Cornell University, Ithaca, NY, USA

    Patrick Reed

Rights and permissions

Reprints and permissions

Copyright information

© 2019 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Irawan, D., Naujoks, B. (2019). Comparison of Reference- and Hypervolume-Based MOEA on Solving Many-Objective Optimization Problems. In: Deb, K., et al. Evolutionary Multi-Criterion Optimization. EMO 2019. Lecture Notes in Computer Science(), vol 11411. Springer, Cham. https://doi.org/10.1007/978-3-030-12598-1_22

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-12598-1_22

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-12597-4

  • Online ISBN: 978-3-030-12598-1

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation