[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Multi-objective Optimization

  • Chapter
  • First Online:
Search Methodologies

  • 152k Accesses

Abstract

Multi-objective optimization is an integral part of optimization activities and has a tremendous practical importance, since almost all real-world optimization problems are ideally suited to be modeled using multiple conflicting objectives. The classical means of solving such problems were primarily focused on scalarizing multiple objectives into a single objective, whereas the evolutionary means have been to solve a multi-objective optimization problem as it is. In this chapter, we discuss the fundamental principles of multi-objective optimization, the differences between multi-objective optimization and single-objective optimization, and describe a few well-known classical and evolutionary algorithms for multi-objective optimization. Two application case studies reveal the importance of multi-objective optimization in practice. A number of research challenges are then highlighted. The chapter concludes by suggesting a few tricks of the trade and mentioning some key resources to the field of multi-objective optimization.

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
£29.99 /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
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 79.50
Price includes VAT (United Kingdom)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 99.99
Price includes VAT (United Kingdom)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book
GBP 129.99
Price includes VAT (United Kingdom)
  • Durable hardcover 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

References

  • Babu B, Jehan ML (2003) Differential evolution for multi-objective optimization. In: Proceedings of the CEC’2003, Canberra, vol 4. IEEE, Piscataway, pp 2696–2703

    Google Scholar 

  • Bader J, Deb K, Zitzler E (2010) Faster hypervolume-based search using Monte Carlo sampling. In: Proceedings of the MCDM 2008, Auckland. LNEMS 634. Springer, Heidelberg, pp 313–326

    Google Scholar 

  • Bagchi T (1999) Multiobjective scheduling by genetic algorithms. Kluwer, Boston

    Book  Google Scholar 

  • Balicki J, Kitowski Z (2001) Multicriteria evolutionary algorithm with tabu search for task assignment. In: Proceedings of the EMO-01, Zurich, pp 373–384

    Google Scholar 

  • Bandaru S, Deb K (2010) Automated discovery of vital knowledge from pareto-optimal solutions: first results from engineering design. In: Proceedings of the WCCI-2010, Barcelona. IEEE, Piscataway

    Google Scholar 

  • Bandaru S, Deb K (2011a) Automated innovization for simultaneous discovery of multiple rules in bi-objective problems. In: Proceedings of the EMO-2011, Ouro Preto. Springer, Heidelberg, pp 1–15

    Google Scholar 

  • Bandaru S, Deb K (2011b) Towards automating the discovery of certain innovative design principles through a clustering based optimization technique. Eng Optim 43:911–941

    Article  Google Scholar 

  • Bandyopadhyay S, Saha S, Maulik U, Deb K (2008) A simulated annealing-based multiobjective optimization algorithm: Amosa. IEEE Trans Evol Comput 12:269–283

    Article  Google Scholar 

  • Belton V, Stewart TJ (2002) Multiple criteria decision analysis: an integrated approach. Kluwer, Boston

    Book  Google Scholar 

  • Bleuler S, Brack M, Zitzler E (2001) Multiobjective genetic programming: reducing bloat using SPEA2. In: Proceedings of the CEC-2001, Seoul, pp 536–543

    Google Scholar 

  • Bradstreet L, While L, Barone L (2008) A fast incremental hypervolume algorithm. IEEE Trans Evol Comput 12:714–723

    Article  Google Scholar 

  • Branke J (2001) Evolutionary optimization in dynamic environments. Springer, Heidelberg

    Google Scholar 

  • Branke J, Greco S, Slowinski R, Zielniewicz P (2009) Interactive evolutionary multiobjective optimization using robust ordinal regression. In: Proceedings of the EMO-09, Nantes. Springer, Berlin, pp 554–568

    Google Scholar 

  • Brockhoff D, Zitzler E (2006) Are all objectives necessary? On dimensionality reduction in evolutionary multiobjective optimization. In: PPSN IX, Reykjavik. LNCS 4193, pp 533–542

    Google Scholar 

  • Brockhoff D, Zitzler E (2007) Dimensionality reduction in multiobjective optimization: the minimum objective subset problem. In: Waldmann KH, Stocker UM (eds) OR proceedings 2006, Karlsruhe, Germany. Springer, Berlin, pp 423–429

    Google Scholar 

  • Chankong V, Haimes YY (1983) Multiobjective decision making theory and methodology. North-Holland, New York

    Google Scholar 

  • Chattopadhyay A, Seeley C (1994) A simulated annealing technique for multiobjective optimization of intelligent structures. Smart Mater Struct 3:98–106

    Article  Google Scholar 

  • Coello CAC (2000) Treating objectives as constraints for single objective optimization. Eng Optim 32:275–308

    Article  Google Scholar 

  • Coello CAC (2003) http://www.lania.mx/~ccoello/EMOO/

  • Coello CAC, Lamont GB (2004) Applications of multi-objective evolutionary algorithms. World Scientific, Singapore

    Book  Google Scholar 

  • Coello CAC, Lechuga MS (2002) MOPSO: a proposal for multiple objective particle swarm optimization. In: Proceedings of the CEC 2002, vol 2. IEEE, Piscataway, Honolulu, USA, pp. 1051–1056

    Google Scholar 

  • Coello CAC, Toscano G (2000) A micro-genetic algorithm for multi-objective optimization. Technical report Lania-RI-2000–06, Laboratoria Nacional de Informatica Avanzada, Xalapa, Veracruz

    Google Scholar 

  • Coello CAC, Van Veldhuizen DA, Lamont G (2002) Evolutionary algorithms for solving multi-objective problems. Kluwer, Boston

    Book  Google Scholar 

  • Coello CAC, Aguirre AH, Zitzler E (eds) (2005) Evolutionary multi-criterion optimization (EMO-2005). LNCS 3410. Springer, Berlin

    Google Scholar 

  • Collette Y, Siarry P (2004) Multiobjective optimization: principles and case studies. Springer, Berlin

    Book  Google Scholar 

  • Cormen TH, Leiserson CE, Rivest RL (1990) Introduction to algorithms. Prentice-Hall, New Delhi

    Google Scholar 

  • Corne DW, Knowles JD (2007) Techniques for highly multiobjective optimization: some nondominated points are better than others. In: Proceedings of the GECCO-07, London. ACM, New York, pp 773–780

    Google Scholar 

  • Corne DW, Knowles JD, Oates M (2000) The Pareto envelope-based selection algorithm for multiobjective optimization. In: Proceedings of the PPSN-VI, Paris, pp 839–848

    Google Scholar 

  • Coverstone-Carroll V, Hartmann JW, Mason WJ (2000) Optimal multi-objective low-thurst spacecraft trajectories. Comput Methods Appl Mech Eng 186:387–402

    Article  Google Scholar 

  • Deb K (1995) Optimization for engineering design: algorithms and examples. Prentice-Hall, New Delhi

    Google Scholar 

  • Deb K (1999) Solving goal programming problems using multi-objective genetic algorithms. In: Proceedings of the CEC, Washington, pp 77–84

    Google Scholar 

  • Deb K (2001) Multi-objective optimization using evolutionary algorithms. Wiley, Chichester

    Google Scholar 

  • Deb K (2003) Unveiling innovative design principles by means of multiple conflicting objectives. Eng Optim 35:445–470

    Article  Google Scholar 

  • Deb K, Datta R (2010) A fast and accurate solution of constrained optimization problems using a hybrid bi-objective and penalty function approach. In: Proceedings of the IEEE WCCI 2010, Barcelona, pp 165–172

    Google Scholar 

  • Deb K, Jain S (2002) Running performance metrics for evolutionary multi-objective optimization. In: Proceedings of the 4th Asia-Pacific conference on simulated evolution and learning (SEAL-02), Singapore, pp 13–20

    Google Scholar 

  • Deb K, Jain S (2003) Multi-speed gearbox design using multi-objective evolutionary algorithms. ASME Trans Mech Des 125:609–619

    Article  Google Scholar 

  • Deb K, Jain H (2012) Handling many-objective problems using an improved NSGA-II procedure. In: Proceedings of the CEC 2012, Brisbane

    Google Scholar 

  • Deb K, Kumar A (2007a) Interactive evolutionary multi-objective optimization and decision-making using reference direction method. In: Proceedings of the GECCO 2007, London. ACM, New York, pp 781–788

    Google Scholar 

  • Deb K, Kumar A (2007b) Light beam search based multi-objective optimization using evolutionary algorithms. In: Proceedings of the CEC-07, Singapore, pp 2125–2132

    Google Scholar 

  • Deb K, Saha A (2012) Multimodal optimization using a bi-objective evolutionary algorithms. Evol Comput J 20:27–62

    Article  Google Scholar 

  • Deb K, Saxena D (2006) Searching for Pareto-optimal solutions through dimensionality reduction for certain large-dimensional multi-objective optimization problems. In: Proceedings of the WCCI 2006, Vancouver, pp 3352–3360

    Google Scholar 

  • Deb K, Srinivasan A (2006) Innovization: innovating design principles through optimization. In: Proceedings of the GECCO-2006, Seattle. ACM, New York, pp 1629–1636

    Google Scholar 

  • Deb K, Tiwari S (2004) Multi-objective optimization of a leg mechanism using genetic algorithms. Technical report KanGAL 2004005, Kanpur Genetic Algorithms Laboratory (KanGAL), IIT, Kanpur

    Google Scholar 

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

    Article  Google Scholar 

  • Deb K, Zope P, Jain A (2003a) Distributed computing of pareto-optimal solutions using multi-objective evolutionary algorithms. In: Proceedings of the EMO-03, Faro. LNCS 2632, pp 535–549

    Google Scholar 

  • Deb K, Mohan M, Mishra S (2003b) Towards a quick computation of well-spread pareto-optimal solutions. In: Proceedings of the EMO-03, Faro. LNCS 2632, pp 222–236

    Google Scholar 

  • Deb K, Jain P, Gupta N, Maji H (2004a) Multi-objective placement of electronic components using evolutionary algorithms. IEEE Trans Compon Packag Technol 27:480–492

    Article  Google Scholar 

  • Deb K, Mitra K, Dewri R, Majumdar S (2004b) Towards a better understanding of the epoxy polymerization process using multi-objective evolutionary computation. Chem Eng Sci 59:4261–4277

    Article  Google Scholar 

  • Deb K, Thiele L, Laumanns M, Zitzler E (2005) Scalable test problems for evolutionary multi-objective optimization. In: Abraham A et al (eds) Evolutionary multiobjective optimization. Springer, London, pp 105–145

    Chapter  Google Scholar 

  • Deb K, Sundar J, Uday N, Chaudhuri S (2006) Reference point based multi-objective optimization using evolutionary algorithms. Int J Comput Intell Res (IJCIR) 2:273–286

    Article  Google Scholar 

  • Deb K, Rao UB, Karthik S (2007) Dynamic multi-objective optimization and decision-making using modified NSGA-II: a case study on hydro-thermal power scheduling bi-objective optimization problems. In: Proceedings of the EMO-2007, Matsushima

    Google Scholar 

  • Deb K, Sinha A, Korhonen P, Wallenius J (2010) An interactive evolutionary multi-objective optimization method based on progressively approximated value functions. IEEE Trans Evol Comput 14:723–739

    Article  Google Scholar 

  • Ehrgott M (2000) Multicriteria optimization. Springer, Berlin

    Book  Google Scholar 

  • Ehrgott M, Fonseca CM, Gandibleux X, Hao JK, Sevaux M (eds) (2009) Proceedings of the EMO-2009, Nantes. LNCS 5467. Springer, Heidelberg

    Google Scholar 

  • Fonseca C, Fleming P, Zitzler E, Deb K, Thiele L (eds) (2003) Proceedings of the EMO-2003, Faro. LNCS 2632. Springer, Heidelberg

    Google Scholar 

  • Giel O (2003) Expected runtimes of a simple multi-objective evolutionary algorithm. In: Proceedings of the CEC-2003, Canberra. IEEE, Piscatway, pp 1918–1925

    Google Scholar 

  • Goh CK, Tan KC (2009) Evolutionary multi-objective optimization in uncertain environments: issues and algorithms. Springer, Berlin

    Google Scholar 

  • Goldberg DE (1989) Genetic algorithms for search, optimization, and machine learning. Addison-Wesley, Reading

    Google Scholar 

  • Gravel M, Price WL, Gagné C (2002) Scheduling continuous casting of aluminum using a multiple objective ant colony optimization metaheuristic. Eur J Oper Res 143:218–229

    Article  Google Scholar 

  • Haimes YY, Lasdon LS, Wismer DA (1971) On a bicriterion formulation of the problems of integrated system identification and system optimization. IEEE Trans Syst Man Cybern 1:296–297

    Article  Google Scholar 

  • Hansen MP (1997) Tabu search in multiobjective optimization: MOTS. Paper presented at MCDM’97, University of Cape Town

    Google Scholar 

  • Huband S, Barone L, While L, Hingston P (2005) A scalable multi-objective test problem toolkit. In: Proceedings of the EMO-2005, Guanajuato. Springer, Berlin

    Google Scholar 

  • Hughes EJ (2005) Evolutionary many-objective optimization: many once or one many? In: Proceedings of the CEC-2005, Edinburgh, pp 222–227

    Google Scholar 

  • Ishibuchi H, Tsukamoto N, Nojima Y (2008) Evolutionary many-objective optimization: a short review. In: Proceedings of the CEC-2008, Hong Kong, pp 2424–2431

    Google Scholar 

  • Jensen MT (2003a) Guiding single-objective optimization using multi-objective methods. In: Raidl G et al (eds) Applications of evolutionary computing. Evoworkshops 2003: EvoBIO, EvoCOP, EvoIASP, EvoMUSART, EvoROB, and EvoSTIM, Essex. LNCS 2611. Springer, Berlin, pp 199–210

    Google Scholar 

  • Jensen MT (2003b) Reducing the run-time complexity of multiobjective EAs. IEEE Trans Evol Comput 7:503–515

    Article  Google Scholar 

  • Khor EF, Tan KC, Lee TH (2001) Tabu-based exploratory evolutionary algorithm for effective multi-objective optimization. In: Proceedings of the EMO-01, Zurich, pp 344–358

    Google Scholar 

  • Knowles JD, Corne DW (2000) Approximating the non-dominated front using the Pareto archived evolution strategy. Evol Comput J 8:149–172

    Article  Google Scholar 

  • Knowles J, Corne D (2007) Quantifying the effects of objective space dimension in evolutionary multiobjective optimization. In: Proceedings of the EMO-2007, Matsushima. LNCS 4403, pp 757–771

    Google Scholar 

  • Knowles JD, Corne DW, Deb K (2008) Multiobjective problem solving from nature. Natural computing series. Springer, Berlin

    Book  Google Scholar 

  • Kumral M (2003) Application of chance-constrained programming based on multi-objective simulated annealing to solve a mineral blending problem. Eng Optim 35:661–673

    Article  Google Scholar 

  • Kung HT, Luccio F, Preparata FP (1975) On finding the maxima of a set of vectors. J Assoc Comput Mach 22:469–476

    Article  Google Scholar 

  • Laumanns M, Thiele L, Deb K, Zitzler E (2002a) Combining convergence and diversity in evolutionary multi-objective optimization. Evol Comput 10:263–282

    Article  Google Scholar 

  • Laumanns M, Thiele L, Zitzler E, Welzl E, Deb K (2002b) Running time analysis of multi-objective evolutionary algorithms on a simple discrete optimization problem. In: Proceedings of the PPSN-VII, Granada, pp 44–53

    Google Scholar 

  • Laumanns M, Thiele L, Zitzler E (2004) Running time analysis of multiobjective evolutionary algorithms on pseudo-Boolean functions. IEEE Trans Evol Comput 8:170–182

    Article  Google Scholar 

  • López JA, Coello Coello CA (2009) Some techniques to deal with many-objective problems. In: Proceedings of the 11th annual conference companion on genetic and evolutionary computation, Montreal. ACM, New York, pp 2693–2696

    Google Scholar 

  • Loughlin DH, Ranjithan S (1997) The neighborhood constraint method: a multiobjective optimization technique. In: Proceedings of the 7th international conference on genetic algorithms, East Lansing, pp 666–673

    Google Scholar 

  • McMullen PR (2001) An ant colony optimization approach to addessing a JIT sequencing problem with multiple objectives. Artif Intell Eng 15:309–317

    Article  Google Scholar 

  • Miettinen K (1999) Nonlinear multiobjective optimization. Kluwer, Boston

    Google Scholar 

  • Mostaghim S, Teich J (2003) Strategies for finding good local guides in multi-objective particle swarm optimization (MOPSO). In: Proceedings of the 2003 IEEE symposium on swarm intelligence, Indianapolis. IEEE, Piscataway, pp 26–33

    Google Scholar 

  • Obayashi S, Deb K, Poloni C, Hiroyasu T, Murata T (eds) (2007) Proceedings of the EMO-2007, Matsushima. LNCS 4403. Springer, Berlin

    Google Scholar 

  • Osyczka A (2002) Evolutionary algorithms for single and multicriteria design optimization. Physica-Verlag, Heidelberg

    Google Scholar 

  • Parks G, Suppapitnarm A (1999) Multiobjective optimization of PWR reload core designs using simulated annealing. In: Aragonès JM (eds) Mathematics and computation, reactor physics and environmental analysis in nuclear applications, vol 2. Senda Editorial, Madrid, pp 1435–1444

    Google Scholar 

  • Rudolph G (1998) Evolutionary search for minimal elements in partially ordered finite sets. In: Proceedings of the 7th annual conference on evolutionary programming, San Diego. Springer, Berlin, pp 345–353

    Google Scholar 

  • Rudolph G, Agapie A (2000) Convergence properties of some multi-objective evolutionary algorithms. In: Proceedings of the CEC 2000, San Diego, pp 1010–1016

    Google Scholar 

  • Saxena D, Duro JA, Tiwari A, Deb K, Zhang Q (2013) Objective reduction in many-objective optimization: linear and nonlinear algorithms. IEEE Trans Evol Comput 17(1):77–99

    Article  Google Scholar 

  • Sharma D, Collet P (2010) GPGPU compatible archive based stochastic ranking evolutionary algorithm (G-ASREA) for multi-objective optimization. In: Proceedings of the PPSN-2010, Kraków. Springer, Berlin, pp 111–120

    Google Scholar 

  • Srinivas N, Deb K (1994) Multi-objective function optimization using non-dominated sorting genetic algorithms. Evol Comput J 2:221–248

    Article  Google Scholar 

  • Surry PD, Radcliffe NJ, Boyd ID (1995) A multi-objective approach to constrained optimization of gas supply networks: the COMOGA method. In: Evolutionary computing. AISB workshop, Sheffield. Springer, Berlin, pp 166–180

    Google Scholar 

  • Takahashi RHC, Deb K, Wanner EF, Greco S (2011) Proceedings of the EMO-2011, Ouro Preto. LNCS 6576. Springer, Berlin

    Google Scholar 

  • Tzeng GH, Huang J-J (2011) Multiple attribute decision making: methods and applications. CRC, Boca Raton

    Google Scholar 

  • Veldhuizen DV, Lamont GB (2000) Multiobjective evolutionary algorithms: analyzing the state-of-the-art. Evol Comput J 8:125–148

    Article  Google Scholar 

  • While L, Hingston P, Barone L, Huband S (2006) A faster algorithm for calculating hypervolume. IEEE Trans Evol Comput 10:29–38

    Article  Google Scholar 

  • Wong ML (2009) Parallel multi-objective evolutionary algorithms on graphics processing units. In: Proceedings of the GECCO-2009, Montreal, pp 2515–2522

    Google Scholar 

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

    Article  Google Scholar 

  • Zhang Q, Zhou A, Zhao SZ, Suganthan PN, Liu W, Tiwari S (2008) Multiobjective optimization test instances for the CEC-2009 special session and competition. Technical report, Nanyang Technological University, Singapore

    Google Scholar 

  • Zitzler E (1999) Evolutionary agorithms for multiobjective optimization: methods and applications. PhD thesis, Swiss Federal Institute of Technology ETH, Zürich

    Google Scholar 

  • Zitzler E, Künzli S (2004) Indicator-based selection in multiobjective search. In: Proceedings of the PPSN VIII, Birmingham. LNCS 3242. Springer, Berlin, pp 832–842

    Google Scholar 

  • Zitzler E, Thiele L (1998) An evolutionary algorithm for multiobjective optimization: the strength Pareto approach. Technical report 43, Computer Engineering and Networks Laboratory, Switzerland

    Google Scholar 

  • Zitzler E, Thiele L (1999) Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach. IEEE Trans Evol Comput 3:257–271

    Article  Google Scholar 

  • Zitzler E, Deb K, Thiele L, Coello CAC, Corne DW (2001a) Proceedings of the EMO-2001, Zurich. LNCS 1993. Springer, Berlin

    Google Scholar 

  • Zitzler E, Laumanns M, Thiele L (2001b) SPEA2: improving the strength Pareto evolutionary algorithm for multiobjective optimization. In: Giannakoglou KC, Tsahalis DT, Périaux J, Papailiou KD, Fogarty T (eds) Evolutionary methods for design optimization and control with applications to industrial problems, Athens. International Center for Numerical Methods in Engineering (CIMNE), pp 95–100

    Google Scholar 

  • Zitzler E, Thiele L, Laumanns M, Fonseca CM, da Fonseca VG (2003) Performance assessment of multiobjective optimizers: an analysis and review. IEEE Trans Evol Comput 7:117–132

    Article  Google Scholar 

  • Zitzler E, Thiele L, Bader J (2010) On set-based multiobjective optimization. IEEE Trans Evol Comput 14:58–79

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Electrical and Computer Engineering, Michigan State University, East Lansing, 428 S. Shaw Lane, 2120 EB, MI, 48824, USA

    Kalyanmoy Deb (Koenig Endowed Chair Professor) & Kalyanmoy Deb (Professor)

  2. Department of Computer Science, Michigan State University, East Lansing, MI, USA

    Kalyanmoy Deb (Koenig Endowed Chair Professor) & Kalyanmoy Deb (Professor)

  3. Department of Mechanical Engineering, Michigan State University, East Lansing, MI, USA

    Kalyanmoy Deb (Koenig Endowed Chair Professor) & Kalyanmoy Deb (Professor)

Authors
  1. Kalyanmoy Deb
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Kalyanmoy Deb
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Kalyanmoy Deb .

Editor information

Editors and Affiliations

  1. Computing Science and Mathematics, University of Stirling, Scotland, United Kingdom

    Edmund K. Burke

  2. Research and Knowledge Transfer, University of Nottingham, Malaysia & UK, Semenyih, Malaysia

    Graham Kendall

Rights and permissions

Reprints and permissions

Copyright information

© 2014 Springer Science+Business Media New York

About this chapter

Cite this chapter

Deb, K., Deb, K. (2014). Multi-objective Optimization. In: Burke, E., Kendall, G. (eds) Search Methodologies. Springer, Boston, MA. https://doi.org/10.1007/978-1-4614-6940-7_15

Download citation

Publish with us

Policies and ethics

Search

Navigation