Dynamic multi-objective optimization algorithm based on adaptive prediction of new evaluation index

doi:10.11772/j.issn.1001-9081.2022091453

Abstract

Abstract:

Most of the Multi-objective Optimization Problems （MOP） in real life are Dynamic Multi-objective Optimization Problems （DMOP）， and the objective function， constraint conditions and decision variables of such problems may change with time， which requires the algorithm to quickly adapt to the new environment after the environment changes， and guarantee the diversity of Pareto solution sets while converging to the new Pareto frontier quickly. To solve the problem， an Adaptive Prediction Dynamic Multi-objective Optimization Algorithm based on New Evaluation Index （NEI-APDMOA） was proposed. Firstly， a new evaluation index better than crowding was proposed in the process of population non-dominated sorting， and the convergence speed and population diversity were balanced in different stages， so as to make the convergence process of population more reasonable. Secondly， a factor that can judge the strength of environmental changes was proposed， thereby providing valuable information for the prediction stage and guiding the population to better adapt to environmental changes. Finally， three more reasonable prediction strategies were matched according to environmental change factor， so that the population was able to respond to environmental changes quickly. NEI-APDMOA， DNSGA-Ⅱ-A （Dynamic Non-dominated Sorting Genetic Algorithm-Ⅱ-A）， DNSGA-Ⅱ-B （Dynamic Non-dominated Sorting Genetic Algorithm-Ⅱ-B） and PPS （Population Prediction Strategy） algorithms were compared on nine standard dynamic test functions. Experimental results show that NEI-APDMOA achieves the best average Inverted Generational Distance （IGD） value， average SPacing （SP） value and average Generational Distance （GD） value on nine， four and eight test functions respectively， and can respond to environmental changes faster.

Key words: dynamic multi-objective optimization, evolutionary algorithm, evaluation index, non-dominated sorting, prediction strategy

摘要：

现实生活中的多目标优化问题（MOP）大多为动态多目标优化问题（DMOP），此类问题的目标函数、约束条件和决策变量都可能随时间的变化而发生改变，这需要算法在环境变化后快速适应新的环境，且在保证Pareto解集多样性的同时快速收敛到新的Pareto前沿。针对此问题，提出一种基于新评价指标自适应预测的动态多目标优化算法（NEI-APDMOA）。首先，在种群非支配排序过程中提出一种优于拥挤度的新评价指标，并分阶段平衡收敛快速性和种群多样性，使种群的收敛过程更加合理；其次，提出一种可判断环境变化强弱的因子，为预测阶段提供有价值信息，并引导种群更好地适应环境变化；最后，根据环境变化因子匹配3种更加合理的预测策略，使种群快速响应环境变化。将NEI-APDMOA与DNSGA-Ⅱ-A（Dynamic Non-dominated Sorting Genetic Algorithm-Ⅱ-A）、DNSGA-Ⅱ-B（Dynamic Non-dominated Sorting Genetic Algorithm-Ⅱ-B）和PPS（Population Prediction Strategy）算法在9个标准动态测试函数上进行对比。实验结果表明，NEI-APDMOA分别在9、4和8个测试函数上取得了最优的平均反世代距离（IGD）值、平均间距（SP）值和平均世代距离（GD）值，可以更快地响应环境变化。

关键词: 动态多目标优化, 进化算法, 评价指标, 非支配排序, 预测策略

CLC Number:

TP273

Erchao LI, Shenghui ZHANG. Dynamic multi-objective optimization algorithm based on adaptive prediction of new evaluation index[J]. Journal of Computer Applications, 2023, 43(10): 3178-3187.

李二超, 张生辉. 基于新评价指标自适应预测的动态多目标优化算法[J]. 《计算机应用》唯一官方网站, 2023, 43(10): 3178-3187.

Figures/Tables 14

Fig. 1 Flow of dynamic multi-objective optimization algorithm

Fig. 2 Positive ideal point and negative ideal point

Fig. 3 Degree of correlation of same solution set at different time

Fig. 4 Schematic diagram of reference line

Fig. 5 Random initialization of dominating population individuals

Fig. 6 Centroid of population profiles at different time

Tab. 1 Average IGD and SP values at different metric weights

（ $ω m a x$ ， $ω m i n$ ）	初期		后期
（ $ω m a x$ ， $ω m i n$ ）	平均IGD	平均SP	平均IGD	平均SP
（1，0.05）	0.572 9	0.145 3	0.177 0	0.194 1
（1，0.15）	0.689 3	0.127 0	0.220 9	0.157 4
（1，0.25）	0.752 1	0.106 8	0.324 3	0.181 1

Tab. 1 Average IGD and SP values at different metric weights

（ $ω m a x$ ， $ω m i n$ ）	初期		后期
（ $ω m a x$ ， $ω m i n$ ）	平均IGD	平均SP	平均IGD	平均SP
（1，0.05）	0.572 9	0.145 3	0.177 0	0.194 1
（1，0.15）	0.689 3	0.127 0	0.220 9	0.157 4
（1，0.25）	0.752 1	0.106 8	0.324 3	0.181 1

Fig. 7 Curve of average IGD value changing with environmental detection threshold

Tab. 2 Average IGD value statistics of four algorithms

测试函数	DNSGA-Ⅱ-A			DNSGA-Ⅱ-B			PPS			NEI-APDMOA
测试函数	平均值	方差	性能	平均值	方差	性能	平均值	方差	性能	平均值	方差
共计	6-/3~/0+			7-/2~/0+			9-/0~/0+
FDA1	1.48E-01	8.51E-03	-	1.43E-01	9.89E-03	-	2.10E-01	1.73E-02	-	1.10E-01	8.05E-03
FDA2	5.24E-02	4.38E-03	-	5.16E-02	3.97E-03	-	7.80E-02	1.69E-03	-	1.99E-02	2.92E-03
FDA3	1.38E-01	9.46E-03	-	1.39E-01	1.26E-02	-	2.07E-01	2.53E-02	-	1.19E-01	8.44E-03
FDA4	6.65E-02	1.76E-03	-	6.23E-02	2.29E-03	-	8.61E-02	4.92E-03	-	6.03E-02	9.78E-04
FDA5	3.33E-02	1.84E-03	~	3.28E-02	7.41E-04	~	4.39E-02	2.42E-03	-	3.26E-02	6.74E-04
DMOP1	9.07E-02	1.74E-02	-	8.27E-02	1.89E-02	-	1.22E-01	2.90E-02	-	6.20E-02	5.54E-03
DMOP2	6.61E-02	3.36E-03	~	6.99E-02	5.48E-03	-	9.05E-02	9.85E-03	-	6.34E-02	5.14E-03
DTLZ1	2.52E-02	2.92E-04	~	2.57E-02	4.83E-04	~	2.58E-02	7.63E-04	-	2.51E-02	2.02E-04
DTLZ2	4.00E-02	1.62E-04	-	3.96E-02	8.57E-04	-	4.69E-02	3.08E-04	-	3.82E-02	7.87E-04

Tab. 3 Average SP value statistics of four algorithms

测试函数	DNSGA-Ⅱ-A			DNSGA-Ⅱ-B			PPS			NEI-APDMOA
测试函数	平均值	方差	性能	平均值	方差	性能	平均值	方差	性能	平均值	方差
共计	2-/4~/3+			2-/5~/2+			2-/3~/4+
FDA1	1.80E-01	2.01E-02	~	1.85E-01	2.33E-02	~	1.91E-01	2.30E-02	~	1.76E-01	1.94E-02
FDA2	7.42E-01	2.14E-02	+	7.43E-01	1.71E-02	+	5.27E-01	4.53E-02	+	3.11E+00	1.69E-01
FDA3	1.59E-01	1.73E-02	~	1.61E-01	1.49E-02	~	1.31E-01	1.31E-01	+	1.53E-01	8.18E-03
FDA4	3.14E-01	1.56E-02	+	3.18E-01	2.40E-02	~	2.97E-01	2.20E-02	+	3.28E-01	1.20E-02
FDA5	3.84E-01	1.72E-02	+	3.83E-01	1.40E-02	+	4.02E-01	2.67E-02	+	1.02E+00	1.59E-01
DMOP1	3.48E-01	3.74E-02	-	3.61E-01	4.69E-02	-	4.79E-01	5.93E-02	-	2.90E-01	2.16E-02
DMOP2	3.42E-01	2.51E-02	-	3.45E-01	1.40E-02	-	3.57E-01	1.52E-02	-	2.87E-01	3.12E-02
DTLZ1	6.49E-01	1.78E-02	~	6.54E-01	1.74E-02	~	6.78E-01	2.02E-02	~	6.39E-01	8.52E-03
DTLZ2	7.63E-01	2.49E-02	~	7.61E-01	2.13E-02	~	7.72E-01	2.11E-02	~	7.66E-01	2.60E-03

Tab. 4 Average GD value statistics of four algorithms

测试函数	DNSGA-Ⅱ-A			DNSGA-Ⅱ-B			PPS			NEI-APDMOA
测试函数	平均值	方差	性能	平均值	方差	性能	平均值	方差	性能	平均值	方差
共计	7-/1~/1+			7-/1~/1+			7-/2~/0+
FDA1	1.14E-02	7.64E-04	-	1.08E-02	7.33E-04	-	1.65E-02	1.88E-03	-	8.89E-03	2.68E-03
FDA2	1.32E-03	7.36E-05	+	1.35E-03	8.25E-05	+	2.17E-03	3.75E-04	~	2.39E-03	1.39E-04
FDA3	1.21E-02	9.32E-04	-	1.18E-02	1.13E-03	-	2.00E-02	3.07E-03	-	1.02E-02	3.32E-04
FDA4	6.29E-03	1.59E-04	-	5.96E-03	1.99E-04	-	1.37E-02	1.32E-03	-	5.65E-03	3.17E-04
FDA5	5.52E-03	2.82E-04	-	5.42E-03	2.07E-04	-	8.08E-03	6.77E-04	-	4.93E-03	2.08E-04
DMOP1	1.62E-02	1.88E-03	-	1.49E-02	1.81E-03	-	1.80E-02	2.25E-03	-	9.74E-03	4.51E-04
DMOP2	7.02E-03	2.67E-04	-	7.08E-03	4.13E-04	-	9.37E-03	8.52E-04	-	6.10E-03	1.41E-04
DTLZ1	3.21E-03	1.18E-04	-	3.26E-03	1.56E-04	-	3.79E-03	9.07E-05	-	2.84E-03	1.03E-04
DTLZ2	9.35E-03	4.55E-04	~	9.27E-03	2.43E-04	~	1.14E-02	7.19E-04	~	9.20E-03	7.58E-05

Fig. 8 Evolution curves of IGD values of different algorithms on 6 test functions

Fig. 9 Solution set distribution of DMOP1 at different stages in same environment

Fig. 10 Solution set distribution of DTLZ2 in different environments

References 29

1	ZHOU A， QU B Y， LI H， et al. Multiobjective evolutionary algorithms： a survey of the state of the art［J］. Swarm and Evolutionary Computation， 2011， 1（1）：32-49. 10.1016/j.swevo.2011.03.001
2	刘若辰，李建霞，刘静，等. 动态多目标优化研究综述［J］. 计算机学报， 2020， 43（7）：1246-1278. 10.11897/SP.J.1016.2020.01246
	LIU R C， LI J X， LIU J， et al. A survey on dynamic multi-objective optimization［J］. Chinese Journal of Computers， 2020， 43（7）：1246-1278. 10.11897/SP.J.1016.2020.01246
3	RUAN G， YU G， ZHENG J， et al. The effect of diversity maintenance on prediction in dynamic multi-objective optimization［J］. Applied Soft Computing， 2017， 58： 631-647. 10.1016/j.asoc.2017.05.008
4	MURUGANANTHAM A， TAN K C， VADAKKEPAT P. Evolutionary dynamic multiobjective optimization via Kalman filter prediction［J］. IEEE Transactions on Cybernetics， 2016， 46（12）： 2862-2873. 10.1109/tcyb.2015.2490738
5	DEB K， RAO N U B， KARTHIK S. Dynamic multi-objective optimization and decision-making using modified NSGA-Ⅱ： a case study on hydro-thermal power scheduling［C］// Proceedings of the 2007 International Conference on Evolutionary Multi-Criterion Optimization， LNCS 4403. Berlin： Springer， 2007： 803-817.
6	DEB K， PRATAP A， AGARWAL S， et al. A fast and elitist multiobjective genetic algorithm： NSGA-Ⅱ［J］. IEEE Transactions on Evolutionary Computation， 2002， 6（2）： 182-197. 10.1109/4235.996017
7	AZEVEDO C R B， ARAÚJO A F R. Generalized immigration schemes for dynamic evolutionary multiobjective optimization［C］// Proceedings of the 2011 IEEE Congress of Evolutionary Computation. Piscataway： IEEE， 2011： 2033-2040. 10.1109/cec.2011.5949865
8	SAHMOUD S， TOPCUOGLU H R. A memory-based NSGA-Ⅱ algorithm for dynamic multi-objective optimization problems［C］// Proceedings of the 2016 European Conference on the Applications of Evolutionary Computation， LNCS 9598. Cham： Springer， 2016： 296-310.
9	JIANG M， WANG Z， QIU L， et al. A fast dynamic evolutionary multiobjective algorithm via manifold transfer learning［J］. IEEE Transactions on Cybernetics， 2021， 51（7）： 3417-3428. 10.1109/tcyb.2020.2989465
10	CAO L， XU L， GOODMAN E D， et al. Evolutionary dynamic multiobjective optimization assisted by a support vector regression predictor［J］. IEEE Transactions on Evolutionary Computation， 2020， 24（2）： 305-319. 10.1109/tevc.2019.2925722
11	RONG M， GONG D， PEDRYCZ W， et al. A multimodel prediction method for dynamic multiobjective evolutionary optimization［J］. IEEE Transactions on Evolutionary Computation， 2020， 24（2）： 290-304. 10.1109/tevc.2019.2925358
12	WANG C， YEN G G， JIANG M. A grey prediction-based evolutionary algorithm for dynamic multiobjective optimization［J］. Swarm and Evolutionary Computation， 2020， 56： No.100695. 10.1016/j.swevo.2020.100695
13	ZHAO Q， YAN B， SHI Y， et al. Evolutionary dynamic multiobjective optimization via learning from historical search process［J］. IEEE Transactions on Cybernetics， 2022， 52（7）： 6119-6130. 10.1109/tcyb.2021.3059252
14	GONG D， XU B， ZHANG Y， et al. A similarity-based cooperative co-evolutionary algorithm for dynamic interval multiobjective optimization problems［J］. IEEE Transactions on Evolutionary Computation， 2020， 24（1）： 142-156. 10.1109/tevc.2019.2912204
15	FENG L， ZHOU W， LIU W， et al. Solving dynamic multiobjective problem via autoencoding evolutionary search［J］. IEEE Transactions on Cybernetics， 2022， 52（5）： 2649-2662. 10.1109/tcyb.2020.3017017
16	ZHANG Q， YANG S， JIANG S， et al. Novel prediction strategies for dynamic multiobjective optimization［J］. IEEE Transactions on Evolutionary Computation， 2020， 24（2）： 260-274. 10.1109/tevc.2019.2922834
17	SAHMOUD S， TOPCUOGLU H R. Sensor-based change detection schemes for dynamic multi-objective optimization problems［C］// Proceedings of the 2016 IEEE Symposium Series on Computational Intelligence. Piscataway： IEEE， 2016： 1-8. 10.1109/ssci.2016.7849963
18	RICHTER H. Detecting change in dynamic fitness landscapes［C］// Proceedings of the 2009 IEEE Congress on Evolutionary Computation. Piscataway： IEEE， 2009： 1613-1620. 10.1109/cec.2009.4983135
19	JIANG S， YANG S. A steady-state and generational evolutionary algorithm for dynamic multiobjective optimization［J］. IEEE Transactions on Evolutionary Computation， 2017， 21（1）：65-82. 10.1109/tevc.2016.2574621
20	XU B， ZHANG Y， GONG D， et al. Environment sensitivity-based cooperative co-evolutionary algorithms for dynamic multi-objective optimization［J］. IEEE/ACM Transactions on Computational Biology and Bioinformatics， 2018， 15（6）： 1877-1890. 10.1109/tcbb.2017.2652453
21	GOH C K， TAN K C. A competitive-cooperative coevolutionary paradigm for dynamic multiobjective optimization［J］. IEEE Transactions on Evolutionary Computation， 2009， 13（1）：103-127. 10.1109/tevc.2008.920671
22	DEB K， THIELE L， LAUMANNS M， et al. Scalable test problems for evolutionary multiobjective optimization［M］// ABRAHAM A， JAIN L， GOLDBERG R. Evolutionary Multiobjective Optimization： Theoretical Advances and Applications， AI&KP. London： Springer， 2005： 105-145. 10.1007/1-84628-137-7
23	ZHOU A， JIN Y， ZHANG Q. A population prediction strategy for evolutionary dynamic multiobjective optimization［J］. IEEE Transactions on Cybernetics， 2014， 44（1）： 40-53. 10.1109/tcyb.2013.2245892
24	FARINA M， DEB K， AMATO P. Dynamic multiobjective optimization problems： test cases， approximations， and applications［J］. IEEE Transactions on Evolutionary Computation， 2004， 8（5）：425-442. 10.1109/tevc.2004.831456
25	DENG H， YEH C H， WILLIS R J. Inter-company comparison using modified TOPSIS with objective weights［J］. Computers and Operations Research， 2000， 27（10）：963-973. 10.1016/s0305-0548(99)00069-6
26	何春雄，龙卫江，朱锋峰. 概率论与数理统计［M］. 北京：高等教育出版社， 2012：79-80.
	HE C X， LONG W J， ZHU F F. Probability Theory and Mathematical Statistics［M］. Beijing： Higher Education Press， 2012：79-80.
27	CAO L， XU L， GOODMAN E D， et al. Decomposition-based evolutionary dynamic multiobjective optimization using a difference model［J］. Applied Soft Computing， 2019， 76： 473-490. 10.1016/j.asoc.2018.12.031
28	周永道，王会琦，吕王勇. 时间序列分析及应用［M］. 北京：高等教育出版社， 2015：69-87.
	ZHOU Y D， WANG H Q， LYU W Y. Time Series Analysis and Application［M］. Beijing： Higher Education Press， 2015：69-87.
29	WANG C， YEN G G， ZOU F. A novel predictive method based on key points for dynamic multi-objective optimization［J］. Expert Systems with Applications， 2022， 190： No.116127. 10.1016/j.eswa.2021.116127

[1]	Ye TIAN, Jinjin CHEN, Xingyi ZHANG. Hybrid optimizer combining evolutionary computation and gradient descent for constrained multi-objective optimization [J]. Journal of Computer Applications, 2024, 44(5): 1386-1392.
[2]	Kaiwen ZHAO, Peng WANG, Xiangrong TONG. Two-stage search-based constrained evolutionary multitasking optimization algorithm [J]. Journal of Computer Applications, 2024, 44(5): 1415-1422.
[3]	Maojiang TIAN, Mingke CHEN, Wei DU, Wenli DU. Two-stage differential grouping method for large-scale overlapping problems [J]. Journal of Computer Applications, 2024, 44(5): 1348-1354.
[4]	Wanting ZHANG, Wenli DU, Wei DU. Multi-timescale cooperative evolutionary algorithm for large-scale crude oil scheduling [J]. Journal of Computer Applications, 2024, 44(5): 1355-1363.
[5]	Jiawei ZHAO, Xuefeng CHEN, Liang FENG, Yaqing HOU, Zexuan ZHU, Yew‑Soon Ong. Review of evolutionary multitasking from the perspective of optimization scenarios [J]. Journal of Computer Applications, 2024, 44(5): 1325-1337.
[6]	Jianqiang LI, Zhou HE. Hybrid NSGA-Ⅱ for vehicle routing problem with multi-trip pickup and delivery [J]. Journal of Computer Applications, 2024, 44(4): 1187-1194.
[7]	Kedi NIU, Min LI, Zhongyuan YAO, Xueming SI. Review of blockchain consensus algorithms for internet of things [J]. Journal of Computer Applications, 2024, 44(12): 3678-3687.
[8]	Jie HUANG, Ruizi WU, Junli LI. Efficient adaptive robustness optimization algorithm for complex networks [J]. Journal of Computer Applications, 2024, 44(11): 3530-3539.
[9]	Yongjian MA, Xuhua SHI, Peiyao WANG. Constrained multi-objective evolutionary algorithm based on two-stage search and dynamic resource allocation [J]. Journal of Computer Applications, 2024, 44(1): 269-277.
[10]	Maozu GUO, Yazhe ZHANG, Lingling ZHAO. Electric vehicle charging station siting method based on spatial semantics and individual activities [J]. Journal of Computer Applications, 2023, 43(9): 2819-2827.
[11]	Saijuan XU, Zhenyu PEI, Jiawei LIN, Genggeng LIU. Constrained multi-objective evolutionary algorithm based on multi-stage search [J]. Journal of Computer Applications, 2023, 43(8): 2345-2351.
[12]	Erchao LI, Yanli CHENG. Dynamic multi-objective optimization algorithm based on weight vector clustering [J]. Journal of Computer Applications, 2023, 43(7): 2226-2236.
[13]	Zhihui GAO, Meng HAN, Shujuan LIU, Ang LI, Dongliang MU. Survey of high utility itemset mining methods based on intelligent optimization algorithm [J]. Journal of Computer Applications, 2023, 43(6): 1676-1686.
[14]	Bin WANG, Tian XIANG, Yidong LYU, Xiaofan WANG. Adaptive multi-scale feature channel grouping optimization algorithm based on NSGA‑Ⅱ [J]. Journal of Computer Applications, 2023, 43(5): 1401-1408.
[15]	Hairong XUE, Xiaolong HAN. Integrated scheduling considering automated guided vehicle charging strategy based on improved NSGA-Ⅱ [J]. Journal of Computer Applications, 2023, 43(12): 3848-3855.