徐利鋒, 黃祖勝, 楊中柱, 丁維龍

(浙江工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,浙江 杭州 310023)

粒子群優(yōu)化算法(particle swarm optimization,簡稱PSO)是由Kennedy和Eberhart于1995年提出的一種模擬鳥群覓食特性的進(jìn)化算法[1].在算法中,粒子代表著覓食中的鳥個(gè)體.在每個(gè)粒子移動(dòng)時(shí),同時(shí)考慮整個(gè)群體的最優(yōu)位置和當(dāng)前粒子曾經(jīng)經(jīng)歷過的最優(yōu)位置,類似于鳥群覓食時(shí)鳥之間的信息交流.當(dāng)群體中所有粒子都移動(dòng)之后,記為一輪優(yōu)化迭代完成,接著進(jìn)行下一輪優(yōu)化迭代,直到滿足預(yù)設(shè)的迭代深度或者其他條件為止.整個(gè)群體就像鳥群覓食一樣,總是向著最優(yōu)位置移動(dòng).

PSO算法具有易操作和收斂快等優(yōu)點(diǎn),但也存在著一些問題,比如因其收斂快而導(dǎo)致的易陷入局部最優(yōu)值,以及算法在多局部峰值場(chǎng)景中的精確性不高等問題.研究者們一直在針對(duì) PSO的這些問題進(jìn)行針對(duì)性的研究和改進(jìn),并提出一些解決方法,形成了若干PSO的改進(jìn)算法.其中,Shi和Eberhart于1998年提出的帶有慣性權(quán)重的粒子群優(yōu)化算法[2],便是針對(duì)最初的PSO算法易陷入局部最優(yōu)值的改進(jìn).Clerc于1999年提出了帶壓縮因子的粒子群優(yōu)化算法[3],意在擺脫局部最優(yōu)值的同時(shí)提高收斂速度.這是兩種最經(jīng)典的改進(jìn)PSO算法,其他的改進(jìn)算法一般都是在此基礎(chǔ)之上通過與其他方法結(jié)合或是針對(duì)參數(shù)進(jìn)行修改來獲得新的改進(jìn)算法.例如,劉麗玨等人提出了基于克隆選擇的粒子群優(yōu)化算法[4],主要利用了克隆和變異操作來提高算法的收斂速度,并保持種群多樣性.再如,針對(duì)多目標(biāo)優(yōu)化問題而提出的基于網(wǎng)格排序的多目標(biāo)粒子群優(yōu)化算法[5]、為逼近非凸或不連續(xù)的Pareto最優(yōu)前端而提出的基于Pareto熵的多目標(biāo)粒子群優(yōu)化算法[6]、面向粒子群優(yōu)化算法中學(xué)習(xí)因子自調(diào)節(jié)優(yōu)化器的PSO算法[7]、基于粒子群優(yōu)化算法的類集成測(cè)試序列確定方法[8]、加入了微生物行為機(jī)制的粒子群優(yōu)化算法[9]以及微分進(jìn)化算法與粒子群優(yōu)化的結(jié)合[10]和其他一些針對(duì) PSO參數(shù)進(jìn)行自適應(yīng)選擇的算法[11,12]等.這些改進(jìn)的算法直接針對(duì)PSO算法本身存在的缺陷進(jìn)行彌補(bǔ).另外,還有一些改進(jìn)算法實(shí)現(xiàn)了在不同領(lǐng)域中的適配和應(yīng)用.對(duì)于算法適配,例如：對(duì)典型的NP難題中的Web服務(wù)組合優(yōu)化問題,研究者提出了基于改進(jìn)粒子群算法的Web服務(wù)組合[13];ECT系統(tǒng)中如果忽略電容傳感器的敏感場(chǎng)(又叫軟場(chǎng)),會(huì)使傳統(tǒng)圖像重建方法精度下降,為了清除這個(gè)瓶頸,提出了基于雙粒子群協(xié)同優(yōu)化的 ECT圖像重建算法[14];為了在不修改源代碼的同時(shí)能夠評(píng)價(jià)優(yōu)化目標(biāo)的每個(gè)分支,提出了粒子群優(yōu)化測(cè)試用例生成方法[15].對(duì)于算法應(yīng)用,例如跳躍-滑翔軌跡優(yōu)化研究(混沌粒子群算法)[16]、電力系統(tǒng)環(huán)保經(jīng)濟(jì)負(fù)荷分配應(yīng)用研究(空間粒子群優(yōu)化算法)[17]以及求解服務(wù)鏈映射問題(離散粒子群優(yōu)化算法)[18]等.

上述各種基于PSO的改進(jìn)和適配后優(yōu)化算法各有優(yōu)點(diǎn),但總體來說都是嘗試去解決原始PSO算法的固有問題——易于陷入局部極值的問題.針對(duì)這種問題,本研究基于現(xiàn)有的兩種經(jīng)典改進(jìn)PSO算法,在不過分提高算法時(shí)間復(fù)雜度的前提下,通過引入多級(jí)擾動(dòng)策略來避免PSO算法易陷入局部最優(yōu)值的問題,同時(shí)也能運(yùn)用不同的擾動(dòng)來處理算法探索能力差或算法提前收斂的情況.研究中,運(yùn)用了 Sphere,Ackley,Rastrigin,Styblinski-Tang,Duadric和Rosenbrock函數(shù)對(duì)算法的性能進(jìn)行了測(cè)試,并對(duì)不同的PSO相關(guān)優(yōu)化算法結(jié)果進(jìn)行對(duì)比驗(yàn)證.本研究提出的改進(jìn)型 PSO算法巧妙地結(jié)合了兩種經(jīng)典的改進(jìn)粒子群優(yōu)化算法(帶慣性權(quán)重和帶收縮因子的粒子群優(yōu)化算法)的特性,使得本算法能夠?qū)⑦@兩種優(yōu)化算法的優(yōu)點(diǎn)實(shí)現(xiàn)最大化的發(fā)揮.同時(shí),針對(duì)易陷入局部最優(yōu)這個(gè)問題,提出了多級(jí)擾動(dòng)機(jī)制.總體來說,本算法不僅能夠增加粒子對(duì)于解空間的探索能力,還能夠較好地跳出局部最優(yōu)值.本文首先在第1節(jié)介紹上述兩種經(jīng)典的改進(jìn)粒子群優(yōu)化算法.然后,在第2節(jié)詳細(xì)講述了提出的新的改進(jìn)型PSO算法,即混合型粒子群優(yōu)化算法的概念及流程.在第3節(jié)中,通過對(duì)4個(gè)測(cè)試函數(shù)的結(jié)合應(yīng)用,對(duì)混合型粒子群優(yōu)化算法的可行性及準(zhǔn)確性進(jìn)行對(duì)比和驗(yàn)證.最后,對(duì)本算法和相關(guān)的粒子群優(yōu)化算法進(jìn)行討論,對(duì)后續(xù)研究進(jìn)行展望.

1 傳統(tǒng)粒子群優(yōu)化算法

1.1 粒子群優(yōu)化算法

最初提出的粒子群優(yōu)化算法在模擬鳥群覓食的過程中,各個(gè)粒子的位置信息代表解空間中的一個(gè)可能的解,速度信息則代表粒子的更新(移動(dòng))動(dòng)力.初始的粒子群優(yōu)化算法總是能高效地進(jìn)行更新,從而體現(xiàn)出收斂快的特點(diǎn).

假設(shè)：所要優(yōu)化的問題的種群大小為n,解空間維數(shù)為m,種群中每個(gè)粒子的位置為Xi(i=1,2,…,n),每個(gè)粒子的適應(yīng)度值為f(Xi)(i=1,2,…,n),第k代中第i個(gè)粒子的位置為Xik,粒子的速度為Vik,第i個(gè)粒子得到的最優(yōu)適應(yīng)度值的位置為Pik(i=1,2,…,n),所有粒子中得到最優(yōu)適應(yīng)度值的位置為Pgk.公式(1)和公式(2)為粒子群優(yōu)化算法中對(duì)于第k代粒子的速度、位置更新公式：

其中,c1和c2為學(xué)習(xí)因子,r1和r2為使速度具有隨機(jī)性的隨機(jī)數(shù),取值在[0,1]之間.

從公式(1)和公式(2)中可以看出,粒子速度更新公式包含了3部分[19,20]：第1部分為粒子當(dāng)前速度對(duì)于之前速度及方向的繼承能力;第2部分為粒子的自我認(rèn)知部分,用來繼承粒子歷史屬性;第3部分為粒子的社會(huì)認(rèn)知部分,表示為所有粒子之間的信息共享,合作地去探索更好的位置.但是由于此方法易陷入局部最優(yōu)值,所以針對(duì)上述更新公式進(jìn)行一定修改后,得到了下文所提到的兩種主流的改進(jìn)算法.

1.2 標(biāo)準(zhǔn)粒子群優(yōu)化算法

標(biāo)準(zhǔn)粒子群優(yōu)化算法(standard particle swarm optimization,簡稱SPSO),即帶有慣性權(quán)重的PSO算法,在繼承粒子歷史速度時(shí),引入慣性權(quán)重參數(shù).目的是在尋優(yōu)問題中,能夠先進(jìn)行全局搜索,在縮小的搜索范圍或經(jīng)過一段時(shí)間的搜索之后,再針對(duì)當(dāng)前局部進(jìn)行更為細(xì)致的搜索來獲得最優(yōu)解.當(dāng)慣性權(quán)重ω取值較大時(shí),全局搜索能力強(qiáng);較小時(shí),局部搜索能力強(qiáng).所以,該算法的慣性權(quán)重通常是線性遞減的[2].

假設(shè)：所要優(yōu)化問題的種群大小為n,解空間維數(shù)為m,種群中每個(gè)粒子的位置為Xi(i=1,2,…,n),每個(gè)粒子的適應(yīng)度值為f(Xi)(i=1,2,…,n),第k代中第i個(gè)粒子的位置為Xik,粒子的速度為Vik,第i個(gè)粒子得到的最優(yōu)適應(yīng)度值的位置為Pik(i=1,2,…,n),所有粒子中得到最優(yōu)適應(yīng)度值的位置為Pgk.公式(3)、公式(4)為標(biāo)準(zhǔn)粒子群優(yōu)化算法中對(duì)于第k代粒子的速度、位置更新公式：

其中,ω為慣性權(quán)重,一般為線性遞減,運(yùn)算方法見公式(5).

也有研究者使用一種基于對(duì)數(shù)遞減的慣性權(quán)重運(yùn)算方式[21],見公式(6),一般取值由0.9遞減到0.4[22]：

其中,ωs為起始慣性權(quán)重值,ωe為結(jié)束慣性權(quán)重值,Tc為當(dāng)前迭代深度,Tm為最大迭代深度.

除此之外,還有許多其他有關(guān)慣性權(quán)重的修改方法.例如指數(shù)遞減策略[23]、自適應(yīng)慣性權(quán)重[24]等,在此不做詳細(xì)介紹.

SPSO算法的大致思路為：粒子群中每個(gè)粒子都有自己的位置及速度,每次迭代就相當(dāng)于更新了群體中每個(gè)粒子的位置和速度,粒子的速度更新與粒子前一次速度及自身歷史最優(yōu)位置和群體歷史最優(yōu)位置與當(dāng)前自身位置的差值有關(guān),粒子的位置更新與速度有關(guān).而 SPSO算法的特點(diǎn)是對(duì)于粒子的繼承能力部分,添加了一個(gè)慣性權(quán)重,以此來改變粒子歷史速度屬性對(duì)于當(dāng)前屬性的影響能力.其主要思想為：在優(yōu)化算法剛開始時(shí),通過較大的慣性權(quán)重來使得粒子群的全局搜索能力強(qiáng)于局部搜索能力,而在算法不斷進(jìn)行迭代優(yōu)化之后,通過減少慣性權(quán)重來逐步加強(qiáng)粒子群的局部搜索能力.

1.3 帶收縮因子的粒子群優(yōu)化算法

帶收縮因子的粒子群優(yōu)化算法(standard particle swarm optimization with a constriction factor,簡稱PSOCF)流程與最初的PSO算法相似,區(qū)別在于粒子的速度更新公式不同.PSOCF運(yùn)用收縮因子來對(duì)每次更新后的速度進(jìn)行壓縮,從而提升收斂速度.

其中,φ為收縮因子.

與 SPSO算法不同,該算法的收縮因子不僅僅是改變了自身歷史速度的影響能力,同時(shí)也改變了歷史最優(yōu)位置對(duì)粒子速度的影響能力.由于收縮因子是固定常量,為了能夠較好地平衡全局搜索與局部搜索之間的權(quán)重,一般使用公式(9)來計(jì)算收縮因子常量[3]：

PSOCF算法的特點(diǎn)是對(duì)于粒子的繼承能力、自我認(rèn)知能力及社會(huì)認(rèn)知能力部分,添加了一個(gè)壓縮因子,因此與SPSO算法相比,PSOCF算法在速度更新方面會(huì)更快地趨于穩(wěn)定.其主要思想為擴(kuò)大了慣性權(quán)重的影響范圍,因此PSOCF算法全局搜索能力的減弱速度以及局部搜索能力的增強(qiáng)速度都得到了提升,從而提升了整體算法的收斂速度.

2 新的帶多級(jí)擾動(dòng)的混合型粒子群優(yōu)化算法

SPSO和PSOCF這兩種改進(jìn)優(yōu)化算法各有特點(diǎn).在粒子群算法中,不同的參數(shù)影響著算法不同的方面：慣性權(quán)重影響的是算法中粒子屬性的繼承性;而壓縮因子不僅影響繼承性,更影響了整體算法的收斂性.壓縮因子過大,收斂性差,且算法接近于隨機(jī)搜索優(yōu)化;壓縮因子過小,則易提早收斂,導(dǎo)致結(jié)果可能為局部最優(yōu)值,精度下降.從針對(duì)粒子進(jìn)行分層[24]得到靈感,本研究提出的新型改進(jìn)算法——帶多級(jí)擾動(dòng)的混合型粒子群優(yōu)化算法(mixed particle swarm optimization with multistage disturbances,簡稱MPSO),是將以上兩種優(yōu)化算法的優(yōu)點(diǎn)進(jìn)行整合,在考慮粒子能夠較好繼承自身最優(yōu)解和群體最優(yōu)解的基礎(chǔ)上,引入多級(jí)擾動(dòng)來增加粒子位置變異的隨機(jī)性以及防止粒子的早熟收斂.

粒子群優(yōu)化算法具有收斂快的特點(diǎn),使得算法容易陷入局部最優(yōu)值而使得最終優(yōu)化結(jié)果產(chǎn)生誤差,因此在本研究中引入多級(jí)擾動(dòng)來防止早熟收斂.多級(jí)擾動(dòng)策略分為兩級(jí)：一級(jí)擾動(dòng)的主要作用是使粒子能夠更充分地遍歷解空間,類似于混沌擾動(dòng)[25],都是為了增加粒子的遍歷能力;二級(jí)擾動(dòng)則是為應(yīng)對(duì)在多峰值情況下易陷入局部最優(yōu)值的問題而提出的輔助策略,提高搜索結(jié)果的精度,類似于蜜蜂尋找蜂蜜.目前已尋找到暫時(shí)最佳的,但是仍需要再去其他地方探索觀察是否有更為豐富的蜂蜜,那么便假設(shè)此時(shí)刻的最優(yōu)位置的食物已耗盡,以此為基礎(chǔ)再去尋找其他食物[26].一級(jí)擾動(dòng)在粒子更新位置之后引入.具體的引入概率與當(dāng)前迭代深度(Tc)及最大迭代深度(Tm)有關(guān),見公式(10).

其中,ε為引入一級(jí)擾動(dòng)的概率.得到的概率會(huì)隨著迭代深度的增加而減少.與此方法類似的是將粒子分為兩種：一種負(fù)責(zé)標(biāo)準(zhǔn)運(yùn)行,另一種負(fù)責(zé)群體多樣性.將兩種粒子進(jìn)行結(jié)合,可以趨近粒子在探索和收斂間的平衡[27].二級(jí)擾動(dòng)在一級(jí)擾動(dòng)判斷之后引入.是否引入二級(jí)擾動(dòng),與粒子是否早熟的判斷有關(guān)：若在優(yōu)化過程探索期中最優(yōu)粒子連續(xù)出現(xiàn)10次相同狀態(tài)(前期實(shí)驗(yàn)表明：觸發(fā)二級(jí)擾動(dòng)的相同次數(shù)分別為10,20,30,40時(shí),精度都沒有顯著差異(見表1),因此設(shè)置為10次),則判定為局部收斂(早熟),從而引入二級(jí)擾動(dòng),使粒子快速跳脫出局部最優(yōu)值.

MPSO算法主要是將優(yōu)化過程的中前期定義為探索期,盡量保持較強(qiáng)的全局搜索能力;而在優(yōu)化后期,為了快速收斂,盡量加強(qiáng)局部搜索能力.結(jié)合前述兩種經(jīng)典優(yōu)化算法的優(yōu)點(diǎn)：探索期中利用慣性權(quán)重及一級(jí)擾動(dòng)A(后文公式(12))在優(yōu)化前期較強(qiáng)的全局搜索能力,盡可能的去遍歷解空間,并使用二級(jí)擾動(dòng)來擺脫局部極值;在優(yōu)化后期,則使用收縮因子及一級(jí)擾動(dòng)B(后文公式(13))來增強(qiáng)粒子的局部搜索能力,從而完成收斂.

Table 1 Result of four optimization algorithms for different second disturb condition of five test functions表1 4種優(yōu)化算法對(duì)于不同二級(jí)擾動(dòng)條件的5種測(cè)試函數(shù)的優(yōu)化結(jié)果

基于與前述現(xiàn)有算法相同的假設(shè),MPSO算法具體優(yōu)化流程如下.

Step 1. 初始化粒子群中所有粒子的位置和速度.

Step 2. 計(jì)算每個(gè)粒子的適應(yīng)度值.

Step 3. 對(duì)于每個(gè)粒子,將此次優(yōu)化得到的適應(yīng)度值與其自身經(jīng)歷過的歷史最優(yōu)適應(yīng)度值Pik進(jìn)行比較,若優(yōu)于Pik則更新該粒子的歷史最優(yōu)位置.

Step 4. 當(dāng)所有粒子都更新粒子歷史最優(yōu)速度Pik之后,將每個(gè)粒子的適應(yīng)度值與整個(gè)群體的最優(yōu)值Pgk進(jìn)行比較,若優(yōu)于Pgk的適應(yīng)度值,則對(duì)Pgk進(jìn)行更新.

Step 5. 根據(jù)當(dāng)前迭代深度判斷使用公式(3)、公式(4)還是公式(7)、公式(8)對(duì)所有粒子更新速度及位置.

Step 6. 更新適應(yīng)度值.

Step 7. 根據(jù)公式(10)判斷是否引入一級(jí)擾動(dòng)：若引入擾動(dòng),則到Step 8;若不引入,則到Step 9.

Step 8. 引入一級(jí)擾動(dòng)后再次更新適應(yīng)度值：若新適應(yīng)度值優(yōu)于原適應(yīng)度值,則保留擾動(dòng);否則刪除擾動(dòng).

Step 9. 判斷當(dāng)前收斂狀況是否滿足提早收斂的條件：

? 若滿足,則引入二級(jí)擾動(dòng),并回到Step 5;

? 若不滿足,則判斷是否滿足終止條件：若滿足,則結(jié)束算法;若不滿足,則回到Step 3.

第5步中的速度、位置更新算法有兩個(gè)：首先使用的是標(biāo)準(zhǔn)粒子群優(yōu)化算法的公式(3)、公式(4),之后再使用帶收縮因子的公式(7)、公式(8).之所以選擇這種更新方式,是因?yàn)檫@兩種公式各有特點(diǎn).例如,SPSO對(duì)解空間的探索好,而 PSOCF的收斂速度快.所以定義中前期為探索期,中后期則可根據(jù)情況實(shí)現(xiàn)收斂.將其兩者結(jié)合在一起,可使優(yōu)化過程盡量徹底且全面,同時(shí)又能及時(shí)得到收斂得到優(yōu)化結(jié)果.MPSO算法流程如圖1所示.其中的一級(jí)擾動(dòng)的算法流程如圖2所示.

探索期時(shí)間點(diǎn)的定義,主要由通過一系列的前期預(yù)備實(shí)驗(yàn)確定.要確定切換時(shí)間點(diǎn),主要考慮算法的兩個(gè)因素：探索范圍的大小及探索最終結(jié)果的精度.由于探索范圍與迭代深度正相關(guān),因此將探索最終結(jié)果的精度作為首要評(píng)價(jià)標(biāo)準(zhǔn),在結(jié)果精度無顯著差異的情況下,將探索范圍的大小納入評(píng)判依據(jù).

最佳切換時(shí)間的獲取也是一個(gè)優(yōu)化問題,因此,將算法中的切換時(shí)間點(diǎn)作為優(yōu)化目標(biāo),通過使用本文提出的混合型粒子群優(yōu)化算法來獲取最優(yōu)解.由于獲取最佳切換時(shí)間的算法執(zhí)行中還會(huì)涉及探索期切換的最佳切換時(shí)間設(shè)置,因而為簡化起見,將最佳切換時(shí)間優(yōu)化過程中的當(dāng)次迭代深度的探索期切換時(shí)間設(shè)置為前次迭代探索到的最優(yōu)解.本研究運(yùn)用Sphere函數(shù)、Ackley函數(shù)、Rastrigin函數(shù)、Styblinski-Tang函數(shù)、Duadric函數(shù)和Rosenbrock函數(shù)進(jìn)行仿真實(shí)驗(yàn),因此也對(duì)這6個(gè)測(cè)試函數(shù)的優(yōu)化來獲取最優(yōu)的探索期切換區(qū)間.

對(duì)這個(gè)子問題的優(yōu)化過程的具體設(shè)置是：把切換時(shí)間點(diǎn)所處的算法總體迭代過程歸一化為[0,1]區(qū)間(將區(qū)間歸一化是因?yàn)樵诓煌瑑?yōu)化問題中,得到的范圍是不確定的,精度也是不確定的,因此為了拓展算法的通用性,將整體區(qū)間進(jìn)行歸一化處理);設(shè)定優(yōu)化算法中粒子個(gè)數(shù)為 10,粒子維度(探索步長)為 10;時(shí)間點(diǎn)探索迭代深度為100;函數(shù)極值探索的迭代深度為2 000;以對(duì)不同函數(shù)探索到的極值精度(或偏差度)作為適應(yīng)度函數(shù),評(píng)價(jià)比較切換時(shí)間點(diǎn)優(yōu)劣.優(yōu)化結(jié)果顯示,對(duì)所有函數(shù)來說,最優(yōu)值(即極值)探索到的時(shí)間點(diǎn)基本上都在10/20～12/20之間(即迭代深度1000～1200).具體對(duì)比結(jié)果見表2.

Table 2 Optimization algorithm for the same dimension of the six test functions for the time switching point表2 優(yōu)化算法對(duì)于相同維度的6種測(cè)試函數(shù)的時(shí)間切換點(diǎn)優(yōu)化結(jié)果表

考慮算法存在的系統(tǒng)誤差以及一定的隨機(jī)性因素,將算法的切換時(shí)間點(diǎn)定義到合適的范圍區(qū)間.從表 2的結(jié)果,確定該區(qū)間范圍為[1/2,3/5].

本文提出算法的迭代深度到達(dá)切換時(shí)間區(qū)間后,通過判斷當(dāng)前最優(yōu)值第 1次出現(xiàn)的迭代深度來確定本次優(yōu)化探索期結(jié)束的時(shí)間點(diǎn).因此,本研究提出了公式(11),使得能夠方便地在歸一化后的區(qū)間找到時(shí)間切換點(diǎn)T：

其中,Tf為當(dāng)前最優(yōu)值第1次出現(xiàn)的迭代深度,Rsa為歸一化整體迭代過程中切換時(shí)間區(qū)間的開始,Rst為切換時(shí)間區(qū)間的結(jié)束.

為了針對(duì)不同狀態(tài)和特點(diǎn)的粒子,算法中所引入的一級(jí)擾動(dòng)分為兩種不同的形式,記為A和B(如圖2所示).

· 一級(jí)擾動(dòng)A在優(yōu)化前期引入,主要作用是增大粒子對(duì)本身鄰域的探索能力;同時(shí),reset保證了粒子有突破當(dāng)前局限的可能性;

·B部分在算法后期引入,主要作用是對(duì)粒子位置進(jìn)行小幅度的探索修正.

其中,r0為[-2,2]之間的隨機(jī)數(shù),有關(guān)r0的取值將在本文下文中進(jìn)行驗(yàn)證;T為通過公式(11)獲得的時(shí)間切換點(diǎn);r1,r2,r3為[0,1]的隨機(jī)數(shù);ga為標(biāo)準(zhǔn)高斯隨機(jī)數(shù)(μ=0,σ=1,在[-3,3]的概率為99.8%);reset表示對(duì)當(dāng)前粒子的位置在當(dāng)前解空間中進(jìn)行隨機(jī)重置.一級(jí)擾動(dòng)A和B中是兩種不同的擾動(dòng)方式,在具體實(shí)施中選擇其一進(jìn)行,且兩者選擇概率是相同的.每次引入一級(jí)擾動(dòng)之后,都要檢測(cè)當(dāng)前引入的一級(jí)擾動(dòng)是否使得適應(yīng)度值更優(yōu)：若更優(yōu),則保留此次一級(jí)擾動(dòng);否則,刪除當(dāng)次擾動(dòng)(避免無用擾動(dòng)對(duì)結(jié)果產(chǎn)生影響).

算法中對(duì)粒子陷入局部最優(yōu)的判斷：如果粒子連續(xù)10次的狀態(tài)都相同,那么便定義當(dāng)前粒子陷入了局部最優(yōu)值.若已陷入局部最優(yōu)值,則會(huì)引入二次擾動(dòng).二級(jí)擾動(dòng)主要是將粒子的位置重置為與當(dāng)前局部最優(yōu)結(jié)果有關(guān)的位置(見公式(14)),并且讓其脫離當(dāng)前局部最優(yōu).但脫離結(jié)果不能過于隨機(jī),因此運(yùn)用了基于最優(yōu)位置值附近的隨機(jī)位置分布,來更新粒子位置,從而達(dá)到脫離的效果：

前述公式中,包含兩個(gè)隨機(jī)數(shù)r0和ra.這兩個(gè)參數(shù)在整個(gè)算法中,目的是增強(qiáng)粒子的探索能力和跳脫出局部最優(yōu)值的能力,因此其取值對(duì)優(yōu)化算法的改進(jìn)比較關(guān)鍵.在本研究中,運(yùn)用了一些前期預(yù)備實(shí)驗(yàn)對(duì)這兩個(gè)隨機(jī)數(shù)的取值范圍進(jìn)行探索.實(shí)驗(yàn)中,首先設(shè)置了一個(gè)前提假設(shè)：這兩個(gè)隨機(jī)數(shù)的取值范圍是基于 0對(duì)稱的;隨后,選擇不同的上下限范圍,并對(duì)研究中涉及的測(cè)試函數(shù)(Sphere函數(shù)、Ackley函數(shù)、Rastrigin函數(shù)、Styblinski-Tang函數(shù)、Duadric函數(shù)和Rosenbrock函數(shù))進(jìn)行預(yù)運(yùn)算;最后,對(duì)不同取值范圍下的優(yōu)化結(jié)果進(jìn)行評(píng)判.表2中列出了不同取值組合設(shè)置下的優(yōu)化結(jié)果優(yōu)劣比較——選用了[-2,2]范圍作為基準(zhǔn),將其他取值范圍的優(yōu)化結(jié)果與[-2,2]的優(yōu)化結(jié)果作對(duì)比.

· 若優(yōu)化結(jié)果比基準(zhǔn)要好,則認(rèn)為該取值范圍更優(yōu);否則,記為更差;

· 在極值為0的測(cè)試函數(shù)優(yōu)化中,若收斂精度差值不超過1,或者在極值非0的測(cè)試函數(shù)仿真中收斂誤差不超過1,則記為無差異;

· 基準(zhǔn)本身不進(jìn)行自身對(duì)比.

另外,在對(duì)不同的參數(shù)范圍進(jìn)行比較時(shí),我們將最優(yōu)值為0的函數(shù)占最終結(jié)果的比重為0.5,最優(yōu)值不為0的函數(shù)占最終結(jié)果的比重為0.5.由此,從表3中可以得出結(jié)論：當(dāng)r0,ra取值[-2,2]時(shí),對(duì)于最優(yōu)值為0以及非0的情況的綜合效果最好.

本研究中所引入的多級(jí)擾動(dòng)機(jī)制,實(shí)質(zhì)是在相對(duì)穩(wěn)定的優(yōu)化過程中加入隨機(jī)性和變異性,并且針對(duì)于仍未跳出局部最優(yōu)值的情況,提供了二級(jí)擾動(dòng),把粒子進(jìn)行大幅度的移動(dòng),從而擺脫當(dāng)前局部最優(yōu)值的影響.若二級(jí)擾動(dòng)引入后仍陷于局部最優(yōu)值,則再次引入二級(jí)擾動(dòng)….以此遞進(jìn),最多可進(jìn)行64次(前期實(shí)驗(yàn)表明,重復(fù)引入二級(jí)擾動(dòng)的次數(shù)在16,32,64,128這4種設(shè)置下,除Sphere函數(shù)外,其余的函數(shù)都不能體現(xiàn)出顯著差異.而Sphere函數(shù)則是在64次重復(fù)引入的情況下,優(yōu)化結(jié)果精度最高(見表4),因此,這里設(shè)置為64次).這是為了能在陷入無限循環(huán)之后,從其中跳脫出來的同時(shí)又能嘗試引入多次擾動(dòng)來擺脫局部最優(yōu).

Table 3 Result of different r0 & ra to optimization algorithms for different dimension of sixtest functions表3 不同r0 & ra的MPSO算法對(duì)于對(duì)于不同維度的6種測(cè)試函數(shù)的優(yōu)化結(jié)果表

Table 4 Result of four optimization algorithms for different max number of second disturb of five test functions表4 4種優(yōu)化算法對(duì)于二級(jí)擾動(dòng)不同最高次數(shù)的5種測(cè)試函數(shù)的優(yōu)化結(jié)果表

本研究使用了異步粒子群優(yōu)化算法的粒子更新方式[28].同步粒子群優(yōu)化算法的粒子更新方式是在一輪粒子全部更新得到適應(yīng)度值之后,再更新粒子最優(yōu)及群體最優(yōu).而這種異步的形式是在搜索中,當(dāng)任意一個(gè)粒子發(fā)現(xiàn)其計(jì)算的適應(yīng)值優(yōu)于共享信息中的適應(yīng)值時(shí),則立即更新共享信息,以此提高粒子的利用效率.同時(shí),粒子群算法根據(jù)鄰域內(nèi)粒子數(shù)量的不同,可以分為全局和局部兩個(gè)形式[1]：全局版本就是所有粒子都是其中某一顆粒子的鄰域成員,局部版本就是只有一部分粒子是某一顆粒子的鄰域成員.對(duì)于簡單的問題,鄰域內(nèi)的粒子越多,效果越好;對(duì)于復(fù)雜的多模問題,鄰域內(nèi)的粒子越少,效果越好[29],除此之外,還要一些其他的定義方式,如 4類結(jié)構(gòu)、金字塔結(jié)構(gòu)[28]、可變多簇結(jié)構(gòu)[30]等.MPSO采用的是異步全局粒子群算法的形式.

在對(duì)指定優(yōu)化問題進(jìn)行優(yōu)化時(shí),粒子的運(yùn)動(dòng)范圍往往都是限定的,因此需要對(duì)超出限定閾值的粒子進(jìn)行處理,處理方法一般有吸收墻、反射墻、衰減墻和隱匿墻[31].本研究運(yùn)用了重置的方法——將超出閾值的粒子重置在閾值邊界附近,此方法近似于反射墻,但是反射能力被大大削弱,可稱為弱反射墻.假設(shè)當(dāng)前問題限制的粒子閾值范圍為[-α,α],那么結(jié)合反射墻及衰減墻,可將弱反射墻的運(yùn)算定義為如公式(15)所示形式：

其中,r4為[0,1]之間的隨機(jī)數(shù).

算法整體的時(shí)間復(fù)雜度由原本的O(n)變?yōu)镺(cn),其中,c為一個(gè)常數(shù)(c＞1),取值與引入擾動(dòng)的次數(shù)呈正相關(guān);n與粒子維度d、種群粒子數(shù)m、最大迭代次數(shù)t有關(guān).

3 算法仿真實(shí)驗(yàn)

在本研究中,為了測(cè)試MPSO算法的有效性,選擇了6個(gè)函數(shù)——Sphere函數(shù)、Ackley函數(shù)、Rastrigin函數(shù)、Styblinski-Tang函數(shù)、Duadric函數(shù)及Rosenbrock函數(shù)來進(jìn)行測(cè)試.同時(shí),運(yùn)用現(xiàn)有的3個(gè)改進(jìn)PSO算法——SPSO,PSOCF和 PSO-DT[32]進(jìn)行相同條件的優(yōu)化運(yùn)算,再將三者的優(yōu)化過程與結(jié)果進(jìn)行對(duì)比與驗(yàn)證.仿真實(shí)驗(yàn)在Windows 10平臺(tái)中Eclipse環(huán)境中進(jìn)行,硬件配置為Inter i5-2430M,RAM 4GB.

3.1 測(cè)試函數(shù)

1. Sphere函數(shù).

函數(shù)在xi=0時(shí)達(dá)到全局最小值0,為單峰值函數(shù).函數(shù)表達(dá)式見公式(16).

2. Ackley函數(shù).

函數(shù)在xi=0時(shí)達(dá)到全局最小值0,且函數(shù)在解空間中存在大量局部極小值點(diǎn).函數(shù)表達(dá)式見公式(17).

3. Rastrigin函數(shù).

函數(shù)在xi=0時(shí)達(dá)到全局最小值 0,且函數(shù)在解空間中存在大量的正弦凸起的局部極小值點(diǎn).函數(shù)形式見公式(18).

4. Styblinski-Tang函數(shù).

函數(shù)在xi=-2.903534時(shí)達(dá)到全局最小值-39.16599乘上d(d為維度,表示自變量x的坐標(biāo)數(shù)目),且為多維多峰多局部最優(yōu)值函數(shù).函數(shù)表達(dá)式見公式(19).

5. Duadric函數(shù).

函數(shù)在xi=0時(shí)達(dá)到全局最小值 0,為單峰值多極值函數(shù).此函數(shù)與 Sphere函數(shù)類似,但是考慮了維度因素d(此處同樣為自變量x的坐標(biāo)數(shù)目),因此更容易陷入局部極值.函數(shù)表達(dá)式見公式(20).

6. Rosenbrock函數(shù).

函數(shù)在xi=0時(shí)達(dá)到全局最小值0,為單峰值凹槽型函數(shù).此函數(shù)在極值附近的值存在極微小的差別：

在標(biāo)準(zhǔn)粒子群優(yōu)化算法中,有關(guān)參數(shù)的設(shè)置通常是類似的.一般來說,學(xué)習(xí)因子c1,c2取值范圍為[0,2],在算法中一般取值為2.0,而ω則是從0.9遞減到0.4[21],見公式(22).

而在帶收縮因子的實(shí)驗(yàn)中,發(fā)現(xiàn)了當(dāng)c=c1+c2=4.1,根據(jù)公式(7),得到φ=0.729時(shí),PSOCF算法能夠較好的平衡探索及收斂能力[3].

因此,在本研究的仿真實(shí)驗(yàn)中,設(shè)置各個(gè)算法的粒子規(guī)模n為5,10,15和20;標(biāo)準(zhǔn)粒子群算法中,c1=c2=2;慣性權(quán)重ω采用對(duì)數(shù)遞減,從0.9對(duì)數(shù)遞減到0.4;帶收縮因子的粒子群算法中,收縮因子φ=0.729,學(xué)習(xí)因子c1=c2=2.05.

3.2 仿真實(shí)驗(yàn)結(jié)果與分析

通過仿真實(shí)驗(yàn),對(duì)上述4個(gè)函數(shù)進(jìn)行優(yōu)化測(cè)試：定義函數(shù)的全局極值為最優(yōu)值;運(yùn)用3種基于粒子群的優(yōu)化算法(混合粒子群優(yōu)化算法、標(biāo)準(zhǔn)粒子群優(yōu)化算法以及帶收縮因子的粒子群優(yōu)化算法)進(jìn)行優(yōu)化運(yùn)算;算法中,設(shè)置4種步長維度(5,10,15和20,表示優(yōu)化算法中粒子個(gè)數(shù))分別進(jìn)行運(yùn)算;單次優(yōu)化的終止條件為迭代次數(shù)達(dá)到2 000次;實(shí)驗(yàn)重復(fù)次數(shù)為10次,取平均值對(duì)不同設(shè)置和場(chǎng)景(函數(shù))分別進(jìn)行比較.前3個(gè)函數(shù)——Sphere函數(shù)、Ackley函數(shù)和 Rastrigin函數(shù)因其全局最小值都為零,因此優(yōu)化算法的優(yōu)化效果以其最終優(yōu)化結(jié)果值的精度表示,具體對(duì)比結(jié)果見表5.而Styblinski-Tang的全局最小值不為0,因此優(yōu)化結(jié)果以算法優(yōu)化值與函數(shù)極值之間的偏差來表示.偏差φ的計(jì)算方法由公式(23)計(jì)算而來：

其中,Vt為Styblinski-Tang函數(shù)的結(jié)果真值,op為優(yōu)化算法得到的結(jié)果值.具體的結(jié)果對(duì)比見表6.

Table 5 Result of four optimization algorithms for different dimension of five test functions表5 4種優(yōu)化算法對(duì)于不同維度類型的5種測(cè)試函數(shù)的優(yōu)化結(jié)果表

Table 6 Result of three optimization algorithms for different dimension of Styblinski-Tang test functions表6 3種優(yōu)化算法對(duì)于不同維度的Styblinski-Tang測(cè)試函數(shù)的優(yōu)化結(jié)果表

從表5可以看出,在優(yōu)化結(jié)果精度方面,在所有的4種不同維度設(shè)置下,本研究提出的MPSO算法對(duì)3種最優(yōu)值為 0的測(cè)試函數(shù)的優(yōu)化結(jié)果都顯著優(yōu)于另外兩種改進(jìn)算法的結(jié)果;并且在其他算法無法定位到最優(yōu)值的情況下,MPSO算法依然能夠找到最優(yōu)值,且具有較高的精度.具體來說,在Sphere和Ackley函數(shù)上,PSOCF算法也能找到正確的最優(yōu)值,但是在最后結(jié)果的精度上與MPSO算法仍有較大差距;對(duì)Rastrigin函數(shù)的優(yōu)化結(jié)果來說,PSOCF不能找到正確的最優(yōu)值,而MPSO的最終結(jié)果精度較高;而SPSO算法對(duì)這3個(gè)測(cè)試函數(shù)的優(yōu)化結(jié)果的精度都處于最低的位置,幾乎都未能定位到最優(yōu)值.

從維度上來說,隨著測(cè)試函數(shù)維度的提升,所有算法的優(yōu)化結(jié)果精度都相應(yīng)降低.從表5中可以看出,在實(shí)驗(yàn)中設(shè)置的維度范圍內(nèi),本研究提出的MPSO都能準(zhǔn)確的找到最優(yōu)值并保證一定的精度;SPSO算法在此范圍內(nèi)基本上都沒有能夠找到最優(yōu)值;PSOCF算法則是在對(duì)Sphere函數(shù)和Ackley函數(shù)的的優(yōu)化中,以5和10為維度時(shí)能夠找到最優(yōu)值并進(jìn)行一定的精度探索;但在15和20維度,則并不能夠找到最優(yōu)值.

整體優(yōu)化迭代過程如圖3～圖8所示.結(jié)合圖3～圖6可以發(fā)現(xiàn),在優(yōu)化前期(探索期),MPSO算法一直在探索,直到后半期轉(zhuǎn)入低幾率弱一級(jí)擾動(dòng)B后開始逐漸收斂,而在切換更新公式后進(jìn)行了快速收斂;而 SPSO算法則較為穩(wěn)定,一直在探索,最終并沒有很好地收斂在最優(yōu)值上;PSOCF算法則是在一開始就在最優(yōu)值附近開始快速收斂;PSODT與PSOCF算法類似,但是最終優(yōu)化結(jié)果的精度在5維度、10維度時(shí)沒有PSOCF算法精確.同時(shí)能夠發(fā)現(xiàn),其他3種算法在5維度、10維度的Sphere函數(shù)優(yōu)化時(shí)效果較好;在5維度、10維度的Ackley函數(shù)優(yōu)化時(shí)效果一般,但還是找到了最優(yōu)值,但在一定深度之后則趨于穩(wěn)定,不再繼續(xù)探索;而在其他情況下則并沒有找到最優(yōu)值,而是在局部最優(yōu)值附近進(jìn)行快速收斂.從圖中我們可以清楚地發(fā)現(xiàn)MPSO算法的特點(diǎn)：在探索期中,以探索為主;在后半優(yōu)化過程中,以快速收斂為主.這樣就能較好地在平衡探索與收斂基礎(chǔ)之上,優(yōu)化到最優(yōu)值.而從圖7能夠發(fā)現(xiàn)：無論哪種優(yōu)化算法在維度超過5時(shí),得到的優(yōu)化結(jié)果都不夠精確;但對(duì)同樣的優(yōu)化問題而言,本研究提出的混合型粒子群優(yōu)化算法總是能得到精度更高的優(yōu)化結(jié)果.

從時(shí)間上來說,本研究提出的MPSO算法中,耗時(shí)的主要是引入的多級(jí)擾動(dòng).因?yàn)槊看我胍患?jí)擾動(dòng)之后都要重新計(jì)算一次適應(yīng)度值,并因?yàn)樵缡於攵?jí)擾動(dòng)后,重新去引入一級(jí)擾動(dòng),所以整體時(shí)間為原本的2倍～4倍.多出的時(shí)間主要為計(jì)算適應(yīng)度值情況下,對(duì)原本算法的整體算法流程上所耗費(fèi)的時(shí)間并沒有增加,只是增加了一些引入擾動(dòng)后重新計(jì)算適應(yīng)度值的時(shí)間.

從表6可以看出,對(duì)最優(yōu)值不為0的Styblinski-Tang函數(shù)的優(yōu)化測(cè)試中,當(dāng)維度分別為5和10時(shí),MPSO算法的精確度較好;但當(dāng)維度為15和20時(shí),偏差接近3%.在考慮到真值較大的情況下,這種偏差率可以接受;SPSO算法在維度為5和10時(shí),偏差度達(dá)到了3%左右.雖然偏差度有些大,但還在可接受范圍;但是在維度為15時(shí),偏差超過了9%;而在維度為20時(shí),偏差更是達(dá)到了16%,這表示了偏差過大,優(yōu)化結(jié)果不夠準(zhǔn)確;而PSOCF算法在測(cè)試的維度為 5,10,15中的偏差都超過了 10%,在維度為 20時(shí)更是超過了 20%,說明 PSOCF算法對(duì)于Styblinski-Tang函數(shù)優(yōu)化能力很差;PSODT算法相對(duì)于SPSO和PSOCF算法來說要更為優(yōu)秀,但其優(yōu)化精度仍然不如MPSO算法高.結(jié)合圖8同樣也發(fā)現(xiàn),MPSO在前半優(yōu)化過程中以探索為主,在后半優(yōu)化過程中以快速收斂為主.這樣就能較好地在平衡探索與收斂基礎(chǔ)之上,優(yōu)化到最優(yōu)值.這也體現(xiàn)了MPSO算法在上述情況下的優(yōu)化結(jié)果都優(yōu)于其他兩種算法,同時(shí),耗費(fèi)時(shí)間大概為其他兩種算法的2倍～4倍.

4 結(jié) 論

針對(duì)經(jīng)典粒子群優(yōu)化算法易陷入局部最優(yōu)及收斂速度較慢等問題,本研究在分析經(jīng)典的兩種粒子群優(yōu)化算法SPSO和PSOCF的基礎(chǔ)上,提出了帶多級(jí)擾動(dòng)的混合型粒子群優(yōu)化算法.原始的粒子群優(yōu)化算法在多局部極值情況下容易陷入局部最優(yōu)值.SPSO和 PSOCF算法正式針對(duì)這一特點(diǎn)而進(jìn)行了改進(jìn).本研究中提出的MPSO算法結(jié)合了這兩種經(jīng)典改進(jìn)優(yōu)化算法的優(yōu)點(diǎn),引入多級(jí)擾動(dòng)的策略,利用多級(jí)擾動(dòng)干擾粒子探索進(jìn)程,使粒子在本身速度和位置更新之外,獲得了一種“震動(dòng)”,不但增長了算法對(duì)局部極值附近的探索能力,也擴(kuò)展了算法在陷入局部最優(yōu)值時(shí)的跳脫能力,從而在保證算法及時(shí)收斂的情況下,使粒子群優(yōu)化算法的探索能力和最優(yōu)值的精度上都得到極大的提升.

通常認(rèn)為,在PSO相關(guān)的算法中最重要的參數(shù)是慣性權(quán)重和學(xué)習(xí)因子[33].如何選擇、調(diào)整這些參數(shù),會(huì)直接影響粒子群優(yōu)化算法的收斂性和結(jié)果的有效性.在本文中,粒子更新公式中的慣性權(quán)重使用的是對(duì)數(shù)遞減形式.另外,還有其他方法對(duì)慣性權(quán)重進(jìn)行遞減用以針對(duì)不同的優(yōu)化問題,而如何結(jié)合具體優(yōu)化問題設(shè)置不同的慣性權(quán)重并加以應(yīng)用、如何對(duì)其他參數(shù)進(jìn)行適應(yīng)性設(shè)置以及如何根據(jù)迭代情況自適應(yīng)的去尋找最優(yōu)參數(shù),這些都沒能在本研究中進(jìn)行實(shí)驗(yàn)和探討.

本研究中對(duì)整個(gè)優(yōu)化周期進(jìn)行了簡單的定義——分為探索期和收斂期.在探索期內(nèi),粒子保持跳動(dòng)能力,對(duì)整個(gè)解空間進(jìn)行搜索;而過了探索期之后,則允許其進(jìn)行收斂.這樣的分割對(duì)學(xué)習(xí)因子和慣性權(quán)重的應(yīng)用起到了至關(guān)重要的作用.因此,研究中對(duì)兩個(gè)時(shí)期的切換時(shí)間點(diǎn)做了細(xì)致的前期實(shí)驗(yàn),而在后續(xù)的仿真實(shí)驗(yàn)中,發(fā)現(xiàn)前期實(shí)驗(yàn)所得的最佳切換時(shí)間點(diǎn)所處區(qū)間確實(shí)很好得平衡了搜索能力和收斂能力.另外,算法中運(yùn)用的兩個(gè)隨機(jī)參數(shù)r0和ra,取值對(duì)整體算法的優(yōu)化能力有比較關(guān)鍵的影響.本研究中,在基于經(jīng)驗(yàn)取值的基礎(chǔ)上,對(duì)著兩個(gè)參數(shù)的取值進(jìn)行了不同設(shè)置下的對(duì)比和前期驗(yàn)證.對(duì)于優(yōu)化算法中的參數(shù)取值,總是在不同的應(yīng)用場(chǎng)景下往往有不同的表現(xiàn).例如,本文提出的MPSO算法在對(duì)間作中的不同作物的間作模式有較好的優(yōu)化和預(yù)測(cè)作用,但其與對(duì)不同環(huán)境下的水稻田間種植模式優(yōu)化過程的參數(shù)設(shè)置和適應(yīng)度函數(shù)選取都有不同的策略.因此,很難說在普遍的場(chǎng)景下有一個(gè)通用的取值.在這種情況下,運(yùn)用其他較為成熟和穩(wěn)健算法先期對(duì)參數(shù)進(jìn)行優(yōu)化是一個(gè)比較好的選擇.另外,如果能開發(fā)出對(duì)不同場(chǎng)景自適應(yīng)調(diào)整的智能策略,將能夠比較有力地推動(dòng)優(yōu)化問題解決及優(yōu)化算法方面的研究.