基于參考點(diǎn)預測的動(dòng)態(tài)多目標優(yōu)化算法
doi: 10.16383/j.aas.2017.c150811
-
1.
東北大學(xué)流程工業(yè)綜合自動(dòng)化國家重點(diǎn)實(shí)驗室 沈陽(yáng) 110004
-
2.
東北大學(xué)自動(dòng)化研究中心 沈陽(yáng) 110004
基金項目:
遼寧省教育廳人才項目 LR2015021
國家自然科學(xué)基金 61590922
國家自然科學(xué)基金 61273031
遼寧省自然科學(xué)基金項目 2014020021
國家自然科學(xué)基金 61525302
Dynamic Multi-objective Optimization Algorithm Based on Reference Point Prediction
-
1.
State Key Laboratory of Integrated Automation of Process Industry, Northeastern University, Shenyang 110004
-
2.
Research Center of Automation, Northeastern University, Shenyang 110004
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
-
摘要: 為了快速跟蹤動(dòng)態(tài)多目標優(yōu)化問(wèn)題變化的Pareto前沿，本文提出一種基于參考點(diǎn)預測策略的動(dòng)態(tài)多目標優(yōu)化算法（PDMOP）.該算法對關(guān)聯(lián)到相同參考點(diǎn)的個(gè)體建立時(shí)間序列，并對這些時(shí)間序列通過(guò)線(xiàn)性回歸模型預測新環(huán)境下種群.同時(shí)，將歷史時(shí)刻的預測誤差反饋到當前預測中來(lái)提高預測的準確性，并在每個(gè)預測的個(gè)體上加入擾動(dòng)來(lái)增加初始種群多樣性，從而能夠加快算法在新環(huán)境下的收斂速度.通過(guò)4個(gè)標準測試函數對該算法測試，并和兩個(gè)現有算法對比分析，結果表明所提算法在處理動(dòng)態(tài)多目標優(yōu)化問(wèn)題時(shí)能夠保持良好的性能.
-
關(guān)鍵詞:
- 動(dòng)態(tài)優(yōu)化 /
- 多目標優(yōu)化 /
- 時(shí)間序列 /
- 預測 /
- 參考點(diǎn)
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) 本文責任編委?魏慶來(lái) -
圖 1 兩目標優(yōu)化問(wèn)題的結構化參考點(diǎn)
Fig. 1 Two-objective optimization problem structured reference point
圖 2 兩目標優(yōu)化問(wèn)題個(gè)體和參考點(diǎn)關(guān)聯(lián)
Fig. 2 Two objective optimization problem of individual associated with reference point
表 1 個(gè)體關(guān)聯(lián)算法
Table 1 Individual correlation algorithm
算法1 個(gè)體關(guān)聯(lián)算法 步驟1 for $i=1:H$ do ///H參考點(diǎn)的個(gè)數 步驟2 ??鏈接參考點(diǎn)和原點(diǎn)作為該參考點(diǎn)參考線(xiàn) 步驟3 end 步驟4 for $i=1:N$ do? ///N種群的個(gè)體數 步驟5 ??for $j=1:H$ do 步驟6 ????計算每個(gè)個(gè)體和參考線(xiàn)的距離 步驟7 ??end 步驟8 ??與個(gè)體垂直距離最小的參考點(diǎn)記錄為關(guān)聯(lián)參考點(diǎn) 步驟9 end? 
下載: 導出CSV
表 2 PDMOP算法偽代碼
Table 2 Pseudo code of PDMOP
算法2 PDMOP算法偽代碼 步驟1 參數及種群初始化:設置初始化參數, 時(shí)間常數τt, 種群大小pop, 進(jìn)化代數max_gen, 并在決策空間內隨機產(chǎn)生規模為pop初始種群p0t.令t=0, T=0, gen=0 步驟2 環(huán)境探測：根據式(7) 計算η (t), 如果η (t) < η則轉步驟3, 否則轉步驟4. 步驟3 環(huán)境未發(fā)生變化, 進(jìn)化操作更新父代個(gè)體. 步驟3.1 進(jìn)化操作:以一定的交叉概率pc, 變異概率pm, 對當前父代個(gè)體ptgen進(jìn)行進(jìn)化操作, 產(chǎn)生新的種群?gent. 步驟3.2 對?tgen∪ptgen快速排序, 并根據參考點(diǎn)關(guān)聯(lián)選擇個(gè)體pt+1gen作為下一代個(gè)體, 轉步驟5. 步驟4 環(huán)境發(fā)生變化, 產(chǎn)生預測種群響應變化 步驟4.1 產(chǎn)生預測種群, 基于式(4) 所示預測模型, 產(chǎn)生與種群大小為pop的預測種群, 并將其作為下一時(shí)刻算法的初始種群. 步驟4.2 存儲歷史信息, 轉步驟5. 步驟5 判斷是否滿(mǎn)足算法停止條件, 若滿(mǎn)足則停止; 否則, 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 算法性能評價(jià)比較
Table 4 The comparison of algorithm performance
測試函數 性能評價(jià)指標算法 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
亚洲第一网址_国产国产人精品视频69_久久久久精品视频_国产精品第九页<button id="qm3rj"><thead id="qm3rj"></thead></button> <samp id="qm3rj"></samp> <source id="qm3rj"><menu id="qm3rj"><pre id="qm3rj"></pre></menu></source> <video id="qm3rj"><code id="qm3rj"></code></video> <tt id="qm3rj"><track id="qm3rj"></track></tt> -
[1] 柴天佑, 丁進(jìn)良, 王宏, 蘇春翌.復雜工業(yè)過(guò)程運行的混合智能優(yōu)化控制方法.自動(dòng)化學(xué)報, 2008, 34(5):505-515 http://www.ynkaiyun.com/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.ynkaiyun.com/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] 王大志, 劉士新, 郭希旺.求解總拖期時(shí)間最小化流水車(chē)間調度問(wèn)題的多智能體進(jìn)化算法.自動(dòng)化學(xué)報, 2014, 40(3):548-555 http://www.ynkaiyun.com/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.ynkaiyun.com/CN/abstract/abstract18320.shtml [4] 田云娜, 李冬妮, 劉兆赫, 鄭丹.一種基于動(dòng)態(tài)決策塊的超啟發(fā)式跨單元調度方法.自動(dòng)化學(xué)報, 2016, 42(4):524-534 http://www.ynkaiyun.com/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.ynkaiyun.com/CN/abstract/abstract18840.shtml [5] 戴文戰.一種動(dòng)態(tài)多目標決策模型及其應用.控制與決策, 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] 劉淳安.動(dòng)態(tài)多目標優(yōu)化進(jìn)化算法及其應用.北京:科學(xué)出版社, 2011.Liu Chun-An. Dynamic Multi-Objective Optimization Evolutionary Algorithm and Its Application. Beijing:Science Press, 2011. [9] 陳志旺, 白鋅, 楊七, 黃興旺, 李國強.區間多目標優(yōu)化中決策空間約束、支配及同序解篩選策略.自動(dòng)化學(xué)報, 2015, 41(12):2115-2124 http://www.ynkaiyun.com/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.ynkaiyun.com/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] 郭觀(guān)七, 尹呈, 曾文靜, 李武, 嚴太山.基于等價(jià)分量交叉相似性的Pareto支配性預測.自動(dòng)化學(xué)報, 2014, 40(1):33-40 http://www.ynkaiyun.com/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.ynkaiyun.com/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)
計量
- 文章訪(fǎng)問(wèn)數: 5145
- HTML全文瀏覽量: 1199
- PDF下載量: 2188
- 被引次數: 0
