Journal of Jilin University(Engineering and Technology Edition) ›› 2022, Vol. 52 ›› Issue (6): 1442-1458.doi: 10.13229/j.cnki.jdxbgxb20210082

Previous Articles    

Dynamic multi⁃objective optimization algorithm based on Kalman filter prediction strategy

Yong-jie MA(),Min CHEN   

  1. School of Physics and Electronic Engineering,Northwest Normal University,Lanzhou 730070,China
  • Received:2021-02-19 Online:2022-06-01 Published:2022-06-02

Abstract:

In order to deal with the environmental changes of dynamic multi-objective optimization more effectively, a dynamic multi-objective optimization algorithm based on Kalman filter prediction strategy is proposed. In the evolution process, a new calculation method is used to calculate the population center point. When the environment changes, the Kalman filter prediction model is used to predict the current population center point, and the approximate true Pareto center point of optimal solution set is used to correct the prediction value, and new individuals are generated based on the modified center point to reinitialize the population during the running of the algorithm; In order to increase the diversity of the population, five new individuals are randomly generated from the search space during the operation of the algorithm, and the corresponding number of individuals in the current population are randomly replaced. Compared with other dynamic multi-objective optimization algorithms in multiple test functions, the results show that the value of Modified Inverted Generational Distance (MIGD) in the whole evolution process is relatively small, and the value of Inverted Generational Distance (IGD) in the evolution is generally smaller than that of the contrast algorithm, and the calculation time is equivalent to that of the comparison algorithm.

Key words: pattern recognition and intelligent system, dynamic multi-objective optimization, evolutionary algorithm, Kalman filter prediction

CLC Number: 

  • TP273

Fig.1

Center point calculation"

Fig.2

Tracking comparison of different centerpoint calculation methods"

Table 1

Comparison of performance evaluation results (1)"

测试

函数

算法MIGD(SD)MIGD
1st stage2nd stage3rd stage
FDA1DNSGA-Ⅱ0.032 4(0.002 7)0.056 80.027 30.009 6
DSS0.008 0(0.000 53)0.011 80.006 90.007 1
KFPS0.007 40.000 290.008 50.007 40.006 8
DMOP1DNSGA-Ⅱ0.048 8(0.009 8)0.099 60.040 00.029 3
DSS0.025 1(0.007 9)0.069 70.015 30.008 1
KFPS0.013 2(0.002 5)0.012 90.015 50.007 6
DMOP2DNSGA-Ⅱ0.025 1(0.006 1)0.022 90.027 30.020 8
DSS0.013 2(0.000 54)0.010 20.016 00.007 6
KFPS0.012 7(0.000 19)0.007 40.015 60.000 74
DF2DNSGA-Ⅱ0.021 2(0.008 4)0.036 10.017 30.017 0
DSS0.010 1(0.000 67)0.013 20.009 40.009 0
KFPS0.009 9(0.000 66)0.009 50.010 00.009 5
DF3DNSGA-Ⅱ0.025 7(0.006 2)0.173 80.063 00.011 6
DSS0.108 3(0.003 2)0.055 40.020 50.011 2
KFPS0.018 1(0.000 11)0.011 30.021 20.011 4
F5DNSGA-Ⅱ0.311 2(0.023 4)0.611 20.286 60.103 4
DSS0.186 4(0.003 8)0.206 30.198 20.172 9
KFPS0.155 1(0.019 0)0.139 70.184 40.055 2
F6DNSGA-Ⅱ0.536 1(0.219 9)0.872 80.373 80.239 8
DSS0.152 4(0.026 1)0.135 10.145 20.179 5
KFPS0.118 5(0.016 0)0.126 80.134 50.135 4
F7DNSGA-Ⅱ0.374 0(0.519 6)0.319 20.341 60.158 5
DSS0.057 5(0.028 4)0.089 60.050 90.045 9
KFPS0.087 4(0.052 1)0.106 10.088 20.062 8

Table 2

Comparison of performance evaluation results (2)"

测试

函数

算法MIGD(SD)MIGD
1st stage2nd stage3rd stage
FDA1CKPS0.027 6(0.003 60)0.105 10.009 20.009 1
PPS0.052 8(0.009 13)0.240 60.010 20.006 2
KFPS0.008 10.000 450.008 20.007 50.007 1
DMOP1CKPS0.007 6(0.001 41)0.018 30.005 10.005 1
PPS0.037 9(0.051 52)0.141 30.020 90.005 7
KFPS0.018 9(0.002 5)0.012 70.014 10.014 2
DMOP2CKPS0.027 2(0.006 11)0.102 80.009 40.009 1
PPS0.060 7(0.010 23)0.279 90.011 10.006 1
KFPS0.013 4(0.000 38)0.011 00.014 10.013 8
FDA4CKPS0.021 2(0.001 65)0.138 50.115 90.116 3
PPS0.130 7(0.002 05)0.166 00.124 70.123 1
KFPS0.014 8(0.000 85)0.009 50.014 50.015 0

Table 3

Comparison of performanceevaluation results (3)"

测试函数算法MIGD
FDA1PFMOP0.0227
RLPS0.0137
KFPS0.0125
FDA2PFMOP0.1168
RLPS0.0518
KFPS0.0356
FDA3PFMOP0.2793
RLPS0.2753
KFPS0.5848
FDA4PFMOP0.0244
RLPS0.0228
KFPS0.0121
DMOP1PFMOP0.0088
RLPS0.0049
KFPS0.0158
DMOP2PFMOP0.0920
RLPS0.0693
KFPS0.0194

Fig.3

Pareto front obtained by three algorithms on the test function FDA1"

Fig.4

Pareto front obtained by three algorithms on the test function DMOP1"

Fig.5

Pareto front obtained by three algorithms on the test function DMOP2"

Fig.6

Pareto front obtained by three algorithms on the test function DF2"

Fig.7

Pareto front obtained by three algorithms on the test function DF3"

Fig.8

Pareto front obtained by three algorithms on the test function F5"

Fig.9

Pareto front obtained by three algorithms on the test function F6"

Fig.10

Pareto front obtained by three algorithms on the test function F7"

Fig.11

Pareto front obtained by three algorithms on the test function FDA4"

Fig.12

IGD value obtained by three algorithms on the test function FDA1"

Fig.13

IGD value obtained by three algorithms on the test function DMOP1"

Fig.14

IGD value obtained by three algorithms on the test function DMOP2"

Fig.15

IGD value obtained by three algorithms on the test function DF2"

Fig.16

IGD value obtained by three algorithms on the test function DF3"

Fig.17

IGD value obtained by three algorithms on the test function F5"

Fig.18

IGD value obtained by three algorithms on the test function F6"

Fig.19

IGD value obtained by three algorithms on the test function F7"

Table 4

Average computing time spent by the algorithm to solve different DMOPs"

测试函数DNSGA-ⅡDSSKFPS
FDA1239246258
DMOP1247253259
DMOP2249246255
DF2246279285
DF3254274269
1 孙宝凤, 任欣欣, 郑再思, 等. 考虑工人负荷的多目标流水车间优化调度[J]. 吉林大学学报: 工学版, 2021, 51(3): 900-909.
Sun Bao-feng, Ren Xin-xin, Zheng Zai-si, et al. Multi⁃objective flow shop optimal scheduling considering worker's load[J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 51(3): 900-909.
2 Marichelvam M K, Prabaharan T, Yang X S. A discrete firefly algorithm for the multi-objective hybrid flowshop scheduling problems[J]. IEEE Transactions on Evolutionary Computation, 2014, 18(2): 301-305.
3 马永杰, 陈敏, 龚影, 等. 动态多目标优化进化算法研究进展[J]. 自动化学报, 2020, 46(11): 2302-2318.
Ma Yong-jie, Chen Min, Gong Ying, et al. Research progress of dynamic multi-objective optimization evolutionary algorithm[J]. Acta Automatica Sinica, 2020, 46(11): 2302-2318.
4 刘敏, 曾文华. 记忆增强的动态多目标分解进化算法[J]. 软件学报, 2013, 24(7): 1571-1588.
Liu Min, Zeng Wen-hua. Memory enhanced dynamic multi-objective evolutionary algorithm based on decomposition[J]. Journal of Software, 2013, 24(7): 1571-1588.
5 Kordestani J K, Ranginkaman A E, Meybodi M R, et al. A novel framework for improving multi-population algorithms for dynamic optimization problems: a scheduling approach[J]. Swarm and Evolutionary Computation, 2019, 44: 788-805.
6 Woldesenbet Y G, Yen G G. Dynamic evolutionary algorithm with variable relocation[J]. IEEE Transactions on Evolutionary Computation, 2009, 13(3): 500-513.
7 胡成玉, 姚宏, 颜雪松. 基于多粒子群协同的动态多目标优化算法及应用[J]. 计算机研究与发展, 2013, 50(6): 1313-1323.
Hu Cheng-yu, Yao Hong, Yan Xue-song. Multiple particle swarms coevolutionary algorithm for dynamic multi-objective optimization problems and its application[J]. Journal of Computer Research and Development, 2013, 50(6): 1313-1323.
8 Zhou A M, Jin Y C, Zhang Q F. A population prediction strategy for evolutionary dynamic multiobjective optimization[J]. IEEE Transactions on Cybernetics, 2014, 44(1): 40-53.
9 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 Zou F, Yen G G, Tang L X. A knee-guided prediction approach for dynamic multi-objective optimization[J]. Information Sciences, 2020,509: 193-209.
11 Hatzakis I, Wallace D. Dynamic multi-objective optimization with evolutionary algorithms: a forward-looking approach[C]∥Proceedings of the 8th annual conference on Genetic and evolutionary computation. Seattle, Washington, USA, 2006: 1201-1208.
12 Koo W T, Goh C K, Tan K C. A predictive gradient strategy for multiobjective evolutionary algorithms in a fast changing environment[J]. Memetic Computing, 2010, 2(2): 87-110.
13 Ahrari A, Elsayed S, Sarker R, et al. Weighted pointwise prediction method for dynamic multiobjective optimization[J]. Information Sciences, 2021, 546: 349-367.
14 Rong M, Gong D W, Pedrycz W, et al. A multimodel prediction method for dynamic multiobjective evolutionary optimization[J]. IEEE Transactions on Evolutionary Computation, 2020, 24(2): 290-304.
15 李二超, 周扬. 基于分类的多策略预测方法求解动态多目标优化问题[J]. 控制与决策, 2021, 36(7): 1569-1580.
Li Er-chao, Zhou Yang. A classification-based Multi-strategy prediction method for dynamic multi-objective optimization problems[J]. Control and Decision, 2021, 36(7): 1569-1580.
16 Xie H P, Zou J, Yang S X, et al. A decison variable classification-based cooperative coevolutionary algorithm for dynamic multiobjective optimization[J]. Information Sciences, 2021, 560: 307-330.
17 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: No. 100786.
18 Muruganantham A, Tan K C, Vadakkepat P. Evolutionary dynamic multiobjective optimization via kalman filter prediction[J]. IEEE Transactions on Cybernetics, 2015, 46(12): 2862-2873.
19 李智翔, 李赟, 贺亮, 等. 使用新预测模型的动态多目标优化算法[J]. 西安交通大学学报, 2018, 52(10): 8-15.
Li Zhi-xiang, Li Yun, He Liang, et al. A dynamic multiobjective optimization algorithm with a new prediction model[J]. Journal of Xi'an Jiaotong University, 2018, 52(10): 8-15.
20 Farina M, Deb K, Amato P. Dynamic multiobjective optimization problems[J]. IEEE Transactions on Evolutionary Computation, 2004, 8(5): 425-442.
21 Kalman R E. A new approach to linear filtering and prediction problems[J]. Journal of basic Engineering, 1960, 82(1): 35-45.
22 Wu Y, Jin Y C, Liu X X. A directed search strategy for evolutionary dynamic multiobjective optimization[J]. Soft Computing, 2015, 19(11): 3221-3235.
23 Goh C K, Tan K C. A competitive-cooperative coevolutionary paradigm for dynamic multiobjective optimization[J]. IEEE Transactions on Evolutionary Computation, 2008, 13(1): 103-127.
24 Jiang S Y, Yang S X, Yao X, et al. Benchmark problems for CEC2018 competition on dynamic multiobjective optimisation[R]. United Kingdom: University of Birmingham, 2018.
25 Deb K, Karthik S. Dynamic multi-objective optimization and decision-making using modified NSGA-II: a case study on hydro-thermal power scheduling[C]∥International Conference on Evolutionary Multi-criterion Optimization, Berlin, Heidelberg, 2007: 803-817.
26 刘若辰, 李建霞, 刘静, 等. 动态多目标优化研究综述[J]. 计算机学报, 2020, 43(7): 1246-1278.
Liu Ruo-chen, Li Jian-xia, Liu Jing, et al. A survey on dynamic multiobjective optimization[J]. Chinese Journal of Computers, 2020, 43(7): 1246-1278.
27 武燕, 石露露, 周艳. 动态多目标优化: 测试函数和算法比较[J]. 控制与决策, 2020, 35(10): 2372-2380.
Wu Yan, Shi Lu-lu, Zhou Yan. Dynamic multi-objective optimization: test function and algorithm comparisons[J]. Control and Decision, 2020, 35(10): 2372-2380.
28 周爱民, 张青富, 张桂戌. 一种基于混合高斯模型的多目标进化算法[J]. 软件学报, 2014, 25(5): 913-928.
Zhou Ai-min, Zhang Qing-fu, Zhang Gui-xu. Multiobjective evolutionary algorithm based on mixture Gaussian models[J]. Journal of Software, 2014, 25(5): 913-928.
29 李二超, 赵雨萌. 基于参考线的预测策略求解动态多目标优化问题[J]. 控制与决策, 2020, 35(7): 1547-1560.
Li Er-chao, Zhou Yu-meng. Prediction strategy based on reference line for dynamic multi-objective optimization[J]. Control and Decision, 2020, 35(7): 1547-1560.
[1] Zhou-zhou LIU,Qian-yun ZHANG,Xin-hua MA,Han PENG. Compressed sensing signal reconstruction based on optimized discrete differential evolution algorithm [J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 51(6): 2246-2252.
[2] Zhuo-jun XU,Wen-ting YANG,Cheng-zhi YANG,Yan-tao TIAN,Xiao-jun WANG. Improved residual neural network algorithm for radar intra-pulse modulation classification [J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 51(4): 1454-1460.
[3] Bing-hai ZHOU,Qiong WU. Balancing and bi⁃objective optimization of robotic assemble lines [J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 51(2): 720-727.
[4] Fu LIU,Lu LIU,Tao HOU,Yun LIU. Night road image enhancement method based on optimized MSR [J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 51(1): 323-330.
[5] Lei JIANG,Ren-chu GUAN. Design of fuzzy comprehensive evaluation system for talent quality based on multi⁃objective evolutionary algorithm [J]. Journal of Jilin University(Engineering and Technology Edition), 2020, 50(5): 1856-1861.
[6] Lei CHEN,Jiang⁃feng WANG,Yuan⁃li GU,Xue⁃dong YAN. Multi⁃source traffic data fusion algorithm based onmind evolutionary algorithm optimization [J]. Journal of Jilin University(Engineering and Technology Edition), 2019, 49(3): 705-713.
[7] LIU Fu, LAN Xu-teng, HOU Tao, KANG Bing, LIU Yun, LIN Cai-xia. Metagenomic clustering method based on k-mer frequency optimization [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1593-1599.
[8] HU Guan-yu, QIAO Pei-li. High dimensional differential evolutionary algorithm based on cloud population for network security prediction [J]. 吉林大学学报(工学版), 2016, 46(2): 568-577.
[9] LI Gen,LI Wen-hui. Facial feature tracking based on mind evolutionary algorithm [J]. 吉林大学学报(工学版), 2015, 45(2): 606-612.
[10] LI Gen,LI Wen-hui. Face occlusion recognition based on MEBML [J]. 吉林大学学报(工学版), 2014, 44(5): 1410-1416.
[11] YOU Xiao-ming, LIU Sheng, WANG Yu-ming. Quantum-behaved network resource parallel allocation optimization model and application [J]. 吉林大学学报(工学版), 2012, 42(增刊1): 341-345.
[12] DING Hui, LI Hong-guang. Agent-based evolutionary approach towards solving constrained multi-objective optimization problems [J]. 吉林大学学报(工学版), 2011, 41(增刊1): 173-178.
[13] ZHAO Wen-hong1, WANG Wei1,2, WANG Yu-ping2, HAO Ming-qiang3 . ZHAO Wen-hong1, WANG Wei1,2, WANG Yu-ping2, HAO Ming-qiang3 [J]. 吉林大学学报(工学版), 2008, 38(04): 865-870.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!