基于局部遠親差分增強的擾動粒子群優化算法

王永貴，胡彩云，李 鑫

(遼寧工程技術大學軟件學院，遼寧葫蘆島125105)

(*通信作者電子郵箱1581280425@qq．com)

0 引言

粒子群優化(Particle Swarm Optimization，PSO)算法是根據鳥類覓食、人類認知等社會行為提出的具有記憶功能的群智能進化算法，于1995年由Kennedy等［1］首次提出。該算法具有形式簡潔、調參靈活、收斂快速等特點，受到學者廣泛關注。目前PSO算法在多信道無線網絡、煤與瓦斯的測量、焊接機器人路徑規劃等復雜優化實例中得到大量應用［2－4］。

PSO算法僅根據個體與群體經驗調整自身狀態，因此，個體間缺乏聯系，易逐漸喪失種群多樣性，陷入局部極值，對全局最優解［5］搜索能力弱，在復雜多峰問題中早熟收斂問題尤為突出。為此學者們提出多種改進措施［6－7］:Li等［8］為避免粒子因單一學習模式使特定粒子缺乏智能，從而陷入局部極值，因此引入自學習粒子群優化(Self Learning PSO，SLPSO)算法，為每個粒子提供4種不同策略應對搜索空間中不同情況;van Zyl等［9］提出一種粒子群初始化策略解決高維問題，使粒子的搜索空間為一個子空間，而不是整個搜索空間;Guo等［10］在PSO算法中引入文化算法，群體的優化過程是由信仰與群體兩層之間的演化與交流實現;高衛峰等［11］為加速算法跳出局部極值，僅對粒子搜索到的最優解利用人工蜂群算子進行搜索，并提出基于混沌和反學習的初始化學習方法，提高了全局搜索速度;夏學文等［12］為讓算法較快逃離局部最優，根據較差粒子及每個粒子的歷史較差位置信息指導粒子以較快的飛行速度進行反向學習，提高了算法的求解精度，保證了算法的收斂速度;王東風等［13］根據粒子適應值差異，提出一種對粒子位置進行高斯采樣均值的自適應調整策略，增加粒子分布中心的分散度，減緩粒子在中心的聚集趨勢，并提出“鏡像墻”的越界粒子處理法，大幅提高了算法找到最優解的概率，同時為增加種群多樣性，榜樣粒子的選擇由粒子不同進化時期的不同拓撲結構決定;周偉等［14］在標準粒子群基礎上，選取精英粒子種群，構建精英粒子群－進化融合優化機制，并引入模糊高斯學習策略，提高了種群的多樣性和尋優能力。

上述改進算法的性能皆有提高，但由于PSO算法本身的隨機性，若僅對算法參數改進，搜索中仍具有不確定性且無法避免陷入局部極值;若與其他算法融合，種群的每次迭代都要進行種群重建、計算、比較、尋優，整個過程計算量大，影響算法的執行效率。

為更好地挖掘PSO算法的搜索能力，使算法在收斂速率和收斂精度上都達到理想狀態，本文提出一種基于局部遠親差分增強的擾動粒子群優化算法(Perturbation Particle Swarm Optimization algorithm based on Local Far-neighbor Differential Enhancement，LFDE-PPSO)。LFDE-PPSO主要有以下改進:1)為避免隨機初始化種群帶來的無效解，提出半均勻式初始化種群，使種群既不喪失隨機性又能相對均勻地遍布于搜索空間;2)為擴大粒子的搜索空間，增加解的多樣性，引入擾動因子對慣性權重、學習因子進行擾動，實現智能搜索;3)為提高全局搜索速度，根據適應度值引入重構概率，選擇部分較差個體構建中間種群;4)為避免遺失較差個體中的優秀基因，利用遺傳學機理，防止“近親繁殖”導致的無效操作，引入粒子不相關性，找到差分個體的“遠親”進行差分變異，增加種群多樣性。

1 基本理論

1．1 粒子群優化算法

在PSO算法中，待優化問題的潛在解可看成N維搜索空間中的一個點，即為“粒子”。粒子在N維空間中搜索，則第i個粒子的速度及位置更新如下:

表1 基本PSO算法參數說明Tab．1 Basic PSO algorithm parameter description

1．2 差分進化算法

差分進化(Differential Evolution，DE)算法［15］是一種高效智能全局搜索算法，通過個體間差分、交叉、變異產生新個體，增加種群多樣性，具備自學習、自組織、自適應和全局搜索能力強等特點。DE算法主要操作如下:

1)變異操作。

2)交叉操作。

2 局部遠親差分增強的擾動粒子群算法

2．1 半均勻式初始化

為避免隨機初始化種群導致粒子初始化位置過于集中，不利于粒子的全局搜索，故采用半均勻式初始化種群，使種群既相對均勻地分布在整個搜索空間，又能保持種群的隨機性、多樣性。半均勻式初始化種群為:

其中:NP 為種群規模，i為第 i個個體，i=(1，2，…，NP/2);t為N維變量中第t個變量;t為第0代種群第i個粒子的第t個變量初始值。

2．2 擾動因子

在PSO算法的影響因子中，慣性權重ω是前一代粒子速度對當前粒子速度的影響系數，平衡全局與局部搜索。自我學習因子c1與社會學習因子c2影響系統張力，因而許多學者對影響因子進行了不同的改進:文獻［5］采用了線性遞減策略;文獻［16］采用了非線性慣性權重遞減策略;文獻［17］提出了同步、異步的線性變換策略;文獻［18］中在學習因子中融入慣性權重的影響因素實現異步變換;文獻［19］采用反三角函數變換策略影響學習因子。

研究表明，對影響因子較好的改進方法是遞變策略，但固定的變換形式并不利于個體在全局范圍內搜索，間接影響種群多樣性的保留。受自然界中蝴蝶效應的啟發，初始條件下微小的變化能帶動整個系統具有長期巨大的連鎖反應，任何事物的發展都存在定數和變數。因此，本文引入擾動因子，讓PSO算法的慣性權重和學習因子在整體遞變的基礎上，添加微小的變化，既防止粒子因位置變換引起速度較大的變動，又能保障影響因子在遞變的趨勢上，實現擾動，從而擴大解的搜索空間，使位置和速度呈現浮動式變換搜索，增加解的可能性。

本文擾動因子使用正余弦函數進行策略變換，因其函數值在［－1，1］變動，能夠保障影響因子實現小范圍內跳動。慣性權重、學習因子變換策略為:

其中:k為迭代次數;kmax為最大迭代次數;rand()為(0．9，1)的隨機數;αk、βk分別為正余弦擾動因子;ωk是種群k次迭代的慣性權重;ωmax、ωmin是慣性權重可取到的最大值和最小值;c1，k、c2，k為 k次迭代過程中的自我學習因子、社會學習因子;c1s、c1e為自我學習因子的初始與最終值;c2s、c2e為社會學習因子的初始與最終值。

擾動策略在算法初期，能夠使ω、c1取較大值，使粒子擁有較快的遞減速率，促進粒子進行局部搜索，加快粒子向全局最優聚攏，并使粒子對自身具備較強的思考能力，鼓勵粒子靠近曾發現的最優位置;算法后期ω遞減速率降低，c2取值較大，促進粒子間進行信息共享，幫助粒子在局部搜索的過程中實現精細搜索，引導粒子逼近全局最優位置，保持搜索精度與速度之間的平衡。

2．3 局部遠親差分增強

PSO算法的整個尋優過程僅由個體和社會的歷史最優位置迭代驅動，其所有操作都僅針對優秀個體，容易忽略群體中其他粒子信息，特別是較差個體，而較差個體與優秀個體中的優秀基因往往相差甚遠，這就導致搜索過程中對種群多樣性影響較大的優秀基因逐漸丟失，使種群易陷入局部極值而無法跳脫。為使中間種群中較差個體的優秀基因得以延續，本文根據遺傳學“遠親繁殖，雜交出優勢”，引入了粒子不相關性，由粒子不相關性計算選擇概率，利用選擇概率找出“遠親”進行雜交繁殖，有效保障優秀基因的傳承，使種群在搜索過程中保持活力，避免算法陷入局部極值。

局部遠親差分增強策略首先利用重構概率根據輪盤賭選擇適應度值低的個體重新構建中間種群;然后，在中間種群中隨機選擇差分個體，根據粒子的不相關性計算其余個體的選擇概率，利用選擇概率，從中間種群中找出兩個與差分個體基因差異較大的臨時個體進行差分變異，保留適應度值高的個體基因進入下一代種群。

1)重構概率。

為了使算法每次的搜索結果都能有效反饋給種群，讓種群根據尋優結果進行相應的變換，實現自適應調整，因此，本文引入重構概率，即根據粒子的適應度值求出粒子被選中重新構建中間種群的概率。

其中:i=1，2，…，NP，NP為種群規模。式(11)表明當粒子適應度值越低，對應重構概率越大，即粒子被選擇構成中間種群的可能性越大。

2)粒子不相關性。

其中:t=(1，2，…，n)，t為n維向量中具體的一維。式(12)表明，若個體間變量值差異性較大，則不相關性越大。

3)選擇概率。

3 算法流程

步驟1 初始化 PSO 算法參數，(ωmin，ωmax) =(0．4，0．9)，(c1s，c1e)=(2．5，0．5)，(c2s，c2e)=(0．5，2．5)，種群規模NP，每維變量的上下界范圍，粒子的最大飛行速度Vmax;最大迭代次數 kmax，變異算子 F=0．5，交叉概率 CR=0．9;

步驟2 由式(5)半均勻式初始化種群;

步驟4 FOR i=1，2，…，NP，計算個體適應度值與輪盤賭構建規模為(NP/3)的中間種群;

步驟11 若k≥kmax，則輸出粒子所在位置的適應度值，否則重復步驟3～11。

4 實驗及結果分析

為確保實驗的公平性，本文所有實驗均在Inter Core i5-2450M CPU 2．5 GHz，12 GB內存的機器上實現，軟件運行的環境是Matlab 2014b。種群規模NP=30，變量維度N=30，最大迭代次數kmax=1000，每個測試函數單獨運行30次，可接受誤差為 0．1。

4．1 測試函數及評價標準

為驗證擾動策略和局部遠親差分增強策略的可行性，本文選取了2個經典單峰函數與3個復雜多峰函數進行驗證。函數的搜索空間與理論最優值如表2所示。其中函數1是帶噪聲的四次方緩動函數，最優值隨隨機分布數而改變，較難尋優;函數2是單峰非凸、較難極小化的典型病態二次函數，其最優值與多變量相關，搜尋難度較大;函數3、4、5都是旋轉、不可分離的可變維三角多峰函數，具有大量局部最優點，算法在求解過程中容易逼近局部最優，難以尋到全局極值。

為評定算法性能，本文選用以下評價準則［19］:

1)成功率(SuccR):將適應度函數最終解達到誤差允許范圍內視為有效解，成功率為有效解次數占總執行次數的比例，用來衡量算法的魯棒性;

2)平均最優值(MeanBst):算法30次獨立運行結束后所得適應度函數的平均最優值，該指標可衡量算法的尋優質量;

3)最終適應度值(FinalBst):函數最終收斂時的最優值;

4)平均運行時間(MeanT/s):算法獨立運行30次平均執行時間，是對算法尋優時效性的衡量;

5)穩定性(Stab):算法獨立運行30次，所得精度標準差。

表2 測試函數信息Tab．2 Information of test functions

4．2 單項改進措施有效性驗證

為驗證LFDE-PPSO各個改進措施的有效性，先分別對單項改進措施進行驗證。

1)擾動策略。為驗證擾動策略PPSO(Perturbation PSO)可使粒子在搜索過程中有效降低粒子陷入局部極值的可能。這里將PPSO與基本PSO算法進行對比，采用測試函數f1、f5進行驗證。結果如圖1所示。

圖1 函數收斂特性曲線Fig．1 Function convergence characteristic curves

從圖1中可以看出，PPSO在單峰與多峰函數優化上，能夠很快進入到全局最優狀態，優化精度、速率明顯高于基本PSO算法，充分證明擾動策略利于加快速度變換空間，避免粒子局部聚集，推動粒子在全局范圍內搜索，有效保持種群的多樣性，能夠控制局部與全局間的搜索平衡。

2)局部遠親差分增強策略。為驗證局部遠親差分增強(Local Far-neighbor Differential Enhancement，LFDE)策略能夠增加PSO算法種群多樣性，提高算法的收斂速度，幫助粒子逃離局部聚集狀態，本文將 LFDE算法與基本PSO算法、DEPSO算法采用測試函數f2、f4進行驗證，分別從以下兩個方面進行比較:1)穩定性驗證，比較3種算法在精度相同時適應度值方差;2)收斂速率驗證，比較三種算法在函數評價次數相同時各自的收斂精度。實驗結果如表3所示。

從表3可知，LFDE算法與傳統PSO算法相比，在達到相同精度時，PSO算法在 f2、f4的 Variance是 LFDE算法的6．56E+02、3．44E+06 倍，在運行 10 000、20 000、30 000 次時，PSO算法在f2的適應度值分別是LFDE算法的1．35E+06、4．36E+05、5．96E+04 倍，在 f4的適應度值分別為8．05E+15、7．00E+15倍。與DEPSO算法相比，DEPSO算法在f2的三次適應度值分別是 LFDE 算法的 2．84E+05、4．08E+04、6．24E+02倍，在f4的適應度值分別為1．61E+12、4．84E+10倍。以上結果表明，LFDE算法與基本PSO、DEPSO算法相比，在收斂速率上明顯提高。在穩定性方面，LFDE算法比PSO算法改善明顯，但與DEPSO算法相比，沒有明顯優勢，尤其在單峰函數的優化問題上，LFDE算法的適應度值方差是DEPSO算法的1．27倍，而在多峰函數上是DEPSO算法的39．79倍，說明在穩定性方面，LFDE算法在多峰函數的優化問題上仍具有一定優勢。從上述實驗結果可知，DEPSO算法與LFDE算法都能夠維持種群多樣性，這是由于DEPSO與LFDE算法都是通過交叉、變異產生新個體;但DEPSO算法每次迭代都通過DE與PSO算法生成兩個種群，對這兩個種群進行比較，擇優選出Pbest與Gbest，因而算法整體計算量龐大，極大地降低了算法的收斂速率。

表3 3種算法多樣性、速率比較Tab．3 Diversity and rate comparison of three algorithm

以上兩個單項驗證實驗結果可以得出，本文提出的擾動策略和局部遠親差分增強策略，在算法的收斂速率和種群多樣性的維持上都具有明顯優勢。

4．3 本文算法驗證

為進一步驗證LFDE-PPSO的優化性能，本文將LFDEPPSO 與標準粒子群算法(Standard PSO，SPSO)［20］，以及對PSO算法改進的混沌粒子群優化算法(Chaos PSO，CPSO)［21］、自調節粒子群優化算法 (Self Regulating PSO，SRPSO)［22］、交錯搜索粒子群優化算法 (Crisscross Search PSO，CSPSO)［23］進行比較。表4、5分別為這5種算法對應單峰、多峰測試函數的實驗結果，表5中的最后一項是5種算法在5個測試函數的4項評價準則的實驗結果平均值。

表4 單峰函數算法性能比較Tab．4 Performance comparison of single-peak function algorithms

表5 多峰函數算法性能比較Tab．5 Performance comparison of multi-peak function algorithms

從表4、5中可知，上述幾種算法對f5的優化效果都較為理想，是因為該函數當空間維數超過15維時，函數特性轉變，趨向單峰函數，易找到最優值。SPSO算法在f1上的MeanT/s是LFDE-PPSO的11倍;由平均值中的MeanT/s比較可知，LFDE-PPSO分別是 CPSO、SRPSO、CSPSO 算法的23．68%、74．19%、93．7%，算法的執行效率得到極大的改善;在FinalBst上，LFDE-PPSO在平均值中是CPSO算法的99%，雖然SRPSO、CSPSO算法在FinalBst上均能達到函數對應的極值，但在MeanBst的平均值計算結果上，分別是SRPSO、CSPSO算法的4．84%、6．21%，LFDE-PPSO 依舊具有一定的優勢。因而，從表4、5的各項驗證結果可得出，LFDE-PPSO的尋優精度、速率以及算法的尋優質量明顯優于 SPSO、CPSO、SRPSO、CSPSO 算法。

為進一步驗證LFDE-PPSO在收斂精度和穩定性上的性能，分別對LFDE-PPSO與SPSO算法以及綜合學習粒子群優化算法(Comprehensive Learning PSO，CLPSO)［24］、全 局 信 息 粒 子 群 算 法 (Fully Informed Particle Swarm，FIPS)［25］和 CPSO 算法進行比較。圖2、3分別是算法在30次實驗中，進行1 000次迭代的平均收斂特性曲線和標準差波動圖，圖中橫縱坐標分別是收斂精度對數、標準差與迭代次數。

由于SPSO算法無法向局部其他粒子學習，易造成啟發式信息和計算資源浪費，陷入局部最優，算法尋優質量較差;CPSO算法利用混沌映射創建初始種群，利用最優解附近混沌搜索結果替代種群中部分粒子，但CPSO算法是當種群陷入局部極值后，混沌搜索策略才開始生效，尋優過程中忽略其他粒子可能含有的先進基因，在多峰問題的求解上效果較差，從圖2中可看出，當迭代次數達到500次時，適應度值曲線基本已停止尋優，陷入互補局部極值。CLPSO算法通過選擇榜樣粒子的學習策略能夠改善PSO算法的性能，但該算法對多樣性保留的機制過于強健，在復雜多峰優化上較為有效，而單峰問題上的求解效果并不理想，在單峰問題的求解質量上僅優于SPSO算法。FIPS算法利用鄰域內所有成員最優加權平均值指導更新，結合周邊粒子的信息，該算法在單峰函數優化問題上作用效果尤為明顯，但該算法忽略個體差異性，因而在復雜多峰求解問題上效果較弱。從圖2所有的函數適應度值曲線中可以看出，對于難以優化的高維函數，尤其是存在多個局部極值的多峰函數，SPSO、CLPSO、FIPS、CPSO算法尋優時易陷入局部最優，且粒子一旦陷入局部極值，則很難跳出，因此很難得到理想的效果，LFDE-PPSO根據粒子適應度值自適應的選擇較差粒子重建中間種群，獲取較差個體中優秀基因填充現有種群，豐富了種群的多樣性。因此，在迭代的初期能夠較快地逼近全局最優，在單峰及復雜多峰的問題求解上都能取得優質解。從圖3的平均標準差波動趨向圖可以明顯得出，LFDE-PPSO與SPSO、CLPSO、FIPS、CPSO 算法相比具備較強的穩定性能。

圖2 各算法收斂特性曲線對比Fig．2 Convergence characteristic curve comparison of algorithms

圖3 各算法標準差波動對比Fig．3 Standard deviation comparison of algorithm

5 結語

本文提出了一種基于局部遠親差分增強的擾動粒子群算法，通過多角度對比仿真實驗得出該算法具有以下特點:1)采用擾動策略，使慣性權重與學習因子在迭代過程中動態生成，并加以微小擾動，使粒子在有效位置和速度上實現跳動，擴大搜索范圍，平衡全局搜索和精細搜索，促進粒子跳出局部極值;2)對新生種群中較為低質的粒子采用局部遠親差分增強策略，挖掘低質粒子中優秀基因，通過交叉變異保存下來，填充現有種群基因庫，進而使種群富有活力，不易陷入局部極值進入早熟狀態;3)僅對部分個體進行差分增強操作，避免種群大規模再生，重復計算，算法的收斂速度得到了極大的提升。因此，本文算法在處理較為復雜的優化問題上具有重要的實用價值。接下來，對于受參數影響較大的支持向量機優化問題上，利用LFDE-PPSO自動尋找支持向量機的最優參數，提高向量機的分類準確率與速率是下一步有待研究的問題。