Login Register Cart 0
Generic placeholder image

The Chinese Journal of Artificial Intelligence

Editor-in-Chief

ISSN (Print): 2666-7827
ISSN (Online): 2666-7835

Back
Journal Home About Journal Editorial Board Current Issue Volumes/Issues
Subscribe
Research Article

Multi-Objective Evolutionary Algorithm Based on Two Reference Points Decomposition and Historical Information Prediction

Author(s): Er-chao Li * and Kang-wei Li

Volume 1, Issue 1, 2022

Published on: 06 August, 2021

Article ID: e060821195348 Pages: 19

DOI: 10.2174/2666782701666210806100730

Abstract

Aims: The main goal of this paper is to address the issues of low-quality offspring solutions generated by traditional evolutionary operators, as well as the evolutionary algorithm's inability to solve multi-objective optimization problems (MOPs) with complicated Pareto fronts (PFs).

Background: For some complicated multi-objective optimization problems, the effect of the multiobjective evolutionary algorithm based on decomposition (MOEA/D) is poor. For specific complicated problems, there is less research on how to improve the performance of the algorithm by setting and adjusting the direction vector in the decomposition-based evolutionary algorithm. Considering that in the existing algorithms, the optimal solutions are selected according to the selection strategy in the selection stage, without considering whether it could produce the better solutions in the stage of individual generation to achieve the optimization effect faster. As a result, a multi-objective evolutionary algorithm based on two reference points decomposition and historical information prediction is proposed.

Objective: In order to verify the feasibility of the proposed strategy, the F-series test function with complicated PFs is used as the test function to simulate the proposed strategy.

Methods: Firstly, the evolutionary operator based on historical information prediction (EHIP) is used to generate better offspring solutions to improve the convergence of the algorithm; secondly, the decomposition strategy based on ideal point and nadir point is used to select solutions to solve the MOPs with complicated PFs, and the decomposition method with augmentation term is used to improve the population diversity when selecting solutions according to the nadir point. Finally, the proposed algorithm is compared to several popular algorithms by the F-series test function, and the comparison is made according to the corresponding performance metrics.

Results: The performance of the algorithm is improved obviously compared with the popular algorithms after using the EHIP. When the decomposition method with augmentation term is added, the performance of the proposed algorithm is better than the algorithm with only the EHIP on the whole, but the overall performance is better than the popular algorithms.

Conclusion: The experimental results show that the overall performance of the proposed algorithm is superior to the popular algorithms. The EHIP can produce better quality offspring solutions, and the decomposition strategy based on two reference points can well solve the MOPs with complicated PFs. This paper mainly demonstrates the theory without testing the practical problems. The following research mainly focuses on the application of the proposed algorithm to practical problems such as robot path planning.

Keywords: Multi-objective optimization, evolutionary algorithm, decomposition, two reference points, complicated Pareto front, prediction.

Graphical Abstract

[1]
Zhang, Q.; Li, H. MOEA/D: A multi-objective evolutionary algorithm based on decomposition. IEEE Trans. Evol. Comput., 2007, 11(6), 712-731.
[http://dx.doi.org/10.1109/TEVC.2007.892759]
[2]
Collette, Y.; Siarry, P. Multi-objective optimization; Springer Berlin Heidelberg, 2004, pp. 273-316.
[3]
Jiang, S.; Yang, S. An improved multi-objective optimization evolutionary algorithm based on decomposition for complex pareto fronts. IEEE Trans. Cybern., 2016, 46(2), 421-437.
[http://dx.doi.org/10.1109/TCYB.2015.2403131] [PMID: 25781972]
[4]
Ma, X.; Yu, Y.; Li, X.; Qi, Y.; Zhu, Z. A survey of weight vector adjustment methods for decomposition based multi-objective evolutionary algorithms. IEEE Trans. Evol. Comput., 2020, 24(4), 634-649.
[5]
Cai, X.; Mei, Z.; Fan, Z. A decomposition-based many-objective evolutionary algorithm with two types of adjustments for direction vectors. IEEE Trans. Cybern., 2018, 48(8), 2335-2348.
[http://dx.doi.org/10.1109/TCYB.2017.2737554] [PMID: 28858821]
[6]
Qi, Y.; Ma, X.; Liu, F.; Jiao, L.; Sun, J.; Wu, J. MOEA/D with adaptive weight adjustment. Evol. Comput., 2014, 22(2), 231-264.
[http://dx.doi.org/10.1162/EVCO_a_00109] [PMID: 23777254]
[7]
Wang, Z.; Zhang, Q.; Li, H.; Ishibuchi, H.; Jiao, L. On the use of two reference points in decomposition based multi-objective evolutionary algorithms. Swarm Evol. Comput., 2017, 34, 89-102.
[http://dx.doi.org/10.1016/j.swevo.2017.01.002]
[8]
Ho-Huu, V.; Hartjes, S.; Visser, H.G. An improved MOEA/D algorithm for bi-objective optimization problems with complex Pareto fronts and its application to structural optimization. Exp. Sys. App., 2018, 92(5), 430-446.
[http://dx.doi.org/10.1016/j.eswa.2017.09.051]
[9]
Jain, H.; Deb, K. 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., 2014, 18(4), 602-622.
[http://dx.doi.org/10.1109/TEVC.2013.2281534]
[10]
Bi, X.; Wang, C. An improved NSGA-III algorithm based on elimination operator for many-objective optimization. Memetic Comp., 2017, 9(4), 361-383.
[http://dx.doi.org/10.1007/s12293-017-0240-7]
[11]
Wu, M.; Li, K.; Kwong, S. Evolutionary many-objective optimization based on adversarial decomposition. IEEE Trans. Cybern., 2020, 50(2), 753-764.
[12]
Liang, Z.; Hu, K.; Ma, X. A many-objective evolutionary algorithm based on a two-round selection strategy. IEEE Trans. Cybern., 2021, 51(3), 1417-1429.
[http://dx.doi.org/10.1109/TCYB.2019.2918087]
[13]
Zhang, Q.; Yang, S.; Jiang, S. Novel prediction strategies for dynamic multi-objective optimization. IEEE Trans. Evol. Comput., 2020, 24(2), 260-274.
[http://dx.doi.org/10.1109/TEVC.2019.2922834]
[14]
Wang, C.; Yen, G.G.; Jiang, M. A grey prediction-based evolutionary algorithm for dynamic multi-objective optimization. Swarm Evol. Comput., 2020, 56, 100695.
[http://dx.doi.org/10.1016/j.swevo.2020.100695]
[15]
Rong, M.; Gong, D.; Pedrycz, W.; Wang, L. A multimodel prediction method for dynamic multiobjective evolutionary optimization. IEEE Trans. Evol. Comput., 2020, 24(2), 290-304.
[16]
Jia, Z.H.; Gao, L.Y.; Zhang, X.Y. A new history-guided multi-objective evolutionary algorithm based on decomposition for batching scheduling. Exp. Sys. App., 2020, 141, 112920.1-112920.17..
[http://dx.doi.org/10.1016/j.eswa.2019.112920]
[17]
Li, C.Z.; Li, W.M. Evolutionary many objective optimization based on bidirectional decomposition. J. Syst. Eng. Electron., 2019, 30(2), 319-326.
[http://dx.doi.org/10.21629/JSEE.2019.02.11 ]
[18]
Cheng, R.; Jin, Y.C. Markus, Olhofer A reference vector guided evolutionary algorithm for many-objective optimization. IEEE Trans. Evol. Comput., 2016, 20(5), 773-791.
[19]
Deb, K.; Pratap, A.; Agarwal, S. A fast and elitist multi-objective genetic algorithm: NSGA-II. IEEE Trans. Evol. Comput., 2002, 6(2), 182-197.
[http://dx.doi.org/10.1109/4235.996017]
[20]
Giagkiozis, I.; Fleming, P.J. Methods for multi-objective optimization: An analysis. Inf. Sci., 2015, 293, 338-350.
[http://dx.doi.org/10.1016/j.ins.2014.08.071]
[21]
Das, I.; Dennis, J.E. Normal-Boundary Intersection: A new method for generating the Pareto surface in nonlinear multi-criteria optimization problems. SIAM J. Optim., 1998, 8(3), 631-657.
[http://dx.doi.org/10.1137/S1052623496307510]
[22]
Ding, J.L.; Yang, C.; Chen, L.P. Dynamic multi-objective optimization algorithm based on reference point prediction. Acta Automatica Sinica, 2017, 43(2), 313-320.
[23]
Quintero Santan, V.L.; Coello Coello, A.C. An algorithm based on differential evolution for multi-objective problems. Intern. J. Computat. Intell. Res., 2005, 15(4), 151-169.
[http://dx.doi.org/10.5019/j.ijcir.2005.32]
[24]
Liu, H.L.; Gu, F.; Zhang, Q. Decomposition of a multi-objective optimization problem into a number of simple multi-objective subproblems. IEEE Trans. Evol. Comput., 2014, 18(3), 450-455.
[http://dx.doi.org/10.1109/TEVC.2013.2281533]
[25]
Yuan, Y. Multi-objective evolutionary algorithm based on decomposition and its application; Tsinghua University: Beijing, 2015, pp. 30-61.
[26]
Gu, F.; Liu, L.H.; Tan, C.K. A multi-objective evolutionary algorithm using dynamic weight design method. Intern. J. Innov. Comput. Inform. Control Ijicic, 2012, 8(5B), 3677-3688.
[27]
H.; Zhang, Q. Multi-objective optimization problems with complicated Pareto sets, MOEA/D and NSGA-II. IEEE Trans. Evol. Comput., 2009, 13(2), 284-302.
[http://dx.doi.org/10.1109/TEVC.2008.925798]
[28]
Li, E.; Li, K. Decomposition multi-objective evolutionary algorithm based on minimum distance and aggregation strategy. Jisuanji Yingyong, 2021, 41(01), 22-28.
[29]
Veldhuizen, D.A.V.; Lamont, G.B. In: On Measuring Multi- Objective Evolutionary Algorithm Performance, Proceedings of the 2000 Congress on Evolutionary Computation, La Jolla: CA, USA July 16-19, 2000; IEEE, 2002; pp. 204-211.
[http://dx.doi.org/10.1109/CEC.2000.870296]
[30]
Deb, K.; Jain, S. Running performance metrics for evolutionary multi-objective optimization. KanGAL Report, 2002, 2002004.
[31]
Bosman, P A N.; Thierens, D. The balance between proximity and diversity in multi-objective evolutionary algorithms. IEEE Trans. Evol. Comput., 2003, 7(2), 174-188.
[http://dx.doi.org/10.1109/TEVC.2003.810761]
[32]
Zitzler, E.; Thiele, L. Multi-objective evolutionary algorithms: A comparative case study and the strength Pareto approach. IEEE Trans. Evol. Comput., 1999, 3(4), 257-271.
[http://dx.doi.org/10.1109/4235.797969]

Rights & Permissions Print Cite
Article Metrics
22
1
© 2024 Bentham Science Publishers | Privacy Policy