一種動態(tài)權(quán)值自適應(yīng)粒子群優(yōu)化典型函數(shù)問題

楊 巍，毛劍琳，熊 曄

(昆明理工大學 信息工程與自動化學院，云南 昆明 650500)

粒子群優(yōu)化(Particle Swarm Optimization，PSO)算法源于鳥群捕食行為的模擬，最早于1995年由Eberhart和Kennedy提出，該算法是典型的群體智能優(yōu)化算法[1-2]，具有設(shè)置參數(shù)較少，關(guān)聯(lián)度較低，操作靈活簡單等優(yōu)點。目前主要應(yīng)用在函數(shù)優(yōu)化問題[3]，結(jié)合模糊系統(tǒng)控制，神經(jīng)網(wǎng)絡(luò)控制在工程領(lǐng)域上已被廣泛應(yīng)用[4-6]。但傳統(tǒng)粒子群算法本身也存在缺陷，當變量維數(shù)較多時，目標函數(shù)中存在較多局部極值時，PSO算法容易出現(xiàn)提前收斂或陷入局部極值，進化后期收斂速度慢、精度低、易早熟等問題。目前解決辦法主要集中在兩個方面：一是算法優(yōu)化改進；二是算法研究上。因此，出現(xiàn)了粒子群諸多改進辦法[7-12]。改進過程中通常結(jié)合其他算法，往往增加PSO算法的復(fù)雜性，并未對算法進行實質(zhì)性的改變。在傳統(tǒng)PSO算法的迭代過程中主要是對速度更新和位置進行更新。方程涉及慣性環(huán)節(jié)、個體認知環(huán)節(jié)和群體認知環(huán)節(jié)。三個環(huán)節(jié)共同決定粒子群更新方向，使粒子朝著更好的方向運動。個體認知環(huán)節(jié)決定個體最優(yōu)位置，群體認知環(huán)節(jié)決定群體最優(yōu)位置，并且與當前位置都存有向量差。由于這兩個差的存在，使粒子迭代過程中逐漸趨向群體最優(yōu)解方向。慣性權(quán)值體現(xiàn)的是微粒子繼承上一時刻速度的大小程度。Shi.Y是最早將慣性權(quán)值的理念引入到PSO算法中。分析并指出，更新早期較大的慣性權(quán)值，使算法具有很強全局搜索能力，而更新后期較小的慣性權(quán)值使算法具有很強局部搜索能力，慣性權(quán)值的動態(tài)變化思想是在此基礎(chǔ)上提出的。本文在動態(tài)慣性權(quán)值的基礎(chǔ)上，引入動態(tài)學習因子與迭代次數(shù)相結(jié)合的方法，使微粒子具有較強的探索能力，避免出現(xiàn)陷入局部最優(yōu)的情況。并通過典型函數(shù)仿真驗證，在迭代過程中動態(tài)改變慣性權(quán)值及學習因子幅值，使其能夠擺脫局部極值的干擾，加快算法收斂速度，同時也提高了搜索的精度與準確度。

1 基本粒子群算法

傳統(tǒng)PSO算法是依據(jù)個體(微粒子)的函數(shù)值或適應(yīng)值進行操作的。每個微粒子根據(jù)自己及同伴的經(jīng)驗值共同作用，對速度和位置進行迭代更新，最終在群體空間中搜索出目標最優(yōu)值。粒子可以用N維向量表示,設(shè)N維空間中有m個微粒，粒子i的位置Xi為{xi1,xi2,xi3,…,xiN},速度Vi為{vi1,vi2,vi3,…，viN}，式中i為(1,2,3…，m)，Xi表示i粒子的當前位置，Vi為微粒i的當前速度。每一次的更新過程當中，粒子自身找到的最優(yōu)值，叫做個體極值(用Pbest表示其位置)；整個種群當前找到的群體最優(yōu)值，叫做全體極值(用Gbest表示其位置)。當前粒子通過跟隨個體極值與全體極值來更新自身的位置。粒子在每次更新過程當中，根據(jù)以下兩個公式來重新確定自身的速度和自身的位置。速度和位置更新公式為

(1)

式中，i∈(1,2,3,…，m)；j∈(1,2,3,…，N)；c1，c2學習因子，非負數(shù)；r∈(0,1)之間的隨機數(shù)w為慣性權(quán)值，k為迭代次數(shù)。

2 動態(tài)自適應(yīng)粒子群算法

與其他算法進行比較，傳統(tǒng)PSO算法,具有較短的收斂時間和較好的收斂性能，但是優(yōu)化過程中存在提前收斂早熟等現(xiàn)象。在尋優(yōu)過程中，容易由于種群多樣性(維度)喪失而使種群在局部收斂。因此，本文引入動態(tài)慣性權(quán)值[13]，加快進化速度的同時，加大其全局搜索能力。引入動態(tài)社會因子與動態(tài)認知因子增加局部搜索的準確性，并提高搜索精度。試驗證明，動態(tài)w能獲得比靜態(tài)的權(quán)值更好的尋優(yōu)效果。SHI提出的遞減權(quán)值法(Linearly Decreasing Weight，LDW)如式(2)所示，目前已被廣泛引用[14]

w(k)=wstart-k(wstart-wend)/Tmax

(2)

其中，wstar為初始慣性權(quán)重值，wend為最大迭代次數(shù)時的慣性權(quán)重值；K為當前迭代次數(shù)；Tmax為最大迭次數(shù)。一般來說，wstar=0.9，wend=0.4時尋優(yōu)性能較好。這樣，更新過程中，權(quán)值由0.9線性減至0.4。LDW方法為一種經(jīng)驗取法，常見的動態(tài)權(quán)值還包括以下幾種

(3)

(4)

(5)

幾種w動態(tài)曲線如圖1所示。

圖1 幾種常見動態(tài)權(quán)值曲線

為了驗證w動態(tài)變化性能，采取4種w取值方法并進行比較。粒子群規(guī)模為50，迭代100次。運行20次，比較其平局值，失效次數(shù)，在精度和速度上進行分析。實驗證明，動態(tài)權(quán)值采用式(3)具有更好的搜索性能，靜態(tài)慣性權(quán)值w恒定不變的傳統(tǒng)算法雖然具有較快的全局搜索速度，但后期容易陷入局部最優(yōu)，求解準確度較低。式(3)中的w動態(tài)變化方法，前期w取值較大變化較慢，有利于算法進行全局搜索；后期w取值較小變化較快，有利于算法跳出局部搜索而求得全局最優(yōu)值。提高了算法的求解精度，避免陷入局部陷阱。提高了算法的全局尋優(yōu)能力，取得較好的全局最優(yōu)解。

為了提高搜索的準確性，個體認知環(huán)節(jié)c1采納線性遞減的方法如式(6)所示，社會認知環(huán)節(jié)c2采納線性遞增的方發(fā)如式(7)所示。動態(tài)學習因子基本思想如圖2所示。

c1=c1max+(c1min-c1max)(Tmax-k)/Tmax

(6)

c2=c2min+k(c2max-c2min)Tmax

(7)

圖2 動態(tài)學習因子示意圖

粒子群更新前期，較大的個體認知環(huán)節(jié)有利于粒子群尋找個體最優(yōu)值，更新前期以個體認知為主；更新后期，較小的個體認知部分有利于趨近群體最優(yōu)方向。同樣，更新前期，較小的社會認知部分有利于尋找個體最優(yōu)值；更新后期以社會認知為主；較大的社會認知部分，有利于粒子趨于全體最優(yōu)值算法流程如下

步驟1初始化粒子群，隨機更新粒子位置與速度，設(shè)置種群數(shù)量，迭代次數(shù)；

步驟2計算粒子的適應(yīng)度或函數(shù)值，確定個體最優(yōu)位置Pbest和群體最優(yōu)位置Gbest；

步驟3更新每個微粒子的位置和速度；

步驟4更新個體最優(yōu)值與群體最優(yōu)值；

步驟5迭代次數(shù)k加1，更新w，c1，c2；

步驟6如果k大于最大迭代次數(shù)，則去執(zhí)行步驟7，否則返回到步驟3；

步驟7最終Gbest為所得到的最優(yōu)參數(shù)。

3 實驗仿真及分析

3.1 經(jīng)典函數(shù)

本文采用經(jīng)典的Rastrigin(Ras)函數(shù)和Schaffer函數(shù)對所提出的動態(tài)慣性權(quán)值自適應(yīng)粒子群算法進行仿真測試，具體信息如下。

(1)Ras函數(shù)。Rastrigin函數(shù)為非線性對稱函數(shù)，這個函數(shù)對模擬退火、蜂群算法等算法具有很強的干擾和欺騙性。它具有較多的局部最小值點和局部最大值點，尋優(yōu)過程中容易陷入局部陷阱，提前收斂。這里采用改進的粒子群優(yōu)化算法對其求解最大值，該函數(shù)的數(shù)學公式如下

f(x)=20+x2+y2-10(cos2πx+cos2πy)

(8)

Ras函數(shù)的三維表示如圖3所示。

圖3 Ras函數(shù)三維圖

(2)Schaffer函數(shù)。Schaffer函數(shù)同Ras函數(shù)一樣很難找到最優(yōu)解，原因是全局極值的周圍被很多局部極值所圍繞，該函數(shù)公式如下

(9)

Schaffer函數(shù)的三維表示如圖4所示。

圖4 Schaffer函數(shù)的三維圖

3.2 參數(shù)設(shè)置

為了驗證改進的動態(tài)PSO算法的準確性和有效性，本文采用了經(jīng)典的多峰Ras函數(shù)和Schaffer函數(shù)來測試算法的尋優(yōu)性能，并與模擬退火算法進行比較，算法中粒子群規(guī)模為100，最大迭代次數(shù)300代，v∈[1,-1]，c1∈[1，2.5]，c2∈[1，2.5]。函數(shù)在[-5，5]范圍內(nèi)取最大值，實驗結(jié)果表明，改進的動態(tài)慣性權(quán)值自適應(yīng)粒子群算法具有很強的全局及局部搜索能力，精確度高、響應(yīng)速度快。下面實驗均進行20次，取最優(yōu)作為實驗的結(jié)果。

圖5 Ras函數(shù)最大值

與傳統(tǒng)粒子群算法和模擬退火算法相比，改進的PSO算法收斂速度更快,準確度更高。Ras函數(shù)大約迭代32代，Schaffer函數(shù)大約迭代30次可達到收斂，找到最大值，精度更高，尋優(yōu)效果大幅增強。

表1 Ras函數(shù)尋優(yōu)

圖6 Schaffer函數(shù)最大值

最大值迭代次數(shù)ADPS算法130PSO算法0.999 1110SA算法0.995 035

實驗結(jié)果表明，本文提出動態(tài)慣性權(quán)值自適應(yīng)粒子群算法(ADPSO)與傳統(tǒng)PSO算法，模擬退火算法[15]進行比較。為了更好、更直觀地反應(yīng)尋優(yōu)效果，圖5和圖6給出了3種算法在仿真過程中最優(yōu)目標函數(shù)值變化曲線。改進的PSO算法采用動態(tài)變化的w能夠較精確地控制搜索速度，使每次搜索的速度跟隨迭代的次數(shù)進行變化，擺脫了傳統(tǒng)PSO中搜索速度更新的盲目性。測試結(jié)果表明，改進的PSO算法能在不同程度上加快收斂速度提高搜索精度，同時有利于函數(shù)脫局部最優(yōu)值，使函數(shù)最終收索到全局最優(yōu)值。

4 結(jié)束語

本文提出的一種改進的動態(tài)權(quán)值自適應(yīng)PSO 算法，該算法主要針對慣性因子、認知因子和社會因子的改進，改進的控制算法在尋優(yōu)過程中全局開發(fā)與局部開發(fā)進行了合理搭配，在更新的初期階段w算子的作用較大，有利于發(fā)現(xiàn)目標區(qū)域。隨著迭代次數(shù)的增加，w和c1作用幅值逐漸減小，c2幅值逐漸增大，有利于在最優(yōu)值附近進行局部開發(fā)，體現(xiàn)了全局探索與局部搜索搭配的合理性，典型函數(shù)目標優(yōu)化的實驗結(jié)果證明改進方法的優(yōu)越性。從仿真結(jié)果可以看出，改進后的PSO在收斂速度上和搜索精度上，均高于傳統(tǒng)粒子群算法與模擬退化算法。通過動態(tài)自適應(yīng)調(diào)整種群使群體搜索時不斷取向目標值，仿真結(jié)果表明，改進動態(tài)權(quán)值粒子群算法是有效、可行的。