Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

A Survey of Decomposition Methods for Multi-objective Optimization

  • Chapter
  • First Online:
Recent Advances on Hybrid Approaches for Designing Intelligent Systems

Part of the book series: Studies in Computational Intelligence ((SCI,volume 547))

  • 2400 Accesses

Abstract

The multi-objective optimization methods are traditionally based on Pareto dominance or relaxed forms of dominance in order to achieve a representation of the Pareto front. However, the performance of traditional optimization methods decreases for those problems with more than three objectives to optimize. The decomposition of a multi-objective problem is an approach that transforms a multi-objective problem into many single-objective optimization problems, avoiding the need of any dominance form. This chapter provides a short review of the general framework, current research trends and future research topics on decomposition methods.

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
$34.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
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 169.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Hardcover Book
USD 219.99
Price excludes VAT (USA)
  • 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

  1. Dantzig, G.B., Wolfe, P.: Decomposition principle for linear programs. Oper. Res. 8(1), 101–111 (1960)

    Article  MATH  Google Scholar 

  2. Dantzig, G.B., Harvey, R.P., Lansdowne, Zachary F., Robinson, D.W., Maier, S.F.: Formulating and solving the network design problem by decomposition. Transp. Res. Part B: Methodol. 13(1), 5–17 (1979)

    Article  Google Scholar 

  3. Sobieszczanski-Sobieski, J., James, B.B., Dovi, A.R.: Structural optimization by multi level decomposition. AIAA J. 23(11), 1775–1782 (1985)

    Google Scholar 

  4. Ovacik, I.M., Uzsoy, R.: Decomposition Methods for Complex Factory Scheduling Problems. Kluwer Academic Publishers, Boston (1997)

    Book  Google Scholar 

  5. Dorronsoro, B., Danoy, G., Nebro, A.J., Bouvry, P.: Achieving super-linear performance in parallel multi-objective evolutionary algorithms by means of cooperative coevolution. Comput. Oper. Res. 40(6), 1552–1563(2013) (Emergent nature inspired algorithms for multi-objective optimization)

    Google Scholar 

  6. Liu, M., Zou, X., Chen, Y., Wu, Z.: Performance assessment of DMOEA-DD with CEC 2009 MOEA competition test instances. In: IEEE Congress on Evolutionary Computation (CEC 09), pp. 2913–2918 (2009)

    Google Scholar 

  7. Boyd, S., Xiao, L., Mutapcic, A., Mattingley, J.: Notes on decomposition methods. Notes for EE364B, Stanford University (2008)

    Google Scholar 

  8. Abdelouahed, H., Mishra, S.K.: Decomposition methods based on augmented lagrangians: a survey. In: Mishra, S.K. (ed.) Topics in Nonconvex Optimization, Springer Optimization and Its Applications, pp. 175–203. Springer, New York (2011)

    Google Scholar 

  9. Koko, J.: A survey on dual decomposition methods. SeMA J. 62(1), 27–59 (2013)

    Article  MATH  MathSciNet  Google Scholar 

  10. Palomar, D.P., Chiang, Mung: A tutorial on decomposition methods for network utility maximization. IEEE J. Sel. Areas Commun. 24(8), 1439–1451 (2006)

    Article  Google Scholar 

  11. Sakawa, M., Yano, H.: A fuzzy decomposition method by right-hand-side allocation for large-scale multiobjective nonlinear programming problems. In: Clmaco, J. (ed.) Multicriteria Analysis, pp. 237–246. Springer, Berlin, Heidelberg (1997)

    Chapter  Google Scholar 

  12. Sefrioui, M., Perlaux, J.: Nash genetic algorithms: examples and applications. In: Proceedings of the 2000 Congress on Evolutionary Computation, vol. 1, pp. 509–516 (2000)

    Google Scholar 

  13. Zhan, Z.H., Li, J., Cao, J., Zhang, J., Chung, H.S.-H., Shi, Y.-H.: Multiple populations for multiple objectives: a coevolutionary technique for solving multiobjective optimization problems. IEEE Trans. Cybern. 43(2), 445–463 (2013)

    Article  Google Scholar 

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

    Article  Google Scholar 

  15. Grabisch, M., Marichal, J.-L., Mesiar, R., Pap, E.: Aggregation functions: means. Inf. Sci. 181(1), 1–22 (2011)

    Article  MATH  MathSciNet  Google Scholar 

  16. Zadeh, L.: Optimality and non-scalar-valued performance criteria. IEEE Trans. Autom. Control 8(1), 59–60 (1963)

    Article  Google Scholar 

  17. Marler, R.T., Arora, J.S.: Survey of multi-objective optimization methods for engineering. Struct. Multi. Optim. 26(6), 369–395 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  18. Sindhya, K., Ruuska, S., Haanp, T., Miettinen, K.: A new hybrid mutation operator for multiobjective optimization with differential evolution. Soft. Comput. 15(10), 2041–2055 (2011)

    Article  Google Scholar 

  19. Athan, T.W., Pa-palambros, P.Y.: A note on weighted criteria methods for compromise solutions in multi-objective optimization. Eng. Optim. 27, 155–176 (1996)

    Google Scholar 

  20. Zhang, Q., Liu, W., Li, H.: The performance of a new version of MOEA/D on CEC09 unconstrained mop test instances. In: IEEE Evolutionary Computation (CEC’09), pp. 203–208 (2009)

    Google Scholar 

  21. Messac, A., Mattson, C.A.: Generating well-distributed sets of Pareto points for engineering design using physical programming. Optim. Eng. 3(4), 431–450 (2002)

    Article  MATH  Google Scholar 

  22. Tan, Y.Y., Jiao, Y.C., Li, H., Wang, X.: MOEA/D uniform design: a new version of MOEA/D for optimization problems with many objectives. Comput. Oper. Res. 40(6), 1648−1660 (2013) (emergent nature inspired algorithms for multi-objective optimization)

    Google Scholar 

  23. Hughes, E.J.: Msops-ii: a general-purpose many-objective optimiser. In: IEEE Congress on Evolutionary Computation (CEC 2007), pp. 3944–3951 (2007)

    Google Scholar 

  24. Hughes, E.J.: Multiple single objective Pareto sampling. In: The 2003 Congress on Evolutionary Computation (CEC’03), vol. 4, pp. 2678–2684 (2003)

    Google Scholar 

  25. Hughes, E.J.: Many-objective directed evolutionary line search. In: Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation (GECCO’11), pp. 761–768. ACM, New York (2011)

    Google Scholar 

  26. Fabre, M.G., Pulido, G.T., Coello, C.A.C.: Alternative fitness assignment methods for many-objective optimization problems. In: Collet, P., Monmarch, N., Legrand, P., Schoenauer, M., Lutton, E. (eds.): Artificial Evolution. Lecture Notes in Computer Science, vol. 5975, pp. 146–157. Springer, Berlin, Heidelberg (2010)

    Google Scholar 

  27. Li, H., Zhang, Q.: Multiobjective optimization problems with complicated pareto sets, MOEA/D and NSGA-II. IEEE Trans. Evol. Comput. 13(2), 229–242 (2009)

    Article  Google Scholar 

  28. Ishibuchi, H., Murata, T.: A multi-objective genetic local search algorithm and its application to flowshop scheduling. IEEE Trans. Syst. Man Cybern. Part C Appl. Rev. 28(3), 392–403 (1998)

    Article  Google Scholar 

  29. Tan, Y.-Y., Jiao, Y.-C., Li, H., Wang, X.-K.: MOEA/D-SQA: a multi-objective memetic algorithm based on decomposition. Eng. Opt. 44(9), 1095–1115 (2012)

    Article  Google Scholar 

  30. Mei, Y., Tang, K., Yao, X.: Decomposition-based memetic algorithm for multiobjective capacitated arc routing problem. IEEE Trans. Evol. Comput. 15(2), 151–165 (2011)

    Article  Google Scholar 

  31. Deb, K., Agrawal, S., Pratap, A., Meyarivan, T.: A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: Nsga-ii. In: Proceedings of the 6th International Conference on Parallel Problem Solving from Nature. Lecture Notes in Computer Science, vol. 1917. Springer, Berlin, Heidelberg (2000)

    Google Scholar 

  32. Ke, L., Zhang, Q., Battiti, R.: MOEA/D-ACO: a multiobjective evolutionary algorithm using decomposition and ant colony. IEEE Trans. Cybern. 43(6), 1845–1859 (2013)

    Article  Google Scholar 

  33. Peng, W., Zhang, Q.: A decomposition-based multi-objective particle swarm optimization algorithm for continuous optimization problems. In: IEEE International Conference on Granular Computing (GrC 2008), pp. 534–537 (2008)

    Google Scholar 

  34. Al Moubayed, N., Petrovski, A., McCall, J.: A novel smart multi-objective particle swarm optimisation using decomposition. In: Schaefer, R., Cotta, C., Koodziej, J., Rudolph, G. (eds.) Parallel Problem Solving from Nature, PPSN XI. Lecture Notes in Computer Science, vol. 6239, pp. 1–10. Springer, Berlin Heidelberg (2010)

    Chapter  Google Scholar 

  35. Martínez, S.Z., Coello, C.A.C.: A multi-objective particle swarm optimizer based on decomposition. In: Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation (GECCO’11), pp. 69–76. ACM, New York (2011)

    Google Scholar 

  36. Al Moubayed, N, Petrovski, A., McCall, J.: D2MOPSO: multi-objective particle swarm optimizer based on decomposition and dominance. In: Hao, J.-K., Middendorf, M. (eds.) Evolutionary Computation in Combinatorial Optimization. Lecture Notes in Computer Science, vol. 7245, pp. 75–86. Springer Berlin Heidelberg (2012)

    Google Scholar 

  37. Van Veldhuizen, D.A., Lamont, G.B.: Multiobjective Evolutionary Algorithm Research: A History and Analysis (1998)

    Google Scholar 

  38. Coello, C.A.C.: Evolutionary multi-objective optimization: some current research trends and topics that remain to be explored. Front. Comput. Sci. China 3(1), 18–30 (2009)

    Article  Google Scholar 

  39. Hughes, E.: Evolutionary many-objective optimisation: many once or one many? In: The 2005 IEEE Congress on Evolutionary Computation, 2005, vol. 1, pp. 222–227 (2005)

    Google Scholar 

  40. Berkhin, P.: A survey of clustering data mining techniques. In: Kogan, J., Nicholas, C., Teboulle, M. (eds.) Grouping Multi-dimensional Data, pp. 25–71. Springer, Berlin, Heidelberg (2006)

    Chapter  Google Scholar 

  41. Durillo, J.J., Nebro, A.J., Coello, C.A.C., Garcia-Nieto, J., Luna, F., Alba, E.: A study of multi-objective metaheuristics when solving parameter scalable problems. IEEE Trans. Evol. Comput. 14(4), 618–635 (2010)

    Article  Google Scholar 

  42. Laumanns, M., Deb, K., Thiele, L., Zitzler, E.: Evolutionary Multiobjective Optimization. Theoretical Advances and Applications. Scalable Test Problems for Evolutionary Multi-Objective Optimization. 105−145 (2005)

    Google Scholar 

  43. Barone, L., Huband, S., Hingston, P., While, L.: A review of multi-objective test problems and a scalable test problem toolkit. IEEE Trans. Evol. Comput. 10(5), 447–506 (2006)

    Google Scholar 

Download references

Acknowledgments

B. Dorronsoro acknowledges the support by the National Research Fund, Luxembourg (AFR contract no. 4017742). A. Santiago would like to thank CONACyT Mexico, for the support no. 360199.

Author information

Authors and Affiliations

  1. Instituto Tecnológico de Ciudad Madero, Ciudad Madero, Mexico

    Alejandro Santiago, Héctor Joaquín Fraire Huacuja, Claudia Gómez Santillan, Juan Javier González Barbosa & José Carlos Soto Monterrubio

  2. University of Lille, Lille, France

    Bernabé Dorronsoro

  3. University of Luxembourg, Luxembourg, Luxembourg

    Johnatan E. Pecero

Authors
  1. Alejandro Santiago
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Héctor Joaquín Fraire Huacuja
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Bernabé Dorronsoro
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Johnatan E. Pecero
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Claudia Gómez Santillan
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Juan Javier González Barbosa
    View author publications

    You can also search for this author in PubMed Google Scholar

  7. José Carlos Soto Monterrubio
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Héctor Joaquín Fraire Huacuja .

Editor information

Editors and Affiliations

  1. Division of Graduate Studies and Research, Tijuana Institute of Technology, Tijuana, Mexico

    Oscar Castillo

  2. Division of Graduate Studies and Research, Tijuana Institute of Technology, Tijuana, Mexico

    Patricia Melin

  3. Department of Electrical and Computer Engineering, University of Alberta, Edmonton, Alberta, Canada

    Witold Pedrycz

  4. Systems Research Institute, Polish Academy of Sciences, Warsaw, Poland

    Janusz Kacprzyk

Rights and permissions

Reprints and permissions

Copyright information

© 2014 Springer International Publishing Switzerland

About this chapter

Cite this chapter

Santiago, A. et al. (2014). A Survey of Decomposition Methods for Multi-objective Optimization. In: Castillo, O., Melin, P., Pedrycz, W., Kacprzyk, J. (eds) Recent Advances on Hybrid Approaches for Designing Intelligent Systems. Studies in Computational Intelligence, vol 547. Springer, Cham. https://doi.org/10.1007/978-3-319-05170-3_31

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-05170-3_31

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-05169-7

  • Online ISBN: 978-3-319-05170-3

  • eBook Packages: EngineeringEngineering (R0)

Publish with us

Policies and ethics

Search

Navigation