改進多種群差分進化算法的混沌系統參數估計

何廷年,李曉紅,蔣 蕓

(1.西北師范大學計算機科學與工程學院,蘭州730070;2.北京師范大學信息科學與技術學院,北京100875)

改進多種群差分進化算法的混沌系統參數估計

何廷年1,2,李曉紅1,蔣 蕓1

(1.西北師范大學計算機科學與工程學院,蘭州730070;2.北京師范大學信息科學與技術學院,北京100875)

針對混沌系統參數估計的多峰尋優問題,提出一種改進的多種群差分進化算法。改進差分進化算法的變異操作,使其前期更適合全局性搜索,利用α核心集對當前種群進行聚類,分別對聚類后的子群選用貪婪的差分變異算子完成深度搜索,比較所選取各子群的最優值,得到全局最優值作為是否結束搜索的判斷依據,并將其應用到混沌系統參數估計中。實驗結果表明,該算法對于多峰值、大空間的全局性參數估計在收斂速度、精度上優于混合量子進化算法、改進粒子群優化算法以及DE/best/2算法。

α核心集;差分進化;混沌系統;參數估計;多種群

1 概述

20世紀90年代提出了混沌系統控制的概念,經過20多年的發展,混沌系統控制和同步的理論方法得到了廣泛研究[1-3]。在傳統混沌系統控制和同步方法中,由于混沌系統的多峰值性,在對混沌系統參數進行識別時,需要事先給定混沌系統的參數取值范圍,這種對尋優參數進行限制的方法人為地降低了參數估計的難度,對于參數已知混沌系統的實驗室研究是可行的,但是在實際應用中,由于混沌系統非常復雜,參數的取值范圍根本無法確定,傳統的參數辨識方法無法解決。針對該問題,相關學者通過構造合適的目標函數,將混沌系統參數估計問題轉化為多維的系統參數優化問題,然后利用量子進化算法[4]、演化建模算法[5]、粒子群[6]、地理優化算法[7]等智能優化算法對參數進行尋優。為防止智能算法早熟收斂陷入局部極值,上述文獻各自提出了改進的算法。

群智能優化算法是一種全新的演化計算方法,與人工生命特別是進化策略有著密切關系。差分進化(Differential Evolution,DE)算法作為群智能優化算法的一種,其本質是一種具有保優思想的貪婪的實數編碼遺傳算法。同遺傳算法一樣其包含交叉和變異操作,但不同于遺傳算法的選擇操作,差分進化算法采用一對一的優勝劣汰機制來更新種群。目前,國內學者在差分進化算法應用方面做了諸多研究。例如文獻[8]應用到軋制負荷分配;文獻[9]應用到機床的多道車削操作中等。

DE算法貪婪的保優特點使其具有較好的優化性能,但是種群抵抗局部極值吸引的能力大為降低,可以說基本差分進化算法更加適合于在算法后期加速收斂。對于混沌系統參數估計這種本質是多峰參數尋優的問題,當尋優空間范圍過大時,差分進化算法的優化性能受其特點制約更易早熟收斂。

文獻[4]引入量子算法對差分進化算法進行改進,平衡了算法全局探索與局部開發的能力,取得了很好的參數估計效果,并從量子操作的角度對差分進化算法貪婪的變異選擇算子進行平衡。本文從解空間的區域劃分著手,利用α核心集對種群個體進行區域劃分,通過子類群體在子空間的深度搜索,避免全體種群粒子的相互干擾,使其更利于全局最優估計。

2 混沌系統參數估計

2.1 問題描述

對于如下n維混沌系統:

其中,向量θ0=(θ10,θ20,…,θd0)T為混沌系統參數的真實值;d為混沌系統參數個數;向量x0是混沌系統的初始值;向量x=(x1,x2,…,xn)T∈Rn是n維混沌系統的狀態。

在對混沌系統進行參數估計時,事先假定混沌系統的結構是已知的,針對這樣的系統的參數估計完全可以轉化為參數尋優問題,數學描述如下:

其中,向量θ=(θ1,θ2,…,θd)T為混沌系統的參數估計值;向量y=(y1,y2,…,yn)T∈Rn為混沌待估計系統的狀態。

混沌系統的參數估計問題可描述為,尋找最優的待估計參數,使得待估計系統的狀態變量值與原混沌系統的狀態變量值的誤差最小。其中,誤差目標函數可構造如下:

目標函數值越小說明待估計混沌系統與原混沌系統越接近,參數估計值越精確。

2.2 問題分析

Lorenz函數是典型的混沌系統,相關文獻多以該函數進行仿真實驗[4-7],為便于與相關學者研究成果進行對比,本文采用該混沌系統進行闡述。Lorenz數學描述如下:

圖1 目標誤差函數值隨θ1,θ2的變化

文獻[10]于1997年提出差分進化算法后,由于其在連續域優化問題上的性能優勢,隨后便引發了國內外相關學者的研究熱潮。對于差分進化算法應用于混沌系統參數估計的做法是可行的,但是因為差分進化算法可以看作是貪婪的實數編碼的遺傳算法,所以其在保持種群多樣性方面不占優勢,容易陷于局部峰值。特別是在混沌系統參數估計時,相關文獻一般的處理方式是對參數取值范圍進行合理限制,在保證真實參數在該區域的同時,盡量回避干擾性強的峰值,在一定程度上簡化了參數估計難度,對于參數范圍已知的混沌系統參數估計是可行的,但是當參數的取值范圍未知或者取值范圍較大時,簡單的差分進化算法或者通用的改進方式便不再適合。

通過分析圖1可知,在不同的解空間區域內都會分布很多的局部峰值,這些局部峰值又有局部最優峰值,這些局部最優峰值便是對全局最優峰值的最大干擾,特別是當局部極值和全局極值的數量級相差不大,但是在解空間的距離較大時,該局部最優峰值對于全局最優峰值的影響是相當大的。傳統的對于差分進化算法的改進方式多是平衡種群多樣性和加速收斂,也就是平衡算法的勘探和開發的角度對差分進化算法進行改進,這種方式是從盡量避免陷入局部極值的角度出發來進行算法改進。但是當種群個體一旦陷于距離較遠的局部最優峰值區域,傳統的改進方法很難跳出。因此,本文主要是借助混沌系統參數估計來討論針對此類多峰值問題的差分進化算法的改進方案。

3 基于α核心集的多種群差分進化算法

3.1 α核心集的有關定義

文獻[11]提出一種新穎的凝聚算法,該算法設計了多層次的α核心集提取過程,隨著細化過程的推進,算法的聚類中心不斷增加,有利于提高算法的聚類效果,并且無需事先指定聚類中心,對非凸數據具有很好的分類效果,可以簡化算法識別的難度,通過大量的仿真證明,該算法的聚類精度要好于傳統的一些單層聚類算法。基于以上優點本文采用該聚類算法進行子群的識別。算法相關定義如下:

定義1高斯相似性(表示數據xi與xj的相似性):

其中,σ=σ0d,d為數據集直徑。

定義2首要核心集:

其中,x?為任意數據集X的首要核心點。

定義3α核心集:

定義4凝聚矩陣pX～Xα:

其中,PX～Xα體現的是數據集合X與其核心集Xα的相關程度。

定義5核心集Xα數據間的相似性:

3.2 差分變異方式的改進

差分進化算法同遺傳算法類似,算法的主體結構主要包括變異操作、交叉操作和選擇操作。變異操作是產生新的基因的有效方式,好的變異方式可以防止進化陷于局部極值,有利于保持種群的多樣性和兼顧收斂速度。因此,眾多學者對差分進化算法的變異方式進行了研究,提出了多種變異方式,例如DE/rand/1式(11)和DE/best/2式(12):

不同于遺傳算法及粒子群算法等生物智能優化算法,上述算法在提出變異方式時基于的理論是生物群體模擬,這里差分進化算法可以應用向量的分析方法來解釋變異方式。例如式(11)變異方式中是作為向量運算的基向量,而則可以看作是擾動,這種方式變異后可以解釋為在基向量附近進行擾動變異尋找比更優的個體。這種方式對于每個種群個體都是在其周圍進行擾動變異,有利于保持種群多樣性,但是相應的問題是如果當前種群個體沒有極點附近的個體則該變異方式收斂速度將過于緩慢,對種群初始值的要求比較高。式(12)變異方式是將當前種群中適應度最好的個體作為基向量進行向量運算,這種變異方式有利于加速收斂,但是如果不是全局最優峰值而是局部最優峰值,那么這種變異方式將會加速種群個體向該局部最優進化,而無法跳出。通過分析上述2種變異方式并結合向量分析的思想,對變異方式改進如下:

全局搜索變異方式:

局部深度開發變異方式:

2種變異方式形式比較類似,主要思想是以當前種群個體i作為自身變異的基向量,這樣就保證了個體i變異后的新個體位于自身附近區域,相對于式(11)、式(12)的變異方式,這種變異方式能夠相對的保證新個體進化的獨立性,有利于保持種群的多樣性,對于防止算法早熟非常有必要。2種變異方式的不同之處是在變異擾動項中,全局搜索變異方式采用的是2個隨機粒子個體,而局部深度開發變異方式采用的是當前個體i所在子群的歷史最優位置和一個隨機個體,這樣的變化使得深度開發變異方式能夠引導當前種群的個體向子群的最優個體附近進化,有助于加速收斂。

3.3 多種群差分進化算法

針對這種多峰值取值范圍不確定的參數尋優問題,首先應該明確的是對于大空間進行細分采用多群體進化的方式在理論上是可行的。以前有關文獻在對差分進化算法進行性能改進是多是從優化算法關鍵參數選取[12]、與其他優化算法混合互補[13]、優化變異方式[14]、搜索空間自適應[8]等角度進行改進,這些改進方式能夠提高算法的性能,但是都不是專門針對大空間搜索的。本文在討論混沌參數尋優時主要考慮要解決的問題有2個: (1)解決多峰值搜索問題;(2)解決參數不確定的大空間問題。文獻[15]采用網格化方法是對搜索空間進行劃分用來解決公交運行計劃編制問題,雖然這種改進方式主要不是針對大空間搜索問題,僅僅是為了提高算法躲避不良峰值的性能,但是實際上這種改進方式對于大空間搜索問題有一定的啟示作用。因此,提出一種大空間多種群智能搜索(LargeSpaceMulti-swarmIntelligenceSearch, LSMS)架構,如圖2所示。圖2中直觀地反映出該搜索框架的關鍵步驟,即種群的初始化階段、隨機全局勘探階段、子群識別階段、多種群的深度開發階段。這些關鍵步驟需要注意:(1)需要種群盡量遍布搜索空間,目前方法比較多,比如隨機初始化、基于混沌映射的隨機遍歷等;(2)需要算法的變異方式具有足夠的保持種群多樣性的能力,這里需要對傳統的變異方式進行改進,使其更加適合隨機搜索;(3)子群識別階段需要識別算法具有足夠的精確性,并且計算復雜性越低越好;(4)深度開發階段,這個階段需要算法變異方式具備較強的保持種群多樣性和收斂速度。

圖2 大空間多種群智能搜索架構

本文對上述4個關鍵步驟的改進策略是:步驟(1)采用最簡單的隨機初始化;步驟(2)、步驟(4)根據算法需要對原有差分進化算法的變異方式進行改進(參照3.2節內容);步驟(3)采用文獻[11]提出的基于α核心集的凝聚算法進行聚類識別(相關定義參照3.1節),這種聚類識別算法識別精度高,無需指定聚類中心,可以簡化聚類識別難度。子群識別算法步驟為:

Step 1輸入待分類的種群數據集X及所需要的子群識別個數K。

Step 3利用式(5)來計算最底層核心集的相似性矩陣,并利用式(11)計算最底層核心集的下一層核心集。

Step 4利用式(7)～式(9)計算可得:

Step 5輸出各層核心集及相似性矩陣:

Step 7對于t=1:n依次計算:

4 仿真實驗與分析

4.1 Lorenz函數參數估計

本文以Lorenz函數為例對混沌參數估計問題進行闡述,首先選用Lorenz函數進行仿真,具體形式如式(4)所示。混沌參數的真實值為:θ1=10,θ2=28,。為顯示大空間多種群智能搜索算法在大空間上尋優性能的優勢,這里分別選取參數θ1、θ2和θ3的搜索空間{[9,11],[20,30],[2,3]},[-2 000, 2 000]以及[-2 000,2 000],對比算法采用文獻[4]的混合量子進化算法(Hybrid Quantum Evolutionary Algorithm,HQEA),文獻[6]的改進粒子群優化(Improved Particle Swarm Optimization,IPSO)算法以及未改進的DE/best/2算法。

算法參數設置:混沌系統采用四階Runge-Kutta法進行常微分迭代,迭代步長設為h=0.01,種群大小n=60,維數D=3,縮放因子F=0.75,交叉概率因子CR=0.9,設置LSMS算法子群識別代數N= 45,進化代數T=500,α核心集規模控制參數m= 0.5,子群數量分別設置為:

4種算法的收斂曲線如圖3所示。由圖3可以看出,隨著搜索空間的不斷增大,尋優難度逐漸增加。IPSO算法、DE/best/2算法在3種搜索空間上參數估計效果相對較差,都有早熟收斂的傾向,無法搜索到全局最優值,特別是隨著搜索空間的增大,早熟現象越發明顯。而HQEA算法在搜索空間{[9, 11],[20,30],[2,3]}及[-2 000,2 000]上的搜索結果尚可,但是當搜索空間擴大到[-2 000,2 000]時,HQEA算法也出現早熟收斂現象。LSMS算法在4種算法中的性能最好。

圖3 目標函數收斂曲線

圖4為LSMS算法參數的估計曲線(c3=6,R∈[-2 000,2 000]),可以看出,在子群識別代數t=45之后,算法能夠及時跳出局部干擾峰值,快速收斂到全局最優峰值,搜索空間的擴展對于該算法的全局參數估計效果影響不大。

圖4 LSMS算法的參數估計曲線

從前述分析可知,聚類識別中心數量的設置對于算法搜索性能的影響很大,子群過少影響算法的分類識別精度過低,相當于子群搜索的空間過大,對于提高全局算法收斂精度不利,子群數量過多則導致子群內的個體數量過少,影響子群內部的收斂效果,導致算法收斂速度過慢。這里以搜索空間R∈[-2 000,2 000],種群規模n=60為例進行仿真,由于子群搜索變異方式至少需要2個隨機個體,因此子群的個體數量至少為3個。對c=3～10進行仿真,各運行20次求取成功率和迭代次數的平均值,為防止算法早熟無法尋找到全局最優值影響實驗結果,設置最大迭代次數tmax=1000,目標函數值vtr= lg(f)=1×e-10,子群識別代數N=45。

表1數據顯示出子群數量與算法性能的提高之間存在一個拋物線的關系,并非子群數量越多越好,要根據實際情況和尋優過程遇到的問題進行調整。

表1 子群數量不同時本文算法各運行20次的平均結果

4.2 Rossler函數拓展實驗

前文以Lorenz函數為例闡述,4.1節以該混沌系統為例進行仿真驗證,實驗結果對算法的通用性說服力不強,對此,本節以Rossler函數為例進行仿真實驗驗證算法在混沌系統參數估計上的普適性。Rossler函數方程為:

該系統的混沌參數實際值為δ=0.2,γ=0.2,b=5.7。由4.1節仿真結果可知HQEA算法[4]的性能要優于IPSO算法以及未改進的DE/best/2算法。為了簡化仿真步驟,本節對比算法只采用HQEA算法。相關算法參數設置同4.1節。各算法獨立運行20次,以算法尋找到的最優、最差和平均參數估計值為評價指標。由于在搜索空間過大時HQEA算法也出現早熟收斂,為對比2種算法在合適區間的算法性能,使兩者具有可比性,選取參數δ,γ和b的初始搜索空間為[-20,20],參數估計結果如表2所示。

表2 Rossler系統參數估計結果對比

表2給出的是LSMS算法和HQEA算法在Rossler系統參數估計結果,20次獨立運算中,LSMS算法的最好尋優結果是找到混沌系統的參數真實值,而HQEA算法則只是找到混沌參數真實值附近的一組參數值便早熟收斂。LSMS算法最差尋優結果是找到參數真實值附近的一組參數值,而HQEA算法則完全偏離真實值,尋優效果很差,目標收斂值更為直接的說明了算法尋優效果。仿真結果顯示LSMS算法同樣適用于Rossler系統的參數估計,具有一定的普適性。

5 結束語

本文對混沌系統參數估計進行研究,針對參數初始搜索空間存在耦合的大空間參數估計問題,依托差分進化算法,設計一種適用于大空間多峰函數優化的LSMS算法。通過前期的隨機搜索,種群個體逐步聚集到局部最優峰值附近,通過子群識別算法,將差分進化算法種群分為多個子群,子群獨立進化,避免了局部最優峰值對算法收斂的干擾,從而在一定程度上起到防止早熟收斂的效果,適合對混沌系統參數的大空間全局搜索。對子群數量影響算法性能進行了實驗分析,結果驗證了其有效性。今后將進一步研究如何降低該算法的計算復雜度。

[1] Edward O,Grebogi C,James A Y.Controlling Chaos[J]. Physical Review Letters,1990,64(11):1196-1199.

[2] Zhao Lu,Shieh L S,Chen Guanrong.On Robust Control of Uncertain Chaotic Systems:A Sliding-mode Synthesis via ChaoticOptimization[J].Chaos,Solitons& Fractals,2003,18(4):819-827.

[3] Elabbasy E M,Agiza H N,El-dessoky M M.Global Syn-chronization Criterion and Adaptive Synchronization for New Chaotic System[J].Chaos,Solitons&Fractals, 2005,23(4):1299-1309.

[4] 張大斌,楊添柔,溫 梅.基于差分進化的魚群算法及其函數優化應用[J].計算機工程,2013,39(5):18-22.

[5] 王 柳,何文平,萬仕全,等.混沌系統中參數估計的演化建模方法[J].物理學報,2014,63(1).

[6] 高 飛,童恒慶.基于改進粒子群優化算法的混沌系統參數估計方法[J].物理學報,2006,55(2):577-582.

[7] 林 劍,許 力.基于混合生物地理優化的混沌系統參數估計[J].物理學報,2013,62(3).

[8] 姚 峰,楊衛東,張 明,等.改進自適應變空間差分進化算法[J].控制理論與應用,2010,27(1):32-35.

[9] Ali R.Hybrid Taguchi-differential Evolution Algorithm for Optimization of Multi-pass Turning Operations[J]. Applied Soft Computing,2013,13(3):1433-1439.

[10] Rainer S,KennethP.DifferentialEvolution——A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces[J].Journal of Global Optimization,1997,11(4):341-359.

[11] 馬儒寧,王秀麗,丁軍娣.多層核心集凝聚算法[J].軟件學報,2013,24(3):490-505.

[12] Elsayed S M,Sarke R A,Essam D L.An Improved SelfadaptiveDifferentialEvolutionAlgorithmfor Optimization Problems[J].IEEETransactionson Industrial Informatics,2013,9(1):89-99.

[13] Brest J.Differential Evolution and Differential Antstigmergy on Dynamic Optimization Problems[J]. International Journal of Systems Science,2013,44(4): 663-679.

[14] Gong Wenyin,Cai Zhihua.Differential Evolution With Ranking-based Mutation Operators[J].IEEE Transactions on Cybernetics,2013,43(6):2066-2081.

[15] 聶宗瑤,李 穗,陳呂強.基于協同差分進化的多出救點應急物資調度[J].計算機工程與應用,2013, 49(3):247-250.

編輯 劉 冰

Chaotic System Parameter Estimation of Improved Multi-swarm Differential Evolution Algorithm

HE Tingnian1,2,LI Xiaohong1,JIANG Yun1
(1.College of Computer Science and Engineering,Northwest Normal University,Lanzhou 730070,China;
2.School of Information Science and Technology,Beijing Normal University,Beijing100875,China)

In order to solve the multimodal optimization problem in chaotic systems parameter estimation,an improved multi-swarm Differential Evolution(DE)algorithm is proposed.The mutation operator of DE algorithm is improved, which is more suitable for the global search.By usingαcore set clustering the current swarm,the depth search with greed DE operator is completed on clustered swarms respectively.By comparing the optimal values of selected swarms,the global optimal value is obtained as the judgment of whether to end the search,and is applied to the parameter estimation of chaotic systems.Experimental results show that the proposed algorithm is better than the Hybrid Quantum Evolutionary Algorithm(HQEA),Improved Particle Swarm Optimization(IPSO)and original DE/best/2 algorithm in convergence rate and accuracy for multi peak,large space of global parameter estimation.

αcore set;Differential Evolution(DE);chaotic system;parameter estimation;multi-swarm

何廷年,李曉紅,蔣 蕓.改進多種群差分進化算法的混沌系統參數估計[J].計算機工程,2015, 41(2):178-183,188.

英文引用格式:He Tingnian,Li Xiaohong,Jiang Yun.Chaotic System Parameter Estimation of Improved Multi-swarm Differential Evolution Algorithm[J].Computer Engineering,2015,41(2):178-183,188.

1000-3428(2015)02-0178-06

:A

:TP18

10.3969/j.issn.1000-3428.2015.02.034

國家自然科學基金資助項目(61163036)。

何廷年(1979-),男,講師、博士研究生,主研方向:人工智能,計算機視覺;李曉紅,講師、碩士;蔣 蕓,教授、博士。

2014-06-20

:2014-07-28E-mail:hetingnian1979@163.com