基于分層型的改進粒子群優化算法

安無恙，呂柏權，李 嫽

（上海大學 機電工程與自動化學院，上海 200072）

粒子群優化算法PSO是一種基于生物群智能的隨機啟發式搜索算法。其思想來源于對魚群，鳥群等生物群體捕食的行為觀察研究[1]。PSO具有計算簡單、可調參數少、容易實現、尋優能力強等優勢[2]，但基本的PSO算法容易陷入局部最優，出現早熟收斂現象，導致優化精度不高，因此改進基本PSO算法顯得尤為重要[3]。

本文針對粒子群的特點與存在的缺陷，基于函數映射到不同平面的特點，提出了一種基于分層型的改進粒子群優化算法。

1 基本粒子群算法

粒子群優化算法在求解優化問題時，每個優化問題都好比是在搜索空間中的每只鳥的位置[4]，將這些鳥都看作是單個“粒子”，每個粒子都有自己相應的位置和速度，以及一個由優化函數確定的相適應的值。在整個優化尋優的過程中，每個粒子都將以當前自身的最小值來跟蹤其當前所有粒子的最小值，并在搜索的過程中向著最小值的方向前進，通過一次次迭代不斷接近全局最小點[5]。

定義粒子所找到的當前自身的最優解為個體極值pbest；定義整個粒子群體找到的當前的最優解為全局極值gbest。在每一次迭代過程中，每個粒子將自己的當前值與其pbest進行比較，如果粒子的當前值比pbest小，則用該值代替pbest，否則pbest值不變，同時將pbest與gbest比較，如果pbest比gbest小，則用此值代替gbest，否則gbest值不變。

設在D維搜索空間中，有N個粒子，其中第i個粒子的位置是Xi=（xi1，xi2，…，xiD），其速度為Vi=（vi1，vi2，…，viD）。 記第i個粒子搜索到的歷史最優位置為Pi=（pi1，pi2，…，piD），也稱為pbest，整個粒子群體搜索到的最優位置為Pg=（pg1，pg2，…，pgD）， 也稱為gbest。Knenedy和Eberhrt最早提出的PSO算法的位置和速度公式如下：

式中：i=1，2，…N；d=1，2，…，D；r1和r2是 2 個隨機數，他們相互獨立，服從［0，1］上的均勻分布；t則為當前迭代的次數；學習因子c1和c2為2個非負的常數，也被叫做加速系數，c1所作用的部分是粒子通過比較自身當前值與自身最優值，并不斷向當前自身最優值靠近的過程，c2所作用的部分是粒子通過比較自身當前值與所有粒子的最優值，并不斷向所有粒子的最優值靠近的過程，c1與c2合適的取值可加快搜索的收斂，而且不易陷入局部最優解。一般情況下c1和c2取2。為了控制xi和Vi躍出邊界，需 要 進 行 限 制 ，xid∈［ximin，ximax］、vid∈［-vmax，vmax］，ximin為xid定義域中的x的最小值，ximax為xid定義域中x的最大值，vmax是之前設定的粒子的最大速率。

2 分層型粒子群優化算法的原理

分層型粒子群優化算法通過對粒子群進行旋轉分層，增加粒子的多樣性，將函數映射到不同的平面，從不同的角度和平面尋求函數的最優解。

假設該算法將粒子分為10層，每層10個粒子。在第一層的基礎上，旋轉α角或幾個α角，形成第二層，在第二層的基礎上，再旋轉α角或幾個α角，形成第三層，以此類推，形成10個粒子層。

要使一個層旋轉，首先需要一個旋轉矩陣。為了推導D維空間中的旋轉矩陣，可以從二維以及三維旋轉矩陣的推導入手，然后以此推出多維空間中旋轉矩陣M的生成。

2.1 二維旋轉矩陣

對于在二維平面內的向量，其在平面內只旋轉了一個角度，而向量的模不變，如圖1所示。

圖1 二維平面內向量旋轉Fig.1 Vector rotation in two dimensional plane

設向量OP的模為R，則可以得到旋轉前所對應的坐標大小為

而旋轉后的向量OP的模并沒有發生變化，此時對應的橫縱坐標變為

于是寫成矩陣形式表示為

所以二維空間的旋轉矩陣M可以表示為

2.2 三維旋轉矩陣

推導三維空間中旋轉矩陣的表達形式，先考慮特殊情況，即以坐標系的3個軸為旋轉軸的情況下向量的坐標變化情況。

如圖2，當向量OP繞著x軸旋轉時，其x坐標是不會發生變化的，產生變化的只是其在yoz平面上的投影位置，即對應的y、z坐標發生了變化。

圖2 三維空間內向量旋轉Fig.2 Vector rotation in three dimensional plane

旋轉前：

旋轉后：

用矩陣形式可以寫成：

所以繞x軸旋轉時的旋轉矩陣：

同理可以分別得到繞y，z軸旋轉的旋轉矩陣。三種情況下旋轉矩陣分別為

根據歐拉旋轉定理，任何一個角位移都可以分解為繞3個互相垂直的坐標軸的3次旋轉，所以當三維空間里向量繞任意1個軸旋轉時，可以表示成分別以x、y、z為旋轉軸的旋轉運動的疊加。

如果向量的旋轉分解為繞著z軸旋轉α角，繞著y軸旋轉γ角，繞著x軸旋轉角得到了旋轉后的向量，總的旋轉矩陣可表示為M=Mx（ β）·My（γ）·Mz（α）。

2.3 D維旋轉矩陣

從二維和三維的旋轉矩陣發現，在三維矩陣旋轉時，當繞某一坐標軸旋轉時，該坐標軸在旋轉矩陣中對應的那一行列的向量不變，而在相應的位置中添加元素

二維空間向量是繞著1個點旋轉，三維空間向量是繞著1條軸旋轉，以此類推，四維空間是繞著1個平面進行旋轉，即由2條互相垂直的坐標軸組成的平面。那么在D維空間里，當向量繞著某D-2個坐標軸所組成的空間進行旋轉時，D×D維矩陣中D-2個行列的元素不變，相應位置中添加元素即代表了1次旋轉。所以構建旋轉矩陣的Matlab程序可以表示成如下：

上述每一次循環所產生的旋轉矩陣即為D維空間中圍繞由其中D-2個坐標軸組成的空間旋轉隨機角度RR所產生的旋轉角，在每次循環的基礎上乘上一個新的旋轉矩陣代表了每一次旋轉的疊加。上述語句代表著生成一個隨機的D維空間的正交旋轉矩陣在空間旋轉一個角度α。

MM1=eye（D，D）；

MM2=（D21）*M1^（D20）*M1；%旋轉

MM3=（D21）*M1^（D20）*MM2；%旋轉

MM4=（D21）*M1^（D20）*MM3；%旋轉

MM5=（D21）*M1^（D20）*MM4；%旋轉

MM6=（D21）*M1^（D20）*MM5；%旋轉

MM7=（D21）*M1^（D20）*MM6；%旋轉

MM8=（D21）*M1^（D20）*MM7；%旋轉

MM9=（D21）*M1^（D20）*MM8；%旋轉

MM10=（D21）*M1^（D20）*MM9；%旋轉

D20是一個正系數，表示一次旋轉D20個α角，D21是縮放系數，適當的取值可以避免旋轉后超出搜索范圍。上述程序進行了10次旋轉，在前一矩陣的基礎上旋轉D20個α角，依次旋轉得到了10個不同角度的矩陣，起到了分層的效果。

用所在層的粒子隨機產生的位置乘上該層的線性正交矩陣M得到新的位置，然后將所得位置值x代入優化函數計算出適應值。圖3顯示了一個二維函數有無旋轉情況下的取值分布?？梢园l現旋轉不會改變函數的結構，但增加了尋找的多樣性。

圖3 曲面旋轉前后情況Fig.3 Rotation result of curved surface

將目標函數分別映射到不同層上，在各個層搜索函數的最優解，將每層最優值與10層中找到的最優值進行比較更新，最終整個粒子群的全局的最優值。

粒子群的位置和速度更新公式如下：

式中：i表示第幾層；j表示第幾個粒子；k表示在第幾維空間；x_best（i，j，k）表示每個粒子的個體最優值，x_allbest（i，k）表示第i層的最優值，x_allbestg（k）表示整個粒子群的全局最優值。

3 分層型粒子群優化算法的原理

圖4為粒子群優化算法流程。

圖4 分層型粒子群優化算法流程Fig.4 Flow chart of particle swarm optimization algorithm based on hierarchical

分層型粒子群優化算法流程：

（1）設置粒子群的層數和每層的粒子數和每個層的旋轉角度，對粒子的位置和速度隨機初始化。

（2）根據式（3）、（4）、（5）計算每個粒子的適應值。

（3）根據每個粒子的位置，更新個體歷史最優位置x_best（i，j，k）。

（4）根據每個粒子的位置，將其適應值與該層內的所有粒子中最好的個體極值比較，如果更好，則將此位置設置為該層的全局最優值，更新該層最優值x_allbest（i，k）。

（5）根據每個粒子的位置，若適應值比整個群體的全局最優值更好，則將其位置設為整個群體的全局最優值，更新x_allbestg（k）。

（6）判斷是否達到最大迭代次數或解在誤差允許范圍之內。若是，則x_allbestg（k）為全局最優值，否則，轉至（2）。

4 仿真

在本文中，通過表1的基準測試函數仿真檢驗提出算法。

表1 基準測試函數（維數：30）Tab.1 Benchmark function（dimension：30）

4.1 仿真參數設置

用Matlab軟件對上述9個基準測試函數進行仿真。分層型粒子群優化算法仿真參數初始值如表2所示。

表2 分層型粒子群優化算法的參數初始值Tab.2 Parameter initial value of particle swarm optimization algorithm based on hierarchical

4.2 仿真試驗結果

將上述9個基準測試函數作為測試函數，對每個基準測試函數都運行30次，統計每次運行的全局最優值結果及30次中成功收斂的次數，以及CPU運行的時間，在除去搜索失敗的結果后，計算出每個函數成功收斂的最優值的平均值、最大值、最小值。為了比較算法在其他維數空間的性能優劣，分別在40、50、60維空間對每個基準函數都運行了一次，并把在四個維數空間運行的仿真曲線放在了一張圖上。

表3是對9個基準測試函數的仿真結果。仿真結果顯示：30個實驗值全部成功搜索全局最優解，成功率為100%。

4.3 仿真試驗迭代曲線

圖5是對9個基準測試函數的仿真實驗迭代曲線，各參數設置和初始值與前面相同，縱坐標表示搜索到的全局最優值，橫坐標表示最大迭代次數。為了比較算法在其他維數空間的性能優劣，還對40、50、60維空間分別仿真了一次，將這4個維數空間的迭代曲線放在了1張圖上。

表3 分層型粒子群優化算法對測試函數的結果Tab.3 Test function results of particle swarm optimization algorithm based on hierarchical

從圖中，可以發現雖然有些函數的搜索精度隨著維度的上升而減弱，但是40，50，60維的精度還是與30維的精度相差無幾，這說明了本算法的魯棒性還是比較強的。

5 結語

圖5 仿真對比圖Fig.5 Simulation contrast diagram

本文對于傳統粒子群算法容易陷入局部極值點的問題提出了基于分層型的改進粒子群優化算法，通過旋轉形成10個不同角度的粒子層，從不同的角度和平面求解函數的最優解，增加了粒子群的多樣性，提高了搜索到最優點的可能性。并對9個基準測試函數在30、40、50、60維進行了仿真，從不同維度比較算法的搜索性能。從總體來看，分層型粒子群優化算法搜索性能較好。