基于自適應多種群的粒子群優化算法

曾 輝，王 倩 ，夏學文 ，方 霞 ，5

1.新疆工程學院 計算機工程系，烏魯木齊 830023

2.新疆師范大學 數學科學學院，烏魯木齊 830017

3.華東交通大學 軟件學院，南昌 330013

4.華東交通大學 智能優化與信息處理研究所，南昌 330013

5.加拿大薩斯卡切溫大學 地理與規劃系，加拿大 薩斯卡通 SK S7N5C8

1 引言

粒子群優化算法（Particle Swarm Optimization algorithm，PSO）是Kenndy和Eberhart于1995年提出的一種演化算法[1]。在算法的優化過程中，粒子依據自身和鄰居的經驗信息對飛行方向和步長進行調整。盡管單個粒子的搜索模式非常簡單，但是由于粒子間的競爭機制的存在，整個種群的搜索表現非常復雜而智能。粒子群算法概念簡單、易于實現、智能高效，得到了廣泛的應用[2-3]。

粒子群算法尋找全局最優解的能力主要取決于兩個特征：探測性和開采性[4-5]，但這兩者之間存在著矛盾[6]。探測能力在多峰函數上表現更好，但在單峰函數上性能欠佳。相反，開采能力對單峰函數來說就比較重要。于是針對特定的問題可對算法的探測能力或開采能力進行改進[7]。但是現實中獲得具體問題的特征非常困難。

許多研究對探測能力和開采能力進行折衷，以提高PSO算法的綜合性能[8-9]。其共同特點是在進化的早期保持種群的多樣性，在后期加速其收斂速度。受此啟發，本文提出一種基于自適應多種群的粒子群優化算法（PSO-SMS）。算法在演化的初始階段將整個種群劃分為多個子群，然后使用三種模塊提高算法的性能。實驗對比表明，PSO-SMS算法在解決不同類型的函數優化問題上表現突出。

2 相關工作

2.1 標準粒子群優化算法

在粒子群算法中，每個粒子都被看成是一個潛在的解，種群的飛行軌跡被看作是算法的一個連續優化過程。在每一代中，第i個粒子與兩個向量相關，位置向量Xi=[xi,1,xi,2,…,xi,D]和速度向量Vi=[vi,1,vi,2,…,vi,D],其中，D表示問題的維數。Xi表示問題的一個候選解，Vi表示第i個粒子的搜索方向和步長。在進化過程中，每個粒子依據其歷史最好位置向量Pbi=[pbi,1,pbi,2,…,pbi,D]和鄰居的歷史最好位置向量Nbi=[nbi,1,nbi,2,…,nbi,D]來調整飛行軌跡。第i個粒子的速度和位置更新規則分別定義為公式（1）和（2）。

其中，w代表慣性權重，確定速度的存量；c1和c2為加速因子，表示 pbi與nbi的相對學習權重。r1、r2是區間[0，1]上的隨機數；和分別表示t代種群中第i粒子在第 j維上的位置和速度。

2.2 粒子群算法研究現狀

粒子群算法發展了多種變異形式，大致可分為參數調整、學習榜樣的選擇和混合策略等3類。

Shi和Eberhart于1998年提出的一種線性遞減的w新規則[10]，目前該策略仍然被很多PSO算法所采用。此外，有學者對PSO的另兩個關鍵參數，即加速因子c1和c2，也進行了類似的改進，提出了時變加速因子PSO算法（HPSO-TVAC）[9]。為進一步對算法涉及的參數進行更為合理的調整，Zhan等提出了一種自適應粒子群優化算法（APSO）[11]，其參數w、c1和c2的調節主要依賴于種群分布和粒子的適應值而不是迭代次數。實驗結果表明，該算法在單峰和多峰問題中都具有比較可靠的性能。

通過調整鄰居拓撲結構來改變學習榜樣在近年來也涌現出較好的成果。如譚陽等人[12]將PSO中的全局最優解擴展為由多個精英粒子組成的精英子群，精英粒子間采用了排異策略，同時采用適應值競爭策略指導整個粒子群，以保證種群多樣性。Zhan等提出了一種正交學習粒子群算法[13]（OLPSO），使用正交實驗設計法將粒子的最優解和鄰居的最優解合成為一種更有效的樣本。此外，許多研究結果也表明，動態種群結構[14-16]和自適應[17]學習框架均能有效提高算法的全局能力，在一定程度上克服了PSO的早熟現象。

考慮到不同算法和搜索策略都有其各自的優點，混合策略也引起了眾多學者的關注。例如，采用遺傳算子[18]和局部搜索策略[14，19]可分別提高種群多樣性和加快收斂速度。Xin等提出了一種基于差分進化（DE）的混合粒子群優化算法DEPSO[20]。DE和PSO的雜交算法[21]表明雜交策略解決了單一算法的某些缺陷。文獻[22-23]則是將粒子群算法和人工蜂群算法（ABC）進行雜交。

盡管將PSO算法的變異情況分成了三種不同的類型，但在實際中常常會將各種類型結合起來應用[24-25]。如在Frankenstein的PSO算法[26]中（本文中簡記為FPSO），使用了一個隨時間衰減的慣性權重和時變的種群拓撲兩種策略。

3 基于自適應多種群的粒子群優化算法

在PSO-SMS算法中，種群在初始演化階段分成許多同等規模的子種群。各小型子群根據公式（1）與公式（2）使用自身的成員并行去尋找更優的域。將局部PSO算法（LPSO）的拓撲結構[8]應用于各個子群，同時引入了重組、調整子群規模和探測模塊等三個模塊。新引入模塊的詳細描述如下。

3.1 重組模塊

PSO-SMS選擇由全部種群中得到的最優位置的連續停滯代數Staggbest作為算法的一個重組準則。此時，種群可以不必等待一個預定義的重組期，在停滯超過一個閾值時可及時重組。考慮到較大子群中包括最優粒子在內的每個粒子在從其他粒子中完整提取有益信息可能需要更多代，設置Staggbest=「」gsm/2為閾值，gsm代表各子群的種群規模。如每個子群的粒子數為10，種群將在 Staggbest超過5時重組。LPSO拓撲結構中的信息擴散過程描述如圖1。

圖1 LPSO拓撲結構中的信息擴散過程

3.2 調整子群規模模塊

演化開始時，種群被劃分為許多較小的子群，通常每個子群只包含兩個粒子。隨著演化的進行，各子群的規模逐漸增大，數量相應減少。演化的最后階段將其合并為一個種群。可使得進化過程的初始階段保持種群多樣性，因為整個種群之間的知識擴散速度非常慢。相反，種群規模的逐漸增大使得知識流動隨著進化過程越來越快，這有利于優化后期的開采能力。

本文中所有子群在每一代的規模均相同，即每個子群的規模必是總種群規模的一個因子。若種群規模為N=30，則各子群的規模選自整數集N={2,3,5,6,10,15}每個元素都是N的一個因子。同時，將子群規模調整的時機安排在 k個適應值評估（FEs）中(k=MaxFEs/|N|)，| N |代表N中元素的個數。在不同的演化階段的總種群（即在子群規模不同的情況下）分配給相同的FEs。這一方案可使種群保持平穩的調整過程。

此外，從種群獲得的全局最優位置GB周期性地執行一個局部搜索算子，可以提高求解精度。于是，在子群規模調整之后，對GB采用擬牛頓法進行改良[14-15]。為簡化起見，BFGS擬牛頓法由MATLAB中的“fminunc”函數來實現。當GB每一次在子群規模調整之后執行局部搜索算子時，對算子執行[0.10?fes]次適應值評估，fes是種群業已消耗的適應值評估次數。這樣，在后期演化階段將對局部搜索算子進行更多的適應值評估，可增強局部搜索能力，提高解的精度。

3.3 探測模塊

探測模塊需要考慮的第一個問題是如何選擇有用的信息。為了方便地收集信息和執行探測算子，將函數每個維度的搜索空間劃分為滿足以下條件的多個小區域：

Si是第i維全部搜索空間；Rn為子區域數；與分別是第i維的第 j與第k子區域(1≤j,k≤Rn)。

基于此劃分方案，可以很容易地確定GB每一維屬于哪一子區域，以及GB可以探測哪一子區域。探測算子最簡單的方法是GB隨機選擇某個子區域執行探測。但如果選擇一個更合適的子區域進行探測而非隨機地選擇，將會更有效地跳出局部最優。本文利用每一個體的歷史最好位置pbi來指導GB探測合適的子區域。為簡單起見，記錄所有粒子的歷史最優位置落入特定子區域中的次數。定義子區域的優值如下：

ME(1≤i≤D,1≤j≤R)為第i維第 j子區域的n優值；pbk,i(1≤i≤D,1≤k≤N)為第k個粒子歷史最優位置的第i維度值；N、D與Rn分別是種群規模、維數與子區域數。

第二個問題是GB何時執行探測算子。本文中在調整子群規模時利用子區域的優化來指導GB執行探測算子。

最后，如何根據優值來指導探測算子的執行。為此，針對一個固定的i值將子區域分為三種類型：（1）優越子區域，具有最大的ME值；（2）不良子區域，具有最小的ME值；（3）優化子區域，既無最大亦無最小ME值。當GB的第i維度值（本文用GBi表示）位于第i維的優越子區域時，GB將探測第i維的一個不良子區域，進而執行一個置換算子（將在后文介紹）。因為包括 GB在內的所有個體都從未或者極少進入不良區域，如果這一子區域中存在一個全局最優解，使GB探測不良子區域或許可以得到一個有效算子。即使此不良子區域中不存在全局最優解，這一操作也僅浪費一次適應值評估。另兩種情形，即GBi落入不良子區域、優化子區域的情況，GB并不執行探測算子，此時其他粒子可以指導它的飛行。

置換算子采用貪心策略。僅當探測到的新位置有助于提高最初的GB性能時，GBi才會被新位置所取代。

考慮到不同時期的統計信息可能會導致GBi探測到同一子區域，使其失去一次發現其他子區域的機會，因此對GBi采用基于禁忌的探測策略。如當GBi探測第i維的第 j子區域之后，這一子區域被設置禁忌標簽tabui,j，其值為1。此時這一區域不再被GBi探測，直到tabui,j的值重置為0。當第i維所有的禁忌標志tabui,j都被設置為1時，這些禁忌標簽會一次性重置為0。即當GBi在所有子區域執行探測后，tabui,j(1≤j≤Rn)將被重置為0；同時記錄新的統計信息。

第i維的探測操作如算法1所示。

算法1探測（）

1.TmpGB=GB；

2.Fori=1toN Do

3. Iftmpgbi在一個較好的子區域內Then/*tmpgbi是TmpGB的第i個值*/

4. tmpgbi被一較差區域的一個隨機值取代，此時，tabui;k=0；

5. 評估TmpGB；

6. If TmpGB好于GB Then

7. GB=TmpGB；impi=1；

8. Else

9. impi=0；

10. End If

11. tabui;k=1；

12. If所有的tabui;k1≤k≤Rn都等于1 Then

13. 設置所有tabui;k1≤k≤Rn等于0；

14. End If

15.End If

16.End For

探測算子完成后，GB進行一個簡單的逐維置換算子。為了保留探測的良好結果，只選擇那些GB并沒有探測出有前途的值的維度來執行置換。置換操作詳見算法2。

算法2置換（）

1.TmpGB=GB；在種群中隨機選擇一個粒子Xi；

2.For TmpGB的每一個維度的值tmpgbjDo

3. Ifimpj==0Then

4. tmpGbj=xi,j//tmpGbj是TmpGB的第 j維

5. 評估TmpGB；

6. fes++；

7. If TmpGB較Gb好 Then

8. GB=TmpGB；

9. End If

10. End If

11.End For

3.4 PSO-SMS框架

綜上所述，PSO-SMS算法流程如圖2所示。

4 實驗分析

4.1 實驗設置

為驗證PSO-SMS在不同環境中的表現，對CEC2013測試集中的20個函數進行實驗，包括5個單峰函數(f1～f5)和15個多峰函數(f6～f20)。測試函數的具體內容可參考文獻[27]。

本文選取了近十年內涌現的7個PSO算法作為對比算法，具體包括DMSPSO[15]、F-PSO[26]、OLPSO[13]、SLPSO[17]、PSODDS[28]、SL_PSO[29]及 HCLPSO[30]。各對比算法的參數設置與原文一致，詳情可參考相應的文獻，這里不再贅述。測試函數的變量維數與最大適應值評估次數(MaxFEs)分別設置為30和300 000。

4.2 實驗結果與分析

圖2 PSO-SMS算法流程圖

實驗中，所有30維問題的PSO算法種群規模與在原始文獻中應用的規模相同。每個算法對所有測試函數獨立運行100次。結果如表1、表2所示。

4.2.1 單峰函數

表2中對第一組的5個單峰函數實驗結果進行了總結。所有算法對 f1和 f5均表現出了較好的性能，其中包括PSO-SMS在內的4種算法在100次運行中實現了f1的全局最優。

均值方面，PSO-SMS給出了 f2的最優和 f4的次優結果，對 f3欠佳。中值方面，DMSPSO表現最好，其在3個單峰函數上均給出了最精確的解。PSO-SMS在 f1、f2和 f4上也取得了很好的性能。

雖然PSO-SMS與DMSPSO都具有多種群結構特性，但PSO-SMS對 f1和 f5的作用比DMSPSO弱，因PSO-SMS中種群較大且探測算子耗費較多的評估過程（在這兩個簡單問題中無局部最優）。相反，由于 f2、f3和 f4這三個基準測試問題均具有平滑的局部不規則性，PSO-SMS給出了較DMSPSO更好的綜合性能。比較結果驗證了探測算子對該類適應度景觀的有效性。

表1 15個多峰函數的比較結果

4.2.2 多峰函數

表1中對15個多峰問題的比較結果進行了總結，從均值和中值來看，PSO-SMS都獲得了非常滿意的性能。

對于 f8、f9、f16和 f20，大多數算法在均值這一指標上取得了相近的結果。考慮到這些算法的種群大小不同，可認為多數算法在這幾個多峰問題上具有幾乎相同的性能。DMSPSO、PSO-SMS和SLPSO在多峰函數上的整體綜合性能較之其他算法更好。其中，PSO-SMS在最優均值方面取得了更好的結果。

表2 5種單峰函數的比較結果

5 結束語

本文提出了一種粒子群算法的變種，基于自適應多種群的粒子群算法PSO-SMS。算法將整個種群分為若干子種群，同時將重組模塊、調整子種群規模和探測模塊引入到算法中以提高綜合性能。

為驗證PSO-SMS算法的性能，將其與其他7種PSO變種算法同時在cec2013測試集的20個函數上進行了對比實驗。從實驗結果可得出如下結論。首先，探測模塊有利于多峰函數優化，因其有助于種群逃離局部最優。其次，子種群規模的調整在一定程度上彌補了PSO算法的探測能力與開采能力之間的矛盾。第三，重組模塊對粒子信息共享行為也有積極的影響，可顯著提高收斂速度。

：

[1]Kennedy J，Eberhart R C.Particle swarm optimization[C]//Proc of IEEE International Conf on Neural Networks（CNN’95），1995：1942-1948.

[2]Ling S H，Iu H H C，Chan K Y，et al.Hybrid particle swarm optimization with wavelet mutation and its industrial applications[J].IEEE Trans on Syst，Man，Cybern B，Cybern，2004，34（2）：997-1006.

[3]Soh H，Ong Y S，Nguyen Q C，et al.Discovering unique，low-energy pure water isomers：memetic exploration，optimization and landscape analysis[J].IEEE Trans on Evol Comput，2010，14（3）：419-437.

[4]Janson S，Middendorf M.A hierarchical particle swarm optimizer and its adaptive variant[J].IEEE Trans on Syst，Man，Cybern B，Cybern，2005，35（6）：1272-1282.

[5]Kadirkamanathan V，Selvarajah K，Fleming P J.Stability analysis of the particle dynamics in particle swarm optimizer[J].IEEE Trans on Evol Comput，2006，10（3）：245-255.

[6]夏學文，劉經南，高柯夫，等.具備反向學習和局部學習能力的粒子群算法[J].計算機學報，2015（7）：1397-1407.

[7]肖閃麗，王宇嘉，聶善坤.動態鄰居維度學習的多目標粒子群算法[J].計算機工程與應用，2017，53（20）：31-37.

[8]Kennedy J，Mendes R.Population structure and particle swarm performance[C]//Proc of Cong on Evolutionary Computation（CEC’02），2002：1671-1676.

[9]Ratnaweera A，Halgamuge S K，Watson H C.Self-organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients[J].IEEE Trans on Evol Comput，2004，8（3）：240-255.

[10]Shi Y，Eberhart R C.A modified particle swarm optimizer[C]//Proc of Cong on Evolutionary Computation（CEC’98），1998：69-73.

[11]Zhan Z H，Zhang J，Li Y，et al.Adaptive particle swarm optimization[J].IEEE Trans on Syst，Man，Cybern B，Cybern，2009，39（6）：1362-1381.

[12]譚陽，譚德權，全慧云.一種排異競爭的粒子群優化算法[J].系統仿真學報，2011，23（12）：2635-2640.

[13]Zhan Z H，Li Y，Shi Y H.Orthogonal learning particle swarm optimization[J].IEEE Trans on Evol Comput，2011，15（6）：832-847.

[14]Liang J J，Suganthan P N.Dynamic multi-swarm particle swarm optimizer[C]//Proc of IEEE Swarm Intelligence Symposium（SIS’05），2005：124-129.

[15]Zhao S Z，Liang J J，Suganthan P N，et al.Dynamic multi-swarm particle optimizer with local search for large scale global optimization[C]//Proc of Cong on Evolutionary Computation（CEC’08），2008：3845-3852.

[16]倪慶劍.一種基于可變多簇結構的動態概率粒子群優化算法[J].軟件學報，2009，20（2）：339-349.

[17]Li C，Yang S，Nguyen T T.A self-learning particle swarm optimizer for global optimization problems[J].IEEE Trans on Syst Man，Cybern B，Cybern，2012，42（3）：627-646.

[18]Higashi H，Iba H.Particle swarm optimization with Gaussian mutation[C]//Proc of IEEE Swarm Intelligence Symposium（SIS’03），2003：72-79.

[19]程畢蕓，魯海燕，徐向平，等.求解旅行商問題的改進局部搜索混沌離散粒子群優化算法[J].計算機應用，2016，36（1）：138-142.

[20]Xin B，Chen J，Peng Z H.An adaptive hybrid optimizer based on particle swarm and differential evolution for global optimization[J].Sci China Ser F：Inf Sci，2010，53（5）：980-989.

[21]Xin B，Chen J，Zhang J，et al.Hybridizing differential evolution and particle swarm optimization to design powerfuloptimizers：areview andtaxonomy[J].IEEE Trans on Syst Man，Cybern C，Appl Rev，2012，42（5）：744-767.

[22]Kiran M S，Gndz M.A recombination-based hybridization of particle swarm optimization and artificial bee colony algorithm for continuous optimization problems[J].Appl Soft Comput，2013，13（4）：2188-2203.

[23]劉俊芳，張雪英，寧愛平.PSO和ABC的混合優化算法[J].計算機工程與應用，2011，47（35）：32-34.

[24]喻飛，李元香，魏波，等.透鏡成像反學習策略在粒子群算法中的應用[J].電子學報，2014，42（2）：230-235.

[25]Oca M D，Stutzle T，Enden K V D，et al.Incremental social learning in particle swarms[J].IEEE Trans Syst，Man，Cybern B，Cybern，2011，42（2）：368-384.

[26]Oca M A M D，Stutzle T，Birattari M，et al.Frankenstein’s PSO：a composite particle swarm optimization algorithm[J].IEEE Trans on Evol Comput，2009，13（5）：1120-1132.

[27]Liang J J，Qu B Y，Suganthan P N.Problem definitions and evaluation criteria for the CEC 2013 special session on real-parameter optimization[R].Nanyang Technological Univ.，Singapore，2013.

[28]Jin X，Liang Y Q，Tian D P，et al.Particle swarm optimization using dimension selection methods[J].Appl Math Comput，2013，219（10）：5185-5197.

[29]Cheng R，Jin Y.A social learning particle swarm optimization algorithm for scalable optimization[J].Inf Sci，2015，291（6）：43-60.

[30]Lynn N，Suganthan P N.Heterogeneous comprehensive learning particle swarm optimization with enhanced exploration and exploitation[J].Swarm Evol Comput，2015，24：11-24.