王麗穎,帥真浩

(大連海事大學(xué) 信息科學(xué)與技術(shù)學(xué)院,大連 116033)

差分進(jìn)化算法(DE)是美國(guó)學(xué)者Storn[1]于1995年以技術(shù)報(bào)告的形式提出的基于種群優(yōu)化理論的算法,通過變異、交叉和選擇父代之間的差異向量來優(yōu)化,與常見的進(jìn)化計(jì)算技術(shù)[2-4]類似,進(jìn)化計(jì)算使用逐代優(yōu)化過程,然后使用并行處理在引導(dǎo)隨機(jī)搜索中選擇該群體,以實(shí)現(xiàn)期望的目的.近年來,許多改進(jìn)變異策略的DE 的變體都得到了很好的改進(jìn).其在約束優(yōu)化計(jì)算[5],聚類優(yōu)化計(jì)算[6],非線性優(yōu)化控制[7],神經(jīng)網(wǎng)絡(luò)優(yōu)化[8],濾波器設(shè)計(jì)[9],陣列天線方向圖綜合[10,11]及其它方面[12-14]得到廣泛應(yīng)用.

1 差分策略

自DE 概念化以來,研究主要圍繞著種群重構(gòu)問題,差分策略問題以及控制參數(shù)問題3 個(gè)方面進(jìn)行改進(jìn),本文則主要針對(duì)差分策略問題進(jìn)行改進(jìn).為了更加有效的解決實(shí)際問題,國(guó)內(nèi)外許多學(xué)者對(duì)DE 算法在差分策略上進(jìn)行了大量的改進(jìn).Das 等人[15]和Zhang等人[16]在2009年對(duì)每個(gè)種群成員采用鄰域的概念,并在DE 中采用DE/target-to-best/1 突變方案.Zhang 等人[16]在2009年提出了一種具有可選的外部存檔和自適應(yīng)更新控制參數(shù)的差分變異策略DE/current-to-bestp,其可選的歸檔操作利用歷史數(shù)據(jù)來提供有關(guān)進(jìn)展方向的信息.Mallipeddi 等人[17]在2010年提出了一種不同的突變策略池以及每個(gè)控制參數(shù)的值池在整個(gè)進(jìn)化過程中共存,并競(jìng)爭(zhēng)產(chǎn)生后代解的EPSDE 策略.Islam 等人[18]在2012年提出了一種新的具有二項(xiàng)交叉和自適應(yīng)控制參數(shù)的變異策略.Piotrowski[19]在2013年提出了一種基于全局鄰域和局部鄰域的模因變異算子.Liao等人[20]在2014年利用基于環(huán)拓?fù)涞耐蛔儾呗蕴岣逥E 的性能,以更快地收斂到全局解.Aldabbagh 等人[21]同年提出了DE 的一種將標(biāo)準(zhǔn)變異方案DE/current-to-rand/1 替換為DE/current-to-rand 方案的新變體DE-bea,其新突變方案稱為細(xì)菌突變方案.Yu 等人[22]在2015年提出了一種DE 變體,當(dāng)種群聚集在局部最優(yōu)時(shí),他們考慮自適應(yīng)控制參數(shù).Mohamed[23]在2015年提出了一種基于凸組合向量的三角形突變方法.他隨機(jī)選取3 個(gè)向量,計(jì)算出最佳和最差向量的差值,并將其與基本變異規(guī)則相結(jié)合.Cui 等人[24]在2016年發(fā)了一種MPADE 算法,該算法根據(jù)適應(yīng)度值將種群分為3 部分,并在其上應(yīng)用3 種變異策略進(jìn)行開發(fā)或探索,進(jìn)而設(shè)計(jì)一種參數(shù)調(diào)整的自適應(yīng)技術(shù).Sun 等人[25]在2017年將依靠鄰域關(guān)系的DE 算法變異算子稱為NDE 池的種群拓?fù)溆糜诙x多個(gè)社區(qū)關(guān)系,為每個(gè)單獨(dú)的鄰里關(guān)系是自適應(yīng)地選擇.

差分策略可以被表示為DE/x/y,其中,x表示當(dāng)前被變異的向量的狀態(tài),是隨機(jī)的,最佳的或者其他;y表示在變異過程中所采用的差分向量的個(gè)數(shù).多種變異策略中DE/best/1 和DE/rand/1 的應(yīng)用最為廣泛.其中,DE/best/1 策略的局部搜索能力強(qiáng),但是與此同時(shí),存在全局探測(cè)能力較差的特點(diǎn);而DE/rand/1 策略全局探測(cè)能力強(qiáng),但是擁有局部搜索能力弱的缺點(diǎn).為了解決這一問題,本文基于差分突變的靈感提出了一種不需要作為參考的可行解的方法,即結(jié)合兩個(gè)著名的DE 變體:DE/rand/1 和DE/best/1,提出了一種新的變異策略.結(jié)合外部存檔的思想,同時(shí)將分治法的思想引入種群初始化,提出DE/bestbp-randw/2 策略和DE/bestwprandb/2 策略相結(jié)合的雙種群兩階段變異策略(TPSDE),TPSDE 大致可以劃分為兩個(gè)階段,分別是初始化后每i個(gè)鄰域內(nèi)的局部搜索階段,以及在整個(gè)集合內(nèi)的搜索階段.首先,TPSDE 第一階段是在初始化后,經(jīng)過一輪訓(xùn)練,個(gè)體按照適應(yīng)度大小排序完成后,將整個(gè)種群進(jìn)行區(qū)域劃分為子種群P1和子種群P2,其中P1種群個(gè)體適應(yīng)度普遍比P2更高,然后分別按照不同的變異策略進(jìn)行局部搜索.這種做法使得算法在進(jìn)化過程的初期,兩個(gè)子種群的內(nèi)部進(jìn)化可以讓結(jié)構(gòu)往好的方向發(fā)展,更好的提高算法的收斂速度找到最優(yōu)解;但是,在種群進(jìn)化后期,算法經(jīng)過多次迭代之后,由于個(gè)體間差異過小,從而導(dǎo)致后期種群向全局最優(yōu)解的進(jìn)化停滯,收斂速度較慢.因此,為了增加個(gè)體多樣性,同時(shí)需要第二個(gè)階段勘測(cè)整個(gè)種群范圍來提高全局搜索尋優(yōu)能力.其相對(duì)于其他的變異策略主要的優(yōu)勢(shì)在于可以很好的平衡收斂性能的提高和種群多樣性保持之間的關(guān)系.

2 差分進(jìn)化過程

DE 是一種低空間復(fù)雜度,高可拓展性并且在解決非線性、多模態(tài)和不可分離性等各種具有挑戰(zhàn)性問題時(shí)表現(xiàn)更高效的優(yōu)化進(jìn)化算法.DE 算法有兩個(gè)階段,分別是初始化和進(jìn)化.在第一階段,種群是隨機(jī)生成的,是一次性的過程;在第二階段,即進(jìn)化,生成的種群會(huì)經(jīng)歷突變、交叉和選擇過程,這些過程在DE 的搜索過程中重復(fù)進(jìn)行,直到滿足終止標(biāo)準(zhǔn),最終在 D 維實(shí)參數(shù)空間中搜索全局最優(yōu)點(diǎn).終止條件可以通過如下來判斷:根據(jù)目標(biāo)函數(shù)的復(fù)雜性所對(duì)應(yīng)固定次數(shù)的迭代Gmax值;群體的最佳適應(yīng)度在連續(xù)迭代中沒有明顯變化;取得了預(yù)先指定的目標(biāo)函數(shù)值.

算法的基本流程為:首先隨機(jī)初始化一個(gè)隨機(jī)設(shè)定的NP維實(shí)值參數(shù)向量的總體.每個(gè)向量,也稱為基因組或者 染色體,形成多維優(yōu)化問題的候選解.我們將用G=0,1,…,Gmax來表示DE 中的后代.從中隨機(jī)選取兩個(gè)解向量作差,用一個(gè)標(biāo)量F來定標(biāo),定標(biāo)后的差加到第3 個(gè)向量上進(jìn)而產(chǎn)生一個(gè)新的解即變異個(gè)體vi,g.然后這個(gè)新的解與預(yù)先設(shè)定的初始解xi,g根據(jù)交叉原則進(jìn)行操作,在保證變異個(gè)體一定對(duì)交叉后的解產(chǎn)生一些影響即有基因傳給下一代的同時(shí),按照一定的概率決定生成的個(gè)體ui,g繼承的基因來自于哪個(gè)個(gè)體.交叉操作完成后,為了在隨后的世代中保持種群大小不變,算法的下一步需要進(jìn)行選擇,需要將xi,g和ui,g進(jìn)行一對(duì)一的錦標(biāo)賽選擇,如果的ui,g適應(yīng)度值優(yōu)于xi,g的適應(yīng)度值,則ui,g取代xi,g繼續(xù)進(jìn)行進(jìn)化活動(dòng),算法通過不斷地迭代計(jì)算,保留適應(yīng)度值更高的個(gè)體,即保留更優(yōu)解取代局部最優(yōu)解,直到向全局最優(yōu)解逼近.下面為標(biāo)準(zhǔn)差分進(jìn)化算法步驟:

(1)種群初始化,初始化是在 DE 中尋找位于D 維參數(shù)空間中的實(shí)數(shù)全局最優(yōu)解的第一個(gè)過程.對(duì)于問題的每個(gè)參數(shù),可能存在一定的范圍,參數(shù)的值應(yīng)該被限制在這個(gè)范圍內(nèi).初始種群即在G= 0 時(shí),應(yīng)通過在受規(guī)定的最小和最大邊界約束的搜索空間內(nèi)均勻隨機(jī)化個(gè)體來盡可能覆蓋此范圍.參數(shù)向量個(gè)體表示為:

xi,g表示的是第g代的第i個(gè)解,即目標(biāo)個(gè)體,隨機(jī)產(chǎn)生NP個(gè)初始解,每個(gè)解均有D維向量.式(2)為在可行域內(nèi)隨機(jī)產(chǎn)生的初始種群.

其中,xmax,j,xmin,j分別是個(gè)體中第j個(gè)分量的上下限;rand(0,1)為[0,1]區(qū)間的一個(gè)隨機(jī)數(shù).

(2)變異操作.生物學(xué)上,“突變”是指染色體基因特征的突然變化.然而,在進(jìn)化計(jì)算范式的背景下,突變也被視為隨機(jī)元素的變化或擾動(dòng).變異操作即將目標(biāo)向量xi,g通過差分變異操作后與自身重組形成變異向量vi,g+1的過程,其最大優(yōu)勢(shì)之一是變異步長(zhǎng)的大小和方向都會(huì)自動(dòng)適應(yīng)目標(biāo)函數(shù)值.這個(gè)過程一般需要3 個(gè)個(gè)體,而這3 個(gè)目標(biāo)向量索引的選取是從范圍[1,NP]中隨機(jī)選擇的互斥整數(shù)r1、r2和r3,將任何兩個(gè)向量差值都按標(biāo)量F進(jìn)行縮放,然后再將縮放后的差值添加到第3 個(gè)向量中.如圖1所示.兩個(gè)應(yīng)用最廣泛的變異策略DE/best/1 的第3 個(gè)個(gè)體xr1,g是種群中的最優(yōu)個(gè)體;而DE/rand/1 策略的xr1,g是種群中的隨機(jī)個(gè)體,然后將(xr2,g-xr3,g)乘上F后與xr1,g求和而產(chǎn)生變異個(gè)體Vi,g+1.具體如式(3)表示.

圖1 TPSDE 基本流程圖

其中,F是變異因子,位于[0,1]之間,一般取值0.5.g表示進(jìn)化的代數(shù),i表示第i個(gè)染色體,即第i個(gè)個(gè)體,r1,r2,r3表示索引,即隨機(jī)第ri個(gè)個(gè)體.

(3)交叉操作.通過交換部分變異向量vi,g和目標(biāo)向量xi,g維度產(chǎn)生中間向量Ui,g來提高種群的多樣性,使用下面交叉策略進(jìn)行交叉.染色體i=1,2,3,…,N;基因j=1,2,…,D;CR是交叉因子是[0,1]內(nèi)隨機(jī)數(shù),一般取值0.5.jrand是1 到D隨機(jī)數(shù),以保證變異向量至少有一維信息被保存在交叉向量里.j取隨機(jī)數(shù)保證了交叉過程中一定會(huì)有變異后個(gè)體vi,(g+1)的基因,而r1,r4 的取值小于等于CR,因此交叉后代ui,(g+1)的基因來自于變異后的染色體vi,(g+1),而r2,r3 的大于CR,因此交叉后代ui,(g+1)的基因來自于親本的染色體xi,g.

(4)選擇操作.選擇所的生成的下一代個(gè)體是xi,g還是ui,g,即最優(yōu)解是初始解還是經(jīng)過一系列操作之后形成的新解.需要將這組新解根據(jù)適應(yīng)度和原來那組解進(jìn)行一對(duì)一的錦標(biāo)賽選擇,式(5)為差分進(jìn)化算法適應(yīng)度計(jì)算方法.對(duì)于求最小值問題,如果目標(biāo)函數(shù)值比原來那組解小則將它們替換掉,否則保留原來解.f(x)為目標(biāo)函數(shù)值,而對(duì)于應(yīng)用在神經(jīng)架構(gòu)搜索中的差分進(jìn)化算法的選擇方法是根據(jù)適應(yīng)度函數(shù)進(jìn)行選擇.

(5)適應(yīng)度函數(shù)的計(jì)算.適應(yīng)度指的是個(gè)體在種群生存的優(yōu)勢(shì)程度度量,用于區(qū)分個(gè)體的“好與壞”,通過比較適應(yīng)度值的大小.對(duì)于求函數(shù)最優(yōu)解問題時(shí),標(biāo)準(zhǔn)差分進(jìn)化算法需要將這組解和原來那組解根據(jù)適應(yīng)度值的大小進(jìn)行一對(duì)一的錦標(biāo)賽選擇,判斷從上面得到的進(jìn)化之后的解是否可以作為下一代的解,適應(yīng)度函數(shù)即用來計(jì)算適應(yīng)度值的函數(shù).

3 改進(jìn)差分策略的差分進(jìn)化算法

本文通過重新構(gòu)建子種群網(wǎng)絡(luò),并按照各自合適的變異策略進(jìn)行變異,同時(shí)結(jié)合局部和全局同時(shí)進(jìn)化的方法,取代使用單一變異策略,從而提高了種群的全局搜索尋優(yōu)能力和局部搜索尋優(yōu)能力,進(jìn)而避免了過早收斂和搜索停滯等問題的出現(xiàn),提升算法的收斂速度和求解精度.TPSDE 首先隨機(jī)初始化固定長(zhǎng)度的種群,經(jīng)過一輪訓(xùn)練后得到種群的適應(yīng)值大小,然后進(jìn)行變異交叉的操作.為了進(jìn)行下面的變異操作,TPSDE 提出了向量之間的鄰域結(jié)構(gòu),向量的鄰域是它所連接的其他參數(shù)向量的集合.該鄰域是根據(jù)種群成員的適應(yīng)度順序確定的.例如,的兩個(gè)鄰域向量.因?yàn)猷徲虼笮”仨毿∮诜N群大小,所以每個(gè)向量都有一個(gè)半徑為k的鄰域,其中k是從0 到(NP-1)的非零正整數(shù),取領(lǐng)域向量被表示為:

同時(shí),他們適應(yīng)度的大小為:

局部?jī)?yōu)化過程針對(duì)不同子種群運(yùn)用不同的變異策略.結(jié)合DE/best/1 和DE/rand/1 策略的優(yōu)點(diǎn)做出改進(jìn)應(yīng)用于不同的進(jìn)化階段,仿真實(shí)驗(yàn)結(jié)果表示這比整個(gè)進(jìn)化過程中僅采用一種變異策略表現(xiàn)出了更加優(yōu)越的性能.基于此,本文提出DE/bestbp-randw/2 策略和DE/bestwp-randb/2 策略相結(jié)合的變異策略使兩個(gè)子種群協(xié)同進(jìn)化,這種策略下較好個(gè)體的數(shù)量會(huì)隨著階段的發(fā)展逐級(jí)增加,不僅不斷增強(qiáng)子種群P1的全局搜索尋優(yōu)能力;而且子種群P2的局部搜索尋優(yōu)能力同時(shí)得到提高.從而避免了其因個(gè)體間差異過小,種群個(gè)體多樣性的缺失,從而導(dǎo)致的搜索停滯問題.雙種群變異策略具體如下.

TPSDE 引入了新的參數(shù)ω在DE 中起著參數(shù)F的相同作用.參數(shù)ω控制勘探和開采之間的平衡,比如ω取較小的值時(shí),比如趨近于0,有利于全局變量分量,即更好的開采,而取較大的值時(shí),比如趨近于1 時(shí),有利于局部鄰域分量,即更好的勘探.

結(jié)合標(biāo)準(zhǔn)差分進(jìn)化算法的框架以及雙種群兩階段的變異策略,局部與整體協(xié)同進(jìn)化的思想,提出基于雙種群兩階段變異策略的差分進(jìn)化算法(TPSDE),具體實(shí)現(xiàn)流程如下所示.

Step 1.種群初始化.隨機(jī)生成種群規(guī)模為NP的初始解集合.

Step 2.第一階段局部?jī)?yōu)化.將初始化的種群進(jìn)行一輪訓(xùn)練,并且按照適應(yīng)度從大到小排序,并在k=(NP-1)/2 處將其分成兩個(gè)子種群區(qū)域,即子種群(better)P1和子種群(worse)P2.

Step 3.對(duì)于子種群P1的個(gè)體,采用DE/bestbprandw/2 的變異策略進(jìn)行差分進(jìn)化得到向量Vbi,g.

Step 4.對(duì)于子種群P2的個(gè)體,采用DE/bestwprandb/2 的變異策略進(jìn)行差分進(jìn)化得到向量Vwi,g.

Step 5.將子種群P1,P2變異后產(chǎn)生的Vbi,g和Vwi,g加權(quán)求和產(chǎn)生變異子向量V1i,g.

Step 6.第二階段全局優(yōu)化.采用DE/rand/1 的變異策略在全種群范圍內(nèi)搜索,得到變異子向量V2i,g.

Step 7.將變異子向量V1i,g和變異子向量V2i,g按照同樣的規(guī)則組合在一起得到最終的變異向量vi,g.

Step 8.按照式(4)交換部分變異向量vi,g和目標(biāo)向量xi,g基因產(chǎn)生中間向量ui,g.

Step 9.算法初始化將產(chǎn)生的交叉向量ui,g和目標(biāo)向量xi,g根據(jù)適應(yīng)度的大小進(jìn)行一對(duì)一的錦標(biāo)賽選擇,保留適應(yīng)度更高的個(gè)體作為新的種群P′.

Step 10.種群初始化判斷算法是否滿足終止條件.若滿足,則算法結(jié)束,輸出當(dāng)前最優(yōu)值為最終結(jié)果;若不滿足,則令g=g+1,并跳到Step 2.圖1 即TPSDE 的基本流程圖.

4 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

4.1 實(shí)驗(yàn)仿真

為了驗(yàn)證TPSDE 算法的有效性與先進(jìn)性,在實(shí)驗(yàn)過程中將標(biāo)準(zhǔn)Benchmark 測(cè)試函數(shù)分別進(jìn)行固定次數(shù)的仿真實(shí)驗(yàn),這里我進(jìn)行30 次實(shí)驗(yàn)之后進(jìn)行統(tǒng)計(jì),同時(shí)對(duì)于函數(shù)的選取也是極具代表性,選取的這些測(cè)試函數(shù)包括單峰函數(shù)以及多峰函數(shù),單模態(tài)以及多模態(tài)函數(shù),函數(shù)曲線是連續(xù)或者間斷的以及有的具有多個(gè)局部最優(yōu)解而有的函數(shù)沒有局部最優(yōu)解.他們的函數(shù)名稱、搜索范圍,維數(shù)以及理論上最優(yōu)值如表1所示.所有函數(shù)維數(shù)取D=30,種群規(guī)模NP=50,F=0.5,CR=0.5,4 種算法獨(dú)立運(yùn)行30 次后的誤差平均值與標(biāo)準(zhǔn)方差的統(tǒng)計(jì)結(jié)果如表2所示.

表1 測(cè)試函數(shù)及特征

表2 各算法運(yùn)行30 次統(tǒng)計(jì)

4.2 實(shí)驗(yàn)結(jié)果分析

將TPSDE 算法與目前性能最優(yōu)、應(yīng)用范圍最廣的兩種變異策略下的差分進(jìn)化算法和我所提出算法的一種變體進(jìn)行對(duì)比實(shí)驗(yàn),分別為DE/best/1,DE/rand/1和TPSDE1,其中TPSDE1 是TPSDE 算法的變體,是鄰域向量劃分的時(shí)候,i和k的取值均為一個(gè)隨機(jī)整數(shù),即多種群的變異策略,此時(shí)i的取值范圍為[0,(NP-1)/2)∪((NP-1)/2,NP-1] 范圍內(nèi)的隨機(jī)整數(shù),k為[1,(NP-1)/2)∪((NP-1)/2,NP-2]內(nèi)隨機(jī)生成的整數(shù).選擇最小誤差、取得固定誤差值所需要的函數(shù)評(píng)價(jià)次數(shù)這兩個(gè)指標(biāo)進(jìn)行結(jié)果分析,具體如圖2所示.

從表2 可以看出,無論是簡(jiǎn)單30 維單模態(tài)Sphere函數(shù)還是多模態(tài)Rantrigin 函數(shù),無論是單峰函數(shù)還是多峰函數(shù),從優(yōu)化結(jié)果可以看出,各個(gè)算法的最優(yōu)值、最差值、平均值和標(biāo)準(zhǔn)差結(jié)果顯示,TPSDE 算法都具有的尋優(yōu)能力明顯優(yōu)于其他算法,能夠持續(xù)有效地搜索函數(shù)全局最優(yōu)點(diǎn).圖2 為每個(gè)測(cè)試函數(shù)經(jīng)過多輪迭代之后的誤差值統(tǒng)計(jì)圖.我們可以很明顯的看出,TPSDE算法幾乎在每個(gè)測(cè)試函數(shù)上相對(duì)于其他3 種差分策略的算法都表現(xiàn)出了突出的優(yōu)勢(shì).當(dāng)TPSDE 算法和各種差分策略算法都能找到函數(shù)的最優(yōu)點(diǎn)時(shí),TPSDE 算法表現(xiàn)出了較好的全局收斂性和健壯性,其前期收斂速度快,能夠在最優(yōu)極值點(diǎn)所在局部區(qū)域進(jìn)行細(xì)致搜索,能夠快速的找到最優(yōu)解所在的局部區(qū)域,收斂曲線能夠迅速地接近于最優(yōu)點(diǎn),利用較短的時(shí)間就可以接近于最小誤差值;后期能夠增加種群的多樣性,跳出局部最優(yōu)解,避免出現(xiàn)搜索停滯,從他們接近于最小誤差時(shí)的迭代次數(shù)可以看出,對(duì)于Schaffer 和Griewank 測(cè)試函數(shù)圖顯示函數(shù)收斂到大概相同誤差值時(shí),DE/best/1算法使用的迭代次數(shù)最少;Rantrigin 函數(shù)的收斂曲線圖說明在前期TPSDE1 變異策略能達(dá)到一個(gè)較好的效果,而更多的情況,比如Rosenbrock、Step 和Sphere測(cè)試函數(shù)誤差圖顯示,TPSDE 算法使用最少的評(píng)估次數(shù),可以做到快速收斂到極值點(diǎn)附近,而其他差分策略收斂速度較慢.

圖2 測(cè)試函數(shù)收斂圖

5 結(jié)論與展望

本文提出的基于雙種群兩階段變異策略的差分進(jìn)化算法,通過將全局優(yōu)化和雙種群協(xié)同進(jìn)化策略下的局部?jī)?yōu)化相結(jié)合,在以最有效的方式搜索到最優(yōu)解的同時(shí),增加了種群多樣性,防止了搜索停滯和陷入局部最優(yōu)解現(xiàn)象的出現(xiàn).以上函數(shù)仿真實(shí)驗(yàn)結(jié)果表明TPSDE算法在迭代次數(shù)明顯減少,精度得到明顯提高,以及魯棒性上都達(dá)到了更加優(yōu)秀的效果.另外,在接下來的研究中,由于差分進(jìn)化算法的通用性強(qiáng),易與其他算法相結(jié)合,諸如與人工免疫網(wǎng)絡(luò)、神經(jīng)架構(gòu)搜索等相結(jié)合,進(jìn)行模型參數(shù)優(yōu)化,相信其在提高預(yù)測(cè)精度上會(huì)有較好的效果,能夠更好地解決現(xiàn)實(shí)中的問題.