基于个体预测的动态多目标优化算法

doi:10.3785/j.issn.1008-973X.2023.11.001

浙江大学学报(工学版)

2023, Vol. 57

Issue (11): 2133-2146 DOI: 10.3785/j.issn.1008-973X.2023.11.001

计算机技术

基于个体预测的动态多目标优化算法

王万良(

),陈忠馗,吴菲,王铮,俞梦娇

浙江工业大学计算机科学与技术学院，浙江杭州 310023

Dynamic multi-objective optimization algorithm based on individual prediction

Wan-liang WANG(

),Zhong-kui CHEN,Fei WU,Zheng WANG,Meng-jiao YU

College of Computer Science and Technology, Zhejiang University of Technology, Hangzhou 310023, China

全文: PDF(1723 KB) HTML

摘要：

为了快速追踪随环境变化的动态多目标优化问题的Pareto前沿，提出基于个体预测的动态多目标优化算法(IPS). 利用参考点联系算法筛选出特殊点，该特殊点具有良好的收敛性和多样性，通过对特殊点集的预测快速响应环境变化. 提出针对种群中心点预测的反馈校正机制，在预测非支配解集的过程中，对预测步长进行反馈校正，从而使预测更加准确；为了避免算法陷入局部最优，提出混合多样性维持机制，引入由拉丁超立方抽样和精度可控的突变策略分别产生的随机个体，以提高种群的多样性. 将所提算法与其他4种动态多目标优化算法进行对比分析，实验结果表明，IPS能够平衡种群的多样性和收敛性，在FDA、DMOP、F5~F10系列问题上，实验结果优于其他4种算法.

关键词： 动态多目标优化; 参考点联系算法; 特殊点; 反馈校正; 多样性

Abstract:

A dynamic multi-objective optimization algorithm based on individual prediction (IPS) was proposed to quickly track the Pareto optimal front of the dynamic multi-objective optimization problem that changed with the environment. Firstly, the special points with good convergence and diversity were selected by the reference point relation algorithm, and the environment changes can be quickly responded to by predicting the special points set. Secondly, a feedback correction mechanism for population center point predication was proposed, and in the process of predicting the non-dominant solution set, the prediction step size was corrected to make the prediction more accurate. Finally, to avoid the algorithm falling into local optimal, a hybrid diversity maintenance mechanism was proposed, which introduced random individuals generated by Latin hypercube sampling and a precision controllable mutation strategy to improve the diversity of the population. The proposed algorithm was compared with the other four dynamic multi-objective optimization algorithms. Experimental results show that IPS can balance the diversity and convergence of the population, and the experimental results are better than that of the other four algorithms on the FDA, DMOP, and F5~F10 test suite.

Key words: dynamic multi-objective optimization reference point relation algorithm special point correction by feedback diversity

收稿日期: 2022-11-30 出版日期: 2023-12-11

CLC:

TP 301

基金资助: 国家自然科学基金资助项目(51875524, 61873240)；浙江大学CAD&CG国家重点实验室开放课题资助项目(A2210)

作者简介: 王万良（1957—），男，教授，从事人工智能及其自动化、网络控制研究. orcid.org/0000-0002-1552-5075.E-mail： zjutwwl@zjut.edu.cn

	服务
	把本文推荐给朋友
	加入引用管理器
	E-mail Alert
	作者相关文章
	王万良
	陈忠馗
	吴菲
	王铮
	俞梦娇

引用本文:

王万良,陈忠馗,吴菲,王铮,俞梦娇. 基于个体预测的动态多目标优化算法[J]. 浙江大学学报(工学版), 2023, 57(11): 2133-2146.

Wan-liang WANG,Zhong-kui CHEN,Fei WU,Zheng WANG,Meng-jiao YU. Dynamic multi-objective optimization algorithm based on individual prediction. Journal of ZheJiang University (Engineering Science), 2023, 57(11): 2133-2146.

链接本文:

https://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2023.11.001 或 https://www.zjujournals.com/eng/CN/Y2023/V57/I11/2133

表 1 4种不同类型的DMOPs

图 1 RM-MEDA流程图

图 2 非支配个体与参考点关联示意图

图 3 特殊点预测策略示意图

图 4 决策空间变量的步长探索

图 5 IPS流程图

问题	阶段	MIGD
问题	阶段	PPS	CKPS	SPPS	HPPCM	IPS
1）注：?和?分别表示IPS算法的性能显著优于和等同于相应的算法.
FDA1	总阶段	0.0592(0.01680)?^1）	0.0297(0.00636)?	0.0264(0.00630)?	0.0211(0.00518)?	0.0188(0.00423)
	第1阶段	0.2743(0.08625)?	0.1168(0.03308)?	0.1032(0.03278)?	0.0813(0.02744)?	0.0692(0.02245)
	第2阶段	0.0100(0.00117)?	0.0090(0.00013)?	0.0082(0.00021)?	0.0068(0.00076)?	0.0067(0.00029)
	第3阶段	0.0063(0.00011)	0.0089(0.00020)?	0.0081(0.00022)?	0.0067(0.00069)	0.0070(0.00046)
FDA2	总阶段	0.0093(0.00120)?	0.0085(0.00056)?	0.0087(0.00044)?	0.0079(0.00087)?	0.0076(0.00075)
	第1阶段	0.0219(0.00539)?	0.0183(0.00276)?	0.0170(0.00248)?	0.0172(0.00419)?	0.0160(0.00376)
	第2阶段	0.0067(0.00058)?	0.0065(0.00021)?	0.0067(0.00025)?	0.0058(0.00028)?	0.0057(0.00009)
	第3阶段	0.0059(0.00012)?	0.0060(0.00010)?	0.0068(0.00026)?	0.0056(0.00004)	0.0056(0.00004)
FDA3	总阶段	0.0843(0.01313)?	0.0383(0.00726)?	0.0363(0.00724)?	0.0216(0.00479)	0.0258(0.00647)
	第1阶段	0.2590(0.06128)?	0.1222(0.03371)?	0.1323(0.03870)?	0.0862(0.02561)	0.1023(0.03297)
	第2阶段	0.0436(0.01250)?	0.0189(0.00279)?	0.0137(0.00325)?	0.0064(0.00038)	0.0074(0.00060)
	第3阶段	0.0419(0.00778)?	0.0179(0.00243)?	0.0133(0.00262)?	0.0061(0.00035)	0.0077(0.00067)
FDA4	总阶段	0.1314(0.00333)?	0.1184(0.00230)?	0.1095(0.00211)?	0.1020(0.00104)?	0.1010(0.00148)
	第1阶段	0.1609(0.00920)?	0.1332(0.00845)?	0.1300(0.00688)?	0.1209(0.00692)?	0.1161(0.00498)
	第2阶段	0.1258(0.00312)?	0.1148(0.00268)?	0.1050(0.00221)?	0.0969(0.00198)	0.0976(0.00167)
	第3阶段	0.1230(0.00312)?	0.1149(0.00232)?	0.1043(0.00234)?	0.0980(0.00245)?	0.0973(0.00216)
DMOP1	总阶段	0.1296(0.24085)?	0.0076(0.00174)?	0.0099(0.00276)?	0.0068(0.00504)?	0.0064(0.00052)
	第1阶段	0.5522(1.06835)?	0.0181(0.00901)?	0.0310(0.01421)?	0.0161(0.00382)?	0.0118(0.00272)
	第2阶段	0.0528(0.09413)?	0.0050(0.00005)	0.0050(0.00070)	0.0047(0.00004)	0.0051(0.00002)
	第3阶段	0.0057(0.00002)?	0.0051(0.00006)	0.0048(0.00054)	0.0046(0.00006)	0.0051(0.00005)
DMOP2	总阶段	0.0659(0.03602)?	0.0267(0.00616)?	0.0316(0.00584)?	0.0252(0.00504)?	0.0223(0.00254)
	第1阶段	0.3008(0.16637)?	0.1006(0.03204)?	0.1263(0.03040)?	0.1021(0.02651)?	0.0848(0.01365)
	第2阶段	0.0142(0.01391)?	0.0092(0.00012)?	0.0093(0.00026)?	0.0069(0.00047)	0.0075(0.00020)
	第3阶段	0.0061(0.00003)?	0.0090(0.00020)?	0.0090(0.00030)?	0.0069(0.00042)	0.0073(0.00030)
DMOP3	总阶段	0.0482(0.04869)?	0.0277(0.00629)	0.0279(0.00828)	0.0242(0.00544)	0.0288(0.00431)
	第1阶段	0.2173(0.00125)?	0.1065(0.03292)	0.1111(0.04314)	0.0958(0.02797)	0.1204(0.02258)
	第2阶段	0.0099(0.00010)?	0.0091(0.00017)?	0.0082(0.00018)?	0.0078(0.00138)?	0.0071(0.00047)
	第3阶段	0.0062(0.00954)	0.0089(0.00011)?	0.0081(0.00017)?	0.0066(0.00043)	0.0069(0.00017)

表 2 5种策略在FDA和DMOP上的MIGD指标

问题	阶段	MHVD
问题	阶段	PPS	CKPS	SPPS	HPPCM	IPS
F5	总阶段	0.5124(0.07330)?	0.2769(0.01312)?	0.2782(0.01280)?	0.2745(0.00810)?	0.2725(0.01327)
	第1阶段	1.4519(0.28264)?	0.4064(0.07001)	0.4155(0.06438)?	0.3752(0.03314)	0.4132(0.05877)
	第2阶段	0.3309(0.05948)?	0.2466(0.00230)?	0.2455(0.00379)?	0.2508(0.00777)?	0.2379(0.00468)
	第3阶段	0.2477(0.00173)?	0.2456(0.00171)?	0.2457(0.00174)?	0.2505(0.00681)?	0.2403(0.00508)
F6	总阶段	0.3222(0.03755)?	0.2659(0.00655)?	0.2693(0.01432)?	0.2652(0.00692)	0.2655(0.00412)
	第1阶段	0.6239(0.18580)?	0.3462(0.03272)?	0.3647(0.07603)?	0.3470(0.03468)?	0.3455(0.02249)
	第2阶段	0.2545(0.00503)?	0.2467(0.00117)?	0.2467(0.00093)?	0.2455(0.00147)	0.2459(0.00118)
	第3阶段	0.2466(0.00144)	0.2470(0.00104)	0.2467(0.00095)	0.2459(0.00084)	0.2472(0.00165)
F7	总阶段	0.3596(0.03072)?	0.2690(0.01654)?	0.2664(0.00844)?	0.2672(0.01441)?	0.2614(0.00741)
	第1阶段	0.8307(0.15396)?	0.3740(0.08647)?	0.3560(0.04440)?	0.3633(0.07469)?	0.3332(0.03972)
	第2阶段	0.2492(0.00359)?	0.2443(0.00101)	0.2454(0.00071)?	0.2444(0.00074)?	0.2443(0.00105)
	第3阶段	0.2463(0.00111)?	0.2439(0.00080)	0.2447(0.00093)?	0.2443(0.00075)	0.2444(0.00094)
F8	总阶段	0.3954(0.03307)?	0.4108(0.02681)?	0.3852(0.01921)?	0.3223(0.01427)	0.3277(0.00396)
	第1阶段	0.6076(0.16045)?	0.5809(0.13203)?	0.5864(0.08519)?	0.4663(0.05926)?	0.4568(0.02104)
	第2阶段	0.3504(0.01283)?	0.3684(0.05066)?	0.3374(0.00970)?	0.2889(0.00725)	0.2959(0.00706)
	第3阶段	0.3397(0.01085)?	0.3725(0.02345)?	0.3373(0.01247)?	0.2872(0.01162)	0.2983(0.00646)
F9	总阶段	0.6408(0.07758)?	0.3705(0.03890)?	0.3411(0.01947)?	0.3353(0.04994)?	0.3113(0.02232)
	第1阶段	1.6206(0.23861)?	0.7310(0.18668)?	0.6319(0.06566)?	0.6164(0.12440)?	0.5565(0.10975)
	第2阶段	0.4945(0.09275)?	0.2950(0.01834)?	0.2697(0.01675)?	0.2695(0.05153)?	0.2593(0.00953)
	第3阶段	0.3216(0.07873)?	0.2746(0.00704)?	0.2744(0.02416)?	0.2674(0.02417)?	0.2468(0.01399)
F10	总阶段	0.7720(0.06904)?	0.3612(0.01334)	0.3361(0.02204)	0.4034(0.05090)?	0.3927(0.03353)
	第1阶段	1.5730(0.10988)?	0.7354(0.05476)?	0.6343(0.10452)?	0.6220(0.11651)?	0.5665(0.09724)
	第2阶段	0.6341(0.13136)?	0.2782(0.01809)	0.2652(0.00560)	0.3423(0.04547)	0.3631(0.01942)
	第3阶段	0.5294(0.08679)?	0.2666(0.01608)	0.2653(0.00905)	0.3606(0.06961)?	0.3398(0.03363)

表 3 5种策略在F5~F10上的MHVD指标

表 4 5种策略在部分测试问题上的MIGD指标

表 5 5种策略在部分测试问题上的MHVD指标

图 6 5种策略在求解DMOP2过程中所获得的解集

图 7 5种策略在求解F9过程中所获得的解集

图 8 IPS(0)和IPS(9)在F6和F9问题上运行20次时环境变化的IGD趋势

图 9 IPS和IPS(N)在F6和F9问题上运行20次时环境变化的IGD趋势

1	ZOU J, ZHENG J, DENG C, et al An evaluation of non-redundant objective sets based on the spatial similarity ratio[J]. Soft Computing, 2015, 19 (8): 2275- 2286
2	王万良, 金雅文, 陈嘉诚, 等多角色多策略多目标粒子群优化算法[J]. 浙江大学学报: 工学版, 2022, 56 (3): 531- 541 WANG Wan-liang, JIN Ya-wen, CHEN Jia-cheng, et al Multi-objective particle swarm optimization algorithm with multi-role and multi-strategy[J]. Journal of Zhejiang University: Engineering Science, 2022, 56 (3): 531- 541
3	张程, 金涛, 李培强, 等采用多目标蝙蝠算法的电力系统广域协调控制策略[J]. 浙江大学学报: 工学版, 2019, 53 (3): 589- 597 ZHANG Cheng, JIN Tao, LI Pei-qiang, et al Wide-area coordination control strategy for power system using multi-objective bat algorithm[J]. Journal of Zhejiang University: Engineering Science, 2019, 53 (3): 589- 597
4	陈俊杰, 李洪均, 曹张华性能感知的核心网控制面资源分配算法[J]. 浙江大学学报: 工学版, 2021, 55 (9): 1782- 1787 CHEN Jun-jie, LI Hong-jun, CAO Zhang-hua Performance-aware resource allocation algorithm for core network control plane[J]. Journal of Zhejiang University: Engineering Science, 2021, 55 (9): 1782- 1787
5	DEB K, PRATAP A, AGARWAL S, et al A fast and elitist multiobjective genetic algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002, 6 (2): 182- 197 doi: 10.1109/4235.996017
6	ZHANG Q, ZHOU A, JIN Y RM-MEDA: a regularity model-based multiobjective estimation of distribution algorithm[J]. IEEE Transactions on Evolutionary Computation, 2008, 12 (1): 41- 63 doi: 10.1109/TEVC.2007.894202
7	ZHANG Q, LI H MOEA/D: a multiobjective evolutionary algorithm based on decomposition[J]. IEEE Transactions on Evolutionary Computation, 2007, 11 (6): 712- 731 doi: 10.1109/TEVC.2007.892759
8	GIUSEPPE P, STEFANO S To Celigny, in the footprints of vilfredo pareto's "optimum" [Historical Corner][J]. IEEE Antennas and Propagation Magazine, 2014, 56 (3): 249- 254 doi: 10.1109/MAP.2014.6867724
9	HATZAKIS I, WALLACE D. Dynamic multi-objective optimization with evolutionary algorithms: a forward-looking approach [C]// Genetic and Evolutionary Computation Conference. Washington: ACM, 2006: 1201-1208.
10	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 doi: 10.1109/TCYB.2013.2245892
11	ZOU J, LI Q, YANG S, et al A prediction strategy based on center points and knee points for evolutionary dynamic multi-objective optimization[J]. Applied Soft Computing, 2017, 61: 806- 818 doi: 10.1016/j.asoc.2017.08.004
12	LI Q, ZOU J, YANG S, et al A predictive strategy based on special points for evolutionary dynamic multi-objective optimization[J]. Soft Computing, 2019, 23 (11): 3723- 3739 doi: 10.1007/s00500-018-3033-0
13	RONG M, GONG D, ZHANG Y, et al Multidirectional prediction approach for dynamic multiobjective optimization problems[J]. IEEE Transactions on Cybernetics, 2018, 49 (9): 3362- 3374
14	CHEN Y, ZOU J, LIU Y, et al Combining a hybrid prediction strategy and a mutation strategy for dynamic multiobjective optimization[J]. Swarm and Evolutionary Computation, 2022, 70: 101041 doi: 10.1016/j.swevo.2022.101041
15	EATON J, YANG S, GONGORA M Ant colony optimization for simulated dynamic multi-objective railway junction rescheduling[J]. IEEE Transactions on Intelligent Transportation Systems, 2017, 18 (11): 1- 13 doi: 10.1109/TITS.2017.2760981
16	ZHANG Z, QIAN S Artificial immune system in dynamic environments solving time-varying non-linear constrained multi-objective problems[J]. Soft Computing, 2011, 15 (7): 1333- 1349 doi: 10.1007/s00500-010-0674-z
17	HUTZSCHENREUTER A K, PETER A N, HAN B, et al. Evolutionary multiobjective optimization for dynamic hospital resource management [C]// Evolutionary Multi-Criterion Optimization. Nantes: EMO, 2013: 320-334.
18	GUO Y, CHENG J, LUO S, et al Robust dynamic multi-objective vehicle routing optimization method[J]. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2018, 15 (6): 1891- 1903 doi: 10.1109/TCBB.2017.2685320
19	SAHMOUD S, TOPCUOGLU H R. Sensor-based change detection schemes for dynamic multi-objective optimization problems [C]// Symposium Series on Computational Intelligence. Athens: IEEE, 2016: 1-8.
20	RICHTER H. Detecting change in dynamic fitness landscapes [C]// IEEE Congress on Evolutionary Computation. Trondheim: IEEE, 2009: 1613-1620.
21	LIU R, LI J, FAN J, et al A coevolutionary technique based on multi-swarm particle swarm optimization for dynamic multi-objective optimization[J]. European Journal of Operational Research, 2017, 261 (3): 1028- 1051 doi: 10.1016/j.ejor.2017.03.048
22	SAHMOUD S, TOPCUOGLU H R. A memory-based NSGA-II algorithm for dynamic multi-objective optimization problems [C]// Applications of Evolutionary Computation: 19th European Conference. Porto: [s. n. ], 2016: 296-310.
23	FARINA M, DEB K, PAOLO A Dynamic multiobjective optimization problems: test cases, approximations, and applications[J]. IEEE Transactions on Evolutionary Computation, 2004, 8 (5): 311- 326
24	DAS I, DENNIS J E Normal boundary intersection: a new method for generating the Pareto surface in nonlinear multicriteria optimization problems[J]. SIAM Journal on Optimization, 1998, 8 (3): 631- 657 doi: 10.1137/S1052623496307510
25	DEB K, JAIN H An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: solving problems with box constraints[J]. Evolutionary Computation, IEEE Transactions, 2014, 18 (4): 577- 601 doi: 10.1109/TEVC.2013.2281535
26	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[J]. IEEE Transactions on Evolutionary Computation, 2014, 18 (4): 602- 622 doi: 10.1109/TEVC.2013.2281534
27	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 doi: 10.1016/j.asoc.2017.05.008
28	ZHENG J, ZHOU Y, ZOU J, et al A prediction strategy based on decision variable analysis for dynamic multi-objective optimization[J]. Swarm and Evolutionary Computation, 2021, 60: 100786 doi: 10.1016/j.swevo.2020.100786
29	LIANG Z, ZOU Y, ZHENG S, et al A feedback-based prediction strategy for dynamic multi-objective evolutionary optimization[J]. Expert Systems with Applications, 2021, 172: 114594 doi: 10.1016/j.eswa.2021.114594
30	LIANG Z, WU T, MA X, et al A dynamic multiobjective evolutionary algorithm based on decision variable classification[J]. IEEE Transactions on Cybernetics, 2022, 52 (3): 1602- 1615 doi: 10.1109/TCYB.2020.2986600
31	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 doi: 10.1109/TEVC.2019.2922834
32	MCKAY M D, BECKMAN R J, CONOVER W J A comparison of three methods for selecting values of input variables in the analysis of output from a computer code[J]. Technometrics, 2012, 42 (1): 55- 61
33	ZHANG K, SHEN C, LIU X, et al Multiobjective evolution strategy for dynamic multiobjective optimization[J]. IEEE Transactions on Evolutionary Computation, 2020, 24 (5): 974- 988 doi: 10.1109/TEVC.2020.2985323
34	GOH C K, TAN C K A competitive-cooperative coevolutionary paradigm for dynamic multiobjective optimization[J]. IEEE Transactions on Evolutionary Computation, 2009, 13 (1): 103- 127 doi: 10.1109/TEVC.2008.920671
35	YUAN Y, XU H, WANG B, et al Balancing convergence and diversity in decomposition-based many-objective optimizers[J]. IEEE Transactions on Evolutionary Computation, 2015, 20 (2): 180- 198
36	ZHOU A, JIN Y, ZHANG Q, et al. Prediction-based population re-initialization for evolutionary dynamic multi-objective optimization [C]// International conference on evolutionary multi-criterion optimization. Matsushima: EMO, 2007: 832-846.

[1]	朱雅光,刘春潮,张亮. 基于虚拟运动神经网络的六足机器人行为控制[J]. 浙江大学学报(工学版), 2022, 56(6): 1107-1118.
[2]	王万良,金雅文,陈嘉诚,李国庆,胡明志,董建杭. 多角色多策略多目标粒子群优化算法[J]. 浙江大学学报(工学版), 2022, 56(3): 531-541.
[3]	何杰光,彭志平,崔得龙,李启锐. 基于种群多样性的自适应乌鸦搜索算法[J]. 浙江大学学报(工学版), 2022, 56(12): 2426-2435.
[4]	韩冬阳,林泽宇,郑宇,郑美妹,夏唐斌. 基于选择性深度神经网络集成的涡扇发动机剩余寿命预测[J]. 浙江大学学报(工学版), 2022, 56(11): 2109-2118.
[5]	刘洲洲, 李士宁, 李彬, 王皓, 张倩昀, 郑然. 基于弹性碰撞优化算法的传感云资源调度[J]. 浙江大学学报(工学版), 2018, 52(8): 1431-1443.
[6]	柳景青, 罗志逢, 周晓燕, 何晓芳, 任红星, 胡宝兰, 裘尚德. 水流剪切力对供水管道管壁生物膜生长的影响[J]. 浙江大学学报(工学版), 2016, 50(2): 250-256.
[7]	张震, 潘再平, 潘晓弘. 骨干粒子群算法两种不同实现的优化特性[J]. 浙江大学学报(工学版), 2015, 49(7): 1350-1357.
[8]	叶建芳王正肖潘晓弘. 免疫粒子群优化算法在车间作业调度中的应用[J]. J4, 2008, 42(5): 863-868.

Viewed

Full text

Abstract

Cited

Shared

Discussed