2.624

2020影响因子

(CJCR)

  • 中文核心
  • EI
  • 中国科技核心
  • Scopus
  • CSCD
  • 英国科学文摘

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

基于参考点预测的动态多目标优化算法

丁进良 杨翠娥 陈立鹏 柴天佑

丁进良, 杨翠娥, 陈立鹏, 柴天佑. 基于参考点预测的动态多目标优化算法. 自动化学报, 2017, 43(2): 313-320. doi: 10.16383/j.aas.2017.c150811
引用本文: 丁进良, 杨翠娥, 陈立鹏, 柴天佑. 基于参考点预测的动态多目标优化算法. 自动化学报, 2017, 43(2): 313-320. doi: 10.16383/j.aas.2017.c150811
DING Jin-Liang, YANG Cui-E, CHEN Li-Peng, CHAI Tian-You. Dynamic Multi-objective Optimization Algorithm Based on Reference Point Prediction. ACTA AUTOMATICA SINICA, 2017, 43(2): 313-320. doi: 10.16383/j.aas.2017.c150811
Citation: DING Jin-Liang, YANG Cui-E, CHEN Li-Peng, CHAI Tian-You. Dynamic Multi-objective Optimization Algorithm Based on Reference Point Prediction. ACTA AUTOMATICA SINICA, 2017, 43(2): 313-320. doi: 10.16383/j.aas.2017.c150811

基于参考点预测的动态多目标优化算法

doi: 10.16383/j.aas.2017.c150811
基金项目: 

辽宁省教育厅人才项目 LR2015021

国家自然科学基金 61590922

国家自然科学基金 61273031

辽宁省自然科学基金项目 2014020021

国家自然科学基金 61525302

详细信息
    作者简介:

    杨翠娥东北大学硕士研究生.主要研究方向为进化优化算法.E-mail:Yang_Cuie@126.com

    陈立鹏东北大学硕士研究生.主要研究方向为进化优化算法.E-mail:peterchenneu@gmail.com

    柴天佑中国工程院院士, 东北大学教授, IEEE Fellow, IFAC Fellow.主要研究方向为自适应控制, 智能解耦控制, 流程工业综合自动化理论、方法与技术.E-mail:tychai@mail.neu.edu.cn

    通讯作者:

    丁进良东北大学教授.主要研究方向为复杂工业过程建模, 运行优化控制与进化计算.本文通信作者.E-mail:jlding@mail.neu.edu.cn

Dynamic Multi-objective Optimization Algorithm Based on Reference Point Prediction

Funds: 

Talent Support Project of Liaoning LR2015021

Natural Science Fundation of China 61590922

Natural Science Fundation of China 61273031

National Natural Science Fundation of Liaoning Province 2014020021

Natural Science Fundation of China 61525302

More Information
    Author Bio:

    Master student at Northeastern University. Her main research interest is evolutionary optimization algorithm

    Master student at Northeastern University. His main research interest is evolutionary optimization algorithm

    Member of Chinese Engineering Academy, professor at Northeastern University. IEEE Fellow and IFAC Fellow. His research interest covers adaptive control, intelligent decoupling control, integrated automation theory, method and technology of industrial process

    Corresponding author: DING Jin-Liang Professor at Northeastern University. His research interest covers modeling, operational optimization control of the complex industrial process and evolutionary computation. Corresponding author of this paper
  • 摘要: 为了快速跟踪动态多目标优化问题变化的Pareto前沿,本文提出一种基于参考点预测策略的动态多目标优化算法(PDMOP).该算法对关联到相同参考点的个体建立时间序列,并对这些时间序列通过线性回归模型预测新环境下种群.同时,将历史时刻的预测误差反馈到当前预测中来提高预测的准确性,并在每个预测的个体上加入扰动来增加初始种群多样性,从而能够加快算法在新环境下的收敛速度.通过4个标准测试函数对该算法测试,并和两个现有算法对比分析,结果表明所提算法在处理动态多目标优化问题时能够保持良好的性能.
    1)  本文责任编委 魏庆来
  • 图  1  两目标优化问题的结构化参考点

    Fig.  1  Two-objective optimization problem structured reference point

    图  2  两目标优化问题个体和参考点关联

    Fig.  2  Two objective optimization problem of individual associated with reference point

    图  3  FDA1的IGD均值

    Fig.  3  Average IGD of FDA1

    图  4  FDA3的IGD均值

    Fig.  4  Average IGD of FDA3

    图  5  FDA4的IGD均值

    Fig.  5  Average IGD of FDA4

    图  6  FDA5的IGD均值

    Fig.  6  Average IGD of FDA5

    图  7  FDA1的HVR均值

    Fig.  7  Average HVR of FDA1

    图  8  FDA3的HVR均值

    Fig.  8  Average HVR of FDA3

    图  9  FDA4的HVR均值

    Fig.  9  Average HVR of FDA4

    图  10  FDA5的HVR均值

    Fig.  10  Average HVR of FDA5

    图  11  FDA1的预测种群

    Fig.  11  Prediction population of FDA1

    图  12  FDA3的预测种群

    Fig.  12  Prediction population of FDA3

    图  13  FDA4的预测种群

    Fig.  13  Prediction population of FDA4

    图  14  FDA5的预测种群

    Fig.  14  Prediction population of FDA5

    表  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 对Ωtgenptgen快速排序, 并根据参考点关联选择个体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.shtml

    Chai 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.shtml

    Wang 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.shtml

    Tian 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.htm

    Dai 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.shtml

    Chen 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.shtml

    Guo 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)
计量
  • 文章访问数:  3874
  • HTML全文浏览量:  861
  • PDF下载量:  2013
  • 被引次数: 0
出版历程
  • 收稿日期:  2015-12-07
  • 录用日期:  2016-05-23
  • 刊出日期:  2017-02-01

目录

    /

    返回文章
    返回