nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

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

verfasst von : Margarita Markina, Maxim Buzdalov

Erschienen in: Parallel Problem Solving from Nature – PPSN XV

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Towards a More General Many-objective Evolutionary Optimizer

Nächstes Kapitel Tree-Structured Decomposition and Adaptation in MOEA/D

https://github.com/mbuzdalov/non-dominated-sorting/releases/tag/v0.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)

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_52CrossRef

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_9CrossRefMATH

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

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)

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)CrossRef

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)CrossRef

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)CrossRef

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)

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)

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)CrossRef

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)CrossRef

13.

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

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)MathSciNetCrossRef

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)

16.

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

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_51CrossRef

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)

19.

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

20.

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

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)CrossRef

22.

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

23.

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

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)CrossRef

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_84CrossRef

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)

Titel: Towards Large-Scale Multiobjective Optimisation with a Hybrid Algorithm for Non-dominated Sorting
verfasst von: Margarita Markina
Maxim Buzdalov
Verlag: Springer International Publishing
Buch: Parallel Problem Solving from Nature – PPSN XV
Print ISBN: 978-3-319-99252-5

Electronic ISBN: 978-3-319-99253-2

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-99253-2_28

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner