張榮華 劉長征 郭 理

一種兩狀態(tài)動態(tài)優(yōu)化的自學習差異進化算法

張榮華 劉長征*郭 理

(新疆石河子大學信息科學與技術(shù)學院 新疆 石河子 832003)

提出一種具有自學習機制的差異進化算法SeDE(Self-Learning Differential Evolution)，提高在動態(tài)優(yōu)化求解過程中群體適應(yīng)環(huán)境動態(tài)變化的能力。采用重新評估特定個體的方式監(jiān)測環(huán)境變化。通過群體向新狀態(tài)歷史最優(yōu)解引導學習，將當代最優(yōu)個體和兩隨機個體共同引導個體，保持群體多樣性的同時加快算法收斂速度，降低環(huán)境的頻繁變化對算法搜索能力的影響。通過6個動態(tài)函數(shù)測試了變化周期、函數(shù)維數(shù)對算法的影響，同時將新算法與兩個同類算法比較，實驗結(jié)果表明，自學習差異進化能更快地適應(yīng)環(huán)境動態(tài)變化，獲得更好的優(yōu)化結(jié)果。

智能計算 差異進化 動態(tài)優(yōu)化 自學習機制

0 引 言

在科學與工程中存在大量的動態(tài)優(yōu)化問題。這類問題的設(shè)計變量、目標函數(shù)、約束條件或者參數(shù)等都隨著時間的變化而變化，改變了函數(shù)的拓撲結(jié)構(gòu)，因此在優(yōu)化該類函數(shù)時，所獲得的最優(yōu)解具有時效性，極大地增加了優(yōu)化該類問題的復(fù)雜度。目前研究者設(shè)計的動態(tài)環(huán)境共分三類[1]：(1) 約束條件的變化產(chǎn)生的動態(tài)優(yōu)化環(huán)境，如動態(tài)背包問題；(2) 基于二進制編碼的異或運算生成的動態(tài)測試環(huán)境，個體編碼中二進制字符串發(fā)生異或運算，從而改變了優(yōu)化環(huán)境；(3) 改變函數(shù)的拓撲結(jié)構(gòu)，如函數(shù)的維度、峰的高度、寬度和位置等屬性均發(fā)生改變，從而得到動態(tài)優(yōu)化環(huán)境。在上述三類動態(tài)優(yōu)化問題中，前兩類問題都得到較好的解決，而第三類動態(tài)優(yōu)化問題中，由于多個因素同時發(fā)生變化，極大地增加了問題解決的難度，致使當前的優(yōu)化結(jié)果不甚理想。在處理動態(tài)優(yōu)化問題時，智能優(yōu)化算法表現(xiàn)出良好的競爭力[2]，但在動態(tài)環(huán)境中，環(huán)境的改變極大地降低了歷史信息的復(fù)用性。同時在環(huán)境變化后，群體需要迅速地適應(yīng)新的環(huán)境，是對群體學習能力的極大考驗。當群體陷入局部極值點時，所有的個體趨向一致喪失多樣性，失去進化能力。為了算法能及時跟蹤變化后的極值點，盡快適應(yīng)環(huán)境的變化，進化群體需要保持較好的多樣性， Cobb等[3]通過超級變異或可變局部搜索增加群體的多樣性，當探測到環(huán)境發(fā)生變化后，“瞬間”增大或者逐步增加個體的變異率。Yao[4]提出基于群體的增量學習模式，進化個體增加學習率以適應(yīng)環(huán)境的變化。Yang等[5]提出了具有導向性的個體遷入機制，能夠更高效地解決某幾類動態(tài)優(yōu)化問題。Rosa等[6]認為漢明距離較遠的個體交叉，其后代具有更好的多樣性，并用動態(tài)欺騙函數(shù)問題驗證了該結(jié)論。文獻[7,8]將預(yù)測和記憶機制引入到動態(tài)進化算法的研究中，對算法所得的某些信息進行記憶并構(gòu)建預(yù)測模型，當環(huán)境發(fā)生變化時能夠通過預(yù)測模型對動態(tài)環(huán)境進行預(yù)先判斷。董明剛等[9]提出一種改進的Oracle罰函數(shù)方法與三種自適應(yīng)差分進化算法相結(jié)合，提出三種自適應(yīng)約束差分進化算法，減少動態(tài)環(huán)境算法參數(shù)。文獻[11]采用一種帶有動態(tài)變量的DE和自適應(yīng)約束處理方法來自適應(yīng)動態(tài)環(huán)境變化。Thanh等[10]較為系統(tǒng)的論述了群體智能進化算法在動態(tài)優(yōu)化問題求解中的優(yōu)勢與不足，并比較了不同進化算法的求解機制和效果。

為此，受前兩類動態(tài)問題的啟發(fā)，減少引起環(huán)境動態(tài)變化的因素，降低解決問題的難度，設(shè)計可行的解決方案，進而推進第三類問題的解決。本文提出具有自學習機制的自適應(yīng)差異進化算法SeDE，處理兩階段動態(tài)優(yōu)化問題。該算法在保持良好群體多樣性的同時，加強了精英個體對進化群體的引導作用，利用歷史信息加快群體適應(yīng)環(huán)境的動態(tài)變化。

1 動態(tài)函數(shù)設(shè)計

動態(tài)優(yōu)化問題DOPs(Dynamic Optimzation Problems)的數(shù)學描述為：

minf(x,t)

(1)

其中f(x,t)是與時間相關(guān)的目標函數(shù)，hi(x,t)=0是第i個與時間t相關(guān)的等式約束條件，共m個等式約束條件。gj(x,t)<0是第j個與時間t相關(guān)的不等式約束條件，共有n個。

當時間因素t發(fā)生變化時，函數(shù)f(x,t)的維度、極值、極值的位置等因素均可能發(fā)生變化，本文處理極值位置變化引起的動態(tài)優(yōu)化問題。設(shè)靜態(tài)環(huán)境下的n維函數(shù)f(x)，第i個狀態(tài)點為οi(ci1,ci2,…,cin)，i=1,2,…,K。則動態(tài)函數(shù)為:

F(x,ο,t)=f(φ(x,ο),t)

(2)

其中F(x,ο,t)是與時間相關(guān)的動態(tài)函數(shù)；φ(x,ο)是變量x和狀態(tài)點o間的映射關(guān)系；t是驅(qū)動f(x)動態(tài)變化的時間變量，如算法中的迭代次數(shù)、運算平臺的物理時間等因素。

F(x,ο,t)=(x1-οi1)2+(x2-οi2)2

(3)

當t滿足條件τ時i=1，否則i=2，τ可以與進化代數(shù)相關(guān)的控制參數(shù)。當t變化時，函數(shù)的最小值在ο1和ο2間切換。

2 自適應(yīng)差異進化算法

SeDE算法主要由動態(tài)環(huán)境檢測機制、兩階段的個體學習機制和參數(shù)的自適應(yīng)調(diào)整三部分構(gòu)成。其主要框架如下所示。

算法1 SeDE

輸入：動態(tài)環(huán)境下被優(yōu)化函數(shù)f(x)及其定義域

輸出：算法獲得的函數(shù)f(x)的最優(yōu)適應(yīng)值

Step1 初始化群體P：在定義域內(nèi)初始化群體P、NP個體、D維，P={xij},i=1,2,…,NP;j=1,2,…,D,初始化參數(shù)F和CR；

Step2 動態(tài)環(huán)境檢測：檢測環(huán)境變化，若優(yōu)化環(huán)境改變則執(zhí)行Step3至Step8，否則執(zhí)行Step4至Step8；

Step3 學習操作1：判定當前優(yōu)化環(huán)境所在的狀態(tài)，用當前狀態(tài)的歷史最優(yōu)解引導群體P學習適應(yīng)環(huán)境；

Step4 學習操作2：群體P向當代最優(yōu)個體學習；

Step5 評估群體P，從父代和對應(yīng)的子代中選擇優(yōu)秀個體；

Step6 控制參數(shù)調(diào)整：采用自適應(yīng)機制更新變異步長F和交叉概率CR；

Step7 記錄最優(yōu)解x*與最優(yōu)解對應(yīng)的適應(yīng)值fit=f(x*)；

Step8 若滿足結(jié)束條件，則輸出相關(guān)統(tǒng)計數(shù)據(jù)；否則執(zhí)行Step2。

2.1 環(huán)境檢測機制

環(huán)境檢測機制包含兩個階段，首先檢測環(huán)境是否發(fā)生變化，其次確定當前環(huán)境所處的狀態(tài)。在DOPs中檢測環(huán)境變化的方法主要有兩種[12]，即重新評估環(huán)境監(jiān)測器和監(jiān)測算法行為，優(yōu)化問題的特點決定了環(huán)境檢測方式的選擇。本文處理的動態(tài)優(yōu)化問題有兩個不同的狀態(tài)，當環(huán)境從一個狀態(tài)轉(zhuǎn)變到另一個狀態(tài)后，個體適應(yīng)值發(fā)生明顯變化。圖1以二維Sphere函數(shù)為例。

圖1 環(huán)境變化瞬間個體適應(yīng)值變化

其次是確定環(huán)境所處的狀態(tài)。在算法中用變量changTime統(tǒng)計環(huán)境變化的次數(shù)，設(shè)定初始值changTime=1，若環(huán)境發(fā)生變化則changTime=changTime+1。用邏輯變量Status標志當前環(huán)境所處的狀態(tài)，Status=mod(changeTime,2)，其中mod表示取余函數(shù)。Status=1表明當前環(huán)境處于狀態(tài)1；否則處于狀態(tài)2。

2.2 個體自學習機制

為讓群體盡快適應(yīng)變化后的環(huán)境，算法采用精英引導下的個體學習機制。根據(jù)進化過程中所處的“時空”位置，群體的學習過程分為兩個階段。第一階段，環(huán)境變化后的“瞬間”即環(huán)境從狀態(tài)i轉(zhuǎn)變到狀態(tài)j時，群體向狀態(tài)j下的歷史最優(yōu)解學習，i≠j,i,j∈{1,2}。第二階段，向歷史最優(yōu)解學習結(jié)束后，群體向當代最優(yōu)個體學習。算法2詳細描述了群體在兩個階段的學習過程。

算法2 Self-learning algorithm

輸入：群體P及其適應(yīng)值fit；

狀態(tài)的歷史最優(yōu)解stageBestIndi 及適應(yīng)值stageBestFit changeTime=1;

% 環(huán)境變化次數(shù)記錄器

輸出：測試向量 v

Step1 確定當前群體的最優(yōu)解bestIndi和最優(yōu)值bestFit;

Step2 if bestFit≠Revaluate(bestIndi)

% 重新評估最優(yōu)解，確定優(yōu)化環(huán)境發(fā)生改變;

Step3 flag=mod(changeTime, 2);

Step4 if flag==2;

% 優(yōu)化環(huán)境從第一種狀態(tài)轉(zhuǎn)變到第二種狀態(tài);

Step5 if bestFit

% 更新第一種狀態(tài)的歷史最優(yōu)解與適應(yīng)值;

Step6 update(bestIndi, bestFit) ;

Step7 對群體P中的所有個體x, v=x+w×(stageBestIndi(2)-x)

% 向狀態(tài)2下的歷史最優(yōu)個體學習;

Step8 else

% 環(huán)境從第二種狀態(tài)轉(zhuǎn)變到第一種狀態(tài);

Step9 if bestFit

% 更新第二種狀態(tài)的歷史最優(yōu)解與適應(yīng)值;

Step10 update(bestIndi, bestFit)；

Step11 對群體P中的所有個體x, v= w×(stageBestIndi(1)-x)

% 向狀態(tài)1下的歷史最優(yōu)個體學習;

Step12 changeTime=changeTime+1;

Step13 else

% 環(huán)境沒有發(fā)生動態(tài)變化, 向當代最優(yōu)個體學習;

Step14 對群體P中所有個體x，vi=bestIndi+F×(bestIndi-randP1)+k×(randP2-randP3)。

向歷史最優(yōu)解學習 當優(yōu)化環(huán)境從狀態(tài)i轉(zhuǎn)變到狀態(tài)j后，個體適應(yīng)值和優(yōu)秀程度均發(fā)生變化，群體需要盡快學習、適應(yīng)新環(huán)境。因此，算法以狀態(tài)j下的歷史最優(yōu)解作為個體的學習對象。

設(shè)算法在狀態(tài)j下的歷史最優(yōu)解為stageBest(j)。當環(huán)境從i轉(zhuǎn)變?yōu)閖后，個體x在歷史最優(yōu)個體stageBest(j)引導下學習，學習策略如下。

(4)

圖2以二維空間中兩狀態(tài)的動態(tài)Sphere函數(shù)為例，說明了個體x的學習過程。狀態(tài)1下的個體被狀態(tài)2的歷史最優(yōu)解引導到v點，更接近狀態(tài)2下的Sphere函數(shù)的最優(yōu)解，比學習之前有更好的適應(yīng)值。

圖2 個體自學習機制

向當代最優(yōu)解學習 在應(yīng)用智能優(yōu)化問題處理問題時，評價次數(shù)、進化代數(shù)等均可看做驅(qū)動群體進化的資源。動態(tài)優(yōu)化問題中由于環(huán)境的動態(tài)變換，算法需要在給定資源下快速適應(yīng)新環(huán)境，進而獲得相對較好的解。因此，算法采用個體向當代最優(yōu)解學習的策略。

vi=bestIndi+F×(bestIndi-randP1)+k×(randP2-randP3)

其中，vi是對應(yīng)于第i個體的過渡測試向量，bestIndi是本代的最優(yōu)個體，randPj,j=1,2,3是從群體P中隨機選擇的，不同于bestIndi和當前個體的個體，F(xiàn)是控制變異步長的參數(shù)，k是(0,1]間的隨機均勻分布。

2.3 個體交叉和更新

交叉對象是vi和Pi，生成目標向量ui，ui=(ui1,ui2,…,uiD)。

(5)

(6)

2.4 參數(shù)的自適應(yīng)機制

群體P中個體均對應(yīng)變異步長F和交叉概率CR兩個控制參數(shù)，三者同時進化。第g+1代第i個體的參數(shù)F與CR的更新機制如下[12]：

(7)

(8)

其中，randj,j=1,2,3,4是[0,1]上的隨機數(shù),τ1和τ2是調(diào)整概率，都設(shè)定為0.1，F(xiàn)l=0.1,Fu=0.9。

3 實驗與分析

為了測試算法的性能，采用給出的6個測試函數(shù)作為測試樣例，如表1所示。實驗確定了算法在動態(tài)環(huán)境中不同參數(shù)下的優(yōu)化性能，然后與基本差異進化、自適應(yīng)差異進化比較。選擇6個靜態(tài)可擴展函數(shù)作為測試樣例，包括了單峰函數(shù)f1至f4和多峰函數(shù)f5、f6兩種類型。為了獲得兩個狀態(tài)的動態(tài)環(huán)境，在函數(shù)f(x)的定義域范圍內(nèi)隨機生成固定點O，令f*(x)=f(x-o)。實驗中令優(yōu)化環(huán)境在f(x)和f*(x)間循環(huán)轉(zhuǎn)換。

表1 測試函數(shù)用例

3.1 低維、動態(tài)環(huán)境下的算法性能實驗

為客觀測試SeDE在低維問題上的優(yōu)化性能，算法獨立運行25次，在問題定義域上重新初始化群體，規(guī)模為30。進化代數(shù)限定為2500代。優(yōu)化環(huán)境動態(tài)變化的頻率為每25代，優(yōu)化結(jié)果的精度設(shè)定為1E-8。實驗的數(shù)值結(jié)果如表2所示。

表2 SeDE算法對低維動態(tài)函數(shù)的優(yōu)化結(jié)果

針對每個測試問題，實驗記錄第k個狀態(tài)下，第i獨立次運行中第j個循環(huán)周期內(nèi)的最小值pbest(k,i,j)。為了獲得狀態(tài)k下的近似最優(yōu)值sbest(k)，獨立運行算法25次，進化1E+5代，統(tǒng)計每次運行獲得最優(yōu)值的均值。結(jié)合上述兩類實驗數(shù)據(jù)，計算相對離線誤差的最優(yōu)值的均值和方差，表2中Score條目列出了算法對全部測試函數(shù)在狀態(tài)k下的優(yōu)化結(jié)果均值。可以發(fā)現(xiàn)，維數(shù)為5時算法在不同環(huán)境下的得分相差不大；當維數(shù)增加到10時，得分相差一個數(shù)量級。這是因為當函數(shù)維數(shù)從5維增加到10維時，問題的狀態(tài)空間變大，復(fù)雜度增加，加大了算法對環(huán)境的跟蹤難度，致使優(yōu)化結(jié)果變差。

優(yōu)化環(huán)境從狀態(tài)i變化到狀態(tài)j時，進化群體因環(huán)境的變化而發(fā)生波動，破壞了個體在狀態(tài)i下的模式，這種“破壞”作用持續(xù)進行，直至環(huán)境狀態(tài)j轉(zhuǎn)變回狀態(tài)i。同樣，個體在環(huán)境i下的搜索學習過程也是對狀態(tài)j下模式的破壞。所以，環(huán)境的轉(zhuǎn)換過程也是當前環(huán)境下個體模式的“重建”和前一個環(huán)境下個體模式的“破壞”。上述過程的重復(fù)出現(xiàn)造成了適應(yīng)值的類周期波動，其中橫坐標為環(huán)境變化值，縱坐標為群體適應(yīng)度值，如圖3所示。

圖3 動態(tài)環(huán)境中群體適應(yīng)值的周期性波動

3.2 高維、動態(tài)環(huán)境下不同算法性能比較實驗

本次實驗比較了環(huán)境轉(zhuǎn)變頻率對不同算法的影響，并與標準DE算法和文獻[12]自適應(yīng)差分算法做比較。算法在每個頻率下獨立運行25次，并將每次運行最優(yōu)結(jié)果的均值作為統(tǒng)計指標。為了保證不同周期下環(huán)境有相同次數(shù)的周期變化，設(shè)定算法的迭代次數(shù)為GenLmt×100。三個算法的群體規(guī)模都設(shè)定為30，函數(shù)維數(shù)設(shè)定為30，并在問題空間內(nèi)隨機初始化。實驗結(jié)果如表3、表4所示。表3、表4中Score指標表示SeDE算法優(yōu)化結(jié)果占優(yōu)的函數(shù)個數(shù)。與另外兩種算法相比，在不同的環(huán)境變化周期下SeDE算法的Score數(shù)值為4或5，優(yōu)勢明顯。在genLmt=5，10時，環(huán)境的快速變化要求個體快速適應(yīng)新環(huán)境，以便盡可能接近或者找到該狀態(tài)下的最優(yōu)解，因此要求進化群體具有快速學習能力。在SeDE算法中，新環(huán)境的歷史最優(yōu)解在環(huán)境變化的“瞬間”引領(lǐng)個體學習，之后當代最優(yōu)解引導個體學習，這賦予SeDE算法良好的學習能力，比DE更快適應(yīng)環(huán)境變化，獲得較好的優(yōu)化結(jié)果。當genLmt=50，100時，環(huán)境轉(zhuǎn)變速度較慢，在搜索動態(tài)多模函數(shù)極值時要求進化群體能保持良好的多樣性，以防止陷入局部極值。SeDE算法以保持群體多樣性見長的DE算法為基礎(chǔ)，并且在個體的學習過程中引入群體中的隨機個體信息，所以SeDE算法具有良好的群體多樣性，獲得較好的優(yōu)化結(jié)果。

表3 不同變化周期下，幾種算法的性能比較

表4 不同變化周期下，幾種算法的性能比較

4 結(jié) 語

本文針對動態(tài)優(yōu)化問題，提出一種基于精英引導學習的新算法SeDE。新算法利用了DE算法群體多樣性好的特點，采用重新評估特定個體的方式監(jiān)測環(huán)境變化，同時采用個體的自學習機制，以適應(yīng)環(huán)境的動態(tài)變化。當環(huán)境發(fā)生變化的“瞬間”，新環(huán)境的歷史最優(yōu)個體引導群體學習，以便快速適應(yīng)環(huán)境的變化。進入新環(huán)境后個體向當代最優(yōu)個體學習，保持群體多樣性

的同時加快算法收斂速度。最后以兩狀態(tài)動態(tài)優(yōu)化的實驗結(jié)果表明算法能盡快適應(yīng)環(huán)境的動態(tài)變化，具有良好的全局和局部搜索能力。但本文只設(shè)計了解決兩狀態(tài)的動態(tài)優(yōu)化問題，而現(xiàn)實生活中存在大量多狀態(tài)動態(tài)優(yōu)化問題，此類問題的研究不僅具有極高的挑戰(zhàn)性，也具有重要的實用價值。今后將著重研究此類問題，驗證本文算法對多狀態(tài)動態(tài)優(yōu)化的適應(yīng)性及應(yīng)用效果。

[1] Gonza′lez J R,Pelta D A,Cruz C.Optimization in dynamic environments:a survey on problems,methods and measures[J].Soft Computing,2011,15(1):1427-1448.

[2] Yang S,Li C.A clustering particle swarm optimizer for locating and tracking multiple optima in dynamic environments[J].IEEE Transaction on Evolutionary Computation,2010,14(6):959-974.

[3] Cobb H G,Grefenstette J J.Genetic Algorithms for Tracking Changing Environments[C]//International Conference on Genetic Algorithms,Morgan Kaufmann,1993:523-530.

[4] Yao X,Yang S.Population-based incremental learning with associative memory for dynamic environments[J].IEEE Transactions on Evolutionary Computation,2008,12(5):542-561.

[5] Yang S.Genetic algorithms with memory and elitismbased immigrants in dynamic environments[J].Evolutionary Computation,2008,16(3):385-416.

[6] Rosa A C,Fernandes C M.Self adjusting the intensity of assortative mating in genetic algorithms[J].Soft Computing,2008,12(10):955-979.

[7] 陳昊,黎明,陳曦.動態(tài)環(huán)境下基于預(yù)測機制的多種群進化算法[J].小型微型計算機系統(tǒng),2012,33(4):795-799.

[8] Chen Hao,Li Ming,Chen Xi.Hybrid memory scheme for genetic algorithm in dynamic environments[J].Journal of Applied Science,2010,28( 5):540-545.

[9] 董明剛,程小輝,牛秦洲.基于Oracle罰函數(shù)的自適應(yīng)約束差分進化算法[J].計算機應(yīng)用與軟件,2014,31(1):290-292,322.

[10] Thanh N T,Yang S,Branke J.Evolutionary Dynamic Optimization:A Survey of the State of the Art[J].Swarm and Evolutionary Computation,2012,6(10):1-24.

[11] Silva E K,Barbosa H J C,Lemonge A C C.An adaptive constraint handling technique for differential evolution with dynamic use of variants in engineering optimization[J].Optimization and Engineering,2011,12(12):31-54.

[12] Brest J,Greiner S,Bo?kovic B,et al.Self-adapting control parameters in differential evolution:A comparative study on numerical benchmark problems[J].IEEE Transactions on Evolutionary Computation,2006,10(6):646-657.

A SELF-LEARNING DIFFERENTIAL EVOLUTION ALGORITHM WITH DUAL-STATE DYNAMIC OPTIMISATION

Zhang Ronghua Liu Changzheng*Guo Li

(SchoolofInformationScienceandTechnology,ShiheziUniversity,Shihezi832003,Xinjiang,China)

We proposed a differential evolution algorithm with self-learning mechanism for improving the capability of population in adapting to dynamic environmental changes in dynamically optimised solving process. By using the approach of re-evaluating specific individuals the algorithm monitors the environmental changes. Through population it guides the learning of the new state historical optimal solution, and guides the individuals by the contemporary optimal individual and the dual random individuals jointly; it keeps the diversity of the population while speeding up the convergence rate of the algorithm, and reduces the impact of frequent environmental changes on algorithm’s search ability. We tested the influences of change period and function’s dimension on the algorithm through 6 dynamic functions, and compared the new algorithm with two similar algorithms at the same time. Experimental result demonstrated that the self-learning differential algorithm could adapt to the dynamic environmental changes more rapidly and achieved better optimisation result.

Intelligent computation Differential evolution Dynamic optimisation Self-learning mechanism

2014-09-09。國家社科基金項目(14XXW004)；教育部社科基金項目(11XJJAZH001)；新疆生產(chǎn)建設(shè)兵團社科基金項目(13QN11)。張榮華，講師，主研領(lǐng)域：人工智能。劉長征，高工。郭理，副教授。

TP18 TP31

A

10.3969/j.issn.1000-386x.2016.04.057