基于雙種群兩階段變異策略的差分進化算法①

王麗穎,帥真浩

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

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

1 差分策略

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

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

2 差分進化過程

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

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

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

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

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

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

圖1 TPSDE 基本流程圖

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

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

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

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

3 改進差分策略的差分進化算法

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

同時,他們適應度的大小為:

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

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

結合標準差分進化算法的框架以及雙種群兩階段的變異策略,局部與整體協同進化的思想,提出基于雙種群兩階段變異策略的差分進化算法(TPSDE),具體實現流程如下所示.

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

Step 2.第一階段局部優化.將初始化的種群進行一輪訓練,并且按照適應度從大到小排序,并在k=(NP-1)/2 處將其分成兩個子種群區域,即子種群(better)P1和子種群(worse)P2.

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

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

Step 5.將子種群P1,P2變異后產生的Vbi,g和Vwi,g加權求和產生變異子向量V1i,g.

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

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

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

Step 9.算法初始化將產生的交叉向量ui,g和目標向量xi,g根據適應度的大小進行一對一的錦標賽選擇,保留適應度更高的個體作為新的種群P′.

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

4 實驗設計與結果分析

4.1 實驗仿真

為了驗證TPSDE 算法的有效性與先進性,在實驗過程中將標準Benchmark 測試函數分別進行固定次數的仿真實驗,這里我進行30 次實驗之后進行統計,同時對于函數的選取也是極具代表性,選取的這些測試函數包括單峰函數以及多峰函數,單模態以及多模態函數,函數曲線是連續或者間斷的以及有的具有多個局部最優解而有的函數沒有局部最優解.他們的函數名稱、搜索范圍,維數以及理論上最優值如表1所示.所有函數維數取D=30,種群規模NP=50,F=0.5,CR=0.5,4 種算法獨立運行30 次后的誤差平均值與標準方差的統計結果如表2所示.

表1 測試函數及特征

表2 各算法運行30 次統計

4.2 實驗結果分析

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

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

圖2 測試函數收斂圖

5 結論與展望

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