基于種群關系的多種群粒子群協(xié)同優(yōu)化算法①

劉 悅,楊 樺,王青正

1（開封大學 信息工程學院,開封 475004）

2（上海交通大學 電子信息與電氣工程學院,上海 200240）

粒子群優(yōu)化算法（Particle Swarm Optimization,PSO）是1995年 Kennedy和Eberhart提出的一種隨機搜索算法[1],它模仿鳥群和魚群的群體覓食行為,通過種群中個體之間的協(xié)同進化在解空間內(nèi)搜索最優(yōu)解.種群中的每一個粒子被視為獨立個體,粒子通過自身的歷史位置信息以及整個種群的位置信息來對當前的速度和位置進行相應地調(diào)整.粒子群優(yōu)化算法具有操作簡單,收斂速度快的優(yōu)點,因此受到國內(nèi)外學者的廣泛關注.由于PSO的操作不關心優(yōu)化函數(shù)是否具有可微、連續(xù)等性質(zhì),所以應用PSO解決實際問題時更容易建模,具有很強的實用性,例如農(nóng)業(yè)、電力系統(tǒng)、自動控制、車輛制造[2-5],但是粒子群優(yōu)化算法在解決復雜多峰問題時,容易陷入局部最優(yōu)解.

目前,學者們采用多種改進方式來提高算法的全局搜索能力,主要包括:（1）改進拓撲結構.如Eberhart和Kennedy在文獻[6]中提出了局部版本的粒子群優(yōu)化算法,提出了環(huán)形拓撲結構,保證了搜索過程中粒子的多樣性.靳雁霞等在文獻[7]中,提出環(huán)狀全互聯(lián)結構,通過自適應逃逸機制,防止算法陷入局部最優(yōu).焦重陽等在文獻[8]中,提出混合拓撲結構,結合全局與局部尋優(yōu),將PSO應用于軟件測試,大大提高測試效果;（2）算法參數(shù)的改進.Shi和Eberhart在文獻[9]中為PSO的公式引入了慣性參數(shù),詳細分析了PSO速度公式的意義,從而在求解不同問題時可通過調(diào)整慣性參數(shù)來調(diào)節(jié)算法收斂速度和全局搜索能力,改善了算法的性能.董紅斌等在文獻[10]中,通過粒子最大適應值和最小適應值的指數(shù)函數(shù)來動態(tài)調(diào)整算法中的慣性權重,有利于算法跳出局部最優(yōu).（3）自適應PSO.如Gong和Zhang在文獻[11]中提出了自適應拓撲結構的改進,使算法在不同階段自適應地調(diào)整拓撲結構,顯著地提升了算法的精度.曹玉蓮等在文獻[12]中,提出基于擬熵的自適應局部搜索策略,融合具有高效收斂性的傳統(tǒng)局部搜索策略,提出混合自適應粒子群算法,提高算法性能.（4）多種群.Geng和Zhu在文獻[13]中提出了使用3個種群協(xié)同搜索的算法,其中一個種群按照PSO搜索,第2個種群搜索最優(yōu)位置附近,而第3個種群用于增強多樣性.Yan等在文獻[14]中使用多個子種群,并用一個種群來優(yōu)化PSO的參數(shù).Liang在文獻[15]中介紹了一種動態(tài)多種群PSO算法（DMSPSO）,通過重組策略使粒子歸屬的種群動態(tài)變化,增強了算法的性能.胡成玉等在文獻[16]中,提出了基于斥力勢場的多粒子群算法.但是上述算法未明確定義種群關系和種群交互策略,尋優(yōu)能力有限,并且未與其他主流粒子群改進算法進行對比.曾輝等在文獻[17]中,將自適應與多種群結合,提出自適應多種群粒子群搜索方法,但是該方法未對種群關系進行定義,文中探測與開采的平衡十分依賴于調(diào)參,搜索速度與精度的平衡未在實驗結果中明確說明.

本文從種群關系和斥力因子的角度出發(fā),提出一種新的多種群粒子群優(yōu)化算法SRB-PSO（Swarm-Relation-Based PSO）,使用多個種群分別按照PSO算法獨立地搜索,依據(jù)種群粒子的適應值判定兩個種群間的關系,定義了“統(tǒng)治”、“對等”和“被統(tǒng)治”3種關系,算法根據(jù)種群間關系自適應采取種群間影響策略:（1）通過在對等種群間使用斥力因子來維持不同種群在不同區(qū)域搜索,從而增強了搜索的多樣性,有助于跳出局部最優(yōu)值,避免過早收斂;（2）通過使被統(tǒng)治種群向統(tǒng)治它的種群收斂,相比單純的多種群算法,提高了搜索的效率,加快了收斂速度.由于每個種群在獨立搜索時仍然依照PSO算法進行搜索,其他針對各種場景下單種群PSO算法的改進方法可以直接應用在各個種群上,因此SRB-PSO算法具有良好的可擴展性.本文最后通過實驗將SRB-PSO與全局版本PSO和局部版本PSO對比,結果表明,SRB-PSO在求解多峰問題時性能最優(yōu),且求解單峰問題時優(yōu)于局部版本的PSO.

1 全局和局部粒子群優(yōu)化算法

1.1 全局版本的PSO

粒子群優(yōu)化算法使用一定數(shù)量的粒子在搜索空間中飛行,每個粒子具有各自的速度,并會記錄各自的歷史最優(yōu)位置pbest以及整個種群的最優(yōu)位置gbest.每次迭代將計算粒子適應值,更新最優(yōu)位置,然后按照式（1）更新粒子的速度,并根據(jù)式（2）更新粒子的位置.持續(xù)迭代直到滿足終止條件,終止條件可以是評估次數(shù)達到上限、迭代次數(shù)達到規(guī)定次數(shù)、最優(yōu)解已滿足需求.算法的流程圖如圖1所示.

圖1 粒子群優(yōu)化算法的流程

具體公式為:

式（1）是更新粒子速度的公式,vid表示粒子i的速度在d維的分量,pbestid表示粒子的歷史最優(yōu)位置的d維坐標,xid表示粒子i的當前位置的d維坐標,gbestd表示群體最優(yōu)位置的d維坐標,c1、c2是常數(shù),rand1（）和rand2（）是隨機數(shù)函數(shù),產(chǎn)生0至1的隨機數(shù).式中第2項體現(xiàn)了粒子根據(jù)自身經(jīng)驗對搜索狀態(tài)的調(diào)整,第3項體現(xiàn)了種群最優(yōu)粒子對粒子搜索狀態(tài)的引導.式（2）表示依據(jù)速度更新粒子位置的公式.

算法通過設定最大速度來限定粒子的速度范圍,它限制粒子在空間飛行的最大速度.如果最大速度太大,粒子更容易越過最優(yōu)解,降低了算法的搜索精度,如果最大速度太小,粒子不能進行更廣泛的探索,容易陷入局部最優(yōu)解.通常最大速度是根據(jù)求解空間大小乘以常數(shù)系數(shù)設定的,當粒子更新后的速度大小超過最大速度時,速度大小被設定為最大速度.此外,式（2）得到的粒子的新位置可能會超出搜索空間,當粒子位置在某維度上超出邊界時,粒子在該維度的坐標被置為邊界值.

文獻[6]中為粒子群優(yōu)化的速度公式引入了新的參數(shù)w,速度更新公式對應修改為式（3）.

文獻[6]中指出,粒子群優(yōu)化算法的速度公式既體現(xiàn)了搜索空間中更廣泛的區(qū)域,又體現(xiàn)了向已知較優(yōu)區(qū)域收斂以獲得最優(yōu)值,參數(shù)的選取體現(xiàn)了對這兩方面的權衡.不同問題對擴展搜索空間和收斂能力的權衡通常是不同的,因此,相比式（1）,式（3）引入了慣性參數(shù)w,從而提供了更多的權衡空間,通過選取恰當?shù)膮?shù)w,算法的性能將會大幅改善,這一改進策略已被廣泛使用.

1.2 局部版本的PSO

Eberhart和Kennedy在文獻[6]中詳細介紹并測試了兩個版本的粒子群優(yōu)化算法,分別為全局版本和局部版本的PSO.全局版本即前文所述的算法,粒子的速度受自身經(jīng)驗的調(diào)整和群體最優(yōu)粒子的引導; 而局部版本中粒子的速度則受自身經(jīng)驗的調(diào)整和拓撲鄰域最優(yōu)粒子的引導.這兩種版本的算法的區(qū)別在于,粒子間信息交互的拓撲結構不同.全局版本中,所有粒子構成一個完全圖,因此每個粒子都能獲悉整個種群所經(jīng)過的最優(yōu)位置并受其引導,而在局部版本中,粒子并不能獲悉整個種群所經(jīng)過的最優(yōu)位置,而只能獲悉它的鄰域粒子所經(jīng)過的最優(yōu)位置,比如,1個粒子只有2個鄰居,則所有粒子構成一個環(huán)形的拓撲結構.

從局部版本使用的拓撲結構分析,每個粒子僅能獲知其鄰域粒子經(jīng)過的最優(yōu)位置,因此多數(shù)粒子并不會很快向全種群最優(yōu)位置收斂,而是在不同區(qū)域進行了相對獨立的搜索,從而保持了粒子的多樣性.全局版本的PSO具有更快的收斂速度,相比之下,使用環(huán)形拓撲結構的局部版本PSO盡管收斂速度慢,卻擁有更強的全局搜索能力,更加不易陷入局部最優(yōu)解.

2 基于種群關系的SRB-PSO算法

盡管環(huán)形拓撲結構PSO相比傳統(tǒng)PSO在全局搜索能力方面有了很大的改觀,但也存在著以下缺陷:如果一些粒子在探索適應值很差的空間,由于使用了環(huán)形拓撲結構,粒子之間相對比較獨立,這些粒子在向好的區(qū)域收斂之前,將在這個很差的空間進行大量的探索,而這些探索是無意義的,浪費了計算資源.對于單峰問題,環(huán)形拓撲結構使收斂速度慢了很多,在相同計算量的情況下,相比傳統(tǒng)PSO,算法的精度將會大幅下降; 此外,環(huán)形拓撲結構帶來的全局搜索能力增強也是有限的,對很多帶有大量局部最優(yōu)的復雜多峰問題仍會陷入局部最優(yōu)解.

針對以上缺陷,本文提出了一種新的算法SRBPSO,使用多個種群,分別按照PSO算法搜索,并且在種群之間引入斥力因子,從而使不同種群進行相對獨立的搜索,以獲得更強的全局搜索能力,同時使用一定的收斂機制,以使算法的收斂速度得到保證.SRBPSO算法的流程圖如圖2所示.下文將分別就各關鍵操作進行詳細介紹與分析,最后給出整體的流程綜述.

圖2 引入斥力因子的多種群PSO流程圖

2.1 初始化種群

SRB-PSO中使用多個種群,令不同種群進行相對獨立的搜索.如使用n個種群進行搜索,通過將求解空間的隨機某個維度等分為n段,從而對應將求解空間劃分為n個子空間,在每個子空間中分別初始化一個種群.這樣的設定使不同種群從初始化時開始,就具有很強的獨立性.

2.2 SRB-PSO的4個階段

SRB-PSO的種群間交互是影響算法性能的重要因素.在算法的不同階段有不同的需求,種群間影響的施加頻率是不同的.在算法的前中期,每個種群比較獨立地進行搜索,從而種群間的影響是不施加的或是低頻施加的; 在算法中后期,種群之間的交互將被高頻施加,以通過種群間的交互取得更好的結果; 在算法末期,所有種群合并為一個種群收斂,以提高算法的精度.算法據(jù)此分為4個階段,分別為:獨立搜索期、弱影響期、強影響期和收斂期.

（1）獨立搜索期:應用于算法運行的初期,在這個階段,各個種群進行完全獨立的搜索,即各個種群的粒子都依據(jù)自身經(jīng)過的最優(yōu)位置、本種群經(jīng)過的最優(yōu)位置,來調(diào)整自己的速度,不同種群之間在這個階段沒有任何的交互,即任何一個種群都覺察不到其他種群的存在,而是各自按照傳統(tǒng)PSO進行搜索.由于各個種群初始化在求解空間的不同子空間,因此各個種群之間的搜索具有很強的獨立性,具有較強的全局搜索能力.這個階段結束后,每個種群都會獲得初步的搜索結果.

（2）弱影響期:這個階段種群間的影響在算法迭代中被間歇地施加,依據(jù)不同種群的求解現(xiàn)狀,引入外種群的影響來幫助種群進化.每隔一定的迭代次數(shù),就會依據(jù)當前各個種群的搜索狀態(tài),對每個種群施加來自外種群的影響,具體操作是該種群的每個粒子的速度會受到外種群粒子的影響.影響策略共有3種,分別是:向外種群收斂、受到外種群排斥和不受外種群影響,這些策略的設定是基于收斂速度和全局搜索兩方面考慮的,具體的策略選擇在下文將被詳細介紹.值得強調(diào)的是,在弱影響期,種群間的影響是被間歇地施加的,在兩次施加之間,種群的搜索行為仍然是完全獨立的.

（3）強影響期:在算法運行的中后期,種群間的影響將被施加到每次迭代.在這個階段,一個種群的粒子在每次迭代中,都同時受到所屬種群和其他種群的影響,具體影響策略與弱影響期相同,區(qū)別在于每次迭代都施加種群間影響.

（4）收斂期:在算法運行的末期,所有種群通過合并,形成一個種群,執(zhí)行單種群的搜索算法,綜合之前所有的結果,最終使得算法逐漸收斂,得到最優(yōu)結果.

2.3 種群間影響策略

在算法的弱影響期和強影響期,種群之間通過交互從而提高搜索性能.但最優(yōu)種群,即歷史最優(yōu)位置所在的種群,并不會受到其他種群的影響,因為通常其他種群的影響會對最優(yōu)種群產(chǎn)生干擾,影響最優(yōu)種群的收斂速度.

施加某個種群受到的外種群的影響時,首先會評估該種群與外種群的相對關系,以使用不同的影響策略.影響策略的偽代碼如算法1所示.在這個算法中,種群與外種群的相對關系被定義為3種:統(tǒng)治、對等和被統(tǒng)治.評估基于兩個參量,average-fitness與gbest-fitness,前者是種群所有粒子的當前適應值的平均值,后者則是該種群的歷史最優(yōu)適應值.評估規(guī)則如表1所示.

表1 種群間關系評估表

根據(jù)評估規(guī)則,種群間的3種關系定義如下:種群統(tǒng)治外種群,當且僅當種群的average-fitness與gbestfitness均優(yōu)于外種群; 種群與外種群對等,當且僅當種群的average-fitness與gbest-fitness中,一項優(yōu)于外種群而另一項差于外種群; 種群被外種群統(tǒng)治,當且僅當種群的average-fitness與gbest-fitness都比外種群差.確認了種群與外種群的關系后,依據(jù)關系分別施加以下策略:

（1）種群統(tǒng)治外種群,則該種群不受外種群影響.當種群統(tǒng)治外種群時,認為該種群正探索的區(qū)域遠好于外種群的區(qū)域,因此不會受到外種群的影響.

（2）種群與外種群對等,則該種群的粒子受到外種群gbest位置的排斥,且這個斥力反比于粒子與外種群gbest的距離,以A、B分別表示種群與外種群,i表示粒子,d表示維度,種群粒子的速度公式變更為式（4）.

c3是算法引入的新參數(shù)—斥力因子,它影響種群間斥力的大小,Decreasing（）是一個二次衰減函數(shù),隨迭代次數(shù)增加由1衰減至0.這種策略的意義在于,當種群與外種群具有相仿的搜索結果時,種群的粒子將受到外種群的斥力,且斥力大小反比于粒子與外種群gbest位置的距離,從而保持與外種群在相對獨立的區(qū)域搜索,增強算法的全局搜索能力,避免所有種群都向某個局部最優(yōu)收斂.衰減函數(shù)的引入使種群間斥力在算法前中期時很大,作用明顯,隨迭代次數(shù)增加其作用逐漸減弱,以使不同種群在進行獨立搜索的同時兼顧收斂性能.此外,施加種群間影響后,算法檢查新的速度大小是否超出最大速度,如果超出,則將速度大小置為最大速度,從而保證搜索的精度.

（3）種群被外種群統(tǒng)治,則該種群放棄當前的搜索區(qū)域,向外種群收斂.具體的實現(xiàn)是將每個粒子的pbest位置依次對應改為外種群每個粒子的pbe st位置,將該種群的gbe st位置改為外種群的gbe st位置.

當種群被外種群統(tǒng)治時,認為種群正搜索的空間明顯差于外種群正搜索的空間,因此放棄種群正搜索的區(qū)域,向外種群區(qū)域轉移.這個策略節(jié)約了搜索資源,可以提高算法的收斂速度.

2.4 算法綜述

算法使用多個種群,在解空間的等分子空間進行分別初始化.首先在獨立搜索期,每個種群進行完全獨立的搜索.接著在弱影響期和強影響期,種群將被施加外種群間的影響,算法定義了統(tǒng)治、對等、被統(tǒng)治3種種群間關系.被統(tǒng)治的種群將放棄當前搜索區(qū)域,轉而向統(tǒng)治它的種群收斂; 對等的種群則會互相產(chǎn)生斥力,從而保持在相對獨立的空間搜索.但最優(yōu)種群并不會受到外種群的影響,以避免其他種群干擾最優(yōu)種群的收斂,同時可以避免這種情況:兩個種群都圍繞著最優(yōu)解收斂卻因互斥都無法進一步靠近最優(yōu)解.斥力將隨迭代次數(shù)增加而減弱,且在算法末期所有粒子將被整合為一個種群,這樣的操作大大提高了算法的收斂速度.接下來本文將通過實驗測試算法性能.

3 實驗分析

3.1 測試函數(shù)與參數(shù)設定

為驗證性能,將SRB-PSO與全局版本以及局部版本的PSO進行對比.實驗使用文獻[4]中的12個測試函數(shù),如表2所示,函數(shù)維度D取30.其中f1至f4是單峰函數(shù),f5是階梯函數(shù),f6是帶噪音的四次函數(shù),f7至f12是有大量局部最優(yōu)解的多峰函數(shù).將評估次數(shù)設定為300 000,分別使用3種算法對這13個測試函數(shù)求最小值,每個算法獨立運行30次,記錄并對比30次運行的最優(yōu)結果、平均結果與方差.

表2 測試函數(shù)

為確保比較的公平性,3種算法使用的基本參數(shù)相同,分別為:慣性參數(shù)w=0.55,c1=c2=2,速度上限為解空間一維長度的0.04倍.全局版本與局部版本的PSO種群規(guī)模均為60,迭代5000次.新算法總粒子數(shù)也為60,迭代5000次,但使用5個種群,每個種群的規(guī)模為12,此外,如前文所述,SRB-PSO在此基礎上引入了種群關系和斥力因子,分為4個執(zhí)行階段,實驗中取斥力因子c3=0.001,前1000次迭代為獨立搜索期,第1001-3000次迭代為弱影響期,弱影響期內(nèi)每50次迭代施加一次種群間影響,第3001-4500次迭代為強影響期,最后500次迭代為收斂期.

3.2 測試結果與分析

算法每次運行后計算算法所得最小值與函數(shù)理論最小值的誤差,針對每個測試函數(shù),統(tǒng)計30次運行的平均誤差、最小誤差、方差.小的平均值意味著算法的求解精度更高,穩(wěn)定性更好,小的方差進一步體現(xiàn)了算法的穩(wěn)定性.結果在表3中列出,加粗表明該算法的該項結果是3種算法中最優(yōu)的,斜體表示該算法的該項結果強于另兩種算法中的一種.

表3 3種算法的平均值、最佳值與方差結果

算法對f1至f6的結果體現(xiàn)算法對單峰問題的求解性能,對f7至f12的結果體現(xiàn)算法對多峰問題的求解性能.表3結果表明,傳統(tǒng)PSO在求解單峰問題時性能最優(yōu),SRB-PSO在求解多峰問題時性能最優(yōu).為進一步分析實驗結果,針對每個函數(shù)的實驗結果作箱線圖,箱線圖能夠更直觀地表現(xiàn)算法的精度和穩(wěn)定性.首先分析3種算法對單峰問題的求解性能,3種算法求解f1至f6的結果在圖3中以箱線圖表示.

圖3表明,對于單峰問題,3種算法中,傳統(tǒng)的全局版本PSO有最優(yōu)的精度和穩(wěn)定性,這與理論分析是一致的,因為局部版本的PSO和新算法都一定程度上犧牲了收斂速度來提升全局搜索能力.還可以發(fā)現(xiàn),新算法的精度與穩(wěn)定性明顯強于局部版本的PSO.這表明新算法比局部版本的PSO擁有更強的對單峰問題的優(yōu)化能力.其中誤差范圍表示算法的穩(wěn)定性,可以看出新算法誤差范圍在大多數(shù)測試案例中都表現(xiàn)出了更高的穩(wěn)定性,而對于多峰問題,考慮表3結果中的f7至f12,傳統(tǒng)全局PSO的性能顯然落后于局部版本PSO和新算法.對于多峰問題求解的實驗結果在圖4中進一步以箱線圖表示.

圖3 3種算法求解單峰問題結果的箱線圖

圖4 3種算法求解多峰問題結果的箱線圖

圖4表明,相比傳統(tǒng)PSO,新算法與局部版本的PSO對多峰問題都有很高的求解精度和穩(wěn)定性.表3數(shù)據(jù)顯示,新算法在f8,f9,f10,f12,f13上的性能都優(yōu)于局部版本PSO,僅在f11上稍有落后.綜合來看,新算法對于多峰問題的求解性能最優(yōu).同時新算法在問題求解的穩(wěn)定性上,在所有案例當中都最高,可以看出新算法對于多峰問題求解有非常好的穩(wěn)定性.

以上實驗結果可總結為:傳統(tǒng)PSO對求解單峰問題有最優(yōu)的性能,但在求解多峰問題時誤差較大; 局部版本的PSO求解單峰問題的精度最差,但求解多峰問題的性能較強; 新算法求解多峰問題的性能最優(yōu),且新算法求解單峰問題的性能明顯優(yōu)于局部版本的PSO.

4 結論與展望

粒子群優(yōu)化算法是一種操作簡單、收斂速度快的智能優(yōu)化算法,通過對算法進行一定的改進,可以提高算法在求解多峰問題時的性能.本文提出一種多種群粒子群優(yōu)化算法SRB-PSO,并引入斥力因子來保證不同種群的個體之間搜索全局最優(yōu)解時的相對獨立性,從而加強了算法中期的全局搜索能力.文章通過實驗對算法性能進行了系統(tǒng)性地對比與分析.實驗結果表明,相對于全局版本以及局部版本的粒子群優(yōu)化算法而言,本文提出的多種群粒子群優(yōu)化算法在解決多峰問題時具有更高的求解精度.因此算法在全局搜索能力上優(yōu)于傳統(tǒng)的粒子群優(yōu)化算法.