一種求解約束優(yōu)化問題的自適應差分進化算法

閤大海,李元香,龔文引,何國良

(1.武漢大學軟件工程國家重點實驗室,武漢大學計算機學院,湖北武漢430072;2.中國地質(zhì)大學(武漢)計算機學院,湖北武漢 430074)

?

一種求解約束優(yōu)化問題的自適應差分進化算法

閤大海1,李元香1,龔文引2,何國良1

(1.武漢大學軟件工程國家重點實驗室,武漢大學計算機學院,湖北武漢430072;2.中國地質(zhì)大學(武漢)計算機學院,湖北武漢 430074)

自適應算子選擇方式已被用于差分進化算法求解全局優(yōu)化問題及多目標優(yōu)化問題,然而在求解約束優(yōu)化時難于為自適應算子選擇方式找到一種方式來恰當分配信用.為此,本文提出了一種基于混合種群的自適應適應值方式來對約束優(yōu)化問題中變異策略進行信用分配并采用概率匹配方法自適應選擇差分變異策略,同時對算法變異縮放因子與交叉率進行自適應設置提高算法的成功率.實驗結果表明算法在求解約束優(yōu)化問題相比于CODEA/OED,ATMES,εBBO-dm,COMDE 以及εDE算法有較高的收斂精度及收斂速度,同時驗證了自適應方式的有效性.該算法可用于預報、質(zhì)量控制、會計過程等科學和工程應用領域.

約束優(yōu)化;差分進化算法;自適應;信用分配;概率匹配

1 引言

差分進化算法需要根據(jù)實際問題需要設置相關參數(shù)(種群規(guī)模NP,變異縮放因子F,交叉率CR)以及選擇合適變異策略,這通常需要進行反復試驗才能得到最佳設置.而且隨著算法搜尋的解空間區(qū)域不同,不同區(qū)域所需要的參數(shù)及變異策略也不相同[1].因此自適應選擇變異策略及設置參數(shù)是一種較好的方式.

自適應算子選擇(Adaptive Operator Selection,AOS)開始被用于遺傳算法[2,3],近來被引入差分進化算法解決全局優(yōu)化[4,5]以及多目標優(yōu)化[6]問題,就作者所知該類方法尚未用于解決約束優(yōu)化問題(Constrained Optimization Problems,COPs).文獻[5]提出了一種利用概率匹配(probability matching)方式自適應選擇算子的差分進化算法,受此啟發(fā)本文提出了一種用于解決約束優(yōu)化的自適應算子選擇方法.自適應算子選擇需要解決兩個問題:一是如何根據(jù)操作算子在近期搜尋過程中的表現(xiàn)給出相應信用分配(credit assignment),本文為此提出了一種基于混合種群的自適應適應值的方法來分配信用;二是如何根據(jù)分配的信用值來選擇操作算子,本文使用了概率匹配方式來選擇.此外,對于算法的交叉率CR和縮放因子F,本文采用了JADE算法[7]算法機制來對參數(shù)做自適應設置.新的自適應差分約束算法稱為PJAD-CDE算法,通過標準測試函數(shù)測試測試表明算法在求解約束優(yōu)化問題時有較好的收斂精度及收斂速度并驗證了自適應方法的有效性.

2 約束優(yōu)化問題定義

不失一般性,約束優(yōu)化問題可按照以下規(guī)則定義:

(1)

一般將等式約束轉換為不等式約束處理

|hj(x)|-δ≤0,j∈{q+1,…,m}

(2)

δ為一個正的容忍值.一個解x到第j個約束的距離定義為

(3)

解x到可行區(qū)域邊界的距離定義為G(x),反映了x違反約束值的大小

(4)

3 標準差分進化算法

標準差分進化算法利用個體混合變異雜交產(chǎn)生后代個體,當后代個體優(yōu)于父代個體時替換父代個體.差分進化算法中的主要參數(shù)包括種群規(guī)模NP,變異縮放因子F,以及交叉率CR.

變異算子是差分算法的主要算子.對于種群個體xi,經(jīng)過變異算子變異后產(chǎn)生的相應變異個體記為vi,常用的差分變異算子包括:

(1)”DE/rand/1”:

vi=xr1+F(xr2-xr3)

(5)

(2)”DE/rand/2”:

vi=xr1+F(xr2-xr3)+F(xr4-xr5)

(6)

(3)”DE/rand-to-best/2”:

vi=xr1+F(xbest-xr1)+F(xr2-xr3)+F(xr4-xr5)

(7)

(4)”DE/current-to-rand/1”:

vi=xi+F(xr1-xi)+F(xr2-xr3)

(8)

其中xr1,xr2,xr3,xr4,xr5是從整個種群中隨機選取的互不相同個體,xbest為整個種群中適應值最好的個體.

4 PJAD-CDE算法的變異策略自適應選擇

本文和文獻[5]一樣選取式(5)～(8)的變異策略組成變異策略池來進行自適應選擇.自適應選擇實現(xiàn)包括:(1)信用分配機制,即如何衡量不同的變異策略在搜尋中的優(yōu)劣;(2)策略選擇機制,即采用何種方式選擇變異策略.下面介紹兩者的實現(xiàn).

4.1 信用分配機制

信用分配機制包括:(1)如何衡量由單個策略造成的適應值變化;(2)如何根據(jù)適應值變化分配恰當?shù)男庞弥?對于(1),約束優(yōu)化問題需要同時考慮個體的目標函數(shù)值和違約值,因此需要找到一個恰當?shù)臉藴蕘砗饬總€體的適應值變化.文獻[8]提出了一種在約束優(yōu)化中的個體排序標準,受此啟發(fā)本文提出了一種混合種群的自適應適應值(combined population based adaptive fitness)方法來衡量個體的適應值變化.將當前種群記為Pt,下代種群記為Pt+1,將Pt和Pt+1混合之后的種群記為Pc.種群Pc分為三種狀態(tài):不可行狀態(tài),半可行狀態(tài),可行狀態(tài).計算個體xi的適應值Fit(xi)方法如下:

(1)不可行狀態(tài).該狀態(tài)下種群中只有不可行個體,因此找到可行個體是最重要的,所以個體適應值按照違約值G(xi)計算.

Fit(xi)=G(xi)

(9)

(2)半可行狀態(tài).在半可行狀態(tài)下,種群中同時包含可行個體和非可行個體,按照文獻[9]中的自適應適應值轉換(Adaptive Fitness Transformation,AFT)方法來計算個體適應值.

將種群Pc分為可行解集合(Z1)和非可行解集合(Z2),個體xi的目標函數(shù)值f(xi)按以下公式轉換

f′(xi)=

(10)

φ為種群Pc可行解所占比率,xbest與xworst為Z1的最好與最差個體.f′(x)標準化為

(11)

用式(4)來計算個體的違約值并將其標準化

(12)

個體適應值按以下公式計算

Fit(xi)=fnor(xi)+Gnor(xi)

(13)

(3) 可行狀態(tài).該狀態(tài)下種群中只有可行解,適應值由目標函數(shù)值f(xi)決定.

Fit(xi)=f(xi)

(14)

種群Pt中的個體xi適應值記為Fit(xi),對應試驗個體xi+1適應值記為Fit(xi+1),適應值變化FIi= Fit(xi)-Fit(xi+1).由于在進化早期低劣個體較多適應值提高較大,在進化晚期則反之,因此直接使用適應值的差來計算適應值提高FIi會使進化早期效果較好的策略在進化中占據(jù)優(yōu)勢,所以對F(xi)進行標準化.

(15)

個體適應值提高FIi按以下方式計算

FIi=Fitnormal(xi)-Fitnormal(xi+1)

(16)

將Sa記為策略a(a=1,…,k)在第t代的適應值提高集合.則策略a在第t代的信用分配ra(t)按集合Sa的平均值計算:

(17)

4.2 策略選擇機制

在策略選擇機制上,本文采用概率匹配方法來選擇策略.ra(t)為策略a在第t代所獲取的信用,qa(t)為策略的已知質(zhì)量,則該策略在下代質(zhì)量qa(t+1)的更新公式為:

qa(t+1)=qa(t)+α[ra(t)-qa(t)]

(18)

α∈(0,1]為適應率.策略選擇概率按以下公式更新

(19)

pmin∈(0,1)為最小選擇概率.

5 PJAD-CDE算法中的參數(shù)自適應設置

(20)

(21)

meanL(·)為Lehmer平均值.

(22)

6 PJAD-CDE算法流程

PJAD-CDE算法具體流程如下,”DE/rand-to-best/2”策略中的best個體按如下方式選擇:(1)可行個體優(yōu)于不可行個體;(2)不可行個體中違反約束值G(x)小的個體占優(yōu);(3)可行個體中目標函數(shù)值f(x)小的個體占優(yōu).在處理等式約束時,按文獻[9]中類似機制將等式約束轉換為不等式約束處理,t為進化代數(shù)

算法1 PJAD-CDE算法

輸入:搜索空間R,目標函數(shù)f,違約函數(shù)G;

輸出:最優(yōu)解;

(1) 初始化種群,評估個體的目標函數(shù)值與違約值

(2) 對每個策略a,設置qa(t)=0,pa(t) = 1/k

(3) while不滿足停止條件

綜上所述，匹多莫德口服液聯(lián)合葛根素治療兒童過敏性紫癜有效改善患兒血清OPN、PTX3表達水平，提升患兒的免疫功能，降低復發(fā)率，安全性較好，療效顯著，值得在臨床工作中進行推廣。

(4) fori=1 to NP do

(5) 按輪盤賭方式選擇策略SIi

(6) 隨機選擇個體r1≠r2≠r3≠r4≠r5≠i,生成jrand= rndint(1,D)

(8) forj=1 toDdo

(10) 使用策略SIi生成個體uij

(11)endif

(12)endfor

(13)endfor

(14)fori=1toNPdo

(15) 評估后代ui

(16)ifF(ui)≤F(xi)then

(17) 用式(16)計算FIi并用個體ui替代個體xi

(18)else

(19)FIi=0

(20)endif

(21) SSIi=FIi

(22)endfor

(23) 根據(jù)式(17)計算每個策略的報酬ra(t)

(24) 根據(jù)式(18)更新每個策略的質(zhì)量qa(t)

(25) 根據(jù)式(19)更新每個策略的選擇概率pa(t)

(27) t=t+1

(28)endwhile

(29) 輸出當前最優(yōu)解

7 實驗結果及分析

為了驗證PJAD-CDE算法的有效性,本文選取了13個約束優(yōu)化測試函數(shù)來測試,測試函數(shù)詳見文獻[10].將PJAD-CDE算法與ATMES[9],CODEA/OED[11],εDE[12],COMDE[13],εBBO-dm[14]5種約束算法進行比較.PJAD-CDE算法參數(shù)設置如下:k=4,pmin=0.05,α=0.3,c=0.1.7.1 PJAD-CDE與其它算法的性能比較

將PJAD-CDE算法與CODEA/OED,ATMES,εBBO-dm,COMDE,εDE5種算法進行比較,PJAD-CDE,CODEA/OED,εBBO-dm,ATMES均獨立運行30次,最大函數(shù)評價次數(shù)為240000次.εDE運行50次,最大函數(shù)評價次數(shù)為2000000次.COMDE運行30次,最大函數(shù)評價次數(shù)為200000次.

由表1看到就收斂精度而言,PJAD-CDE在除函數(shù)g02外的其余12個測試函數(shù)中的運行得到的最優(yōu)值,最差值以及平均值均小于或等于其它5種算法的運行結果.函數(shù)g02為高維多峰函數(shù),主要考察算法的尋優(yōu)能力.在該函數(shù)的運行結果上，PJAD-CDE運行結果略差于εDE，好于其它幾種算法,但考慮到εDE的函數(shù)評價次數(shù)遠大于PJAD-CDE,可以認為PJAD-CDE與εDE在g02上的表現(xiàn)至少是相當?shù)?，表明PJAD-CDE的搜索能力強于或者不弱于其它幾種算法.在含有等式約束的函數(shù)g03,g05,g11,g13的運行結果中,函數(shù)g03和g05只有PJAD-CDE找到了最優(yōu)解.對于函數(shù)g11和g13PJAD-CDE與εBBO-dm,COMDE均在每次運行中找到了最優(yōu)解.顯然PJAD-CDE相對于其它5種算法有更好的解決含有等式約束的問題的能力.對于函數(shù)g01,g04,g06-g10以及g12,PJAD-CDE與εBBO-dm每次均能找到最優(yōu)解,優(yōu)于其它3種算法.在魯棒性上,PJAD-CDE在函數(shù)g01,g03,g05-g08,g11-g13中的方差均小于等于其它5種算法，顯然PJAD-CDE在魯棒性上占優(yōu).通過以上對比可以看出在尋優(yōu)精度及穩(wěn)定性上PJAD-CDE優(yōu)于其它算法.

表1 算法運行結果比較

續(xù)表

為了對比算法的收斂速度,表2給出了PJAD-CDE算法與CODEA/OED,ATMES,εBBO-dm以及COMDE在函數(shù)評價次數(shù)為240000次到達最優(yōu)解的成功率以及在最大函數(shù)評價次數(shù)為500000次時到達最優(yōu)解所用的平均函數(shù)評價次數(shù)的比較,NA表示達到最大評價次數(shù)仍未找到最優(yōu)解,SR表示成功率,NFEs表示評估次數(shù).對于εDE,其函數(shù)評價次數(shù)為2000000次遠高于其它算法而尋優(yōu)精度劣于PJAD-CDE,顯然PJAD-CDE時間復雜度小于εDE.由表3可以看到在成功率上PJAD-CDE算法優(yōu)于其它4種算法.在函數(shù)評價次數(shù)上,PJAD-CDE在函數(shù)g01,g02,g07,g09,g10,g12上優(yōu)于其它算法.為了進一步衡量算法在評價次數(shù)上的優(yōu)劣,對5種算法給出Friedman排名.由表3可得PJAD-CDE和εBBO-dm表現(xiàn)最好.但在平均評價次數(shù)上,PJAD-CDE明顯優(yōu)于εBBO-dm.總體來看,PJAD-CDE在收斂速度上優(yōu)于其它算法.

表2 算法在成功率,平均評價次數(shù)的對比

表3 算法在函數(shù)評價次數(shù)上的Friedman排名

由以上分析可知PJAD-CDE算法相對于CODEA/OED,ATMES,εBBO-dm,εDE以及COMDE5種算法在求解約束問題的收斂精度以及收斂速度上均有明顯優(yōu)勢.

7.2 自適應選擇策略的有效性驗證

為了驗證基于自適應選擇策略的有效性,將PJAD-CDE算法的策略自適應部分改為運行策略“DE/rand/1”,“DE/rand/2”,“DE/rand-to-best/2”,“DE/current-to-rand/1”,算法分別定義為PJAD-CDE1,PJAD-CDE2,PJAD-CDE3,PJAD-CDE4.運行30次,函數(shù)最大評估次數(shù)為500000次.運行結果如表4,NFEs表示評價次數(shù),SR表示成功率.

表4 PJAD-CDE與PJAD-CDE1,PJAD-CDE2,PJAD-CDE3,PJAD-CDE4在平均評價次數(shù)及成功率的對比

續(xù)表

由表4可以看到在成功率上,PJAD-CDE與PJAD-CDE1相同,優(yōu)于PJAD-CDE2,PJAD-CDE3,PJAD-CDE4.在評價次數(shù)上PJAD-CDE在函數(shù)g01-g12以及平均評價次數(shù)上均優(yōu)于 PJAD-CDE1.PJAD-CDE3在函數(shù)g01,g02,g04-g10,g12的評價次數(shù)上均優(yōu)于其它四種算法,表明使用"DE/rand-to-best/2"策略在收斂速度上有較大優(yōu)勢,但同時易于陷入局部最優(yōu)導致算法成功率下降.總體來看PJAD-CDE算法相比于使用單個策略的PJAD-CDE1,PJAD-CDE2,PJAD-CDE3,PJAD-CDE4算法在保持成功率同時有較好的收斂速度,顯示了自適應選擇策略的有效性.

7.3 參數(shù)自適應設置的有效性驗證

PJAD-CDE算法使用了JADE算法機制對參數(shù)CR,F自適應設置.為了驗證參數(shù)自適應設置的有效性,將參數(shù)CR,F取文獻[5]中的值CR=0.9,F=0.5,算法命名為PJAD-CDE5,算法運行30次,函數(shù)最大評估次數(shù)為500000次運行，由運行結果發(fā)現(xiàn)PJAD-CDE與PJAD-CDE5在各函數(shù)的算法評價次數(shù)上相差不大,即表示參數(shù)自適應設置對算法收斂速度影響不明顯.在此僅給出兩者在成功率上的對比如表5,SR表示成功率.

表5 PJAD-CDE與PJAD-CDE5在成功率上的對比

由表5可以看到在PJAD-CDE算法在函數(shù)g02,g11,g13以及平均值上的成功率明顯優(yōu)于PJAD-CDE5.表明參數(shù)CR,F的自適應設置相比于固定取值方式來說在成功率上作用明顯.

8 結束語

本文提出了一種自適應約束差分進化算法,算法提出了一種基于混合種群的自適應適應值的方法來分配信用值并采用概率匹配方式自適應選擇差分變異算子,對于參數(shù)CR與F采用JADE算法機制進行自適應設置.與其他算法的對比結果驗證了算法的有效性,同時也驗證了自適應機制的有效性.

[1]A K Qin,V L Huang,P N Suganthan.Differential evolution algorithm with strategy adaptation for global numerical optimization[J].IEEE Transactions on Evolutionary Computation,2009,13(2):398-417.

[2]D Thierens.An adaptive pursuit strategy for allocating operator probabilities[A].Genetic and Evolutionary Computation Conference(GECCO'2005)[C].Washington DC,USA:ACM Press,2005.1539-1546.

[3]A Fialho,M Schoenauer,M Sebag,Analysis of adaptive operator selection techniques on the royal road and long k-path problems[A].Genetic and Evolutionary Computation Conference(GECCO'2009)[C].Montreal,Canada:ACM Press,2009.779-786.

[4]Wenyin Gong,Alvaro Fialho,Zhihua Cai,Hui Li.Adaptive strategy selection in differential evolution for numerical optimization:An empirical study[J].Information Sciences,2011,181(24):5346-5386.

[5]Wenyin Gong,A.Fialho,Zhihua Cai,Adaptive strategy selection in differential evolution[A].Genetic and Evolutionary Computation Conference(GECCO'2010)[C].Portland,USA:ACM Press,2010.409-416.

[6]Ke Li,A′ lvaro Fialho,Sam Kwong,Qingfu Zhang.Adaptive operator selection with bandits for a multiobjective evolutionary algorithm based on decomposition[J].IEEE Transactions on Evolutionary Computation,2014,18(1):114-130.

[7]Jingqiao Zhang,Arthur C.Sanderso.JADE:Adaptive differential evolution with optional external archive[J].IEEE Transactions on Evolutionary Computation,2009,13(5):945-958.

[8]Wenyin Gong,Zhihua Cai,Dingwen Liang.Adaptive ranking mutation operator based differential evolution for constrained optimization[J].IEEE Transactions on Cybernetics,2015,45(4):716-727.

[9]Yong Wang,Zixing Cai,Yuren Zhou,An adaptive tradeoff model for constrained evolutionary optimization[J].IEEE Transactions on Evolutionary Computation,2008,12(1):80-92.

[10]Runarsson TP,Yao X.Stochastic ranking for constrained evolutionary optimization[J].IEEE Transactions on Evolutionary Computation,2000,4(3):284-294.

[11]蔡自興,江中央,王勇,等.一種新的基于正交實驗設計的約束優(yōu)化進化算法[J].計算機學報,2010,33(5):855-864.

Cai Zixing,Jiang Zhongyang,Wang Yong,et al.A novel constrained optimization evolutionary algorithm based on orthogonal experimental design[J].Chinese Journal of Computers,2010,33(5):855-864.(in Chinese)

[12]鄭建國,王翔,劉榮輝,等.求解約束優(yōu)化問題的εDE算法[J].軟件學報,2012,23(9):2374-2387.

Zheng Jianguo,Wang Xiang,Liu Ronghui,et al.ε-differential evolution algorithm for constrained optimization problems[J].Journal of Software,2012,23(9):2374-2387.(in Chinese)

[13]A W Mohamed,H Z Sabry.Constrained optimization based on modified differential evolution algorithm[J].Information Sciences,2012,194(1):171-208.

[14]畢曉君,王鈺,李博,等.基于動態(tài)遷移的ε約束生物地理學優(yōu)化算法[J].計算機研究與發(fā)展,2014,51(3):580-589.

Bi Xiaojun,Wang Jue,Li Bo,et al.An εconstrained biogeography-based optimization with dynamic migration[J].Journal of Computer Research and Development,2014,51(3):580-589.(in Chinese)

閤大海 男,1981年生于湖北隨州.現(xiàn)為武漢大學計算機學院博士生.主要研究方向為演化計算,約束優(yōu)化.

E-mail:xdh628@163.com

李元香 男，1962年出生于湖北監(jiān)利，武漢大學計算機學院軟件工程國家重點實驗室教授，博士生導師，主要研究方向為演化計算的理論與應用研究.

E-mail:yxli@whu.edu.cn

龔文引 男,1979年出生于湖南永順,博士,中國地質(zhì)大學(武漢)計算機學院副教授,主要研究方向為演化計算及應用.

E-mail:wygong@cug.edu.cn

An Adaptive Differential Evolution Algorithm for Constrained Optimization Problems

XIA Da-hai1,LI Yuan-xiang1,GONG Wen-yin2,HE Guo-liang1

(1.CollegeofComputerScience,WuhanUniversity.Wuhan,Hubei430072,China;2.SchoolofComputerScience,ChinaUniversityofGeosciences.Wuhan,Hubei430074,China)

The adaptive operator selection method is used to solve the global optimization problem and multi-objective optimization problem of differential evolution algorithm.However,it is difficult to find a way to properly allocate credit for the adaptive operator selection in solving the constrained optimization problem.In order to realize the adaptive strategy selection in differential evolution,we present a combined population based adaptive fitness method to achieve the credit assignment of mutate strategies for constrained optimization problems and use probability matching method to select the mutate strategy adaptively.And we also set the mutation scaling factor and the crossover rate adaptively to improve the success rate of the algorithm.Experimental results show that the algorithm has higher accuracy and convergence speed comparing to CODEA/OED,ATMES,εBBO-dm,COMDE and εDE.We also test and verify the effectiveness of the adaptive method.The algorithm can be used in forecasting,quality control,accounting process,and other scientific and engineering applications.

constrained optimization; differential evolution algorithm;adaptation; credit assignment; probability matching

2015-11-20;

2016-01-07；責任編輯:覃懷銀

國家重大儀器專項(No.2011YQ170065.4);國家自然科學基金(No.61573324)

TP18

A

0372-2112 (2016)10-2535-08

??學報URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.10.036