一種基于雙子群的改進粒子群優化算法*

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

(1.湖南大學計算機與通信學院,湖南長沙 410082;2.湖南機電職業技術學院,湖南長沙 410151)

一種基于雙子群的改進粒子群優化算法*

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

(1.湖南大學計算機與通信學院,湖南長沙 410082;2.湖南機電職業技術學院,湖南長沙 410151)

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

收斂性;粒子群優化算法;子群;雜交機制;遺傳算法

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

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

1 標準粒子群優化算法

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

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

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

式中:ωstart為始權值;ωend為終權值 ,并建議 ωstart和ωend分別取0.9和0.4;Iter max和Iter分別為最大迭代次數和當前迭代次數.

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

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

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

該子群稱為輔子群.在每次迭代結束時,比較2個子群個體最優位置所對應的適應值大小,適應值較差的個體最優粒子被更優者替代.這樣通過主、輔2個子群相互補充、協同進化,在不增加粒子規模的情況下,充分擴展搜索范圍,挖掘搜索域內的有用信息,降低PSO算法陷入局部最優點的風險.

2.2 雜交機制

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

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

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

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

2.3 慣性因子選擇策略

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

根據文獻[8]選擇一種自適應的非線性慣性權值遞減函數,具體表達式為:

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

2.4 TS-IPSO的算法步驟

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

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

2)將隨機初始化的粒子群等分為2組子群.計算每個粒子的適應值,設置Pi為初始群體的當前位置,Pg為最優粒子位置.

3)判斷算法收斂準則是否滿足,如果滿足執行8),否則轉向4).

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

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

6)根據適應度值計算每個個體的選擇概率,通常按線性排名計算.

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

8)檢查是否滿足PSO算法終止條件,若否,轉向4),繼續;若是,則求出最優解.

3 TS-IPSO算法仿真

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

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

表1 4個基準測試函數的參數設置Tab.1 Parameter settings of four benchmark functions

在TS-IPSO算法中,學習因子 C1,C2均取1.496 2,rand1,rand2為在區間[0,1]內均勻分布的隨機數,慣性權重 ω按照式(9)進行計算.每個函數運行50次,以平均值作為優化結果.通過表2的數據可以看出,本文提出的TS-IPSO算法的尋優結果,無論是50次優化運行得到的函數最優解或是平均最優解,都明顯優于標準PSO算法的優化結果.

表2 實驗結果Tab.2 Experiment results

為了更直觀地體現TS-IPSO算法的性能,分別將4個測試函數迭代的收斂曲線與標準PSO算法的尋優曲線進行對比,如圖1～圖4所示.

圖1 Sphere函數尋優曲線Fig.1 Comparison of optim izing process on Sphere function

圖2 G riewank函數尋優曲線Fig.2 Comparison of optim izing process on Griewank function

圖3 Rastrigin函數尋優曲線Fig.3 Com parison of op tim izing process on Rastrigin function

圖4 Rosenbrock函數尋優曲線Fig.4 Comparison of optim izing process on Rosenbrock function

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

4 結 語

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

[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] 焦巍,劉光斌.動態環境下的雙子群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] 曹春紅,張永堅,李文輝.雜交粒子群算法在工程幾何約束求解中的應用[J].儀器儀表學報,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] 陳貴敏,賈建援,韓琪.粒子群優化算法的慣性權值遞減策略研究[J].西安交通大學學報,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].北京:科學出版社, 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

國家自然科學基金資助項目(60634020);湖南省科技計劃重點資助項目(2010GK 2022)

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

?通訊聯系人,E-mail:zy j18502@hnu.cn