一種兩狀態(tài)動(dòng)態(tài)優(yōu)化的自學(xué)習(xí)差異進(jìn)化算法

張榮華 劉長征 郭 理

一種兩狀態(tài)動(dòng)態(tài)優(yōu)化的自學(xué)習(xí)差異進(jìn)化算法

張榮華 劉長征*郭 理

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

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

智能計(jì)算 差異進(jìn)化 動(dòng)態(tài)優(yōu)化 自學(xué)習(xí)機(jī)制

0 引 言

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

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

1 動(dòng)態(tài)函數(shù)設(shè)計(jì)

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

minf(x,t)

(1)

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

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

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

(2)

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

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

(3)

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

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

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

算法1 SeDE

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

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

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

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

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

Step4 學(xué)習(xí)操作2：群體P向當(dāng)代最優(yōu)個(gè)體學(xué)習(xí)；

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

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

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

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

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

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

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

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

2.2 個(gè)體自學(xué)習(xí)機(jī)制

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

算法2 Self-learning algorithm

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

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

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

輸出：測試向量 v

Step1 確定當(dāng)前群體的最優(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中的所有個(gè)體x, v=x+w×(stageBestIndi(2)-x)

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

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中的所有個(gè)體x, v= w×(stageBestIndi(1)-x)

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

Step12 changeTime=changeTime+1;

Step13 else

% 環(huán)境沒有發(fā)生動(dòng)態(tài)變化, 向當(dāng)代最優(yōu)個(gè)體學(xué)習(xí);

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

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

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

(4)

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

圖2 個(gè)體自學(xué)習(xí)機(jī)制

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

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

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

2.3 個(gè)體交叉和更新

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

(5)

(6)

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

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

(7)

(8)

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

3 實(shí)驗(yàn)與分析

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié) 語

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

的同時(shí)加快算法收斂速度。最后以兩狀態(tài)動(dòng)態(tài)優(yōu)化的實(shí)驗(yàn)結(jié)果表明算法能盡快適應(yīng)環(huán)境的動(dòng)態(tài)變化，具有良好的全局和局部搜索能力。但本文只設(shè)計(jì)了解決兩狀態(tài)的動(dòng)態(tài)優(yōu)化問題，而現(xiàn)實(shí)生活中存在大量多狀態(tài)動(dòng)態(tài)優(yōu)化問題，此類問題的研究不僅具有極高的挑戰(zhàn)性，也具有重要的實(shí)用價(jià)值。今后將著重研究此類問題，驗(yàn)證本文算法對多狀態(tài)動(dòng)態(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] 陳昊,黎明,陳曦.動(dòng)態(tài)環(huán)境下基于預(yù)測機(jī)制的多種群進(jìn)化算法[J].小型微型計(jì)算機(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ìn)化算法[J].計(jì)算機(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。國家社科基金項(xiàng)目(14XXW004)；教育部社科基金項(xiàng)目(11XJJAZH001)；新疆生產(chǎn)建設(shè)兵團(tuán)社科基金項(xiàng)目(13QN11)。張榮華，講師，主研領(lǐng)域：人工智能。劉長征，高工。郭理，副教授。

TP18 TP31

A

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