安 寧，張 軍，季偉東

（哈爾濱師范大學(xué) 計(jì)算機(jī)科學(xué)與信息工程學(xué)院，哈爾濱 150025）

0 引 言

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

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

1 基于競(jìng)爭(zhēng)侵略策略的粒子群算法（CAPSO）

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

（1）CAPSO算法為二個(gè)不同種群間的粒子競(jìng)爭(zhēng)，而不是同種群內(nèi)相同更新規(guī)則的粒子間競(jìng)爭(zhēng)。

（2）獲勝的粒子定義為競(jìng)爭(zhēng)最優(yōu)，指導(dǎo)擇優(yōu)進(jìn)化群的更新，而不是指導(dǎo)失敗粒子進(jìn)行更新。

1.1 競(jìng)爭(zhēng)池

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

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

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

圖1 競(jìng)爭(zhēng)最優(yōu)入池示意圖Fig.1 Schematic diagram of competition for optimal entry into the pool

圖2 競(jìng)爭(zhēng)最優(yōu)出池示意圖Fig.2 Schematic diagram of competitive optimal pool

1.2 侵略性自由粒子

初始設(shè)定N個(gè)粒子，當(dāng)N為偶數(shù)，即選取N／2個(gè)粒子作為侵略性自由粒子；當(dāng)N為奇數(shù)時(shí)，隨機(jī)選取一個(gè)粒子，定義該粒子即是侵略性自由粒子，也是擇優(yōu)進(jìn)化群中的粒子。此策略可保證侵略性自由粒子與擇優(yōu)進(jìn)化群的規(guī)模保持一致。侵略性自由粒子具備高自由度和侵略性。

1.2.1 高自由度

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

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

1.2.2 侵略性

自由粒子的侵略性體現(xiàn)在粒子群的優(yōu)化更新過(guò)程中。當(dāng)擇優(yōu)進(jìn)化群的粒子在適應(yīng)度值競(jìng)爭(zhēng)中獲勝作為競(jìng)爭(zhēng)最優(yōu)時(shí)，侵略性未被激活，擇優(yōu)進(jìn)化群按原有軌跡進(jìn)行更新；當(dāng)侵略性自由粒子在適應(yīng)度值競(jìng)爭(zhēng)中獲勝作為競(jìng)爭(zhēng)最優(yōu)時(shí)，激活侵略性。此時(shí)侵略性自由粒子以改進(jìn)速度公式作為載體，參與擇優(yōu)進(jìn)化群的更新過(guò)程，指導(dǎo)擇優(yōu)進(jìn)化群向侵略性自由粒子的位置信息進(jìn)行學(xué)習(xí)，使擇優(yōu)進(jìn)化群擺脫原有更新軌跡。該策略增強(qiáng)了算法擺脫局部最優(yōu)的能力。

1.3 改進(jìn)速度公式

傳統(tǒng)粒子群算法（PSO）的速度更新公式中，存在個(gè)體最優(yōu)與全局最優(yōu)兩個(gè)概念。本文提出的算法憑借競(jìng)爭(zhēng)最優(yōu)（Cbest）的選擇機(jī)制，摒棄個(gè)體最優(yōu)與全局最優(yōu)，將原有的兩個(gè)外部存檔，優(yōu)化為僅對(duì)競(jìng)爭(zhēng)最優(yōu)進(jìn)行外部存檔，降低了算法的空間復(fù)雜度。算法在粒子速度更新時(shí)，僅向競(jìng)爭(zhēng)最優(yōu)進(jìn)行學(xué)習(xí)，提高粒子的學(xué)習(xí)精度。對(duì)比傳統(tǒng)速度公式，改進(jìn)后的速度公式提高了算法的運(yùn)算速度，將算法效率進(jìn)一步提升。速度公式如式（1）所示。

2 實(shí)驗(yàn)結(jié)果分析

通過(guò)對(duì)8個(gè)典型標(biāo)準(zhǔn)函數(shù)的測(cè)試，對(duì)比CAPSO算法和其它改進(jìn)算法的性能。其中f1～f4為單峰函數(shù)；f5～f8為多峰函數(shù)，具體函數(shù)見(jiàn)表1。

表1 標(biāo)準(zhǔn)測(cè)試函數(shù)Tab.1 Standard test functions

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

通過(guò)Matlab仿真，得到不同算法在8個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)的收斂曲線如圖4、圖5，各算法測(cè)試結(jié)果見(jiàn)表2。

圖5 不同算法在4個(gè)多峰標(biāo)準(zhǔn)測(cè)試函數(shù)的收斂曲線Fig.5 Convergence curves of different algorithms on four multi-peak standard test functions

表2 不同算法在8個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)中的結(jié)果Tab.2 Results of different algorithms in 8 standard test functions

圖4 不同算法在4個(gè)單峰標(biāo)準(zhǔn)測(cè)試函數(shù)的收斂曲線Fig.4 Convergence curves of different algorithms on four unimodal standard test functions

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

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

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

3 結(jié)束語(yǔ)

本文結(jié)合多種改進(jìn)策略，提出基于競(jìng)爭(zhēng)侵略策略的粒子群算法（CAPSO），該算法利用侵略性自由粒子的高自由度特性結(jié)合競(jìng)爭(zhēng)池概念，大幅度的提升了算法的性能。CAPSO算法在避免陷入局部最優(yōu)和提高收斂速度的問(wèn)題上表現(xiàn)出較強(qiáng)的能力，通過(guò)競(jìng)爭(zhēng)最優(yōu)（Cbest）的選擇機(jī)制，摒棄個(gè)體最優(yōu)與全局最優(yōu)，達(dá)到簡(jiǎn)化速度公式的目的，令算法進(jìn)化過(guò)程中更新速度更快，學(xué)習(xí)效率更高，在單峰函數(shù)和多峰函數(shù)中都具有優(yōu)秀的收斂速度和收斂精度，且算法穩(wěn)定，證明CAPSO算法的機(jī)制可以解決多種優(yōu)化問(wèn)題。