求解大規(guī)模函數(shù)優(yōu)化的粒子群優(yōu)化算法

肖天宇，張著洪

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

0 引 言

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

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

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

1 問題描述與PSO的進化策略

1.1 問題描述與PSO的基本更新策略

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

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

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

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

(1)

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

(2)

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

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

給定全局最優(yōu)粒子xgbest以及2m個粒子x1,x2,…,x2m。假定粒子xi的適應(yīng)度不低于粒子xi+1的適應(yīng)度；將前m個粒子視為優(yōu)質(zhì)粒子，而后m個粒子視為劣質(zhì)粒子；粒子xm+i借助xgbest對稱地向優(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較為靠近，因此會造成群體多樣性喪失，使算法陷入局部搜索[17]。通過上述“對稱學(xué)習(xí)”策略，用群體中較好粒子取代PSO中粒子的歷史最好位置，使粒子不再單一地向粒子歷史最優(yōu)解學(xué)習(xí)；粒子間不斷進行信息交互，充分利用群體信息，增強粒子學(xué)習(xí)的多選擇性，保證粒子不向單一方向轉(zhuǎn)移，增強算法的全局搜索能力；同時，利用全局最優(yōu)粒子引導(dǎo)粒子進化，提升算法的收斂速度，達到全局尋優(yōu)的目的。

1.3 粒子的位置擾動

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

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

(5)

其中

(6)

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

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

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

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

圖1 NPSO算法流程

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

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

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

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

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

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

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

(5)t←t+1；若t

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

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

3 數(shù)值實驗

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

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

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

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

3.1 實驗結(jié)果與比較分析

情形1：CEC′2010測試集

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

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

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

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

情形2：CEC′2013測試集

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

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

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

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

3.2 顯著性檢驗

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

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

表5(續(xù))

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

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

4 結(jié)束語

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