肖天宇，張著洪

(貴州大學(xué) 大數(shù)據(jù)與信息工程學(xué)院 貴州省系統(tǒng)優(yōu)化與科學(xué)計(jì)算特色重點(diǎn)實(shí)驗(yàn)室，貴州 貴陽(yáng) 550025)

0 引 言

受生物或自然現(xiàn)象啟發(fā)的智能優(yōu)化理論及應(yīng)用作為人工智能的重要分支[1-3]，在求解離散、連續(xù)或混合型偏低維優(yōu)化問(wèn)題方面，已發(fā)揮不可替代的作用，且近年不斷涌現(xiàn)的新型智能優(yōu)化算法為求解維度低于1000的偏高維優(yōu)化問(wèn)題的研究提供了啟迪?？墒?，對(duì)于維度超過(guò)1000的大規(guī)模全局優(yōu)化(large-scaled global optimization，LSGO)問(wèn)題[4,5]，因維度較高，性能指標(biāo)的特性復(fù)雜，導(dǎo)致求解算法的性能退化嚴(yán)重[6]。由此，LSGO作為極為重要的科技難題已初步受到關(guān)注。

已報(bào)道求解LSGO的算法大致可概括為兩類[6,7]，即動(dòng)態(tài)分群協(xié)同進(jìn)化和群智能優(yōu)化。前者是將決策變量動(dòng)態(tài)劃分為多個(gè)部分，各部分對(duì)應(yīng)的子群獨(dú)立進(jìn)化，經(jīng)由協(xié)同策略動(dòng)態(tài)分配各子群，促使子群協(xié)同發(fā)現(xiàn)全局最優(yōu)解[8-10]；后者是一種基于現(xiàn)有群體智能優(yōu)化算法的改進(jìn)型優(yōu)化方法，其具有潛在的并行性與分布式特點(diǎn)[11]，搜索能力強(qiáng)，能克服分組策略“兩步向前，合并向后”存在的不足[12]。可是，一旦決策變量不可分割或少許變量可分離時(shí)，算法的搜索效率急劇下降，種群的局部勘測(cè)和全局開(kāi)采能力退化嚴(yán)重，因而算法極難獲得全局最優(yōu)解[6]。因此，如何有效權(quán)衡算法的開(kāi)采與勘測(cè)能力，已成為求解LSGO的關(guān)鍵。

粒子群算法(particle swarm algorithm，PSO)自提出以來(lái)，因其結(jié)構(gòu)簡(jiǎn)單、計(jì)算效率高等優(yōu)點(diǎn)，獲得研究人員的廣泛關(guān)注。但是，PSO求解LSGO的效果并不理想，仍然存在收斂精度低、穩(wěn)定性差、局部收斂等問(wèn)題。為此，本文從如何提高和平衡PSO的開(kāi)采與勘測(cè)能力出發(fā)，提出一種用于求解LSGO的新型粒子群優(yōu)化算法(new particle swarm optimization algorithm，NPSO)。比較性的實(shí)驗(yàn)結(jié)果表明，NPSO在尋優(yōu)質(zhì)量方面具有優(yōu)勢(shì)，有潛在的應(yīng)用價(jià)值。

1 問(wèn)題描述與PSO的進(jìn)化策略

1.1 問(wèn)題描述與PSO的基本更新策略

考慮如下大規(guī)模單目標(biāo)全局函數(shù)優(yōu)化問(wèn)題

minf(x)=f(x1,x2,…,xD)xi∈[ai,bi],1≤i≤D

式中：f(x)關(guān)于x連續(xù)，xi為決策變量，D≥1000。

PSO是一種源于鳥(niǎo)類遷徙過(guò)程且結(jié)構(gòu)簡(jiǎn)單、搜索效率高、進(jìn)化能力極大依賴于學(xué)習(xí)率的尋優(yōu)算法，已廣泛被應(yīng)用于工程領(lǐng)域[13-15]。其將優(yōu)化問(wèn)題的每個(gè)解看成一個(gè)粒子，通過(guò)種群中粒子不斷進(jìn)行信息交互，以及借助個(gè)體最優(yōu)位置xpbest和全局最優(yōu)位置xgbest引導(dǎo)粒子移動(dòng)，促成最終獲得最優(yōu)解?；镜腜SO的粒子更新方式如下

(1)

xi(t+1)=xi(t)+vi(t+1)

(2)

理論分析表明，PSO在處理低維優(yōu)化問(wèn)題時(shí)，能兼顧勘測(cè)與開(kāi)采能力，但當(dāng)問(wèn)題的維數(shù)較高時(shí)，因搜索空間成指數(shù)級(jí)增長(zhǎng)，導(dǎo)致PSO的搜索效率急劇下降且極易陷入局部搜索，以及普適性下降[16]。因此，如何增強(qiáng)PSO處理LSGO問(wèn)題的勘測(cè)與開(kāi)采能力，是本文研究的重點(diǎn)。

1.2 劣質(zhì)粒子學(xué)習(xí)

給定全局最優(yōu)粒子xgbest以及2m個(gè)粒子x1,x2,…,x2m。假定粒子xi的適應(yīng)度不低于粒子xi+1的適應(yīng)度；將前m個(gè)粒子視為優(yōu)質(zhì)粒子，而后m個(gè)粒子視為劣質(zhì)粒子；粒子xm+i借助xgbest對(duì)稱地向優(yōu)質(zhì)粒子xi學(xué)習(xí)，并執(zhí)行更新，即

xm+i,j(t+1)=xm+i,j(t)+vm+i,j(t+1)

(3)

在此

(4)

在PSO中，由于xgbest的影響，在迭代后期，xpbest很可能與xgbest較為靠近，因此會(huì)造成群體多樣性喪失，使算法陷入局部搜索[17]。通過(guò)上述“對(duì)稱學(xué)習(xí)”策略，用群體中較好粒子取代PSO中粒子的歷史最好位置，使粒子不再單一地向粒子歷史最優(yōu)解學(xué)習(xí)；粒子間不斷進(jìn)行信息交互，充分利用群體信息，增強(qiáng)粒子學(xué)習(xí)的多選擇性，保證粒子不向單一方向轉(zhuǎn)移，增強(qiáng)算法的全局搜索能力；同時(shí)，利用全局最優(yōu)粒子引導(dǎo)粒子進(jìn)化，提升算法的收斂速度，達(dá)到全局尋優(yōu)的目的。

1.3 粒子的位置擾動(dòng)

給定以上最優(yōu)粒子xgbest以及m個(gè)粒子x1,x2,x3,…,xm，xi在xgbest的引導(dǎo)下，依據(jù)變異概率pm對(duì)xi中第j個(gè)維度分量進(jìn)行高斯擾動(dòng)，即當(dāng)1～D之間的隨機(jī)數(shù)k=j或者r

xi,j(t+1)=xi,j(t)+vi,j(t+1)

(5)

其中

(6)

在以上位置擾動(dòng)策略下，粒子依概率或者依維度確定位置是否更新，同時(shí)利用最優(yōu)粒子和需更新的粒子的位置偏差，對(duì)需更新的位置進(jìn)行高斯擾動(dòng)，確保每個(gè)粒子每次至少有一個(gè)分量發(fā)生改變，使粒子每次搜索都在xgbest附近進(jìn)行，防止無(wú)效搜索，增強(qiáng)粒子的局部勘測(cè)能力。粒子通過(guò)自適應(yīng)地調(diào)整其搜索范圍，防止因搜索范圍偏大而跳過(guò)最優(yōu)解的位置。此策略可消除原PSO中粒子更新過(guò)度對(duì)xpbest的依賴，增強(qiáng)粒子的局部搜索能力。

2 算法的原理與設(shè)計(jì)

NPSO主要由粒子群分割與更新兩個(gè)模塊組成，如圖1所示。前者根據(jù)當(dāng)前粒子群中粒子的適應(yīng)度，將粒子群劃分為精英種群(A)、優(yōu)質(zhì)種群(B)、中等種群(E)、劣質(zhì)種群(F)。各種群經(jīng)由粒子的歷史信息和特定的更新策略產(chǎn)生新粒子群。

結(jié)合第1節(jié)的模塊設(shè)計(jì)和圖1，NPSO的具體描述如下：

圖1 NPSO算法流程

(1)輸入?yún)?shù)：種群規(guī)模N，維度D，最大迭代數(shù)Gmax，位置更新概率pm，學(xué)習(xí)率φ；

(2)置t←1，隨機(jī)生成規(guī)模為N的初始粒子群P(t)，其最好粒子記作xgbest；

(3)按粒子適應(yīng)度對(duì)P(t)中粒子進(jìn)行降序排列后，前N/4個(gè)粒子構(gòu)成種群A，隨后N/4個(gè)粒子構(gòu)成種群B；依此類推，獲規(guī)模為N/4的種群E和F；

(4)種群A、B、E、F分別執(zhí)行如下更新步驟：

1)依據(jù)種群A及xgbest，利用第1.2節(jié)的劣質(zhì)粒子學(xué)習(xí)策略，對(duì)種群F中各粒子進(jìn)行更新；

2)依據(jù)xgbest及位置更新概率pm，利用第1.3節(jié)的粒子位置擾動(dòng)策略，對(duì)種群E中各粒子更新；

3)組合種群A、B及更新后的種群E、F為粒子群P(t+1)，更新xgbest；

(5)t←t+1；若t

以上算法設(shè)計(jì)中，種群A引導(dǎo)種群F進(jìn)行更新，促使種群中粒子間信息交互，增強(qiáng)算法的全局開(kāi)采能力；種群B并不直接參與進(jìn)化，其目的在于防止在每次迭代中由于粒子重復(fù)更新而導(dǎo)致算法陷入局部搜索；種群E中的粒子依概率及高斯變異策略執(zhí)行局部搜索，防止因粒子的大量位置更新而導(dǎo)致劣質(zhì)粒子變得更差，增強(qiáng)算法的局部勘測(cè)能力。該算法的結(jié)構(gòu)簡(jiǎn)單，易于實(shí)現(xiàn)，且兼顧群體勘測(cè)與開(kāi)采對(duì)獲取全局最優(yōu)解的貢獻(xiàn)；同時(shí)，在優(yōu)質(zhì)粒子引導(dǎo)下，劣質(zhì)粒子經(jīng)對(duì)稱學(xué)習(xí)逐漸變?yōu)閮?yōu)質(zhì)粒子。

在NPSO中，算法的計(jì)算復(fù)雜度主要由步驟(3)、步驟(4)決定。在一個(gè)迭代周期內(nèi)，步驟(3)需對(duì)粒子進(jìn)行排序，其計(jì)算復(fù)雜度為O(NlogN)；步驟(4)需對(duì)種群E和F中的粒子進(jìn)行更新以及計(jì)算適應(yīng)度，其至多執(zhí)行(N(D+1)/2)次。因此，在最壞情形，NPSO的計(jì)算復(fù)雜度為O(N(logN+(D+1)/2))。此表明，N和D是影響算法效率的關(guān)鍵因素。

3 數(shù)值實(shí)驗(yàn)

在Windows 10/CPU 3.30 GHz/RAM 8.0 GB/ Visual Studio 2013環(huán)境下展開(kāi)數(shù)值實(shí)驗(yàn)。為比較分析NPSO的性能，將其與6種不同的算法進(jìn)行比較，即基于種群競(jìng)爭(zhēng)學(xué)習(xí)的粒子群算法(CSO)[17]、基于偏置中心學(xué)習(xí)的粒子群算法(RBLSO)[18]、經(jīng)典粒子群算法(PSO)、蟻群優(yōu)化算法(ACO)、聯(lián)合操作算法(JOA)[19]、氣體擴(kuò)散算法(GPBO)[20]。上述對(duì)比算法的詳細(xì)參數(shù)設(shè)置以及本文的參數(shù)設(shè)置見(jiàn)表1。測(cè)試事例為文獻(xiàn)[17]中CEC′2010和CEC′2013測(cè)試集，共計(jì)35個(gè)可分解、部分可分解、不可分解的LSGO最小化問(wèn)題，其中CEC′2010包含20個(gè)測(cè)試函數(shù)，CEC′2013包含15個(gè)測(cè)試函數(shù)，每個(gè)問(wèn)題的維度D均為1000；測(cè)試事例的目標(biāo)函數(shù)的特征見(jiàn)表2。

表1 各算法參數(shù)設(shè)置

各算法對(duì)每個(gè)測(cè)試問(wèn)題均獨(dú)立運(yùn)行25次，每次的最大適應(yīng)度評(píng)價(jià)次數(shù)均為3×106；每種算法求解每個(gè)測(cè)試問(wèn)題25次后，獲得的25個(gè)最好目標(biāo)值被用于算法比較分析。為充分呈現(xiàn)NPSO的性能，算法的比較分析包括：①研究以上算法求解表2中測(cè)試問(wèn)題的性能差異；②借助假設(shè)檢驗(yàn)分析算法的搜索效果是否存在顯著性差異。

表2 測(cè)試函數(shù)特性

3.1 實(shí)驗(yàn)結(jié)果與比較分析

情形1：CEC′2010測(cè)試集

將以上每種算法作用于CEC′2010測(cè)試集中每種測(cè)試問(wèn)題25次后，獲得的統(tǒng)計(jì)結(jié)果見(jiàn)表3，其中μ代表25個(gè)最優(yōu)值的均值，σ代表25個(gè)最優(yōu)值的標(biāo)準(zhǔn)差；以f1、f4、f15、和f19為例，各算法的平均搜索曲線如圖2所示。

表3 算法求解CEC′2010測(cè)試問(wèn)題獲得的統(tǒng)計(jì)結(jié)果比較

經(jīng)由表3可知，NPSO與RBLSO、CSO和PSO相比，其求解以上表2中CEC′2010的20個(gè)測(cè)試問(wèn)題，能分別獲得12、14、20個(gè)最小均值以及11、11、18個(gè)最小均方差；從函數(shù)特性上看，無(wú)論對(duì)哪種測(cè)試函數(shù)，NPSO獲得的解質(zhì)量都要好于PSO的解質(zhì)量；與兩種改進(jìn)型粒子群算法RBLSO和CSO相比，NPSO求解單模態(tài)(如f1、f7)以及可分函數(shù)(如f12、f13)的尋優(yōu)效果要好。當(dāng)其與新型算法GPBO、JOA及傳統(tǒng)算法ACO相比，能分別獲得19、19、20個(gè)最小均值以及16、15、18個(gè)最小均方差，可以看出，NPSO獲得的解質(zhì)量都要好于這3種算法。

圖2表明，NPSO的改進(jìn)型策略能有效地克服PSO易陷入局部搜索的不足，同時(shí)可兼顧勘測(cè)與開(kāi)采的能力。圖2(a)表明，對(duì)于單模態(tài)可分函數(shù)f1，PSO在搜尋初期就已陷入局部最優(yōu)，而NPSO不僅未陷入局部最優(yōu)，而且擁有較快的收斂速度以及較高的收斂精度。NPSO與RBLSO、CSO相比，其雖然在搜尋初期的收斂速度略慢，但其局部尋優(yōu)能力較強(qiáng)。它在迭代中期以及后期的收斂速度較快，同時(shí)可以在迭代后期能有效防止陷入局部搜索。結(jié)合表3中的統(tǒng)計(jì)結(jié)果可知，NPSO不僅對(duì)單模態(tài)函數(shù)(如f1、f7)的尋優(yōu)能力較強(qiáng)，而且對(duì)多模態(tài)函數(shù)(f13、f15)、完全不可分函數(shù)(如f19)這類較復(fù)雜的函數(shù)都有較強(qiáng)尋優(yōu)能力，且易于跳出局部搜索。

情形2：CEC′2013測(cè)試集

類似于以上情形1的數(shù)值實(shí)驗(yàn)，各算法求解CEC′2013測(cè)試集中每種測(cè)試問(wèn)題25次后，獲得的統(tǒng)計(jì)結(jié)果見(jiàn)表4；以f1、f4、f14和f15為例，各算法獲得的目標(biāo)值的平均搜索曲線如圖3所示。

經(jīng)由表4，NPSO與RBLSO、CSO及PSO相比，其分別獲得7、9、14個(gè)最小均值和8、12、13個(gè)最小均方差；與GPBO、JOA和ACO相比，其分別獲得11、11、15個(gè)最小均值與11、14、15個(gè)最小均方差。結(jié)合表3中的實(shí)驗(yàn)結(jié)果，NPSO對(duì)于15個(gè)單模態(tài)函數(shù)，求解其中13個(gè)函數(shù)具有優(yōu)勢(shì)；對(duì)于20個(gè)多模態(tài)函數(shù)，其求解其中5個(gè)函數(shù)具有優(yōu)勢(shì)。此表明，NPSO求解單模態(tài)LSGO問(wèn)題比求解多模態(tài)LSGO問(wèn)題更有優(yōu)勢(shì)。這是因?yàn)樗惴ㄔ诘^(guò)程中多次使用全局最優(yōu)粒子引導(dǎo)種群粒子進(jìn)化，粒子逐漸靠近全局最優(yōu)粒子，因此對(duì)單模態(tài)問(wèn)題具有潛力。對(duì)于較難的3個(gè)完全不可分問(wèn)題以及3個(gè)重疊問(wèn)題，NPSO分別獲得2、2個(gè)最小均值與標(biāo)準(zhǔn)差，并且結(jié)合圖3中的收斂曲線，NPSO在解決更為復(fù)雜的完全不可分問(wèn)題以及重疊問(wèn)題時(shí)，已初步具有一定的優(yōu)勢(shì)。如圖3(d)所示，對(duì)于完全不可分函數(shù)f15，雖然NPSO在迭代初期與RBLSO和CSO的下降速度大致相同，但隨迭代數(shù)的增大，RBLSO與CSO的收斂速度變慢，NPSO仍然保持較快收斂速度，而PSO卻快速陷入局部搜索。

圖3 算法求解f1、f4、f14、f15的平均搜索曲線比較

表4 算法求解CEC′2013測(cè)試問(wèn)題獲得的統(tǒng)計(jì)結(jié)果比較

3.2 顯著性檢驗(yàn)

為分析以上7種算法求解CEC′2010、CEC′2013中測(cè)試問(wèn)題后獲得的解是否存在顯著性差異，將得到的解的目標(biāo)值作為樣本值進(jìn)行t檢驗(yàn)。通過(guò)取顯著性水平α=0.05，獲得的t檢驗(yàn)結(jié)果見(jiàn)表5、表6，表中W、T、L分別指NPSO在求解測(cè)試問(wèn)題上表現(xiàn)較好、相等以及較差的個(gè)數(shù)。

表5 算法求解CEC′2010測(cè)試集的t檢驗(yàn)結(jié)果比較

表5(續(xù))

表6 算法求解CEC′2013 測(cè)試集的t檢驗(yàn)結(jié)果比較

經(jīng)由表5、表6可知，針對(duì)CEC′2010、CEC′2013測(cè)試集的35個(gè)測(cè)試問(wèn)題，NPSO依次與RBLSO、CSO、GPBO、JOA、PSO及ACO相比，能獲得最好效果的問(wèn)題個(gè)數(shù)依次是16、21、28、30、31及34。因此，NPSO較參與比較的6種算法在獲得的解質(zhì)量方面具有明顯優(yōu)勢(shì)。

4 結(jié)束語(yǔ)

鑒于LSGO是智能優(yōu)化未來(lái)研究的重點(diǎn)分支，以及LSGO屬于極具挑戰(zhàn)性的研究課題，本文從粒子群優(yōu)化角度，圍繞粒子的學(xué)習(xí)效果提升、多樣性增強(qiáng)問(wèn)題，借助粒子對(duì)稱學(xué)習(xí)、高斯變異，設(shè)計(jì)劣質(zhì)粒子學(xué)習(xí)、粒子位置擾動(dòng)策略，獲得適合于求解LSGO的新型粒子群優(yōu)化算法(NPSO)。理論分析表明，該算法的計(jì)算復(fù)雜度由粒子群規(guī)模和優(yōu)化問(wèn)題的維度確定。比較性的實(shí)驗(yàn)分析表明，NPSO在相同的最大粒子評(píng)價(jià)次數(shù)下，在求解質(zhì)量方面具有明顯優(yōu)勢(shì)。另外，雖然NPSO求解單模態(tài)LSGO問(wèn)題的優(yōu)勢(shì)較為突出，但求解多模態(tài)LSGO問(wèn)題時(shí)，其局部勘測(cè)能力仍有提升空間，這也是未來(lái)努力的研究方向。