Skip to main content
Top
Published in: Natural Computing 3/2015

01-09-2015

Incorporating user preferences in many-objective optimization using relation ε-preferred

Authors: Nicole Drechsler, André Sülflow, Rolf Drechsler

Published in: Natural Computing | Issue 3/2015

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

During the last 10 years, many-objective optimization problems, i.e. optimization problems with more than three objectives, are getting more and more important in the area of multi-objective optimization. Many real-world optimization problems consist of more than three mutually dependent subproblems, that have to be considered in parallel. Furthermore, the objectives have different levels of importance. For this, priorities have to be assigned to the objectives. In this paper we present a new model for many-objective optimization called Prio-ε-Preferred, where the objectives can have different levels of priorities or user preferences. This relation is used for ranking a set of solutions such that an ordering of the solutions is determined. Prio-ε-Preferred is controlled by a parameter ε, that is problem specific and has to be adjusted experimentally by the developer. Therefore we also present an extension called Adapted-ε-Preferred (AEP), that determines the ε values automatically without any user interaction. To demonstrate the efficiency of our approach, experiments are performed. The method based on Prio-ε-Preferred is used to guide the search of an Evolutionary Algorithm. As optimization problem a very complex scheduling problem, i.e. a utilization planning in a hospital is used. The considered benchmarks consist of 2 up to 90 optimization objectives. First, Prio-ε-Preferred  where ε is set “by hand”, is compared to the basic method NSGA-II. It is shown that Prio-ε-Preferred clearly outperforms NSGA-II. Furthermore, it turns out that the results obtained by AEP are as good as if ε is adjusted manually.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

Footnotes
1
In contrast to (Sülflow et al. 2007) benchmarks from (Benchmarks 2012) are taken. This makes the results comparable to other approaches.
 
2
But indeed, the modeling of user preferences as presented here in combination with the hypervolume indicator is an interesting task for future work.
 
3
If \(p \ge \#days\), the algorithm stops. But if the border of the next planning period is known, the operator can easily be extended such that it can mutate the first days of the next planning period.
 
4
In all Tables Millar-2Shift is an abbreviation for benchmark Millar-2Shift-DATA1.
 
Literature
go back to reference Auger A, Bader J, Brockhoff D, Zitzler E (2009) Articulating user preferences in many-objective problems by sampling the weighted hypervolume. In: Genetic and evolutionary computation conference, pp 555–562 Auger A, Bader J, Brockhoff D, Zitzler E (2009) Articulating user preferences in many-objective problems by sampling the weighted hypervolume. In: Genetic and evolutionary computation conference, pp 555–562
go back to reference Bader J, Zitzler E (2011) HypE: an algorithm for fast hypervolume-based many-objective optimization. Evol Comput 19(1):45–76CrossRef Bader J, Zitzler E (2011) HypE: an algorithm for fast hypervolume-based many-objective optimization. Evol Comput 19(1):45–76CrossRef
go back to reference Brockhoff D, Zitzler E (2009) Objective reduction in evolutionary multiobjective optimization: theorie and applications. Evol Comput 17(2):135–166CrossRef Brockhoff D, Zitzler E (2009) Objective reduction in evolutionary multiobjective optimization: theorie and applications. Evol Comput 17(2):135–166CrossRef
go back to reference Burke EK, De Causmaecker P, Berghe GV, Landeghem HV (2004) The state of the art of nurse rostering. J Schedu 7:441–499CrossRefMATH Burke EK, De Causmaecker P, Berghe GV, Landeghem HV (2004) The state of the art of nurse rostering. J Schedu 7:441–499CrossRefMATH
go back to reference Cormen TH, Leierson CE, Rivest RC (1990) Introduction to algorithms. MIT Press, CambridgeMATH Cormen TH, Leierson CE, Rivest RC (1990) Introduction to algorithms. MIT Press, CambridgeMATH
go back to reference Corne D, Knowles J (2007) Techniques for highly multiobjective optimization: theorie and applications. In: Genetic and evolutionary computation conference, pp 773–780 Corne D, Knowles J (2007) Techniques for highly multiobjective optimization: theorie and applications. In: Genetic and evolutionary computation conference, pp 773–780
go back to reference Deb K (2001) Multi-objective optimization using evolutionary algorithms. Wiley, New YorkMATH Deb K (2001) Multi-objective optimization using evolutionary algorithms. Wiley, New YorkMATH
go back to reference Deb K, Saxena K (2006) Searching for pareto-optimal solutions through dimensionality reduction for certain large-dimensional multi-objective optimization problems. In: IEEE congress on evolutionary computation, 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: IEEE congress on evolutionary computation, pp 3353–3360
go back to reference Deb K, Pratap A, Agarwal S, Meyarivan T (2000) A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans Evol Comput 6:182–197CrossRef Deb K, Pratap A, Agarwal S, Meyarivan T (2000) A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans Evol Comput 6:182–197CrossRef
go back to reference Deb K, Thiele L, Laumanns M, Zitzler E (2005) Scalable test problems for evolutionary multi-objective optimization. In: In evolutionary multiobjective optimization, theoretical advances and applications, pp 105–145 Deb K, Thiele L, Laumanns M, Zitzler E (2005) Scalable test problems for evolutionary multi-objective optimization. In: In evolutionary multiobjective optimization, theoretical advances and applications, pp 105–145
go back to reference di Pierro F, Khu ST, Savic DA (2007) An investigation on preference order ranking scheme for multi-objective optimization. IEEE Trans Evol Comput 11(1):17–45CrossRef di Pierro F, Khu ST, Savic DA (2007) An investigation on preference order ranking scheme for multi-objective optimization. IEEE Trans Evol Comput 11(1):17–45CrossRef
go back to reference Drechsler N, Drechsler R, Becker B (2001) Multi-objective optimisation based on relation favour. In: International conference on evolutionary multi-criterion optimization, pp 154–166 Drechsler N, Drechsler R, Becker B (2001) Multi-objective optimisation based on relation favour. In: International conference on evolutionary multi-criterion optimization, pp 154–166
go back to reference Farina M, Amato P (2002) On the optimal solution definition for many-criteria optimization problems. In: Proceedings of the NAFIPS-FLINT international conference 2002. IEEE Press, Piscataway, NJ, pp 233–238 Farina M, Amato P (2002) On the optimal solution definition for many-criteria optimization problems. In: Proceedings of the NAFIPS-FLINT international conference 2002. IEEE Press, Piscataway, NJ, pp 233–238
go back to reference Fleming PJ, Purshouse RC, Lygoe RJ (2005) Many-objective optimization: an engineering design perspective. In: International conference on evolutionary multi-criterion optimization, pp 14–32 Fleming PJ, Purshouse RC, Lygoe RJ (2005) Many-objective optimization: an engineering design perspective. In: International conference on evolutionary multi-criterion optimization, pp 14–32
go back to reference Fonseca CM, Fleming PJ (1995) An overview of evolutionary algorithms in multiobjective optimization. Evol Comput 3(1):1–16CrossRef Fonseca CM, Fleming PJ (1995) An overview of evolutionary algorithms in multiobjective optimization. Evol Comput 3(1):1–16CrossRef
go back to reference Geiger MJ (2009) 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 Geiger MJ (2009) 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
go back to reference Goldberg DE (1989) Genetic algorithms in search, optimization & machine learning. Addision-Wesley Publisher Company, Inc., BostonMATH Goldberg DE (1989) Genetic algorithms in search, optimization & machine learning. Addision-Wesley Publisher Company, Inc., BostonMATH
go back to reference Hughes EJ (2007) Radar waveform optimization as a many-objective application benchmark. In: International conference on evolutionary multi-criterion, optimization, pp 700–714 Hughes EJ (2007) Radar waveform optimization as a many-objective application benchmark. In: International conference on evolutionary multi-criterion, optimization, pp 700–714
go back to reference Ishibuchi H, Tsukamoto N, Nojima Y (2008) Evolutionary many-objective optimization: a short review. In: IEEE congress on evolutionary computation, pp 2424–2431 Ishibuchi H, Tsukamoto N, Nojima Y (2008) Evolutionary many-objective optimization: a short review. In: IEEE congress on evolutionary computation, pp 2424–2431
go back to reference Khare VR, Yao X, Deb K (2003) Performance scaling of multi-objective evolutionary algorithms. In: EMO 2003. Lecture Notes in Computer Science, vol 2632, pp 376–390 Khare VR, Yao X, Deb K (2003) Performance scaling of multi-objective evolutionary algorithms. In: EMO 2003. Lecture Notes in Computer Science, vol 2632, pp 376–390
go back to reference Koza J (1992) Genetic programming—on the programming of computers by means of natural selection. MIT Press, CambridgeMATH Koza J (1992) Genetic programming—on the programming of computers by means of natural selection. MIT Press, CambridgeMATH
go back to reference Onety R, Moreira G, Neto O, Takahashi R (2011) Variable neighborhood multiobjective genetic algorithm for the optimization of routes in IP networks. In: International conference on evolutionary multi-criterion optimization, pp 443–447 Onety R, Moreira G, Neto O, Takahashi R (2011) Variable neighborhood multiobjective genetic algorithm for the optimization of routes in IP networks. In: International conference on evolutionary multi-criterion optimization, pp 443–447
go back to reference Pizzuti C (2012) A multiobjective genetic algorithm to find communities in complex networks. IEEE Trans Evol Comput 16(3):418–430CrossRef Pizzuti C (2012) A multiobjective genetic algorithm to find communities in complex networks. IEEE Trans Evol Comput 16(3):418–430CrossRef
go back to reference Purshouse RC, Fleming PJ (2003) Evolutionary multi-objective optimisation: an exploratory analysis. In: Proceedings of the (2003) IEEE congress on evolutionary computation (CEC’2003), Canberra, Australia, pp 2066–2073 Purshouse RC, Fleming PJ (2003) Evolutionary multi-objective optimisation: an exploratory analysis. In: Proceedings of the (2003) IEEE congress on evolutionary computation (CEC’2003), Canberra, Australia, pp 2066–2073
go back to reference Sato H, Aguirre HE, Tanaka K (2007) Controlling dominance area solutions and its impact on the performance of MOEAs. In: International conference on evolutionary multi-criterion optimization, pp 5–20 Sato H, Aguirre HE, Tanaka K (2007) Controlling dominance area solutions and its impact on the performance of MOEAs. In: International conference on evolutionary multi-criterion optimization, pp 5–20
go back to reference Schmiedle F, Drechsler N, Große D, Drechsler R (2001) Priorities in multi-objective optimization for genetic programming. In: Genetic and evolutionary computation conference, pp 129–136 Schmiedle F, Drechsler N, Große D, Drechsler R (2001) Priorities in multi-objective optimization for genetic programming. In: Genetic and evolutionary computation conference, pp 129–136
go back to reference Sülflow A, Drechsler N, Drechsler R (2007) Robust multi-objective optimization in high-dimensional spaces. In: International conference on evolutionary multi-criterion optimization, pp 715–726 Sülflow A, Drechsler N, Drechsler R (2007) Robust multi-objective optimization in high-dimensional spaces. In: International conference on evolutionary multi-criterion optimization, pp 715–726
go back to reference Wagner T, Trautmann H (2010) Integration of preferences in hypervolume-based multiobjective evolutionary algorithms by means of desirability functions. IEEE Trans Evol Comput 14(5):688–701CrossRef Wagner T, Trautmann H (2010) Integration of preferences in hypervolume-based multiobjective evolutionary algorithms by means of desirability functions. IEEE Trans Evol Comput 14(5):688–701CrossRef
go back to reference Wagner T, Beume N, Naujoks B (2007) Pareto-, aggregation- and indicator-based methods in many-objective optimization. In: International conference on evolutionary multi-criterion optimization, pp 742–756 Wagner T, Beume N, Naujoks B (2007) Pareto-, aggregation- and indicator-based methods in many-objective optimization. In: International conference on evolutionary multi-criterion optimization, pp 742–756
go back to reference Wickramasinghe U, Li X (2009) 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 Wickramasinghe U, Li X (2009) 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
go back to reference Zhang Q, Li H (2007) Moea/d: a multiobjective evolutionary algorithm based on decomposition. IEEE Trans Evol Comput 11(6):712–731CrossRef Zhang Q, Li H (2007) Moea/d: a multiobjective evolutionary algorithm based on decomposition. IEEE Trans Evol Comput 11(6):712–731CrossRef
go back to reference Zitzler E, Thiele L (1999) Multiobjective evolutionary algorithms: a comparative case study and the strength pareto approach. IEEE Trans Evol Comput 3(4):257–271CrossRef Zitzler E, Thiele L (1999) Multiobjective evolutionary algorithms: a comparative case study and the strength pareto approach. IEEE Trans Evol Comput 3(4):257–271CrossRef
Metadata
Title
Incorporating user preferences in many-objective optimization using relation ε-preferred
Authors
Nicole Drechsler
André Sülflow
Rolf Drechsler
Publication date
01-09-2015
Publisher
Springer Netherlands
Published in
Natural Computing / Issue 3/2015
Print ISSN: 1567-7818
Electronic ISSN: 1572-9796
DOI
https://doi.org/10.1007/s11047-014-9422-0

Other articles of this Issue 3/2015

Natural Computing 3/2015 Go to the issue

Premium Partner