-
摘要: 为了快速跟踪动态多目标优化问题变化的Pareto前沿，本文提出一种基于参考点预测策略的动态多目标优化算法（PDMOP）.该算法对关联到相同参考点的个体建立时间序列，并对这些时间序列通过线性回归模型预测新环境下种群.同时，将历史时刻的预测误差反馈到当前预测中来提高预测的准确性，并在每个预测的个体上加入扰动来增加初始种群多样性，从而能够加快算法在新环境下的收敛速度.通过4个标准测试函数对该算法测试，并和两个现有算法对比分析，结果表明所提算法在处理动态多目标优化问题时能够保持良好的性能.Abstract: In tracking the moving Pareto front of dynamic multi-objective optimization problem as soon as possible, a new algorithm based on reference point prediction (PDMOP) is proposed. Firstly, PDMOP distributes the past individuals to different time series according to the information of reference point association. Then for these time series, a linear regression model is used to predict the new environment population. At the same time, historical prediction error is added to the current prediction to enhance prediction accuracy, and a Gauss noise is added to every new individual to increase the initialized population diversity. In this way, the algorithm can speed up convergence in the new environment. The results of four benchmark problems and the comparison with other two existing dynamic multi-objective algorithms indicate that the proposed algorithm can maintain better performance in dealing with dynamic multi-objective problems.
-
Key words:
- Dynamic optimization /
- multi-objective optimization /
- time series /
- prediction /
- reference point
1) 本文责任编委 魏庆来 -
图 1 两目标优化问题的结构化参考点
Fig. 1 Two-objective optimization problem structured reference point
图 2 两目标优化问题个体和参考点关联
Fig. 2 Two objective optimization problem of individual associated with reference point
表 1 个体关联算法
Table 1 Individual correlation algorithm
算法1 个体关联算法 步骤1 for $i=1:H$ do ///H参考点的个数 步骤2 链接参考点和原点作为该参考点参考线 步骤3 end 步骤4 for $i=1:N$ do ///N种群的个体数 步骤5 for $j=1:H$ do 步骤6 计算每个个体和参考线的距离 步骤7 end 步骤8 与个体垂直距离最小的参考点记录为关联参考点 步骤9 end 
下载: 导出CSV
表 2 PDMOP算法伪代码
Table 2 Pseudo code of PDMOP
算法2 PDMOP算法伪代码 步骤1 参数及种群初始化:设置初始化参数, 时间常数τt, 种群大小pop, 进化代数max_gen, 并在决策空间内随机产生规模为pop初始种群p0t.令t=0, T=0, gen=0 步骤2 环境探测：根据式(7) 计算η (t), 如果η (t) < η则转步骤3, 否则转步骤4. 步骤3 环境未发生变化, 进化操作更新父代个体. 步骤3.1 进化操作:以一定的交叉概率pc, 变异概率pm, 对当前父代个体ptgen进行进化操作, 产生新的种群Ωgent. 步骤3.2 对Ωtgen∪ptgen快速排序, 并根据参考点关联选择个体pt+1gen作为下一代个体, 转步骤5. 步骤4 环境发生变化, 产生预测种群响应变化 步骤4.1 产生预测种群, 基于式(4) 所示预测模型, 产生与种群大小为pop的预测种群, 并将其作为下一时刻算法的初始种群. 步骤4.2 存储历史信息, 转步骤5. 步骤5 判断是否满足算法停止条件, 若满足则停止; 否则, t=t + 1, 转步骤2.
下载: 导出CSV
表 3 测试函数
Table 3 Test instance
测试函数 搜索空间 目标值, PS和PF FDA1 $[0, 1]\times[-1, 1]^{n - 1}$ $\begin{array}{l} {f_1}\left( {{\pmb x}, t} \right) = {{\pmb x}_1}, {f_2}\left( {{\pmb x}, t} \right) = g\left( {1 - \sqrt {\frac{{{f_1}}}{g}} } \right)\\ g = 1 + {\sum\nolimits_{i = 2}^n {\left( {{x_i} - G\left( t \right)} \right)} ^2}, G = \sin \left( {0.5\pi \frac{t}{{{n_T}}}} \right)\\ {\rm PS}\left( t \right):0 \le {x_1} \le 1, {x_i} = G, {\rm for}{\kern 1pt} {\kern 1pt} i = 2, \cdots, n\\ {\rm PF}\left( t \right):{f_2} = 1 - \sqrt {{f_1}}, {\kern 1pt} {\kern 1pt} {\kern 1pt} 0 \le {f_1} \le 1 \end{array}$ FDA3 $[0, 1]\times [-1, 1]^{n - 1}$ $\begin{array}{l} {f_1}\left( {{\pmb x}, t} \right) = {\pmb x}_1^F, {f_2}\left( {{\pmb x}, t} \right) = g\left( {1 - \sqrt {\frac{{{f_1}}}{g}} } \right)\\ g = 1 + G + {\sum\nolimits_{i = 2}^n {\left( {{x_i} - G\left( t \right)} \right)} ^2}\\ G = \left| {\sin \left( {0.5\pi \frac{t}{{{n_T}}}} \right)} \right|, {\kern 1pt} {\kern 1pt} F = {\kern 1pt} {10^{2\sin \left( {0.5\pi t} \right)}}\\ \textrm{PS}\left( t \right):0 \le {x_1} \le 1, {x_i} = G, \textrm{for}{\kern 1pt} {\kern 1pt} i = 2, \cdots, n\\ \textrm{PF}\left( t \right):{f_2} = 1 - \sqrt {{f_1}}, {\kern 1pt} {\kern 1pt} {\kern 1pt} 0 \le {f_1} \le 1 \end{array}$ FDA4 ${[0, 1]^n}$ $\begin{array}{l} {f_1}\left( {{\pmb x}, t} \right) = \left( {1 + g} \right)\cos \left( {0.5\pi {x_1}} \right)\\ {f_2}\left( {{\pmb x}, t} \right) = \left( {1 + g} \right)\sin \left( {0.5\pi {x_1}} \right)\\ g = {\sum\nolimits_{i = 2}^n {\left( {{x_i} - G\left( t \right)} \right)} ^2}\\ G = \left| {\sin \left( {0.5\pi \frac{t}{{{n_T}}}} \right)} \right|\\ \textrm{PS}\left( t \right):0 \le {x_1} \le 1, {x_i} = G, \textrm{for}{\kern 1pt} {\kern 1pt} i = 2, \cdots, n\\ \textrm{PF}\left( t \right):f_1^2 + f_2^2 = 1 \end{array}$ FDA5 ${[0, 1]^n}$ $\begin{array}{l} {f_1}\left( {{\pmb x}, t} \right) = \left( {1 + g} \right)\cos \left( {0.5\pi {y_1}} \right)\\ {f_2}\left( {{\pmb x}, t} \right) = \left( {1 + g} \right)\sin \left( {0.5\pi {y_1}} \right)\\ g = G + {\sum\nolimits_{i = 2}^n {\left( {{x_i} - G\left( t \right)} \right)} ^2}\\ G = \left| {\sin \left( {0.5\pi \frac{t}{{{n_T}}}} \right)} \right|\\ {y_i} = x_i^F, F = 1 + 100{\sin ^4}\left( {0.5\pi t} \right)\\ \textrm{PS}\left( t \right):0 \le {x_1} \le 1, {x_i} = G, \textrm{for}{\kern 1pt} {\kern 1pt} i = 2, \cdots, n\\ \textrm{PF}\left( t \right):f_1^2 + f_2^2 = {\left( {1 + G} \right)^2} \end{array}$
下载: 导出CSV
表 4 算法性能评价比较
Table 4 The comparison of algorithm performance
测试函数 性能评价指标算法 IGD HVR FDA1 DNSGA-Ⅱ 0.071365018(0.002269256) 0.71946556 (0.000297) DSS 0.02600748(0.001803211) 0.70582515 (0.000535) PDMOP 0.015680472 (0.000359908) 0.73517365 (0.000364) FDA3 DNSGA-Ⅱ 0.044540016 (0.001073) 0.71305567 (0.000135) DSS 0.025739528 (0.001627) 0.6885821 (0.001138) PDMOP 0.01396887 (0.000212644) 0.72832574 (0.00032) FDA4 DNSGA-Ⅱ 0.52746455 (0.00360) 0.9912373 (4.065E-05) DSS 0.590349722 (0.019668538) 0.991158595 (0.00059) PDMOP 0.487834225 (0.002480901) 0.9936884 (4.83E-05) FDA5 DNSGA-Ⅱ 0.815775725 (0.0609696) 0.9958528 (3.26E-05) DSS 0.785075639 (0.020305) 0.981521674 (0.00057) PDMOP 0.767482022 (0.0258126) 0.99085766 (1.58E-06)
下载: 导出CSV
-
[1] 柴天佑, 丁进良, 王宏, 苏春翌.复杂工业过程运行的混合智能优化控制方法.自动化学报, 2008, 34(5):505-515 http://www.aas.net.cn/CN/abstract/abstract13476.shtmlChai Tian-You, Ding Jin-Liang, Wang Hong, Su Chun-Yi. Hybrid intelligent optimal control method for operation of complex industrial processes. Acta Automatica Sinica, 2008, 34(5):505-515 http://www.aas.net.cn/CN/abstract/abstract13476.shtml [2] Audsley N C, Burns A, Richardson M F, Wellings A J. Real-time scheduling:the deadline-monotonic approach. In:Proceedings of the 1991 IEEE Workshop on Real-Time Operating Systems and Software. IEEE, 1991. 133-137 [3] 王大志, 刘士新, 郭希旺.求解总拖期时间最小化流水车间调度问题的多智能体进化算法.自动化学报, 2014, 40(3):548-555 http://www.aas.net.cn/CN/abstract/abstract18320.shtmlWang Da-Zhi, Liu Shi-Xin, Guo Xi-Wang. A multi-agent evolutionary algorithm for solving total tardiness permutation flow-shop scheduling problem. Acta Automatica Sinica, 2014, 40(3):548-555 http://www.aas.net.cn/CN/abstract/abstract18320.shtml [4] 田云娜, 李冬妮, 刘兆赫, 郑丹.一种基于动态决策块的超启发式跨单元调度方法.自动化学报, 2016, 42(4):524-534 http://www.aas.net.cn/CN/abstract/abstract18840.shtmlTian Yun-Na, Li Dong-Ni, Liu Zhao-He, Zheng Dan. A hyper-heuristic approach with dynamic decision blocks for inter-cell scheduling. Acta Automatica Sinica, 2016, 42(4):524-534 http://www.aas.net.cn/CN/abstract/abstract18840.shtml [5] 戴文战.一种动态多目标决策模型及其应用.控制与决策, 2000, 15(2):197-200 http://www.cnki.com.cn/Article/CJFDTOTAL-KZYC200002016.htmDai Wen-Zhan. A new kind of model of the dynamic multiple attribute decision making based on new effective function and its application. Control and Decision, 2000, 15(2):197-200 http://www.cnki.com.cn/Article/CJFDTOTAL-KZYC200002016.htm [6] Ding J L, Wang H C, Nie R, Chai T Y. Multiobjective optimization for planning of mineral processing under varied equipment capability. In:Proceedings of the 2013 International Conference on Advanced Mechatronic Systems. Luoyang, China:IEEE, 2013. 576-581 [7] Zhou A M, Jin Y C, Zhang Q F. A population prediction strategy for evolutionary dynamic multiobjective optimization. IEEE Transactions on Cybernetics, 2014, 44(1):40-53 doi: 10.1109/TCYB.2013.2245892 [8] 刘淳安.动态多目标优化进化算法及其应用.北京:科学出版社, 2011.Liu Chun-An. Dynamic Multi-Objective Optimization Evolutionary Algorithm and Its Application. Beijing:Science Press, 2011. [9] 陈志旺, 白锌, 杨七, 黄兴旺, 李国强.区间多目标优化中决策空间约束、支配及同序解筛选策略.自动化学报, 2015, 41(12):2115-2124 http://www.aas.net.cn/CN/abstract/abstract18784.shtmlChen Zhi-Wang, Bai Xin, Yang Qi, Huang Xing-Wang, Li Guo-Qiang. Strategy of constraint, dominance and screening solutions with same sequence in decision space for interval multi-objective optimization. Acta Automatica Sinica, 2015, 41(12):2115-2124 http://www.aas.net.cn/CN/abstract/abstract18784.shtml [10] Deb K, Pratap A, Agarwal S, Meyarivan T. A fast and elitist multiobjective genetic algorithm:NSGA-II. IEEE Transactions on Evolutionary Computation, 2002, 6(2):182-197 doi: 10.1109/4235.996017 [11] Zitzler E, Laumanns M, Thiele L. SPEA2:Improving the Strength Pareto Evolutionary Algorithm, TIK-Report 103, 2001. [12] Storn R, Price K. Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimization, 1997, 11(4):341-359 doi: 10.1023/A:1008202821328 [13] Deb K, Udaya Bhaskara Rao N, Karthik S. Dynamic multi-objective optimization and decision-making using modified NSGA-II:a case study on hydro-thermal power scheduling. In:Proceedings of the 4th International Conference on Evolutionary Multi-Criterion Optimization. Matsushima, Japan:Springer, 2007. 803-817 [14] Zhang Z H. Multiobjective optimization immune algorithm in dynamic environments and its application to greenhouse control. Applied Soft Computing, 2008, 8(2):959-971 doi: 10.1016/j.asoc.2007.07.005 [15] Hatzakis I, Wallace D. Dynamic multi-objective optimization with evolutionary algorithms:a forward-looking approach. In:Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation. Washington, USA:ACM, 2006. 1201-1208 [16] Ishibuchi H, Masuda H, Tanigaki Y, Nojima Y. Difficulties in specifying reference points to calculate the inverted generational distance for many-objective optimization problems. In:Proceedings of the 2014 IEEE Symposium on Computational Intelligence in Multi-Criteria Decision-Making. Orlando, USA:IEEE, 2014. 170-177 [17] Branke J. Memory enhanced evolutionary algorithms for changing optimization problems. In:Proceedings of the 1999 Congress on Evolutionary Computation. Washington, D.C., USA:IEEE, 1999. [18] Zhou A M, Jin Y C, Zhang Q F, Sendhoff B, Tsang E. Prediction-based population re-initialization for evolutionary dynamic multi-objective optimization. In:Proceedings of the 4th International Conference on Evolutionary Multi-Criterion Optimization. Matsushima, Japan:Springer, 2007. 832-846 [19] Helbig M, Engelbrecht A P. Archive management for dynamic multi-objective optimisation problems using vector evaluated particle swarm optimisation. In:Proceedings of the 2011 Congress on Evolutionary Computation. New Orleans, USA:IEEE, 2011. 2047-2054 [20] Farina M, Deb K, Amato P. Dynamic multiobjective optimization problems:test cases, approximation, and applications. In:Proceedings of the 2nd International Conference on Evolutionary Multi-Criterion Optimization. Faro, Portugal:Springer, 2003. 311-326 [21] 郭观七, 尹呈, 曾文静, 李武, 严太山.基于等价分量交叉相似性的Pareto支配性预测.自动化学报, 2014, 40(1):33-40 http://www.aas.net.cn/CN/abstract/abstract18264.shtmlGuo Guan-Qi, Yin Cheng, Zeng Wen-Jing, Li Wu, Yan Tai-Shan. Prediction of Pareto dominance by cross similarity of equivalent components. Acta Automatica Sinica, 2014, 40(1):33-40 http://www.aas.net.cn/CN/abstract/abstract18264.shtml [22] Das I, Dennis J E. Normal-boundary intersection:a new method for generating the Pareto surface in nonlinear multicriteria optimization problems. SIAM Journal on Optimization, 1998, 8(3):631-657 doi: 10.1137/S1052623496307510 [23] Deb K, Jain H. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, Part I:Solving problems with box constraints. IEEE Transactions on Evolutionary Computation, 2014, 18(4):577-601 doi: 10.1109/TEVC.2013.2281535 [24] Asafuddoula M, Ray T, Sarker R. A decomposition based evolutionary algorithm for many objective optimization with systematic sampling and adaptive epsilon control. In:Proceedings of the 7th International Conference on Evolutionary Multi-Criterion Optimization. Sheffield, UK:Springer, 2013. 413-427 [25] 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 Transactions on Evolutionary Computation, 2014, 18(4):602-622 doi: 10.1109/TEVC.2013.2281534 [26] Azzouz R, Bechikh S, Ben Said L. A multiple reference point-based evolutionary algorithm for dynamic multi-objective optimization with undetectable changes. In:Proceedings of the 2014 IEEE Congress on Evolutionary Computation. Beijing, China:IEEE, 2014. 3168-3175 [27] Cheng R, Jin Y C, Narukawa K, Sendhoff B. A multiobjective evolutionary algorithm using Gaussian process-based inverse modeling. IEEE Transactions on Evolutionary Computation, 2015, 19(6):838-856 doi: 10.1109/TEVC.2015.2395073 [28] Farina M, Deb K, Amato P. Dynamic multiobjective optimization problems:test cases, approximations, and applications. IEEE Transactions on Evolutionary Computation, 2004, 8(5):425-442 doi: 10.1109/TEVC.2004.831456 [29] Li X D, Branke J, Kirley M. On performance metrics and particle swarm methods for dynamic multiobjective optimization problems. In:Proceedings of the 2007 IEEE Congress on Evolutionary Computation. Singapore:IEEE, 2007. 576-583 [30] Zhang Q F, Zhou A M, Jin Y C. RM-MEDA:a regularity model-based multiobjective estimation of distribution algorithm. IEEE Transactions on Evolutionary Computation, 2008, 12(1):41-63 doi: 10.1109/TEVC.2007.894202 [31] Van Veldhuizen D A. Multiobjective Evolutionary Algorithms:Classifications, Analyses, and New Innovations[Ph.D. dissertation], Air Force Institute of Technology Wright Patterson AFB, OH, USA, 1999. -
图(14) / 表(4)
计量
- 文章访问数: 5164
- HTML全文浏览量: 1210
- PDF下载量: 2190
- 被引次数: 0
