一種基于雙子群的改進(jìn)粒子群優(yōu)化算法*

張英杰,李 亮,張英豪,羅春松

(1.湖南大學(xué)計(jì)算機(jī)與通信學(xué)院,湖南長沙 410082;2.湖南機(jī)電職業(yè)技術(shù)學(xué)院,湖南長沙 410151)

一種基于雙子群的改進(jìn)粒子群優(yōu)化算法*

張英杰1?,李 亮1,張英豪2,羅春松1

(1.湖南大學(xué)計(jì)算機(jī)與通信學(xué)院,湖南長沙 410082;2.湖南機(jī)電職業(yè)技術(shù)學(xué)院,湖南長沙 410151)

針對粒子群優(yōu)化算法易于陷入局部最優(yōu)解并存在早熟收斂的問題,提出了一種基于雙子群的改進(jìn)粒子群優(yōu)化算法(TS-IPSO),通過2組搜索方向相反的主、輔子群之間的相互協(xié)同,擴(kuò)大搜索范圍,借鑒遺傳算法的雜交機(jī)制,并采用慣性權(quán)值的非線性遞減策略,加快算法的收斂速度和提高粒子的搜索能力,降低了算法陷入局部極值的風(fēng)險.實(shí)驗(yàn)結(jié)果表明該算法較標(biāo)準(zhǔn)PSO算法提高了全局搜索能力和收斂速度,改善了優(yōu)化性能.

收斂性;粒子群優(yōu)化算法;子群;雜交機(jī)制;遺傳算法

粒子群優(yōu)化算法(Particle Swarm Op timization,PSO)是一種基于群體的演化算法,是通過群體內(nèi)粒子間的合作與競爭產(chǎn)生的群體智能指導(dǎo)優(yōu)化策略,最早由Kennedy和Eberhart于 1995年提出的[1].該算法操作簡單,前期收斂速度快、設(shè)置參數(shù)少、容易實(shí)現(xiàn)、能有效地解決復(fù)雜優(yōu)化問題,在函數(shù)優(yōu)化、模式識別、機(jī)器人學(xué)習(xí)、組合優(yōu)化以及一些工程領(lǐng)域得到了廣泛應(yīng)用.但由于PSO算法的數(shù)學(xué)基礎(chǔ)相對薄弱,存在早熟收斂、搜索精度不高、后期迭代效率低[2]的缺點(diǎn),尤其是當(dāng)解空間為非凸集時,應(yīng)用PSO算法容易在后期陷入局部極優(yōu)點(diǎn).針對這些問題,目前出現(xiàn)了許多改進(jìn)算法,如文獻(xiàn)[3]用動態(tài)調(diào)整慣性權(quán)重來平衡搜索能力和收斂速度;文獻(xiàn)[4]通過對粒子位置或速度引入一個小概率隨機(jī)變異操作來增強(qiáng)種群的多樣性,使算法能有效地進(jìn)行全局搜索;文獻(xiàn)[5]提出了一種帶有混沌變異算子的量子粒子群優(yōu)化算法,文中利用混沌序列代替隨機(jī)序列從而增加粒子的多樣性,防止粒子陷入局部收斂;文獻(xiàn)[6]提出了一種新的雙子群PSO算法(TSPSO).

大量研究實(shí)驗(yàn)表明,設(shè)法保持種群的多樣性,或引入跳出局部最優(yōu)點(diǎn)的機(jī)制,或與其他算法融合可以克服全局優(yōu)化算法早熟收斂.鑒于此,本文在文獻(xiàn)[6]的基礎(chǔ)上提出了一種改進(jìn)粒子群優(yōu)化算法(TSIPSO),該算法在不增加粒子規(guī)模的情況下充分?jǐn)U展搜索范圍,挖掘搜索域內(nèi)的有用信息,并借鑒了遺傳算法的雜交機(jī)制,還采用慣性因子的非線性遞減策略,以有效地提高粒子的探索能力,解決粒子群算法的局部收斂問題.

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

PSO算法通過模擬鳥群捕食行為實(shí)現(xiàn)優(yōu)化問題的求解.首先在解空間內(nèi)隨機(jī)初始化鳥群,鳥群中的每一只鳥稱為粒子,這些粒子在解空間內(nèi)按照某種規(guī)則移動,經(jīng)過若干次修正后找到最優(yōu)解.在每一次修正中,粒子通過跟蹤兩個極值來更新自己的速度和位置.一個是粒子本身的最優(yōu)解p,另一個是整個種群目前找到的最優(yōu)解g.每個粒子根據(jù)p和g修正自身的飛行方向和飛行速度,使得每個粒子最終能夠發(fā)現(xiàn)并到達(dá)解空間內(nèi)最優(yōu)解位置.

假設(shè)搜索空間是D維,粒子群由m個粒子組成.Xi=(xi1,xi2,…,xid)表示D維空間中的第i個粒子,其速度為Vi=(vi1,vi2,…,vid),其最大值為一個指定閾值 V max.粒子的速度-位置進(jìn)化方程為:

式中:i=1,2,…,m;d=1,2,…,D;C1,C2為非負(fù)常數(shù),一般取2.0;rand1,rand2為介于[0,1]之間服從均勻分布的隨機(jī)數(shù);Pi=(pi1,pi2,…,pid)為粒子i當(dāng)前所經(jīng)歷的最優(yōu)位置,稱為個體最優(yōu)位置;Pg =(pg1,pg2,…,pg d)為群體中所有粒子所經(jīng)歷的最優(yōu)位置,稱為全局最優(yōu)位置.慣性權(quán)值ω按式(3)線性遞減:

式中:ωstart為始權(quán)值;ωend為終權(quán)值 ,并建議 ωstart和ωend分別取0.9和0.4;Iter max和Iter分別為最大迭代次數(shù)和當(dāng)前迭代次數(shù).

2 基于雙子群的TS-IPSO算法

2.1 雙子群PSO算法(TSPSO)[6]

TSPSO算法是一種操作簡單、易于實(shí)現(xiàn)的雙子群的PSO算法,其實(shí)現(xiàn)思想為:在隨機(jī)初始化一組粒子群之后,將其等分為2個相互獨(dú)立的子群,其中一組子群按標(biāo)準(zhǔn)PSO算法迭代搜索,稱為主子群;另一組子群沿主子群的相反方向迭代搜索,即位置進(jìn)化方程按下式更新:

該子群稱為輔子群.在每次迭代結(jié)束時,比較2個子群個體最優(yōu)位置所對應(yīng)的適應(yīng)值大小,適應(yīng)值較差的個體最優(yōu)粒子被更優(yōu)者替代.這樣通過主、輔2個子群相互補(bǔ)充、協(xié)同進(jìn)化,在不增加粒子規(guī)模的情況下,充分?jǐn)U展搜索范圍,挖掘搜索域內(nèi)的有用信息,降低PSO算法陷入局部最優(yōu)點(diǎn)的風(fēng)險.

2.2 雜交機(jī)制

遺傳算法是模擬達(dá)爾文的自然選擇學(xué)說的生物進(jìn)化過程的一種計(jì)算模型,是一種隨機(jī)搜索最優(yōu)化計(jì)算方法,具有的基本操作運(yùn)算是選擇、雜交和變異等.文獻(xiàn)[2]借鑒遺傳算法的雜交操作運(yùn)算思想,最早提出了雜交PSO算法的概念.該算法在每次迭代中,選取指定數(shù)量的粒子放入一個池中,種群中被選中的粒子被賦予了一個隨機(jī)的與適應(yīng)值無關(guān)的雜交概率,依據(jù)雜交概率對池中的粒子隨機(jī)進(jìn)行雜交操作,產(chǎn)生同樣數(shù)目的孩子粒子,并用孩子粒子代替父母粒子,以保持種群的粒子數(shù)目不變.孩子粒子位置由父母粒子位置的算數(shù)加權(quán)來計(jì)算[7],即

式中:X1(t)和X2(t)為選擇進(jìn)行雜交操作的粒子,且都是D維的位置向量;r為D維均勻分布的且每個分量都在[0,1]取值的隨機(jī)向量.

孩子粒子的速度由下面的公式得到:

式中:V1(t)和V2(t)為進(jìn)行雜交操作的雙親粒子的速度.這樣,子代粒子的位置和速度的信息來自父代粒子的位置和速度的交叉操作.交叉操作使后代粒子繼承了雙親粒子的優(yōu)點(diǎn),這在理論上加強(qiáng)了對粒子間區(qū)域的搜索能力.假設(shè)兩個雙親粒子均處于不同的局部最優(yōu)區(qū)域,那么兩者交叉產(chǎn)生的后代粒子往往能夠擺脫局部最優(yōu),獲得改進(jìn)的搜索結(jié)果.數(shù)值實(shí)驗(yàn)結(jié)果表明,雜交粒子群算法比原始粒子群算法搜索速度更快,收斂精度更高.

2.3 慣性因子選擇策略

慣性權(quán)值ω的取值對算法性能有影響,如果 ω的取值隨著算法迭代的進(jìn)行而線性減小,那么算法的性能可明顯地得到改善.若ω取值較大,則粒子的全局搜索能力較強(qiáng);若ω取值較小,則粒子的局部挖掘能力增強(qiáng).

根據(jù)文獻(xiàn)[8]選擇一種自適應(yīng)的非線性慣性權(quán)值遞減函數(shù),具體表達(dá)式為:

式中:t max為群體的最大迭代次數(shù);ti為當(dāng)前的迭代代數(shù);ωstart,ωend分別為初始慣性權(quán)重的最大值和最小值.以式(9)構(gòu)造的慣性因子,初期具有最大值,迭代的最后一步達(dá)到最小值,中間迭代周期是非線性減小的,目的是在迭代的早期加大慣性權(quán)值的遞減速度來讓算法更快地進(jìn)入局部搜索,均衡全局和局部搜尋能力.文獻(xiàn)[8]證明了采用慣性因子非線性遞減機(jī)制的算法性能相對線性縮小慣性因子的PSO的收斂速度更快,能獲得更好的求解質(zhì)量.

2.4 TS-IPSO的算法步驟

綜上所述,本文提出了一種新的粒子群優(yōu)化算法 ——基于雙子群的改進(jìn)粒子群算法(TS-IPSO),其算法步驟如下:

1)隨機(jī)初始化粒子群中粒子的位置與速度.

2)將隨機(jī)初始化的粒子群等分為2組子群.計(jì)算每個粒子的適應(yīng)值,設(shè)置Pi為初始群體的當(dāng)前位置,Pg為最優(yōu)粒子位置.

3)判斷算法收斂準(zhǔn)則是否滿足,如果滿足執(zhí)行8),否則轉(zhuǎn)向4).

4)主子群根據(jù)式(1),式(2)和式(9)更新粒子的位置與速度,輔子群按式(1),式(4)和式(9)更新粒子的位置與速度;并對主、輔子群進(jìn)行速度、位置限制.當(dāng)Vi＞V max或Vi＜V m in時,則令Vi=V max或Vi=Vmin;當(dāng) Xi＞Xmax或 Xi＜Xmin時 ,則令 Xi= X max或Xi=X min.

5)更新主、輔子群個體最優(yōu)位置和全局最優(yōu)位置,如果粒子的適應(yīng)值優(yōu)于Pi的適應(yīng)值,則Pi更新為新位置,反之保持不變;如果粒子的適應(yīng)值優(yōu)于Pg的適應(yīng)值,則Pg更新為新位置,反之保持不變;然后比較兩組子群的個體最優(yōu)位置所對應(yīng)的適應(yīng)值,優(yōu)者更新為兩組子群共同的個體最優(yōu)位置.同樣,比較兩組子群的全局最優(yōu)位置所對應(yīng)的適應(yīng)值,優(yōu)者更新為整個粒子群的全局最優(yōu)位置.

6)根據(jù)適應(yīng)度值計(jì)算每個個體的選擇概率,通常按線性排名計(jì)算.

7)執(zhí)行選擇、雜交操作,按式(7),式(8)對每2個粒子的速度進(jìn)行雜交操作,若當(dāng)Vi＞V max或Vi＜Vmin時,則令Vi=Vmax或Vi=Vmin;按式(5),式(6)對每2個粒子的位置進(jìn)行雜交操作,若當(dāng)Xi＞X max或Xi＜X min時,則令Xi=X max或Xi=X m in,生成新一代種群.

8)檢查是否滿足PSO算法終止條件,若否,轉(zhuǎn)向4),繼續(xù);若是,則求出最優(yōu)解.

3 TS-IPSO算法仿真

下面采用4個基準(zhǔn)測試函數(shù)[9]來評價所提出的基于雙子群的改進(jìn)粒子群算法(TS-IPSO)的性能,并與標(biāo)準(zhǔn)PSO算法進(jìn)行了比較.這4個基準(zhǔn)測試函數(shù)如下所示:

其中:函數(shù)f1(x)為一個簡單的單峰函數(shù),在(0,0,…,0)達(dá)到極小值;f2(x)的全局極小點(diǎn)在xi=0(i =1,2,…,n),且有眾多的局部極小點(diǎn),可用來考查算法避免陷入局部最優(yōu)點(diǎn),并進(jìn)行全局探索的能力; f3(x)為具有大量局部極值點(diǎn)的多峰函數(shù),一般算法難以求得最優(yōu)解,且函數(shù)存在一個全局最小值f min=0;f4(x)是一個非凸函數(shù),在(1,1,…,1)時達(dá)到最小值0.文獻(xiàn)[10]論述了上述4個函數(shù)能有效驗(yàn)證PSO算法的尋優(yōu)性能及代表性.4個測試函數(shù)的參數(shù)設(shè)置如表1所示.

表1 4個基準(zhǔn)測試函數(shù)的參數(shù)設(shè)置Tab.1 Parameter settings of four benchmark functions

在TS-IPSO算法中,學(xué)習(xí)因子 C1,C2均取1.496 2,rand1,rand2為在區(qū)間[0,1]內(nèi)均勻分布的隨機(jī)數(shù),慣性權(quán)重 ω按照式(9)進(jìn)行計(jì)算.每個函數(shù)運(yùn)行50次,以平均值作為優(yōu)化結(jié)果.通過表2的數(shù)據(jù)可以看出,本文提出的TS-IPSO算法的尋優(yōu)結(jié)果,無論是50次優(yōu)化運(yùn)行得到的函數(shù)最優(yōu)解或是平均最優(yōu)解,都明顯優(yōu)于標(biāo)準(zhǔn)PSO算法的優(yōu)化結(jié)果.

表2 實(shí)驗(yàn)結(jié)果Tab.2 Experiment results

為了更直觀地體現(xiàn)TS-IPSO算法的性能,分別將4個測試函數(shù)迭代的收斂曲線與標(biāo)準(zhǔn)PSO算法的尋優(yōu)曲線進(jìn)行對比,如圖1～圖4所示.

圖1 Sphere函數(shù)尋優(yōu)曲線Fig.1 Comparison of optim izing process on Sphere function

圖2 G riewank函數(shù)尋優(yōu)曲線Fig.2 Comparison of optim izing process on Griewank function

圖3 Rastrigin函數(shù)尋優(yōu)曲線Fig.3 Com parison of op tim izing process on Rastrigin function

圖4 Rosenbrock函數(shù)尋優(yōu)曲線Fig.4 Comparison of optim izing process on Rosenbrock function

由圖1～圖4可知,本文提出的TS-IPSO算法的優(yōu)化效果和優(yōu)化過程明顯好于標(biāo)準(zhǔn)PSO算法.對于函數(shù) f1(x),f2(x)和 f3(x),本文算法都取得了理論最優(yōu)值,都能經(jīng)過較少的迭代次數(shù)而獲得最優(yōu)解;對于 f4(x),改進(jìn)算法也取得了較標(biāo)準(zhǔn)PSO算法更好的結(jié)果.同時對于搜索目標(biāo)函數(shù)全局最優(yōu)值,標(biāo)準(zhǔn)PSO算法不是陷入局部極值,就是計(jì)算逐步趨于停頓,而基于雙子群的TS-IPSO算法則表現(xiàn)出更為強(qiáng)大的搜索能力和更快的收斂速度.

4 結(jié) 語

基于雙子群的改進(jìn)粒子群算法TS-IPSO以搜索方向相反的主、輔2組子群協(xié)同搜索,擴(kuò)展了搜索范圍,結(jié)合遺傳算法的雜交機(jī)制并采用慣性因子非線性遞減策略,具有良好的優(yōu)化效果和探索性能,從而降低了優(yōu)化算法陷入局部最優(yōu)點(diǎn)的風(fēng)險,同時加快了收斂速度.實(shí)驗(yàn)表明該算法不僅具有較強(qiáng)的全局搜索能力,而且能有效避免常規(guī)算法的早熟收斂問題,顯著提高了優(yōu)化性能.

[1] KENNEDY J,EBERH ART R C.Particle sw arm algorithm [C]//Proceedingsof the 1995 IEEE In ternational Conference on Neu ral Netw orks.New York:IEEE Press,1995,4:1942-1948.

[2] ANGELINE P J.Evolutionary optim ization versus particle swarm optim ization:philosophy and performance differences [C]//Proceedings of the 7th Annual Conference on Evolutionary Programm ing.Berlin:Springer,1998:601-610.

[3] KENNEDY J,EBERHART R C.A discrete binary version of the particle swarm algorithm[C]//Proceedingsof IEEE Conference on Systems,M an and Cybernetics.Orlando:IEEE, 1997:4104-4109.

[4] X IE X F,ZHANG W J,YANG Z L.A dissipative particle swarm optim ization[C]//Proc of the IEEE IntConf on Evolutionary Com putation.H onolulu:IEEE,2002:1456-1461.

[5] LEANDRO DOS SANTOS COELHO.A quan tum particle sw arm op tim izer with chaotic mu tation operator[J].Chaos, Solitons and F ractals,2008,37(5):1409-1418.

[6] 焦巍,劉光斌.動態(tài)環(huán)境下的雙子群PSO算法[J].控制與決策,2009,24(7):1083-1091.

JIAOW ei,LIU Guang-bin.Tw o subpopu lation sw arm PSO algorithm in dynamic environment[J].Control and Decision, 2009,24(7):1083-1091.(In Chinese)

[7] 曹春紅,張永堅(jiān),李文輝.雜交粒子群算法在工程幾何約束求解中的應(yīng)用[J].儀器儀表學(xué)報,2004,25(增刊4):397-400.

CAO Chun-hong,ZHANG Yong-jian,LIWen-hui.The application of crossb reeding particle sw arm optim izer in the engineering geometric constraint solving[J].Chinese Journal of Scientific Instrument,2004,25(Sup4):397-400.(In Chinese)

[8] 陳貴敏,賈建援,韓琪.粒子群優(yōu)化算法的慣性權(quán)值遞減策略研究[J].西安交通大學(xué)學(xué)報,2006,40(1):53-56.

CHEN Gui-m in,JIA Jian-yuan,H AN Qi.Study on the strategy of decreasing inertiaweigh t in particle swarm op timization algorithm[J].Journal of Xi'an Jiaotong University,2006,40 (1):53-56.(In Chinese)

[9] 王俊偉,汪定偉.一種帶有梯度加速的粒子群算法[J].控制與決策,2004,19(11):1298-1230.

WANG Jun-wei,W ANG Ding-wei.Partic le sw arm optim ization algorithm w ith g radient acceleration[J].Controland Decision, 2004,19(11):1298-1230.(In Chinese)

[10]曾建潮,介蜻,崔志華.微粒群算法[M].北京:科學(xué)出版社, 2004:11-51.

ZENG Jian-chao,JIE Qing,CUI Zhi-hua.Partic le sw arm optim ization[M].Beijing:Science Press,2004:11-51.(In Chinese)

An Im proved Particle Swarm Op timization A lgorithm Based on Two-subpopulation

ZHANG Ying-jie1?,LI Liang1,ZHANG Ying-hao2,LUO Chun-song1
(1.Co llege of Computer and Communication,H unan Univ,Changsha,H unan 410082,China; 2.H unan Mechanical and Electrical Polytechnic,Changsha,H unan 410151,China)

Particle Sw arm Optimization algorithm easily gets stuck at localoptimal solution and shows premature convergence.An imp roved Particle Swarm Optimization algorithm based on tw o-subpopu lation(TS-IPSO)was proposed.Thesearch range of the algorithm w asextended through main subpopulation particle swarm and assistant subpopulation particle swarm,w hose search direction was inversed comp letely.It also adopts the crossbreeding mechanism in genetic algorithm,and uses non-linear inertia weight reduction strategy to accelerate the op timization convergence and improve the search capabilitiesof particles,then effectively decrease the risk of trapping into localoptima. Experiment resultshave shown that the TS-IPSO can greatly improve the global convergence ability and enhance the rate of convergence,compared with SPSO.

convergence;Particle Swarm Optimization(PSO)algorithm;subpopulation;crossbreeding;genetic arithmetic

TP18

A

1674-2974(2011)01-0084-05 *

2010-05-30

國家自然科學(xué)基金資助項(xiàng)目(60634020);湖南省科技計(jì)劃重點(diǎn)資助項(xiàng)目(2010GK 2022)

張英杰(1970-),男,湖南邵陽人,湖南大學(xué)副教授,博士

?通訊聯(lián)系人,E-mail:zy j18502@hnu.cn