基于全局最優和差分變異的頭腦風暴優化算法

馬威強, 高永琪, 趙 苗

(海軍工程大學兵器工程學院, 湖北 武漢 430033)

0 引 言

群體智能優化算法通過個體間信息共享、合作、競爭等一系列規則,實現群體走向解決方案搜索空間中越來越好的領域。傳統的群體智能優化算法如粒子群優化(particle swarm optimization, PSO)算法、蟻群優化(ant colony optimization, ACO)算法、野草入侵優化(invasive weeds optimization, IWO)算法等,多受到生物行為的啟發,而人是世界上最聰明的群居生物,受人類創造性問題求解過程啟發的頭腦風暴優化(brain storm optimization,BSO)算法可以認為是一種很有潛力的算法。

近年來,BSO作為一種新的群體智能優化算法,引起了眾多學者的廣泛關注,BSO及其改進型已在一些領域得到成功應用,如衛星編隊優化、直流無刷電機優化、無線傳感器網絡、Wiener模型參數辨識、圖像處理、航路規劃等等。在BSO的基礎上,國內外學者圍繞其聚類、選擇、變異等方式衍生出不同的BSO算法,提高了算法性能。Zhan等人用一種簡單的聚類方法(simple group method, SGM)代替原BSO中的K-means聚類,并用差分變異代替高斯變異,以縮短運行時間和提高尋優精度,但多次尋優結果的離散程度較大。Zhu等人提出使用k-medians算法進行聚類,避免K-means聚類中異常值所帶來的弱點,同時提高算法運算速度,但在部分多峰函數中的尋優精度不高。El-abd等人提出基于適應度的分組方法,按維度更新,并遵循全局最優思想尋優,提高了尋優精度,但收斂速度較慢。本文采用追隨全局最優策略和差分變異策略,提出了一種改進的BSO算法,以提高算法尋優精度,加快算法收斂速度。

1 BSO算法

初始種群隨機給出,其個體散亂分布在整個搜索空間。BSO通過聚類、取代、選擇、變異等操作產生新個體,優勝劣汰,從而一代代改進個體,實現全局優化,得到更優解。

聚類操作采取K-means策略,并定義每一類的最優個體為該類的類中心。聚類后,以一定概率產生隨機個體取代某一個類的類中心,防止算法過早地收斂,并有助于算法跳出局部最優。

BSO有以下4種方法選擇待變異個體:① 按照輪盤賭概率選中一個類,選擇該類的類中心為待變異個體;② 按照輪盤賭概率選中一個類,選擇該類中隨機一個個體為待變異個體;③ 隨機選中兩個類,融合兩個類的類中心成為待變異個體;④ 隨機選中兩個類,在兩個類中各隨機選出一個個體,融合成為待變異個體。

選擇操作中的融合過程按如下表達式進行:

=r+(1-)

(1)

式中:是兩個個體融合后產生的待變異個體;與是接受融合的兩個個體;是一個0到1的隨機數,調節兩個個體的權重。

變異操作將在待變異個體上加擾動量,本文稱該擾動量為變異步長,高斯變異按如下表達式進行:

=+·(,)

(2)

式中:是新個體的第維;是待變異個體的第維;(,)是以為均值、以為方差的高斯隨機數;變異系數的計算公式如下:

(3)

式中:是最大迭代次數;是當前迭代次數;是調節型傳輸函數logsig坡度的系數;rand(·)是0到1之間的隨機數。

2 基于全局最優和差分變異的BSO算法

本文采用追隨全局最優策略,在更新個體過程中充分利用全局最優信息,并用差分變異代替原來的高斯變異以自適應調節變異步長,不僅提高了尋優精度,而且加快了運算速度。

2.1 追隨全局最優策略

在PSO算法中提出的追隨全局最優策略,在許多算法中得到應用。本文將追隨全局最優策略引入BSO,原個體通過追隨全局最優個體產生新個體。BSO在選擇待變異操作個體時,有一定概率采用選擇類中心的方法,實際上就是選擇類的最優個體,可以不再考慮追隨全局最優;若不采用選擇類中心的方法,讓選擇出來的個體追隨全局最優。追隨全局最優策略如下:

(4)

式中:是全局最優個體;是一個維的向量,其每一維為0到1的隨機數;是全局最優影響系數;是通過類中心確定待變異個體的概率,可表示為

=·+(1-)·

(5)

式中:為通過一個類選擇個體的概率;為選擇一個類后選擇類中心的概率;為選擇兩個類后選擇類中心融合的概率。

進行最優個體的搜索時,搜索初期的個體隨機性較大,全局最優個體質量可能不高,追隨全局最優的意義較小,不必太大。隨著搜索的進行,個體質量整體上升,全局最優個體質量提高,追隨全局最優的意義變大,應該隨之增大。令隨迭代次數遞增,表達式如下:

(6)

式中:與是系數的邊界值。

2.2 差分變異策略

搜索初期應該進行全局搜索,到后期由于個體質量的整體上升,應重點進行局部搜索,因此算法前期變異步長應該比較大,后期變異步長比較小。BSO采取高斯變異,變異系數由logsig函數確定,變化趨勢如圖1所示。

圖1 高斯變異系數變化趨勢Fig.1 Variation trend of Gauss mutation coefficient

在算法搜索前期,變異系數比較大,后期變異系數比較小,符合前期變異步長大,后期變異步長小的需求。但一旦最大迭代次數確定,高斯變異系數變化趨勢就固定了,變異系數未考慮到種群自身情況,算法不能很好地捕捉搜索特征,而不同優化問題的搜索特征往往是不一樣的。

在人類頭腦風暴過程中,前期每個人的想法都會有很大差異。在創造新觀念時,要考慮到現有觀念的差異。因此,本文通過差分變異來確定變異步長。基于差分變異的變異操作如下所示:

(7)

式中:與是搜索空間的邊界值;表示有一定概率得到一個隨機新個體;*表示哈達馬積；與是種群中的任意兩個不同個體。

差分變異相對于高斯變異有兩方面的優勢。一方面,高斯變異的運算包括logsig函數、高斯分布函數、隨機函數和四則混合運算,而差分變異僅有隨機函數和四則混合運算,運算量大大減少。另一方面,差分變異的變異步長基于當代種群而來,根據種群個體的離散程度進行自適應調節:在種群分散時有較大的變異步長,在種群集中時有較小的變異步長。變異步長根據種群反饋情況來實時確認,算法能較好捕捉搜索特征。

3 仿真研究

利用6個標準測試函數(如表1所示),從3、10、30、50維度來研究基于全局最優和差分變異的BSO(global-best difference-mutation brain storm optimization，GDBSO)算法,這里的維度是指自變量的個數。為每個標準測試函數設置一個可接受解,其中,Griewank、Rastrigin函數的可接受解為1.00E-02,其他函數的可接受解為1.00E-10。首先研究參數設置對GDBSO性能的影響,給出參數設置建議范圍;隨后對BSO、改良BSO(modified BSO,MBSO)算法、全局最優BSO(global-best BSO,GBSO)算法與GDBSO進行仿真對比研究,檢驗分析算法性能。每一組仿真都獨立運行50次。計算機仿真平臺為Matlab 2016a,處理器為Inter(R) Core(TM)i5-6200U CPU@2.30GHZ,RAM4GB,操作系統為Windows10-64位。

表1 選取的標準測試函數

3.1 參數選擇

參考文獻[2]中BSO算法共同參數設置為:種群規模=100、聚類數目=5、取代操作執行概率=02、=08、=04、=05。文獻[11]指出,與的選取對算法性能影響不大,取=08,=02。最大函數評估次數為=×10,為維度。取為0、0001、0005、001、005、01進行仿真,3維度、30維度下的尋優結果如表2和表3所示。

表2 GDBSO設置不同參數在3維度下尋優結果

表3 GDBSO設置不同參數在30維度下尋優結果

仿真結果表明,在不同維度的單峰函數中,在[0,0.001]內取值,能讓GDBSO有更高的尋優精度。這是由于單峰函數只有一個嚴格局部極大值,較小的值能充分發揮差分變異策略的作用,種群在最優值附近區域不斷收縮,逼近最優值。

仿真結果表明,求解3維度、10維度多峰函數時,在[0,0.005]內取值,求解30維度多峰函數時,在[0.001,0.01]內取值,求解50維度多峰函數時,在[0.005,0.1]內取值,均能使GDBSO有更高的尋優精度。GDBSO求解多峰問題時,過大或過小都會降低算法尋優精度。過小值讓算法加速收斂,但易陷入局部最優,過大值幫助算法跳出局部最優,但更像隨機搜索,降低了搜索效率。找到合適的值,保證兩者的平衡是提高GDBSO算法尋優精度的關鍵。高維度的多峰問題,復雜程度高,需要更大的概率跳出局部最優,則需要更大的值。而低維度的多峰問題,復雜程度相對低,更需要注重搜索效率,則需要較小的值。

3.2 不同算法比較

參考文獻[2]設置BSO的特有參數:=20、=0、=1。文獻[9]指出,MBSO設置在[0.001,0.1]范圍內有更好的性能,再根據前文結論,MBSO、GDBSO均設置=0.005,保證算法都有較好的性能。仿真得到4種算法在4個維度下的仿真結果。3維度、50維度下仿真結果如表4和表5所示。

表4 不同算法在3維度下尋優結果

表5 不同算法在50維度下尋優結果

在不同維度的單峰函數中,GDBSO算法在尋優精度上均有極大的優勢,平均值與標準差均優于其他3種頭腦風暴算法。這是由于單峰函數只有一個嚴格局部極大值,采用追隨全局最優策略與差分變異策略使得算法在該局部極大值附近收斂,極大提高尋優精度。

各算法求解不同維度多峰函數表現各異。在3維中,GDBSO尋優結果的平均值及標準差在4種算法中表現優異;在10維中,GDBSO與MBSO尋優精度相近,在Ackley、Apline、Griewank函數中表現較好,但在Rastrigin函數中表現略差于GBSO;在30維中,各改進型算法尋優精度相似,且均高于BSO。在50維中,GDBSO僅在Apline函數上表現最佳,在其他函數中表現一般。這是因為算法轉入局部搜索后,個體更新受到全局最優的影響大,且變異系數小,使得搜索效率高,因此在更注重搜索效率的低維多峰問題中,GDBSO有更高的尋優精度,而隨著維度上升,搜索效率重要性下降,精度優勢逐漸削弱。

表6、表7給出了優化算法尋得可接受解的情況。平均迭代次數是指優化算法尋得可接受解時迭代次數的平均值,表征優化效率;成功率是指優化算法在仿真中尋得可接受解的概率,表征可靠性。表中橫桿表示算法不能尋得可接受解。

從表6、表7可見,在3維和30維中,除了Griewank函數外,GDBSO尋得其他標準測試函數的可接受解時迭代次數最少,說明其優化效率最高。這是由于差分變異策略能實時捕捉搜索特征,加之變異前追隨全局最優,能夠更高效地得到更優解。

成功率對于優化算法來說是非常重要的,因為我們不知道將會面臨什么樣的問題,對于不同類型的問題,優先考慮具有較強可靠性的優化算法。從表6可見,GDBSO和MBSO均能在大部分低維度標準測試函數的極值尋優過程中,以100%的概率尋得可接受解。在中,各算法均無法保證100%尋得可接受解,GDBSO尋得可接受解的概率最高,為94%。因此,GDBSO求解低維問題時具有較強可靠性。

表6 3維度下的優化效率與可靠性

從表7可見,問題維度上升至30時,各優化算法可靠性下降,均無法尋得的可接受解。MBSO成功率均位居榜首,可靠性最強,GDBSO成功率緊隨其后,可靠性僅稍差于MBSO。

表7 30維度下的優化效率與可靠性

仿真結果表明,在求解各維度標準測試函數時,GDBSO收斂速度最快。10維Ackley、Apline和Sphere函數以及30維Griewank、Rastrigin、Schwefel函數的適應度變化曲線,如圖2和圖3所示。算法轉入局部搜索后,變異步長小導致更新后的種群更加集中,而種群收縮使得步長變小,從而形成正反饋,加速算法收斂。加之算法在變異前還追隨當前最優個體,收斂速度更快。

圖2 10維部分函數適應度值變化曲線Fig.2 Variation curve of fitness value of several functions of 10 dimensions

圖3 30維部分函數適應度值變化曲線Fig.3 Variation curve of fitness value of several functions of 30 dimensions

4 應用實例

自主水下航行器(autonomous underwater vehicle,AUV)路徑規劃是保證其在水下安全隱蔽航行和可靠高效完成作戰任務的關鍵技術。目前智能優化算法是路徑規劃算法的研究熱點與未來重點。本文借鑒文獻[26]提出的空間環境模型與路徑規劃策略,仿真驗證GDBSO的有效性和可行性。

計算機仿真平臺為Matlab 2014a,處理器為Intel(R)Core(TM)i7-7700 CPU @3.60 GHZ,RAM 8GB,操作系統為Windows7-64位。將振蕩型IWO、GDBSO、GBSO、MBSO、BSO應用于AUV路徑規劃,各獨立運行50次。水下空間參數設置參考文獻[28],其中,障礙物水平面中心坐標為(133 100,25 400),禁航區水平面中心坐標為(133 200,25 400),AUV起點為(132 820,25 540,-80)、終點為(133 300,25 360,-80),水面艦艇布放位置為(132 950,25 440,-10),潛艇布放位置為(133 180,25 430,-130)。海流通過20個粘性Lamb渦流運動方程疊加而成,渦流中心位置隨機給出,渦流強度為8,半徑為2。

BSO及其改進型的參數設置參考第3節。振蕩型IWO的參數設置參考文獻[28]。算法的種群規模=30,問題維度=10。對算法終止條件的選取,本文進行了研究,先設置最大迭代次數為=200,路徑代價變化曲線如圖4所示。

圖4 最大迭代200次路徑代價變化曲線Fig.4 Variation curve of path cost with 200 iterations

由圖4可知,當迭代至100次時,各算法基本求得較優值。最大迭代次數增加使算法尋優結果更好,但花費的時間也隨之大大增加。戰場情況瞬息萬變,AUV路徑規劃的實時性具有非常重要的意義。因此,設置最大迭代次數=100。

仿真得到的AUV規劃路徑如圖5所示。圖5中藍色線條構成的類半球狀圖形表示武器平臺的最大探測范圍,紅色線條構成的類半球狀圖形表示武器平臺殺傷性武器的殺傷范圍,黃色圓柱體表示禁航區的范圍,青藍色圓柱體表示障礙物的影響范圍。藍色短矢線表示矢線起點的海流方向與強度。

圖5 不同算法規劃的最優路徑三維示意圖Fig.5 Three dimensional diagram of optimal path planned by different algorithms

最優路徑數據如表8所示。GDBSO算法規劃的路徑長度最長,但其航行時間最短。將最優路徑局部放大得到圖6,GDBSO與GBSO規劃出的路徑順應海流方向,利用海流推動助力AUV運動。GDBSO充分利用海流,即使路徑長度最長,也可以更快達到目的地。

表8 不同算法規劃的最優路徑比較

圖6最優路徑局部放大圖Fig.6 Locally enlarged view of optimal path

算法運行50次的統計結果如表9所示。最優值表征算法找到更優解的潛力,表現最好的是GDBSO;最差值表征算法尋優的保底程度,表現最好的是振蕩型IWO,GDBSO表現一般;平均值表征算法尋優結果的一般水平,表現最好的是GBSO,其次是GDBSO;標準差表征算法尋優結果的離散程度,表現最好的是振蕩型IWO,GDBSO表現一般。這里的平均值是指去除最大最小值后的平均值,降低極端情況對最終計算結果的影響,更好地表征樣本一般水平。

表9 不同算法的路徑代價比較

從圖4可見,5種算法規劃路徑時的收斂速度相近,因此在這里不作為算法性能評價標準。以最優值、最差值、平均值、標準差作為評價標準進行評分,得到表10。可見,GDBSO在AUV路徑規劃中有著最佳的綜合表現。

表10 不同算法規劃路徑評分表

5 結 論

本文分析了BSO算法,針對算法在選擇操作中僅部分個體更新追隨全局最優和變異操作中步長不能自適應的問題,應用了追隨全局最優策略和差分變異策略,對BSO算法進行了改進。仿真結果表明改進算法在處理單峰函數時精度極高;處理低維多峰函數時也有較好尋優能力,但隨著維數上升,尋優能力下降;求解大多數函數時都有很快的收斂速度、較高的優化效率和較強的可靠性。改進算法結合AUV路徑規劃應用的仿真驗證表明算法找到更優解的潛力較高,能充分利用海流規劃路徑,并有著最佳的綜合性能。改進算法的進一步理論分析和應用領域擴展仍是下一步的研究重點。