Towards Large-Scale Multiobjective Optimisation with a Hybrid Algorithm for Non-dominated Sorting | SpringerLink
Skip to main content
Springer Nature Link
Log in

Towards Large-Scale Multiobjective Optimisation with a Hybrid Algorithm for Non-dominated Sorting

  • Conference paper
  • First Online:
Parallel Problem Solving from Nature – PPSN XV (PPSN 2018)

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

Included in the following conference series:

Abstract

We present an algorithm for non-dominated sorting that is suitable for large-scale multiobjective optimisation. This algorithm is a hybrid of two previously known algorithms: the divide-and-conquer algorithm initially proposed by Jensen, and the non-dominated tree algorithm proposed by Gustavsson and Syberfeldt.

While possessing the good worst-case asymptotic behaviour of the divide-and-conquer algorithm, the proposed algorithm is also very efficient in practice. In our experimental study it is shown to outperform both of its parents on the majority of problem instances, both sampled uniformly from a hypercube and having a single front, with as large as \(10^6\) points and up to 15 objectives.

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
¥17,985 /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
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • 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

Notes

  1. 1.

    https://github.com/mbuzdalov/non-dominated-sorting/releases/tag/v0.1.

References

  1. Brockhoff, D., Wagner, T.: GECCO 2016 tutorial on evolutionary multiobjective optimization. In: Proceedings of Genetic and Evolutionary Computation Conference Companion, pp. 201–227 (2016)

    Google Scholar 

  2. Buzdalov, M., Shalyto, A.: A provably asymptotically fast version of the generalized jensen algorithm for non-dominated sorting. In: Bartz-Beielstein, T., Branke, J., Filipič, B., Smith, J. (eds.) PPSN 2014. LNCS, vol. 8672, pp. 528–537. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-10762-2_52

    Chapter  Google Scholar 

  3. Coello Coello, C.A., Toscano Pulido, G.: A micro-genetic algorithm for multiobjective optimization. In: Zitzler, E., Thiele, L., Deb, K., Coello Coello, C.A., Corne, D. (eds.) EMO 2001. LNCS, vol. 1993, pp. 126–140. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44719-9_9

    Chapter  MATH  Google Scholar 

  4. Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge (2001)

    MATH  Google Scholar 

  5. Corne, D.W., Jerram, N.R., Knowles, J.D., Oates, M.J.: PESA-II: Region-based selection in evolutionary multiobjective optimization. In: Proceedings of Genetic and Evolutionary Computation Conference, pp. 283–290. Morgan Kaufmann Publishers (2001)

    Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

  8. Fang, H., Wang, Q., Tu, Y.C., Horstemeyer, M.F.: An efficient non-dominated sorting method for evolutionary algorithms. Evol. Comput. 16(3), 355–384 (2008)

    Article  Google Scholar 

  9. Fonseca, C.M., Fleming, P.J.: Nonlinear system identification with multiobjective genetic algorithm. In: Proceedings of the World Congress of the International Federation of Automatic Control, pp. 187–192 (1996)

    Google Scholar 

  10. Fortin, F.A., Grenier, S., Parizeau, M.: Generalizing the improved run-time complexity algorithm for non-dominated sorting. In: Proceedings of Genetic and Evolutionary Computation Conference, pp. 615–622. ACM (2013)

    Google Scholar 

  11. Gustavsson, P., Syberfeldt, A.: A new algorithm using the non-dominated tree to improve non-dominated sorting. Evol. Comput. 26(1), 89–116 (2018)

    Article  Google Scholar 

  12. Jensen, M.T.: Reducing the run-time complexity of multiobjective EAs: the NSGA-II and other algorithms. IEEE Trans. Evol. Comput. 7(5), 503–515 (2003)

    Article  Google Scholar 

  13. Knowles, J.D., Corne, D.W.: Approximating the nondominated front using the pareto archived evolution strategy. Evol. Comput. 8(2), 149–172 (2000)

    Article  Google Scholar 

  14. Kung, H.T., Luccio, F., Preparata, F.P.: On finding the maxima of a set of vectors. J. ACM 22(4), 469–476 (1975)

    Article  MathSciNet  Google Scholar 

  15. Markina, M., Buzdalov, M.: Hybridizing non-dominated sorting algorithms: divide-and-conquer meets best order sort. In: Proceedings of Genetic and Evolutionary Computation Conference Companion, pp. 153–154 (2017)

    Google Scholar 

  16. McClymont, K., Keedwell, E.: Deductive sort and climbing sort: new methods for non-dominated sorting. Evol. Comput. 20(1), 1–26 (2012)

    Article  Google Scholar 

  17. Nekrich, Y.: A fast algorithm for three-dimensional layers of maxima problem. In: Dehne, F., Iacono, J., Sack, J.-R. (eds.) WADS 2011. LNCS, vol. 6844, pp. 607–618. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-22300-6_51

    Chapter  Google Scholar 

  18. Roy, P.C., Islam, M.M., Deb, K.: Best Order Sort: a new algorithm to non-dominated sorting for evolutionary multi-objective optimization. In: Proceedings of Genetic and Evolutionary Computation Conference Companion, pp. 1113–1120 (2016)

    Google Scholar 

  19. Schlünz, E.B.: Multiobjective in-core fuel management optimisation for nuclear research reactors. Ph.D. thesis, Stellenbosch University, December 2016

    Google Scholar 

  20. Srinivas, N., Deb, K.: Multiobjective optimization using nondominated sorting in genetic algorithms. Evol. Comput. 2(3), 221–248 (1994)

    Article  Google Scholar 

  21. Stevens, J., Smith, K., Rempe, K., Downar, T.: Optimization of pressurized water reactor shuffling by simulated annealing with heuristics. Nucl. Sci. Eng. 121(1), 67–88 (1995)

    Article  Google Scholar 

  22. Wang, H., Yao, X.: Corner sort for pareto-based many-objective optimization. IEEE Trans. Cybern. 44(1), 92–102 (2014)

    Article  Google Scholar 

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

    Article  Google Scholar 

  24. Zhang, X., Tian, Y., Cheng, R., Jin, Y.: An efficient approach to nondominated sorting for evolutionary multiobjective optimization. IEEE Trans. Evol. Comput. 19(2), 201–213 (2015)

    Article  Google Scholar 

  25. Zitzler, E., Künzli, S.: Indicator-based selection in multiobjective search. In: Yao, X., Burke, E.K., Lozano, J.A., Smith, J., Merelo-Guervós, J.J., Bullinaria, J.A., Rowe, J.E., Tiňo, P., Kabán, A., Schwefel, H.-P. (eds.) PPSN 2004. LNCS, vol. 3242, pp. 832–842. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-30217-9_84

    Chapter  Google Scholar 

  26. Zitzler, E., Laumanns, M., Thiele, L.: SPEA2: improving the strength pareto evolutionary algorithm for multiobjective optimization. In: Proceedings of the EUROGEN 2001 Conference, pp. 95–100 (2001)

    Google Scholar 

Download references

Acknowledgment

We would like to acknowledge the support of this research by the Russian Scientific Foundation, agreement No. 17-71-20178.

Author information

Authors and Affiliations

  1. ITMO University, 49 Kronverkskiy prosp., Saint-Petersburg, 197101, Russia

    Margarita Markina & Maxim Buzdalov

Authors
  1. Margarita Markina
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Maxim Buzdalov
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Maxim Buzdalov .

Editor information

Editors and Affiliations

  1. Inria Saclay, Palaiseau, France

    Anne Auger

  2. University of Coimbra, Coimbra, Portugal

    Carlos M. Fonseca

  3. University of Coimbra, Coimbra, Portugal

    Nuno Lourenço

  4. University of Coimbra, Coimbra, Portugal

    Penousal Machado

  5. University of Coimbra, Coimbra, Portugal

    Luís Paquete

  6. Colorado State University, Fort Collins, Colorado, USA

    Darrell Whitley

Rights and permissions

Reprints and permissions

Copyright information

© 2018 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Markina, M., Buzdalov, M. (2018). Towards Large-Scale Multiobjective Optimisation with a Hybrid Algorithm for Non-dominated Sorting. In: Auger, A., Fonseca, C., Lourenço, N., Machado, P., Paquete, L., Whitley, D. (eds) Parallel Problem Solving from Nature – PPSN XV. PPSN 2018. Lecture Notes in Computer Science(), vol 11101. Springer, Cham. https://doi.org/10.1007/978-3-319-99253-2_28

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-99253-2_28

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-99252-5

  • Online ISBN: 978-3-319-99253-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation