一種跨鄰域?qū)W習(xí)的改進(jìn)粒子群優(yōu)化算法

唐懿芳 鐘達(dá)夫 楊葉芬

摘要：為了改善傳統(tǒng)粒子群優(yōu)化算法過早陷入局部最優(yōu)解的缺點(diǎn)，進(jìn)一步增強(qiáng)算法收斂性，通過使用一定范圍內(nèi)鄰域最好位置1Best代替自身歷史最好位置pBest進(jìn)行速度與位置更新，以增強(qiáng)粒子跨鄰域?qū)W習(xí)能力。使用整個(gè)群體中最好位置gBest進(jìn)行速度與位置更新，可增強(qiáng)算法收斂性，且具有較好的全局搜索能力。在8個(gè)不同的單峰和多峰函數(shù)上系統(tǒng)地對(duì)3種算法進(jìn)行測(cè)試與比較，實(shí)驗(yàn)結(jié)果表明，提出的跨鄰域?qū)W習(xí)改進(jìn)粒子群優(yōu)化算法可避免粒子群陷入局部最優(yōu)解，求解精度與算法收斂性都提升了15%以上。

關(guān)鍵詞：粒子群優(yōu)化算法;跨鄰域?qū)W習(xí);局部最優(yōu);加速收斂

DOI：10.11907/rjdk.191162

中圖分類號(hào)：TP312 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2019）012-0122-04

0引言

美國(guó)心理學(xué)家Kennedy和電氣工程師Eberhart在1995年通過模擬鳥群或魚群等群體覓食行為而提出的粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）是一種群體協(xié)作的隨機(jī)搜索進(jìn)化算法。該算法從隨機(jī)解出發(fā)，通過捕獲當(dāng)前搜尋到的最優(yōu)值，不斷循環(huán)迭代尋找到全局最優(yōu)解，并使用適應(yīng)度函數(shù)值評(píng)價(jià)解的質(zhì)量。該算法實(shí)現(xiàn)較為容易，已被成功應(yīng)用于多個(gè)領(lǐng)域，尤其在各類智能優(yōu)化問題方面應(yīng)用廣泛。

但PSO研究中一直存在兩個(gè)待改進(jìn)的問題：加速收斂與容易陷入局部最優(yōu)。為解決以上問題，研究人員對(duì)算法進(jìn)行改進(jìn)，改進(jìn)方案主要有：對(duì)慣量系數(shù)的改進(jìn)、增強(qiáng)多樣性的改進(jìn)、拓?fù)浣Y(jié)構(gòu)改進(jìn)，以及協(xié)同其它優(yōu)化算法混合改進(jìn)等。這些方法對(duì)粒子群優(yōu)化算法的性能都有一定提升，但截至目前，針對(duì)上述兩個(gè)問題，仍有較大改進(jìn)空間。

本文所討論的改進(jìn)粒子群優(yōu)化算法是基于當(dāng)人們行為傾向于朝同伴方向變化時(shí)，會(huì)逐步趨同，比較容易陷人局部最優(yōu)解，如果其學(xué)習(xí)別的鄰域最優(yōu)解，則會(huì)對(duì)容易陷人局部最優(yōu)的問題有一定改善。同時(shí)算法選擇鄰域最優(yōu)值學(xué)習(xí)要在一定范圍內(nèi)，不能選擇較遠(yuǎn)的領(lǐng)域?qū)W習(xí)，因此比目前的粒子群優(yōu)化算法易于收斂。

1粒子群優(yōu)化算法改進(jìn)基本思想

最開始通過隨機(jī)產(chǎn)生一定規(guī)模的粒子作為問題搜索空間的有效解，這是粒子群優(yōu)化算法的慣常步驟，然后進(jìn)行迭代搜索得到優(yōu)化結(jié)果。由于粒子群優(yōu)化算法具有簡(jiǎn)單易用、高效實(shí)用的特點(diǎn)，自提出以來(lái)，眾多研究者對(duì)其進(jìn)行了探討與改進(jìn)，并且在越來(lái)越多的領(lǐng)域得到運(yùn)用。

但Trelea在2003年指出，PSO最終穩(wěn)定地收斂于空間中某個(gè)點(diǎn)，并不能保證收斂到全局最優(yōu)點(diǎn)，甚至不一定是局部最優(yōu)，而是過早停留在一個(gè)當(dāng)前最好的點(diǎn)上。為了提高PSO算法性能，以Eberhart&Shi為代表的研究者提出3個(gè)方向：①算法參數(shù)研究;②拓?fù)浣Y(jié)構(gòu)研究;③混合算法研究。

算法參數(shù)研究是指PSO具有慣量權(quán)重ω、加速系數(shù)c1與c2、最大速度、種群規(guī)模等參數(shù)，參數(shù)分析試圖通過研究這些參數(shù)對(duì)算法全局搜索能力與局部搜素能力的影響，找到更好的參數(shù)配置或自適應(yīng)調(diào)整方案，提高算法性能。

拓?fù)浣Y(jié)構(gòu)研究是指PSO有全局版本與局部版本之分，其不同之處在于更新速度時(shí)采用整個(gè)種群最優(yōu)的粒子作為樣本，不同拓?fù)浣Y(jié)構(gòu)會(huì)影響算法局部搜索與全局搜索能力。本文重點(diǎn)針對(duì)拓?fù)浣Y(jié)構(gòu)的改進(jìn)進(jìn)行研究。

混合算法研究是指基于PSO自身收斂速度快，但容易陷人局部最優(yōu)的特點(diǎn)，混合算法引入進(jìn)化算法中的相關(guān)算子，例如選擇、交叉、變異等算子，或者其它增加算法多樣性的技術(shù)，以提高算法性能。

2粒子群優(yōu)化算法拓?fù)浣Y(jié)構(gòu)改進(jìn)思路

粒子群算法拓?fù)浣Y(jié)構(gòu)也稱為社會(huì)結(jié)構(gòu)，是指算法中的個(gè)體如何進(jìn)行相互作用的問題。群體中的每個(gè)個(gè)體都在相互學(xué)習(xí)，除基于自身的認(rèn)知外，還在不斷地向比自己更好的鄰居移動(dòng)。通過這樣的信息交流，整個(gè)群體能夠聚集到一個(gè)全局最優(yōu)位置。本文針對(duì)在復(fù)雜問題中PSO表現(xiàn)出更好性能、更能避免陷入局部最優(yōu)的特點(diǎn)，主要針對(duì)拓?fù)浣Y(jié)構(gòu)算法進(jìn)行改進(jìn)。

為了改進(jìn)PSO過早陷入局部最優(yōu)的缺點(diǎn)，PSO有全局版本PSO（Global Version PSO，GPSO）和局部版本PSO（Lo-cal Version PSO，LPSO）。在GPSO中，整個(gè)群體構(gòu)成一個(gè)“社會(huì)”，即粒子在進(jìn)行速度與位置更新時(shí)，將會(huì)使用自身的歷史最好位置pBest與整個(gè)群體中的最好位置gBest作為更新向?qū)?。在LPSO中，每個(gè)粒子所處的“社會(huì)”僅是一個(gè)小的領(lǐng)域，除使用自身的歷史最好位置pBest外，粒子在進(jìn)行速度與位置更新時(shí)還要使用領(lǐng)域中的最好位置1Best作為參考。可見，LPSO版本中能夠用作更新向?qū)У奈恢靡菺PSO更加多樣化（因?yàn)樵贚PSO中每個(gè)粒子對(duì)應(yīng)的1Best很可能不同，而在GPSO中的gBest都是一樣的），所以LPSO的多樣性更好，在處理復(fù)雜問題時(shí)會(huì)表現(xiàn)出比GPSO更優(yōu)異的性能。GPSO和LPSO中的粒子更新示意圖如圖1所示。

相關(guān)研究表明，人們的信仰、態(tài)度與行為一般趨同，即人們行為會(huì)受到身處群體的影響，人們會(huì)模擬自身所在群體的典型行為。但如果一味拘泥于自己群體的最優(yōu)值，比較容易陷入局部最優(yōu)。為了避免固定鄰居的不足，用別的領(lǐng)域的最好值進(jìn)行學(xué)習(xí)，可在較大程度上避免出現(xiàn)局部最優(yōu)問題。

文獻(xiàn)[17]使用簇分析改進(jìn)算法性能，具體實(shí)現(xiàn)過程為：首先將整個(gè)粒子群劃分為幾個(gè)簇，確定簇中心，然后用個(gè)體i的簇中心CLUSI代替pBest，或用目前找到的最優(yōu)個(gè)體g的簇中心CLUSG代替gBest，用于進(jìn)行粒子速度和位置更新。其采用帶收斂因子的粒子群優(yōu)化算法進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明，用CLUSI代替pBest可顯著改善算法性能，用CLISG代替gBest則會(huì)降低算法性能，這也顯示了增加算法多樣性效果的兩面性。

社會(huì)心理學(xué)研究也表明，當(dāng)人們行為傾向于朝同伴方向變化時(shí)，其互相之間會(huì)有一個(gè)潛移默化的作用，即逐步趨同，也即容易陷入局部最優(yōu)解。如果他們跳出圈子，學(xué)習(xí)別的鄰域最優(yōu)解，對(duì)粒子群優(yōu)化算法容易陷入局部最優(yōu)的問題則會(huì)有一定改善。選擇鄰域最優(yōu)值學(xué)習(xí)要在一定范圍內(nèi)，不能選擇較遠(yuǎn)領(lǐng)域?qū)W習(xí)，這樣不容易收斂，應(yīng)選擇一定距離范圍內(nèi)的鄰域，相當(dāng)于遺傳算法變異過程。設(shè)定合適的變異因子，小于變異因子的適應(yīng)值才能進(jìn)行變異，形成多樣化的結(jié)果。

基于以上分析，本文改進(jìn)算法思路是，基于增強(qiáng)多樣性、避免陷入局部最優(yōu)的原則，在粒子更新速度和位置時(shí)，不用本領(lǐng)域的最優(yōu)值，而用與粒子群本身領(lǐng)域lbest最小距離范圍內(nèi)別的領(lǐng)域的最優(yōu)值lbest'進(jìn)行學(xué)習(xí)。即：

循環(huán)過程中，每隔一代就采用聚類方式，得到最近鄰域進(jìn)行學(xué)習(xí)，使粒子不會(huì)過早陷入局部最優(yōu)，而用全局最優(yōu)gBest更新位置和速度，可保證粒子盡早趨近于全局最優(yōu)。

3實(shí)驗(yàn)測(cè)試與結(jié)果

3.1基準(zhǔn)函數(shù)說(shuō)明

為了驗(yàn)證改進(jìn)算法的有效性和高效性，本文采用8個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)進(jìn)行測(cè)試。8個(gè)基準(zhǔn)函數(shù)都是用來(lái)測(cè)試算法性能的典型函數(shù)，如表1所示。對(duì)于每個(gè)測(cè)試函數(shù)，通過進(jìn)化過程中的每一次迭代對(duì)函數(shù)進(jìn)行優(yōu)化。

表1列出了用于實(shí)驗(yàn)測(cè)試的函數(shù)，這些函數(shù)可分為兩組，前4個(gè)是單峰函數(shù)，后4個(gè)是多峰函數(shù)，其中多峰函數(shù)存在多個(gè)局部最優(yōu)解。另外，在表1中還給出了測(cè)試的基因維數(shù)D（第2列）、基因數(shù)據(jù)搜索空間（第3列），以及該函數(shù)對(duì)應(yīng)的全局最優(yōu)值fmin（第4列）。

由于改進(jìn)算法會(huì)多次調(diào)用適應(yīng)值評(píng)價(jià)函數(shù)，而調(diào)用適應(yīng)值評(píng)價(jià)函數(shù)對(duì)系統(tǒng)資源量消耗較大，因此為了公平地與其它算法進(jìn)行比較，所有算法都采用最大適應(yīng)值評(píng)價(jià)次數(shù)2000作為循環(huán)結(jié)束條件。同時(shí)，為了減少統(tǒng)計(jì)誤差，各算法在每個(gè)函數(shù)上測(cè)試30次，分別取最優(yōu)值、平均值、最差值進(jìn)行比較。

3.2結(jié)果比較與分析

實(shí)驗(yàn)結(jié)果采用經(jīng)典的PSO算法、Lin提出的分層改進(jìn)粒子群優(yōu)化算法HSPPSO（A Hierarchical StructurePoly-Particle Swarm Optimization）與本文提出的LANPSO算法作比較。3種算法在單峰函數(shù)f1和f4的比較結(jié)果如圖3、圖4所示，在多峰函數(shù)f7和f8的比較結(jié)果如圖5、圖6所示。

在一定范圍內(nèi)的鄰域?qū)W習(xí)有更精細(xì)的局部搜索能力，如果粒子與全局最優(yōu)位置相距較遠(yuǎn)，則收斂速度較慢，但本文提出的LANPSO算法仍能較快收斂。

圖5、圖6顯示在多峰函數(shù)f7和f8中出現(xiàn)較早收斂，使用跨領(lǐng)域?qū)W習(xí)方法可以增強(qiáng)算法多樣性，不容易過早陷人局部最優(yōu)。

實(shí)驗(yàn)結(jié)果表明，無(wú)論是單峰函數(shù)還是多峰函數(shù)，本文提出的LANPSO算法在收斂性和多樣性方面都得到了一定程度改善。

4結(jié)語(yǔ)

為了解決粒子群優(yōu)化算法收斂速度慢與容易陷人局部最優(yōu)的問題，本文提出一種基于跨領(lǐng)域?qū)W習(xí)的改進(jìn)粒子群優(yōu)化算法。該算法在粒子更新速度與位置時(shí)，用與粒子群本身領(lǐng)域lbest最小距離范圍內(nèi)別的領(lǐng)域最優(yōu)值lbest'進(jìn)行學(xué)習(xí)，避免了過早陷人局部最優(yōu)，在一定程度上平衡了算法的局部搜索能力與全局搜索能力。通過對(duì)8個(gè)基準(zhǔn)函數(shù)進(jìn)行測(cè)試對(duì)比，實(shí)驗(yàn)結(jié)果表明，本文提出的改進(jìn)算法收斂速度快、求解精度高，對(duì)大多數(shù)函數(shù)都能避免陷入局部最優(yōu)，因此對(duì)粒子群優(yōu)化算法性能有較大提升。下一步研究重點(diǎn)主要集中在如何應(yīng)用LANPso算法降低無(wú)線傳感器網(wǎng)絡(luò)能耗方面。