Skip to main content
Erschienen in: Evolutionary Intelligence 4/2009

01.12.2009 | Special Issue

Adaptive ε-Ranking on many-objective problems

verfasst von: Hernán Aguirre, Kiyoshi Tanaka

Erschienen in: Evolutionary Intelligence | Ausgabe 4/2009

Einloggen

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

search-config
loading …

Abstract

This work proposes Adaptive ε-Ranking to enhance Pareto based selection, aiming to develop effective many-objective evolutionary optimization algorithms. ε-Ranking fine grains ranking of solutions after they have been ranked by Pareto dominance, using a randomized sampling procedure combined with ε-dominance to favor a good distribution of the samples. In the proposed method, sampled solutions keep their initial rank and solutions located within the virtually expanded ε-dominance regions of the sampled solutions are demoted to an inferior rank. The parameter ε that determines the expanded regions of dominance of the sampled solutions is adapted at each generation so that the number of best-ranked solutions is kept close to a desired number that is expressed as a fraction of the population size. We enhance NSGA-II with the proposed method and analyze its performance on MNK-Landscapes, showing that the adaptive method works effectively and that compared to NSGA-II convergence and diversity of solutions can be improved remarkably on MNK-Landscapes with 3 ≤ M ≤ 10 objectives. Also, we compare the performance of Adaptive ε-Ranking with two representative many-objective evolutionary algorithms on DTLZ continuous functions. Results on DTLZ functions with 3 ≤ M ≤ 10 objectives suggest that the three many-objective approaches emphasize different areas of objective space and could be used as complementary strategies to produce a better approximation of the Pareto front.

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!

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!

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!

Literatur
1.
Zurück zum Zitat Deb K (2001) Multi-objective optimization using evolutionary algorithms. Wiley, ChichesterMATH Deb K (2001) Multi-objective optimization using evolutionary algorithms. Wiley, ChichesterMATH
2.
Zurück zum Zitat Coello C, Van Veldhuizen D, Lamont G (2002) Evolutionary algorithms for solving multi-objective problems. Kluwer, BostonMATH Coello C, Van Veldhuizen D, Lamont G (2002) Evolutionary algorithms for solving multi-objective problems. Kluwer, BostonMATH
3.
Zurück zum Zitat Purshouse RC, Fleming PJ (2003, April) Conflict, harmony, and independence: relationships in evolutionary multi-criterion optimization. In: Proceedings of 2nd international conference on evolutionary multi-criterion optimization, vol 2632. LNCS (Springer), pp16–30 Purshouse RC, Fleming PJ (2003, April) Conflict, harmony, and independence: relationships in evolutionary multi-criterion optimization. In: Proceedings of 2nd international conference on evolutionary multi-criterion optimization, vol 2632. LNCS (Springer), pp16–30
4.
Zurück zum Zitat Aguirre H, Tanaka K (2004) Insights on properties of multi-objective MNK-landscapes. In: Proceedings of 2004 IEEE congress on evolutionary computation. IEEE Service Center, pp.196–203 Aguirre H, Tanaka K (2004) Insights on properties of multi-objective MNK-landscapes. In: Proceedings of 2004 IEEE congress on evolutionary computation. IEEE Service Center, pp.196–203
5.
Zurück zum Zitat Zitzler E, Kunzli S (2004) Indicator based selection in multi-objective search. In: Proceedings of conference on parallel problem solving from nature (PPSN VIII). Springer, pp. 832–842 Zitzler E, Kunzli S (2004) Indicator based selection in multi-objective search. In: Proceedings of conference on parallel problem solving from nature (PPSN VIII). Springer, pp. 832–842
6.
Zurück zum Zitat Aguirre H, Tanaka K (2005) Selection, drift, recombination, and mutation in multi-objective evolutionary algorithms on scalable MNK-landscapes. In: Proceedings of 3rd international conference on evolutionary multi-criterion optimization, vol. 3410. LNCS (Springer), pp 355–369 Aguirre H, Tanaka K (2005) Selection, drift, recombination, and mutation in multi-objective evolutionary algorithms on scalable MNK-landscapes. In: Proceedings of 3rd international conference on evolutionary multi-criterion optimization, vol. 3410. LNCS (Springer), pp 355–369
7.
Zurück zum Zitat Hughes EJ (2005, September) evolutionary many-objective optimisation: many once or one many? In: Proceedings of 2005 IEEE congress on evolutionary computation, vol 1. IEEE Service Center, pp 222–227 Hughes EJ (2005, September) evolutionary many-objective optimisation: many once or one many? In: Proceedings of 2005 IEEE congress on evolutionary computation, vol 1. IEEE Service Center, pp 222–227
8.
Zurück zum Zitat Aguirre H, Tanaka K (2007, September) Working principles, behavior, and performance of MOEAs on MNK-landscapes. Eur J Oper Res Elsevier 181(3):1670–1690MATHCrossRef Aguirre H, Tanaka K (2007, September) Working principles, behavior, and performance of MOEAs on MNK-landscapes. Eur J Oper Res Elsevier 181(3):1670–1690MATHCrossRef
9.
Zurück zum Zitat Emmerich M, Beume N., Naujoks B (2005) An EMO algorithm using the hypervolume measure as selection criterion. In: Proceedings of 3rd international conference on evolutionary multi-criterion optimization, vol 3410, LNCS (Springer), pp 62–76 Emmerich M, Beume N., Naujoks B (2005) An EMO algorithm using the hypervolume measure as selection criterion. In: Proceedings of 3rd international conference on evolutionary multi-criterion optimization, vol 3410, LNCS (Springer), pp 62–76
10.
Zurück zum Zitat Deb K, Saxena K (2006) Searching for pareto-optimal solutions through dimensionality reduction for certain large-dimensional multi-objective optimization problems. In: Proceedings of 2006 IEEE congress on evolutionary computation (CEC 2006), pp 3353–3360 Deb K, Saxena K (2006) Searching for pareto-optimal solutions through dimensionality reduction for certain large-dimensional multi-objective optimization problems. In: Proceedings of 2006 IEEE congress on evolutionary computation (CEC 2006), pp 3353–3360
11.
Zurück zum Zitat Deb K, Sundar J (2006) Preference point based multi-objective optimization using evolutionary algorithms. In: Proceedings of 2006 genetic and evolutionary computation conference (GECCO 2006), pp 635–642 Deb K, Sundar J (2006) Preference point based multi-objective optimization using evolutionary algorithms. In: Proceedings of 2006 genetic and evolutionary computation conference (GECCO 2006), pp 635–642
12.
Zurück zum Zitat Corne D, Knowles J (2007) Techniques for highly multi-objective optimization: some non-dominated points are better than others. In: Proceedings of 2007 genetic and evolutionary computation conference (GECCO 2007), pp 773–780 Corne D, Knowles J (2007) Techniques for highly multi-objective optimization: some non-dominated points are better than others. In: Proceedings of 2007 genetic and evolutionary computation conference (GECCO 2007), pp 773–780
13.
Zurück zum Zitat Kukkonen S, Lampinen J (2007) Ranking-dominance and many objective optimization. In: Proceedings of 2007 IEEE congress on evolutionary computation (CEC 2007), pp 3983–3990 Kukkonen S, Lampinen J (2007) Ranking-dominance and many objective optimization. In: Proceedings of 2007 IEEE congress on evolutionary computation (CEC 2007), pp 3983–3990
14.
Zurück zum Zitat Ishibuchi H, Tsukamoto N, Nojima Y (2007) Iterative approach to indicator-based multi-objective optimization. In: Proceedings of 2007 IEEE congress on evolutionary computation (CEC 2007), pp 3697–3704 Ishibuchi H, Tsukamoto N, Nojima Y (2007) Iterative approach to indicator-based multi-objective optimization. In: Proceedings of 2007 IEEE congress on evolutionary computation (CEC 2007), pp 3697–3704
15.
Zurück zum Zitat Ishibuchi H, Nojima Y (2007) Optimization of scalarizing functions through evolutionary multi-objective optimization. In: Proceedings of 4th international conference on evolutionary multi-criterion optimization (EMO 2007), vol 4403. LNCS (Springer), pp 51–65 Ishibuchi H, Nojima Y (2007) Optimization of scalarizing functions through evolutionary multi-objective optimization. In: Proceedings of 4th international conference on evolutionary multi-criterion optimization (EMO 2007), vol 4403. LNCS (Springer), pp 51–65
16.
Zurück zum Zitat Brockhoff D, Zitzler E (2006) Are all objectives necessary? On dimensionality reduction in evolutionary multi-objective optimization. In: Parallel problem solving from nature, PPSN IX, vol 4193. LNCS (Springer), pp 533–542 Brockhoff D, Zitzler E (2006) Are all objectives necessary? On dimensionality reduction in evolutionary multi-objective optimization. In: Parallel problem solving from nature, PPSN IX, vol 4193. LNCS (Springer), pp 533–542
17.
Zurück zum Zitat Sulflow A, Drechsler N, Drechsler R (2007) Robust multi-objective optimization in high dimensional spaces. In: Proceedings of 4th international conference on evolutionary multi-criterion optimization, vol 4403. LNCS (Springer), pp 715–726 Sulflow A, Drechsler N, Drechsler R (2007) Robust multi-objective optimization in high dimensional spaces. In: Proceedings of 4th international conference on evolutionary multi-criterion optimization, vol 4403. LNCS (Springer), pp 715–726
18.
Zurück zum Zitat Koppen M, Yoshida K (2007) Substitute distance assignments in NSGA-II for handling many-objective optimization problems. In: Proceedings of 4th international conference on evolutionary multi-criterion optimzation, vol 4403. LNCS (Springer), pp 727–741 Koppen M, Yoshida K (2007) Substitute distance assignments in NSGA-II for handling many-objective optimization problems. In: Proceedings of 4th international conference on evolutionary multi-criterion optimzation, vol 4403. LNCS (Springer), pp 727–741
19.
Zurück zum Zitat Wagner T, Beume N, Naujoks B (2007) Pareto-, aggregation, and indicator-based methods in many-objective optimization. In: Proceedings of 4th international conference on evolutionary multi-criterion optimization, vol 4403. LNCS (Springer), pp 742–756 Wagner T, Beume N, Naujoks B (2007) Pareto-, aggregation, and indicator-based methods in many-objective optimization. In: Proceedings of 4th international conference on evolutionary multi-criterion optimization, vol 4403. LNCS (Springer), pp 742–756
20.
Zurück zum Zitat Hughes EJ (2003) Multiple single objective pareto sampling. In: Proceedings of 2003 IEEE congress on evolutionary computation. IEEE Service Center Hughes EJ (2003) Multiple single objective pareto sampling. In: Proceedings of 2003 IEEE congress on evolutionary computation. IEEE Service Center
21.
Zurück zum Zitat Deb K, Agrawal S, Pratap A, Meyarivan T (2000) A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II. KanGAL report 200001 Deb K, Agrawal S, Pratap A, Meyarivan T (2000) A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II. KanGAL report 200001
22.
Zurück zum Zitat Aguirre H, Tanaka K (2008) Robust optimization by ε-Ranking on high dimensional objective spaces. In: Proceedings of 7th international conference on simulated evolution and learning, vol 5361. LNCS (Springer), pp 421–431 Aguirre H, Tanaka K (2008) Robust optimization by ε-Ranking on high dimensional objective spaces. In: Proceedings of 7th international conference on simulated evolution and learning, vol 5361. LNCS (Springer), pp 421–431
23.
Zurück zum Zitat Ishibuchi H, Tsukamoto N, Nojima Y (2008) Evolutionary many-objective optimization: a short review. In: Proceedings of IEEE congress on evolutionary computation (CEC 2008). IEEE Press, pp 2424–2431 Ishibuchi H, Tsukamoto N, Nojima Y (2008) Evolutionary many-objective optimization: a short review. In: Proceedings of IEEE congress on evolutionary computation (CEC 2008). IEEE Press, pp 2424–2431
24.
Zurück zum Zitat Yu PL (1974) Cone convexity, cone extreme points, and nondominated solutions in decision problems with multi-objectives. J Optim Theory Appl 14(3):319–377MATHCrossRef Yu PL (1974) Cone convexity, cone extreme points, and nondominated solutions in decision problems with multi-objectives. J Optim Theory Appl 14(3):319–377MATHCrossRef
25.
Zurück zum Zitat Laumanns M, Thiele L, Deb K, Zitzler E (2002) Combining convergence and diversity in evolutionary multi-objective optimization. Evol Comput 10(3):263–282 (Fall)CrossRef Laumanns M, Thiele L, Deb K, Zitzler E (2002) Combining convergence and diversity in evolutionary multi-objective optimization. Evol Comput 10(3):263–282 (Fall)CrossRef
26.
Zurück zum Zitat Kauffman SA (1993) The origins of order: self-organization and selection in evolution. Oxford University Press, New York Kauffman SA (1993) The origins of order: self-organization and selection in evolution. Oxford University Press, New York
27.
Zurück zum Zitat Deb K, Thiele L, Laumanns M, Zitzler E (2002) Scalable multi-objective optimization test problems. In: Proceedings of 2002 congress on evolutionary computation. IEEE Service Center, pp 825–830 Deb K, Thiele L, Laumanns M, Zitzler E (2002) Scalable multi-objective optimization test problems. In: Proceedings of 2002 congress on evolutionary computation. IEEE Service Center, pp 825–830
28.
Zurück zum Zitat Zitzler E (1999) Evolutionary algorithms for multiobjective optimization: methods and applications. PhD thesis, Swiss Federal Institute of Technology, Zurich Zitzler E (1999) Evolutionary algorithms for multiobjective optimization: methods and applications. PhD thesis, Swiss Federal Institute of Technology, Zurich
29.
Zurück zum Zitat Knowles J, Corne D (2002) On metrics for comparing non-dominated sets. In: Proceedings of 2002 congress on evolutionary computation. IEEE Press, pp 711–716 Knowles J, Corne D (2002) On metrics for comparing non-dominated sets. In: Proceedings of 2002 congress on evolutionary computation. IEEE Press, pp 711–716
30.
Zurück zum Zitat Fleischer M (2003) The measure of pareto optima: applications to multi-objective metaheuristics. In: 2nd International conference on evolutionary multi-criterion optimization, Lecture Notes in Computer Science, vol 2632. Springer, pp 519–533 Fleischer M (2003) The measure of pareto optima: applications to multi-objective metaheuristics. In: 2nd International conference on evolutionary multi-criterion optimization, Lecture Notes in Computer Science, vol 2632. Springer, pp 519–533
31.
Zurück zum Zitat Fonseca C, Paquete L, López-Ibáñez M (2006) An improved dimension-sweep algorithm for the hypervolume indicator. In: Proceedings of 2006 IEEE congress on evolutionary computation, IEEE Service Center, pp 1157–1163 Fonseca C, Paquete L, López-Ibáñez M (2006) An improved dimension-sweep algorithm for the hypervolume indicator. In: Proceedings of 2006 IEEE congress on evolutionary computation, IEEE Service Center, pp 1157–1163
32.
Zurück zum Zitat Salomon R (1996) Re-evaluating genetic algorithm performance under coordinate rotation of benchmark functions. A survey of some theoretical and practical aspects of genetic algorithms, vol 39, no.3. Byosystems, Elsevier, pp 263–278 Salomon R (1996) Re-evaluating genetic algorithm performance under coordinate rotation of benchmark functions. A survey of some theoretical and practical aspects of genetic algorithms, vol 39, no.3. Byosystems, Elsevier, pp 263–278
33.
Zurück zum Zitat Aguirre H, Tanaka K (2003) Genetic algorithms on NK-landscapes: effects of selection, drift, mutation, and recombination. In: Proceedings of 3rd European workshop on evolutionary computation in combinatorial optimization (EvoCOP 2003), vol 2611. LNCS (Springer), pp 131–142 Aguirre H, Tanaka K (2003) Genetic algorithms on NK-landscapes: effects of selection, drift, mutation, and recombination. In: Proceedings of 3rd European workshop on evolutionary computation in combinatorial optimization (EvoCOP 2003), vol 2611. LNCS (Springer), pp 131–142
34.
Zurück zum Zitat Iorio A.W., Li X (2004) Solving rotated multi-objective optimization problems using differential evolution. In: Proceedings of 17th Australian joint conference on artificial intelligence 2004, vol 3339. LNAI (Springer), pp 861–872 Iorio A.W., Li X (2004) Solving rotated multi-objective optimization problems using differential evolution. In: Proceedings of 17th Australian joint conference on artificial intelligence 2004, vol 3339. LNAI (Springer), pp 861–872
35.
Zurück zum Zitat Bleuler S, Laumanns M, Thiele L, Zitzler E (2003) PISA—a platform and programming language independent interface for search algorithms. In: Proceedings of 2nd international conference on evolutionary multi-criterion optimization, vol 2632. LNCS (Springer), pp 494–508 Bleuler S, Laumanns M, Thiele L, Zitzler E (2003) PISA—a platform and programming language independent interface for search algorithms. In: Proceedings of 2nd international conference on evolutionary multi-criterion optimization, vol 2632. LNCS (Springer), pp 494–508
Metadaten
Titel
Adaptive ε-Ranking on many-objective problems
verfasst von
Hernán Aguirre
Kiyoshi Tanaka
Publikationsdatum
01.12.2009
Verlag
Springer-Verlag
Erschienen in
Evolutionary Intelligence / Ausgabe 4/2009
Print ISSN: 1864-5909
Elektronische ISSN: 1864-5917
DOI
https://doi.org/10.1007/s12065-009-0031-2

Weitere Artikel der Ausgabe 4/2009

Evolutionary Intelligence 4/2009 Zur Ausgabe