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

陳　巖,王宗憲

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

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

陳巖,王宗憲

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

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

關(guān)鍵詞：多準(zhǔn)則尋優(yōu);差分進(jìn)化算法;啟發(fā)式算法;個(gè)體適應(yīng)度

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

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

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

1差分進(jìn)化算法

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

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

標(biāo)準(zhǔn)差分進(jìn)化算法流程如圖1所示。

圖1　差分進(jìn)化算法流程圖

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

1.1變異

(1)

1.2交叉

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

(2)

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

1.3選擇

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

(3)

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

歸納起來(lái),差分進(jìn)化算法具有以下優(yōu)點(diǎn)：

1)具有通用性,不要求問(wèn)題具有很強(qiáng)的數(shù)學(xué)條件;

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

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

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

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

2.1種群生存規(guī)模

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

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

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

2.2變異因子與交叉概率

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

圖2　F變化示意圖

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

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

圖3　種群中個(gè)體的篩選

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

定義2非優(yōu)秀個(gè)體是指在進(jìn)化過(guò)程中,適應(yīng)度較低的個(gè)體。

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

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

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

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

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

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

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

Step 1計(jì)算種群中每個(gè)個(gè)體的適應(yīng)度；

Step 2對(duì)當(dāng)代種群中的個(gè)體按照適應(yīng)度進(jìn)行排序；

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

Step 4根據(jù)距離的大小對(duì)每個(gè)個(gè)體進(jìn)行編號(hào)；

Step 5結(jié)合權(quán)重,對(duì)適應(yīng)度與個(gè)體間距離綜合評(píng)價(jià),并按優(yōu)劣程度編號(hào)；

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

Step 7生成新的個(gè)體,補(bǔ)充種群中的空缺位置。

3算例

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

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

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

(4)

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

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

(5)

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

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

(6)

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

(7)

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

(8)

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

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

(9)

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

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

(10)

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

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

(11)

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

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

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

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

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

表1　測(cè)試函數(shù)對(duì)應(yīng)的計(jì)算結(jié)果

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

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

4結(jié)束語(yǔ)

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

參考文獻(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]謝曉鋒,張文俊,張國(guó)瑞,等.差異演化的實(shí)驗(yàn)研究[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]吳亮紅,王耀南,袁小芳,等.自適應(yīng)二次變異差分進(jìn)化算法[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ìn)化算法研究進(jìn)展[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]王培崇,賀毅朝,錢旭.基于兩種進(jìn)化模式的雙種群協(xié)作差分演化算法[J].計(jì)算機(jī)工程與應(yīng)用,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ìn)化計(jì)算研究綜述[J].計(jì)算機(jī)工程與應(yīng)用,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]高岳林,劉軍民.差分進(jìn)化算法的參數(shù)研究[J].黑龍江大學(xué)自然科學(xué)學(xué)報(bào),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.

(責(zé)任編輯：呂文紅)

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

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

中圖分類號(hào)：O221.4

文獻(xiàn)標(biāo)志碼：A

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