基于食物鏈機制的動態多物種粒子群算法

劉角 馬迪 馬騰波 張瑋

摘要：針對粒子群優化（PSO）算法在解決多峰函數時容易陷入局部最優的問題，提出了一種基于食物鏈機制的動態多物種粒子群（DSPSO）算法。受生物界的啟發，引入食物鏈機制來保證種群的多樣性，并結合繁殖機制使得算法具有良好的優化性能。食物鏈機制中，整個標榜群被分為幾個子種群，每個子種群都能夠捕食另外一個子種群。通過一定概率發生的捕食現象使得標榜群得以進化，剔除對種群貢獻小的粒子，并通過繁殖策略生成新的粒子。種群通過不斷地進化保證了種群的多樣性，同時通過剔除較差粒子的誤導作用使算法的進化更有效率。為了驗證算法的有效性，選擇了包括偏移函數、旋轉函數在內的10個測試函數來測試DSPSO算法的性能。實驗結果表明DSPSO算法有著良好的尋優性能。與PSO、局部版本的粒子群（LPSO）算法、動態多群粒子群（DMSPSO）算法和全面學習粒子群（CLPSO）算法相比，DSPSO算法不僅能夠得到較高精度的解，而且還具有較高的可信度。

關鍵詞：粒子群優化算法； 食物鏈機制；動態多物種

中圖分類號：TP301.6 文獻標志碼：A

Abstract：a novel Dynamic multiSpecies Particle Swarm Optimization （DSPSO） algorithm based on food chain mechanism was proposed aiming at the problem that the basic Particle Swarm Optimization （PSO） algorithm is easy fall into local optimal solution when solving multimodal problems. Inspired by the natural ecosystem， a food chain mechanism and a reproduction mechanism were employed to keep the swarm diversity and good performance. In food chain mechanism， the swarm was divided into several subswarms， and each subswarm could prey on the others. The memory leader swarm was evolved and the less contributed particle was eliminated through predation， and then the new particle was generated through reproduction mechanism. The diversity was kept through the evaluation of the swarm， and the efficiency of the algorithm was enhanced through eliminating the misleading effect of the less contributed particles. In order to verify the effectiveness of the algorithm， ten benchmark problems including shifted problems and rotated problems were chose to test the performance of DSPSO. The experimental results show that DSPSO has a well optimizing performance. Compared with PSO algorithm， Local version Particle Swarm Optimization （LPSO） algorithm， Dynamic MultiSwarm Particle Swarm Optimization （DMSPSO） algorithm and Comprehensive Learning Particle Swarm Optimization （CLPSO） algorithm， DSPSO algorithm not only obtains more accurate solutions， but also has higher reliability.

Key words：Particle Swarm Optimization （PSO） algorithm； food chain mechanism； dynamic multispecies

0 引言

粒子群優化（Particle Swarm Optimization，PSO）算法是Kennedy等[1]于1995年提出的一種群智能優化算法，其思想來源于鳥群的捕食行為。由于其尋優速度快，易于實現，相較與其他元啟發式優化算法具有良好的性能，其出現以后便迅速得到了國際學者的關注并廣泛應用于諸如神經網絡、資源調度、圖像處理、電容配置等諸多領域。

盡管粒子群算法有著諸多優點，但是和其他元啟發式算法一樣，它也有著容易陷入局部最優、尋優后期收斂速度慢等缺點。為了克服這些缺點，許多學者都試圖從各個角度來提升粒子群算法的性能[2-3]。算法的改進總體分為三類，分別為：參數選取機制、種群拓撲結構以及學習機制。在參數選取方面，Shi等[4]提出慣性權重線性遞減的粒子群算法，該算法前期具有較好的探索能力，后期具有較強的勘探能力，從而兼具良好的全局搜索能力和局部搜索能力；Zhan等[5]提出了一種自適應粒子群算法，能夠根據不同的情況自動調整算法的加速因子和慣性權重。在種群拓撲結構方面，Kennedy等[6]研究了不同拓撲結構下粒子群算法的性能，一些典型的拓撲結構，如環形拓撲、馮諾依曼拓撲被應用到粒子群算法中。其中，采用環形拓撲的粒子群算法被稱為局部版本的粒子群（Local version Particle Swarm Optimization，LPSO）算法；Mendes等[7]提出了一種新的改進粒子群算法叫作全信息粒子群算法（Fully Informed Particle Swarm，FIPS）。FIPS認為沒有必要只選用全局最優點和局部最優點引導算法進化，所有的個體最優點均可以作為算法的進化目標，即每個粒子都可以依據其他粒子包含的信息進行進化。Liang等[8]提出了一種動態多群粒子群算法（Dynamic MultiSwarm Particle Swarm Optimization，DMSPSO），種群具有動態變化的拓撲結構，這種結構使得算法的信息在種群中的傳播速度降低，避免粒子過快聚集，從而提高了粒子群算法的尋優性能。在學習機制方面，一些改進算法借助于其他元啟發式算法的思想改善了粒子群算法的性能，例如Beheshti[9]提出的萬有引力粒子群算法，Lim等[10]提出的教學與同伴學習粒子群算法。還有一些具有新穎的學習機制，例如Zhan等[11]提出的正交學習粒子群算法，Liang等[12]提出的全面學習粒子群算法（Comprehensive Learning Particle Swarm Optimization，CLPSO），Ren等[13]提出的分散學習粒子群算法，這些算法均明顯地提升了粒子群算法的性能。

然而，早熟收斂仍然是粒子群算法的一大缺點，而多樣性的喪失是導致粒子群算法陷入早熟收斂的一個重要原因。為了防止多樣性的喪失，并使得算法更有效地進化，本文提出一種基于食物鏈機制的動態多物種粒子群算法（Dynamic multiSpecies Particle Swarm Optimization， DSPSO）。該算法受生物界的啟發，提出通過食物鏈機制來保證種群的多樣性，結合繁殖機制使得算法具有良好的優化性能，很大程度上改善了粒子群算法容易陷入局部收斂的缺點，并且提升了粒子群算法的收斂效率。

2 基于食物鏈機制的動態多物種粒子群算法

傳統的粒子群算法有著容易陷入局部收斂的缺點，在解決多峰問題時并不能得到良好的最優解。為了克服其缺點，本文提出了基于食物鏈機制的改進粒子群算法（DSPSO）。DSPSO引入了兩種機制，分別為食物鏈機制和繁殖機制，本章將對這兩種機制的構架及目的進行詳細的說明。

2.1 食物鏈機制

傳統的粒子群算法中，整個種群均以個體最優點和群體最優點為標榜進行進化，盡管這樣的處理能夠使算法擁有較快的收斂速度，但同時有可能使種群的多樣性快速流失，導致算法陷入局部收斂。另一方面，作為種群標榜的被記錄的個體最優點，也就是標榜群pbest中，有很多較差的個體最優點并不能夠為整個種群的進化作出貢獻，這些被記錄的個體最優點則需要被排除。由以上兩點可以看出，粒子群算法的性能很大程度上取決于標榜的選擇方式。因此，不僅僅是粒子群需要進化，標榜群也需要按照一定的規律進化并選取。

眾所周知，生物界能夠很好地保持物種的多樣性，其中最有特色的就是食物鏈。食物鏈的存在使得能量在生態系統中互相傳導，并且保證了各個物種在生物界的平衡。食物鏈機制通過模仿生物界的這種特點，對標榜群進行進化。在食物鏈機制中，整個標榜群被分為幾個子種群，每個子種群都能夠捕食另外一個子種群，但同時也會被第三個子種群捕食。在本文算法中，各個子種群的捕食結構為環形。在算法進化的每一代中，都會依次判斷各個子種群是否發生捕食現象，一旦發生捕食現象，當前子種群的最差粒子則被捕食，此時該粒子將被剔除，取而代之的則是捕食者所在子種群按繁殖機制所繁殖的標榜粒子，該標榜粒子則被劃入到捕食者所在種群。捕食是否發生則取決于捕食概率P，而P根據一定規則進行計算，該規則受生物界捕食規律啟發。對于每個子種群，若捕食者子種群適應度值大于被捕食者子種群適應度值，則代表捕食者子種群所在環境適合生存，當前被捕食者種群則更容易被捕食。捕食概率計算方案如下：

2.2 繁殖策略

繁殖是一種常見的自然現象，也是物種進化的關鍵很多算法，如差分進化算法、遺傳算法，都曾模仿過這種現象。在文獻[11]中，Liang等認為，對于一些已知的個體最優點，可能對于某些維所得位置已經非常接近全局最優點，但是由于其他維數得到的結果比較差而造成了整個的最優點有較差的適應度值，因此，本文模仿Liang等的全面學習機制構造了一種繁殖機制，其公式表現為：

在實驗對比仿真中，種群規模均設置為50，測試函數的維數均為30維，速度上限被設置為尋優范圍的0.1倍，DSPSO的子種群數量設置為5。每組實驗算法獨立計算25次，單個實驗中，算法在經過3.00E+5次函數計算次數后停止計算。需要注意的是，慣性權重在2.00E+5函數計算次數之前保持線性遞減，當函數計算次數大于2.00E+5后，慣性權重將保持0.4不變。各個算法的具體參數設置如表2所示。

需要注意的是，PSO、LPSO和DMSPSO的加速因子c1和c2分別被設置為2和1，與傳統的設置方法略有不同。對于CLPSO和DSPSO，如表2的設置方式使得算法具有良好的性能，如若令加速因子為2，算法的性能不佳。之所以在相同的參數下幾種算法的性能差異較大，是因為PSO、LPSO和DMSPSO采用的最優點粒子是傳統意義上的全局最優點和局部最優點，而CLPSO和DSPSO采用的則分別是全面學習機制遴選組合出的全面學習標榜粒子和食物鏈機制遴選出的標榜粒子，其算法本質決定了算法的社會學習因子并不能設置太高。因此對于CLPSO和DSPSO，其參數設置并沒有按照傳統的設置方法設置。為了使不同的算法具有可比性，本文同樣將PSO、LPSO和DMSPSO的加速因子c1和c2設置為2和1。而對于CLPSO，本文則采用文獻[12]中推薦的設置方法。

3.1 算法參數靈敏度分析

為了測試輔助最優點選擇周期period和輔助最優點選擇參數n對算法性能的影響，本文對參數period和n作靈敏度分析。首先將period和n分別設置為5、25，然后保持n為25不變，改變period。選出具有最好性能的period值之后保持period為最佳值不變，改變n值，最后得到最佳參數，其他參數設置如表2所示。實驗中以F1、F4、F5調整算法參數，對于每個測試函數與參數組合，實驗獨立執行10次，結果為10次實驗得到的最優適應度值的平均值，實驗結果如表3和表4所示。從實驗結果可以得知，當period和n分別為5和25時，算法具有良好性能。

3.2 算法性能分析

為了全面反映DSPSO的性能，本節選取了4種不同的改進粒子群算法作為對比來反映DSPSO的有效性。4種算法的參數設置、拓撲結構等見表2。仿真結果見表5、表6。表5中，平均精度代表算法在經過2.00E+5次函數計算后得到的適應度值與函數最優值偏差的均值，標準差代表2.00E+5次函數計算后得到的適應度值的標準差，最優值則為經過2.00E+5次函數計算后得到的適應度值與函數最優值偏差的最小值；T檢驗值為將DSPSO于其他算法進行比較后的T檢驗值，目的是為了驗證性能的提升是否有統計學意義；h則代表根據T檢驗值得到的DSPSO的性能是否得到了提升，以置信度95%為界，若提升則表示為“+”，具有相同的統計學意義則為“=”，否則為“-”。Rank代表各個算法的排名。表6列出了算法的成功率以及達到目標精度時的函數計算次數。

1）精度對比。

根據表5可以看出，DSPSO有著非常明顯的優勢。DSPSO擁有最高的平均排名，其值為1.9，而PSO，LPSO，DMSPSO和CLPSO的平均排名則分別為4.3、2.4、2.3和3.6，且對于大部分測試函數，DSPSO都優于其他四種改進算法。尤其是F2、F3、F6、F9，DSPSO得到的平均精度值都明顯地優于其他算法，且根據h值可以看出其提升大多數都具有統計意義。

但是從實驗結果中也可以看出，對于大多數測試函數，DSPSO并不能完全地優于其他四種改進算法，其Rank值多數都為2，但從算法獲得的最優值來看，對于這些函數DSPSO都能夠獲得比較優異的結果。可見，食物鏈機制的引入使得算法能夠保持良好的種群多樣性，從而使得算法不容易陷入局部最優，得到的結果更加接近真實的最優值，因此擁有較好的尋優精度。

2）尋優效率對比。

根據表6中的計算次數值可以看出，DSPSO效率要低于PSO、LPSO和DMSPSO。PSO、LPSO、DMSPSO、CLPSO和DSPSO的平均計算次數分別為46282.58、56566.40、76263.11、118978.00和103180.32。對于選出的10個測試函數，DSPSO擁有較高的函數計算次數。但DSPSO的尋優效率要明顯高于CLPSO。算法對函數F4、F6、F9的尋優過程的對比軌跡如圖1～3所示。

由此可見，食物鏈機制使得算法的精度有所提升，但使算法的尋優效率變低。食物鏈機制使得算法消耗一部分計算在食物鏈機制的執行上，因此相較于PSO、LPSO和DMSPSO而言，算法的尋優效率相對較低。

3）尋優結果可信度。

PSO、LPSO、DMSPSO、CLPSO和DSPSO的平均成功率分別為70.00%、90.00%、89.60%、100.00%和94.40%。DSPSO得到的結果具有較高的可信度，在解決這10個測試函數時，其中的9個問題都以100%的概率達到了目標精度，僅僅在解決F4時沒有達到100%。但是相對而言，CLPSO具有更好的可信度，對所有的尋優問題CLPSO均達到了100%的可信度。可見食物鏈機制能夠很好地抑制算法發生早熟收斂現象，提升算法的可信度。

4） 算法時間復雜度分析。

標準粒子群算法的時間復雜度為TPSO（N）=O（NDT），其中N、D、T分別為粒子總數、搜索維數和最大迭代次數。由于DSPSO引入了食物鏈機制和繁殖策略，因此其時間復雜度應為TPSO（N）=O（NDT）+ O（NT）。表7為各算法經過3.00E+5次函數計算次數后所消耗的時間，由結果可知，相對于PSO、LPSO和DMSPSO， DSPSO消耗的計算時間較長，擁有較高的計算復雜度。相對而言，CLPSO擁有最高的計算復雜度。

總體而言，盡管DSPSO算法還有一些不足，但它還是擁有不錯的性能，相對其他四種改進算法，DSPSO算法擁有非常優秀的精度和可信度。

4 結語

受生物界中的食物鏈機制啟發，本文提出了一種具有食物鏈結構的改進粒子群算法DSPSO。與PSO算法、局部版本的粒子群（LPSO）算法、動態多群粒子群（DMSPSO）算法和全面學習粒子群（CLPSO）算法相比，DSPSO擁有更好的尋優能力，更容易避免陷入早熟收斂；其得到的解質量好、尋優效率高、可信度高，具有更好的優越性。但是，DSPSO仍然有一些不足之處，它并不能完全超越其他改進粒子群算法，在解決多峰函數時并不能夠保證每次都能得到高質量的解，且計算復雜度相對較高。在以后的研究中，我們將就這些問題對DSPSO進行進一步改進，提升該算法的性能。

參考文獻：

[1]KENNDY J， EBERHART R. Particle swarm optimization[C]// Proceedings of the 4th IEEE International Conference on Neural Networks. Piscataway， NJ： IEEE， 1995： 1942-1948.

[2]饒興華， 王文格， 胡旭. 多樣性反饋與控制的粒子群優化算法[J]. 計算機應用， 2014， 34（2）：506-509.（RAO X H， WANG W G， HU X. Diversity feedback and control particle swarm optimization algorithm[J]. Journal of Computer Applications， 2014， 34（2）：506-509.）

[3]呂莉， 趙嘉， 孫輝. 具有反向學習和自適應逃逸功能的粒子群優化算法[J]. 計算機應用， 2015， 35（5）：1336-1341.（LYU L， ZHAO J， SUN H. Partical swarm optimization algorithm using oppositionbased learning and adaptive escape[J]. Journal of Computer Applications， 2015， 35（5）：1336-1341.）

[4]SHI Y， EBERHART R. A modified particle swarm optimizer[C]// Proceedings of the 1998 IEEE World Congress on Computational Intelligence. Piscataway， NJ： IEEE， 1998：69-73.

[5]ZHAN ZH， ZHANG J， LI Y， et al. Adaptive particle swarm optimization[J]. IEEE Transactions on Systems， Man， and Cybernetics， 2009， 39（6）： 1362-81.

[6]KENNEDY J， MENDES R. Population structure and particle swarm performance[C]// Proceedings of the 2002 Congress on Evolutionary Computation. Piscataway， NJ： IEEE， 2002：1671-1676.

[7]MENDES R， KENNEDY J， NEVES J. The fully informed particle swarm： simpler， maybe better[J]. IEEE Transactions on Evolutionary Computation， 2004， 8（3）： 204-210.

[8]LIANG J， SUGANTHAN P N. Dynamic multiswarm particle swarm optimizer[C]// Proceedings of the 2005 IEEE Swarm Intelligence Symposium. Piscataway， NJ： IEEE， 2005：124-129.

[9]BEHESHTI Z， SHAMSUDDIN S M H. CAPSO： Centripetal accelerated particle swarm optimization[J]. Information Sciences， 2014， 258：54-79.

[10]LIM W H， MATISA N A. Teaching and peerlearning particle swarm optimization[J]. Applied Soft Computing， 2014， 18（18）：39-58.

[11]ZHAN ZH， ZHANG J， LI Y， et al. Orthogonal learning particle swarm optimization[J]. IEEE Transactions on Evolutionary Computation， 2011， 15（6）： 832-847.

[12]LIANG J J， QIN A K， SUGANTHAN P N， et al. Comprehensive learning particle swarm optimizer for global optimization of multimodal functions [J]. IEEE Transactions on Evolutionary Computation， 2006， 10（3）： 281-295.

[13]REN Z， ZHANG A， WEN C， et al. A scatter learning particle swarm optimization algorithm for multimodal problems [J]. IEEE Transactions on Cybernetics， 2014， 44（7）： 1127-1140.

[14]SUGANTHAN P N， HANSEN N， LIANG J J， et al. Problem definitions and evaluation criteria for the CEC 2005 special session on realparameter optimization[R]. Singapore： Nanyang Technological University， 2005.