Correo Electrónico
DNINFOA - SIA
Bibliotecas
Convocatorias
Identidad U.N.
Published
EF1-NSGA-III: An evolutionary algorithm based on the first front to obtain non-negative and non-repeated extreme points
EF1-NSGA-III: Un algoritmo evolutivo basado en el primer frente para obtener puntos extremos no negativos y no repetidos
DOI:
https://doi.org/10.15446/inginvestig.v40n3.82906Keywords:
evolutionary algorithm, manyobjective optimization problem (en)algoritmo evolutivo, problema de optimización de muchos objetivos (es)
Multi-Objective and Many-objective Optimization problems have been extensively solved through evolutionary algorithms over a few decades. Despite the fact that NSGA-II and NSGA-III are frequently employed as a reference for a comparative evaluation of new evolutionary algorithms, the latter is proprietary. In this paper, we used the basic framework of the NSGA-II, which is very similar to the NSGA-III, with significant changes in its selection operator. We took the first front generated at the non-dominating sort procedure to obtain nonnegative and nonrepeated extreme points. This opensource version of the NSGA-III is called EF1-NSGA-III, and its implementation does not start from scratch; that would be reinventing the wheel. Instead, we took the NSGA-II code from the authors in the repository of the Kanpur Genetic Algorithms Laboratory to extend the EF1-NSGA-III. We then adjusted its selection operator from diversity, based on the crowding distance, to the one found on reference points and preserved its parameters. After that, we continued with the adaptive EF1-NSGA-III (A-EF1-NSGA-III), and the efficient adaptive EF1-NSGA-III (A2-EF1-NSGA-III), while also contributing to explain how to generate different types of reference points. The proposed algorithms resolve optimization problems with constraints of up to 10 objective functions. We tested them on a wide range of benchmark problems, and they showed notable improvements in terms of convergence and diversity by using the Inverted Generational Distance (IGD) and the HyperVolume (HV) performance metrics. The EF1-NSGA-III aims to resolve the power consumption for Centralized Radio Access Networks and the BiObjective Minimum DiameterCost Spanning Tree problems.
Los problemas de optimización de varios objetivos se han resuelto ampliamente usando algoritmos evolutivos durante algunas décadas. A pesar de que los algoritmos NSGA-II y NSGA-III se emplean con frecuencia como referencia para evaluar nuevos algoritmos evolutivos, este último es propietario. En este artículo, utilizamos el marco NSGA-II, similar al NSGA-III, con cambios en su operador de selección. Tomamos el primer frente generado por ordenamiento no dominante para obtener puntos extremos no negativos y no repetidos. Esta versión del NSGA-III se llama EF1-NSGA-III, y su implementación no comienza desde cero; eso serıa reinventar la rueda. En lugar de eso, tomamos el código NSGA-II de los autores en el repositorio del Laboratorio de Algoritmos Genéticos Kanpur para extender el EF1-NSGA-III. Luego ajustamos su operador de selección de la diversidad en función de la distancia de hacinamiento al que se encuentra usando los puntos de referencia y preservamos sus parámetros. Después continuamos con el EF1-NSGA-III adaptativo (A-EF1-NSGA-III), y el eficiente adaptativo EF1-NSGA-III (A2-EF1-NSGA-III) contribuyendo en la explicación de cómo generar diferentes tipos de puntos de referencia. Los algoritmos propuestos resuelven problemas de optimización con restricciones de hasta 10 funciones objetivos. Los probamos en una amplia gama de problemas de referencia, y mostraron mejoras notables en términos de convergencia y diversidad utilizando las métricas de rendimiento de Distancia Generacional Invertida (IGD) e Hipervolumen (HV). El EF1-NSGA-III tiene como objetivo resolver el consumo de energía para las redes de acceso de radio centralizado y los problemas del árbol de expansión de diámetro mínimo bi-objetivo.
References
Ariza Vesga, L. F. (2019). A fast non-dominated sorting genetic algorithm extension to solve many-objective problems. https://github.com/lfarizav/NSGA-III
Ariza Vesga, L. F. (2020). Many-objective problems op-timization focused on energy efficiency applied to 5G heterogeneous cellular networks using the small cell switch-off framework (Doctoral thesis, Univer-sidad Nacional de Colombia, Bogotá, Colombia). https://repositorio.unal.edu.co/handle/unal/77582
Bader, J. and Zitzler, E. (2011). HypE: An Algorithm for Fast Hypervolume-Based Many-Objective Optimization. Evolutionary Computation, 19(1), 45-76. https://doi.org/10.1162/evco_a_00009
Bi, X. and Wang, C. (2017). An improved NSGA-III algorithm based on elimination operator for many-objective optimization. Memetic Computing, 9(4), 361-383. https://doi.org/10.1007/s12293-017-0240-7
Blank, J. and Deb, K. (2020). Pymoo: Multi-Objective Optimization in Python. IEEE Access, 8, 89497-89509. https://doi.org/10.1109/access.2020.2990567
Blank, J., Deb, K., and Roy, P. C. (2019). Investigating the Normalization Procedure of NSGA-III. In Deb, K., Goodman, E., Coello-Coello, C. A., Klamroth, K., Miettinen, K., Mostaghim, S., and Reed, P. (Eds.) Evolutionary Multi-Criterion Optimization (vol. 11411, pp. 229-240). New York, NY: Springer, Cham https://doi.org/10.1007/978-3-030-12598-1_19
Chiang, T.-C. (2014). nsga3cpp: A c++ implementation of nsga-iii. https://web.ntnu.edu.tw/~tcchiang/publications/nsga3cpp/nsga3cpp.htm
Das, I., and Dennis, J. E. (1998). Normal-Boundary Intersection: A New Method for Generating the Pareto Surface in Nonlinear Multicriteria Optimization Problems. SIAM Journal on Optimization, 8(3), 631-657. https://doi.org/10.1137/s1052623496307510
Deb, K. (1999). An introduction to genetic algorithms. Sadhana, 24, 293315. https://doi.org/10.1007/BF02823145
Deb, K. and Jain, H. (2014). 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), 577-601. https://doi.org/10.1109/tevc.2013.2281535
Deb, K., Pratap, A., Agarwal, S., and Meyarivan, T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2), 182-197. https://doi.org/10.1109/4235.996017
Deb, K., Thiele, L., Laumanns, M., and Zitzler, E. (2005). Scalable Test Problems for Evolutionary Multiobjective Optimization. In Abraham, A., Jain, L., and Goldberg, R. (Eds.) Evolutionary Multiobjective Optimization (pp. 105-145) New York, NY: Springer, Cham. https://doi.org/10.1007/1-84628-137-7_6
Fonseca, C., Paquete, L., and Lopez-Ibanez, M. (2006). An Improved Dimension-Sweep Algorithm for the Hypervolume Indicator. Paper presented at the IEEE International Conference on Evolutionary Computation, Vancouver, BC, Canada. https://doi.org/10.1109/cec.2006.1688440
Fraser, A. (1957). Simulation of Genetic Systems by Automatic Digital Computers II. Effects of Linkage on Rates of Advance Under Selection. Australian Journal of Biological Sciences, 10(4), 492. https://doi.org/10.1071/bi9570492
Gu, Z. and Wang, G. (2020). Improving NSGA-III algorithms with information feedback models for large-scale manyobjective optimization. Future Generation Computer Systems, 107, 49-69. https://doi.org/10.1016/j.future.2020.01.048
Gupta, R., Nanda, S. J. (2019). Many-Objective B/NSGA-III for Band Selection in Cloud Contaminated Hyper-Spectral Images. Paper presented at the 2019 International Conference on Information Technology (ICIT), Bhubaneswar, India. https://doi.org/10.1109/icit48102.2019.00068
Holland, J. H. (1975). Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. https://doi.org/10.7551/mitpress/1090.001.0001
Huband, S., Hingston, P., Barone, L., and While, L. (2006). A review of multiobjective test problems and a scalable test problem toolkit. IEEE Transactions on Evolutionary Computation, 10(5), 477-506. https://doi.org/10.1109/tevc.2005.861417
Ibrahim, A., Rahnamayan, S., Martin, M. V., and Deb, K. (2016). EliteNSGA-III: An improved evolutionary many-objective optimization algorithm. Paeper presented at the 2016 IEEE Congress on Evolutionary Computation (CEC). https://doi.org/10.1109/cec.2016.7743895
Ishibuchi, H., Imada, R., Setoguchi, Y., and Nojima, Y. (2016). Performance comparison of NSGA-II and NSGA- III on various many-objective test problems. Paper presented at 2016 IEEE Congress on Evolutionary Computation (CEC). https://doi.org/10.1109/cec.2016.7744174
Jain, H. and Deb, K. (2013). An Improved Adaptive Approach for Elitist Nondominated Sorting Genetic Algorithm for Many-Objective Optimization. In Purshouse, R. C., Fleming, P. J., Fonseca, C. M., Greco S., and Shaw, J. (Eds.) Evolutionary Multi-Criterion Optimization (vol. 7811, pp. 307-321). New York, NY: Springer, Cham. https://doi.org/10.1007/978-3-642-37140-0_25
Jain, H. and 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 Transactions on Evolutionary Computation, 18(4), 602-622. https://doi.org/10.1109/tevc.2013.2281534
Jiang, S. and Yang, S. (2017). A Strength Pareto Evolutionary Algorithm Based on Reference Direction for Multiobjective and Many-Objective Optimization. IEEE Transactions on Evolutionary Computation, 21(3), 329-346. https://doi.org/10.1109/tevc.2016.2592479
jMetal (2015). Metaheuristic algorithms in java. http://jmetal.sourceforge.net
KanGAL (2011). Software Developed at KanGAL. http://www.iitk.ac.in/kangal/codes.shtml
Li, K., Wang, R., Zhang, T., and Ishibuchi, H. (2018). Evolutionary Many-Objective Optimization: A Comparative Study of the State-of-the-Art. IEEE Access, 6, 26194-26214. https://doi.org/10.1109/access.2018.2832181
Li, H. and Zhang, Q. (2009). Multiobjective Optimization Problems With Complicated Pareto Sets, MOEA/D and NSGA-II. IEEE Transactions on Evolutionary Computation, 13(2), 284-302. https://doi.org/10.1109/tevc.2008.925798
Li, M. and Yao, X. (2020). What Weights Work for You? Adapting Weights for Any Pareto Front Shape in Decomposition-Based Evolutionary Multiobjective Optimisation. Evolutionary Computation, 28(2), 227-253. https://doi.org/10.1162/evco_a_00269
Li, W., Wang, G., and Alavi, A. H. (2020). Learning-based ele-phant herding optimization algorithm for solving numerical optimization problems. Knowledge-Based Systems, 195, 105675. https://doi.org/10.1016/j.knosys.2020.105675
Li, H., Deb, K., Zhang, Q., Suganthan, P., and Chen, L. (2019). Comparison between MOEA/D and NSGA-III on a set of novel many and multi-objective benchmark problems with challenging difficulties. Swarm and Evolutionary Computation, 46, 104-117. https://doi.org/10.1016/j.swevo.2019.02.003
Marti, L. (2016). An implementation of nsga-iii in python. https://github.com/lmarti/nsgaiii
Prakash, V. P., Patvardhan, C., and Srivastav, A. (2020). A novel Hybrid Multi-objective Evolutionary Algorithm for the bi-Objective Minimum Diameter-Cost Spanning Tree (bi-MDCST) problem. Engineering Applications of Artificial Intelligence, 87, 103237. https://doi.org/10.1016/j.engappai.2019.103237
Purshouse, R. C. and Fleming, P. J. (2007). On the Evolutionary Optimization of Many Conflicting Objectives. IEEE Transactions on Evolutionary Computation, 11(6), 770-784. https://doi.org/10.1109/tevc.2007.910138
Redcedartech (2015). Heeds smashes barriers on multi-objective design studies. https://redcedartech.com/newsletters/HEEDSNews-Mar15.htm.
Seada, H. and Deb, K. (2015). U-NSGA-III: A Unified Evolutionary Optimization Procedure for Single, Multiple, and Many Objectives: Proof-of-Principle Results. In António Gaspar-Cunha, A., Henggeler-Antunes, C., and Coello-Coello, C. (Eds.) Evolutionary Multi-Criterion Optimization (vol. 9019, pp. 34-49). New York, NY: Springer, Cham. https://doi.org/10.1007/978-3-319-15892-1_3
Seada, H., Abouhawwash, M., Deb, K. (2017). Towards a Better Balance of Diversity and Convergence in NSGA-III First Results. In Trautmann, H., Rudolph, G., Klamroth, K., Schütze, O., Wiecek, M., Jin, Y., and Grimme C. (Eds.) Evolutionary Multi-Criterion Optimization (vol. 10173, pp. 545-559). New York, NY: Springer, Cham. https://doi.org/10.1007/978-3-319-54157-0_37
Seada, H., Abouhawwash, M., and Deb, K. (2018). Multiphase Balance of Diversity and Convergence in Multiobjective Optimization. IEEE Transactions on Evolutionary Computation, 23(3), 503-513. https://doi.org/10.1109/tevc.2018.2871362
Shu, Z., Wang, W., and Wang, R. (2018). Design of an Optimized Architecture for Manned and Unmanned Combat System-of-Systems: Formulation and Coevolutionary Optimization. IEEE Access, 6, 52725-52740. https://doi.org/10.1109/access.2018.2870969
Surjanovic, S. and Bingham, D. (2013). Virtual Library of Simulation Experiments: Test Functions and Datasets. http://www.sfu.ca/ ssurjano
Tian, Y., Cheng, R., Zhang, X., and Jin, Y. (2017). PlatEMO: A MATLAB Platform for Evolutionary Multi-Objective Optimization [Educational Forum]. IEEE Computational Intelligence Magazine, 12(4), 73-87. https://doi.org/10.1109/mci.2017.2742868
Wangsom, P., Bouvry, P., and Lavangnananda, K. (2018). Extreme Solutions NSGA-III (E-NSGA-III) for Scien-tific Workflow Scheduling on Cloud. Paper presented at the 2018 17th IEEE International Conference on Machine Learning and Applications (ICMLA), Orlando, FL, USA. https://doi.org/10.1109/icmla.2018.00184
Wang, G., Guo, L., Gandomi, A. H., Hao, G., and Wang, H. (2014). Chaotic Krill Herd algorithm. Information Sciences, 274, 17-34. https://doi.org/10.1016/j.ins.2014.02.123
Wang, G. and Tan, Y. (2019). Improving Metaheuristic Algorithms with Information Feedback Models. IEEE Transactions on Cybernetics, 49(2), 542-555. https://doi.org/10.1109/tcyb.2017.2780274
Wang, H. and Yi, J. (2017). An improved optimization method based on krill herd and artificial bee colony with information exchange. Memetic Computing, 10(2), 177-198. https://doi.org/10.1007/s12293-017-0241-6
Wang, G., Deb, S., and Cui, Z. (2019). Monarch butterfly optimization. Neural Computing and Applications, 31(7), 1995-2014. https://doi.org/10.1007/s00521-015-1923-y
Wang, G. (2016). Moth search algorithm: A bio-inspired metaheuristic algorithm for global optimization problems. Memetic Computing, 10(2), 151-164. https://doi.org/10.1007/s12293-016-0212-3
Yarpiz (2018). Nsga-iii: Non-dominated sorting genetic algorithm, the third version. http://yarpiz.com/456/ypea126-nsga3
Yi, J., Deb, S., Dong, J., Alavi, A. H., and Wang, G. (2018). An improved NSGA-III algorithm with adaptive mutation operator for Big Data optimization problems. Future Generation Computer Systems, 88, 571-585. https://doi.org/10.1016/j.future.2018.06.008
Yi, J., Xing, L., Wang, G., Dong, J., Vasilakos, A. V., Alavi, A. H., and Wang, L. (2020). Behavior of crossover operators in NSGA-III for large-scale optimization problems. Information Sciences, 509, 470-487. https://doi.org/10.1016/j.ins.2018.10.005
Yuan, Y., Xu, H., and Wang, B. (2014). An improved NSGA-III procedure for evolutionary many-objective optimization. In Igel, C. (Ed.) GECCO '14: Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation (pp. 661-668). New York, NY: ACM. https://doi.org/10.1145/2576768.2598342
Zhang, Q., Liu, W., and Li, H. (2009). The performance of a new version of MOEA/D on CEC09 unconstrained MOP test instances. Paper presented at the 2009 IEEE Congress on Evolutionary Computation. https://doi.org/10.1109/cec.2009.4982949
Zhang, Y., Wang, G., Li, K., Yeh, W., Jian, M., and Dong, J. (2020). Enhancing MOEA/D with information feedback models for large-scale many-objective optimization. Information Sciences, 522, 1-16. https://doi.org/10.1016/j.ins.2020.02.066
Zhang, Q. and Li, H. (2007). MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition. IEEE Transactions on Evolutionary Computation, 11(6), 712-731. https://doi.org/10.1109/tevc.2007.892759
Zhang, X., Tian, Y., and Jin, Y. (2015). A Knee Point-Driven Evolutionary Algorithm for Many-Objective Optimization. IEEE Transactions on Evolutionary Computation, 19(6), 761-776. https://doi.org/10.1109/tevc.2014.2378512
Zhang, Q., Zhou, A., Zhao S., Suganthan, P. N., Liu, W., and Tiwari S. (2009). Multiobjective optimization test instances for the cec-2009 special session and competition. https://www.al-roomi.org/multimedia/CEC_Database/CEC2009/MultiObjectiveEA/CEC2009_MultiObjectiveEA_TechnicalReport.pdf
Zitzler, E., Deb, K., and Thiele, L. (2000). Comparison of Multiobjective Evolutionary Algorithms: Empirical Results. Evolutionary Computation, 8(2), 173-195. https://doi.org10.1162/106365600568202
How to Cite
APA
ACM
ACS
ABNT
Chicago
Harvard
IEEE
MLA
Turabian
Vancouver
Download Citation
CrossRef Cited-by
1. Juan Lu, Shiying Tu, Ying Li, Liang Zhang, Xiaoping Liao. (2025). Process planning of parameter intelligent adjustment for batch machining based on historical data segmented modeling. Engineering Applications of Artificial Intelligence, 145, p.110180. https://doi.org/10.1016/j.engappai.2025.110180.
2. Kabeer Ahmed Bhatti, Sohail Asghar, Imran Ali Qureshi. (2024). Self-adaptive bifold-objective rate optimization algorithm for Wireless Sensor Networks. Simulation Modelling Practice and Theory, 135, p.102984. https://doi.org/10.1016/j.simpat.2024.102984.
3. Meihui Wang, Yong Li, Chujie Liao, De Li Liu, Jianlin Shen, Jinshui Wu. (2024). Identifying the best fertilization practices by many-objective optimization to mitigate nitrous oxide emissions from tea field in the subtropics in Central China. Agriculture, Ecosystems & Environment, 375, p.109222. https://doi.org/10.1016/j.agee.2024.109222.
4. Sai Yang, Hongyu Chen, Zongbao Feng, Yawei Qin, Jian Zhang, Yuan Cao, Yang Liu. (2023). Intelligent multiobjective optimization for high-performance concrete mix proportion design: A hybrid machine learning approach. Engineering Applications of Artificial Intelligence, 126, p.106868. https://doi.org/10.1016/j.engappai.2023.106868.
5. Juan Lu, Zhiheng Chen, Xiaoping Liao, Chaoyi Chen, Haibin Ouyang, Steven Li. (2023). Multi-objective optimization for improving machining benefit based on WOA-BBPN and a Deep Double Q-Network. Applied Soft Computing, 142, p.110330. https://doi.org/10.1016/j.asoc.2023.110330.
6. Kabeer Ahmed Bhatti, Sohail Asghar, Bilal Rauf, Imran Ali Qureshi. (2024). A multi-objective integrated PID controller combined with NSGA-III for minimizing congestion in WSNs. Wireless Networks, 30(3), p.1423. https://doi.org/10.1007/s11276-023-03579-z.
Dimensions
PlumX
Article abstract page views
Downloads
License
Copyright (c) 2020 Luis Felipe Ariza Vesga, Johan Sebastian Eslava Garzon, Rafael Puerta Ramirez
This work is licensed under a Creative Commons Attribution 4.0 International License.
The authors or holders of the copyright for each article hereby confer exclusive, limited and free authorization on the Universidad Nacional de Colombia's journal Ingeniería e Investigación concerning the aforementioned article which, once it has been evaluated and approved, will be submitted for publication, in line with the following items:
1. The version which has been corrected according to the evaluators' suggestions will be remitted and it will be made clear whether the aforementioned article is an unedited document regarding which the rights to be authorized are held and total responsibility will be assumed by the authors for the content of the work being submitted to Ingeniería e Investigación, the Universidad Nacional de Colombia and third-parties;
2. The authorization conferred on the journal will come into force from the date on which it is included in the respective volume and issue of Ingeniería e Investigación in the Open Journal Systems and on the journal's main page (https://revistas.unal.edu.co/index.php/ingeinv), as well as in different databases and indices in which the publication is indexed;
3. The authors authorize the Universidad Nacional de Colombia's journal Ingeniería e Investigación to publish the document in whatever required format (printed, digital, electronic or whatsoever known or yet to be discovered form) and authorize Ingeniería e Investigación to include the work in any indices and/or search engines deemed necessary for promoting its diffusion;
4. The authors accept that such authorization is given free of charge and they, therefore, waive any right to receive remuneration from the publication, distribution, public communication and any use whatsoever referred to in the terms of this authorization.
