基于模糊控制的權重決策灰狼優化算法①

邢燕禎, 王東輝

1(中國科學院 聲學研究所, 北京 100190)

2(中國科學院 聲學研究所 中國科學院水下航行器信息技術重點實驗室, 北京 100190)

3(中國科學院大學, 北京 100049)

自20世紀80年代開始, 啟發式算法得以迅速發展, 較為經典的有遺傳算法(Genetic Algorithm, GA)[1],粒子群算法(Particle Swarm Optimization, PSO)[2], 蟻群算法(Ant Colony Optimization, ACO)[3], 模擬退火算法(Simulated Annealing, SA)[4]等, 并得到了廣泛應用. 近些年來, 很多模擬自然界群體行為的新型啟發式算法蜂擁而出, 如蝙蝠算法(Bat Algorithm, BA)[5], 螢火蟲算法(Firefly Algorithm, FA)[6], 布谷鳥搜索算法(Cuckoo Search, CS)[7]等. 灰狼優化算法(Grey Wolf Optimizor, GWO)是一種2014年由學者S Mirhalili等人提出的新型啟發式算法[8], 源于對灰狼群體追蹤、圍捕、攻擊獵物捕食行為的模擬. GWO算法實現簡單且具有較強的尋優性能, 因此在各個領域都得到了廣泛的應用, 如流水車間調度[9], 醫學影像優化[10], 電力系統穩定器的參數優化[11], 多層感知器的訓練[12]等.

盡管GWO算法在很多領域獲得較成功的應用,但GWO算法也同其他啟發式算法一樣, 存在求解精度較低, 容易陷入局部最優等問題. 為提高GWO算法的尋優性能, 國內外學者相繼做了很多研究, 改進的方法有幾類[13], 一類是對GWO算法種群進行優化, 如引入反向學習理論、混沌擾動理論等優化搜索種群[14–16];一類是對GWO算法本身的變量參數進行改進, 如改進收斂因子和種群更新策略等[17];還有引入其他進化算法的理論到GWO算法中, 以改進算法尋優新能, 如混合差分進化算法、粒子群算法等[18–20].

為提高基本GWO算法的收斂速度, 獲得更高的求解精度, 本文提出了一種基于模糊控制的權重決策灰狼優化算法(Fuzzy Weight Grey Wolf Optimizer,FWGWO). 首先, 提出了一種新的收斂因子, 通過增加前期廣度搜索的比例, 可提高算法的全局搜索能力, 同時使算法后期具有更快的收斂速度. 其次, 提出一種基于模糊控制的權重決策策略, 在算法迭代的不同時期.對決策層的個體賦予不同權重進行決策, 以增強決策的公平性, 提高算法的尋優能力. 最后, 對23個標準測試函數的實驗結果表明, FWGWO算法相較于對比算法具有更快的收斂速度和更高的收斂精度.

1 GWO算法

1.1 灰狼群體的社會層級制度

社會層級制度是灰狼群體的顯著的特征之一, 一般呈金字塔形, 將灰狼群體分為四層, 分別是α, β, δ和ω層, 如圖 1所示. 第一層為種群的頭狼α, 作為灰狼群體的領導者, 是灰狼群體行為的主要決策者;處于第二層的是β, 主要負責協助頭狼α對狼群的行為做決策,是頭狼的主要候選者;處于第三層級的是δ, 是灰狼群體比較特殊的一類, 包括偵查員、看護者、狩獵者等;最底層為ω狼, 負責平衡灰狼群體內部的關系.

1.2 GWO算法描述

對于灰狼群體來說, 捕食行為是其另外一個有趣的行為特征. Muro C指出[21], 狼群捕食一般包括以下階段:

第一階段:跟蹤、追趕、靠近獵物

第二階段:包圍, 擾亂獵物, 直到獵物停止移動

第三階段:攻擊獵物

GWO算法是模擬灰狼群體捕食過程的尋優算法.尋找最優解的過程可看做狼群捕食的過程, 目標獵物的位置即為對應函數的最優解. 將靠近目標最優解的個體看作狼群中起領導決策作用的狼, 領導個體通過不斷更新與目標之間的距離判斷移動的方向, 最后帶領群體靠近目標.

圖1 灰狼群體社會等級示意圖

為便于利用GWO算法求解函數最優解的問題,首先對GWO算法進行建模[16]:定義灰狼種群中最優個體為α, 可理解為種群中適應度最高, 離最優解距離最近的個體, 適應度值排名第二和第三的個體記為β和δ, 剩余個體記為ω.

定義1. 灰狼群體與目標獵物的相對距離. 捕食初期, 狼群會先對獵物進行包圍, 狼群個體與獵物之間的相對距離由D表示:

其中,Xp(t)代表獵物當前的位置,X(t)代表第t代灰狼個體的位置,C為影響因子,r1為[0,1]區間均勻分布的隨機數.

定義2. 灰狼個體位置更新. 灰狼個體會根據自己與獵物的相對距離做出位置更新, 下一步灰狼個體的位置為:

其中,A為收斂影響因子,a為收斂因子, 隨迭代次數的增加線性遞減,r2為[0,1]區間均勻分布的隨機數,Max_iter為最大迭代次數.

定義3. 灰狼群體位置更新. 在灰狼群體中,α,β和δ三頭狼為距離獵物相對最近的狼, 假設這三頭狼對獵物的位置具有更多的信息, 因此在捕食過程中由這三頭狼帶領狼群其他狼一起向獵物靠近, 其他狼每一步移動的位置由這三頭狼共同決策.α,β和δ需通過式(6)–(8)分別計算各自與獵物的位置, 然后通過式(9)–(11)更新各自下一步的位置, 則灰狼群體其他狼下一步移動的位置由式(12)決定.

2 FWGWO算法

2.1 改進的收斂因子

對于啟發式算法, 尋優的過程都涵蓋了廣度搜索和深度搜索兩類操作. 一般, 前期缺少先驗知識, 種群會在全局范圍內進行搜索, 此時主要為廣度搜索, 目的是盡可能探索更廣度的區域, 發現較多的全局最優解;深度搜索則主要是在算法后期, 在廣度搜索基礎上進行深度開發, 此階段種群會根據前期搜索的先驗知識,逐漸靠近較優解, 盡可能靠近最優解以及獲得更好的求解精度. 一個優秀的尋優算法不僅要求算法有較快的收斂速度, 還要求在前期有較強的探索能力, 在后期有較強的開發能力, 以獲得更高的求解精度. 因此, 提高算法的尋優性能務必要協調好廣度搜索和深度搜索的比例關系.

在GWO算法中, 變量A是主要影響到廣度搜索和深度搜索的變量. 在GWO算法中定義了, 當|A|>1時, 灰狼群體將擴大包圍圈, 此時, 算法為廣度搜索, 當|A|<1時, 灰狼群體將縮小包圍圈, 以完成對獵物的包圍攻擊, 此時, 算法為深度搜索, 如圖 2所示[8].

由式(4)可知,A的變化區間主要由收斂因子a決定, 當a從2遞減為0,A的取值在[-a,a]之間變化. 由此可知,A的取值變化主要受收斂因子a影響, 因此, 通過調整收斂因子a, 可以調整算法尋優過程中廣度和深度搜索的比例.

圖2 變量A與種群搜索的關系

在原GWO算法中, 廣度搜索和深度搜索比例為1:1. 為加快GWO算法的收斂速度, 避免原GWO算法容易陷入局部最優的問題, 本文提出了一種新的非線性收斂因子, 增加了前期廣度搜索的比例, 一方面利于搜索更多的全局最優點, 避免陷入局部最優, 另一方面該收斂因子在算法后期的取值變化迅速, 能使得算法在后期獲得更快的收斂速度, 從而獲得更好的求解精度. 改進后的收斂因子由式(13)表示.

2.2 基于權重決策的位置更新策略

在GWO算法中, 由式(8)可知, 種群下一次移動的位置由α,β,δ共同做決策, 且決策平均. 顯然, 這種平均決策方法并沒有考慮α,β,δ的個體特征, 沒辦法體現出α狼作為主要領導者和適應度最高的個體在決策時的重要性.

為實現自適應調整決策個體在不同時期的權重比例, 本文提出了一種基于模糊控制的權重決策種群位置更新策略, 在算法迭代的不同時期, 通過模糊控制器對α,β和δ賦予不同的權重比例, 使得種群更新的位置更加可靠, 改進的種群更新位置公式如式(14)所示.

其中,fwα、fwβ、fwδ分別為α,β,δ的模糊權重系數由模糊控制器獲得.

基本的模糊控制器一般包括輸入量模糊化, 模糊邏輯和模糊判決, 其結構如圖 3表示[22].

圖3 基本模糊控制器

本文定義的模糊控制器包括一個輸入和三個輸出,其中迭代次數作為輸入, 模糊集包括“前”, “中前”,“中”, “中后”, “后”;α,β,δ的模糊系數作為輸出, 模糊集均用“低”, “較低”, “中”, “較高”, “高”來描述. 算法迭代次數的隸屬度函數, 如圖 4 所示,α,β,δ的模糊系數的隸屬度函數相同, 如圖 5所示.

圖4 模糊控制器輸入—迭代次數的隸屬度函數

圖5 模糊控制器輸出—fwα/fwβ/fwδ的隸屬度函數

定義如下IF-THEN模糊規則:

規則1. IF<迭代次數為“前”>, THEN<α的模糊系數fwα為“中”,β的模糊系數fwβ為“中”,δ的模糊系數fwδ為“較低”>;

規則2. IF<迭代次數為“中前”>, THEN<α的模糊系數fwα為“較高”,β的模糊系數fwβ為“中”,δ的模糊系數fwδ為“較低”>;

規則3. IF<迭代次數為“中”>, THEN<α的模糊系數fwα為“較高”,β的模糊系數fwβ為“中”,δ的模糊系數fwδ為“低”>;

規則4. IF<迭代次數為“中后”>, THEN<α的模糊系數fwα為“較高”,β的模糊系數fwβ為“較低”,δ的模糊系數fwδ為“低”>;

規則5. IF<如果迭代次數為“后”>, THEN<α的模糊系數fwα為“高”,β的模糊系數fwβ為“較低”,δ的模糊系數fwδ為“低”>.

最后, 使用Matlab的模糊控制器工具箱完成模糊控制器的設計, 解模糊采取“重心法”.

2.3 FWGWO算法描述

綜上所述, FWGWO的算法描述如下:

3 實驗及分析

本文采用Matlab R2012b進行仿真, 運行環境為Intel(R) Corel(TM) i7-3770處理器, 3.5 GHZ內存. 測試集為CEC2005, 將GWO算法、粒子群算法(Particle Swarm Optimization, PSO)及FWGWO算法對測試集中的23個標準測試函數進行測試, 其中F1–F7為單峰函數, F8–F13為多峰函數, F14–F23為固定維數多峰函數, 篇幅原因, 測試函數的定義、維度及最小值等參數詳見文獻[1].

仿真實驗設置種群數目為30, 迭代次數為500, 測試函數的維度按文獻[1]中設置. 幾種算法的參數設置如下:PSO算法中設置ωmax=0.9,ωmin=0.2,c1=c2=2;GWO算法和FWGWO算法設置amax=2,amin=0. 針對同一測試函數, 將每種算法獨立運行50次, 并統計均值和標準差.

表1給出了三種算法針對13個標準測試函數獨立運行50次的均值和標準差, 其中F1–F7為單峰標準函數, F8–-F13為多峰標準函數.

表2給出了三種算法針對10個固定維數多峰函數獨立運行50次的均值和標準差.

表1 三種算法針對13個標準函數的測試結果

表2 三種算法針對固定維數多峰測試函數的測試結果

由表 2可以看出, FWGWO算法對于大部分函數均取得較好的尋優結果, 特別是對于單峰標準函數F1-F4, FWGWO算法性能明顯優于對比算法. FWGWO和GWO算法在F1、F2、F3、F4、F10上可判定為找到全局最優解, 而FWGWO算法相對于基本GWO算法具有更好的求解精度. 對于F9、F11, 在100次獨立測試中, FWGWO算法尋優正確率分別是91%、93%,而GWO算法尋優正確率分別為51%、72%. 由此可知, FWGWO算法相較于GWO算法, 在大部分函數的尋優性能上有明顯提升. PSO算法在測試函數F6、F12、F13取得較好的尋優結果, 但整體看來, FWGWO算法在大部分函數的尋優結果均優于PSO算法.

由表3可以看出, FWGWO算法在測試函數F16-F23都能收斂到函數最小值, 對于測試函數F14、F15基本接近函數最小值. 相比于對比算法, FWGWO算法在大部分函數具有更好的求解精度. 圖 6示意了三種算法針對不同測試函數的收斂曲線, 展示了算法針對兩個單峰測試函數F1、F3和兩個多峰測試函數F9、F10的收斂曲線.

由圖 6可以看出, FWGWO算法相較于對比算法,算法后期具有更快的收斂速度, 且能取得更好的尋優結果. 綜合以上分析可知, 相較于PSO算法和GWO算法, FWGWO算法具有更好的算法尋優性能和算法穩定性.

4 結論與展望

本文提出一種改進的灰狼優化算法, 提出了一種新的收斂因子以及一種基于動態權重的種群位置更新策略, 通過模糊控制器獲得決策個體的權重系數, 使決策時更好地體現決策個體的差異性, 從而使種群更新位置更準確. 算法在23個標準測試函數上的實驗結果表明, 本文提出的模糊權重灰狼優化算法FWGWO與對比算法相比, 具有更好的尋優性能和更好的穩定性.

圖6 算法針對不同函數的收斂曲線示意圖