一種基于進(jìn)化的自適應(yīng)卡爾曼修正粒子群優(yōu)化算法

侯 森 李才發(fā)

（1.中國人民解放軍信息工程大學(xué)，河南 鄭州450002；2.中國人民解放軍75842部隊(duì)，廣東 廣州510880）

1.引言

粒 子 群 優(yōu) 化 算 法 （Particle Swarm Optimization，PSO）是一種基于群體智能理論的全局優(yōu)化算法，粒子群中的粒子代表著優(yōu)化問題的可能解，每個(gè)粒子根據(jù)它自身存儲(chǔ)的歷史最優(yōu)點(diǎn)和它鄰居粒子記錄的歷史最優(yōu)點(diǎn)來調(diào)整自己的運(yùn)動(dòng)速率和方向“飛”向全局最優(yōu)解[1，2]。近年來，國內(nèi)外學(xué)者進(jìn)行了大量的粒子群優(yōu)化算法相關(guān)研究，這些研究工作主要集中在兩個(gè)方向上：一是改進(jìn)粒子速率的更新方式，從而提高算法的收斂速度或者保持粒子群的多樣性。如文獻(xiàn)[3]中引入了慣性權(quán)重，文獻(xiàn)[4]中提出了基于動(dòng)態(tài)速率的算法。二是研究不同的樣本，選擇學(xué)習(xí)策略，從而使粒子能夠快速收斂到接近最優(yōu)解的區(qū)域內(nèi)。這一類典型的方法包括廣義自適應(yīng)粒子群法[5]，基于異構(gòu)分簇的粒子群優(yōu)化算法[6]等。

大量的研究工作極大地豐富了粒子群算法的應(yīng)用領(lǐng)域。但是這些研究工作大都是專注于提升粒子群算法某一方面的性能，目前仍然缺乏能夠在各個(gè)領(lǐng)域普遍適用的算法。此外，粒子群算法因其可能出現(xiàn)早熟收斂,所以容易陷入局部最優(yōu)點(diǎn)。改進(jìn)PSO的關(guān)鍵在于如何選擇合適的收斂速度，過快的收斂速度容易導(dǎo)致算法陷入局部最優(yōu)點(diǎn)，而過慢的收斂速度又將極大地影響算法的效率。

本文從種群粒子位置更新過程的相關(guān)性角度出發(fā)，提出了一種基于進(jìn)化的自適應(yīng)卡爾曼修正粒子群優(yōu)化算法。該算法在每次迭代過程中根據(jù)卡爾曼濾波修正機(jī)制調(diào)整算法最優(yōu)點(diǎn)的位置，提升算法在搜索空間中的搜索效率和收斂速度。同時(shí)作者使用了一種基于子梯度計(jì)算的方法自適應(yīng)地調(diào)整算法的系數(shù)，從而提高算法的收斂率。此外，為了克服早熟收斂，作者采取了基于自然選擇的達(dá)爾文進(jìn)化機(jī)制，通過多個(gè)子群的自然進(jìn)化，增強(qiáng)粒子群的多樣性，從而使算法免于陷入局部最優(yōu)點(diǎn)。

2.粒子群優(yōu)化算法(PSO)

2.1 PSO的基本形式

每個(gè)粒子的速度和位置更新策略分別為：

2.2 改進(jìn)PSO算法

由于算法的簡潔和高效，PSO自被提出以來就受到了眾多學(xué)者的關(guān)注和研究。近年來國內(nèi)外學(xué)者提出了許多PSO改進(jìn)算法，其中比較有代表性的研究有：Clerc and Kennedy引入了慣性權(quán)重ω來控制粒子的運(yùn)動(dòng)速率[3]，它通過前一狀態(tài)速率的加權(quán)乘積來防止當(dāng)前速率過度激增，并將速度更新公式改寫成了如下形式：

慣性權(quán)重ω對(duì)于算法的收斂非常重要，慣性權(quán)重既可以是靜態(tài)的，也可以采用動(dòng)態(tài)的。在算法初期搜索階段，粒子被賦予較大的速度有助于提高搜索效率加快收斂；在算法后期收斂階段，粒子被賦予較小的速度則能夠避免陷入局部最優(yōu)點(diǎn)。文獻(xiàn)[7]采取了一種非線性的慣性權(quán)重方式：

其中ω1和ω2分別代表慣性權(quán)重的初始值和最終值。慣性權(quán)重在初始階段具有較大的值，隨著迭代次數(shù)k的增加慣性權(quán)重快速減小，從而使得慣性權(quán)重在算法不同的階段發(fā)揮不同的作用。公式（4）所定義的慣性權(quán)重能夠較好地改善算法性能，但是這種形式的慣性權(quán)重并不能模擬所有優(yōu)化問題的情況，例如對(duì)于多峰類型的優(yōu)化函數(shù)，這種形式的慣性權(quán)重就不能很好地發(fā)揮作用。

3.基于進(jìn)化的自適應(yīng)卡爾曼修正粒子群算法

目前，絕大多數(shù)的PSO改進(jìn)算法都是基于速度更新公式的改進(jìn)，通過控制慣性權(quán)重或者加速系數(shù)等方式使得PSO算法在不同階段具有不同的變化趨勢(shì)，從而實(shí)現(xiàn)快速收斂和避免陷入局部極值點(diǎn)。然而基于位置更新公式的改進(jìn)尚未有人嘗試，位置更新公式同樣提供給我們了許多信息，位置的變化趨勢(shì)更多地體現(xiàn)了種群的相關(guān)特性，因而將有助于算法的快速收斂。本文提出了一種基于進(jìn)化的自適應(yīng)卡爾曼修正粒子群優(yōu)化算法。該算法在每次迭代過程中根據(jù)卡爾曼濾波修正機(jī)制調(diào)整算法最優(yōu)點(diǎn)的位置，這樣的調(diào)整能夠顯著地提升算法在搜索空間中的搜索效率和收斂速度。同時(shí)作者使用了一種基于子梯度計(jì)算的方法來自適應(yīng)地調(diào)整算法的系數(shù)，以此來實(shí)現(xiàn)提高算法收斂率。此外，為了克服早熟收斂，作者采取了基于自然選擇的達(dá)爾文進(jìn)化機(jī)制，通過多個(gè)子群的自然進(jìn)化，避免使算法陷入局部極值點(diǎn)。

3.1 卡爾曼修正機(jī)制(Kalman Correction)

粒子群算法在對(duì)種群中每個(gè)粒子的位置進(jìn)行迭代更新后，會(huì)計(jì)算它們的適應(yīng)度，然后通過適應(yīng)度的數(shù)值判斷粒子的優(yōu)劣。如果粒子當(dāng)前位置的適應(yīng)度好于歷史全局最優(yōu)點(diǎn)，則新的位置代替原來的全局最優(yōu)點(diǎn)。這種簡單比較的方式雖然有效，但是并沒有充分考慮到全局最優(yōu)點(diǎn)更新過程中的相關(guān)性。由于群體智能的社會(huì)認(rèn)知特性，粒子群在向全局最優(yōu)點(diǎn)收斂過程中的運(yùn)動(dòng)并不是隨機(jī)的，因而我們可以利用其中的相關(guān)性來修正粒子群全局最優(yōu)點(diǎn)的更新過程。

本文采用一種類似非線性濾波的卡爾曼修正機(jī)制 (Kalman Correction)在每次位置更新后對(duì)全局最優(yōu)點(diǎn)進(jìn)行調(diào)整，從而提高算法搜索效率。假設(shè)粒子群的適應(yīng)度函數(shù)為。第k次迭代后，粒子i在位置的適應(yīng)度值如下：

經(jīng)過k次迭代后，粒子群中當(dāng)前位置適應(yīng)度最優(yōu)的點(diǎn)為xg，歷史全局最優(yōu)點(diǎn)位置為pg。我們定義兩者之間的估算誤差為。

通過上式所示卡爾曼修正機(jī)制，算法可以根據(jù)全局最優(yōu)點(diǎn)的歷次更新，擬合出近似最優(yōu)點(diǎn)的非線性更新軌跡。最優(yōu)點(diǎn)適應(yīng)度的觀察噪聲為零，而最優(yōu)點(diǎn)的激勵(lì)噪聲可以看做是零均值的協(xié)方差為Q的高斯白噪聲。假設(shè)我們給定噪聲協(xié)方差初始值，根據(jù)Sage-Husa自適應(yīng)算法[8]，噪聲統(tǒng)計(jì)特性的更新方程為：

其中d為權(quán)重系數(shù)。

我們?cè)诿看蔚笥?jì)算出修正的當(dāng)前最優(yōu)點(diǎn)，然后同種群歷史全局最優(yōu)點(diǎn)進(jìn)行適應(yīng)度的比較，如果修正后的當(dāng)前最優(yōu)點(diǎn)x_tempg(k)優(yōu)于歷史全局最優(yōu)點(diǎn) pg(k)，則用 x_tempg(k)代替 pg(k)。

3.2 基于子梯度的自適應(yīng)系數(shù)更新

雖然卡爾曼修正機(jī)制能夠有效地提升算法在解空間中的搜索速度，但是算法仍會(huì)受到慣性權(quán)重ω和加速系數(shù)的制約。根據(jù)PSO算法的原理，當(dāng)初始化階段算法從遠(yuǎn)離全局最優(yōu)點(diǎn)的任意位置開始搜索時(shí)，如果我們能夠給予粒子較大的速度則有利于算法快速收斂；當(dāng)粒子群逐漸匯聚到最優(yōu)點(diǎn)附近區(qū)域時(shí)，如果我們適度降低粒子的速度，則能夠避免粒子跳過最優(yōu)點(diǎn)，提高算法收斂率。因而我們考慮根據(jù)粒子到最優(yōu)點(diǎn)距離的不同，自適應(yīng)地調(diào)整算法的相關(guān)系數(shù)，賦予粒子不同的搜索速度，這樣將有效地提高我們算法的準(zhǔn)確性和收斂率。本文設(shè)計(jì)了一種基于子梯度的自適應(yīng)系數(shù)更新方案，根據(jù)粒子到最優(yōu)點(diǎn)的距離動(dòng)態(tài)地更新算法系數(shù)。

慣性權(quán)重ω以及加速系數(shù)c1、c2對(duì)PSO算法的性能非常重要，根據(jù)粒子到最優(yōu)點(diǎn)距離的不同我們可以賦予粒子不同的參數(shù)。當(dāng)粒子遠(yuǎn)離全局最優(yōu)點(diǎn)時(shí)，我們可以設(shè)置較大的參數(shù)，提高運(yùn)動(dòng)速度從而加快收斂；當(dāng)粒子越來越靠近全局最優(yōu)點(diǎn)的時(shí)候，我們可以選擇較小的參數(shù)，避免算法在最優(yōu)點(diǎn)附近震蕩，跳過最優(yōu)點(diǎn)。假設(shè)粒子i與全局最優(yōu)點(diǎn)的距離為Dig，優(yōu)化的目標(biāo)是選取合適的參數(shù)使得此距離最小。

受子梯度方法的啟發(fā)，我們用下列形式更新慣性權(quán)重ω以及加速系數(shù)c1、c2：

其中 αi是步幅，gwi(k)、gc1i(k)、gc2i(k)分別是慣性權(quán)重ω以及加速系數(shù)c1、c2在公式(8)中的子梯度。

根據(jù)Polyak步幅方程，步幅αi可以寫作：

通過公式(10)～(16)，我們可以根據(jù)粒子到最優(yōu)點(diǎn)的距離自適應(yīng)地調(diào)整粒子的參數(shù)。

3.3 基于自然選擇的達(dá)爾文進(jìn)化過程

通過采取上述卡爾曼修正和子梯度系數(shù)更新機(jī)制，雖然我們可以提高粒子群算法的搜索速度和收斂效率，但是算法仍然容易陷入局部最優(yōu)點(diǎn)。正如硬幣的雙面一樣，快速收斂和避免陷入局部最優(yōu)點(diǎn)是粒子群算法固有的悖論。提高搜索速度難免增加早熟收斂的可能性，已有的許多算法通過增加粒子群多樣性來調(diào)和兩者之間的矛盾。受文獻(xiàn)[7]的啟發(fā)，我們采取基于自然選擇的達(dá)爾文進(jìn)化機(jī)制提高算法的全局搜索能力。

首先，我們將整個(gè)粒子群劃分為無數(shù)個(gè)動(dòng)態(tài)子群，各子群通過獨(dú)立地繁殖、選擇和淘汰等自然操作，逐步向全局最優(yōu)進(jìn)化，通過搜索多樣性，能夠有效地避免陷入局部極值點(diǎn)。子群可以動(dòng)態(tài)的增長或者消亡。一個(gè)子群可以找到更好的適應(yīng)度值從而延長壽命，同時(shí)也可以增加新的粒子來加快搜索速度；在連續(xù)若干迭代步驟中，如果一個(gè)子群沒有得到更優(yōu)的適應(yīng)度值，那么將縮短它的壽命，并且刪除子群中性能較差的粒子，當(dāng)子群中的粒子數(shù)量減少到一定閾值時(shí)，該子群將被銷毀。

達(dá)爾文進(jìn)化機(jī)制為每個(gè)粒子群中設(shè)置一個(gè)搜索計(jì)數(shù)器SC，記錄適應(yīng)度值沒有變化的次數(shù)，如果SC超過最大門限SCcmax，則刪掉適應(yīng)度值最差的粒子。初始SC設(shè)置為0，每次刪除粒子后，SC值不復(fù)位，而是按照公式（17）重新設(shè)置。

3.4 基于達(dá)爾文進(jìn)化的自適應(yīng)卡爾曼修正粒子群算法

綜上所述，AKDPSO算法的實(shí)現(xiàn)步驟可概括如下。

（1）輸入：粒子群，粒子數(shù)N及空間維數(shù)D。

（2）輸出：全局最優(yōu)點(diǎn)pg與最佳適應(yīng)度值。

（3）初始化：設(shè)定最大迭代代數(shù)tmax搜索計(jì)數(shù)器最大門限SCcmax，粒子的初始位置xi(0)和初始速度pi(0)，粒子群初始最優(yōu)位置pg(0)，初始慣性權(quán)重 ω(0)以及加速系數(shù) c1(0)、c2(0)。

（4）劃分若干初始子群，估計(jì)每個(gè)粒子的適應(yīng)度，設(shè)置粒子當(dāng)前位置為其極值pi(0)，設(shè)置初始全局最佳粒子的位置為全局極值pg(0)。

（5）Repeat

for每個(gè)粒子群 do

for每個(gè)粒子 do

①根據(jù)式(13)-(15)更新系數(shù)子梯度：

根據(jù)式(10)-(12)自適應(yīng)更新慣性權(quán)重ω和加速系數(shù)：

②應(yīng)用式(2)與(3)實(shí)現(xiàn)粒子位置與速度的更新

③對(duì)狀態(tài)更新后的粒子適應(yīng)度值進(jìn)行評(píng)估，如果優(yōu)于當(dāng)前的自身最優(yōu)值，則將pi(k)設(shè)置為該粒子的位置，并且更新自身最優(yōu)值。

end for

④如果存在粒子的最優(yōu)值好于當(dāng)前全局最優(yōu)值，則將pg(k)設(shè)置為該粒子的位置，且更新全局最優(yōu)點(diǎn)。

⑤根據(jù)式(6)-(8)定義的卡爾曼修正機(jī)制調(diào)整全局最優(yōu)點(diǎn)的位置

如果修正的最優(yōu)點(diǎn)適應(yīng)度好于當(dāng)前記錄的全局最優(yōu)值，則用修正值更新全局最優(yōu)點(diǎn)。

⑥if粒子群的全局最優(yōu)點(diǎn)得到了改進(jìn) do

獎(jiǎng)勵(lì)粒子群：增加粒子；延長粒子群壽命

endif

elseif do

懲罰粒子群：縮短粒子群壽命；刪除計(jì)數(shù)器SC超過SCcmax的粒子。

endif end for

for每個(gè)粒子群 do

⑦如果粒子群壽命或者粒子群中粒子數(shù)量少于門限，刪除該粒子群，按照式(17)重置搜索計(jì)數(shù)器。

⑧如果粒子群中沒有粒子被刪除，并且粒子群數(shù)量不超過其最大數(shù)目N，則按概率衍生后代，產(chǎn)生新的子群。

end for

until當(dāng)達(dá)到最大迭代次數(shù)或者整個(gè)粒子群適應(yīng)度不再發(fā)生顯著變化，停止迭代。

return全局最優(yōu)點(diǎn)pg與最佳適應(yīng)度值。

上述算法能夠有效提高搜索速度和收斂率，同時(shí)繼承了達(dá)爾文進(jìn)化的優(yōu)點(diǎn)，降低了粒子群陷入局部極值的可能。

4.實(shí)驗(yàn)與分析

4.1 測試函數(shù)與算法配置

我們選取了六個(gè)典型函數(shù)來測試AK-DPSO算法的性能，它們的表達(dá)式如下表所示。

表1 六個(gè)典型函數(shù)

其中f*為全局極值。同時(shí)我們選取PSO、HPSO、DPSO、APSO、FO-PSO 五種算法與本文提出的AK-DPSO算法進(jìn)行比較，將上述6個(gè)函數(shù)表達(dá)式作為適應(yīng)度函數(shù)。各PSO算法的初始參數(shù)設(shè)置如表2所示，其中粒子數(shù)N=50，空間維數(shù)D為20，最大迭代次數(shù) tmax=1000。

表2 各PSO算法的參數(shù)設(shè)置

4.2 搜索精度比較

為了減少統(tǒng)計(jì)誤差，對(duì)每個(gè)函數(shù)進(jìn)行了30次測試，然后取其平均值進(jìn)行比較。通過表3可以看出，無論是在單峰函數(shù) f1、f2、f3上，還是在多峰函數(shù)f4、f5、f6上，基于進(jìn)化的自適應(yīng)卡爾曼修正粒子群優(yōu)化算法的測試結(jié)果均要好于現(xiàn)有的PSO及其優(yōu)化算法。

表3 不同粒子群優(yōu)化算法對(duì)6個(gè)測試函數(shù)的搜索結(jié)果比較

4.3 算法穩(wěn)定性能比較

我們用最優(yōu)解方差函數(shù)來評(píng)價(jià)算法的穩(wěn)定性，定義如下：

當(dāng)∣fi-favg∣＞1 時(shí)，fmax取值為 max(∣fi-favg∣)，否則取1。如表4所示，AK-DPSO算法的最優(yōu)值方差小于其他五種算法，因此AK-DPSO算法搜索到的最優(yōu)解最穩(wěn)定。

表4 測試函數(shù)的最優(yōu)值方差比較

4.4 收斂速度比較

圖 1(a)～(f)為 APSO、HPSO、DPSO 與本文提出AK-DPSO算法對(duì)典型測試函數(shù)優(yōu)化過程中，種群收斂性能的對(duì)比。圖1中的縱坐標(biāo)表示適應(yīng)度的對(duì)數(shù)值，橫坐標(biāo)為迭代次數(shù)。

通過上圖可以看出，本文提出的AK-DPSO算法比APSO、HPSO和DPSO算法收斂速度更快，并且能夠跳出局部最優(yōu)值，從而提升了算法的全局搜索能力，有效地避免了早熟收斂問題。

綜上所述，與現(xiàn)有的幾種PSO算法相比較，AK-DPSO算法收斂速度、穩(wěn)定性以及搜索精度都得到了明顯提高，展示出更令人滿意的整體優(yōu)化性能。

4.5 算法的計(jì)算復(fù)雜度分析

作者對(duì)比了AK-DPSO算法和上文五種對(duì)比算法在1000次迭代次數(shù)內(nèi)對(duì)上文六個(gè)函數(shù)的平均計(jì)算時(shí)間，以比較幾種算法的復(fù)雜度。同時(shí)作者還比較了粒子群規(guī)模與算法復(fù)雜度的關(guān)系，實(shí)驗(yàn)結(jié)果如圖2所示。

AK-DPSO算法復(fù)雜度略高于其他算法，其主要原因是AK-DPSO算法由于使用了粒子的位置和速度參數(shù)進(jìn)行動(dòng)態(tài)調(diào)整，粒子每次迭代都將增加O(2(N-1)D+N)的計(jì)算復(fù)雜度。AK-DPSO增加了計(jì)算復(fù)雜度，但是獲得了較高的搜索精度、較快的收斂速度和較好的穩(wěn)定性。

5.結(jié)論

為了避免陷入局部極值點(diǎn)和快速收斂，本文從種群粒子位置更新過程的相關(guān)性角度出發(fā)，提出了一種基于進(jìn)化的自適應(yīng)卡爾曼修正粒子群優(yōu)化算法，在此基礎(chǔ)上給出了AK-DPSO算法。該算法在每次迭代過程中根據(jù)卡爾曼濾波修正機(jī)制調(diào)整算法最優(yōu)點(diǎn)的位置，提升算法在搜索空間中的搜索效率和收斂速度；同時(shí)作者使用了一種基于子梯度計(jì)算方法自適應(yīng)地調(diào)整算法的系數(shù)，采取了基于自然選擇的達(dá)爾文進(jìn)化機(jī)制，避免使算法陷入局部極值點(diǎn)。相比于現(xiàn)有的主要粒子群優(yōu)化算法，本文的AK-DPSO算法的搜索精度、收斂速度和穩(wěn)定性都有了顯著提高，全局尋優(yōu)能力得到了極大提升。