nach oben

Computing

Erschienen in:

15.03.2024 | Regular Paper

An improved indicator-based two-archive algorithm for many-objective optimization problems

verfasst von: Weida Song, Shanxin Zhang, Wenlong Ge, Wei Wang

Erschienen in: Computing | Ausgabe 5/2024

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The large number of objectives in many-objective optimization problems (MaOPs) has posed significant challenges to the performance of multi-objective evolutionary algorithms (MOEAs) in terms of convergence and diversity. To design a more balanced MOEA, a multiple indicator-based two-archive algorithm named IBTA is proposed to deal with problems with complicated Pareto fronts. Specifically, a two-archive framework is introduced to focus on convergence and diversity separately. In IBTA, we assign different selection principles to the two archives. In the convergence archive, the inverted generational distance with noncontributing solution detection (IGD-NS) indicator is applied to choose the solutions with favorable convergence in each generation. In the diversity archive, we use crowdedness and fitness to select solutions with favorable diversity. To evaluate the performance of IBTA on MaOPs, we compare it with several state-of-the-art MOEAs on various benchmark problems with different Pareto fronts. The experimental results demonstrate that IBTA can deal with multi-objective optimization problems (MOPs)/MaOPs with satisfactory convergence and diversity.

Vorheriger Artikel Efficient processing of all neighboring object group queries with budget range constraint in road networks

Nächster Artikel Reducing the wrapping effect of set computation via Delaunay triangulation for guaranteed state estimation of nonlinear discrete-time systems

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

For \( x_1, x_2 \in X \), \(x_1\) Pareto dominates \(x_2\)(denoted as \(x_1 \prec x_2\)) means: 1) for all objectives, \(f_i(x_1) \le f_i(x_2)\) \(i = 1,..., m\), and 2) at least one objective satisfies that \(f_j(x_1) < f_j(x_2)\). Sequentially, A solution \(x^* \in X\) is Pareto optimal if there is no solution \(x \in X \) satisfies \(x \succ x^* \).

Farina M, Amato P (2002) On the optimal solution definition for many-criteria optimization problems. In: 2002 annual meeting of the North American fuzzy information processing society proceedings. NAFIPS-FLINT 2002 (Cat. No. 02TH8622), pp 233–238

Li B, Li J, Tang K, Yao X (2015) Many-objective evolutionary algorithms: a survey. ACM Comput Surv 48(1):1–35CrossRef

Coello CDA, Van Veldhuizen CA, Lamont GB (2007) Evolutionary algorithms for solving multi-objective problems. Springer, New York

Ishibuchi H, Yu S, Masuda H, Nojima Y (2017) Performance of decomposition-based many-objective algorithms strongly depends on pareto front shapes. IEEE Trans Evol Comput 21(2):169–190CrossRef

Falcón-Cardona JG, Emmerich MTM, Coello CCA (2019a) On the cooperation of multiple indicator-based multi-objective evolutionary algorithms. In: 2019 IEEE congress on evolutionary computation (CEC), pp 2050–2057

Falcón-Cardona JG, Ishibuchi H, Coello CC (2020) A Exploiting the trade-off between convergence and diversity indicators. In: 2020 IEEE symposium series on computational intelligence (SSCI), pp 141–148

Gómez RH, Coello CA (2017) A hyper-heuristic of scalarizing functions. Association for Computing Machinery

Falcón-Cardona JG, Coello Coello CA, Emmerich M (2019b) CRI-EMOA: a pareto-front shape invariant evolutionary multi-objective algorithm. In: Evolutionary multi-criterion optimization, Springer International Publishing, pp 307–318

Márquez-Vega LA, Falcón-Cardona JG, COE (2021) Towards a pareto front shape invariant multi-objective evolutionary algorithm using pair-potential functions. In: Advances in computational intelligence, Springer International Publishing, pp 369–382

10.

Wang Z, Zhang Q, Li H, Ishibuchi H, Jiao L (2017) On the use of two reference points in decomposition based multiobjective evolutionary algorithms. Swarm Evol Comput 34:89–102CrossRef

11.

Saborido R, Ruiz AB, Luque M (2017) Global WASF-GA: an evolutionary algorithm in multiobjective optimization to approximate the whole pareto optimal front. Evolut Comput 25(2):309–349CrossRef

12.

Hoai NB, Bing X, Peter A, Hisao I, Mengjie Z (2020) Multiple reference points-based decomposition for multiobjective feature selection in classification: Static and dynamic mechanisms. IEEE Trans Evol Comput 24(1):170–184CrossRef

13.

Zhou Aimin Q, Bo-Yang LH, Shi-Zheng Z, Nagaratnam SP, Qingfu Z (2011) Multiobjective evolutionary algorithms: a survey of the state of the art. Swarm Evol Comput 1(1):32–49CrossRef

14.

Trivedi A, Srinivasan D, Sanyal K, Ghosh A (2017) A survey of multiobjective evolutionary algorithms based on decomposition. Trans Evol Comp 21(3):440–462

15.

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

16.

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–716CrossRef

17.

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–601CrossRef

18.

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–791CrossRef

19.

Asafuddoula M, Ray T, Sarker R (2015) A decomposition-based evolutionary algorithm for many objective optimization. IEEE Trans Evol Comput 19(3):445–460CrossRef

20.

Ishibuchi H, Hitotsuyanagi Y, Ohyanagi H, Nojima Y (2011) Effects of the existence of highly correlated objectives on the behavior of MOEA/D. In: Evolutionary multi-criterion optimization–6th international conference, EMO 2011, Ouro Preto, Brazil, April 5-8, 2011. Proceedings, pp 166–181

21.

Giagkiozis I, Purshouse RC, Fleming PJ (2012) Generalized decomposition and cross entropy methods for many-objective optimization. Inf Sci 21:169–190

22.

Sato H (2014) Inverted PBI in MOEA/D and its impact on the search performance on multi and many-objective optimization. In: Genetic and evolutionary computation conference (GECCO), Vancouver, pp 645–652

23.

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–197CrossRef

24.

Zitzler E, Laumanns M, Thiele L (2001) SPEA2: improving the strength pareto evolutionary algorithm for multiobjective optimization. In: Evolutionary methods for design, optimization and control with applications to industrial problems. Proceedings of the EUROGEN’2001. Athens. Greece, September 19-21, pp 95–100

25.

Corne DW, Jerram NR, Knowles JD, Oates MJ (2002) PESA-II: region-based selection in evolutionary multiobjective optimization. Morgan Kaufmann Publishers Inc., UK, pp 283–290

26.

Purshouse RC, Fleming PJ (2007) On the evolutionary optimization of many conflicting objectives. IEEE Trans Evol Comput 11(6):770–784CrossRef

27.

Ikeda K, Kita H, Kobayashi S (2001) Failure of pareto-based MOEAs: does non-dominated really mean near to optimal? In: Proceedings of the 2001 congress on evolutionary computation (IEEE Cat. No.01TH8546), vol. 2, pp 957–962

28.

Laumanns M, Thiele L, Deb K, Zitzler E (2002) Combining convergence and diversity in evolutionary multiobjective optimization. Evol Comput 10(3):263–282CrossRef

29.

Yuan Y, Xu H, Wang B, Yao X (2016) A new dominance relation-based evolutionary algorithm for many-objective optimization. IEEE Trans Evol Comput 20(1):16–37CrossRef

30.

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–736CrossRef

31.

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–365CrossRef

32.

Falcón-Cardona JG, Coello CA (2020) Indicator-based multi-objective evolutionary algorithms: a comprehensive survey. ACM Comput Surv 53(2):1–35CrossRef

33.

Zitzler E, Künzli S (2004) Indicator-based selection in multiobjective search. In: International conference on parallel problem solving from nature, pp 832–842

34.

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

35.

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

36.

Gómez RH, Coello CA (2015) Improved metaheuristic based on the R2 indicator for many-objective optimization. In: Genetic and evolutionary computation conference, pp 679–686

37.

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

38.

Coello Coello CA, Reyes Sierra M (2004) A study of the parallelization of a coevolutionary multi-objective evolutionary algorithm. In: Mexican international conference on artificial intelligence (MICAI), pp 688–697

39.

Brockhoff D, Wagner T, Trautmann H (2012) On the properties of the R2 indicator. In: Genetic and evolutionary computation conference, pp 465–472

40.

Wang H, Jiao L, Yao X (2015) Two_Arch2: an improved two-archive algorithm for many-objective optimization. IEEE Trans Evol Comput 19(4):524–541. https://doi.org/10.1109/TEVC.2014.2350987CrossRef

41.

Guillermo F-CJ, Hisao I, Coello Coello Carlos A, Michael E (2021) On the effect of the cooperation of indicator-based multiobjective evolutionary algorithms. IEEE Trans Evol Comput 25(4):681–695CrossRef

42.

Li B, Tang K, Li J, Yao X (2016) Stochastic ranking algorithm for many-objective optimization based on multiple indicators. IEEE Trans Evol Comput 20(6):924–938CrossRef

43.

Phan DH, Suzuki J (2011) Boosting indicator-based selection operators for evolutionary multiobjective optimization algorithms. In: 2011 IEEE 23rd international conference on tools with artificial intelligence, pp 276–281

44.

Phan DH, Suzuki J, Hayashi I (2012) Leveraging indicator-based ensemble selection in evolutionary multiobjective optimization algorithms. In: Proceedings of the 14th annual conference on genetic and evolutionary computation, pp 497–504

45.

Tian Y, Zhang X, Cheng R, Jin Y (2016) A multi-objective evolutionary algorithm based on an enhanced inverted generational distance metric. In: 2016 IEEE congress on evolutionary computation (CEC), pp 5222–5229

46.

Tian Y, Cheng R, Zhang X, Cheng F, Jin Y (2018) An indicator-based multiobjective evolutionary algorithm with reference point adaptation for better versatility. IEEE Trans Evol Comput 22(4):609–622CrossRef

47.

Glamsch J, Rosnitschek T, Rieg F (2021) Initial population influence on hypervolume convergence of NSGA-III. Int J Simul Modell 20(1):123–133CrossRef

48.

Zhou Y, Chen Z, Huang Z, Xiang Y (2022) A multiobjective evolutionary algorithm based on objective-space localization selection. IEEE Trans Cybern 52(5):3888–3901. https://doi.org/10.1109/TCYB.2020.3016426CrossRef

49.

He C, Cheng R, Yazdani D (2022) Adaptive offspring generation for evolutionary large-scale multiobjective optimization. IEEE Trans Syst Man Cyber Syst 52(2):786–798CrossRef

50.

He C, Cheng R, Li L, Tan KC, Jin Y (2022) Large-scale multiobjective optimization via reformulated decision variable analysis. IEEE Trans Evol Comput 28:1–1

51.

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–87CrossRef

52.

Indraneel D, Dennis JE (1998) Normal-boundary intersection: a new method for generating the pareto surface in nonlinear multicriteria optimization problems. SIAM J Optim 8(3):631–657MathSciNetCrossRef

53.

Agrawal RB, Deb K, Agrawal RB (1994) Simulated binary crossover for continuous search space. Complex Syst 9(3):115–148MathSciNet

54.

Deb K, Goyal M (1996) A combined genetic adaptive search (geneas) for engineering design. Comput Sci Inf 26(4):30–45

55.

Jain H, Deb K (2014) 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–622CrossRef

56.

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–74CrossRef

57.

Ishibuchi H, Masuda H, Tanigaki Y, Nojima Y (2015) Modified distance calculation in generational distance and inverted generational distance. In: Evolutionary multi-criterion optimization, Springer International Publishing, pp 110–125

58.

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

59.

Tian Y, Xiang X, Zhang X, Cheng R, Jin Y (2018b) Sampling reference points on the pareto fronts of benchmark multi-objective optimization problems. In: 2018 IEEE congress on evolutionary computation (CEC), pp 1–6

Titel: An improved indicator-based two-archive algorithm for many-objective optimization problems
verfasst von: Weida Song
Shanxin Zhang
Wenlong Ge
Wei Wang
Publikationsdatum: 15.03.2024
Verlag: Springer Vienna
Erschienen in: Computing / Ausgabe 5/2024
Print ISSN: 0010-485X
Elektronische ISSN: 1436-5057
DOI: https://doi.org/10.1007/s00607-024-01272-3

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Weitere Artikel der Ausgabe 5/2024

Many-BSP: an analytical performance model for CUDA kernels

Generalizing truth discovery by incorporating multi-truth features

SVFLDetector: a decentralized client detection method for Byzantine problem in vertical federated learning

Reducing the wrapping effect of set computation via Delaunay triangulation for guaranteed state estimation of nonlinear discrete-time systems

Solving the SAT problem with the string multiset rewriting calculus

Preference based multi-issue negotiation algorithm (PMINA) for fog resource allocation

Premium Partner