基于分層型的改進(jìn)粒子群優(yōu)化算法

安無恙，呂柏權(quán)，李 嫽

（上海大學(xué) 機(jī)電工程與自動化學(xué)院，上海 200072）

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

本文針對粒子群的特點(diǎn)與存在的缺陷，基于函數(shù)映射到不同平面的特點(diǎn)，提出了一種基于分層型的改進(jìn)粒子群優(yōu)化算法。

1 基本粒子群算法

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

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

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

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

2 分層型粒子群優(yōu)化算法的原理

分層型粒子群優(yōu)化算法通過對粒子群進(jìn)行旋轉(zhuǎn)分層，增加粒子的多樣性，將函數(shù)映射到不同的平面，從不同的角度和平面尋求函數(shù)的最優(yōu)解。

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

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

2.1 二維旋轉(zhuǎn)矩陣

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

圖1 二維平面內(nèi)向量旋轉(zhuǎn)Fig.1 Vector rotation in two dimensional plane

設(shè)向量OP的模為R，則可以得到旋轉(zhuǎn)前所對應(yīng)的坐標(biāo)大小為

而旋轉(zhuǎn)后的向量OP的模并沒有發(fā)生變化，此時對應(yīng)的橫縱坐標(biāo)變?yōu)?/p>

于是寫成矩陣形式表示為

所以二維空間的旋轉(zhuǎn)矩陣M可以表示為

2.2 三維旋轉(zhuǎn)矩陣

推導(dǎo)三維空間中旋轉(zhuǎn)矩陣的表達(dá)形式，先考慮特殊情況，即以坐標(biāo)系的3個軸為旋轉(zhuǎn)軸的情況下向量的坐標(biāo)變化情況。

如圖2，當(dāng)向量OP繞著x軸旋轉(zhuǎn)時，其x坐標(biāo)是不會發(fā)生變化的，產(chǎn)生變化的只是其在yoz平面上的投影位置，即對應(yīng)的y、z坐標(biāo)發(fā)生了變化。

圖2 三維空間內(nèi)向量旋轉(zhuǎn)Fig.2 Vector rotation in three dimensional plane

旋轉(zhuǎn)前：

旋轉(zhuǎn)后：

用矩陣形式可以寫成：

所以繞x軸旋轉(zhuǎn)時的旋轉(zhuǎn)矩陣：

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

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

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

2.3 D維旋轉(zhuǎn)矩陣

從二維和三維的旋轉(zhuǎn)矩陣發(fā)現(xiàn)，在三維矩陣旋轉(zhuǎn)時，當(dāng)繞某一坐標(biāo)軸旋轉(zhuǎn)時，該坐標(biāo)軸在旋轉(zhuǎn)矩陣中對應(yīng)的那一行列的向量不變，而在相應(yīng)的位置中添加元素

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

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

MM1=eye（D，D）；

MM2=（D21）*M1^（D20）*M1；%旋轉(zhuǎn)

MM3=（D21）*M1^（D20）*MM2；%旋轉(zhuǎn)

MM4=（D21）*M1^（D20）*MM3；%旋轉(zhuǎn)

MM5=（D21）*M1^（D20）*MM4；%旋轉(zhuǎn)

MM6=（D21）*M1^（D20）*MM5；%旋轉(zhuǎn)

MM7=（D21）*M1^（D20）*MM6；%旋轉(zhuǎn)

MM8=（D21）*M1^（D20）*MM7；%旋轉(zhuǎn)

MM9=（D21）*M1^（D20）*MM8；%旋轉(zhuǎn)

MM10=（D21）*M1^（D20）*MM9；%旋轉(zhuǎn)

D20是一個正系數(shù)，表示一次旋轉(zhuǎn)D20個α角，D21是縮放系數(shù)，適當(dāng)?shù)娜≈悼梢员苊庑D(zhuǎn)后超出搜索范圍。上述程序進(jìn)行了10次旋轉(zhuǎn)，在前一矩陣的基礎(chǔ)上旋轉(zhuǎn)D20個α角，依次旋轉(zhuǎn)得到了10個不同角度的矩陣，起到了分層的效果。

用所在層的粒子隨機(jī)產(chǎn)生的位置乘上該層的線性正交矩陣M得到新的位置，然后將所得位置值x代入優(yōu)化函數(shù)計算出適應(yīng)值。圖3顯示了一個二維函數(shù)有無旋轉(zhuǎn)情況下的取值分布?？梢园l(fā)現(xiàn)旋轉(zhuǎn)不會改變函數(shù)的結(jié)構(gòu)，但增加了尋找的多樣性。

圖3 曲面旋轉(zhuǎn)前后情況Fig.3 Rotation result of curved surface

將目標(biāo)函數(shù)分別映射到不同層上，在各個層搜索函數(shù)的最優(yōu)解，將每層最優(yōu)值與10層中找到的最優(yōu)值進(jìn)行比較更新，最終整個粒子群的全局的最優(yōu)值。

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

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

3 分層型粒子群優(yōu)化算法的原理

圖4為粒子群優(yōu)化算法流程。

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

分層型粒子群優(yōu)化算法流程：

（1）設(shè)置粒子群的層數(shù)和每層的粒子數(shù)和每個層的旋轉(zhuǎn)角度，對粒子的位置和速度隨機(jī)初始化。

（2）根據(jù)式（3）、（4）、（5）計算每個粒子的適應(yīng)值。

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

（4）根據(jù)每個粒子的位置，將其適應(yīng)值與該層內(nèi)的所有粒子中最好的個體極值比較，如果更好，則將此位置設(shè)置為該層的全局最優(yōu)值，更新該層最優(yōu)值x_allbest（i，k）。

（5）根據(jù)每個粒子的位置，若適應(yīng)值比整個群體的全局最優(yōu)值更好，則將其位置設(shè)為整個群體的全局最優(yōu)值，更新x_allbestg（k）。

（6）判斷是否達(dá)到最大迭代次數(shù)或解在誤差允許范圍之內(nèi)。若是，則x_allbestg（k）為全局最優(yōu)值，否則，轉(zhuǎn)至（2）。

4 仿真

在本文中，通過表1的基準(zhǔn)測試函數(shù)仿真檢驗提出算法。

表1 基準(zhǔn)測試函數(shù)（維數(shù)：30）Tab.1 Benchmark function（dimension：30）

4.1 仿真參數(shù)設(shè)置

用Matlab軟件對上述9個基準(zhǔn)測試函數(shù)進(jìn)行仿真。分層型粒子群優(yōu)化算法仿真參數(shù)初始值如表2所示。

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

4.2 仿真試驗結(jié)果

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

表3是對9個基準(zhǔn)測試函數(shù)的仿真結(jié)果。仿真結(jié)果顯示：30個實(shí)驗值全部成功搜索全局最優(yōu)解，成功率為100%。

4.3 仿真試驗迭代曲線

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

表3 分層型粒子群優(yōu)化算法對測試函數(shù)的結(jié)果Tab.3 Test function results of particle swarm optimization algorithm based on hierarchical

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

5 結(jié)語

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

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