A many-objective evolutionary algorithm based on vector angle distance scaling

Abstract

In the past two decades, multi-objective evolutionary algorithms (MOEAs) have achieved great success in solving two or three multi-objective optimization problems. As pointed out in some recent studies, however, MOEAs face many difficulties when dealing with many-objective optimization problems(MaOPs) on account of the loss of the selection pressure of the non-dominant candidate solutions toward the Pareto front and the ineffective design of the diversity maintenance mechanism. This paper proposes a many-objective evolutionary algorithm based on vector guidance. In this algorithm, the value of vector angle distance scaling(VADS) is applied to balance convergence and diversity in environmental selection. In addition, tournament selection based on the aggregate fitness value of VADS is applied to generate a high quality offspring population. Besides, we adopt an adaptive strategy to adjust the reference vector dynamically according to the scales of the objective functions. Finally, the performance of the proposed algorithm is compared with five state-of-the-art many-objective evolutionary algorithms on 52 instances of 13 MaOPs with diverse characteristics. Experimental results show that the proposed algorithm performs competitively when dealing many-objective with different types of Pareto front.

Keywords

Vector angle distance scaling evolutionary algorithm many-objective optimization problem

Get full access to this article

View all access options for this article.

References

Zhang

and Xing

, A Survey of Multiobjective Evolutionary Algorithms, 2017 IEEE International Conference on Computational Science and Engineering (CSE) and IEEE International Conference on Embedded and Ubiquitous Computing(EUC) 1 (2017), 93–100. doi: 10.1109/CSE-EUC.2017.27in.

Wang

, Su

, Lin

, Ma

, Gong

, Li

and Ming

, A survey of decomposition approaches in multiobjective evolutionary algorithms, Neurocomputing 408 (2020), 308–330. ISSN 0925-2312, doi: https://doi.org/10.1016/j.neucom.2020.01.114.

, Wang

, Jia

and Cui

, An intelligent braking system composed single-pedal and multi-objective optimization neural network braking control strategies for electric vehicle, Applied Energy 259 (2020), 114172. ISSN 0306-2619, doi: https://doi.org/10.1016/j.apenergy.2019.114172.

, Vaddi

and Wong

, Multi-objective Precision Optimization of Deep Neural Networks for Edge Devices, in: 2019 Design, Automation Test in Europe Conference Exhibition(DATE), 1100–1105, doi:10.23919/DATE.2019.8714785,2019

Tkachenko

, Izonin

, Kryvinska

, Dronyuk

and Zub

, An Approach towards Increasing Prediction Accuracy for the Recovery of Missing IoT Data Based on the GRNN-SGTM Ensemble, Sensors 20(9) (2020), 2625.

Izonin

, Tkachenko

, Verhun

and Zub

, An approach towardsmissing datamanagement using improved GRNNSGTM ensemble method, Engineering Science and Technology, an International Journal ISSN 2215–0986. doi: https://doi.org/10.1016/j.jestch.2020.10.005.

Deb

, Pratap

, Agarwal

and Meyarivan

, A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Transactions on Evolutionary Computation 6(2) (2002), 182–197. ISSN 1089-778X, doi: https://doi.org/10.1109/4235.996017.

Zitzler

, Laumanns

and Thiele

, SPEA2: Improving the strength Pareto evolutionary algorithm, TIK-report 103.

Corne

D.W.

, Jerram

N.R.

, Knowles

J.D.

and Oates

M.J.

, PESAII: Region-based selection in evolutionary multiobjective optimization, in: Proceedings of the 3rd Annual Conference on Genetic and Evolutionary Computation, Morgan Kaufmann Publishers Inc., (2001), 283–290.

10.

Ishibuchi

, Tsukamoto

and Nojima

, Evolutionary Many-Objective Optimization: A Short Review, (2008), 2419–2426, doi:10.1109/CEC.2008.4631121.

11.

, Li

, Tang

and Yao

, Many-Objective Evolutionary Algorithms: A Survey, ACM Comput Surv 48(1) ISSN 0360-0300, doi:10.1145/2792984, URL https://doi.org/10.1145/2792984.

12.

, Wang

, Zhang

and Ishibuchi

, Evolutionary Many-Objective Optimization: A Comparative Study of the Stateofthe-Art, IEEE Access 6 (2018), 26194–26214. ISSN 2169-3536, doi: https://doi.org/10.1109/ACCESS.2018.2832181.

13.

Laumanns

, Thiele

, Deb

and Zitzler

, Combining Convergence and Diversity in Evolutionary Multiobjective Optimization, Evolutionary Computation 10(3) (2002), 263–282.

14.

Deb

, Mohan

and Mishra

, Evaluating the epsilondomination based multi-objective evolutionary algorithm for a quick computation of Pareto-optimal solutions, Evolutionary Computation 13(4) (2014), 501–525.

15.

Ikeda

, Kita

and Kobayashi

, Failure of Pareto-based MOEAs: Does non-dominated really mean near to optimal?, 2 (2001), 957–962. doi: 10.1109/CEC.2001.934293

16.

Farina

and Amato

, A fuzzy definition of “optimality” for many-criteria optimization problems, IEEE Transactions on Systems Man and Cybernetics Part A Systems and Humans 34(3) (2004), 315–326.

17.

K?ppen

, Vicente-Garcia

and Nickolay

, Fuzzy-Pareto-Dominance and its Application in Evolutionary Multiobjective Optimization, in: C. A. Coello Coello, A. Hernĺćndez Aguirre, E. Zitzler (Eds.), Evolutionary Multi-Criterion Optimization, Springer Berlin Heidelberg, Berlin, Heidelberg, (2005), 399–412.

18.

Yang

, Li

, Liu

and Zheng

, A Grid-Based Evolutionary Algorithm for Many-Objective Optimization, IEEE Transactions on Evolutionary Computation 17(5) (2013), 721–736. doi: 10.1109/TEVC.2012.2227145

19.

Ląŕopez

, Coello

C.A.C.

, Oyama

and Fujii

, An Alternative Preference Relation to Deal with Many-Objective Optimization Problems, in: R. C. Purshouse, P. J. Fleming, C. M. Fonseca, S. Greco, J. Shaw (Eds.), Evolutionary Multi-Criterion Optimization, Springer Berlin Heidelberg, Berlin, Heidelberg, (2013), 291–306.

20.

, Yang

and Liu

, Shift-Based Density Estimation for Pareto-Based Algorithms in Many-Objective Optimization, IEEE Transactions on Evolutionary Computation 18(3) (2014), 348–365.

21.

Cheng

, Yen

G.G.

and Zhang

, A Many-Objective Evolutionary AlgorithmWith Enhanced Mating and Environmental Selections, IEEE Transactions on Evolutionary Computation 19(4) (2015), 592–605.

22.

Zhang

, Tian

and Jin

, A Knee Point-Driven Evolutionary Algorithm for Many-Objective Optimization, IEEE Transactions on Evolutionary Computation 19(6) (2015), 761–776. ISSN 1089-778X, doi: https://doi.org/10.1109/TEVC.2014.2378512.

23.

Beume

, Naujoks

and Emmerich

, SMS-EMOA: Multiobjective selection based on dominated hypervolume, European Journal of Operational Research 181(3) (2007), 1653–1669. ISSN 0377-2217, doi: https://doi.org/10.1016/j.ejor.2006.08.008.

24.

Bader

and Zitzler

, HypE: An algorithm for fast hypervolumebased many-objective optimization, Evolutionary Computation 19(1) (2011), 45–76.

25.

Coello

C.A.C.

, MOPSOhv: A new hypervolume-based multi-objective particle swarm optimizer, in: 2014 IEEE Congress on Evolutionary Computation (CEC) 1 (2014), 266–273. doi: 10.1109/CEC.2014.6900540.

26.

Trautmann

, Wagner

and Brockhoff

, R2-EMOA: Focused Multiobjective Search Using R2-Indicator-Based Selection, in: G. Nicosia, P. Pardalos (Eds.), Learning and Intelligent Optimization, Springer Berlin Heidelberg, Berlin, Heidelberg, (2013), 70–74.

27.

, Liu

, Tan

and Yu

, R2-MOPSO: A multi-objective particle swarm optimizer based on R2-indicator and decomposition, in: 2015 IEEE Congress on Evolutionary Computation (CEC), (2015), 3148–3155, doi:10.1109/CEC.2015.7257282

28.

Phan

D.H.

and Suzuki

, R2-IBEA: R2 indicator based evolutionary algorithm for multiobjective optimization, in: 2013 IEEE Congress on Evolutionary Computation (2013), 1836–1845. doi:10.1109/CEC.2013.6557783

29.

Coello Coello

C.A.

, Improved Metaheuristic Based on the R2 Indicator for Many-Objective Optimization, in: The, (2015), 679–686.

30.

, Cheng

, Liu

and Jin

, A two-stage R2 indicator based evolutionary algorithm for many-objective optimization, Applied Soft Computing 67 (2018), 245–260. ISSN 1568-4946, doi: https://doi.org/10.1016/j.asoc.2018.02.048.

31.

Villalobos

and Coello

, A New Multi-Objective Evolutionary Algorithm Based on a Performance Assessment Indicator 505–512. doi:10.1145/2330163.2330235, 2012

32.

Sun

, Yen

G.G.

and Yi

, IGD Indicator-Based Evolutionary Algorithm for Many-Objective Optimization Problems, IEEE Transactions on Evolutionary Computation 23(2) (2019), 173–187. doi: 10.1109/TEVC.2018.2791283

33.

Lopez

E.M.

and Coello

C.A.C.

, Improving the integration of the IGD+ indicator into the selection mechanism of a Multi-objective Evolutionary Algorithm, in: 2017 IEEE Congress on Evolutionary Computation (CEC), (2017), 2683–2690. doi:10.1109/CEC.2017.7969633

34.

Schutze

, Esquivel

, Lara

and Coello

C.A.C.

, Using the Averaged Hausdorff Distance as a Performance Measure in Evolutionary Multiobjective Optimization, IEEE Transactions on Evolutionary Computation 16(4) (2012), 504–522. doi: 10.1109/TEVC.2011.2161872

35.

Zhang

, Gong

, Hu

and Zhang

, Feature selection algorithm based on bare bones particle swarm optimization, Neurocomputing 148 (2015), 150–157.

36.

, Li

and Huang

, A Multi-Objective Evolutionary Algorithm Based on Principal Component Analysis and Grid Division, in: 2018 14th International Conference on Computational Intelligence and Security (CIS), (2018), 201–204. doi:10.1109/CIS2018.2018.00051

37.

Singh

H.K.

, Isaacs

and Ray

, A Pareto Corner Search Evolutionary Algorithm and Dimensionality Reduction in Many-Objective Optimization Problems, IEEE Transactions on Evolutionary Computation 15(4) (2011), 539–556.

38.

Bechikh

, Kessentini

, Said

L.B.

and Ghąäl?edira

, Preference Incorporation in Evolutionary Multiobjective Optimization: A Survey of the State-of-the-Art, Advances in Computers 98 (2015), 141–207.

39.

Bentley

P.J.

and Wakefield

J.P.

, Finding Acceptable Solutions in the Pareto-Optimal Range using Multiobjective Genetic Algorithms, in: P.K. Chawdhry, R. Roy, R.K. Pant (Eds.), Soft Computing in Engineering Design and Manufacturing, Springer London, (1998), 231–240.

40.

Thiele

, Miettinen

, Korhonen

P.J.

and Molina

, A Preference-Based Evolutionary Algorithm for Multi-Objective Optimization, Evolutionary Computation 17(3) (2009), 411–436.

41.

Ben Said

S.K.

and Bechikh

, The r-Dominance: A New Dominance Relation for Interactive Evolutionary Multicriteria Decision Making, IEEE Transactions on Evolutionary Computation 14(5) (2010), 801–818.

42.

Bechikh

, Said

L.B.

and Ghąäl?edira

, Searching for knee regions of the Pareto front using mobile reference points, Soft Computing 15(9) (2011), 1807–1823.

43.

Zhang

and Li

, MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition, IEEE Transactions on Evolutionary Computation 11(6) (2007), 712–731. ISSN 1089-778X, doi: https://doi.org/10.1109/TEVC.2007.892759.

44.

and Zhang

, Multiobjective optimization problems with complicated Pareto sets, MOEA/D and NSGA-II, IEEE Transactions on Evolutionary Computation 13(2) (2009), 284–302.

45.

, Deb

, Zhang

and Kwong

, An Evolutionary Many-Objective Optimization Algorithm Based on Dominance and Decomposition, IEEE Transactions on Evolutionary Computation 19(5) (2015), 694–716.

46.

Liu

, Gu

and Zhang

, Decomposition of a Multiobjective Optimization Problem Into a Number of Simple Multiobjective Subproblems, IEEE Transactions on Evolutionary Computation 18(3) (2014), 450–455.

47.

Deb

and Jain

, An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point-Based Nondominated Sorting Approach, Part I: Solving Problems With Box Constraints, IEEE Transactions on Evolutionary Computation 18(4) (2014), 577–601. ISSN 1089-778X, doi: https://doi.org/10.1109/TEVC.2013.2281535.

48.

Yuan

, Xu

and Wang

, An improved NSGA-III procedure for evolutionary many-objective optimization, in: Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation (2014), 661–668.

49.

Zhao

, Zhang

, Bin

and Peibo

, Decomposition-based sub-problem optimal solution updating direction-guided evolutionary many-objective algorithm, Information ences: An International Journal (2018), 448–449.

50.

Cheng

, Jin

, Olhofer

and Sendhoff

, A Reference Vector Guided Evolutionary Algorithm for Many-Objective Optimization, IEEE Transactions on Evolutionary Computation 20(5) (2015).

51.

Elarbi

, Bechikh

, Gupta

, Ben Said

and Ong

, A New Decomposition-Based NSGA-II for Many-Objective Optimization, IEEE Transactions on Systems, Man, and Cybernetics: Systems 48(7) (2018), 1191–1210. doi: 10.1109/TSMC.2017.2654301

52.

Jiang

and Yang

, A Strength Pareto Evolutionary Algorithm Based on Reference Direction for Multiobjective and Many-Objective Optimization, IEEE Transactions on Evolutionary Computation 21(3) (2017), 329–346. doi: 10.1109/TEVC.2016.2592479

53.

Liu

, Lin

, Tan

K.C.

, Gong

and Coello

C.A.C.

, A Fuzzy Decomposition-Based Multi/Many-Objective Evolutionary Algorithm, IEEE Transactions on Cybernetics (2020). 1ĺC15doi:10.1109/TCYB.2020.3008697

54.

Hughes

E.J.

, MSOPS-II: A general-purpose Many-Objective optimiser, in: 2007 IEEE Congress on Evolutionary Computation (2007), 3944–3951. doi:10.1109/CEC.2007.4424985.

55.

Deb

, Thiele

, Laumanns

and Zitzler

, Scalable Test Problems for Evolutionary Multiobjective Optimization (2006), 105–145.

56.

Huband

, Hingston

, Barone

and While

, A review of multiobjective test problems and a scalable test problem toolkit, IEEE Transactions on Evolutionary Computation 10 (2006), 477–506. doi: 10.1109/TEVC.2005.861417

57.

Neri

and Cotta

, Memetic algorithms and memetic computing optimization: A literature review, Swarm and Evolutionary Computation 2 (2012), 1–14.

58.

Wilcoxon

, Some Rapid Approximate Statistical Procedures, Annals of the New York Academy of ences 52(The Place of Statistical Methods in Biological and Chemical Experimentation) (2010), 808–814.

59.

Wolpert

D.H.

and Macready

W.G.

, No free lunch theorems for optimization, IEEE Transactions on Evolutionary Computation 1(1) (1997), 67–82.