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

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

1.南昌工程學(xué)院 信息工程學(xué)院，南昌 330099

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

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

1 引言

為解決傳統(tǒng)優(yōu)化算法無法解決的復(fù)雜優(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]。該算法具備計算快速和易實(shí)現(xiàn)等優(yōu)點(diǎn)，作為群體智能算法的重要分支，得到了眾多學(xué)者廣泛深入的研究。且已應(yīng)用于圖像處理[3-4]、工程設(shè)計[5]、無線傳感網(wǎng)絡(luò)[6-7]、經(jīng)濟(jì)和模式識別等眾多領(lǐng)域。

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

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

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

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

2 標(biāo)準(zhǔn)PSO

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

設(shè)粒子數(shù)為N的種群，在維度為D的空間中搜索，粒子在解空間所處的位置可表示為xi=(xi1,xi2,…,xiD)，i=1,2,…,N，代表第i個粒子的位置，每個xi都可由目標(biāo)函數(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)位置。粒子速度和位置可按照以下公式更新：

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

3 提出的新算法

3.1 Pareto速度分配策略

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

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

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

式中，t表示當(dāng)前迭代次數(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）間的隨機(jī)數(shù)。

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

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

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

為不失一般性，仍以最小為最優(yōu)，當(dāng)D=5 時，該函數(shù)的最優(yōu)解為（0,0,0,0,0）。當(dāng)在解空間中存在某個粒子的位置為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 維退化而使整個粒子的適應(yīng)值變差。

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

式（5）中，int 表示取整函數(shù)，t表示算法當(dāng)前迭代次數(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)隨機(jī)選擇的一維。rand2_ji為進(jìn)行第i次隨機(jī)不重復(fù)的挑選時，從粒子維度D內(nèi)挑選的第rand2_j維，rand1_j≠rand2_ji。式（6）表示只隨機(jī)選擇粒子異于子空間的一維進(jìn)行變異，其值等于子空間內(nèi)各維度的平均值。

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

3.3 新算法原理

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

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

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

4 算法分析

4.1 Pareto速度分配策略分析

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

為驗證采用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 的策略進(jìn)行比較，實(shí)驗選取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萬次的條件下進(jìn)行比較，算法獨(dú)立運(yùn)行30 次，Mean 表示30 次運(yùn)行的最優(yōu)解平均值，Std表示標(biāo)準(zhǔn)差，所得結(jié)果見表1所示。

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

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

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

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

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

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

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

Table 2 Friedman test result表2 Friedman 檢驗結(jié)果

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中所得平均值進(jìn)行Friedman 檢驗，動態(tài)子空間策略所得秩均值最小（5.21），驗證了本文采用動態(tài)子空間策略的綜合優(yōu)化性能更強(qiáng)。

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

Table 4 Friedman test result表4 Friedman 檢驗結(jié)果

5 仿真實(shí)驗

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

引入26 個基準(zhǔn)函數(shù)進(jìn)行仿真實(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ù)設(shè)置如下：種群規(guī)模N設(shè)置為20，Max_t表示最大迭代次數(shù)，t表示當(dāng)前迭代次數(shù)。在種群進(jìn)化的前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ù)設(shè)置參照文獻(xiàn)[20]。

5.2 數(shù)值仿真實(shí)驗

將SDMPSO 再與7 種知名PSO 改進(jìn)算法分別在維度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ù)都按照原文獻(xiàn)設(shè)置，當(dāng)D=30 時，評估次數(shù)設(shè)為20 萬次；D=50 時，評估次數(shù)設(shè)為25 萬次；D=100 時，評估次數(shù)設(shè)為50 萬次。所有算法獨(dú)立運(yùn)行30 次，最終結(jié)果取30 次的平均值，具體實(shí)驗數(shù)據(jù)見表6～表8所示，表中Mean表示平均最優(yōu)適應(yīng)值，標(biāo)準(zhǔn)差用Std 表示，最好值在表中用粗體標(biāo)示。

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

續(xù)表

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

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

（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 維時算法性能有待加強(qiáng)。CLPSO主要借助不同的個體最優(yōu)（pbest）優(yōu)勢信息產(chǎn)生最優(yōu)解，但因其在搜索過程中種群常更新停滯，早熟收斂仍是CLPSO 需解決的問題。

HPSO-TVAC算法引入時變的加速因子控制“社會認(rèn)知”和“自我認(rèn)知項”，但當(dāng)進(jìn)化后期粒子聚集時，難以逃離局部最優(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維的測試結(jié)果

Table 7 50-dimensional test results表7 50維的測試結(jié)果

續(xù)表

Table 8 100-dimensional test results表8 100維的測試結(jié)果

LFPSO、PSOLF、RPSOLF都采用列維飛行策略，使種群增加隨機(jī)步長，其中LFPSO 使種群粒子繞著最優(yōu)解做列維飛行，在算法后期種群易更新停滯，故LFPSO 在低維時測試單模和多模函數(shù)，搜索到最優(yōu)解的質(zhì)量較高，但在高維仍易陷入局部最優(yōu)。PSOLF 和RPSOLF 則另增加了隨機(jī)選擇策略，在一定概率范圍內(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習(xí)初始化種群后，采用改進(jìn)的速度更新公式，其在優(yōu)化函數(shù)f4時，能夠取得較高質(zhì)量的解，在函數(shù)f1、f2、f6、f8、f12、f13、f14同樣求得函數(shù)最優(yōu)解，但在測試函數(shù)f9和f10時，算法仍陷入局部最優(yōu)。

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

為進(jìn)一步綜合評價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ù)復(fù)雜多模函數(shù)上，優(yōu)化性能逐漸下降。CLPSO、HPSO-TVAC、DMS-PSO、LFPSO 算法在維度逐漸增高后，各算法在測試函數(shù)上的優(yōu)化性能逐漸下降。

Table 9 Friedman test result表9 Friedman 檢驗結(jié)果

在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 檢驗結(jié)果

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)化過程中的收斂性能進(jìn)行分析，圖中橫坐標(biāo)FEs 表示評估次數(shù)，F(xiàn)itness 表示算法所得適應(yīng)值。

在單模函數(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 與相關(guān)新算法比較

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

ABC 算法每次只選擇父代的一維進(jìn)行變異，本文算法同樣采用單維變異的策略得出新的粒子位置。因此，為進(jìn)一步驗證算法的優(yōu)化性能，選取新改進(jìn)的人工蜂群算法：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 個基準(zhǔn)測試函數(shù)上進(jìn)行比較，測試維度為100 維，評估次數(shù)為500 000次。所有算法獨(dú)立運(yùn)行25次，最終結(jié)果取25次的平均值，具體實(shí)驗數(shù)據(jù)見表11所示，表中Mean為平均最優(yōu)適應(yīng)值，標(biāo)準(zhǔn)差用Std 表示，最好值在表中用粗體標(biāo)示。表中數(shù)據(jù)來源和參數(shù)設(shè)置參考文獻(xiàn)[35]。

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

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

群智能算法經(jīng)過近幾年的大量研究，絕大多數(shù)改進(jìn)算法對較早版本的基準(zhǔn)測試函數(shù)有較好優(yōu)化效果。因此，本文采用新近提出的測試函數(shù)CEC 2015[36]進(jìn)一步驗證算法的優(yōu)化性能，其包含的15 個測試函數(shù)中，所有函數(shù)在各個維度的最優(yōu)解都不相同。將SDMPSO分別與新近提出的改進(jìn)螢火蟲算法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ù)上，獨(dú)立運(yùn)行30次后所得平均最優(yōu)適應(yīng)值。SDMPSO算法在所測15 個函數(shù)中，有6 個函數(shù)占較大優(yōu)勢。表14 對各算法進(jìn)行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檢驗結(jié)果

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

Table 14 Result of Friedman test表14 Friedman檢驗結(jié)果

6 結(jié)束語

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

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