陳　巖,王宗憲

(沈陽工業(yè)大學 理學院,遼寧 沈陽 110870)

基于多準則尋優(yōu)策略的差分進化算法

陳巖,王宗憲

(沈陽工業(yè)大學 理學院,遼寧 沈陽 110870)

摘要：在差分進化算法的基礎上,提出一種基于多準則尋優(yōu)策略的改進差分進化算法。該算法可以動態(tài)調(diào)整變異因子和交叉概率,基于文中提出的多準則尋優(yōu)策略,通過個體適應度、個體間距離等評價指標判斷個體的優(yōu)劣程度,并且可以降低種群的高密度程度,增強種群多樣性。這種判斷機制可以有效避免種群過早收斂,易陷入局部最優(yōu)的風險。通過具體的測試函數(shù)對算法進行測試,并與標準差分進化算法進行比較,結(jié)果顯示算法尋優(yōu)效果較好,可以較快地得到全局最優(yōu)解。

關鍵詞：多準則尋優(yōu);差分進化算法;啟發(fā)式算法;個體適應度

近年來,在實際應用中,人們對數(shù)值算法的要求越來越高,傳統(tǒng)數(shù)值尋優(yōu)方法雖然理論基礎較好,能夠給出解析解,但是對問題本身也有較為苛刻的要求,如需要函數(shù)的梯度、可導性等信息,并且隨著問題規(guī)模的擴大,其計算復雜度也會呈指數(shù)形式增長。相較于傳統(tǒng)優(yōu)化方法,進化算法處理該類問題時,不需要函數(shù)具有過多的數(shù)學性質(zhì),并且具有計算速度快、解集可限定在某一誤差范圍之內(nèi)等特點,因而得到廣泛應用。

差分進化(differential evolution,DE)算法是Storn與Price[1]于20世紀90年代提出的一種進化算法。差分進化算法雖然是一種新興算法,但是在數(shù)值計算領域反響很好,應用范圍廣泛,相關研究工作進展迅速。2004年謝曉鋒等[2]對差分進化算法的縮放因子進行了討論；2006年吳亮紅等[3]提出自適應二次變異差分進化算法，Suganthan等[4]提出一種自適應差分進化算法,通過對上代種群的學習生產(chǎn)新的參數(shù)；2007年劉波等[5]對差分進化算法的發(fā)展作出了較全面地描述；2008年王培崇等[6]提出基于兩種進化模式的協(xié)作差分進化算法，2009年Qin等[7]也提出一種自適應進化算法,王培崇等[8]對差分進化算法進行了系統(tǒng)分析,并對其發(fā)展進行了展望；2011年Swagatam等[9]對差分進化算法的研究現(xiàn)狀進行了總結(jié),Mallipeddi等[10]從變異角度對算法提出新見解；2012年Islam等[11]對差分進化算法的變異與交叉策略進行改進。差分進化算法雖然具有很多優(yōu)異的特性,但是存在早熟、易陷入局部最優(yōu)、收斂速度較慢、參數(shù)因子選取不方便等缺點。

差分進化算法的選擇過程是根據(jù)解的適應度進行評價,若解的適應度較高則保留該解,否則放棄。這種選擇機制可以篩選出當前解集中較好的部分,但也存在一定局限性：該過程并不能確保當前解集具有良好的多樣性,易導致解集陷入局部最優(yōu)。本研究通過對適應度值、個體間距離等信息綜合考慮,提出一種可以動態(tài)調(diào)整參數(shù)的多準則尋優(yōu)策略,該策略可以對群體中個體進行多方位的比較,從而更加準確地篩選出更具優(yōu)勢的個體。

1差分進化算法

差分進化算法是基于群體智能理論的優(yōu)化算法,它通過種群內(nèi)部個體間的互相合作與競爭,產(chǎn)生群體智能進行優(yōu)化搜索。相較于其他進化算法,差分進化算法保留了基于種群的全局搜索策略,采用實數(shù)編碼技術,利用基于差分的簡單變異操作和一對一競爭生存策略,降低了進化操作的復雜性。該算法本質(zhì)上是一種基于實數(shù)編碼的具有保優(yōu)策略的貪婪遺傳算法,與遺傳算法的進化思想相似,亦包含交叉、變異和選擇的操作過程,二者的不同之處在于差分進化算法選擇一對一的淘汰機制來更新當代種群,在不降低精確性的前提下降低操作復雜性。

標準差分進化算法的操作過程包含變異、交叉和選擇三個步驟。初始解集在進化機制的作用下不斷向最優(yōu)方向游動,經(jīng)過多次進化迭代之后,能達到可接受誤差范圍之內(nèi),給出可行解。該方法操作簡單易行,求解速度較快。

標準差分進化算法流程如圖1所示。

圖1　差分進化算法流程圖

利用差分進化算法求最值問題時,首先需要生成初始種群,該操作是在可行域內(nèi)通過隨機策略產(chǎn)生一個解集,即隨機產(chǎn)生n個m維的個體,P=(X1，X2，…，XN),其中，Xi=(xi1，xi2，…，xim)T，i=1，2，…，N。結(jié)合進化思想,在初始解集的基礎上進行變異、交叉、選擇等進化操作。

1.1變異

(1)

1.2交叉

交叉操作可以增強種群個體的多樣性,該操作是將變異個體Vi與父代個體Xi進行交叉,從而產(chǎn)生新后代Ui的過程,如式(2)所示：

(2)

其中,Dj是一個隨機數(shù),且Dj～U(0，1)，jrand是[1,m]上的隨機整數(shù),Cr∈[0,1],稱為交叉概率。

1.3選擇

選擇操作是利用貪婪準則對交叉后代與父代個體進行篩選的過程,其選擇依據(jù)是個體適應度的優(yōu)劣程度。適應度高的個體可以進入下一代種群,反之則被淘汰：

(3)

當可行解達到預設精度后停止迭代,并輸出結(jié)果,也可以根據(jù)具體問題選定一個足夠大的迭代次數(shù),當達到該固定的迭代次數(shù)后,停止迭代,輸出結(jié)果。

歸納起來,差分進化算法具有以下優(yōu)點：

1)具有通用性,不要求問題具有很強的數(shù)學條件;

2)操作簡單,易于實現(xiàn);

3)群體效果明顯,可以通過已知最優(yōu)解進一步搜索;

4)易與其他方法混合使用。

2基于多準則尋優(yōu)策略的差分進化算法

2.1種群生存規(guī)模

進化算法借鑒了生物進化過程中的相關概念與機制,并將其運用到數(shù)值計算或問題尋優(yōu)過程當中。但生物在進化過程中以種群為單位,種群規(guī)模在生物進化中有著重要地位,這將涉及到種群生存能力分析(population viability analysis)理論。種群生存能力分析是生物學中研究如何保護生物避免滅絕的一個熱點[12-14],主要研究隨機干擾對小種群滅絕的影響,目的是確定最小生存種群(minimum viable population,MVP)數(shù)量,把種群滅絕的可能性減少到可接受水平。

最小生存種群數(shù)量指的是種群免遭滅絕而必須維持的最低個體數(shù)量，或是確保某一物種長期存活所必需的個體數(shù)。Franklin[15]曾提出小族群管理的50/500法則,指出為了防止族群在短期內(nèi)出現(xiàn)近交衰退的情形,族群中至少需要50個個體,而需要500個以上的個體才能維持種群的遺傳變異性。

本研究結(jié)合最小生存種群數(shù)量的概念與50/500法則,在差分進化算法中引入最小生存種群數(shù)量的概念,為進化算法的種群規(guī)模制定一個相對明確的取值范圍,即在一般情況下種群規(guī)模應當不小于50,在計算機能力允許范圍內(nèi),應當擴大種群規(guī)模至500個個體以上。

2.2變異因子與交叉概率

進化算法的搜索性能取決于算法全局探索和局部開發(fā)能力的平衡,這就需要對算法中的參數(shù)進行恰當?shù)倪x取,差分進化算法中的變異因子與交叉概率的選取直接影響算法的收斂能力與計算速度。變異因子F一般情況下是人為選取的一個經(jīng)驗值,受人為因素影響較大。交叉概率Cr的選取過程亦如此。文獻[16]對差分進化算法的變異因子與交叉概率的選取過程進行分析,提出變異因子F取值在[0.5,1]時算法效果較好,交叉概率Cr的選取則需要根據(jù)求解函數(shù)進行選取,一般單峰函數(shù)的值相對大一些,在[0.6,0.8],多峰函數(shù)Cr的值相對小一些,在[0.1,0.5]。根據(jù)文獻[16]的研究成果,本研究引入動態(tài)適應調(diào)節(jié)機制,在參數(shù)選取過程中逐漸降低變異范圍,以減弱解集在不斷靠近最優(yōu)解時產(chǎn)生的震蕩現(xiàn)象,F取值變化示意圖如圖2所示。F為隨機數(shù),且F～U(a,b),本文中a取定值0.5。隨著迭代次數(shù)的增加,b的取值隨之不斷減小,理論上每一代計算中b的值都可以減小,但是為了方便計算,本研究中令b每隔若干代變化一次,bi+1=bi-(b0-a)/(G/k),其中G為總的進化代數(shù)。k為間隔代數(shù),也可以根據(jù)實際情況選取k的變化規(guī)則。令交叉概率Cr為一個隨機數(shù),且Cr～U(0,0.5)(可根據(jù)函數(shù)性質(zhì)選取)。

圖2　F變化示意圖

2.3多準則尋優(yōu)策略

本研究針對差分進化算法全局搜索能力較弱,收斂速度較差等問題,提出一種多準則尋優(yōu)策略,該策略將結(jié)合群體的適應度、個體間距離等信息進行個體尋優(yōu),在一定程度上增強種群多樣性及全局搜索能力。差分進化算法結(jié)合該策略對每一代種群進行篩選,將部分相似(冗余)個體或非優(yōu)秀個體進行剔除,僅保留更具有代表性的個體或優(yōu)勢個體,在此過程中,為了使種群規(guī)模維持在一個相對穩(wěn)定的狀態(tài),將對缺失部分進行重新填充,從而得到一個新的具有較強優(yōu)勢與豐富多樣性的種群,如圖3所示。

圖3　種群中個體的篩選

定義1相似(冗余)個體是指兩個體在解空間中距離較近,且其適應度排序值相近。

定義2非優(yōu)秀個體是指在進化過程中,適應度較低的個體。

改進的差分進化算法計算過程中亦采取精英保留策略,對每一代種群中的優(yōu)秀個體進行存檔,并與下一代種群相融合以進行擇優(yōu)操作,利用這種機制可以使得每一代種群都能得到不劣于上一代的個體(解),并且該方式可以確保進化方向的正確性,保證優(yōu)秀染色體更加有效地傳遞給下一代,避免進化“倒退”現(xiàn)象的發(fā)生。

該算法中需要對種群中的相似(冗余)個體進行處理,即剔除相似(冗余)個體以及非優(yōu)秀個體。針對該問題需要考慮：①剔除哪些個體,其依據(jù)是什么；②種群中剔除多少個體比較合理，或種群中應保留多少個體比較合理。

問題①是要找到判斷個體優(yōu)劣程度的評價標準。在對種群中所有個體進行評價時,一般情況下是根據(jù)適應度指標找到優(yōu)秀解,而本研究所提出的多準則尋優(yōu)策略除了考慮個體的適應度之外,還考慮個體與個體間的距離,因為距離較近的個體可能處于同一遞增或遞減區(qū)間之內(nèi),此時會影響到種群多樣性,而剔除個體的目的是為了剔除這些相似(冗余)個體或非優(yōu)秀個體,因此除了以適應度作為評價依據(jù)外還應結(jié)合個體之間的距離進行評價,即采用兩個評價依據(jù)：每個個體的適應度值；個體與個體之間的距離。

根據(jù)以上兩個評價依據(jù),首先按照適應度信息對所有個體進行排序,得到非優(yōu)秀個體的相關信息,之后以該類別中適應度最高的個體為原點,計算該個體與其他個體間的距離(本文采用歐式距離),從而得到與該個體相似(冗余)個體的相關信息。

問題②是對種群中個體保留數(shù)量的討論,此時需要考慮種群規(guī)模以及個體間的冗余度,本文給出每一代保留數(shù)量為Pop/10,其中Pop為種群規(guī)模。

對種群篩選完成之后,需要生成新的個體以補充因舍棄相似(冗余)個體或非優(yōu)秀個體所產(chǎn)生的空缺。向種群中投放新個體時,此時仍采取一種互補策略,即盡量生成與現(xiàn)有個體差異性較大的個體,增強種群豐富度。

根據(jù)以上分析,該多準則尋優(yōu)策略算法的步驟為：

Step 1計算種群中每個個體的適應度；

Step 2對當代種群中的個體按照適應度進行排序；

Step 3計算適應度最優(yōu)個體與其他個體間的歐式距離；

Step 4根據(jù)距離的大小對每個個體進行編號；

Step 5結(jié)合權(quán)重,對適應度與個體間距離綜合評價,并按優(yōu)劣程度編號；

Step 6刪除種群中相似(冗余)個體及非優(yōu)秀個體；

Step 7生成新的個體,補充種群中的空缺位置。

3算例

選取8個較為常見的測試函數(shù)[17]進行數(shù)值實驗,以驗證上文所提出的改進差分進化算法的合理性以及可行性。

測試函數(shù) 1:Rosenbrock function

f(1,1)=0,-∞≤xi≤∞,1≤i≤n,此處n=2

(4)

測試函數(shù) 2:Beale function

f(3,0.5)=0,(-4.5≤x,y≤4.5)

(5)

測試函數(shù) 3:Goldstein-Price function

f(0,-1)=3,-2≤x,y≤2

(6)

測試函數(shù) 4:Matyas function

(7)

測試函數(shù) 5:Three-hump camel function

(8)

測試函數(shù) 6:Easom function

f(π,π)=-1,-100≤x,y≤100

(9)

測試函數(shù) 7:Ackley’s function

f(0,0)=0,-5≤x,y≤5

(10)

測試函數(shù) 8:Lévi function N.13

f(1,1)=0,-10≤x,y≤10

(11)

由于篇幅有限,僅給出測試函數(shù)7與測試函數(shù)8的函數(shù)圖象,可以看出測試函數(shù)中存在無數(shù)多個極小點，能夠很好地檢測算法的全局尋優(yōu)特性。每一個測試函數(shù)設定初始種群規(guī)模為200個,進化代數(shù)為100代,每個測試函數(shù)均計算20次,以平均值作為最終計算結(jié)果,該結(jié)果與真實解的對比關系如表1所示。

從表1中可以看出,本文提出的基于多準則尋優(yōu)策略的改進差分進化算法在數(shù)值實驗過程中表現(xiàn)出良好的特性,可以計算出測試函數(shù)的近似解,并且誤差范圍非常較小,滿足精度需求。

為了進一步說明算法的有效性,給出標準差分進化算法與改進算法在求解過程中迭代次數(shù)與最優(yōu)函數(shù)值的變化規(guī)律曲線,由于篇幅有限,僅給出Lévi N.13函數(shù)求解過程的對比曲線,如圖6所示。

圖4　測試函數(shù)7(Ackley’s function)

圖5　測試函數(shù)8(Lévi function N.13)

表1　測試函數(shù)對應的計算結(jié)果

圖6　兩種算法求解Lévi N.13函數(shù)的對比關系

結(jié)合表1和圖6可知,改進的差分進化算法的計算效果要優(yōu)于傳統(tǒng)的差分進化算法,并且可以更具有針對性地選擇優(yōu)勢個體,使之得以保留,這不僅增強了種群多樣性,也避免了搜索過程中易陷入局部極值的缺陷,大大增強了全局搜索能力。

4結(jié)束語

在經(jīng)典差分進化算法基礎上,提出一種動態(tài)調(diào)節(jié)機制用以選取變異因子;針對算法易陷入局部最優(yōu)解,缺乏多樣性的現(xiàn)象,提出一種多準則尋優(yōu)策略,根據(jù)適應度與距離等屬性綜合評價解的優(yōu)劣程度;通過排除冗余個體,加入互補解,增強解集多樣性,避免陷入局部最優(yōu)。最后，通過測試函數(shù)對算法進行測試。測試結(jié)果顯示,改進差分進化算法具有可行性,并且收斂速度與計算精度上均表現(xiàn)良好。

參考文獻：

[1]STORN R，PRICE K.Differential evolution：A simple and efficient heuristic for global optimization over continuous spaces[J].Journal of Global Optimization，1997,11:341-359.

[2]謝曉鋒,張文俊,張國瑞,等.差異演化的實驗研究[J].控制與決策,2004,19(1):49-52.

XIE Xiaofeng,ZHANG Wenjun,ZHANG Guorui,et al.Empirical study of differential evolution[J].Control and Decision,2004,19(1):49-52.

[3]吳亮紅,王耀南,袁小芳,等.自適應二次變異差分進化算法[J].控制與決策,2006,21(8):898-902.

WU Lianghong,WANG Yaonan,YUAN Xiaofang,et al.Differential evolution algorithm with adaptive second mutation[J].Control and Decision,2006,21(8):898-902.

[4]BREST J,GREINER S,BOSKOVIC B,et al.Self-adapting control parameters in differential evolution:A comparative study on numerical benchmark problems[J].Evolutionary Computation,IEEE Transactions on,2006,10(6):646-657.

[5]劉波,王凌,金以慧.差分進化算法研究進展[J].控制與決策,2007,22(7):721-729.

LIU Bo,WANG Ling,JIN Yihui.Advances in differential evolution[J].Control and Decision,2007,22(7):721-729.

[6]王培崇,賀毅朝,錢旭.基于兩種進化模式的雙種群協(xié)作差分演化算法[J].計算機工程與應用,2008,25:60-64.

WANG Peichong,HE Yichao,QIAN Xu.Cooperation differential evolution algorithm with double populations and two evolutionary models[J].Computer Engineering and Applications,2008,44(25):60-64.

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

[8]王培崇,錢旭,王月,等.差分進化計算研究綜述[J].計算機工程與應用,2009,45(28):13-16.

WANG Peichong，QIAN Xu，WANG Yue，et al.Overview of differential evolution algorithm[J].Computer Engineering and Applications,2009,45(28):13-16.

[9]DAS S,SUGANTHAN P N.Differential evolution:A survey of the state-of-the-art[J].IEEE Transactions on Evolutionary Computation,2011,15(1):4-31.

[10]MALLIPEDDI R,SUGANTHAN P N,PAN Q K,et al.Differential evolution algorithm with ensemble of parameters and mutation strategies[J].Applied Soft Computing,2011,11(2):1679-1696.

[11]ISLAM S M,DAS S,GHOSH S,et al.An adaptive differential evolution algorithm with novel mutation and crossover stra-tegies for global numerical optimization[J].IEEE Transactions on Systems,Man,and Cybernetics,Part B:Cybernetics,2012,42(2):482-500.

[12]SHAFFER M L.Minimum population sizes for species conservation[J].Bioscience,1981,31:131-134.

[13]REED D H,O′GRADY J J,BROOK B W,et al.Estimates of minimum viable population sizes for vertebrates and factors influencing those estimates[J].Biological Conservation,2003,113(1):23-34.

[14]TRAILL L W,BRADSHAW C J A,BROOK B W.Minimum viable population size:A meta-analysis of 30 years of published estimates[J].Biological Conservation,2007,139(1):159-166.

[15]FRANKLIN I R.Evolutionary change in small populations[M]//Conservation Biology,An Evolutionary-Ecological Perspective.Sunderland,Massachusetts:Sinauer Associates,USA,1980:135-149.

[16]高岳林,劉軍民.差分進化算法的參數(shù)研究[J].黑龍江大學自然科學學報,2009,26(1):81-85.

GAO Yuelin,LIU Junmin.Parameter study of differential evolution algorithm[J].Journal of Natural Science of Heilongjiang University,2009,26(1):81-85.

[17]Wikipedia contributors.Test functions for optimization[EB/OL].(2015-03-31)[2015-04-09]http://en.wikipedia.org/w/ index.php?title=Test—functions—for—optimization/&oldid=654396409.

(責任編輯：呂文紅)

Differential Evolution Algorithm Based on Multi-criteria Optimization Strategy

CHEN Yan,WANG Zongxian

(College of Science,Shenyang University of Technology,Shenyang,Liaoning 110870,China)

Abstract:Based on differential evolution algorithm,this paper proposed an improved differential evolution algorithm with multi-criteria optimization strategy.This algorithm can adjust the mutation and crossover parameters dynamically,and evaluate individuals' grade of excellence with the evaluation indexes like individual fitness and distance between individuals on the basis of the proposed multi-criteria optimization strategies.It can also reduce the degree of population density and enhance population diversity.Although this evaluation mechanism can effectively avoid premature convergence of population,it tends to result in local optimum risk.After it was tested by some test functionsand compared with standard differential evolution algorithm,this improved algorithm was found to have the best optimization effect,being able to obtain the global optimal solution quickly.

Key words:multi-criteria optimization;differential evolution algorithm;heuristic algorithm;imdividual fitness

收稿日期：2015-11-19

作者簡介：陳巖(1968—),男,遼寧沈陽人,教授,博士,主要從事優(yōu)化方法和決策方面的研究. E-mail:crouse_chen@126.com

中圖分類號：O221.4

文獻標志碼：A

文章編號：1672-3767(2016)01-0102-07