一種跨鄰域學習的改進粒子群優化算法

唐懿芳 鐘達夫 楊葉芬

摘要：為了改善傳統粒子群優化算法過早陷入局部最優解的缺點，進一步增強算法收斂性，通過使用一定范圍內鄰域最好位置1Best代替自身歷史最好位置pBest進行速度與位置更新，以增強粒子跨鄰域學習能力。使用整個群體中最好位置gBest進行速度與位置更新，可增強算法收斂性，且具有較好的全局搜索能力。在8個不同的單峰和多峰函數上系統地對3種算法進行測試與比較，實驗結果表明，提出的跨鄰域學習改進粒子群優化算法可避免粒子群陷入局部最優解，求解精度與算法收斂性都提升了15%以上。

關鍵詞：粒子群優化算法;跨鄰域學習;局部最優;加速收斂

DOI：10.11907/rjdk.191162

中圖分類號：TP312 文獻標識碼：A 文章編號：1672-7800（2019）012-0122-04

0引言

美國心理學家Kennedy和電氣工程師Eberhart在1995年通過模擬鳥群或魚群等群體覓食行為而提出的粒子群優化算法（Particle Swarm Optimization，PSO）是一種群體協作的隨機搜索進化算法。該算法從隨機解出發，通過捕獲當前搜尋到的最優值，不斷循環迭代尋找到全局最優解，并使用適應度函數值評價解的質量。該算法實現較為容易，已被成功應用于多個領域，尤其在各類智能優化問題方面應用廣泛。

但PSO研究中一直存在兩個待改進的問題：加速收斂與容易陷入局部最優。為解決以上問題，研究人員對算法進行改進，改進方案主要有：對慣量系數的改進、增強多樣性的改進、拓撲結構改進，以及協同其它優化算法混合改進等。這些方法對粒子群優化算法的性能都有一定提升，但截至目前，針對上述兩個問題，仍有較大改進空間。

本文所討論的改進粒子群優化算法是基于當人們行為傾向于朝同伴方向變化時，會逐步趨同，比較容易陷人局部最優解，如果其學習別的鄰域最優解，則會對容易陷人局部最優的問題有一定改善。同時算法選擇鄰域最優值學習要在一定范圍內，不能選擇較遠的領域學習，因此比目前的粒子群優化算法易于收斂。

1粒子群優化算法改進基本思想

最開始通過隨機產生一定規模的粒子作為問題搜索空間的有效解，這是粒子群優化算法的慣常步驟，然后進行迭代搜索得到優化結果。由于粒子群優化算法具有簡單易用、高效實用的特點，自提出以來，眾多研究者對其進行了探討與改進，并且在越來越多的領域得到運用。

但Trelea在2003年指出，PSO最終穩定地收斂于空間中某個點，并不能保證收斂到全局最優點，甚至不一定是局部最優，而是過早停留在一個當前最好的點上。為了提高PSO算法性能，以Eberhart&Shi為代表的研究者提出3個方向：①算法參數研究;②拓撲結構研究;③混合算法研究。

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

拓撲結構研究是指PSO有全局版本與局部版本之分，其不同之處在于更新速度時采用整個種群最優的粒子作為樣本，不同拓撲結構會影響算法局部搜索與全局搜索能力。本文重點針對拓撲結構的改進進行研究。

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

2粒子群優化算法拓撲結構改進思路

粒子群算法拓撲結構也稱為社會結構，是指算法中的個體如何進行相互作用的問題。群體中的每個個體都在相互學習，除基于自身的認知外，還在不斷地向比自己更好的鄰居移動。通過這樣的信息交流，整個群體能夠聚集到一個全局最優位置。本文針對在復雜問題中PSO表現出更好性能、更能避免陷入局部最優的特點，主要針對拓撲結構算法進行改進。

為了改進PSO過早陷入局部最優的缺點，PSO有全局版本PSO（Global Version PSO，GPSO）和局部版本PSO（Lo-cal Version PSO，LPSO）。在GPSO中，整個群體構成一個“社會”，即粒子在進行速度與位置更新時，將會使用自身的歷史最好位置pBest與整個群體中的最好位置gBest作為更新向導。在LPSO中，每個粒子所處的“社會”僅是一個小的領域，除使用自身的歷史最好位置pBest外，粒子在進行速度與位置更新時還要使用領域中的最好位置1Best作為參考。可見，LPSO版本中能夠用作更新向導的位置要比GPSO更加多樣化（因為在LPSO中每個粒子對應的1Best很可能不同，而在GPSO中的gBest都是一樣的），所以LPSO的多樣性更好，在處理復雜問題時會表現出比GPSO更優異的性能。GPSO和LPSO中的粒子更新示意圖如圖1所示。

相關研究表明，人們的信仰、態度與行為一般趨同，即人們行為會受到身處群體的影響，人們會模擬自身所在群體的典型行為。但如果一味拘泥于自己群體的最優值，比較容易陷入局部最優。為了避免固定鄰居的不足，用別的領域的最好值進行學習，可在較大程度上避免出現局部最優問題。

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

社會心理學研究也表明，當人們行為傾向于朝同伴方向變化時，其互相之間會有一個潛移默化的作用，即逐步趨同，也即容易陷入局部最優解。如果他們跳出圈子，學習別的鄰域最優解，對粒子群優化算法容易陷入局部最優的問題則會有一定改善。選擇鄰域最優值學習要在一定范圍內，不能選擇較遠領域學習，這樣不容易收斂，應選擇一定距離范圍內的鄰域，相當于遺傳算法變異過程。設定合適的變異因子，小于變異因子的適應值才能進行變異，形成多樣化的結果。

基于以上分析，本文改進算法思路是，基于增強多樣性、避免陷入局部最優的原則，在粒子更新速度和位置時，不用本領域的最優值，而用與粒子群本身領域lbest最小距離范圍內別的領域的最優值lbest'進行學習。即：

循環過程中，每隔一代就采用聚類方式，得到最近鄰域進行學習，使粒子不會過早陷入局部最優，而用全局最優gBest更新位置和速度，可保證粒子盡早趨近于全局最優。

3實驗測試與結果

3.1基準函數說明

為了驗證改進算法的有效性和高效性，本文采用8個標準測試函數進行測試。8個基準函數都是用來測試算法性能的典型函數，如表1所示。對于每個測試函數，通過進化過程中的每一次迭代對函數進行優化。

表1列出了用于實驗測試的函數，這些函數可分為兩組，前4個是單峰函數，后4個是多峰函數，其中多峰函數存在多個局部最優解。另外，在表1中還給出了測試的基因維數D（第2列）、基因數據搜索空間（第3列），以及該函數對應的全局最優值fmin（第4列）。

由于改進算法會多次調用適應值評價函數，而調用適應值評價函數對系統資源量消耗較大，因此為了公平地與其它算法進行比較，所有算法都采用最大適應值評價次數2000作為循環結束條件。同時，為了減少統計誤差，各算法在每個函數上測試30次，分別取最優值、平均值、最差值進行比較。

3.2結果比較與分析

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

在一定范圍內的鄰域學習有更精細的局部搜索能力，如果粒子與全局最優位置相距較遠，則收斂速度較慢，但本文提出的LANPSO算法仍能較快收斂。

圖5、圖6顯示在多峰函數f7和f8中出現較早收斂，使用跨領域學習方法可以增強算法多樣性，不容易過早陷人局部最優。

實驗結果表明，無論是單峰函數還是多峰函數，本文提出的LANPSO算法在收斂性和多樣性方面都得到了一定程度改善。

4結語

為了解決粒子群優化算法收斂速度慢與容易陷人局部最優的問題，本文提出一種基于跨領域學習的改進粒子群優化算法。該算法在粒子更新速度與位置時，用與粒子群本身領域lbest最小距離范圍內別的領域最優值lbest'進行學習，避免了過早陷人局部最優，在一定程度上平衡了算法的局部搜索能力與全局搜索能力。通過對8個基準函數進行測試對比，實驗結果表明，本文提出的改進算法收斂速度快、求解精度高，對大多數函數都能避免陷入局部最優，因此對粒子群優化算法性能有較大提升。下一步研究重點主要集中在如何應用LANPso算法降低無線傳感器網絡能耗方面。