基于新评价指标自适应预测的动态多目标优化算法

doi:10.11772/j.issn.1001-9081.2022091453

《计算机应用》唯一官方网站 ›› 2023, Vol. 43 ›› Issue (10): 3178-3187.DOI: 10.11772/j.issn.1001-9081.2022091453

所属专题：先进计算

基于新评价指标自适应预测的动态多目标优化算法

李二超(), 张生辉

兰州理工大学电气工程与信息工程学院，兰州 730050

收稿日期:2022-09-30 修回日期:2022-11-17 接受日期:2022-11-21 发布日期:2023-02-16 出版日期:2023-10-10
通讯作者: 李二超
作者简介:张生辉（1997—），男，甘肃武威人，硕士研究生，主要研究方向：动态多目标优化。
基金资助:
国家自然科学基金资助项目(62063019);甘肃省自然科学基金资助项目(20JR10RA152)

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

Erchao LI(), Shenghui ZHANG

College of Electrical and Information Engineering，Lanzhou University of Technology，Lanzhou Gansu 730050，China

Received:2022-09-30 Revised:2022-11-17 Accepted:2022-11-21 Online:2023-02-16 Published:2023-10-10
Contact: Erchao LI
About author:ZHANG Shenghui， born in 1997， M. S. candidate. His research interests include dynamic multi-objective optimization.
Supported by:
National Natural Science Foundation of China(62063019);Natural Science Foundation of Gansu Province(20JR10RA152)

摘要/Abstract

摘要：

现实生活中的多目标优化问题（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）值，可以更快地响应环境变化。

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

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

中图分类号:

TP273

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

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.

图/表 14

图1 动态多目标优化算法流程

Fig. 1 Flow of dynamic multi-objective optimization algorithm

图2 正理想点和负理想点

Fig. 2 Positive ideal point and negative ideal point

图3 同一解集在不同时刻下的关联程度

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

图4 参考直线示意图

Fig. 4 Schematic diagram of reference line

图5 支配种群个体的随机初始化

Fig. 5 Random initialization of dominating population individuals

图6 不同时刻种群轮廓质心

Fig. 6 Centroid of population profiles at different time

表1 不同度量权重时的平均IGD、SP值

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

表1 不同度量权重时的平均IGD、SP值

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

图7 平均IGD值随环境检测阈值的变化曲线

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

表2 四种算法的平均IGD值统计

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

表3 四种算法的平均SP值统计

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

表4 四种算法的平均GD值统计

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

图8 不同算法在6个测试函数上的IGD值演变曲线

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

图9 DMOP1在同一环境下不同阶段的解集分布

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

图10 DTLZ2在不同环境下的解集分布

Fig. 10 Solution set distribution of DTLZ2 in different environments

参考文献 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]	田茂江, 陈鸣科, 堵威, 杜文莉. 面向大规模重叠问题的两阶段差分分组方法[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1348-1354.
[2]	张莞婷, 杜文莉, 堵威. 基于多时间尺度协同的大规模原油调度进化算法[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1355-1363.
[3]	赵佳伟, 陈雪峰, 冯亮, 候亚庆, 朱泽轩, Yew‑Soon Ong. 优化场景视角下的进化多任务优化综述[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1325-1337.
[4]	刘晓芳, 张军. 概率驱动的动态多目标多智能体协同调度进化优化[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1372-1377.
[5]	魏凤凤, 陈伟能. 分布式数据驱动的多约束进化优化算法[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1393-1400.
[6]	田野, 陈津津, 张兴义. 面向约束多目标优化的进化计算与梯度下降联合优化算法[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1386-1392.
[7]	赵楷文, 王鹏, 童向荣. 基于双阶段搜索的约束进化多任务优化算法[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1415-1422.
[8]	夏吾吉, 黄鹤鸣, 更藏措毛, 范玉涛. 基于无监督学习和监督学习的抽取式文本摘要综述[J]. 《计算机应用》唯一官方网站, 2024, 44(4): 1035-1048.
[9]	牛科迪, 李敏, 姚中原, 斯雪明. 面向物联网的区块链共识算法综述[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3678-3687.
[10]	黄亚伟, 钱雪忠, 宋威. 基于双档案种群大小自适应方法的改进差分进化算法[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3844-3853.
[11]	黄杰, 武瑞梓, 李均利. 高效的自适应复杂网络鲁棒性优化算法[J]. 《计算机应用》唯一官方网站, 2024, 44(11): 3530-3539.
[12]	马勇健, 史旭华, 王佩瑶. 基于两阶段搜索与动态资源分配的约束多目标进化算法[J]. 《计算机应用》唯一官方网站, 2024, 44(1): 269-277.
[13]	郭茂祖, 张雅喆, 赵玲玲. 基于空间语义和个体活动的电动汽车充电站选址方法[J]. 《计算机应用》唯一官方网站, 2023, 43(9): 2819-2827.
[14]	徐赛娟, 裴镇宇, 林佳炜, 刘耿耿. 基于多阶段搜索的约束多目标进化算法[J]. 《计算机应用》唯一官方网站, 2023, 43(8): 2345-2351.
[15]	李二超, 程艳丽. 基于权重向量聚类的动态多目标进化算法[J]. 《计算机应用》唯一官方网站, 2023, 43(7): 2226-2236.

基于新评价指标自适应预测的动态多目标优化算法

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

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 14

参考文献 29

相关文章 15

编辑推荐

Metrics