基于慣性權(quán)重和學(xué)習(xí)因子動態(tài)調(diào)整的粒子群算法

吳永紅，曾志高，鄧 彬

（湖南工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，湖南 株洲 412007）

0 引言

粒子群算法是一種經(jīng)典的元啟發(fā)式算法[1]，該算法由C.Reynolds 于1987 年對鳥類覓食行為進(jìn)行模擬研究時得出，他提出如下模擬鳥群個體簡單行為的3個規(guī)則：

1）防止鳥群發(fā)生碰撞，即減少與其他粒子產(chǎn)生碰撞；

2）鳥群個體保持速度相近，即速度與鄰近粒子盡可能相近；

3）鳥群個體朝中心靠攏，即朝粒子群中心盡可能聚攏。

其后，J.Kennedy 等基于C.Reynolds 的研究結(jié)論，在1995 年經(jīng)過進(jìn)一步研究提出了一種粒子群優(yōu)化（particle swarm optimization，PSO）算法。該算法對之前的算法進(jìn)行了參數(shù)簡化，算法原理更為簡單，易于實(shí)現(xiàn)[2]，因此得到許多研究人員的關(guān)注，并且被應(yīng)用于處理各種優(yōu)化問題。例如：張鑫等[3]提出了一種自適應(yīng)簡化粒子群優(yōu)化算法，按照一定規(guī)律引入分布的鎖定因子，從而粒子位置的慣性權(quán)重可以通過鎖定因子自適應(yīng)配置，導(dǎo)致算法收斂速度得到了有效提高，但是仍然存在魯棒性較弱、收斂精度較低等缺陷；王永貴等[4]為了增加種群的多樣性，在算法中引入了動態(tài)分裂算子，以此避免陷入局部最優(yōu)解，然后通過采用指數(shù)衰減的慣性權(quán)重，平衡粒子的局部以及全局的搜索；杜美君等[5]提出了一種基于相似度動態(tài)調(diào)整慣性權(quán)重的方法，它將更小的慣性權(quán)重值賦予靠近目前最優(yōu)粒子的個體，但是算法收斂速度較慢，當(dāng)處理復(fù)雜函數(shù)問題時，耗時較長。PSO 算法也存在很多的局限，在迭代時粒子群體多樣性不斷降低，導(dǎo)致算法容易陷入局部最優(yōu)解、收斂速度后期變慢或者出現(xiàn)早熟收斂等問題。上述研究者的改進(jìn)算法對增強(qiáng)種群多樣性有很大幫助，同時有助于平衡算法局部搜索能力與全局搜索能力，在一定程度上提高了PSO 算法的尋優(yōu)精度，也加快了算法的收斂速度。

以上各算法主要針對粒子群算法在迭代過程中種群多樣性降低、收斂速度較慢和尋優(yōu)精度較低等問題[6-10]而提出改進(jìn)方案，但是沒有對算法的慣性權(quán)重和學(xué)習(xí)因子進(jìn)行動態(tài)調(diào)整，有可能導(dǎo)致算法出現(xiàn)早熟收斂現(xiàn)象。針對這一問題，本文提出一種自適應(yīng)的調(diào)整慣性權(quán)重和學(xué)習(xí)因子的粒子群算法，利用慣性權(quán)重和學(xué)習(xí)因子的動態(tài)改進(jìn)調(diào)整，以期提高算法的性能。對比實(shí)驗(yàn)結(jié)果顯示，改進(jìn)算法具有較強(qiáng)的尋優(yōu)能力和收斂性。

1 基本粒子群算法

在粒子群優(yōu)化算法中，所有粒子組成一個種群，每個個體可以被看作一個具有位置和速度的粒子，待求解問題的候選解用粒子位置表示。種群開始初始化，且各粒子被隨機(jī)給予一個位置和速度，不同個體分別代表不同的隨機(jī)解，在不斷迭代后最終得到粒子最優(yōu)解。隨著粒子位置與速度的不斷更新，局部最優(yōu)解和全局最優(yōu)解隨之更新。在迭代期間，各個粒子用跟蹤個體極值與全局極值的方式完成更新。pbest(i, t)表示到第i 個粒子第t 次迭代期間所發(fā)現(xiàn)的粒子最優(yōu)位置，pbest則表示群體迄今為止所發(fā)現(xiàn)的最優(yōu)位置，分別用式（1）與式（2）來表示粒子更新后的速度和位置。

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

式中：w 表示慣性權(quán)重；

vi(t+1)代表第i 個粒子當(dāng)前迭代速度；

xi(t)為第i 個粒子的位置；

r1、r2為介于[0, 1]區(qū)間內(nèi)的隨機(jī)數(shù)；

c1、c2為非負(fù)的學(xué)習(xí)因子。

慣性權(quán)重是重要的進(jìn)化參數(shù)，它決定的是粒子先前飛行速度對當(dāng)前飛行速度的影響程度。當(dāng)慣性權(quán)重較小時，整體的局部搜索能力較強(qiáng)，全局搜索能力較弱；慣性權(quán)重較大時，整體的局部搜索能力較弱，全局搜索能力較強(qiáng)。因而，為優(yōu)化算法尋優(yōu)能力與算法性能，并平衡粒子的局部搜索與全局搜索能力，采用調(diào)整慣性權(quán)重值的方式來完成。算法在搜索速度與搜索精度上能否適當(dāng)平衡，取決于能否找到適當(dāng)?shù)膽T性權(quán)重值，這也成為業(yè)內(nèi)學(xué)者們的一個重要研究方向。

基本粒子群算法仍然有很多缺陷，如算法經(jīng)常產(chǎn)生早熟收斂現(xiàn)象，環(huán)境的變化會影響算法性能，經(jīng)常會受到全局極值和個體極值的影響而陷入局部最優(yōu)等。針對以上問題，本文對算法的慣性權(quán)重和學(xué)習(xí)因子進(jìn)行了動態(tài)改進(jìn)調(diào)整，以提升算法的尋優(yōu)能力和收斂性。

2 改進(jìn)的粒子群算法

粒子群算法的速度迭代公式中有如下3 個重要參數(shù)：慣性權(quán)重w 和學(xué)習(xí)因子c1、c2。慣性權(quán)重w 影響著粒子先前的飛行速度對于當(dāng)前的飛行速度的影響程度，慣性權(quán)重的選取對于平衡算法的全局搜索能力和局部搜索能力有著重要意義。在迭代過程中，要考慮算法的全局性和局部性，要采取合適的慣性權(quán)重來進(jìn)行搜索。本文利用改進(jìn)后的冪指函數(shù)算子，將其加入到慣性權(quán)重中，以總的迭代次數(shù)為基礎(chǔ)，在搜索時讓每個粒子擴(kuò)大搜索空間，以此增大種群多樣性。因此，本文采用改進(jìn)慣性權(quán)重值的策略。對比實(shí)驗(yàn)結(jié)果表明，動態(tài)調(diào)整后的慣性權(quán)重能提高算法搜索性能，有效改善收斂狀況，隨著算法不斷迭代，慣性權(quán)重值動態(tài)改變，表達(dá)式為

式中：g 為當(dāng)前迭代次數(shù)；

a、b、d 為參數(shù)；

gmax為迭代次數(shù)的最大值。

作為算法運(yùn)行中的重要式子，c1是粒子具有自我學(xué)習(xí)總結(jié)能力的體現(xiàn)，代表的是個體自我認(rèn)知；學(xué)習(xí)因子c2是粒子具有向表現(xiàn)更好的粒子學(xué)習(xí)的本領(lǐng)體現(xiàn)，代表的是粒子的社會認(rèn)知。需要設(shè)置恰當(dāng)?shù)腸1、c2以便于粒子進(jìn)行搜尋。初期要關(guān)注個體自我認(rèn)識的能力，后期則應(yīng)注重個體獲取社會信息的能力。本文設(shè)置如下學(xué)習(xí)因子：

式（4）（5）中e1、e2、f1、f2為參數(shù)。

改進(jìn)后新的粒子速度和位置迭代公式跟原始算法相同。

與基本粒子群算法相比較，對基于慣性權(quán)重和學(xué)習(xí)因子動態(tài)調(diào)整的粒子群算法的速度公式作出調(diào)整時，實(shí)現(xiàn)了算法隨著迭代次數(shù)變化而動態(tài)變化，其全局搜索能力有效提高，粒子的收斂性也得到了加強(qiáng)。然而，當(dāng)遇到一些復(fù)雜的多峰值函數(shù)曲線的尋優(yōu)問題時，基于慣性權(quán)重和學(xué)習(xí)因子動態(tài)調(diào)整的粒子群算法，依然存在許多問題，收斂速度以及精度仍達(dá)不到要求等。如當(dāng)受到局部陰影的作用時，光伏陣列的輸出曲線將會變得錯綜變幻，由于多峰值的產(chǎn)生，大大增加了整體尋優(yōu)的難度，也可能使基本粒子群算法和改進(jìn)粒子群算法顯示早熟跡象，而導(dǎo)致產(chǎn)生局部極值。

2.1 改進(jìn)的粒子群算法流程

基于慣性權(quán)重和學(xué)習(xí)因子動態(tài)調(diào)整的粒子群算法的步驟具體描述如下：

Step 1 對粒子群初始化，產(chǎn)生各個粒子的位置和速度，并進(jìn)行子種群劃分，最大迭代次數(shù)gmax，種群規(guī)模Spop等。

Step 2 設(shè)置模型，初始化后存放粒子的速度、位置和適應(yīng)度值，然后在種群中挑選出具有最佳適應(yīng)度值以及對應(yīng)最佳位置的粒子。

Step 3 更新慣性權(quán)重w 與學(xué)習(xí)因子c1、c2。

Step 4 對各個粒子分別評價，并更新粒子的位置、速度。

Step 5 隨著粒子位置不斷更新，分別計(jì)算粒子的適應(yīng)度值，找出每個粒子所能得到的個體最優(yōu)值pbest，當(dāng)每找到一個新的pbest 時，再與之前的最優(yōu)值進(jìn)行比較，將更優(yōu)值更新為全局最優(yōu)值pbest，經(jīng)過粒子的不斷更新迭代，最終更新得到全局最優(yōu)解pbest。

Step 6 判斷算法能否達(dá)到終止標(biāo)準(zhǔn)，若達(dá)到，則輸出最優(yōu)值；若沒達(dá)到，則返回步驟3。

2.2 流程圖

根據(jù)上述改進(jìn)粒子群算法的流程，繪制如圖1 所示流程圖。

圖1 改進(jìn)粒子群算法的流程圖Fig.1 Flow chart of the improved particle swarm optimization

3 實(shí)驗(yàn)和分析

為了驗(yàn)證本研究中所提出的改進(jìn)的粒子群算法是否有效可行， 實(shí)驗(yàn)組使用了6 個典型測試函數(shù)來進(jìn)行測試，并且與基本粒子群算法進(jìn)行比較。仿真實(shí)驗(yàn)的運(yùn)行環(huán)境為Matlab2016a， 64 位 Windows10的操作系統(tǒng)，硬件參數(shù)為 Intel(R) Core(TM) i5-4300U CPU @ 1.09GHz 處理器、內(nèi)存是為 GB。定義6 個測試函數(shù)如下：

函數(shù)在（0, 0）處存在唯一極大值，且在周圍分布著許多局部極值。

函數(shù)在（0, 0）處取得極大值0。

函數(shù)在（0, 0）處取得極小值0。

函數(shù)在（0, 0）處存在最小值 0。

函數(shù)在（1, 3）處取得極小值0。

函數(shù)在（0, 0）處有極小值0。

設(shè)置基本粒子群算法的運(yùn)行參數(shù)如下：c1取值為1.5，c2取值為1.7，種群規(guī)模Spop取值為20，種群維數(shù)為10，實(shí)驗(yàn)共運(yùn)行20 次，每次運(yùn)行迭代500 次，求其平均值。設(shè)置的改進(jìn)粒子群算法的參數(shù)基本粒子群算法的相同。

4 實(shí)驗(yàn)結(jié)果及分析

4.1 測試結(jié)果

為了對改進(jìn)的粒子群算法的尋優(yōu)效果進(jìn)行測試，對基本粒子群算法和改進(jìn)粒子群算法各運(yùn)行20 次，得到各自的平均值，所得測試結(jié)果如表1 所示，表中IPSO 代表改進(jìn)的粒子群算法。其中，最優(yōu)值是得到的所有解值集合中最好的值，最差值是得到的所有解值集合中最差的值，最優(yōu)點(diǎn)為20 次最優(yōu)值位置的平均值。由表1 可知，除了函數(shù)f5以外，IPSO 均找到了最優(yōu)值；所有測試值中，改進(jìn)粒子群算法的標(biāo)準(zhǔn)差更小，優(yōu)化結(jié)果比基本算法更優(yōu)。

表1 兩種算法的結(jié)果比較Table 1 Comparison of the results of the two algorithms

4.2 函數(shù)的收斂曲線

基本算法和改進(jìn)算法的收斂曲線如圖2 所示。

圖2 基本粒子群算法與改進(jìn)粒子群算法在不同函數(shù)下的收斂曲線Fig.2 Comparison of convergence curves between the standard and improved particle swarm optimization algorithms under different functions

由圖2 中各個函數(shù)的收斂曲線可以得知，隨著迭代次數(shù)的增加，粒子群逐漸向最優(yōu)值聚集，改進(jìn)算法得到的收斂曲線比基本算法得到的收斂曲線更快接近水平方向，說明改進(jìn)的算法收斂速度增強(qiáng)，改進(jìn)的PSO 算法的收斂性更好。

5 結(jié)語

針對粒子群算法收斂性不太好、在尋優(yōu)過程中易陷入局部極值等問題，提出了一種基于慣性權(quán)重和學(xué)習(xí)因子動態(tài)調(diào)整的粒子群算法，由運(yùn)行對比實(shí)驗(yàn)結(jié)果可得，改進(jìn)的粒子群算法的收斂性有效提高，性能比基本粒子群算法更優(yōu)。以后的研究方向?qū)帽疚母倪M(jìn)的粒子群算法去優(yōu)化支持向量機(jī)參數(shù)，使支持向量機(jī)的求解更加高效。