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

A point crowding-degree based evolutionary algorithm for many-objective optimization

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

Abstract

It is well known that many-objective optimization problems (MaOPs) are difficultly to be balanced diversity and convergence in the search process because diversity and convergence contradict each other. The method of evaluating the diversity of the solution set can directly affect the final performances of the algorithms. In this article, a point crowding-degree (PC) strategy is proposed to evaluate the diversity of solutions. The proposed PC strategy not only considers the distance between any two points as large as possible, but also considers the gap between each dimension component as large as possible. Moreover, The PC only ponders the influence of surrounding neighbor points on the diversity of a point. A selection strategy is designed to balance convergence and diversity. Based on all, a point crowding-degree based evolutionary algorithm (PCEA) for many-objective optimization problems is proposed. The PCEA is compared experimentally with several state-of-the-art algorithms on the 57 many-objective benchmark functions and the experimental results show that the proposed PCEA algorithm has strong competitiveness and better overall performance. In addition, the proposed PC strategy is integrated into other advanced MaOPs methods. The results show that it is beneficial to improve the performance of other MaOEAs algorithms.

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
$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

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Algorithm 1
Algorithm 2
Algorithm 3
Fig. 1
Fig. 2

Similar content being viewed by others

Explore related subjects

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

References

  1. Luo N, Ye Y, Lin W, Lin Q, Leung VCM (2023) A novel multimodal multiobjective memetic algorithm with a local detection mechanism and a clustering-based selection strategy. Memetic Comput 15:31–43

    Article  Google Scholar 

  2. Jiang Q, Cui J, Wang L, Lin Y, Wu Y, Hei X (2023) A regularity model-based multi-objective estimation of distribution memetic algorithm with auto-controllable population diversity. Memetic Comput 15:45–70

    Article  Google Scholar 

  3. Wei Z, Gao W, Gong M, Yen GG (2022) A bi-objective evolutionary algorithm for multimodal multi-objective optimization. IEEE Trans Evol Comput 1–1

  4. Wei Z, Gao W, Li G, Zhang Q (2022) A penalty-based differential evolution for multimodal optimization. IEEE Trans Cybern 52(7):6024–6033

    Article  Google Scholar 

  5. Gao W, Wei Z, Gong M, Yen GG (2021) Solving expensive multimodal optimization problem by a decomposition differential evolution algorithm. IEEE Trans Cybern 1–11

  6. Gao W, Li Y (2023) Solving a new test set of nonlinear equation systems by evolutionary algorithm. IEEE Trans Cybern 53(1):406–415

    Article  Google Scholar 

  7. Lapucci M, Mansueto P, Schoen F (2023) A memetic procedure for global multi-objective optimization. Math Program Comput 15:227–267

    Article  MathSciNet  MATH  Google Scholar 

  8. Saikia R, Sharma D (2021) Reference-lines-steered memetic multi-objective evolutionary algorithm with adaptive termination criterion. Memetic Comput 13:49–67

    Article  Google Scholar 

  9. Ge H, Zhang N, Sun L, Wang X, Hou Y (2022) A memetic evolution system with statistical variable classification for large-scale many-objective optimization. Appl Soft Comput 114:108158

    Article  Google Scholar 

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

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

    Article  Google Scholar 

  12. Chen ZG, Zhan ZH, Lin Y, Gong YJ, Gu TL, Zhao F, Yuan HQ, Chen X, Li Q, Zhang J (2019) Multiobjective cloud workflow scheduling: a multiple populations ant colony system approach. IEEE Trans Cybern 49(8):2912–2926

    Article  Google Scholar 

  13. Wu M, Li K, Kwong S, Zhang Q (2020) Evolutionary many-objective optimization based on adversarial decomposition. IEEE Trans Cybern 50(2):753–764

    Article  Google Scholar 

  14. Hadka D, Reed P (2013) Borg: an auto-adaptive many-objective evolutionary computing framework. Evol Comput 21(2):231–259

    Article  Google Scholar 

  15. He Z, Yen GG, Zhang J (2014) Fuzzy-based pareto optimality for many-objective evolutionary algorithms. IEEE Trans Evol Comput 18(2):269–285

    Article  Google Scholar 

  16. Yang S, Li M, Liu X, Zheng J (2013) A grid-based evolutionary algorithm for many-objective optimization. IEEE Trans Evol Comput 17(5):721–736

    Article  Google Scholar 

  17. Zhang X, Tian Y, Jin Y (2015) A knee point-driven evolutionary algorithm for many-objective optimization. IEEE Trans Evol Comput 19(6):761–776

    Article  Google Scholar 

  18. Li M, Yang S, Liu X (2014) Shift-based density estimation for pareto-based algorithms in many-objective optimization. IEEE Trans Evol Comput 18(3):348–365

    Article  Google Scholar 

  19. Liu Y, Gong D, Sun J, Jin Y (2017) A many-objective evolutionary algorithm using a one-by-one selection strategy. IEEE Trans Cybern 47(9):2689–2702

    Article  Google Scholar 

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

    Article  Google Scholar 

  21. Emmerich M, Beume N, Naujoks B (2005) An EMO algorithm using the hypervolume measure as selection criterion. International conference on evolutionary multi-criterion optimization. Springer, Berlin, Heidelberg, pp 62–76

    Chapter  MATH  Google Scholar 

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

    Article  Google Scholar 

  23. Brockhoff D, Wagner T, Trautmann H (2012) On the properties of the R2 indicator. In: GECCO’12 - proceedings of the 14th international conference on genetic and evolutionary computation, 07/07

  24. Bosman PAN, Thierens D (2003) The balance between proximity and diversity in multiobjective evolutionary algorithms. IEEE Trans Evol Comput 7(2):174–188

    Article  Google Scholar 

  25. Gómez RH, Coello CAC (2015) Improved metaheuristic based on the R2 indicator for many-objective optimization. In: Proceedings of the 2015 annual conference on genetic and evolutionary computation, Madrid, Spain, pp 679–686

  26. Zitzler E, Künzli S (2004) Indicator-based selection in multiobjective search. Springer, Berlin, Heidelberg

    Book  Google Scholar 

  27. Schutze O, Esquivel X, Lara A, Coello C (2012) Using the averaged Hausdorff distance as a performance measure in evolutionary multiobjective optimization. Evol Comput IEEE Trans 16:504–522

    Article  Google Scholar 

  28. Wang H, Jin Y, Yao X (2017) Diversity assessment in many-objective optimization. IEEE Trans Cybern 47(6):1510–1522

    Article  Google Scholar 

  29. Tian Y, Cheng R, Zhang X, Li M, Jin Y (2019) Diversity assessment of multi-objective evolutionary algorithms: performance metric and benchmark problems [research frontier]. IEEE Comput Intell Mag 14(3):61–74

    Article  Google Scholar 

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

  31. Deb K, Jain H (2014) 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 

  32. Jiang S, Yang S (2017) A strength pareto evolutionary algorithm based on reference direction for multiobjective and many-objective optimization. IEEE Trans Evol Comput 21(3):329–346

    Article  Google Scholar 

  33. Parsons L, Haque E, Liu H (2004) Subspace clustering for high dimensional data: a review. SIGKDD Explor. 6:90–105

    Article  Google Scholar 

  34. Adra SF, Fleming PJ (2011) Diversity management in evolutionary many-objective optimization. IEEE Trans Evol Comput 15(2):183–195

    Article  Google Scholar 

  35. Sun J, Gong D, Zeng X, Geng N (2018) An ensemble framework for assessing solutions of interval programming problems. Inf Sci 436–437:146–161

    Article  MathSciNet  MATH  Google Scholar 

  36. Storn R, Price K (1997) Differential evolution - a simple and efficient heuristic for global optimization over continuous spaces. J Global Optim 11:341–359

    Article  MathSciNet  MATH  Google Scholar 

  37. Agrawal R, Deb K, Agrawal R (2000) Simulated binary crossover for continuous search space. Complex Systems 9:115–148

    MathSciNet  MATH  Google Scholar 

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

  39. Tian Y, Cheng R, Zhang X, Su Y, Jin Y (2019) A strengthened dominance relation considering convergence and diversity for evolutionary many-objective optimization. IEEE Trans Evol Comput 23(2):331–345

    Article  Google Scholar 

  40. Tian Y, He C, Cheng R, Zhang X (2021) A multistage evolutionary algorithm for better diversity preservation in multiobjective optimization. IEEE Trans Syst Man Cybern Syst 51(9):5880–5894

    Article  Google Scholar 

  41. Xiang Y, Zhou Y, Li M, Chen Z (2017) A vector angle-based evolutionary algorithm for unconstrained many-objective optimization. IEEE Trans Evol Comput 21(1):131–152

    Article  Google Scholar 

  42. Tian Y, Cheng R, Zhang X, Jin Y (2017) PlatEMO: a MATLAB platform for evolutionary multi-objective optimization [Educational Forum]. IEEE Comput Intell Mag 12(4):73–87. https://doi.org/10.1109/MCI.2017.2742868

    Article  Google Scholar 

  43. Cheng MLR, Tian Y, Xiang X, Zhang X, Yang S, Jin Y, Yao X (2017) Benchmark functions for the CEC’2018 competition on many-objective optimization.’ CERCIA, School Comput. Sci., Univ. Birmingham Edgbaston, Birmingham, U.K., vol. Tech. Rep. CSR-17-01

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

    Article  Google Scholar 

  45. Steel JHTRDG, Dickey DA (1997) Principles and procedures of statistics: A biometrical approach. McGraw-Hill, New York, NY

    Google Scholar 

Download references

Acknowledgements

This work was supported by National Natural Science Foundations of China [No.12271326, No. 61806120, No. 61502290, No. 61401263, No. 61672334, No. 61673251], China Postdoctoral Science Foundation [No. 2015M582606], Industrial Research Project of Science and Technology in Shaanxi Province [No. 2015GY016, No. 2017JQ6063], Fundamental Research Fund for the Central Universities [No. GK202003071], Natural Science Basic Research Plan in Shaanxi Province of China [No. 2022JM-354].

Author information

Authors and Affiliations

  1. School of Computer Science, Shaanxi Normal University, No. 620, West Chang’an Avenue, Xi’an, 710119, Shaanxi, China

    Cai Dai, Cheng Peng & Xiujuan Lei

Authors
  1. Cai Dai
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Cheng Peng
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Xiujuan Lei
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Cai Dai.

Ethics declarations

Conflict of interest

The authors declare that they have no competing interests.

Additional information

Publisher's Note

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

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Dai, C., Peng, C. & Lei, X. A point crowding-degree based evolutionary algorithm for many-objective optimization. Memetic Comp. 15, 391–403 (2023). https://doi.org/10.1007/s12293-023-00398-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12293-023-00398-9

Keywords

Search

Navigation