李國曉,韋世丹

(廣東水利電力職業(yè)技術學院,廣東 廣州 510635)

基于改進Tent映射的自適應變尺度混沌粒子群算法

李國曉,韋世丹

(廣東水利電力職業(yè)技術學院,廣東 廣州 510635)

為改善標準粒子群優(yōu)化算法本身存在的缺陷,引入種群混沌初始化方法、參數(shù)自適應調(diào)整策略、早熟判斷機制以及基于改進Tent 映射的變尺度混沌局部搜索方法對原有算法進行改進,提出一種基于改進Tent映射的自適應變尺度混沌粒子群算法(Improved Adaptive Chaos PSO,IACPSO)。多種高維Benchmark函數(shù)的計算結果表明,IACPSO算法在計算精度、優(yōu)化穩(wěn)定性及收斂速度方面均明顯優(yōu)于其他改進粒子群優(yōu)化算法。

粒子群優(yōu)化算法；Tent映射；變尺度；混沌；自適應

0 引 言

粒子群優(yōu)化算法(Particle Swarm Optimization,PSO)是一類基于群智能的演化計算方法。該算法在低維空間的函數(shù)優(yōu)化問題上具有求解速度快、質(zhì)量高等優(yōu)點,但若問題解的維數(shù)增加,其優(yōu)化性能便急劇下降,易陷入局部最優(yōu)解。針對PSO算法本身存在的缺陷,國內(nèi)外學者已提出諸多改進方案,這些方案大致可以分為3類：第1類是對PSO參數(shù)(慣性權重w、學習因子c1與c2)進行調(diào)整與改進,如線性遞減權重法[1]、壓縮因子法[2]、動態(tài)慣性權重法[3]等,這些方法在某種程度上較好地解決了PSO算法早熟收斂問題,但參數(shù)的選擇具有隨機性,需要進行大量的數(shù)據(jù)試驗,并且與具體應用存在較大聯(lián)系；第2類是在PSO算法中引入各種變異機制以保持粒子尋優(yōu)的多樣性,這類方法主要為防止粒子在求解空間內(nèi)過早陷入局部最優(yōu)解,但是粒子多樣性的提高會影響到PSO算法的收斂速度[4]；第3類是在PSO算法中融入其他智能算法以增強粒子的局部開發(fā)能力,如與遺傳、差分進化等算法的結合[5-6]。

針對標準PSO算法易陷入局部最優(yōu)、迭代后期收斂較慢等問題,本文提出了一種基于改進Tent映射的自適應變尺度混沌粒子群算法(Improved Adaptive Chaos PSO,IACPSO)。首先,該算法將改進Tent映射產(chǎn)生的混沌序列對種群位置與速度進行賦值,以提高初始種群個體質(zhì)量及粒子分布的多樣性；其次,對慣性權重及學習因子采用自適應調(diào)整策略,以均衡算法在求解空間內(nèi)的全局與局部搜索能力；最后,配合早熟判斷機制及基于改進Tent映射的變尺度混沌局部搜索策略,以進一步提高算法求解精度及收斂速度。

1 IACPSO算法的主要思想

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

標準粒子群優(yōu)化算法(SPSO)算法可描述為：在D維求解空間,第i個粒子根據(jù)個體極值Pi=(pi,1,pi,2,…,pi,D)與全局極值Pg=(pg,1,pg,2,…,pg,D)動態(tài)調(diào)整自身的位置Xi=(xi,1,xi,2,…,xi,D)與速度Vi=(vi,1,vi,2,…,vi,D)。求解前需對各粒子的位置和速度進行初始化,在第t次迭代時,粒子按下式更新下代的速度和位置[7]

vi,d(t+1)=wvi,d(t)+c1r1[pi,d(t)-xi,d(t)]+c2r2[pg,d(t)-xi,d(t)]

(1)

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

(2)

式中,i=1,2,…,M；d=1,2,…,D；vi,d∈[-vdmax,vdmax]；xi,d∈[xmin,d,xmax,d]；M為粒子個數(shù)；D為求解空間的維數(shù)；w為慣性權重；c1和c2為學習因子；r1和r2為均勻分布在[0,1]的隨機數(shù)。

1.2 基于改進Tent映射的種群混沌初始化

種群的初始化對PSO算法的全局收斂速度及解的質(zhì)量產(chǎn)生重要影響。在沒有任何先驗信息可利用的情況下,種群的位置與速度一般采用隨機初始化的方法產(chǎn)生初始解。隨機初始化方法雖在一定程度上能保證初始種群分布均勻,但不能保證個別粒子質(zhì)量,部分群體可能遠離最優(yōu)解,故影響算法收斂速度。利用混沌序列對粒子位置與速度進行初始化,既能不影響PSO算法初始化時所擁有的隨機性本質(zhì),又能利用混沌序列特性提高種群的多樣性及粒子搜索的遍歷性[8]。與傳統(tǒng)混沌優(yōu)化算法常采用的Logistic映射相比,改進Tent映射具有更優(yōu)越的混沌特性,能更好地實現(xiàn)混沌尋優(yōu)[9]。本文采用改進Tent映射對種群位置與速度進行初始化,其表達式為

(3)

式中,k為混沌迭代次數(shù),k=0,1,…,Cmax；當xk=0、0.25、0.5、0.75或xk=xk-m,m={0,1,2,3,4}時,則根據(jù)式(3)重新賦值

(4)

1.3 參數(shù)自適應調(diào)整策略

慣性權重w是影響算法優(yōu)化性能的重要參數(shù),合理選擇w可使粒子具有均衡的全局與局部搜索能力。為此,本文采用一種根據(jù)粒子當前適應度自動調(diào)整w的方法,其表達式為

(5)

式中,wmax、wmin分別為w的最大值與最小值；fi為粒子當前適應度；favg與fmin分別為當前所有粒子的平均適應度和最小適應度。

學習因子c1和c2分別體現(xiàn)了個體粒子的自我探索與群體學習能力。在算法尋優(yōu)初期,粒子應具有較大的自我探索能力和較小的群體學習能力,以加強粒子的全局搜索能力；在尋優(yōu)后期,粒子應具有較小的自我探索能力與較大的群體學習能力,以保證粒子傾向于全局極值。為此,學習因子c1和c2可采用如下調(diào)整策略

(6)

式中,c1max、c2max分別為c1和c2的最大值；c1min、c2min分別為c1和c2的最小值；t為當前迭代次數(shù)；Tmax為最大迭代次數(shù)。

1.4 早熟判斷機制

隨著算法迭代次數(shù)的增加,個體之間的差異性將逐漸降低,而粒子位置的一致性則等價于各粒子具有相同的適應度值,故可根據(jù)種群中全體粒子適應度值的整體變化來判斷種群的收斂狀態(tài)。為此,本文采用群體適應度方差σ2作為早熟判斷機制,其反映的是粒子群中個體粒子的聚集程度,計算公式為[10]

(7)

式中,M為種群規(guī)模的大??；f為歸一化因子,其作用是限制σ2的大小,表達式為

(8)

1.5 基于改進Tent映射的變尺度混沌局部搜索

為提高算法求解精度及收斂速度,可將變尺度混沌優(yōu)化算法[11]與SPSO算法相結合,利用混沌運動所具有的隨機性、遍歷性等特點,在部分較優(yōu)粒子周圍執(zhí)行局部搜索,幫助這些粒子搜尋到更優(yōu)解。同時,搜索范圍將隨迭代次數(shù)的增加而逐漸縮小,以提高混沌變量的搜索效率。變尺度混沌局部搜索的主要步驟如下：

(9)

式中,m為已執(zhí)行局部搜索次數(shù)；pi,d′為第i個較優(yōu)粒子Pi′=(pi,1′,pi,2′,…,pi,D′)第d維分量；φ為收縮因子,其表達式為

(10)

(11)

(12)

式中,β為自適應調(diào)節(jié)系數(shù),其表達式為

β=1-((t-1)/t)η

(13)

式中,η為正整數(shù),可根據(jù)目標函數(shù)而定。

(3)將cxd′按下式轉化為新的決策變量xd′

(14)

(4)根據(jù)新解Xi′=(pi,1′,…,xi,d′,…,pi,D′)計算其適應度f(Xi′)。若f(Xi′)Cmax,則d=d+1并轉至(1)；當d>D，則停止混沌局部搜索。

表1 Benchmark函數(shù)

1.6 IACPSO算法的實現(xiàn)方法

結合基于改進Tent映射的種群混沌初始化方法、早熟判斷機制、參數(shù)自適應調(diào)整策略以及變尺度混沌局部搜索策略,構建出基于改進Tent映射的自適應變尺度混沌粒子群算法(IACPSO)。完整的IACPSO算法的實現(xiàn)方法可歸納為：

(1)設置算法參數(shù)。利用改進Tent映射混沌模型對各粒子的速度與位置進行初始化。

(2)初始參數(shù)下,計算各粒子個體適應度fi,確定并保存群體最優(yōu)位置Pg及個體最優(yōu)位置Pi。

(3)根據(jù)式(5)、(6)調(diào)整慣性權重與學習因子,按式(1)、(2)更新各粒子的速度和位置,重新計算各粒子個體適應度并更新Pg與Pi。

(4)根據(jù)式(7)計算群體的適應度方差σ2。若σ2低于閾值δ,則對個體適應度前20%的粒子執(zhí)行變尺度混沌局部搜索,搜索完成后轉至(3)；否則直接轉至(3)。

(5)若算法滿足終止條件(本文以最大迭代次數(shù)為限制條件),則尋優(yōu)結束,否則轉至(3)。

2 IACPSO算法優(yōu)化性能分析

2.1 試驗設置

為驗證本文提出的IACPSO算法的函數(shù)優(yōu)化性能,選取PSO算法常用的6個Benchmark函數(shù)進行優(yōu)化試驗。表1給出了各函數(shù)的名稱、表達式、最優(yōu)值及搜索范圍。其中,f1、f2與f3為單峰函數(shù)；f4、f5與f6為多峰函數(shù)。同時,將IACPSO算法與相同環(huán)境下的慣性權重線性遞減的PSO算法[12](LDWPSO)、基于Logistic映射的混沌PSO算法[13](CPSO)進行比較分析。計算平臺為Matlab R2009b,算法采用M語言編程實現(xiàn)。

各算法的運行參數(shù)設置如下：IACPSO算法中,wmax=0.9,wmin=0.4,c1max=c2max=2.5,c1min=c2min=0.5,閾值δ=10,適應度閾值fδ=0.1,η1=0.5,η2=10 000,混沌迭代次數(shù)Cmax=10；LDWPSO算法中,慣性權重w由0.9線性遞減至0.4,c1=c1=1.5；CPSO算法中,其慣性權重、混沌迭代次數(shù)與IACPSO一致。此外,各算法的種群規(guī)模N=30,最大迭代次數(shù)Tmax=2 000。各算法的終止條件為當前算法獲得的優(yōu)化值低于表1所對應函數(shù)的最優(yōu)值或者達到最大迭代次數(shù)。

2.2 算法優(yōu)化性能比較及分析

采用平均值(Mean)和標準差(Std)作為各個算法的性能測試與比較指標。其中,Mean用來衡量算法的求解精度；Std用來衡量算法的穩(wěn)定性與魯棒性。表2給出了LDWPSO、CPSO與IACPSO算法對Benchmark函數(shù)f1～f6分別在10、20與30維空間中獨立運行30次的優(yōu)化性能比較結果。其中,粗體字表示相同指標下比較結果的相對最優(yōu)值。

表2 LDWPSO、CPSO與IACPSO算法的優(yōu)化性能比較結果

由表2中的相同維數(shù)下Benchmark函數(shù)測試結果可知,相較于LDWPSO與CPSO算法,IACPSO算法對Benchmark函數(shù)f1～f6的求解質(zhì)量相對較高,尤其是對多峰函數(shù)f4與f5,其Mean與Std值均遠低于其他2種算法。由此可見,IACPSO算法具有更高的求解精度及更好的計算穩(wěn)定性。此外,隨著Benchmark函數(shù)維數(shù)的增加,其復雜性逐漸提高,此時LDWPSO與CPSO算法的Mean與Std值均有不同程度的上升,表明上述2種算法對Benchmark函數(shù)的求解精度及計算穩(wěn)定性逐漸變差,且給算法的收斂帶來較大困難；然而,與LDWPSO、CPSO算法不同的是,Benchmark函數(shù)維數(shù)變化對IACPSO算法的Mean與Std值影響較小,IACPSO算法始終保持較高的求解精度及計算穩(wěn)定性。

為更加直觀地反映出IACPSO算法的函數(shù)尋優(yōu)效果,圖1給出了LDWPSO、CPSO及IACPSO算法對30維Benchmark函數(shù)進行30次獨立試驗的平均適應度值收斂曲線。從圖1可知,IACPSO算法的初始平均適應度值略低于LDWPSO及CPSO算法,這是由于基于改進Tent映射的種群混沌初始化方法能有效提升IACPSO算法初始解的質(zhì)量,一定程度上提高了初始種群的多樣性及粒子搜索的遍歷性。此外,除函數(shù)f4之外,IACPSO算法無論處于迭代初期還是后期,其收斂速度均明顯快于LDWPSO與CPSO算法,且經(jīng)過一定迭代次數(shù)之后,LDWPSO與CPSO算法均過早地陷入早熟收斂狀態(tài),而此時IACPSO算法卻可以非常穩(wěn)健地向全局最優(yōu)解的方向繼續(xù)尋優(yōu)下去,最終IACPSO算法的求解精度遠高于LDWPSO與CPSO算法。究其原因,主要是由于IACPSO算法中采用了參數(shù)自適應調(diào)整策略及基于改進Tent映射的變尺度混沌局部搜索策略。上述2種策略的引入使IACPSO算法擁有更高的搜索效率及更快的收斂速度,在處理Benchmark函數(shù)時能很快跳出局部最優(yōu)解,極大增加了算法收斂到全局最優(yōu)解的可能性。

綜上可知,本文提出的IACPSO算法具有較為平衡的全局搜索及局部開發(fā)能力,在計算精度、優(yōu)化穩(wěn)定性及收斂速度方面均明顯優(yōu)于LDWPSO與CPSO算法。

3 結 語

為改善標準粒子群優(yōu)化算法求解復雜優(yōu)化問題時收斂速度慢及容易早熟收斂等缺陷,本文提出了一種融合有種群混沌初始化方法、早熟判斷機制、參數(shù)自適應調(diào)整策略及變尺度混沌局部搜索策略的自適應變尺度混沌粒子群優(yōu)化算法。對多種高維Benchmark 函數(shù)的計算結果表明,本文所提出的IACPSO算法在計算精度、優(yōu)化穩(wěn)定性及收斂速度方面均明顯優(yōu)于LDWPSO與CPSO算法。

圖1 30維Benchmark函數(shù)的平均適應度值收斂

[1]SHI Y, EBERHART R. A modified particle swarm optimizer[C]∥Proceedings of the 1998 Congress on Evolutionary Computation. Piscataway: IEEE Press, 1998: 69-73．

[2]CLERC M.The swarm and the queen: Towards a deter-ministic and adaptive particle swarm optimization[C]∥Proceedings of the 1999 Congress on Evolutionary Computation. Piscataway: IEEE Press, 1999: 1951-1957．

[3]EBERHART R, SHI Y. Particle swarm optimization: developments, applications and resources[C]∥Proceedings of the 2001 Congress on Evolutionary Computation. Piscataway: IEEE Press， 2001: 81-86．

[4]CHENG S, SHI Y H. Diversity control in particle swarm optimization[C]∥IEEE Symposium on Swarm Intelligence. Piscataway: IEEE Press, 2011: 1-9．

[5]XIN B, CHEN J, ZHANG J. Hybridizing differential evolution and particle swarm optimization to design powerful optimizers: A review and taxonomy[J]. IEEE Trans on Systems,Man and Cybernetics,Part C: Applications and Reviews, 2012, 42(5)： 744-767．

[6]BO Y. A hybrid evolutionary algorithm by combination of PSO and GA for unconstrained and constrained optimization roblems[C]∥IEEE Int Conf on Control and Automation. Piscataway: IEEE Press, 2007: 166-170．

[7]KENNEDY J, EBERHART R. Particle swarm optimization[C]∥Proceedings of the 1995 IEEE International Conference on Neural Networks, Piscataway: IEEE Press, 1995: 1942-1948．

[8]王維博, 馮全源. 基于分層多子群的混沌粒子群優(yōu)化算法[J]. 控制與決策, 2010, 25(11)： 1663-1668．

[9]王瑞琪, 張承慧, 李珂. 基于改進混沌優(yōu)化的多目標遺傳算法[J]. 控制與決策, 2011, 26(9)： 1391-1397．

[10]王小根, 龍海俠, 孫俊. 基于高斯擾動的量子粒子群優(yōu)化算法[J]. 計算機應用研究, 2010, 27(6)： 2093-2096．

[11]張彤, 王宏偉, 王子才. 變尺度混沌優(yōu)化算法及其應用[J]. 控制與決策, 1999, 14(3)： 285-288．

[12]SHI Y, EBERHART R C. Empirical study of particle swarm optimization[C]∥Proc of the 1999 Congress on Evolutionary Computation. Piscataway: IEEE Press, 1999: 1945-1950．

[13]LIU B, WANG L, JIN Y H, et al. Improved particle swarm optimization combined with chaos[J]. Chaos, Solitons and Fractals, 2005, 25(5)： 1261-1271．

(責任編輯 楊 健)

An Improved Adaptive Chaos Particle Swarm Optimization Algorithm Based on Improved Tent Map

LI Guoxiao, WEI Shidan

(Guangdong Polytechnic of Water Resources and Electric Engineering, Guangzhou 510635, Guangdong, China)

In order to improve the defect of basic Particle Swarm Optimization algorithm, an Improved Adaptive Chaos Particle Swarm Optimization (IACPSO) algorithm based on improved Tent map is proposed herein, which including population chaos initialization method, adaptive parameter adjusting strategy, precocious judgment mechanism and mutative scale chaos local search based on improved Tent map. The results of some high-dimensional Benchmark functions show that the IACPSO algorithm is better than other improved PSO on computation accuracy, optimization stability and convergence speed．

Particle Swarm Optimization algorithm; Tent map; mutative scale; chaos; adaptive

2016-06-28

李國曉(1977—),男,河南襄城人,講師,碩士,主要從事水電站動力設備教學與研究工作．

TP301.6

A

0559-9342(2017)02-0089-05