Skip to main content

2016 | OriginalPaper | Buchkapitel

Self-adaptive Evolutionary Many-Objective Optimization Based on Relation \({\varepsilon }\)-Preferred

verfasst von : Nicole Drechsler

Erschienen in: Computational Intelligence

Verlag: Springer International Publishing

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

search-config
loading …

Abstract

Many real-world optimization problems consist of several mutually dependent subproblems. If more than three optimization objectives are involved in the optimization process, the so-called Many-Objective Optimization is a challenge in the area of multi-objective optimization. Often, the objectives have different levels of importance that have to be considered. For this, relation \({\varepsilon }\)-\(\textit{Preferred} \) has been presented, that enables to compare and rank multi-dimensional solutions. \({\varepsilon }\)-\(\textit{Preferred} \) is controlled by a parameter \({\varepsilon }\) that has influence on the quality of the results. In this paper for the setting of the epsilon values three heuristics have been investigated. To demonstrate the behavior and efficiency of these methods an Evolutionary Algorithm for the multi-dimensional Nurse Rostering Problem is proposed. It is shown by experiments that former approaches are outperformed by heuristics that are based on self-adaptive mechanisms.

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!

Fußnoten
1
For the investigation of this approach the NRP has been used as application, because it consists of many objectives with different levels of priorities. There, in contrast to standard benchmarks for MOO (DTLZ [19]), the priorities are provided in the benchmark files.
 
2
Originally the benchmarks are designed for optimization using a Weighted Sum. Thus, the weights are justified by a planner and directly given in the benchmark.
 
3
The main reason for using NSGA-II for comparison is that it can easily be enlarged such that it can handle priorities as described in this paper. Other methods like e.g. Hype [4] are more suitable for Many-Objective Optimization, but it is not obvious how to incorporate the priorities. This is an interesting task for further developments.
 
Literatur
1.
Zurück zum Zitat Fonseca, C., Fleming, P.: An overview of evolutionary algorithms in multiobjective optimization. Evol. Comput. 3(1), 1–16 (1995) CrossRef Fonseca, C., Fleming, P.: An overview of evolutionary algorithms in multiobjective optimization. Evol. Comput. 3(1), 1–16 (1995) CrossRef
2.
Zurück zum Zitat Zitzler, E., Thiele, L.: Multiobjective evolutionary algorithms: a comparative case study and the strength pareto approach. IEEE Trans. Evol. Comput. 3(4), 257–271 (1999) CrossRef Zitzler, E., Thiele, L.: Multiobjective evolutionary algorithms: a comparative case study and the strength pareto approach. IEEE Trans. Evol. Comput. 3(4), 257–271 (1999) CrossRef
3.
Zurück zum Zitat Deb, K.: Multi-objective Optimization using Evolutionary Algorithms. Wiley, New York (2001) Deb, K.: Multi-objective Optimization using Evolutionary Algorithms. Wiley, New York (2001)
4.
Zurück zum Zitat Bader, J., Zitzler, E.: HypE: an algorithm for fast hypervolume-based many-objective optimization. Evol. Comput. 19(1), 45–76 (2011) CrossRef Bader, J., Zitzler, E.: HypE: an algorithm for fast hypervolume-based many-objective optimization. Evol. Comput. 19(1), 45–76 (2011) CrossRef
5.
Zurück zum Zitat Drechsler, N., Drechsler, R., Becker, B.: Multi-objective optimisation based on relation favour. In: International Conference on Evolutionary Multi-Criterion Optimization, pp. 154–166 (2001) Drechsler, N., Drechsler, R., Becker, B.: Multi-objective optimisation based on relation favour. In: International Conference on Evolutionary Multi-Criterion Optimization, pp. 154–166 (2001)
6.
Zurück zum Zitat Hughes, E.: Radar waveform optimization as a many-objective application benchmark. In: International Conference on Evolutionary Multi-Criterion Optimization, pp. 700–714 (2007) Hughes, E.: Radar waveform optimization as a many-objective application benchmark. In: International Conference on Evolutionary Multi-Criterion Optimization, pp. 700–714 (2007)
7.
Zurück zum Zitat Pizzuti, C.: A multiobjective genetic algorithm to find communities in complex networks. IEEE Trans. Evol. Comput. 16(3), 418–430 (2012) CrossRef Pizzuti, C.: A multiobjective genetic algorithm to find communities in complex networks. IEEE Trans. Evol. Comput. 16(3), 418–430 (2012) CrossRef
8.
Zurück zum Zitat Schmiedle, F., Drechsler, N., Große, D., Drechsler, R.: Priorities in multi-objective optimization for genetic programming. In: Genetic and Evolutionary Computation Conference, pp. 129–136 (2001) Schmiedle, F., Drechsler, N., Große, D., Drechsler, R.: Priorities in multi-objective optimization for genetic programming. In: Genetic and Evolutionary Computation Conference, pp. 129–136 (2001)
9.
Zurück zum Zitat Wickramasinghe, U., Li, X.: A distance metric for evolutionary many-objective optimization algorithms using user-preferences. In: 22nd Australasian Joint Conference on Advances in Artificial Intelligence (AI’09), pp. 443–453 (2009) CrossRef Wickramasinghe, U., Li, X.: A distance metric for evolutionary many-objective optimization algorithms using user-preferences. In: 22nd Australasian Joint Conference on Advances in Artificial Intelligence (AI’09), pp. 443–453 (2009) CrossRef
10.
Zurück zum Zitat Auger, A., Bader, J., Brockhoff, D., Zitzler, E.: Articulating user preferences in many-objective problems by sampling the weighted hypervolume. In: Genetic and Evolutionary Computation Conference, pp. 555–562 (2009) Auger, A., Bader, J., Brockhoff, D., Zitzler, E.: Articulating user preferences in many-objective problems by sampling the weighted hypervolume. In: Genetic and Evolutionary Computation Conference, pp. 555–562 (2009)
11.
Zurück zum Zitat Wagner, T., Trautmann, H.: Integration of preferences in hypervolume-based multiobjective evolutionary algorithms by means of desirability functions. IEEE Trans. Evol. Comput. 14(5), 688–701 (2012) CrossRef Wagner, T., Trautmann, H.: Integration of preferences in hypervolume-based multiobjective evolutionary algorithms by means of desirability functions. IEEE Trans. Evol. Comput. 14(5), 688–701 (2012) CrossRef
12.
Zurück zum Zitat Drechsler, N., Sülflow, S., Drechsler, R.: Incorporating user preferences in many-objective optimization using relation \(\epsilon \)-preferred. In: International Conference on Evolutionary Computation Theory and Applications (2013) Drechsler, N., Sülflow, S., Drechsler, R.: Incorporating user preferences in many-objective optimization using relation \(\epsilon \)-preferred. In: International Conference on Evolutionary Computation Theory and Applications (2013)
13.
Zurück zum Zitat Geiger, M.: Multi-criteria curriculum-based course timetabling—a comparison of a weighted sum and a reference point based approach. In: International Conference on Evolutionary Multi-Criterion Optimization, pp. 290–304 (2009) Geiger, M.: Multi-criteria curriculum-based course timetabling—a comparison of a weighted sum and a reference point based approach. In: International Conference on Evolutionary Multi-Criterion Optimization, pp. 290–304 (2009)
14.
Zurück zum Zitat Goldberg, D.: Genetic Algorithms in Search Optimization and Machine Learning. Addison-Wesley Publisher Company, Inc, Reading (1989) Goldberg, D.: Genetic Algorithms in Search Optimization and Machine Learning. Addison-Wesley Publisher Company, Inc, Reading (1989)
15.
Zurück zum Zitat Corne, D., Knowles, J.: Techniques for highly multiobjective optimization: theorie and applications. In: Genetic and Evolutionary Computation Conference, pp. 773–780 (2007) Corne, D., Knowles, J.: Techniques for highly multiobjective optimization: theorie and applications. In: Genetic and Evolutionary Computation Conference, pp. 773–780 (2007)
16.
Zurück zum Zitat Ishibuchi, H., Tsukamoto, N., Nojima, Y.: Evolutionary many-objective optimization: a short review. In: IEEE Congress on Evolutionary Computation, pp. 2424–2431 (2008) Ishibuchi, H., Tsukamoto, N., Nojima, Y.: Evolutionary many-objective optimization: a short review. In: IEEE Congress on Evolutionary Computation, pp. 2424–2431 (2008)
17.
Zurück zum Zitat Sülflow, A., Drechsler, N., Drechsler, R.: Robust multi-objective optimization in high-dimensional spaces. In: International Conference on Evolutionary Multi-Criterion Optimization, pp. 715–726 (2007) Sülflow, A., Drechsler, N., Drechsler, R.: Robust multi-objective optimization in high-dimensional spaces. In: International Conference on Evolutionary Multi-Criterion Optimization, pp. 715–726 (2007)
18.
Zurück zum Zitat Zhang, Q., Li, H.: Moea/d: a multiobjective evolutionary algorithm based on decomposition. IEEE Trans. Evol. Comput. 11(6), 712–731 (2007) CrossRef Zhang, Q., Li, H.: Moea/d: a multiobjective evolutionary algorithm based on decomposition. IEEE Trans. Evol. Comput. 11(6), 712–731 (2007) CrossRef
19.
Zurück zum Zitat Deb, K., Thiele, L., Laumanns, M., Zitzler, E.: Scalable test problems for evolutionary multi-objective optimization. Technical Report 112, Computer Engineering and Networks Laboratory (TIK), Swiss Federal Institute of Technology (ETH), Zurich, Switzerland (2001) Deb, K., Thiele, L., Laumanns, M., Zitzler, E.: Scalable test problems for evolutionary multi-objective optimization. Technical Report 112, Computer Engineering and Networks Laboratory (TIK), Swiss Federal Institute of Technology (ETH), Zurich, Switzerland (2001)
20.
Zurück zum Zitat Burke, E., Curtois, T., Qu, R., Vanden-Berghe, G.: Problem model for nurse rostering benchmark instances. Technical report, ASAP, School of Computer Science, University of Nottingham, UK (2012) Burke, E., Curtois, T., Qu, R., Vanden-Berghe, G.: Problem model for nurse rostering benchmark instances. Technical report, ASAP, School of Computer Science, University of Nottingham, UK (2012)
21.
Zurück zum Zitat Cormen, T., Leierson, C., Rivest, R.: Introduction to Algorithms. MIT Press, Cambridge (1990) Cormen, T., Leierson, C., Rivest, R.: Introduction to Algorithms. MIT Press, Cambridge (1990)
22.
Zurück zum Zitat Burke, E., Causmaecker, P.D., Berghe, G., Landeghem, H.: The state of the art of nurse rostering. J. Sched. 7, 441–499 (2004) MathSciNetCrossRef Burke, E., Causmaecker, P.D., Berghe, G., Landeghem, H.: The state of the art of nurse rostering. J. Sched. 7, 441–499 (2004) MathSciNetCrossRef
Metadaten
Titel
Self-adaptive Evolutionary Many-Objective Optimization Based on Relation -Preferred
verfasst von
Nicole Drechsler
Copyright-Jahr
2016
Verlag
Springer International Publishing
DOI
https://doi.org/10.1007/978-3-319-23392-5_2