具有動態(tài)子空間的隨機單維變異粒子群算法*

鄧志誠，孫 輝,3+，趙 嘉,3，王 暉,3

1.南昌工程學院 信息工程學院，南昌 330099

2.江西省水信息協(xié)同感知與智能處理重點實驗室，南昌 330099

3.鄱陽湖流域水工程安全與資源高效利用國家地方聯(lián)合工程實驗室，南昌 330099

1 引言

為解決傳統(tǒng)優(yōu)化算法無法解決的復雜優(yōu)化問題，研究者們受螢火蟲閃爍吸引其他螢火蟲的行為啟發(fā)，提出螢火蟲算法（firefly algorithm，F(xiàn)A）；受蜜蜂采蜜行為啟發(fā)，提出人工蜂群算法（artificial bee colony，ABC）；受鳥群覓食行為啟發(fā)，提出粒子群優(yōu)化算法（particle swarm optimization，PSO）。

粒子群優(yōu)化算法是由Kennedy和Eberhart在1995年提出的群智能優(yōu)化算法[1-2]。該算法具備計算快速和易實現(xiàn)等優(yōu)點，作為群體智能算法的重要分支，得到了眾多學者廣泛深入的研究。且已應用于圖像處理[3-4]、工程設計[5]、無線傳感網(wǎng)絡[6-7]、經(jīng)濟和模式識別等眾多領域。

粒子群優(yōu)化算法具有高效、實現(xiàn)簡單等特點，已成功應用于許多現(xiàn)實優(yōu)化任務[8]，但存在多樣性差、易早熟收斂等問題，制約了粒子群優(yōu)化算法的發(fā)展。為克服上述問題，眾多學者進行了大量研究。文獻[9]通過檢測粒子健康度，自適應過濾懶惰粒子，并引入引導因子過濾異常粒子。文獻[10]在分析粒子群算法進化方程的基礎上，通過在振蕩環(huán)節(jié)采用互不相同的參數(shù)值調(diào)節(jié)算法的勘探與開發(fā)能力。文獻[11]在粒子只受全局最優(yōu)解影響的情況下，加入鎖定因子使粒子所受影響呈規(guī)律性，并與慣性權重配合，進一步提升算法性能。文獻[12]對種群粒子的運動軌跡進行分析，在標準PSO 速度更新公式上添加限制因子，確保種群收斂并提高收斂速度。文獻[13]按照當前全局最優(yōu)更新的次數(shù)是否達到預設門限值，將種群分為正常和早熟兩種狀態(tài)，當種群在正常狀態(tài)，采用固定慣性權重的標準PSO公式進化；在早熟狀態(tài)則引入矢量高斯學習策略，為精英粒子增加服從高斯分布的隨機步長，且精英粒子進行矢量高斯學習的維度隨種群的進化而減少，以增強種群多樣性。文獻[14]中采用列維飛行作為隨機擾動步長，算法首先為種群各粒子預設一個閥值，當粒子未能自我更新的次數(shù)達到預設的閥值時，則使粒子繞當前全局最優(yōu)做列維飛行，探索更多新區(qū)域；否則，按標準更新公式更新種群。

文獻[15]根據(jù)種群歷史最差和最好粒子的適應值，將當前每個粒子根據(jù)其適應值劃分不同等級，并分配對應的理想速度以更新粒子位置。算法給每個粒子分配專屬的慣性權重和加速因子，并把此三個參數(shù)作為問題的三個維度處理，將粒子當前位置到下一代位置的歐式距離絕對值定義為粒子的絕對速度，再根據(jù)粒子絕對速度和理想速度的關系更新三個參數(shù)。文獻[16]將標準PSO 位置更新公式中的速度項去除，以高斯變異項替代，并在種群中隨機選擇一定數(shù)量的粒子采用上述更新公式進化，以提高多樣性。文獻[17]結合隨機學習和列維飛行策略，在標準速度更新公式中增加一項，讓種群粒子以列維隨機步長向隨機選擇的粒子學習，在種群初始化后，當產(chǎn)生的隨機數(shù)小于預設閥值時，使用標準PSO 公式更新種群，否則使用改進的公式更新種群。文獻[18]在種群初始化階段，采用反向?qū)W習策略隨機初始化種群，取最優(yōu)粒子作為初始種群，并對位置更新公式進行改進，在先前位置、速度項增加慣性權重，并讓粒子向當前全局最優(yōu)學習，慣性權重、加速因子服從正余弦函數(shù)變化，以提高收斂速度。

上述算法采用整體維度更新策略，同時更新粒子每一維，可加快種群收斂速度。但是，在粒子的進化過程中，全局最優(yōu)值與普通粒子每一維的進化方向不總是一致，可能出現(xiàn)整體適應度值改善而粒子某一維退化，或粒子某一維改善而整體適應度值變差等問題。

針對上面所述問題，本文提出具有動態(tài)子空間的隨機單維變異粒子群優(yōu)化算法（stochastic single-dimensional mutated particle swarm optimization with dynamic subspace，SDMPSO）。為解決全局最優(yōu)與普通粒子進化方向不一致問題，提出具有動態(tài)子空間的隨機單維變異策略：從粒子的自身維度中隨機不重復地挑選若干維度組成子空間，子空間隨迭代次數(shù)的增加而減小，每次只隨機選擇異于子空間的一維進行變異，待變異的維度等于子空間內(nèi)各維度的平均值。同時，提出Pareto 速度分配策略：在算法設定的前20%迭代次數(shù)內(nèi)，增強種群的勘探能力，探索更多的新解空間區(qū)域，為后期的平衡搜索做準備；后80%迭代次數(shù)內(nèi)，保持種群的勘探能力與開發(fā)能力平衡，使種群進行有效的平衡搜索。

2 標準PSO

粒子群優(yōu)化算法將所求解空間位置，類比鳥群運動時棲息地。鳥群抽象為粒子群，鳥群間信息傳遞類比各粒子相互學習和信息共享的過程。運動過程中的狀態(tài)信息對種群運動速度產(chǎn)生影響，實質(zhì)為個體最優(yōu)（pbest）和全局最優(yōu)（gbest）控制粒子運動速度和方向，用數(shù)學形式實現(xiàn)該算法的過程如下。

設粒子數(shù)為N的種群，在維度為D的空間中搜索，粒子在解空間所處的位置可表示為xi=(xi1,xi2,…,xiD)，i=1,2,…,N，代表第i個粒子的位置，每個xi都可由目標函數(shù)求得函數(shù)值f(xi)。vi=(vi1,vi2,…,viD)，i=1,2,…,N，代表第i個粒子的速度。pbesti=(pbesti1,pbesti2,…,pbestiD)，i=1,2,…,N，代表第i個粒子所經(jīng)歷的歷史最優(yōu)位置。gbest=(gbest1,gbest2,…,gbestD)，代表整個種群的歷史最優(yōu)位置。粒子速度和位置可按照以下公式更新：

式中，慣性權重w控制粒子先前速度，平衡粒子局部和全局搜索能力，當w較大時，粒子的全局搜索能力較強，反之粒子的局部搜索能力較強。公式中c1、c2為學習因子（也叫加速因子），可使粒子具有自我學習和向其他優(yōu)秀粒子學習的能力，快速向最優(yōu)解靠近。r1、r2為（0,1）內(nèi)的隨機數(shù)為粒子i在第t次迭代時歷史最優(yōu)位置的第j維為第t次迭代時整個種群歷史最優(yōu)位置的第j維。

3 提出的新算法

3.1 Pareto速度分配策略

意大利經(jīng)濟學家Pareto 認為，在任何一組事件中，最重要的占其中一小部分，約20%，其余80%盡管是多數(shù)，卻是次要的，這就是Pareto定律[19]。這種統(tǒng)計的不平衡性在社會、經(jīng)濟及生活中無處不在。由Pareto定律可知，分析或處理問題時不平均用力，要把80%的資源或精力用于求解占問題約20%的重要部分。

勘探與開發(fā)是種群進化的兩個重要搜索能力?？碧侥芰姡N群能探索到更多解空間區(qū)域，提高尋得最優(yōu)解的概率；開發(fā)能力強，種群可對最優(yōu)解所在區(qū)域進行精細搜索，提高尋得最優(yōu)解的精度。然而，當算法勘探能力強的階段持續(xù)時間過長，易導致種群收斂速度緩慢或錯過最優(yōu)解；算法開發(fā)能力強的階段持續(xù)時間過長，則易導致種群早熟收斂而陷入局部最優(yōu)。因此，保持算法勘探與開發(fā)能力相等的平衡搜索，是算法優(yōu)化性能提升的關鍵。而且，算法在未經(jīng)過充分勘探，未獲得更多新解空間區(qū)域的情況下，將降低平衡搜索的效率。

針對上述問題，根據(jù)Pareto定律指導算法在整個迭代過程的搜索狀態(tài)。Pareto 定律的關鍵是明確問題的主要任務。從種群的搜索狀態(tài)看，主要任務是保持勘探搜索與開發(fā)搜索的平衡。因此，依據(jù)Pareto定律，在算法設定的前20%迭代次數(shù)內(nèi)，增強種群的勘探能力，探索更多的新解空間區(qū)域，為后期的平衡搜索做準備；后80%迭代次數(shù)內(nèi)，保持種群的勘探能力與開發(fā)能力平衡，使種群進行有效的平衡搜索。上述過程可用如下公式實現(xiàn)：

式中，t表示當前迭代次數(shù)，Max_t表示最大迭代次數(shù)。c3=2+exp(-t/Max_t)+0.5，c4=0.5-exp(-t/Max_t)+2.0為加速因子。為收縮因子。c5=c6=2，χ2=0.6，r3、r4、r5、r6為（0,1）間的隨機數(shù)。

傳統(tǒng)PSO 算法具有一些不良的動力學特性，特別需要限制粒子的速度以控制它們的軌跡[20]。因此，式（3）、式（4）引入收縮因子限制粒子的速度。文獻[21]指出，自我認知項大于社會認知項，將導致搜索空間中的粒子過度徘徊。式（3）利用這一特性，使加速因子c3大于c4，增大自我認知項，使粒子能探索更廣的解空間區(qū)域。為使粒子保持自我認知項等于社會認知項的平衡搜索，設置式（4）中加速因子c5等于c6。

3.2 具有動態(tài)子空間的隨機單維變異策略

傳統(tǒng)PSO 算法采用整體維度更新策略，粒子每一維的值同時更新。但是，全局最優(yōu)值的進化方向與普通粒子每一維的進化方向不總是一致，將出現(xiàn)整體適應度值改善而粒子某一維退化，或粒子某一維改善而整體適應度值變差等問題。

為不失一般性，仍以最小為最優(yōu)，當D=5 時，該函數(shù)的最優(yōu)解為（0,0,0,0,0）。當在解空間中存在某個粒子的位置為xt(1,0,2,4,3)時，f(xt)=30，根據(jù)PSO 算法公式更新后，若粒子維度變?yōu)閤t+1(0,4,0,4,0)，此時f(xt+1)=32。由于f(xt+1)>f(xt)，xt+1(0,4,0,4,0)將不會作為最優(yōu)解保留。相比xt的維度值，xt+1的第1、3 和5 維都有較大改善，但僅因第2 維退化而使整個粒子的適應值變差。

針對此問題，提出具有動態(tài)子空間的隨機單維變異策略：從粒子的自身維度中，隨機不重復地挑選若干維度組成子空間，子空間的大小隨迭代次數(shù)的增加而逐漸減小，每次只隨機選擇異于子空間的一維進行變異，其值等于子空間內(nèi)各維度的平均值。具體可用下式表示：

式（5）中，int 表示取整函數(shù)，t表示算法當前迭代次數(shù)，Max_t表示最大迭代次數(shù)，d∈(1,2,…,D-1)為子空間內(nèi)的總維度數(shù)。式（5）表示子空間內(nèi)的總維度數(shù)d隨迭代次數(shù)的增加而減少。式（6）中，rand1_j∈D為維度D內(nèi)隨機選擇的一維。rand2_ji為進行第i次隨機不重復的挑選時，從粒子維度D內(nèi)挑選的第rand2_j維，rand1_j≠rand2_ji。式（6）表示只隨機選擇粒子異于子空間的一維進行變異，其值等于子空間內(nèi)各維度的平均值。

通過單維變異的方式，使某一維的進化不影響其他維。同時，單維變異沒有破壞粒子群的整體結構，不影響粒子群正在進行的局部精細搜索。粒子進化到后期，只有某一維或某幾維未達到最優(yōu)解，單維變異可針對某一較差維度進行變異，能有效地提升收斂速度并得到更高質(zhì)量解。

3.3 新算法原理

種群粒子在進化過程中，追隨個體最優(yōu)（pbest）和全局最優(yōu)（gbest）運動，個體最優(yōu)代表種群進化到當前代時最優(yōu)的位置群體，全局最優(yōu)從個體最優(yōu)中產(chǎn)生。本文提出的具有動態(tài)子空間的隨機單維變異策略，從粒子自身維度中，隨機選取若干維度組成子空間，粒子擁有優(yōu)質(zhì)的維度值，對變異產(chǎn)生高質(zhì)量解至關重要。

因此，為保證進行變異粒子的維度質(zhì)量，本文選擇所有個體最優(yōu)和全局最優(yōu)粒子進行變異。具體可用下式表示：

在算法求得個體最優(yōu)和全局最優(yōu)后，分別對這兩類優(yōu)質(zhì)粒子進行變異，增強種群的多樣性。該策略隨機選擇pbest和gbest的某一維進行變異，“隨機”的不確定性，可能導致原優(yōu)質(zhì)維度值被舍棄，替換成變異后的低質(zhì)量維度值。pbest和gbest變異后，直接通過自我認知項和社會認知項影響粒子速度。因此，本文的速度更新公式，選擇具有收縮因子的式（3）和式（4），作為新速度更新模型，收縮因子同時控制先前速度項、自我認知項和社會認知項。文獻[12]指出，當隨機性被引入具有收縮因子的完整模型時，隨機性帶來的有害影響將被控制。新算法運行步驟可用如下偽代碼表示。

4 算法分析

4.1 Pareto速度分配策略分析

算法依據(jù)Pareto定律，在算法設定的前20%的迭代次數(shù)內(nèi)，增強種群的勘探能力，探索更多的新解空間區(qū)域，為后期的平衡搜索做準備；后80%的迭代次數(shù)內(nèi)，保持種群的勘探能力與開發(fā)能力平衡，使種群進行有效的平衡搜索。

為驗證采用Pareto速度分配策略，能更有效地提高算法的優(yōu)化性能，記該速度分配策略為2/8，將其與速度分配策略分別為1/9、3/7、4/6、5/5、9/1、8/2、7/3、6/4、1/0 和0/1 的策略進行比較，實驗選取12 個常用的測試函數(shù)Sphere(f1)、Schwefel's P2.22(f2)、Schwefel's P1.2(f3)、Schwefel's P2.21(f4)、Rosenbrock(f5)、Step(f6)、Quartic(f7)、Schwefel's P2.26(f8)、Rastrigin(f9)、Ackley(f10)、Griewank(f11)、Penalized1(f12)，在維度D=30，評估次數(shù)為20萬次的條件下進行比較，算法獨立運行30 次，Mean 表示30 次運行的最優(yōu)解平均值，Std表示標準差，所得結果見表1所示。

表1 中，本文采取的2/8 策略在5 個函數(shù)上取得最優(yōu)解，在另兩個函數(shù)上取得的Mean比其他策略更優(yōu)，將各策略最優(yōu)解平均值進行Friedman檢驗，所得表2 中2/8 策略下秩均值最?。?.33），驗證了該策略能更有效提高算法的優(yōu)化性能。

4.2 動態(tài)子空間策略分析

粒子進化前期，多數(shù)維度未到達最優(yōu)解位置，存在少數(shù)離最優(yōu)解較近的維度；在進化后期，若粒子陷入局部最優(yōu)，其多數(shù)維度已到達最優(yōu)解位置，只存在少數(shù)未到達最優(yōu)解位置的維度。為證明此現(xiàn)象，對標準PSO 算法在10 維條件下，對Shifted and Rotated Schwefel’s Function 進行測試，迭代次數(shù)為2 500 代，可行域[-100，100]。選種群當前最優(yōu)粒子（gbest）為研究對象，記錄其在100和2 400代的維度信息，繪制成圖1和圖2。

圖中橫坐標D_1～D_10 表示gbest的10 個維度，縱坐標表示各維度的維度值，柱狀圖為gbest所得各維度的具體數(shù)值，折線為函數(shù)在各維度的最優(yōu)值（optimum）。由圖1和圖2可知，gbest在100代時，第1、4、5 和第7 維離最優(yōu)解位置相對較近，其他維度相對較遠；gbest在2 400 代時，第1、2、3、4、5、7、8 和第10維離最優(yōu)解位置相對較近。

因此，本文采取的策略中，子空間大小動態(tài)變化，在粒子進化前期選取多數(shù)維度組成子空間，增大變異維度的多樣性，使粒子探索更多新區(qū)域；后期選取少數(shù)維度組成子空間，使維度變異不過于激進，增強粒子精細搜索的能力。

為驗證動態(tài)子空間策略能更有效平衡勘探與開發(fā)能力，將其與子空間大小固定的策略進行比較，在維度D=10 的條件下，分別固定1,2,…,10 維作為子空間大小，與動態(tài)子空間策略在12 個常用測試函數(shù)上進行比較，評估次數(shù)設為10萬次。為方便書寫，記動態(tài)子空間策略為Dyn_D，子空間大小固定的策略分別記為D_1～D_10，各策略獨立運行30 次，結果見表3所示。

Table 1 Speed allocation strategy test results表1 各速度分配策略測試結果

Table 2 Friedman test result表2 Friedman 檢驗結果

Fig.1 Dimension value in 100 generations圖1 100代時維度值

Fig.2 Dimension value in 2400 generations圖2 2 400代時維度值

動態(tài)子空間策略與其他10種子空間大小固定的策略相比，在7 個函數(shù)上取得的最優(yōu)解更優(yōu)，將表4中所得平均值進行Friedman 檢驗，動態(tài)子空間策略所得秩均值最?。?.21），驗證了本文采用動態(tài)子空間策略的綜合優(yōu)化性能更強。

Table 3 Comparison results between dynamic subspace and fixed subspace strategy表3 動態(tài)子空間與固定子空間策略比較結果

Table 4 Friedman test result表4 Friedman 檢驗結果

5 仿真實驗

5.1 測試函數(shù)與參數(shù)設置

引入26 個基準函數(shù)進行仿真實驗，函數(shù)分為4類：f1、f2、f4、f15、f16、f17、f18、f19和f20為單模函數(shù)，f3在低維時為單模函數(shù)，高維時為多模函數(shù)；f5、f6、f7、f8、f9、f10、f21、f22、f23、f24、f25和f26為多模函數(shù)；f11、f12、f13和f14為旋轉(zhuǎn)函數(shù)。表5中列出了26個測試函數(shù)的基本信息。本文算法（SDMPSO）的參數(shù)設置如下：種群規(guī)模N設置為20，Max_t表示最大迭代次數(shù)，t表示當前迭代次數(shù)。在種群進化的前20%×Max_t的迭代次數(shù)內(nèi)，加速因子c3=2+exp(-t/Max_t)+0.5，c4=0.5-exp(-t/Max_t)+2.0，收縮因子在后80%×Max_t的迭代次數(shù)內(nèi)，加速因子c1=c2，收縮因子χ3=0.6。各對比算法的參數(shù)設置參照文獻[20]。

5.2 數(shù)值仿真實驗

將SDMPSO 再與7 種知名PSO 改進算法分別在維度D=30,50,100 的條件下對比，這7 種算法分別為LFPSO（particle swarm optimization algorithm with Levy flight）[14]、RPSOLF（particle swarm optimization algorithm with random learning mechanism and Levy flight）[17]、H-PSO-SCAC（hybrid particle swarm optimizer with sine cosine acceleration coefficients）[18]、HPSO-TVAC（self- organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients）[21]、CLPSO（comprehensive learning particle swarm optimizer）[22]、DMS-PSO（dynamic multi-swarm particle swarm opt-imizer）[23]、PSOLF（particle swarm optimization with Levy flight）[24]。各算法的參數(shù)都按照原文獻設置，當D=30 時，評估次數(shù)設為20 萬次；D=50 時，評估次數(shù)設為25 萬次；D=100 時，評估次數(shù)設為50 萬次。所有算法獨立運行30 次，最終結果取30 次的平均值，具體實驗數(shù)據(jù)見表6～表8所示，表中Mean表示平均最優(yōu)適應值，標準差用Std 表示，最好值在表中用粗體標示。

Table 5 Benchmark function表5 測試函數(shù)

續(xù)表

表6～表8 中實驗數(shù)據(jù)來源如下：CLPSO、DMS-PSO 在維度為30、50、100 時，所測試函數(shù)f1、f2、f3、f4、f6、f7、f8、f9和f10的數(shù)據(jù)引自文獻[25]；f5、f11、f12、f13和f14在30、50 維的數(shù)據(jù)引自文獻[17]和文獻[26]。HPSO-TVAC 在30 維的數(shù)據(jù)引自文獻[17]。LFPSO、PSOLF 在30、50 維的數(shù)據(jù)引自文獻[24]；PSOLF 在100 維時，f1、f2、f3、f4、f6和f8的數(shù)據(jù)引自文獻[24]。RPSOLF 在30 維時數(shù)據(jù)引自文獻[17]。H-PSO-SCAC在30和50維時，f3、f4、f6、f7、f8的數(shù)據(jù)引自文獻[18]。表中剩余未提及的函數(shù)數(shù)據(jù)，原文獻未進行測試，為筆者按文獻的思路實現(xiàn)所得，并在表中用“*”在數(shù)據(jù)右上角標示。

分析表6～表8數(shù)據(jù)，得出以下結論：

（1）SDMPSO算法性能分析

在相同評估次數(shù)下，SDMPSO算法在D=30、50、100 維時，所測函數(shù)f1、f2、f6、f8、f12、f13和f14全部求得最優(yōu)解，所測函數(shù)f9和f10同樣求得比其他算法更高質(zhì)量的解，測試f3、f4和f5函數(shù)所得最優(yōu)解相比其他算法優(yōu)勢明顯。雖測試維度升高，算法仍能保持較好優(yōu)化性能。

（2）其他算法優(yōu)化性能分析

CLPSO 在測試函數(shù)f5時優(yōu)勢明顯，測試其余函數(shù)時，在30 維能夠取得較好質(zhì)量解，但在50、100 維時算法性能有待加強。CLPSO主要借助不同的個體最優(yōu)（pbest）優(yōu)勢信息產(chǎn)生最優(yōu)解，但因其在搜索過程中種群常更新停滯，早熟收斂仍是CLPSO 需解決的問題。

HPSO-TVAC算法引入時變的加速因子控制“社會認知”和“自我認知項”，但當進化后期粒子聚集時，難以逃離局部最優(yōu)。DMS-PSO 算法將種群中粒子分為多個子種群，通過各子種群的信息交流以平衡算法勘探與開發(fā)能力，但各子種群的協(xié)作能力仍有待提高。HPSO-TVAC 和DMS-PSO 在測試函數(shù)f9、f10時優(yōu)勢明顯，測試其余函數(shù)時，上述算法在低維時能求得較好質(zhì)量的解，在高維搜索時算法易陷入局部最優(yōu)。

Table 6 30-dimensional test results表6 30維的測試結果

Table 7 50-dimensional test results表7 50維的測試結果

續(xù)表

Table 8 100-dimensional test results表8 100維的測試結果

LFPSO、PSOLF、RPSOLF都采用列維飛行策略，使種群增加隨機步長，其中LFPSO 使種群粒子繞著最優(yōu)解做列維飛行，在算法后期種群易更新停滯，故LFPSO 在低維時測試單模和多模函數(shù)，搜索到最優(yōu)解的質(zhì)量較高，但在高維仍易陷入局部最優(yōu)。PSOLF 和RPSOLF 則另增加了隨機選擇策略，在一定概率范圍內(nèi)使用列維飛行策略，在測試函數(shù)f1、f2、f6、f8、f12、f13和f14時求得函數(shù)最優(yōu)解，但在高維條件下測試f9、f10時算法仍陷入局部最優(yōu)。

H-PSO-SCAC采用sin、cosine函數(shù)控制加速因子的變化，并在使用反向?qū)W習初始化種群后，采用改進的速度更新公式，其在優(yōu)化函數(shù)f4時，能夠取得較高質(zhì)量的解，在函數(shù)f1、f2、f6、f8、f12、f13、f14同樣求得函數(shù)最優(yōu)解，但在測試函數(shù)f9和f10時，算法仍陷入局部最優(yōu)。

（3）各算法性能統(tǒng)計分析

為進一步綜合評價SDMPSO 算法的性能，引入Friedman 檢驗分析所得測試數(shù)據(jù)，秩均值作為Friedman 檢驗的評價參數(shù)，該值越小，表明算法的性能更優(yōu)。表9 給出各算法數(shù)據(jù)經(jīng)Friedman 檢驗后的秩均值，并在小括號內(nèi)給出其在所有算法中的排名。表中SDMPSO 算法在維度D=30、50 和100 維時，所得秩均值最小，故該算法性能更優(yōu)。H-PSO-SCAC、RPSOLF、PSOLF 算法在維度逐漸增高時，其在多數(shù)函數(shù)上都能保持較好的優(yōu)化性能，在少數(shù)復雜多模函數(shù)上，優(yōu)化性能逐漸下降。CLPSO、HPSO-TVAC、DMS-PSO、LFPSO 算法在維度逐漸增高后，各算法在測試函數(shù)上的優(yōu)化性能逐漸下降。

Table 9 Friedman test result表9 Friedman 檢驗結果

在Wilcoxon檢驗中，P-values小于0.05則表示兩對比算法存在顯著差異。表10 顯示，SDMPSO 在30、50 和100 維時，顯著優(yōu)于CLPSO、HPSO-TVAC、DMS-PSO和LFPSO。

Table 10 Wilcoxon test result表10 Wilcoxon 檢驗結果

5.3 收斂性分析

圖3（a）～圖3（n）中，在維度為30，評估次數(shù)20萬次的條件下，對SDMPSO 算法與CLPSO、HPSO-TVAC、DMS-PSO、LFPSO、PSOLF、RPSOLF 和H-PSO-SCAC算法，在函數(shù)f1～f14優(yōu)化過程中的收斂性能進行分析，圖中橫坐標FEs 表示評估次數(shù)，F(xiàn)itness 表示算法所得適應值。

在單模函數(shù)Sphere、Schwefel2.22 上，所有算法在Sphere 函數(shù)上都能夠求得較高精度解，但SDMPSO 算法求得最優(yōu)解所用評估次數(shù)更少，收斂速度最快。在Schwefel2.22 上，DMS-PSO 算法未能求得最優(yōu)解，其余算法能求得較高精度解，但消耗的評估次數(shù)比SDMPSO算法多。

在單模函數(shù)Rosenbrock、Quartic上，H-PSO-SCAC的優(yōu)化性能突出，能求得比其他算法更高精度解。SDMPSO 算法相比其他算法，收斂到較有優(yōu)勢的解且收斂速度較快。

在多模函數(shù)Schwefel2.26上，CLPSO的優(yōu)化性能相比其他算法優(yōu)勢明顯，所求解的精度最高，收斂速度最快。SDMPSO對此函數(shù)的優(yōu)化能力相比其他函數(shù)較有優(yōu)勢。

在多模函數(shù)Rastrigin、Ackley、Griewank 上，SDMPSO、PSOLF、RPSOLF 和H-PSO-SCAC 都能求得最優(yōu)解，SDMPSO相比其他算法在收斂速度上，有較大優(yōu)勢。其余算法收斂速度慢，且收斂精度低。

Fig.3 Graph of function convergence圖3 函數(shù)收斂曲線圖

在多模函數(shù)Penalized1、Penalized2 上，H-PSO-SCAC 和PSOLF 收斂精度較低，其他算法能夠收斂到較高精度的解，SDMPSO算法的收斂速度更快，精度更高。

在旋轉(zhuǎn)函數(shù)Rotated Schwefel2.26 上，PSOLF 的收斂精度最高，SDMPSO 相比其他算法收斂速度和精度有較大優(yōu)勢。在旋轉(zhuǎn)函數(shù)Rotated Rastrigin、Rotated Ackley、Rotated Griewank 上，SDMPSO、PSOLF、RPSOLF 和H-PSO-SCAC 都能求得最優(yōu)解，SDMPSO 在收斂速度上優(yōu)勢明顯，其余算法未能求得最優(yōu)解。

5.4 與相關新算法比較

近年來，在智能計算領域，另提出了許多較有優(yōu)勢的算法[27]，且已成功應用于工程實踐。人工蜂群算法（ABC）是Karaboga受蜜蜂覓食啟發(fā)，于2005年提出的新智能算法，該算法具有較好的勘探能力，在解決高維和多模問題時優(yōu)勢明顯。文獻[28-29]在多組不同特性的Benchmark函數(shù)上，將ABC算法與主流的智能算法遺傳算法（genetic algorithm，GA）、差分進化算法（differential evolution，DE）和PSO 等算法進行比較，結果表明ABC算法在處理復雜多模函數(shù)上性能更優(yōu)。

ABC 算法每次只選擇父代的一維進行變異，本文算法同樣采用單維變異的策略得出新的粒子位置。因此，為進一步驗證算法的優(yōu)化性能，選取新改進的人工蜂群算法：GABC（gbest-guided artificial bee colony algorithm）[30]、qABC（quick artificial bee colony algorithm）[31]、best-so-far ABC（best-so-far selection in artificial bee colony algorithm）[32]、dABC（directed artif-icial bee colony algorithm）[33]、MABC（modified artificial bee colony algorithm）[34]和MPGABC（modified Gbest-guided artificial bee colony algorithm）[35]算法在22 個基準測試函數(shù)上進行比較，測試維度為100 維，評估次數(shù)為500 000次。所有算法獨立運行25次，最終結果取25次的平均值，具體實驗數(shù)據(jù)見表11所示，表中Mean為平均最優(yōu)適應值，標準差用Std 表示，最好值在表中用粗體標示。表中數(shù)據(jù)來源和參數(shù)設置參考文獻[35]。

分析表11數(shù)據(jù)，得出以下結論：

（1）SDMPSO算法性能分析

在D=100 維時，算法所測函數(shù)f1、f6、f8、f19、f21和f20全部求得最優(yōu)解，在f2、f4、f9、f15、f16、f18、f20、f23、f24和f25函數(shù)上同樣求得高質(zhì)量解，其余函數(shù)相比其他算法也有較大優(yōu)勢。

（2）其他算法優(yōu)化性能分析

在D=100 維時，GABC在函數(shù)f6、f19、f21、f25和f26上全部求得最優(yōu)解，在f5和f20函數(shù)求得高質(zhì)量解，其余函數(shù)上優(yōu)化性能較好。qABC、best-so-far ABC 和dABC 在函數(shù)f19、f25和f26上全部求得最優(yōu)解，在f20函數(shù)上求得解質(zhì)量較高，對其余函數(shù)的優(yōu)化性能有待加強。MABC 在函數(shù)f19、f6、f21、f24、f25和f26上取得最優(yōu)解，在f7、f9、f10、f20和f23函數(shù)上取得高質(zhì)量解，其余函數(shù)上求得解優(yōu)勢較大。MPGABC 在函數(shù)f6、f19、f21、f25和f26上求得最優(yōu)解，在f3、f9、f10、f17、f20和f23函數(shù)上求得解質(zhì)量較高，其余函數(shù)上求得解優(yōu)勢明顯。

（3）各算法性能統(tǒng)計分析

對表11 中所得數(shù)據(jù)進行Friedman 檢驗分析，表12 列出各算法數(shù)據(jù)經(jīng)Friedman 檢驗后的秩均值，并在小括號內(nèi)給出所有算法的排名。表中，SDMPSO算法在維度D=100 維時，所得秩均值最小，故該算法綜合優(yōu)化性能更強。在Wilcoxon檢驗中，P-values小于0.05則表示兩對比算法存在顯著差異。表12中顯示SDMPSO在100維時，顯著優(yōu)于qABC和dABC算法。

群智能算法經(jīng)過近幾年的大量研究，絕大多數(shù)改進算法對較早版本的基準測試函數(shù)有較好優(yōu)化效果。因此，本文采用新近提出的測試函數(shù)CEC 2015[36]進一步驗證算法的優(yōu)化性能，其包含的15 個測試函數(shù)中，所有函數(shù)在各個維度的最優(yōu)解都不相同。將SDMPSO分別與新近提出的改進螢火蟲算法VSSFA（variable step size firefly algorithm）[37]、WSSFA（wise step strategy for firefly algorithm）[38]、螢火蟲與粒子群混合優(yōu)化算法（hybrid firefly and particle swarm optim-ization algorithm，F(xiàn)FPSO）[39]比較，維度D=30，評估次數(shù)為1 500。

表13為各算法在CEC 2015測試函數(shù)上，獨立運行30次后所得平均最優(yōu)適應值。SDMPSO算法在所測15 個函數(shù)中，有6 個函數(shù)占較大優(yōu)勢。表14 對各算法進行Friedman 檢驗，SDMPSO 算法所得秩均值最小，再次驗證SDMPSO 對新測試函數(shù)同樣具有較好優(yōu)化效果。

Table 11 100-dimensional data表11 100維數(shù)據(jù)

Table 12 Result of Friedman and Wilcoxon test表12 Friedman和Wilcoxon檢驗結果

Table 13 Mean optimum of CEC 2015 experiment表13 CEC 2015 平均最優(yōu)適應值

Table 14 Result of Friedman test表14 Friedman檢驗結果

6 結束語

針對粒子群算法采用整體維度更新策略，易存在某一維或某幾維未達到最優(yōu)解而導致粒子整體適應值變差等問題。本文主要提出兩種改進策略：（1）提出Pareto 速度分配策略控制算法在整個迭代過程的搜索狀態(tài)，在前20%的迭代次數(shù)內(nèi)，探索新解空間區(qū)域，為后80%迭代次數(shù)內(nèi)進行平衡搜索做準備，提高搜索的效率。（2）提出具有動態(tài)子空間的隨機單維變異策略，每次只隨機選擇粒子的一維進行變異，其值等于子空間內(nèi)各維度的平均值。通過子空間的動態(tài)調(diào)整，得到高質(zhì)量的變異值，改善粒子的整體維度質(zhì)量。

將本文算法在30、50 和100 維的條件下，與新近改進的高水平粒子群算法在單模、多模和旋轉(zhuǎn)函數(shù)上進行比較。數(shù)值實驗結果表明，本文算法在收斂精度和收斂速度上高于其他粒子群算法。同時與改進的人工蜂群算法和螢火蟲算法進行比較，實驗結果同樣表明本文算法優(yōu)化性能更強。但是，算法在處理某些高維復雜函數(shù)時仍易陷入局部最優(yōu)。因此，在下一步的研究工作中，將在挑選變異的維度方面，可提出新的策略替代隨機挑選的方式，進一步提高變異的效率。