劉角 馬迪 馬騰波 張瑋

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

關(guān)鍵詞：粒子群優(yōu)化算法； 食物鏈機(jī)制；動態(tài)多物種

中圖分類號：TP301.6 文獻(xiàn)標(biāo)志碼：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 引言

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

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

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

2 基于食物鏈機(jī)制的動態(tài)多物種粒子群算法

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

2.1 食物鏈機(jī)制

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

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

2.2 繁殖策略

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

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

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

3.1 算法參數(shù)靈敏度分析

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

3.2 算法性能分析

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

1）精度對比。

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

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

2）尋優(yōu)效率對比。

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

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

3）尋優(yōu)結(jié)果可信度。

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

4） 算法時間復(fù)雜度分析。

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

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

4 結(jié)語

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

參考文獻(xiàn)：

[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]饒興華， 王文格， 胡旭. 多樣性反饋與控制的粒子群優(yōu)化算法[J]. 計算機(jī)應(yīng)用， 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]呂莉， 趙嘉， 孫輝. 具有反向?qū)W習(xí)和自適應(yīng)逃逸功能的粒子群優(yōu)化算法[J]. 計算機(jī)應(yīng)用， 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.