[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 hybrid greedy indicator- and Pareto-based many-objective evolutionary algorithm

  • Published:
Applied Intelligence Aims and scope Submit manuscript

Abstract

As most of Multi-Objective Evolutionary Algorithms (MOEAs) scale quite poorly when the number of objective functions increases, new strategies have been proposed to face this limitation. Considered one of the most well-succeeded examples of such new strategies, the third version of Non-dominated Sorting Genetic Algorithm (NSGA-III) uses a set of reference points placed on a normalized hyperplane to solve Many Objective Optimization Problems (MaOPs). Despite the good results of NSGA-III, the shape of the hypersurface can influence the algorithm’s performance and it has not been deeply explored in the recent literature. This work aims therefore at proposing a new hybrid algorithm and investigating nonlinear transformations applied to the NSGA-III hyperplane. We categorize our proposed approach as a hybrid MOEA (Indicator- and Pareto-based), and analyze the influence of the modified set of reference points on the proposed algorithm while solving MaOPs. The paper presents as its main contributions: (i) the proposal of a greedy indicator-based variant of NSGA-III that uses math transformations on a subset of chosen reference points; (ii) the use of Vector Guided Adaptation procedure to modify original NSGA-III hyperplane at every few iterations. A set of experiments addressing several benchmark problems is performed to evaluate the performance of the original and adapted NSGA-III versions, and also to compare them with two well known MOEAs, observing both, convergence and diversity of the final Pareto fronts. Based on the analysis of statistical tests, we conclude that the proposed approach is competitive and can provide an interesting alternative to the original NSGA-III conception.

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
Fig. 7
Fig. 8
Fig. 9
Fig. 10

Similar content being viewed by others

Explore related subjects

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

References

  1. Bader JM (2010) Hypervolume-based search for multiobjective optimization: theory and methods. 112 Johannes Bader

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

    Article  Google Scholar 

  3. Brassard G, Bratley P (1996) Fundamentals of algorithmics. Prentice-Hall, Inc, Upper Saddle River

    MATH  Google Scholar 

  4. Carvalho M, Britto A (2018) Influence of reference points on a many-objective optimization algorithm. In: 2018 7th Brazilian conference on intelligent systems (BRACIS), pp 31–36. https://doi.org/10.1109/BRACIS.2018.00014

  5. Chankong V, Haimes Y (1983) Multiobjective decision making: theory and methodology. North-Holland series in system science and engineering. North Holland

  6. 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. https://doi.org/10.1109/TEVC.2016.2519378

    Article  Google Scholar 

  7. Coello CAC, Lamont GB, Veldhuizen DAV (2006) Evolutionary algorithms for solving multi-objective problems (genetic and evolutionary computation). Springer, Berlin

    MATH  Google Scholar 

  8. Cuate O, Derbel B, Liefooghe A, Talbi E, Schütze O (2017) An approach for the local exploration of discrete many objective optimization problems. Evol Multi-Criterion Optim 10173:135–150. https://doi.org/10.1007/978-3-319-54157-0_10

    Article  MathSciNet  Google Scholar 

  9. Das I, 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–657. https://doi.org/10.1137/S1052623496307510

    Article  MathSciNet  Google Scholar 

  10. Deb K (1999) Multi-objective genetic algorithms: problem difficulties and construction of test problems. Evol Comput 7(3):205–230. https://doi.org/10.1162/evco.1999.7.3.205

    Article  Google Scholar 

  11. Deb K (2001) Archive based multi-swarm algorithm for many-objective problems. In: Multi-objective optimization using evolutionary algorithms. Wiley, New York

  12. 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. https://doi.org/10.1109/TEVC.2013.2281535

    Article  Google Scholar 

  13. Deb K, Saxena DK (2006) Searching for Pareto-optimal solutions through dimensionality reduction for certain large-dimensional multi-objective optimization problems. In: 2006 IEEE Congress On Evolutionary Computation (CEC’2006). IEEE, Vancouver, pp 3353–3360

  14. 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. https://doi.org/10.1109/4235.996017

    Article  Google Scholar 

  15. 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. https://doi.org/10.1109/4235.996017

    Article  Google Scholar 

  16. Deb K, Thiele L, Laumanns M, Zitzler E (2002) Scalable multi-objective optimization test problems. In: Congress on evolutionary computation (CEC 2002), pp 825–830

  17. Derrac J, Garcia S, Molina D, Herrera F (2011) A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms. Swarm Evol Comput 1(1):3–18

    Article  Google Scholar 

  18. Fleming P, Purshouse R, Lygoe R (2005) Many-objective optimization: an engineering design perspective. In: Coello Coello C, Hernandez Aguirre A, Zitzler E (eds) 14–32. Springer, Berlin

  19. Fleming PJ, Purshouse RC, Lygoe RJ (2005) Many-objective optimization: an engineering design perspective. In: Coello Coello C A, Hernández Aguirre A, Zitzler E (eds) Evolutionary multi-criterion optimization. Springer, Berlin, pp 14–32

  20. Garza-Fabre M, Pulido GT, Coello CA (2009) Ranking methods for many-objective optimization. In: Proceedings of the 8th Mexican international conference on artificial intelligence, MICAI ’09. Springer, Berlin, pp 633–645

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

    Article  Google Scholar 

  22. 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. https://doi.org/10.1109/TEVC.2005.861417

    Article  Google Scholar 

  23. 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. https://doi.org/10.1109/TEVC.2005.861417

    Article  Google Scholar 

  24. Ibrahim A, Rahnamayan S, Martin MV, Deb K (2016) Elitensga-iii: an improved evolutionary many-objective optimization algorithm. In: 2016 IEEE Congress on evolutionary computation (CEC), pp 973–982. https://doi.org/10.1109/CEC.2016.7743895

  25. Ishibuchi H, Tsukamoto N, Nojima Y (2008) Evolutionary many-objective optimization: a short review. In: CEC 2008. IEEE congress on evolutionary computation, pp 2419–2426

  26. Khan B, Johnstone M, Hanoun S, Lim CP, Creighton D, Nahavandi S (2016) Improved nsga-iii using neighborhood information and scalarization. In: 2016 IEEE international conference on systems, man, and cybernetics (SMC), pp 003033–003038. https://doi.org/10.1109/SMC.2016.7844702

  27. Kramida A, Ralchenko Yu, Reader J (2019) NIST ASD Team: NIST Atomic Spectra Database (ver. 5.7.1), [Online]. Available: https://physics.nist.gov/asd (2017, April 9). National Institute of Standards and Technology, Gaithersburg

  28. Lacour R, Klamroth K, Fonseca CM (2017) A box decomposition algorithm to compute the hypervolume indicator. Comput Oper Res 79:347–360. https://doi.org/10.1016/j.cor.2016.06.021. http://www.sciencedirect.com/science/article/pii/S0305054816301538

    Article  MathSciNet  Google Scholar 

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

    Article  Google Scholar 

  30. Ma Y, Bai Y (2020) A multi-population differential evolution with best-random mutation strategy for large-scale global optimization. Appl Intell 50. https://doi.org/10.1007/s10489-019-01613-2

  31. Ma T, Chen H, Li K, Peng M (2019) Multi-objective optimization intelligent path planning for autonomous driving. IOP Conf Ser: Mater Sci Eng 563:052078. https://doi.org/10.1088/1757-899X/563/5/052078

    Article  Google Scholar 

  32. Maltese J, Ombuki-Berman B, Engelbrecht A (2016) A scalability study of many-objective optimization algorithms. IEEE Trans Evol Comput PP:1–1. https://doi.org/10.1109/TEVC.2016.2639360

    Google Scholar 

  33. Maltese J, Ombuki-Berman BM, Engelbrecht AP (2016) Pareto-based many-objective optimization using knee points. In: 2016 IEEE congress on evolutionary computation (CEC), pp 3678–3686. https://doi.org/10.1109/CEC.2016.7744255

  34. Menchaca-Mendez A, Hernández C, Coello CAC (2016) Δp-moea: a new multi-objective evolutionary algorithm based on the Δp indicator. In: 2016 IEEE Congress on evolutionary computation (CEC), pp 3753–3760. https://doi.org/10.1109/CEC.2016.7744265

  35. Odu G (2019) Weighting methods for multi-criteria decision making technique. J Appl Sci Environ Manag 23(8):1449–1457

    Google Scholar 

  36. Oliver JM, Kipouros T, Savill AM (2014) Electrical power grid network optimisation by evolutionary computing. Procedia Comput Sci 29:1948–1958. https://doi.org/10.1016/j.procs.2014.05.179. http://www.sciencedirect.com/science/article/pii/S1877050914003561. 2014 International Conference on Computational Science

    Article  Google Scholar 

  37. R Core Team (2020) R: a language and environment for statistical computing, R Foundation for Statistical Computing, Vienna. https://www.R-project.org

  38. Riquelme N, Von Lücken C, Baran B (2015) Performance metrics in multi-objective optimization. In: 2015 Latin American computing conference (CLEI), pp 1–11

  39. Schütze O, Lara A, Coello CAC (2011) On the influence of the number of objectives on the hardness of a multiobjective optimization problem. IEEE Trans Evol Comput 15(4):444–455

    Article  Google Scholar 

  40. 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–622. https://doi.org/10.1109/TEVC.2017.2749619

    Article  Google Scholar 

  41. Toscano G, Deb K (2016) Study of the approximation of the fitness landscape and the ranking process of scalarizing functions for many-objective problems. In: 2016 IEEE congress on evolutionary computation (CEC), pp 4358–4365. https://doi.org/10.1109/CEC.2016.7744344

  42. Velasquez M, Hester PT (2013) An analysis of multi-criteria decision making methods. Int J Oper Res 10(2):56–66

    MathSciNet  Google Scholar 

  43. Vesikar Y, Deb K, Blank J (2018) Reference point based nsga-iii for preferred solutions. In: 2018 IEEE symposium series on computational intelligence (SSCI), pp 1587–1594. https://doi.org/10.1109/SSCI.2018.8628819

  44. Wang H, Jiao L, Yao X (2015) Twoarch an improved two-archive algorithm for many-objective optimization. IEEE Trans Evol Comput 19(4):524–541

    Article  Google Scholar 

  45. While R, Bradstreet L, Barone L (2012) A fast way of calculating exact hypervolumes. IEEE Trans Evol Comput 16:86–95. https://doi.org/10.1109/TEVC.2010.2077298

    Article  Google Scholar 

  46. Yu H, Wang Y, Xiao S (2019) Multi-objective particle swarm optimization based on cooperative hybrid strategy. Appl Intell 50. https://doi.org/10.1007/s10489-019-01496-3

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

    Article  Google Scholar 

  48. Zhang Q, Liu W, Li H (2009) The performance of a new version of moea/d on cec09 unconstrained mop test instances. In: IEEE congress on evolutionary computation, 2009. CEC ’09, pp 203–208

  49. Zhang Y, Gong DW, Sun J, Qu BY (2017) A decomposition-based archiving approach for multi-objective evolutionary optimization. Inf Sci 430. https://doi.org/10.1016/j.ins.2017.11.052

  50. Zhang Y, Gong DW, Gao XZ, Tian T, Sun XY (2019) Binary differential evolution with self-learning for multi-objective feature selection. Inf Sci 507. https://doi.org/10.1016/j.ins.2019.08.040

  51. Zhou A, Qu B Y, Li H, Zhao S Z, Suganthan P, Zhang Q (2011) Multiobjective evolutionary algorithms: a survey of the state of the art. Swarm Evol Comput 1:32–49

    Article  Google Scholar 

  52. Zitzler E, Kunzli S (2004) Indicator-based selection in multiobjective search. In: Proceedings of the 8th international conference on parallel problem solving from nature (PPSN VIII), pp 832–842, Springer

Download references

Acknowledgements

This study was financed in part by the Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - Brasil (CAPES) - Finance Code 001 and by the Universal CNPq grant, project number 425861/2016-3. M. Delgado acknowledges CNPq, grants 309935/2017-2 and 439226/2018-0.

Author information

Authors and Affiliations

  1. Post-Graduation Program on Computer Science, Universidade Federal de Sergipe, São Cristóvão, Brazil

    Matheus Carvalho de Oliveira

  2. Academic Department of Informatics, Universidade Tecnológica Federal do Paraná, Curitiba, Brazil

    Myriam Regattieri Delgado

  3. Computation Departament, Universidade Federal de Sergipe, São Cristóvão, Brazil

    André Britto

Authors
  1. Matheus Carvalho de Oliveira
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Myriam Regattieri Delgado
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. André Britto
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Matheus Carvalho de Oliveira.

Ethics declarations

Conflict of interest

The authors declare that they have no conflict of interest.

Additional information

Publisher’s note

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

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

de Oliveira, M., Delgado, M.R. & Britto, A. A hybrid greedy indicator- and Pareto-based many-objective evolutionary algorithm. Appl Intell 51, 4330–4352 (2021). https://doi.org/10.1007/s10489-020-02025-3

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10489-020-02025-3

Keywords

Search

Navigation