顧明亮，李 旻

(華南理工大學(xué)機械與汽車工程學(xué)院，廣東 廣州 510640)

0 引 言

粒子群算法是由Kennedy和Eberhart[1]共同提出的。然而，基本的粒子群算法無法選擇進行全局搜索還是局部搜索。文獻(xiàn)[2]在基本粒子群算法的基礎(chǔ)上提出了帶有慣性權(quán)重的改進粒子群算法，由于該算法在迭代的過程中收斂效果較好，通常被默認(rèn)為標(biāo)準(zhǔn)粒子群算法。文獻(xiàn)[3]提出的線性遞減動態(tài)調(diào)整慣性權(quán)重粒子群算法能夠在迭代的過程中劃分粒子進行局部搜索還是全局搜索，取得了較好的效果。然而，當(dāng)面對復(fù)雜的非線性多維函數(shù)優(yōu)化問題時，算法容易陷入局部最優(yōu)解。因此，為了能夠讓算法達(dá)到最優(yōu)性能，非線性權(quán)值調(diào)整策略逐漸替代線性權(quán)值調(diào)整策略。非線性函數(shù)有很多，常用的調(diào)整曲線為正切曲線、正弦曲線和對數(shù)曲線等[4-6]。權(quán)值調(diào)整曲線的變化規(guī)律一般為：迭代前期，慣性權(quán)重w值較大，此時算法全局搜索能力較強；當(dāng)進入到迭代后期時，w值較小，此時局部搜索能力得到加強。然而，對于一些非線性多峰函數(shù)來說，當(dāng)算法進入到后期時容易陷入局部最優(yōu)解，造成算法早熟收斂[7-8]。

為了讓粒子群算法在迭代的后期可以搜索到全局最優(yōu)解，劉愛軍等人[9]在標(biāo)準(zhǔn)粒子群算法中加入了混沌搜索策略，利用混沌搜索的遍歷性來增強算法全局尋優(yōu)的能力。趙志剛等人[10]根據(jù)迭代過程中適應(yīng)度的大小關(guān)系將處于不同組別適應(yīng)度的粒子賦予不同的慣性權(quán)重。文獻(xiàn)[11]提出了基于反向?qū)W習(xí)的粒子群算法增加種群的多樣性。

本文首先通過拉丁超立方體抽樣產(chǎn)生初始種群，然后引入適應(yīng)度方差的概念，并將其與慣性權(quán)重調(diào)整策略相結(jié)合。當(dāng)方差小于設(shè)定的臨界方差時，對改進的慣性權(quán)重調(diào)整公式進行隨機擾動，并且引入小生境遺傳算法淘汰一些相似的個體，增加種群的多樣性，增強算法全局尋優(yōu)能力。最后通過測試函數(shù)對本文改進算法進行性能測試，將結(jié)果與其他5種算法結(jié)果進行對比，驗證此算法的有效性。

1 標(biāo)準(zhǔn)粒子群算法

假定種群的空間為N×D維，其中N代表種群數(shù)量；D代表粒子維數(shù)；D維向量Xi=(xi1,xi2,…，xiD)表示第i個粒子的位置(i=1,2,…，N)，其速度可表示為Vi=(vi1,vi2,…，viD)；pbest=(pi1,pi2,…，piD)表示個體極值；gbest=(g1,g2,…，gD)表示全局極值。在獲得個體極值與全局極值之后，可以根據(jù)式(1)和式(2)來更新粒子的速度和位置。

vij(t+1)= wvij(t)+c1r1[pij(t)-xij(t)]+

c2r2[pgi(t)-xij(t)]

(1)

xij(t+1)=xij(t)+vij(t+1)

(2)

其中，c1和c2為學(xué)習(xí)因子，也稱加速常數(shù)；r1和r2為[0,1]均勻分布的隨機數(shù)；w為慣性權(quán)重。

2 改進的粒子群算法

2.1 初始種群的改進

算法一般是以隨機方式產(chǎn)生初始種群的位置，這種方式比較容易實現(xiàn)，但是可能會導(dǎo)致種群內(nèi)個體分布不均勻。因此，本文選用拉丁超立方體抽樣的方法產(chǎn)生初始種群的位置[12]。拉丁超立方體抽樣(Latin Hypercube Sampling,LHS)可以保證全空間填充和抽樣點非重疊，從而使得群體分布均勻。

LHS抽樣步驟如下：

step1確定抽樣規(guī)模H。

step2將每維變量xi的定義域區(qū)間[xil, xih]劃分成H個相等的小區(qū)間，這樣就共有Hn個小超立方體產(chǎn)生。

step3產(chǎn)生一個H×n的矩陣A，A的每列均是數(shù)列{1,2,…,n}的一個隨機全排列。

step4A的每行就只有一個小超立方體被選中，在每個小超立方體內(nèi)產(chǎn)生一個樣本，這樣就共有H個樣本被選出，且選出的樣本互不相同。

通過拉丁超立方體抽樣產(chǎn)生的粒子可以充滿整個區(qū)間，產(chǎn)生的初始種群樣本能更好地均勻分布在整個空間，能有效避免出現(xiàn)早熟收斂現(xiàn)象。

2.2 自適應(yīng)慣性權(quán)重的改進

由于慣性權(quán)重決定算法在迭代過程中全局搜索占主要部分還是局部搜索占主要部分，因此權(quán)值的調(diào)整是決定算法性能的關(guān)鍵因素[13]。目前大多數(shù)采用的是線性遞減動態(tài)調(diào)整權(quán)值策略。然而對于一些非線性復(fù)雜函數(shù)優(yōu)化問題來說，使用線性遞減權(quán)值調(diào)整公式時，由于粒子的啟發(fā)性得不到提高，常常會使得種群陷入局部最優(yōu)解，導(dǎo)致算法性能大大降低。為了讓粒子可以搜索到全局最優(yōu)解，本文利用非線性函數(shù)構(gòu)造慣性權(quán)重進化曲線。由于Sigmod函數(shù)在前段和后段變化速度較為緩慢，只需將Sigmod函數(shù)稍微修改一下就完全符合慣性權(quán)重w的變化規(guī)律。因此本文選用Sigmod函數(shù)作為構(gòu)造非線性慣性權(quán)重調(diào)整的基函數(shù)。

Sigmod函數(shù)：

(3)

Sigmod函數(shù)的變化規(guī)律如圖1所示。

圖1 Sigmod函數(shù)曲線

從圖1可以看出，Sigmod函數(shù)曲線在前段和后段曲線斜率較小，變化速度較慢；在中間處，曲線斜率較大，變化速度較快；并且系數(shù)a越大，在曲線前段和后段變化越慢，中間變化越快。為了將Sigmod函數(shù)更好地運用在慣性權(quán)重調(diào)整公式中，本文選用參數(shù)a=5。為了使Sigmod函數(shù)適用于慣性權(quán)重的變化規(guī)律，將其變形為式(4)：

(4)

然而，雖然粒子的慣性權(quán)重調(diào)整公式的變化規(guī)律為非線性變化，但仍然避免不了陷入局部最優(yōu)解，此時種群中粒子的適應(yīng)度大小接近，并且會聚集在局部極值點，粒子出現(xiàn)“靠攏”現(xiàn)象。本文以粒子適應(yīng)度方差[14]評價種群的多樣性好壞。當(dāng)粒子適應(yīng)度方差小于設(shè)定的臨界值時，種群的多樣性很差，粒子有可能陷入局部最優(yōu)解。為了讓粒子跳出局部最優(yōu)解，增強種群的多樣性，此時應(yīng)增大粒子的慣性權(quán)重，給予慣性權(quán)重隨機擾動。

(5)

式(5)中，f為歸一化因子，favg為種群平均適應(yīng)度；σ2為適應(yīng)度方差；歸一化因子f取值如公式(6)所示：

(6)

因此整個慣性權(quán)重的調(diào)整公式如公式(7)所示：

(7)

式(7)中，ε為設(shè)定的適應(yīng)度方差臨界值；rand為[0,1]上均勻分布的隨機數(shù)。

由于粒子的“靠攏”現(xiàn)象，雖然給慣性權(quán)重賦予了較大的數(shù)值，仍然有可能陷入局部最優(yōu)。對于非線性多峰函數(shù)來說，當(dāng)群體多樣性較差時，將小生境遺傳算法嵌入到粒子群算法中，增強算法的全局尋優(yōu)能力。

2.3 小生境淘汰策略

小生境技術(shù)就是將父代種群與經(jīng)過交叉、變異操作過后的子代種群合并在一起，通過某種策略(預(yù)選擇、排擠、分享)選擇適應(yīng)度較好的個體進行下次迭代。小生境策略在小生境距離之內(nèi)只保留一個適應(yīng)度較好的個體，大大增加了種群的多樣性，是一種較好的全局尋優(yōu)算法。

小生境淘汰策略算法步驟如下：

step1初始化種群。

step2執(zhí)行遺傳操作(選擇、交叉、變異)。

step3將經(jīng)過遺傳操作產(chǎn)生的M個子代個體與N個父代個體合并在一起，得到一個含有M+N個個體的新種群。按照公式(8)計算新種群中每2個個體海明距離。

(8)

當(dāng)‖Xi-Xj‖

Fmin(Xi,Xj)=Peanlty

(9)

step4對新種群中個體的適應(yīng)度進行排序，選擇適應(yīng)度最好的N個個體作為下次迭代的父代種群。

step5若滿足算法終止條件則算法停止；否則返回step2。

2.4 非線性動態(tài)調(diào)整慣性權(quán)重小生境粒子群算法(NDWNPSO)

在對一些復(fù)雜的非線性多峰值函數(shù)進行優(yōu)化求解的時候，由于一般的粒子群算法在進化過程中容易過早收斂，陷入局部最優(yōu)解。本文改進算法是在粒子群算法中嵌入小生境遺傳算法[15-17]。算法實現(xiàn)步驟如下：

step1初始化粒子群。由拉丁超立方體抽樣產(chǎn)生初始種群的位置，初始種群中粒子的速度隨機產(chǎn)生。

step2計算粒子的適應(yīng)度值，確定粒子的個體極值，記為pbest(i)；確定粒子的全局極值，記為gbest。

step3根據(jù)公式(5)和公式(6)計算粒子的適應(yīng)度方差；根據(jù)公式(7)計算粒子的慣性權(quán)重；如果σ2ε，轉(zhuǎn)至step4；否則轉(zhuǎn)至step6。

step4執(zhí)行遺傳操作(選擇、交叉、變異)。

step5將初始種群與經(jīng)過操作的種群合并，根據(jù)公式(8)計算粒子之間的海明距離，通過小生境淘汰策略選擇適應(yīng)度最好的N個粒子。

step6更新粒子的速度和位置；計算各粒子的適應(yīng)度值，存儲pbest(i)和gbest。

step7判斷算法是否滿足終止條件；若滿足，則轉(zhuǎn)至step8；否則轉(zhuǎn)至step2。

step8輸出gbest。

3 仿真分析

3.1 測試函數(shù)

為了測試此改進算法的有效性，選取以下6個函數(shù)測試算法性能，其中既有簡單的單峰函數(shù)，又有復(fù)雜的非線性多維函數(shù)和病態(tài)函數(shù)。測試函數(shù)詳細(xì)信息見表1。為體現(xiàn)出改進算法優(yōu)勢，選取基本PSO算法、線性遞減權(quán)重粒子群算法(LDWPSO)、混沌搜索粒子群算法(CLSPSO)、自然選擇粒子群算法(NPSO)和遺傳算法(GA)進行對比仿真實驗。

表1 測試函數(shù)

函數(shù)取值范圍最優(yōu)值Rosenbrock[-10,10]0Rastrigrin[-5.12,5.12]0Griewank[-100,100]0Ackley[-100,100]0Sphere[-100,100]0Quatic[-1.28,1.28]0

3.2 仿真結(jié)果及分析

算法設(shè)置參數(shù)為：學(xué)習(xí)因子c1=2，c2=2；wmax=0.9,wmin=0.4。對每個測試函數(shù)進行30次尋優(yōu)，算法的3種統(tǒng)計特性如表2、表3所示。Best表示最優(yōu)適應(yīng)度，Mean表示適應(yīng)度均值，Std表示適應(yīng)度標(biāo)準(zhǔn)差。

表2 6種算法運行結(jié)果對比(D=10，MaxGen=1000)

函數(shù)統(tǒng)計特性RosenbrockRastrigrinGriewankAckleySphereQuaticPSOBest2.24E-51.993.20E-24.16E-41.91E-112.50E-3Mean1.643.296.73E-22.832.99E-87.80E-3Std2.111.414.53E-26.647.05E-84.90E-3LDWPSOBest6.40E-32.982.22E-21.164.25E-303.10E-3Mean2.146.697.30E-27.701.75E-181.10E-2Std1.992.173.20E-29.345.25E-188.70E-2NPSOBest1.36E-61.994.30E-21.94E-53.21E-181.20E-3Mean0.903.986.87E-24.357.07E-155.63E-3Std1.371.411.10E-27.881.40E-143.30E-3CLSPSOBest2.72E-51.992.11E-22.17E-77.00E-171.90E-3Mean7.62E-22.755.83E-20.101.93E-152.88E-2Std9.90E-20.771.90E-20.312.68E-153.10E-2GABest0.242.130.125.92E-45.95E-102.16E-2Mean1.383.350.188.30E-31.98E-83.40E-2Std0.821.187.40E-25.70E-32.07E-89.00E-3NDWNPSOBest1.91E-54.19E-83.50E-66.52E-57.97E-331.10E-3Mean2.93E-30.101.34E-41.73E-45.54E-266.09E-3Std4.21E-30.512.90E-41.08E-41.66E-253.12E-3

表3 6種算法運行結(jié)果對比(D=30，MaxGen=5000)

函數(shù)統(tǒng)計特性RosenbrockRastrigrinGriewankAckleySphereQuaticPSOBest29.3912.941.89E-41.516.08E-51.65E-2Mean49.5315.251.93E-214.849.90E-34.10E-2Std19.151.611.97E-29.202.99E-41.43E-2LDWPSOBest66.5425.101.90E-22.733.10E-45.46E-2Mean85.3032.733.00E-216.839.90E-47.90E-2Std11.134.748.00E-36.906.00E-41.60E-2NPSOBest19.7913.931.23E-23.60E-33.16E-51.00E-2Mean22.8016.902.26E-214.101.91E-41.98E-2Std1.903.247.80E-39.102.09E-46.10E-3CLSPSOBest18.7013.192.60E-72.90E-34.31E-55.70E-2Mean21.0017.103.33E-28.383.06E-40.13Std1.662.683.50E-210.062.50E-44.50E-2GABest18.7721.662.29E-415.431.28E-50.14Mean21.6126.142.36E-218.101.81E-40.17Std2.099.511.90E-21.531.90E-42.10E-2NDWNPSOBest1.00E-43.971.22E-104.98E-55.05E-61.30E-2Mean1.17E-24.621.31E-25.02E-41.72E-53.10E-2Std1.37E-20.601.69E-24.38E-41.35E-51.39E-2

圖2 Rosenbrock函數(shù)進化曲線 圖3 Rastrigrin函數(shù)進化曲線 圖4 Ackley函數(shù)進化曲線

圖5 Griewank函數(shù)進化曲線 圖6 Sphere函數(shù)進化曲線 圖7 Quatic函數(shù)進化曲線

本文算法主要是對慣性權(quán)重的調(diào)整和全局尋優(yōu)能力方面進行了改進，對比的結(jié)果表明了本文改進算法的有效性；尤其是面對復(fù)雜的非線性多峰函數(shù)時，本文算法能夠跳出局部最優(yōu)解，搜索到全局最優(yōu)解。

Sphere函數(shù)和Quatic函數(shù)為簡單的單峰函數(shù)。從表2和表3中可以看出幾種算法都能以很快的速度搜索到最優(yōu)值，在相同迭代次數(shù)下，本文改進優(yōu)化算法收斂精度較好。

其他4個函數(shù)相對于前2個函數(shù)來說比較復(fù)雜，一般的算法在對這類函數(shù)進行尋優(yōu)時容易陷入局部最優(yōu)解，從表2和表3中可以看出，使用小生境策略跳出局部最優(yōu)解是可行的。由于改進算法將小生境策略嵌入到改進粒子群算法中，使得種群多樣性大大增加，算法的后期性能得到改善。從表中可以看出，其他幾種算法容易陷入局部最優(yōu)解，本文改進算法在一定程度上能夠使算法跳出局部最優(yōu)解。

從圖2～圖7和表中可以看出改進的粒子群算法不管是求解單峰函數(shù)還是多峰函數(shù)都有很好的性能，尤其是面對容易陷入局部最優(yōu)解的非線性復(fù)雜函數(shù)時，本文改進算法較其他2種算法在性能方面有了很大提高。

4 結(jié)束語

本文針對粒子群算法在處理非線性復(fù)雜函數(shù)優(yōu)化方面的不足，提出了將變形的Sigmod函數(shù)作為自適應(yīng)慣性權(quán)重調(diào)整公式的基函數(shù)。改進算法具有如下特點：1)引入非線性權(quán)值調(diào)整公式，在算法前期保證進化速度較快，在算法后期能夠有可能擁有較大的慣性權(quán)重跳出局部最優(yōu)解。2)在處理非線性多維復(fù)雜函數(shù)優(yōu)化方面，引入小生境遺傳算法作為算法跳出局部最優(yōu)解、尋求全局最優(yōu)解的關(guān)鍵。3)以單峰函數(shù)和多峰函數(shù)作為測試函數(shù)，通過對比其他幾種算法性能，發(fā)現(xiàn)改進算法不管是在全局最優(yōu)解的尋求還是在算法收斂速度和精度上均展現(xiàn)出了較好的性能。

結(jié)果表明，改進的自適應(yīng)慣性權(quán)重粒子群算法既兼顧了算法的收斂速度和收斂精度，在多峰函數(shù)的尋優(yōu)上也體現(xiàn)出了較好的性能。因此，改進算法可用于高維非線性復(fù)雜問題的求解。

參考文獻(xiàn)：

[1] Kennedy J, Eberhart R C. Particle swarm optimization[C]// Proceedings of IEEE International Conference on Neural Networks. 1995:1942-1948.

[2] Shi Y H, Eberhart R C. A modified particle swarm optimizer[C]// Proceedings of IEEE Congress on Eveolutionary Computation. 1998:69-73.

[3] Shi Y H, Eberhart R C. Parameter selection in particle swarm optimization[C]// The 7th International Conference on Evolutionary Programming VII. 1998,1447:591-600.

[4] 敖永才,師奕兵,張偉,等. 自適應(yīng)慣性權(quán)重的改進粒子群算法[J]. 電子科技大學(xué)學(xué)報, 2014,43(6):874-880.

[5] 王傳飛,韋濤,孫建芳. 改進粒子群算法求解廣義Usher油田開發(fā)動態(tài)預(yù)測模型[J]. 新疆石油地質(zhì), 2012,33(1):102-105.

[6] Zhang Jianhua, Yang Shaozeng. A novel PSO algorithm based on an incremental PID controlled search strategy[J]. Methodologies and Application, 2016,20(3):991-1005.

[7] 張宏偉,張向鋒,朱晨煊. 一種含駐留粒子的改進粒子群算法[J]. 計算機與現(xiàn)代化, 2017(11):1-5,12.

[8] 董立軍,蒲亦非,周激流. 基于多尺度分?jǐn)?shù)階多重記憶與學(xué)習(xí)的粒子群算法[J]. 計算機應(yīng)用研究, 2018,35(3):1-2.

[9] 劉愛軍,楊育,李斐,等. 混沌模擬退火粒子群優(yōu)化算法研究及應(yīng)用[J]. 浙江大學(xué)學(xué)報(工學(xué)版), 2013,47(10):1722-1730.

[10] 趙志剛,林玉嬌,尹兆遠(yuǎn). 基于自適應(yīng)慣性權(quán)重的均值粒子群優(yōu)化算法[J]. 計算機工程與科學(xué), 2016,38(3):501-506.

[11] Comak E. A generalized particle swarm optimization using reverse direction information[J]. Turk J Elec Eng & Comp Sci, 2016,24(2):639-655.

[12] 鄭金華,羅彪. 一種基于拉丁超立方體抽樣的多目標(biāo)進化算法[J]. 模式識別與人工智能, 2009,22(2):223-233.

[13] He Yan, Ma Weijin, Zhang Jiping. The parameters selection of PSO algorithm influencing on performance of fault diagnosis[C]// 2016 International Conference on Mechatronics, Manufacturing and Materials Engineering. 2016.

[14] 李佳,劉天琪,李興源,等. 改進粒子群-禁忌搜索算法在多目標(biāo)無功優(yōu)化中的應(yīng)用[J]. 電力自動化設(shè)備, 2014,34(8):71-77.

[15] 馬松濤. 復(fù)雜優(yōu)化問題中小生境粒子群優(yōu)化算法的改進及研究[D]. 鄭州:鄭州大學(xué), 2013.

[16] Gong Yuejiao, Li Jingjing, Zhou Yicong. Genetic learning particle swarm optimization[J]. IEEE Transactions on Cybernetics, 2016,46(10):2277-2290.

[17] 謝紅俠,馬曉偉,陳曉曉,等. 基于多種群的改進粒子群算法多模態(tài)優(yōu)化[J]. 計算機應(yīng)用, 2016,36(9):2516-2520.