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

A decomposition-based evolutionary algorithm for scalable multi/many-objective optimization

  • Regular Research Paper
  • Published:
Memetic Computing Aims and scope Submit manuscript

Abstract

The aim of evolutionary multi/many-objective optimization is to obtain a set of Pareto-optimal solutions with good trade-off among the multiple conflicting objectives. However, the convergence and diversity of multiobjective evolutionary algorithms often seriously decrease with the number of objectives and decision variables increasing. In this paper, we present a decomposition-based evolutionary algorithm for solving scalable multi/many-objective problems. The key features of the algorithm include the following three aspects: (1) a resource allocation strategy to coordinate the utility value of subproblems for good coverage; (2) a multioperator and multiparameter strategy to improve adaptability and diversity of the population; and (3) a bidirectional local search strategy to prevent the decrease in exploration capability during the early stage and increase the exploitation capability during the later stage of the search process. The performance of the proposed algorithm is benchmarked extensively on a set of scalable multi/many-objective optimization problems. The statistical comparisons with seven state-of-the-art algorithms verify the efficacy and potential of the proposed algorithm for scalable multi/many-objective problems.

This is a preview of subscription content, log in via an institution to check access.

Access this article

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

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Ponsich A, Jaimes AL, Coello CAC (2012) A survey on multiobjective evolutionary algorithms for the solution of the portfolio optimization problem and other finance and economics applications. IEEE Trans Evol Comput 17(3):321–344

    Article  Google Scholar 

  2. Mardle S, Miettinen K (1999) Nonlinear multiobjective optimization. J Oper Res Soc 51(2):246

    Article  Google Scholar 

  3. Deb K, Pratap A, Agarwal S, Meyarivan T (2002) A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans Evol Comput 6(2):182–197

    Article  Google Scholar 

  4. Cheng R, Jin Y, Narukawa K, Sendhoff B (2015) A multiobjective evolutionary algorithm using gaussian process-based inverse modeling. IEEE Trans Evol Comput 19(6):1–1

    Article  Google Scholar 

  5. Zitzler E, Laumanns M, Thiele L (2001) SPEA2: improving the strength Pareto evolutionary algorithm for multiobjective optimization. Evolutionary methods for design. In: Optimization and control with applications to industrial problems, Athens, pp 95–100

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

    Article  Google Scholar 

  7. Bader J, Zitzler E (2011) HypE: An algorithm for fast hypervolume-based many-objective optimization. Evol Comput 19(1):45–76

    Article  Google Scholar 

  8. Beume N, Naujoks B, Emmerich M (2007) SMS-EMOA: multiobjective selection based on dominated hypervolume. Eur J Oper Res 181(3):1653–1669

    Article  MATH  Google Scholar 

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

    Article  Google Scholar 

  10. 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(2):117–132

    Article  Google Scholar 

  11. Brockhoff D, Wagner T, Trautmann H (2015) R2 indicator-based multiobjective search. Evol Comput 23(3):369–395

    Article  Google Scholar 

  12. Murata T (2001) Specification of genetic search directions in cellular multi-objective genetic algorithm. Evol Multi Criter Opt EMO 1993:82–95

    MathSciNet  Google Scholar 

  13. Sato H (2015) Analysis of inverted PBI and comparison with other scalarizing functions in decomposition based MOEAs. J Heuristics 21(6):819–849

    Article  Google Scholar 

  14. Yang S, Jiang S, Jiang Y (2017) Improving the multiobjective evolutionary algorithm based on decomposition with new penalty schemes. Soft Comput 21(16):4677–4691

    Article  Google Scholar 

  15. Ma X, Zhang Q, Yang J, Zhu Z (2017) On Tchebycheff decomposition approaches for multi-objective evolutionary optimization. IEEE Trans Evol Comput 22(2):226–224

    Article  Google Scholar 

  16. Das I, Dennis J (1998) Normal-boundary intersection: a new method for generating the Pareto surface in nonlinear multicriteria optimization problems. SIAM J Optim 8(3):631–657

    Article  MathSciNet  MATH  Google Scholar 

  17. Zhang Q, Li H, Maringer D, Tsang E (2010) MOEA/D with NBI-style Tchebycheff approach for portfolio management. In: 2010 IEEE congress on evolutionary computation (CEC). IEEE, pp 1–8

  18. Zheng W, Tan Y, Meng L, Zhang H (2018) An improved MOEA/D design for many-objective optimization problems. Appl Intell 48(10):3839–3861

    Article  Google Scholar 

  19. Ishibuchi H, Sakane Y, Tsukamoto N, Nojima Y (2009) Adaptation of scalarizing functions in MOEA/D: an adaptive scalarizing function-based multiobjective evolutionary algorithm. In: International conference on evolutionary multi-criterion optimization. Springer, pp 1–8

  20. Wu M, Li K, Kwong S, Zhang Q, Zhang J (2019) Learning to decompose: a paradigm for decomposition-based multiobjective optimization. IEEE Trans Evol Comput 23(3):376–390

    Article  Google Scholar 

  21. Wang R, Zhang Q, Zhang T (2016) Decomposition-based algorithms using Pareto adaptive scalarizing methods. IEEE Trans Evol Comput 20(6):821–837

    Article  Google Scholar 

  22. Liu H, Gu F, Zhang Q (2014) Decomposition of a multiobjective optimization problem into a number of simple multiobjective subproblems. IEEE Trans Evol Comput 18(3):450–455

    Article  Google Scholar 

  23. Zhang Y, Yang R, Zuo J, Jing X (2015) Enhancing MOEA/D with uniform population initialization, weight vector design and adjustment using uniform design. J Syst Eng Elect 26(5):1010–1022

    Article  Google Scholar 

  24. Jain H, Deb K (2013) An evolutionary many-objective optimization algorithm using reference-point based nondominated sorting approach, part II: handling constraints and extending to an adaptive approach. IEEE Trans Evol Comput 18(4):602–622

    Article  Google Scholar 

  25. Qi Y, Ma X, Liu F, Jiao L, Sun J, Wu J (2014) MOEA/D with adaptive weight adjustment. Evol Comput 22(2):231

    Article  Google Scholar 

  26. Ma X, Liu F, Qi Y, Li L, Jiao L, Deng X, Wu J (2016) MOEA/D with biased weight adjustment inspired by user preference and its application on multi-objective reservoir flood control problem. Soft Comput 20(12):4999–5023

    Article  Google Scholar 

  27. Zhang Q, Liu W, Li H (2009) The performance of a new version of MOEA/D on CEC09 unconstrained MOP test instances. In: 2009 IEEE congress on evolutionary computation (CEC). IEEE, pp 203–208

  28. Kang Q, Song X, Zhou M (2018) A collaborative resource allocation strategy for decomposition-based multiobjective evolutionary algorithms. IEEE Trans Syst Man Cybern Syst 49(12):2416–2423

    Article  Google Scholar 

  29. Zhou A, Zhang Q (2015) Are all the subproblems equally important? Resource allocation in decomposition-based multiobjective evolutionary algorithms. IEEE Trans Evol Comput 20(1):52–64

    Article  Google Scholar 

  30. Wang P, Zhu W, Liu H (2019) A new resource allocation strategy based on the relationship between subproblems for MOEA/D. Inf Sci 501:337–362

    Article  MathSciNet  MATH  Google Scholar 

  31. Li H, Zhang Q (2008) Multiobjective optimization problems with complicated Pareto sets, MOEA/D and NSGA-II. IEEE Trans Evol Comput 13(2):284–302

    Article  Google Scholar 

  32. Chiang T, Lai Y (2011) MOEA/D-AMS: improving MOEA/D by an adaptive mating selection mechanism. In: 2011 IEEE congress on evolutionary computation (CEC). IEEE, pp 1473–1480

  33. Jiang S, Yang S (2015) An improved multiobjective optimization evolutionary algorithm based on decomposition for complex Pareto fronts. IEEE Trans Cybern 46(2):421–437

    Article  Google Scholar 

  34. Wang Z, Zhang Q, Gong M, Zhou A (2014) A replacement strategy for balancing convergence and diversity in MOEA/D. In: 2014 IEEE congress on evolutionary computation (CEC). IEEE, pp 2132–2139

  35. Wang Z, Zhang Q, Zhou A, Gong M, Jiao L (2015) Adaptive replacement strategies for MOEA/D. IEEE Trans Cybern 46(2):474–486

    Article  Google Scholar 

  36. Huang W, Li H (2010). On the differential evolution schemes in MOEA/D. In: 2010 sixth international conference on natural computation. IEEE, pp 2788–2792

  37. Li H, Zhang Q, Deng J (2016) Biased multiobjective optimization and decomposition algorithm. IEEE Trans Cybern 47(1):52–66

    Article  Google Scholar 

  38. Huang W, Li H (2010) On the differential evolution schemes in MOEA/D. In: Sixth international conference on natural computation, vol 6. IEEE, pp 2788–2792

  39. Chong JK (2016) A novel multi-objective memetic algorithm based on opposition-based self-adaptive differential evolution. Memet Comput 8(2):147–165

    Article  Google Scholar 

  40. Venske SM, Gonçalves RA, Delgado MR (2014) ADEMO/D: multiobjective optimization by an adaptive differential evolution algorithm. Neurocomputing 127(127):65–77

    Article  Google Scholar 

  41. Shim V A, Tan. KC, Tan K (2012) A hybrid adaptive evolutionary algorithm in the domination-based and decomposition-based frameworks of multi-objective optimization. Evol Comput 1–8

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

    Article  Google Scholar 

  43. Zheng X, Wang L (2016) A collaborative multiobjective fruit fly optimization algorithm for the resource constrained unrelated parallel machine green scheduling problem. IEEE Trans Syst Man Cybern Syst 48(5):790–800

    Article  Google Scholar 

  44. Paterakis N, Gibescu M, Bakirtzis AG, Catalão JPS (2017) A multi-objective optimization approach to risk-constrained energy and reserve procurement using demand response. IEEE Trans Power Syst 33(4):3940–3954

    Article  Google Scholar 

  45. Fan Z, Fang Y, Li W, Cai X, Wei C (2019) MOEA/D with angle-based constrained dominance principle for constrained multi-objective optimization problems. Appl Soft Comput 74:621–633

    Article  Google Scholar 

  46. Liu J, Gong M, Miao Q, Wang X, Li H (2017) Structure learning for deep neural networks based on multiobjective optimization. IEEE Trans Neural Net Learn Syst 29(6):2450–2463

    Article  MathSciNet  Google Scholar 

  47. Xu Y, Ding O, Qu R, Li K (2018) Hybrid multi-objective evolutionary algorithms based on decomposition for wireless sensor network coverage optimization. Appl Soft Comput 68:268–282

    Article  Google Scholar 

  48. Deb K, Jain H (2013) An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: solving problems with box constraints. IEEE Trans Evol Comput 18(4):577–601

    Article  Google Scholar 

  49. Li K, Deb K, Zhang Q, Kwong S (2014) An evolutionary many-objective optimization algorithm based on dominance and decomposition. IEEE Trans Evol Comput 19(5):694–716

    Article  Google Scholar 

  50. Sun Y, Yen GG, Yi Z (2018) IGD indicator-based evolutionary algorithm for many-objective optimization problems. IEEE Trans Evol Comput 23(2):173–187

    Article  Google Scholar 

  51. Yuan Y, Xu H, Wang B, Zhang B, Yao X (2015) Balancing convergence and diversity in decomposition-based many-objective optimizers. IEEE Trans Evol Comput 20(2):180–198

    Article  Google Scholar 

  52. Gu F, Cheung Y (2017) Self-organizing map-based weight design for decomposition-based many-objective evolutionary algorithm. IEEE Trans Evol Comput 22(2):211–225

    Article  Google Scholar 

  53. Cheng R, Jin Y, Olhofer M, Sendhoff B (2016) A reference vector guided evolutionary algorithm for many-objective optimization. IEEE Trans Evol Comput 20(5):773–791

    Article  Google Scholar 

  54. Jeyakumar G, Velayutham CS (2013) Distributed mixed variant differential evolution algorithms for unconstrained global optimization. Memet Comput 5(4):275–293

    Article  Google Scholar 

  55. Wang Y, Cai Z, Zhang Q (2011) Differential evolution with composite trial vector generation strategies and control parameters. IEEE Trans Evol Comput 15(1):55–66

    Article  Google Scholar 

  56. Mallipeddi R, Suganthan PN (2010) Differential evolution algorithm with ensemble of parameters and mutation and crossover strategies. In: International conference on swarm, evolutionary, and memetic computing. Springer, pp 71–78

  57. Wang Z, Ong Y-S, Ishibuchi H (2018) On scalable multiobjective test problems with hardly dominated boundaries. IEEE Trans Evol Comput 23(2):217–231

    Article  Google Scholar 

  58. Wang Z, Ong Y-S, Sun J, Gupta A, Zhang Q (2018) A generator for multiobjective test problems with difficult-to-approximate pareto front boundaries. IEEE Trans Evol Comput 23(4):556–571

    Article  Google Scholar 

  59. Zitzler E, Deb K, Thiele L (2000) Comparison of multiobjective evolutionary algorithms: empirical results. Evol Comput 8(2):173–195

    Article  Google Scholar 

  60. 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

  61. Deb K, Thiele L, Laumanns M (2005) Scalable test problems for evolutionary multiobjective optimization. In: Evolutionary multiobjective optimization. Springer, pp 105–145

  62. Huband S, Hingston P, Barone L, While L (2006) A review of multiobjective test problems and a scalable test problem toolkit. IEEE Trans Evol Comput 10(5):477–506

    Article  MATH  Google Scholar 

  63. Cheng R, Li M, Tian Y, Zhang X, Yang S, Jin Y, Yao X (2017) A benchmark test suite for evolutionary many-objective optimization. Comp Intell Syst 3(1):67–81

    Article  Google Scholar 

  64. Li H, Deb K, Zhang Q, Suganthan PN, Chen L (2019) Comparison between MOEA/D and NSGA-III on a set of novel many and multi-objective benchmark problems with challenging difficulties. Swarm Evol Comput 46:104–117

    Article  Google Scholar 

  65. Tian Y, Cheng R, Zhang X, Jin Y (2017) PlatEMO: A MATLAB platform for evolutionary multi-objective optimization. IEEE Comput Intell Mag 12(4):73–87

    Article  Google Scholar 

  66. Gong D, Xu B, Zhang Y, Guo Y, Yang S (2019) A similarity-based cooperative co-evolutionary algorithm for dynamic interval multi-objective optimization problems. IEEE Trans Evol Comput 24(1):142–156

    Article  Google Scholar 

  67. Wilcoxon F (1945) Individual comparisons by ranking methods. Biomet Bull 1(6):80–83

    Article  Google Scholar 

Download references

Acknowledgements

This work was supported in part by the National Key Research and Development Program of China under Grant 2018YFB1701104, the National Natural Science Foundation of China under Grant 61988101, the Xingliao Plan of Liaoning Province, China under Grant XLYC1808001 and the Science & Technology program of Liaoning Province, China under Grant 2020JH2/10500001 and 2020JH1/10100008.

Author information

Authors and Affiliations

  1. State Key Laboratory of Synthetical Automation for Process Industries, Northeastern University, Shenyang, China

    Jiaxin Chen, Jinliang Ding & Qingda Chen

  2. Department of Computing, Hong Kong Polytechnic University, Hong Kong, SAR, China

    Kay Chen Tan

Authors
  1. Jiaxin Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jinliang Ding
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Kay Chen Tan
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Qingda Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jinliang Ding.

Ethics declarations

Conflict of interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Supplementary Information

Below is the link to the electronic supplementary material.

Supplementary file1 (DOCX 8386 kb)

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Chen, J., Ding, J., Tan, K.C. et al. A decomposition-based evolutionary algorithm for scalable multi/many-objective optimization. Memetic Comp. 13, 413–432 (2021). https://doi.org/10.1007/s12293-021-00330-z

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12293-021-00330-z

Keywords

Search

Navigation