利用Lyapunov 函數確定粒子群算法參數選擇*

朱辰晨 賈群

(淮南師范學院機械與電氣工程學院,安徽淮南 232038)

0 序言

粒子群是一種基于空間多維搜索的隨機智能算法,它是由Kennedy和Eberhart在1995年提出,其算法模型相對簡單易于實現。粒子群在尋優過程中既能夠體現出群體的智能,又依賴于種群的每一個成員即粒子之間的協同合作尋測全局最優點。但PSO基本模型本身還有許多不足之處,比如算法易早熟、易陷入局部最優等。為了解決基本PSO算法存在缺陷及提高算法本身的適用性,很多文獻提出采用其他智能算法,如小波、神經網絡、混沌、遺傳、量子、聚類分析、模糊理論等進行一定的改善。但究其PSO算法模型本身而言,任何改進最終都會體現在算法參數的選擇上。1998年Shi和Eberhart引入慣性權重系數w并驗證了w選取不同范圍對標準PSO算法性能的影響;2000年Eberhart和Shi又在PSO迭代方程中引入壓縮因子對粒子的速度和位置進行約束,從而進一步提高了算法的性能[1-4]。

本文更側重參數之間的關系,在分析PSO基本算法的基礎上,運用控制理論中關于穩定性分析的李雅普諾夫函數從粒子運動穩定性角度對PSO算法進行分析,得到參數之間的約束關系,以此作為確定PSO算法參數選擇的基本依據,并通過相關的典型函數進行測試,充分證明了選擇合適的參數約束關系對于提高PSO的穩定性收斂性具有非常重要的意義。

1 李雅普諾夫穩定性分析

1.1 PSO穩定性分析及相關定理分析

P SO算法本身是一種非常有效的群智算法,粒子在特定空間搜索過程中粒子通過不斷調整自身最優位置和速度,同時兼顧全局最優位置變化,逐步地積聚于全局最優點,到達可行搜索域中的最優位置。粒子的運動具有逐漸趨向收斂、趨向穩定的特點。這一過程完全可以用Lyapunov原理來分析,許多文獻都有較多的討論,同時也有較深入的應用。根據Lyapunov原理對標準粒子群算法進行穩定性分析,在此基礎上提出粒子群參數選擇范圍的基本依據。

根據以上分析,利用以下定義和定理[5]:

控制系統在平衡狀態附近為漸近穩定,則Ω必須是正定的。判定Ω為正定的矩陣可以依據Sylvester準則,即判定矩陣正定的充要條件是該矩陣的各順序主子式均G為正值。根據上述條件分析必須保證為正定,進一步可以確保Ω是正定的[5]。

1.2 計算分析和PSO算法參數確定

式(3)的第一項為粒子先前的速度,聯系粒子當前的狀態,是粒子慣性的表現,起到了平衡全局和局部搜索的能力;第二項反映了粒子對“自身經驗”的認識,即粒子自身記憶對搜索的影響,這一項使粒子具有全局搜索能力,避免陷入局部最小;第三項反映了整個種群的“社會經驗”,綜合考慮了歷次迭代過程中整個種群所獲得的“經驗”,表示粒子間的信息共享與相互合作,有利于粒子全局搜索能力的提升[2-4]。

引入和選取中間狀態變量φ(t) ,并根據系統的空間狀態方程求解,選擇狀態變量得到以下關系:

可以確定ξ的取值范圍是:ξ∈(ω+ 1,2ω+2)

圖1是結合上面的推導分析所得到的ξ和ω取值關系圖。紅色和黃色區域是Frans van den Bergh通過代數推導方法所得到的PSO算法的收斂區域,黑色區域為算法的不收斂區域,粒子在此區域飛行過程中完全發散。紅色的區域為本文通過Lyapunov Function進行穩定性分析所確定的ξ和ω的取值范圍,這一范圍能夠保證粒子在空間搜索過程中達到穩定收斂的效果。

圖1 ξ和ω取值關系圖Fig.1 ξ and ω value relationship diagram

2 PSO算法的改進和仿真分析

2.1 PSO算法的改進

基于以上分析對標準PSO算法可以進行參數約束的算法改進(簡稱Constraint PSO),其中

保證參數落在紅色區域中,使粒子飛行速度和位置在每一次迭代過程中有一定的變化,這將有利于算法克服局部最優的缺陷。進而對于整個系統而言,既能兼顧PSO算法的隨機性,同時又能夠在一定程度上保證粒子在空間運動中的穩定性進一步保證了算法的收斂性。

2.2 函數測試及仿真

仿真條件:這里選取24個粒子,空間維數設定為3維,采用多峰函數進行測試分析。

f是Rastrigrin函數,該函數是個多峰值的函數,約有10n個局部極小點,而且此函數是一種典型的非線性多模態函數,峰形呈現高低起伏的形態,具有不定跳躍性的特點,所以不易查找到全局最優值。

圖2中可以看到多峰函數f是具有多峰特征,由于在搜索域中存在較多的峰值,相對于單峰函數,PSO在搜尋全局最優點的時候更容易陷入局部最優。圖3是標準PSO和constraint PSO的粒子絕對位置的對數值變化過程,可以看到Constraint PSO收斂性在多峰且復雜情況下能夠具有較好的收斂性。圖5表明Constraint PSO的粒子在空間迭代過程中聚集程度較好,而圖4距離中心處有較多的散點。通過兩個圖的對比分析,說明基于Lyapunov函數的PSO算法的粒子在空間尋優過程中能夠有效地聚集在收斂點處且收斂性較好。

圖2 f 函數空間效果圖Fig.2 f function space effect diagram

圖3 粒子絕對位置的對數值變化過程Fig.3 The logarithmic change process of the absolute position of the particle

圖4 標準PSO 粒子聚集程度Fig.4 Standard PSO particle aggregation degree

圖5 Constraint PSO 粒子空間聚集程度Fig.5 Constraint PSO particle spatial aggregation degree

3 結論

通過以上分析,可以清楚地發現依據Lyapunov函數所確定的PSO參數關系即ω+1＜ξ＜2·(ω+1),對于算法的收斂性具有重要的影響。采用基于Lyapunov函數的穩定性分析所確定的PSO參數選擇關系可以有效保證算法具有較好的收斂性。具有參數約束的PSO算法(Constraint PSO)能夠使每一個粒子飛行于較好的區域、更易于收斂,同時有效地提高粒子飛行的穩定性,使算法本身更具有較強的魯棒性。