Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

On the Combined Impact of Population Size and Sub-problem Selection in MOEA/D

  • Conference paper
  • First Online:

Abstract

This paper intends to understand and to improve the working principle of decomposition-based multi-objective evolutionary algorithms. We review the design of the well-establishedMoea/d framework to support the smooth integration of different strategies for sub-problem selection, while emphasizing the role of the population size and of the number of offspring created at each generation. By conducting a comprehensive empirical analysis on a wide range of multi- and many-objective combinatorial NK landscapes, we provide new insights into the combined effect of those parameters on the anytime performance of the underlying search process. In particular, we show that even a simple random strategy selecting sub-problems at random outperforms existing sophisticated strategies. We also study the sensitivity of such strategies with respect to the ruggedness and the objective space dimension of the target problem.

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

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /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
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight 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

Similar content being viewed by others

References

  1. Aghabeig, M., Jaszkiewicz, A.: Experimental analysis of design elements of scalarizing function-based multiobjective evolutionary algorithms. Soft. Comput.23(21), 10769–10780 (2018).https://doi.org/10.1007/s00500-018-3631-x

    Article  Google Scholar 

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

    Article  Google Scholar 

  3. Cai, X., Li, Y., Fan, Z., Zhang, Q.: An external archive guided multiobjective evolutionary algorithm based on decomposition for combinatorial optimization. IEEE Trans. Evolut. Comput.19(4), 508–523 (2015)

    Article  Google Scholar 

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

    Google Scholar 

  5. Corus, D., Oliveto, P.S.: Standard steady state genetic algorithms can Hillclimb faster than mutation-only evolutionary algorithms. IEEE Trans. Evol. Comput.22(5), 720–732 (2018)

    Article  Google Scholar 

  6. Črepinšek, M., Liu, S.H., Mernik, M.: Exploration and exploitation in evolutionary algorithms: a survey. ACM Comput. Surv.45(3), 1–33 (2013)

    Article  Google Scholar 

  7. Deb, K.: Multi-objective Optimization Using Evolutionary Algorithms. Wiley, Hoboken (2001)

    MATH  Google Scholar 

  8. Glasmachers, T., Naujoks, B., Rudolph, G.: Start small, grow big? Saving multi-objective function evaluations. In: Bartz-Beielstein, T., Branke, J., Filipič, B., Smith, J. (eds.) PPSN 2014. LNCS, vol. 8672, pp. 579–588. Springer, Cham (2014).https://doi.org/10.1007/978-3-319-10762-2_57

    Chapter  Google Scholar 

  9. Ishibuchi, H., Imada, R., Masuyama, N., Nojima, Y.: Two-layered weight vector specification in decomposition-based multi-objective algorithms for many-objective optimization problems. In: CEC, pp. 2434–2441 (2019)

    Google Scholar 

  10. Lavinas, Y., Aranha, C., Ladeira, M.: Improving resource allocation in MOEA/D with decision-space diversity metrics. In: Martín-Vide, C., Pond, G., Vega-Rodríguez, M.A. (eds.) TPNC 2019. LNCS, vol. 11934, pp. 134–146. Springer, Cham (2019).https://doi.org/10.1007/978-3-030-34500-6_9

    Chapter  Google Scholar 

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

    Article  Google Scholar 

  12. Li, K., Zhang, Q., Kwong, S., Li, M., Wang, R.: Stable matching-based selection in evolutionary multiobjective optimization. IEEE TEC18(6), 909–923 (2014)

    Google Scholar 

  13. Marquet, G., Derbel, B., Liefooghe, A., Talbi, E.-G.: Shake them all! Rethinking selection and replacement in MOEA/D. In: Bartz-Beielstein, T., Branke, J., Filipič, B., Smith, J. (eds.) PPSN 2014. LNCS, vol. 8672, pp. 641–651. Springer, Cham (2014).https://doi.org/10.1007/978-3-319-10762-2_63

    Chapter  Google Scholar 

  14. Schumer, M., Steiglitz, K.: Adaptive step size random search. IEEE Trans. Autom. Control13(3), 270–276 (1968)

    Article  Google Scholar 

  15. Tanabe, R., Ishibuchi, H.: An analysis of control parameters of MOEA/D under two different optimization scenarios. Appl. Soft Comput.70, 22–40 (2018)

    Article  Google Scholar 

  16. Trivedi, A., Srinivasan, D., Sanyal, K., Ghosh, A.: A survey of multiobjective evolutionary algorithms based on decomposition. IEEE TEC21(3), 440–462 (2017)

    Google Scholar 

  17. Verel, S., Liefooghe, A., Jourdan, L., Dhaenens, C.: On the structure of multiobjective combinatorial search space: MNK-Landscapes with correlated objectives. Eur. J. Oper. Res.227(2), 331–342 (2013)

    Article MathSciNet  Google Scholar 

  18. Wang, P., et al.: A new resource allocation strategy based on the relationship between subproblems for MOEA/D. Inf. Sci.501, 337–362 (2019)

    Article MathSciNet  Google Scholar 

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

    Article  Google Scholar 

  20. Witt, C.: Population size versus runtime of a simple evolutionary algorithm. Theor. Comput. Sci.403(1), 104–120 (2008)

    Article MathSciNet  Google Scholar 

  21. Zapotecas-Martínez, S., Aguirre, H., Tanaka, K., Coello, C.: On the low-discrepancy sequences and their use in MOEA/D for high-dimensional objective spaces. In: Congress on Evolutionary Computation (CEC 2015), pp. 2835–2842 (2015)

    Google Scholar 

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

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

    Article  Google Scholar 

  24. Zitzler, E., Thiele, L., Laumanns, M., Fonseca, C.M., Grunert da Fonseca, V.: Performance assessment of multiobjective optimizers: an analysis and review. IEEE Trans. Evol. Comput.7(2), 117–132 (2003)

    Article  Google Scholar 

Download references

Acknowledgments

This work was supported by the French national research agency (ANR-16-CE23-0013-01) and the Research Grants Council of Hong Kong (RGC Project No. A-CityU101/16).

Author information

Authors and Affiliations

  1. University of Lille, CRIStAL, Inria, Lille, France

    Geoffrey Pruvost, Bilel Derbel & Arnaud Liefooghe

  2. University of Exeter, Exeter, UK

    Ke Li

  3. City University Hong Kong, Kowloon Tong, Hong Kong

    Qingfu Zhang

Authors
  1. Geoffrey Pruvost

    You can also search for this author inPubMed Google Scholar

  2. Bilel Derbel

    You can also search for this author inPubMed Google Scholar

  3. Arnaud Liefooghe

    You can also search for this author inPubMed Google Scholar

  4. Ke Li

    You can also search for this author inPubMed Google Scholar

  5. Qingfu Zhang

    You can also search for this author inPubMed Google Scholar

Corresponding authors

Correspondence toGeoffrey Pruvost,Bilel Derbel,Arnaud Liefooghe,Ke Li orQingfu Zhang.

Editor information

Editors and Affiliations

  1. University of Coimbra, Coimbra, Portugal

    Luís Paquete

  2. Aberystwyth University, Aberystwyth, UK

    Christine Zarges

Rights and permissions

Copyright information

© 2020 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Pruvost, G., Derbel, B., Liefooghe, A., Li, K., Zhang, Q. (2020). On the Combined Impact of Population Size and Sub-problem Selection in MOEA/D. In: Paquete, L., Zarges, C. (eds) Evolutionary Computation in Combinatorial Optimization. EvoCOP 2020. Lecture Notes in Computer Science(), vol 12102. Springer, Cham. https://doi.org/10.1007/978-3-030-43680-3_9

Download citation

Publish with us

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /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
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight 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

[8]ページ先頭
©2009-2025 Movatter.jp