馬威強, 高永琪, 趙 苗

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

0 引 言

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

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

1 BSO算法

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

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

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

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

=r+(1-)

(1)

式中:是兩個個體融合后產(chǎn)生的待變異個體;與是接受融合的兩個個體;是一個0到1的隨機數(shù),調(diào)節(jié)兩個個體的權(quán)重。

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

=+·(,)

(2)

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

(3)

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

2 基于全局最優(yōu)和差分變異的BSO算法

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

2.1 追隨全局最優(yōu)策略

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

(4)

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

=·+(1-)·

(5)

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

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

(6)

式中:與是系數(shù)的邊界值。

2.2 差分變異策略

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

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

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

在人類頭腦風(fēng)暴過程中,前期每個人的想法都會有很大差異。在創(chuàng)造新觀念時,要考慮到現(xiàn)有觀念的差異。因此,本文通過差分變異來確定變異步長?；诓罘肿儺惖淖儺惒僮魅缦滤?

(7)

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

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

3 仿真研究

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

表1 選取的標準測試函數(shù)

3.1 參數(shù)選擇

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

表2 GDBSO設(shè)置不同參數(shù)在3維度下尋優(yōu)結(jié)果

表3 GDBSO設(shè)置不同參數(shù)在30維度下尋優(yōu)結(jié)果

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

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

3.2 不同算法比較

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

表4 不同算法在3維度下尋優(yōu)結(jié)果

表5 不同算法在50維度下尋優(yōu)結(jié)果

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

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

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

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

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

表6 3維度下的優(yōu)化效率與可靠性

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

表7 30維度下的優(yōu)化效率與可靠性

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

圖2 10維部分函數(shù)適應(yīng)度值變化曲線Fig.2 Variation curve of fitness value of several functions of 10 dimensions

圖3 30維部分函數(shù)適應(yīng)度值變化曲線Fig.3 Variation curve of fitness value of several functions of 30 dimensions

4 應(yīng)用實例

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

計算機仿真平臺為Matlab 2014a,處理器為Intel(R)Core(TM)i7-7700 CPU @3.60 GHZ,RAM 8GB,操作系統(tǒng)為Windows7-64位。將振蕩型IWO、GDBSO、GBSO、MBSO、BSO應(yīng)用于AUV路徑規(guī)劃,各獨立運行50次。水下空間參數(shù)設(shè)置參考文獻[28],其中,障礙物水平面中心坐標為(133 100,25 400),禁航區(qū)水平面中心坐標為(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及其改進型的參數(shù)設(shè)置參考第3節(jié)。振蕩型IWO的參數(shù)設(shè)置參考文獻[28]。算法的種群規(guī)模=30,問題維度=10。對算法終止條件的選取,本文進行了研究,先設(shè)置最大迭代次數(shù)為=200,路徑代價變化曲線如圖4所示。

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

由圖4可知,當?shù)?00次時,各算法基本求得較優(yōu)值。最大迭代次數(shù)增加使算法尋優(yōu)結(jié)果更好,但花費的時間也隨之大大增加。戰(zhàn)場情況瞬息萬變,AUV路徑規(guī)劃的實時性具有非常重要的意義。因此,設(shè)置最大迭代次數(shù)=100。

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

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

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

表8 不同算法規(guī)劃的最優(yōu)路徑比較

圖6最優(yōu)路徑局部放大圖Fig.6 Locally enlarged view of optimal path

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

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

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

表10 不同算法規(guī)劃路徑評分表

5 結(jié) 論

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