基于全局最優(yōu)和差分變異的頭腦風(fēng)暴優(yōu)化算法

馬威強(qiáng), 高永琪, 趙 苗

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

0 引 言

群體智能優(yōu)化算法通過(guò)個(gè)體間信息共享、合作、競(jìng)爭(zhēng)等一系列規(guī)則,實(shí)現(xiàn)群體走向解決方案搜索空間中越來(lái)越好的領(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)造性問(wèn)題求解過(guò)程啟發(fā)的頭腦風(fēng)暴優(yōu)化(brain storm optimization,BSO)算法可以認(rèn)為是一種很有潛力的算法。

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

1 BSO算法

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

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

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

選擇操作中的融合過(guò)程按如下表達(dá)式進(jìn)行:

=r+(1-)

(1)

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

變異操作將在待變異個(gè)體上加擾動(dòng)量,本文稱該擾動(dòng)量為變異步長(zhǎng),高斯變異按如下表達(dá)式進(jìn)行:

=+·(,)

(2)

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

(3)

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

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

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

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

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

(4)

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

=·+(1-)·

(5)

式中:為通過(guò)一個(gè)類選擇個(gè)體的概率;為選擇一個(gè)類后選擇類中心的概率;為選擇兩個(gè)類后選擇類中心融合的概率。

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

(6)

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

2.2 差分變異策略

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

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

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

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

(7)

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

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

3 仿真研究

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

表1 選取的標(biāo)準(zhǔn)測(cè)試函數(shù)

3.1 參數(shù)選擇

參考文獻(xiàn)[2]中BSO算法共同參數(shù)設(shè)置為:種群規(guī)模=100、聚類數(shù)目=5、取代操作執(zhí)行概率=02、=08、=04、=05。文獻(xiàn)[11]指出,與的選取對(duì)算法性能影響不大,取=08,=02。最大函數(shù)評(píng)估次數(shù)為=×10,為維度。取為0、0001、0005、001、005、01進(jìn)行仿真,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ù)只有一個(gè)嚴(yán)格局部極大值,較小的值能充分發(fā)揮差分變異策略的作用,種群在最優(yōu)值附近區(qū)域不斷收縮,逼近最優(yōu)值。

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

3.2 不同算法比較

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

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

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

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

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

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

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

成功率對(duì)于優(yōu)化算法來(lái)說(shuō)是非常重要的,因?yàn)槲覀儾恢缹?huì)面臨什么樣的問(wèn)題,對(duì)于不同類型的問(wèn)題,優(yōu)先考慮具有較強(qiáng)可靠性的優(yōu)化算法。從表6可見(jiàn),GDBSO和MBSO均能在大部分低維度標(biāo)準(zhǔn)測(cè)試函數(shù)的極值尋優(yōu)過(guò)程中,以100%的概率尋得可接受解。在中,各算法均無(wú)法保證100%尋得可接受解,GDBSO尋得可接受解的概率最高,為94%。因此,GDBSO求解低維問(wèn)題時(shí)具有較強(qiáng)可靠性。

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

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

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

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

圖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)用實(shí)例

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

計(jì)算機(jī)仿真平臺(tái)為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ī)劃,各獨(dú)立運(yùn)行50次。水下空間參數(shù)設(shè)置參考文獻(xiàn)[28],其中,障礙物水平面中心坐標(biāo)為(133 100,25 400),禁航區(qū)水平面中心坐標(biāo)為(133 200,25 400),AUV起點(diǎn)為(132 820,25 540,-80)、終點(diǎn)為(133 300,25 360,-80),水面艦艇布放位置為(132 950,25 440,-10),潛艇布放位置為(133 180,25 430,-130)。海流通過(guò)20個(gè)粘性Lamb渦流運(yùn)動(dòng)方程疊加而成,渦流中心位置隨機(jī)給出,渦流強(qiáng)度為8,半徑為2。

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

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

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

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

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

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

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

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

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

表9 不同算法的路徑代價(jià)比較

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

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

5 結(jié) 論

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