基于動態(tài)搜索的自適應(yīng)貓群算法

陳超泉，王悅悅，謝曉蘭

(桂林理工大學(xué) 信息科學(xué)與工程學(xué)院，廣西 桂林 541006)

0 引 言

近幾年，貓群算法[1]的應(yīng)用領(lǐng)域越來越廣泛，搜索機制也得到了優(yōu)化。李昂等[2]在貓群算法中加入投食機制，通過加強算法局部搜索的能力進而提高算法搜索速度，但是這種方法也會加大陷入局部極值的概率。黃偉健等[3]用Logistic混沌映射在貓群算法的每次迭代中對位置進行一個擾動，使其避免陷入局部極值。趙東明等[4]提出一種多目標貓群算法，使得每只貓在迭代中都受最優(yōu)貓的牽引，增加算法收斂速度。Pandi等[5]通過在算法尋優(yōu)過程中把貓當(dāng)作一個和聲，同時進行和聲搜索的方法，增加了貓群多樣性。

以上研究雖然都一定程度上的優(yōu)化了貓群算法，但是對于貓群算法收斂的速度和求解的精度還是沒有得到針對性的改進。本文對于這種情況，提出一種改進方法，對分組率以及慣性權(quán)重進行先變速率增大后變速率減小的動態(tài)變化，使算法在不同的進化時刻有著不同的搜索重心，從而可以提高算法收斂的速度；同時針對貓群算法極易陷入局部極值的問題，本文讓算法在不同的適應(yīng)值情況下?lián)碛凶赃m應(yīng)的變異率，增加算法跳出局部極值的概率。最后通過5個標準測試函數(shù)驗證算法在收斂的速度和尋優(yōu)的精度方面都具有一定的優(yōu)勢。

1 貓群算法

貓群算法模擬正常狀態(tài)中的貓的捕獵行為。貓時刻處于一種警惕狀態(tài)，對于身邊的事物具有高度的警覺性。一般情況下，貓?zhí)幱诰锠顟B(tài)并搜索獵物，一旦發(fā)現(xiàn)合適的獵物，則對獵物進行跟蹤。貓群算法中含有兩種不同的活動模式，一種是貓在沒有獵物目標時對周邊進行巡視的一種狀態(tài)，此情況下的貓可發(fā)現(xiàn)身邊合適的獵物，這種活動狀態(tài)比擬為搜尋模式；另外一種模式是貓選定一個獵物并對其進行追蹤，這種活動狀態(tài)比擬為跟蹤模式。貓群算法結(jié)合了貓捕獵時的兩種活動狀態(tài)，用貓的兩種捕獵狀態(tài)進行建模形成的一種群智能優(yōu)化算法。

貓群算法中，貓的位置向量即待優(yōu)化問題的可行解，按照分組率(mixture ratio，MR)即執(zhí)行跟蹤模式部分占種群總體的比例[6]，將貓隨機的劃分進搜尋模式與跟蹤模式中，兩種模式的貓進行不同的屬性信息更新直至算法迭代結(jié)束。

在搜尋模式中，貓把自己的位置屬性克隆多份到記憶池中，對記憶池中的每個克隆體通過變異改變其位置向量，來產(chǎn)生新的鄰域位置，并將這些變異后的克隆體放入記憶池中作為候選位置點。計算候選位置點的適應(yīng)值，通過隨機選擇一個候選位置點來代替此位置點完成位置更新。

在跟蹤模式中，每只貓都具有一個速度屬性和一個位置屬性，其屬性更新與粒子群算法相差無幾，通過改變每一維度的屬性信息完成更新，使處于跟蹤模式中的貓持續(xù)靠近最優(yōu)貓。

1.1 搜尋模式

此模式包含了4個基本要素：記憶池(seeking memory pool，SMP)、變化域(seeking range of the selected dimension，SRD)、變化數(shù)(counts of dimension to change，CDC)、自身位置判斷(self-position considering，SCP)。具體概念如下：

SMP：用來存放此貓所能記憶的所有位置點；

SRD：指搜尋模式中變異貓每一維發(fā)生變化的范圍，此要素在算法中有著極其重要的作用，其值若取的偏大，則會導(dǎo)致算法偏于隨機搜索，甚至是純粹的隨機搜索，根據(jù)經(jīng)驗，一般取0.2；

CDC：指搜尋模式中貓的位置可以發(fā)生變異的維度個數(shù)，變化數(shù)不能大于維度D；

SCP：表示搜尋模式的貓的位置是否作為候選點，可隨機取0或1。

執(zhí)行搜尋模式的貓通過對記憶池中的候選點的位置變異實現(xiàn)位置的更新：

步驟1 判斷SCP，若此位置點是候選位置點，將自身位置復(fù)制M(M=SMP) 份到記憶池中，否則M=SMP-1；

步驟2 根據(jù)每個貓的CDC值對副本中每個個體的相應(yīng)維數(shù)進行位置變異，通過式(1)得出新位置，并代替原來的位置

(1)

其中，t表示迭代次數(shù)。

步驟3 更新記憶池中每個候選位置點的適應(yīng)值；

(2)

其中，若適應(yīng)度函數(shù)的目標是求最小值，則f*=fmax， 否則f*=fmin。

步驟5 根據(jù)選擇概率的大小使用一個最優(yōu)的候選點替換當(dāng)前貓。

1.2 跟蹤模式

跟蹤模式是對貓追蹤目標時一系列行為的建模，每只貓根據(jù)速度-位移模型對自身屬性的每一維進行相應(yīng)的更新，同時利用最優(yōu)貓的屬性信息，使得個體貓持續(xù)朝著最優(yōu)貓前進。

步驟1 根據(jù)速度更新式(3)完成速度更新

(3)

其中，rand為服從[0,1]的隨機數(shù)；c為事先取定的常數(shù)。

步驟2 檢查更新后的速度是否超出預(yù)先設(shè)定的速度區(qū)間 [Vmin,Vmax]， 如果超出區(qū)間，則根據(jù)式(4)對其進行調(diào)整

(4)

步驟3 根據(jù)式(5)更新貓的位置

(5)

2 基于動態(tài)搜索的自適應(yīng)貓群算法

自貓群算法被用在各個不同的領(lǐng)域中后，人們對于貓群算法的改進也逐漸完善，其中就不乏對分組率和慣性權(quán)重方面的改進。楊進等[7]在利用貓群算法求解TSP問題時引入交換子和變異子，同時讓分組率隨時間改變，進而達到優(yōu)化算法的目的。馬邦雄等[8]提出了隨時間變化的貓群行為模式選擇方法，在迭代過程中根據(jù)迭代次數(shù)動態(tài)改變分組率。陶亞男等[9]通過貓群算法迭代次數(shù)的更新來改變分組率，同時讓慣性權(quán)重隨著適應(yīng)值進行變化，增加了算法的自適應(yīng)性。張繼榮等[10]在前人基礎(chǔ)上加以改進，提出將慣性權(quán)重的變化速率改為一個動態(tài)變化的值，增強算法的搜索能力。

可是，以上的改進方法都只是單一的對慣性權(quán)重或者分組率進行改變，雖然也取得了一定程度的效果，但實際上，分組率和慣性權(quán)重是相輔相成的兩個部分，當(dāng)兩個參數(shù)配合得當(dāng)，算法的收斂速度才會有事半功倍的效果。而且在實驗中發(fā)現(xiàn)，貓群算法雖然有著全局尋優(yōu)的特點，但是作為一個群智能算法，貓群算法也有著很大的概率會陷入局部極值。本文針對此種現(xiàn)象，提出一種同時對分組率和慣性權(quán)重進行動態(tài)變化，并且根據(jù)算法進化狀態(tài)自適應(yīng)改變變異率的方法，使得算法能夠很好地平衡搜索重心，加大跳出局部極值的幾率，增強搜索全局最值的能力。

2.1 動態(tài)搜索

分組率MR和慣性權(quán)重ω是貓群算法中十分重要的兩個參數(shù)，能極大地影響算法的開拓和搜尋能力。分組率表征著有多大數(shù)量的貓會去進行全局搜索，而慣性權(quán)重的大小表示了貓對當(dāng)前速度保留了多少。傳統(tǒng)的貓群算法的分組率和慣性權(quán)重都是固定值，若選取的過大，則算法偏重于全局搜索，收斂速度較慢，而且不能達到一個期望的尋優(yōu)精度；若選取的過小，則算法偏重于局部搜索，容易陷入局部最優(yōu)值，無法實現(xiàn)全局尋優(yōu)。

本文在激活函數(shù)的啟發(fā)下，想到利用激活函數(shù)的特點，把迭代次數(shù)作為輸入量，同時分組率和慣性權(quán)重添加一個閾值，在激活函數(shù)的作用下，使算法在不同的進化狀態(tài)下能夠的到一個動態(tài)變化的值，以此來響應(yīng)算法，提高其收斂速度。根據(jù)函數(shù)的曲線特點，本文選用的是典型的S形函數(shù)：Logistic函數(shù)。

傳統(tǒng)的Logistic函數(shù)如式(6)所示，其特點是無論自變量取值為多少，函數(shù)值永遠局限于一個范圍內(nèi)

(6)

其中，a可以改變曲線的變化程度。

為了讓函數(shù)對算法產(chǎn)生更多積極的影響，本文在傳統(tǒng)的Logistic函數(shù)的基礎(chǔ)上進一步改變其曲線特點。改進的分組率和慣性權(quán)重需要在搜索前期表現(xiàn)出全局搜索的特點，增大發(fā)現(xiàn)更優(yōu)的極值的概率，因此在迭代前期，需要較大的分組率和較大慣性權(quán)重，這樣可以使得在全局搜索的時候，有更多的貓進入跟蹤模式，同時以較大的步長對全局范圍內(nèi)進行搜索；在搜索后期的時候，算法應(yīng)該具備局部搜索的能力，這時候應(yīng)該減少跟蹤模式的貓，增大搜尋模式的貓，同時減少慣性權(quán)重的值，使得跟蹤模式的貓能夠更好地向全局最優(yōu)貓靠近。根據(jù)需要，本文算法使用式(7) 代替式(6)

(7)

因為迭代次數(shù)也是有一個范圍存在的，故本文算法使用式(8)將迭代次數(shù)映射到Logistic函數(shù)的自變量域內(nèi)

(8)

其中，G表示最大迭代次數(shù)。

利用迭代次數(shù)在算法中動態(tài)變化，將分組率和慣性權(quán)重根據(jù)Logistic函數(shù)的曲線特點也進行一個動態(tài)變化，從而使得本文算法具有一個動態(tài)搜索的能力。分組率和慣性權(quán)重可通過式(9)和式(10)求得

(9)

(10)

為了更直觀體現(xiàn)Logistic函數(shù)改變分組率和慣性權(quán)重的特點，本文選擇與傳統(tǒng)的線性改變分組率和慣性權(quán)重方法進行畫圖對比，如圖1和圖2所示。

圖1 分組率變化對比

圖2 慣性權(quán)重變化對比

2.2 自適應(yīng)變異率

群智能算法發(fā)展至今，其陷入局部極值的特點也還是無法得到完全解決，但是不少學(xué)者也針對此問題對算法做出很多改進去進行優(yōu)化，增加算法跳出局部極值的概率?？墒?，對于貓群算法，關(guān)于變異率的改進卻是少之又少。傳統(tǒng)的貓群算法采用固定的變異率，這就導(dǎo)致算法在前期因變異率太大而影響全局搜索的進行，再后因變異率太小而無法跳出局部極值。

對于這種現(xiàn)象，本文提出采用自適應(yīng)變異率，對于搜尋模式的貓，根據(jù)算法的進化狀態(tài)來自適應(yīng)改變變異率，使其能夠以一定的概率跳出局部解。為了增強算法的自適應(yīng)性，本文算法不選用根據(jù)迭代次數(shù)進行變異率的改變，而是引入適應(yīng)度的平均值和最差值來進行判斷。對于搜索過程中的貓群，其適應(yīng)度總是處于一個不斷更新的過程，本文算法不采用即時更新即時判斷的方法，而是在每一代更新一次變異率。在算法搜索前期，算法主要進行全局搜索行為，此時的貓群位置較為松散，而貓群整體的適應(yīng)平均值也基本處于最優(yōu)貓與最差貓的中點附近，對于這種情況，應(yīng)讓搜尋模式的貓?zhí)幱诘妥儺惵实臓顟B(tài)，盡量減少影響全局搜索的行為；隨著迭代的持續(xù)，算法頁相應(yīng)地由全局搜索逐漸向局部搜索靠近，而這種情況下的貓群比較密集，雖也有少許貓?zhí)幱诘瓦m應(yīng)度的位置，但是較優(yōu)的貓占多大部分，這時貓群的適應(yīng)度平均值比較靠近最優(yōu)值，對于這種情況，可適當(dāng)加大搜尋模式的貓的變異率，使其能夠較大概率的對領(lǐng)域范圍甚至更遠一點的位置進行搜索，減少其陷入局部最優(yōu)的可能。

算法對于變異率的求解可由式(11)實現(xiàn)

(11)

其中，favg是貓群適應(yīng)度平均值；fgbest是貓群最優(yōu)值；fgworst是貓群最差值。

2.3 ADSCSO算法流程

步驟1 初始化貓群及控制參數(shù)；

步驟2 計算貓群中個體的適應(yīng)度，同時更新此時的全局最優(yōu)解；

步驟3 計算適應(yīng)值的平均值以及最差值；

步驟4 根據(jù)式(8)將迭代次數(shù)映射到Logistic函數(shù)的自變量域；

步驟5 利用x的取值根據(jù)式(9)求得分組率，人后按照分組率大小將貓群隨機分為兩部分：一部分展開搜尋，其它進行跟蹤；

步驟6 執(zhí)行搜尋模式：對于執(zhí)行搜尋模式的貓群，先根據(jù)式(11)求出這一代的變異率，然后將貓的位置復(fù)制M=SMP份進記憶池(若SPC為假，則M=SMP-1)，按照式(1)對每個副本進行位置更新，計算每個副本的適應(yīng)度值，選擇適應(yīng)度值最高的候選位置點代替此位置點；

步驟7 執(zhí)行跟蹤模式：對于執(zhí)行跟蹤模式的貓群，先利用x的取值根據(jù)式(10)求出慣性權(quán)重的值，然后根據(jù)式(3)、式(4)和式(5)分別對貓執(zhí)行速度更新、速度邊界處理和位置更新；

步驟8 重新計算貓群的適應(yīng)度值，同時更新全局最優(yōu)解；

步驟9 判斷迭代次數(shù)是否符合結(jié)束條件，若是，則立刻結(jié)束算法的進行。否則轉(zhuǎn)向步驟3繼續(xù)進行迭代。

ADSCSO算法流程如圖3所示。

3 實驗結(jié)果分析

本次實驗使用Windows10操作系統(tǒng)，Intel(R)Core(TM)i7-9750H CPU @2.60 GHz 2.59 GHz,8 GB內(nèi)存，Matlab 2018仿真軟件。為了比較充分比較CSO、DSCSO與ADSCSO求解精度和收斂速度方面的情況，本文使用5個標準測試函數(shù)進行驗證，測試函數(shù)范圍限制和算法參數(shù)設(shè)置于表1和表2分別確定。

表1 5個測試函數(shù)范圍限制

表2 CSO與ADSCSO參數(shù)設(shè)置

其中，f1是一個具有代表性的單峰函數(shù)，全局最小值處于一個非常窄小的拋物線谷中,雖然進入這個山谷很簡單，但要搜尋到最小值是很難的；f2是一個有許多局部極值的函數(shù)，其外部區(qū)域幾乎平坦，中心有一個大洞，優(yōu)化算法極容易陷入其局部值內(nèi)，導(dǎo)致算法尋優(yōu)極難。f3是低維多峰函數(shù)，其函數(shù)維度較低，但是其中包含多個極小值。f4是一個高維多峰函數(shù)，此函數(shù)本身就包含了眾多局部極值，維度的增加也使得局部極值增多，尋優(yōu)難度增大。f5是一個搜索范圍比較大的多峰函數(shù)，其中還包含了多個極小值。

3.1 求解精度分析

表3列出了CSO、DSCSO和ADSCSO算法在5個測試函數(shù)上進行實驗的結(jié)果。實驗對每個算法獨立運行20次，每次迭代2000次，每100次采集一次數(shù)據(jù)，分別記錄算法運行結(jié)果，根據(jù)算法仿真數(shù)據(jù)，計算運行20次所得到的最優(yōu)解的平均值來進行比較求解精度，同時對運行20次所得到的最優(yōu)解進行求方差運算，方差越小，說明尋到的最優(yōu)貓變化不大，算法也就越穩(wěn)定。

表3 CSO與ADSCSO算法實驗數(shù)據(jù)對比情況

如表3所示，無論低維多峰函數(shù)還是高維多峰函數(shù)，ADSCSO算法在最優(yōu)值的精度上都要高于DSCSO算法和CSO算法，在單峰函數(shù)上表現(xiàn)的更為明顯，而且同樣的情況下，DSCSO算法又比CSO算法有優(yōu)勢。

對于f1，加入動態(tài)搜索的DSCSO算法和加入動態(tài)搜索以及自適應(yīng)變異率的ADSCSO算法都要優(yōu)于CSO算法。對于多峰函數(shù)，無論是低維還是多維，甚至是搜索域的擴大，ADSCSO算法都能夠很好地尋到更優(yōu)的解，同時，ADSCSO算法在精度上也都高于DSCSO算法，這說明自適應(yīng)變異率增強跳出局部極值的可行性。

3.2 收斂速度分析

圖4至圖8分別展示了CSO算法、DSCSO算法和ADSCSO 算法在5個不同的函數(shù)測試下的適應(yīng)值進化曲線情況。本文選取迭代次數(shù)為橫坐標軸，函數(shù)值即適應(yīng)值為縱坐標軸，且適應(yīng)值使用的是獨立運行20次得到的結(jié)果的平均值。為了能清晰展現(xiàn)出3個算法的比較情況，本文使用函數(shù)值的對數(shù)作為表示，并于圖像中展示出來。

如圖4所示，3個算法的初始搜索值類似，但是ADSCSO 算法全程以較穩(wěn)定的收斂速度持續(xù)探索最優(yōu)解，收斂速度要高于DSCSO算法和CSO算法，而同樣的情況下，DSCSO算法又優(yōu)于CSO算法。對于多個局部極小值的函數(shù)，如圖5和圖8所示，ADSCSO算法也展現(xiàn)了其在收斂速度方面的優(yōu)勢。對于f2這種特殊形狀的函數(shù)，進化曲線如圖4所示，前期低變異率能夠讓算法進行全面的全局搜索，雖然稍微降低了前期的收斂速度，但是后期隨著變異率的增強，局部搜索能力的增加，ADSCSO算法以較快的收斂速度收斂至比DSCSO算法還要優(yōu)的解。對于常規(guī)的多維函數(shù)的進化曲線，如圖6至圖8所示，無論低維還是高維，DSCSO算法雖然收斂速度上超過CSO算法，但在搜索后期，還是極容易陷入局部極值。而ADSCSO算法都能在全局搜索過后，以較快的收斂速度尋到較優(yōu)解，整體形勢都要優(yōu)于DSCSO算法和CSO算法，這也驗證了ADSCSO 算法在收斂速度方面的有效性。

圖4 Zakharov函數(shù)的適應(yīng)值進化曲線

圖5 Ackley函數(shù)的適應(yīng)值進化曲線

圖6 Schaffer N.2函數(shù)的適應(yīng)值進化曲線

圖7 Rastrigin函數(shù)的適應(yīng)值進化曲線

圖8 Griewank函數(shù)的適應(yīng)值進化曲線

4 結(jié)束語

本文針對貓群算法在搜索過程中極易陷入局部最優(yōu)和收斂速度較慢的問題，提出一種基于動態(tài)搜索的自適應(yīng)貓群算法。該算法利用Logistic函數(shù)曲線呈“S”形的特點，使其來根據(jù)迭代次數(shù)對分組率和慣性權(quán)重進行動態(tài)變化，讓算法在不同的時期有著不同的搜索重心，加快算法的收斂速度；同時根據(jù)算法進化狀態(tài)，對變異率進行一個自適應(yīng)的調(diào)整，增強算法跳出局部極值的能力。

本文使用5個經(jīng)典測試函數(shù)對ADSCSO算法、DSCSO算法和CSO算法進行一個對比實驗，實驗結(jié)果表明ADSCSO算法無論是在求解精度還是收斂速度都優(yōu)于其它兩種算法，從而驗證了ADSCSO算法在全局優(yōu)化問題方面的可行性。