基于動態(tài)變化自適應(yīng)慣性權(quán)重混沌粒子群算法

王 翠，姜學(xué)軍

(沈陽理工大學(xué)信息科學(xué)與工程學(xué)院，沈陽 110159)

標(biāo)準(zhǔn)粒子群優(yōu)化算法(Standard Particle Swarm Optimization，SPSO)是一種群智能優(yōu)化算法[1]，與蟻群算法、群搜索算法、人工蜂群算法、螢火蟲算法等類似，均為元啟發(fā)式優(yōu)化算法。 SPSO算法具有易于實現(xiàn)、收斂精度高、收斂速度快等優(yōu)點，被廣泛應(yīng)用于各種優(yōu)化問題的求解，如軟件工程領(lǐng)域的風(fēng)險因素優(yōu)先級劃分和軟件工作量估計、工程優(yōu)化應(yīng)用中對最大功率點的跟蹤控制[2]。SPSO 算法也與其他全局優(yōu)化算法存在相同的缺點，即在局部的搜索能力較差，容易陷入最優(yōu)值而失去搜索多樣性。

為克服以上兩個缺點，相關(guān)研究提出了一些改進(jìn)方法。 一是對SPSO 算法中慣性權(quán)重進(jìn)行調(diào)整。 文獻(xiàn)[3]中提出了新的非線性慣性權(quán)重函數(shù)，同時將柯西變異算子與非線性動態(tài)遞減權(quán)值策略相結(jié)合，以達(dá)到算法跳出局部最優(yōu)的目的；文獻(xiàn)[4]中通過利用粒子速度信息、最優(yōu)性能評價值、多樣性等指標(biāo)，在算法運(yùn)行中動態(tài)調(diào)整慣性權(quán)重和學(xué)習(xí)因子。 二是將SPSO 算法與其他優(yōu)化算法(模擬退火算法、遺傳算法等)相結(jié)合。 文獻(xiàn)[5]中將粒子群算法與螢火蟲算法相結(jié)合處理機(jī)械加工參數(shù)的優(yōu)化問題。 三是改變粒子位置的更新規(guī)則。文獻(xiàn)[6]改變了粒子之間信息交流機(jī)制，引入了自適應(yīng)選擇機(jī)制，從而擴(kuò)大粒子的搜索空間，使粒子在合適的時刻自動選擇合適的學(xué)習(xí)目標(biāo)；文獻(xiàn)[7]通過周期性變異操作改變個體的歷史最優(yōu)值和全局最優(yōu)值，以達(dá)到改變粒子運(yùn)動方向的目的。

上述針對SPSO 改進(jìn)之后的算法性能在一定程度上有所提高，但仍有陷入局部最優(yōu)的可能，無法從根本上徹底解決早熟收斂問題。 為此，提出一種綜合改進(jìn)的基于慣性權(quán)重動態(tài)變化的混沌粒子群優(yōu)化算法，充分利用混沌運(yùn)動的遍歷性與隨機(jī)性生成粒子的初始種群[8]，并根據(jù)迭代狀態(tài)動態(tài)調(diào)整慣性權(quán)重的值。 該算法在處理復(fù)雜的多極值問題時，收斂速度明顯提高，并能在求得較高精度解的同時有效避免早熟問題。

1 SPSO 算法

SPSO 算法的基本思想如下。

設(shè)在一個D維的搜索空間中，有一個規(guī)模為N的種群，將種群中個體抽象成沒有質(zhì)量和體積、只有速度和位置的粒子，粒子速度隨粒子找到的自身最優(yōu)位置和整個群體找到的最優(yōu)位置而進(jìn)行調(diào)整，直至找到最優(yōu)解[9]。 所有粒子通過迭代在搜索空間追蹤兩個極值：個體極值和全局極值，并根據(jù)兩個極值對個體的速度和位置進(jìn)行更新，從而尋求最優(yōu)解。 其中個體極值為粒子個體找到的最優(yōu)位置，全局極值為粒子群體找到的最優(yōu)位置。根據(jù)一定的迭代進(jìn)化規(guī)則，第i個粒子從第t代更新到第t＋1 代時，在d(d＝1，2，…，D)維子空間中的速度vid和位置xid的更新公式為

式中各參數(shù)說明如下：

(1)ω為慣性權(quán)重因子(粒子速度系數(shù))；

(2)c1 為加速因子，在個體搜索歷史中粒子所搜尋到的最佳值的權(quán)重系數(shù)，通常取值在0 ～2之間；

(3)c2 為加速因子，在群體搜索歷史中粒子所搜尋到的最佳值的權(quán)重系數(shù)，通常取值在0 ～2之間；

(4)randdata1、randdata2 為兩個彼此相對獨立的隨機(jī)數(shù)，且在[0，1]區(qū)間上均勻分布；

(5)gbest(t)為歷史個體極值；

(6)zbest(t)為歷史全局極值；

(7)r為約束因子，在更新粒子位置時，為粒子速度的系數(shù)，通常取值為1。

該算法結(jié)構(gòu)簡單，運(yùn)行速度快，但當(dāng)某一粒子發(fā)現(xiàn)當(dāng)前最優(yōu)位置后，如果該位置恰好為局部最優(yōu)，則粒子會迅速向其靠近，從而失去搜索多樣性，無法在解空間內(nèi)重新搜索，即陷入局部最優(yōu)，導(dǎo)致算法出現(xiàn)早熟收斂現(xiàn)象。

2 自適應(yīng)慣性權(quán)重混沌SPSO 算法

2.1 混沌SPSO 算法

混沌SPSO 算法是在SPSO 算法的基礎(chǔ)上加入混沌運(yùn)動思想，充分發(fā)揮混沌運(yùn)動的隨機(jī)性、遍歷性以及規(guī)律性等優(yōu)勢。

算法首先對當(dāng)前種群的最優(yōu)粒子進(jìn)行混沌尋優(yōu)操作，然后通過迭代過程，用尋優(yōu)的結(jié)果隨機(jī)替換群體中的某一個粒子，如此反復(fù)直至找到最優(yōu)解，加快粒子群體的進(jìn)化速度，從而改善SPSO 算法擺脫局部極值點的能力[10]，并在一定程度上提高了算法的收斂速度和精度。

2.2 不同序列的混沌特性比較

本文采用混沌思想對粒子進(jìn)行迭代尋優(yōu)。 首先選取常用的六種混沌映射函數(shù)：Logistic、Tent、Cubic、Singe、Gaussian、Circle，通過Matlab 進(jìn)行仿真實驗，并完成混沌序列分布圖的分析。 六種混沌映射所產(chǎn)生的序列分布圖如圖1所示。

圖1 六種混沌映射的序列分布圖

圖1中橫坐標(biāo)表示映射區(qū)間，除Cubic 的映射區(qū)間為[ -1，1]外，其他混沌函數(shù)的映射區(qū)間均為[0，1]；縱坐標(biāo)表示落在相應(yīng)區(qū)間內(nèi)點的個數(shù)。

從圖1中可以看出，Logistic 和Cubic 的均勻性要好于其他四種混沌映射，雖然Logistic 和Cubic 兩種映射產(chǎn)生的序列都具有混沌特性，但均勻性有所不同，當(dāng)兩個映射區(qū)間都均分為十等份時，Cubic 映射落在[ -1，-0.8]區(qū)間的點有197 個，而Logistic 產(chǎn)生的混沌序列落在[0，0.1]內(nèi)的點有235 個，由此可見，Logistic 映射落在[0，0.1]區(qū)間的點較多，均勻性不如Cubic 映射落在[ -1，-0.8]內(nèi)的情況。 故本文選取Cubic 映射產(chǎn)生混沌序列。

2.3 動態(tài)變化的自適應(yīng)慣性權(quán)重

慣性權(quán)重因子影響SPSO 算法性能，其值較大時有利于全局范圍的搜索，較小的權(quán)重值有利于加快算法的收斂速度，對于局部的細(xì)致開發(fā)益處較大[11]。 在SPSO 算法中，ω為固定值時，迭代初期算法收斂速度較快，后期粒子更新能力差、易陷入局部最優(yōu)的缺陷。 改進(jìn)SPSO 算法的研究中，常常對ω進(jìn)行動態(tài)調(diào)整以提高算法的計算效率。 較為常見的是線性權(quán)重遞減策略，該方法使算法的早期速度較快，后期ω線性遞減至一個較小值，導(dǎo)致粒子的更新能力不夠，且實際的尋優(yōu)過程是非線性的，單純地線性降低慣性權(quán)重的值不能有效改善算法的尋優(yōu)能力。

本文通過對種群粒子在迭代過程中的最大適應(yīng)度值和最小適應(yīng)度值的指數(shù)變換動態(tài)調(diào)整慣性權(quán)重的值，同時引入隨機(jī)因子h增加取值的隨機(jī)性，該策略用公式描述如下。

式中各參數(shù)說明如下：

(1)fitnessgmax為當(dāng)前迭代代數(shù)下種群個體的最大適應(yīng)度值；

(2)fitnessgmin為當(dāng)前迭代代數(shù)下種群個體的最小適應(yīng)度值；

(3)h為隨機(jī)因子，[0，1]之間的隨機(jī)數(shù)；

(4)maxgen為最大迭代次數(shù)；

(5)b為慣性權(quán)重受最大適應(yīng)度的影響程度，服從[0，1]間的均勻分布。

綜合考慮種群粒子適應(yīng)度和隨機(jī)分布，提出一種綜合改進(jìn)算法，其具體流程如下。

步驟1：初始化參數(shù)，確定種群規(guī)模N＝20，進(jìn)化最大迭代次數(shù)maxgen＝1000，加速因子c1 ＝c2 ＝1.49445，ω的初始值設(shè)為0.6，h隨機(jī)選取區(qū)間為[0，1]。

步驟2：隨機(jī)產(chǎn)生一個D維向量，該向量為第1 個粒子，初始化粒子速度。

步驟3：通過使用測試函數(shù)，計算粒子適應(yīng)度值，找到最大適應(yīng)度值和最小適應(yīng)度值。

步驟4：根據(jù)式(3)、式(4)計算新的ω值。

步驟5：將新的ω值帶入式(1)、式(2)，更新粒子的速度和位置。

步驟6：計算更新后粒子的適應(yīng)度值，更新gbest和zbest，再次獲取fitnessgmax和fitnessg-min，并對ω進(jìn)行動態(tài)非線性更新。

步驟7：如未超出預(yù)先設(shè)定的最大迭代次數(shù)，則轉(zhuǎn)向步驟4 繼續(xù)搜索，否則執(zhí)行步驟8。

步驟8：在迭代次數(shù)達(dá)到預(yù)先設(shè)定的最大值maxgen，或在進(jìn)化過程中找到符合條件的最優(yōu)解時，輸出全局最優(yōu)位置，結(jié)束算法運(yùn)行。

3 仿真實驗及分析

3.1 測試函數(shù)

為驗證本文提出的綜合改進(jìn)算法的優(yōu)化效果，評價其收斂速度和全局搜索能力，采用表1列出的五種經(jīng)典的測試函數(shù)對算法進(jìn)行測試。

表1 測試函數(shù)

表1中f1、f4、f5為單峰函數(shù)，用于檢驗算法的收斂速度和求解精度；f2、f3是多峰函數(shù)，用于檢驗算法的全局搜索能力[12]。

3.2 算法測試及分析

實驗環(huán)境為：Intel(R)Core(TM)i5-10400F CPU 2.90GHz，RAM 16.00GB，Windows 10，Matlab R2018b。

實驗中，取種群規(guī)模N＝20，粒子維度D＝10，兩個加速因子c1 ＝c2 ＝1.49445，最大迭代次數(shù)maxgen＝1000，設(shè)置慣性權(quán)重ω的初始值為0.6。

分別測試四種算法。 首先對SPSO 算法進(jìn)行測試；其次，在SPSO 算法的基礎(chǔ)上，采用基于Cubic 映射的混沌序列SPSO 算法(Chaos Initialization Standard Particle Swarm Optimization，CISPSO)對粒子位置進(jìn)行初始化；然后對僅采用自適應(yīng)動態(tài)變化的慣性權(quán)重策略算法(Exponential Inertia Weight Standard Particle Swarm Optimization，EIWSPSO)進(jìn)行測試；最后測試本文提出的綜合改進(jìn)算法。

實驗的評價指標(biāo)為算法優(yōu)化結(jié)果的平均最優(yōu)值和標(biāo)準(zhǔn)差，將以上四種算法的測試結(jié)果進(jìn)行對比分析，見表2所示。

表2 測試結(jié)果對比

從表2可以看出，當(dāng)種群規(guī)模N＝20，粒子維度D＝10 時，本文提出的綜合改進(jìn)算法在f1、f3、f4和f5上都取得了最優(yōu)效果，而在f2上的結(jié)果僅略差于EIWSPSO 算法。

為分析算法在迭代過程中全局最優(yōu)值與算法適應(yīng)度曲線的收斂速度之間的關(guān)系，本實驗將綜合改進(jìn)算法分別運(yùn)行10 次，記錄10 次的全局最優(yōu)值，并通過選取起始點和接近最低目標(biāo)函數(shù)值的臨界點，求得該適應(yīng)度曲線的平均收斂速度，如表3所示。 由表3可知，全局最優(yōu)值與適應(yīng)度曲線的收斂速度互為矛盾關(guān)系，即隨著迭代次數(shù)增加，該算法適應(yīng)度曲線下降更加明顯，收斂速度加快，同時獲得的目標(biāo)函數(shù)值更低。

表3 全局最優(yōu)值與收斂速度對比

收斂速度是衡量算法求解速度的重要指標(biāo)。為進(jìn)一步對算法的收斂速度進(jìn)行分析，將四種算法的最優(yōu)個體適應(yīng)度曲線分別在五種測試函數(shù)上進(jìn)行對比實驗，結(jié)果如圖2～6 所示。

圖2 算法在函數(shù)f1 上的收斂結(jié)果對比

圖3 算法在函數(shù)f2 上的收斂結(jié)果對比

圖4 算法在函數(shù)f3 上的收斂結(jié)果對比

圖5 算法在函數(shù)f4 上的收斂結(jié)果對比

圖6 算法在函數(shù)f5 上的收斂結(jié)果對比

由圖2～6 可見，本文提出的綜合改進(jìn)算法對應(yīng)的收斂曲線的下降速度明顯快于其他三種算法，且除了f2和f4，在其他三個測試函數(shù)上都獲得了更低的目標(biāo)函數(shù)值。

4 結(jié)論

SPSO 算法具有收斂精度差、在算法后期收斂速度慢的缺點，提出了針對該算法的綜合改進(jìn)算法——基于動態(tài)變化自適應(yīng)慣性權(quán)重的混沌粒子群算法。 利用五種經(jīng)典的測試函數(shù)進(jìn)行測試并與其他三種算法進(jìn)行對比實驗，仿真結(jié)果表明：該改進(jìn)方法尋優(yōu)效果明顯，不僅提高了算法的收斂速度和求解精度，也使算法的全局搜索性能得到提高。 實驗結(jié)果證實該方法具備一定的可行性和有效性。