基于競爭侵略策略的粒子群算法

安 寧，張 軍，季偉東

（哈爾濱師范大學 計算機科學與信息工程學院，哈爾濱 150025）

0 引 言

群體智能是模擬自然界生物群體行為而構造的隨機優化算法，它為解決約束性、非線性和求極值等問題提供了新的思路。遺傳算法［1］、蟻群算法［2］與粒子群優化（Particle Swarm Optimization，PSO）算法［3］是群體智能中重要的3種方法。其中PSO算法概念簡明、易于實現、參數設置少，是一種高效的搜索算法。但在算法迭代后期，粒子群算法容易陷入局部最優且收斂速度較慢。為了提高算法性能，涌現出不同思想的優化策略。在基本粒子群算法進化方程的改進方面，Shi Y［4］在慣性權重的基礎上，提出模糊系統動態調整慣性權重策略；Taherkhani M［5］等根據每個粒子與最優位置的距離和粒子性能，賦予每個粒子在不同維度上的慣性權重，實現了慣性權重的動態調整。慣性權重的調整可以平衡算法全局搜索與局部搜索能力，但對于提升算法后期，收斂速度仍有欠缺。胡旺［6］等將簡化粒子速度更新策略應用于一種更簡化而高效的粒子群優化算法。該算法刪除粒子速度項，將二階微分方程簡化為一階微分方程，大幅度的減少了算法的運行時間。同樣，在改變速度更新策略方面，El-Sherbiny［7］提出無速度方程的粒子群優化算法。該算法中每個粒子的新位置直接由個體與群體最佳位置的不同線性組合來確定，用較少的迭代次數尋到較優的解。在借鑒其它優化策略方面，Clerc［8］等為保證算法的收斂效果，在粒子群算法中引入收縮因子，但收縮因子能力有限，不能較好的平衡全局搜索和局部搜索。為了解決該問題，Wang F［9］等將自適應學習策略應用到粒子群算法中，提出自主學習的候選生成策略與競爭學習的預測策略，同時制定了一種自適應的尋優方向調整機制，更好的平衡全局搜索能力和局部搜索能力。該算法中競爭學習的預測策略提供了一種粒子間競爭學習的思路。隨著多種群策略的提出，衍生出大量多種群協同尋優的改進算法。2018年，鄧先禮［10］等在多種群同步進化的基礎上，賦予子種群不同的搜索特性，利用各子種群性能的周期性評價指導個體進行遷移，實現種群間的合作；Niu B［11］在種群合作的基礎上，提出種群內部和種群之間兩種社會活動，在進化過程中粒子不僅與自身種群的其他粒子交換社會經驗，而且還受到其他種群粒子經驗的影響，該策略增強了粒子的學習能力。文獻［12］將反向學習策略與局部學習策略結合，當算法陷入局部最優時，利用較差粒子的位置信息指導部分粒子以較快的飛行速度進行反向學習，跳出局部最優；羅強［13］等將反向學習策略與最優粒子策略結合，利用全局最優粒子進行反向學習，通過全局最優粒子的更新引領粒子向更好的位置飛行，加強算法多樣性的同時擁有較高的收斂速度。為提高算法的收斂速度與擺脫局部最優的能力，各種算法提出了不同的改進策略，文獻中的算法在提高算法收斂速度或擺脫局部最優狀態過程中，都存在一方面的效果比較顯著，但在另一方面表現稍差的現象。

本文提出一種基于競爭侵略策略的粒子群算法（CAPSO）。受最優粒子策略與競爭學習策略啟發，將種群分類、最優粒子與競爭學習思想應用于算法中，定義了侵略性自由粒子和競爭池兩個概念。侵略性自由粒子與競爭池挑選競爭最優粒子，利用競爭最優粒子簡化傳統速度公式并指導擇優進化群更新。為驗證CAPSO算法在提高算法收斂速度與擺脫局部最優能力方面的性能，將其與4種經典算法（RLPSO［12］算法、TDDALFPSO［14］算法、ScDCPS算法［15］、IPSO算法［16］，）進行對比。其中，RLPSO算法在最優粒子與競爭學習方面進行改進；TDDALFPSO算法在自適應學習方面進行改進；ScDCPS算法在種群分類與種群控制方面進行改進；IPSO算法在粒子學習機制上采用了競爭策略，與CAPSO算法形成多方面的對比。在8個標準測試函數下進行仿真實驗，結果表明CAPSO算法具有較快的收斂速度和較高的求解精度。

1 基于競爭侵略策略的粒子群算法（CAPSO）

CAPSO算法將種群劃分為規模相同的二部分：一部分為侵略性自由粒子群，另一部分為擇優進化群。二部分粒子遵循不同的更新規則，侵略性自由粒子群遵循高自由度參數更新原則，擇優進化群遵循改進速度公式進行更新。在CAPSO算法的每次迭代過程中，侵略性自由粒子群中隨機選擇一個粒子與擇優進化群進行一次適應度值競爭，獲勝的粒子作為競爭最優（Cbest）存入競爭池中，并利用該粒子指導擇優進化群進行下一次迭代。此策略增強了算法擺脫局部最優的能力，且算法的收斂速度有較大提高。近年來也涌現出很多結合競爭策略的粒子群優化算法。如2015年，Cheng R［17］提出的大規模優化的競爭群優化算法，在所有粒子中隨機挑選兩個粒子成對進行競爭學習，失敗的粒子直接向獲勝的粒子進行學習，在粒子更新的過程中個體最優與全局最優不參與更新過程；2019年，劉明［18］等將競爭策略與周期性結合，即每隔一定迭代次數運用一次競爭學習機制，競爭機制的原理與Cheng R提出的競爭原理相似，同樣是競爭失敗的粒子向獲勝的粒子學習。上述二種算法中均省去了歷史位置的記錄，算法中個體最優與全局最優歷史位置仍存在，但不參與算法迭代。本文提出的CAPSO算法中，已經完全摒棄了個體最優與全局最優的概念，利用競爭最優粒子直接指導擇優進化群更新。在競爭策略方面，CAPSO算法將所有粒子分為不同更新規則的二個種群，與上述二種算法競爭策略的不同之處為：

（1）CAPSO算法為二個不同種群間的粒子競爭，而不是同種群內相同更新規則的粒子間競爭。

（2）獲勝的粒子定義為競爭最優，指導擇優進化群的更新，而不是指導失敗粒子進行更新。

1.1 競爭池

競爭池存儲競爭最優（Cbest）粒子的位置信息，空間大小為N／2。競爭最優指每一代更新過程中，侵略性自由粒子與擇優進化群中的粒子進行適應度值的競爭，獲勝的粒子定義為競爭最優，并將位置信息保存在競爭池中。競爭最優存入競爭池后，擇優進化群的下一代更新需在競爭池中取出當代競爭最優的位置信息，來指導擇優進化群進行下一次更新。位置信息取出后，競爭池中仍保存每代競爭最優的位置信息。為保證擇優進化群第一次更新，初始所有粒子后，選擇適應度值最優的粒子作為第一個競爭最優并存入競爭池。由于競爭最優的選擇機制，保證了競爭最優的粒子信息為每一代全部粒子的最優信息。競爭池的存在為改進速度公式打下基礎，將傳統的粒子群算法中的個體最優和全局最優用競爭最優替代，以達到簡化傳統速度公式的目的。圖1及圖2為競爭最優的選擇與指導擇優進化群的二維示意圖。

圖中：U是解空間；三角形和圓形分別代表侵略性自由粒子和擇優進化群中的粒子；Cbest是競爭最優；五角星是需要尋找的理論解。

圖1中，侵略性自由粒子距離理論解較近，代表適應度值更優，故侵略性自由粒子作為競爭最優并存入競爭池中。相反，若擇優進化群的粒子距離理論解較近，則擇優進化群的粒子作為競爭最優并存入競爭池中；圖2中，①為在競爭池中取出競爭最優的位置信息，②為競爭最優指導擇優進化群更新。

圖1 競爭最優入池示意圖Fig.1 Schematic diagram of competition for optimal entry into the pool

圖2 競爭最優出池示意圖Fig.2 Schematic diagram of competitive optimal pool

1.2 侵略性自由粒子

初始設定N個粒子，當N為偶數，即選取N／2個粒子作為侵略性自由粒子；當N為奇數時，隨機選取一個粒子，定義該粒子即是侵略性自由粒子，也是擇優進化群中的粒子。此策略可保證侵略性自由粒子與擇優進化群的規模保持一致。侵略性自由粒子具備高自由度和侵略性。

1.2.1 高自由度

本文設置為D維，粒子初始賦予位置信息。大部分隨機優化算法（包括粒子群算法和遺傳算法等）對于粒子的更新多數是D維，采用相同的參數更新。本文侵略性自由粒子，在粒子所具有D維的基礎上，各維逐一與相對應的高自由度參數進行更新。以此更新策略為前提，為保證侵略性自由粒子的每次更新不超出預設邊界，高自由度參數設置為［-1，1］之間的隨機數，由此改變粒子位置，該策略增強了算法的多樣性。更新過程如圖3所示：（其中：Xi為各維的位置信息，Ri是隨著Xi逐一生成的高自由度參數，1≤i≤D。）

圖3 侵略性自由粒子更新示意圖Fig.3 Update diagram of aggressive free particles

1.2.2 侵略性

自由粒子的侵略性體現在粒子群的優化更新過程中。當擇優進化群的粒子在適應度值競爭中獲勝作為競爭最優時，侵略性未被激活，擇優進化群按原有軌跡進行更新；當侵略性自由粒子在適應度值競爭中獲勝作為競爭最優時，激活侵略性。此時侵略性自由粒子以改進速度公式作為載體，參與擇優進化群的更新過程，指導擇優進化群向侵略性自由粒子的位置信息進行學習，使擇優進化群擺脫原有更新軌跡。該策略增強了算法擺脫局部最優的能力。

1.3 改進速度公式

傳統粒子群算法（PSO）的速度更新公式中，存在個體最優與全局最優兩個概念。本文提出的算法憑借競爭最優（Cbest）的選擇機制，摒棄個體最優與全局最優，將原有的兩個外部存檔，優化為僅對競爭最優進行外部存檔，降低了算法的空間復雜度。算法在粒子速度更新時，僅向競爭最優進行學習，提高粒子的學習精度。對比傳統速度公式，改進后的速度公式提高了算法的運算速度，將算法效率進一步提升。速度公式如式（1）所示。

2 實驗結果分析

通過對8個典型標準函數的測試，對比CAPSO算法和其它改進算法的性能。其中f1～f4為單峰函數；f5～f8為多峰函數，具體函數見表1。

表1 標準測試函數Tab.1 Standard test functions

參數設置：維數D=30、種群規模N=50、最大迭代次數為1 000、c=2、r為［0，1］之間的隨機數、ω最大值為0.9、最小值為0.4；每個算法計算10次，最優解取平均值。

通過Matlab仿真，得到不同算法在8個標準測試函數的收斂曲線如圖4、圖5，各算法測試結果見表2。

圖5 不同算法在4個多峰標準測試函數的收斂曲線Fig.5 Convergence curves of different algorithms on four multi-peak standard test functions

表2 不同算法在8個標準測試函數中的結果Tab.2 Results of different algorithms in 8 standard test functions

圖4 不同算法在4個單峰標準測試函數的收斂曲線Fig.4 Convergence curves of different algorithms on four unimodal standard test functions

函數f1、f2是簡單的單峰測試函數，CAPSO算法可以直接尋優。函數f1進化次數為420次尋優，函數f2進化次數為800次尋優。在圖像f1與圖像f2中，CAPSO對比其余五種算法，在收斂速度與收斂精度方面，性能大幅提升，造成圖像重疊；而在表2中可以看出，RLPSO算法與TDDALFPSO算法在精度上優于PSO與ScDCPS算法。結合f1與f2圖像可知，競爭池機制發揮了重要作用，保證算法的每次更新都向最優的粒子學習，算法尋優精度提升明顯；函數f3和f4稍復雜，CAPSO算法未尋到最優值，相對比其它算法收斂精度較高。在f3圖像中可以看出CAPSO算法與TDDALFPSO算法在收斂精度上幾乎一致，但CAPSO算法的收斂速度更快；在f4圖像中，收斂精度最高的是RLPSO算法，但CAPSO算法的收斂速度更快，彌補了收斂精度稍差的劣勢。結合f3圖像和f4圖像，通過ScDCPS算法與PSO算法對比，可以得出ScDCPS算法犧牲收斂速度來提高收斂精度，在此基礎上收斂精度仍不如RLPSO算法。通過4個單峰測試函數可得到，CAPSO算法對比其他改進算法收斂速度更快，收斂精度較高。CAPSO算法在單峰函數求解問題上性能較優。

函數f5～函數f8為較復雜的多峰函數，在f5～f8的4張圖像中，可直觀的觀察到CAPSO算法無論在收斂速度上，還是收斂精度上都保持最優，而在函數f6和函數f7，CAPSO算法可以直接尋優。函數f6進化次數為32次尋優，函數f7進化次數為32次尋優。在函數f5的測試結果中，CAPSO算法最優，PSO算法、RLPSO算法與ScDCPS算法在收斂速度和精度上相差較小，TDDALFPSO算法略優，但對比CAPSO算法存在較大差距。在函數f8的測試結果中，CAPSO算法同樣優于其它算法，雖然有短暫陷入局部最優的情況，但侵略性自由粒子憑借自身高自由度的特性，迅速令算法擺脫局部最優的情況，并且在1 000次進化后，仍有下降的趨勢。TDDALFPSO算法優于RLPSO算法，ScDCPS算法略優于PSO算法。CAPSO算法在多峰函數求解問題上，性能同樣較優。

由上述對比可知，經過改進的CAPSO算法，無論在單峰函數問題還是多峰函數問題，總體性能相比較PSO算法以及其他思想改進方式的RLPSO算法、TDDALFPSO算法、ScDCPS算法和IPSO算法，有較大的提升。與IPSO算法的對比可以得出，經本文優化后的競爭侵略策略對比IPSO算法的競爭策略性能更優，種群間的粒子競爭機制發揮著重要作用。從表2的數據方差中也可看出，在多數測試函數中CAPSO算法的方差值較小，算法穩定性較高。

3 結束語

本文結合多種改進策略，提出基于競爭侵略策略的粒子群算法（CAPSO），該算法利用侵略性自由粒子的高自由度特性結合競爭池概念，大幅度的提升了算法的性能。CAPSO算法在避免陷入局部最優和提高收斂速度的問題上表現出較強的能力，通過競爭最優（Cbest）的選擇機制，摒棄個體最優與全局最優，達到簡化速度公式的目的，令算法進化過程中更新速度更快，學習效率更高，在單峰函數和多峰函數中都具有優秀的收斂速度和收斂精度，且算法穩定，證明CAPSO算法的機制可以解決多種優化問題。