基于慣性權重的蝙蝠算法

楊曉琴

(太原廣播電視大學，太原 030024)

隨著近年來社會快速發(fā)展，在許多工程應用中出現(xiàn)大量單目標優(yōu)化問題，如求解光伏發(fā)電系統(tǒng)中的全局最大功率點問題[1]、柔性車間調(diào)度問題[2]以及梯級水電站中長期經(jīng)濟調(diào)度問題等[3-6]。這些問題大部分具有非連續(xù)、不可導和不可微等特征，利用經(jīng)典的數(shù)學方法一般無法有效求解此類問題。針對此類問題，許多研究者受到自然界生物信息的啟發(fā)，相繼提出了蝙蝠算法(Bat Algorithm, BA)[7]，微粒群算法(Particle Swarm Optimization Algorithm, PSO)[8]和布谷鳥搜索算法(Cuckoo Search algorithm, CS)[9]等。由于此類啟發(fā)式算法對求解問題的約束條件較少，而且可以有效地解決實際應用中的復雜優(yōu)化問題，迅速得到許多研究者的追捧和深入研究。

蝙蝠算法，作為一種有效地求解復雜優(yōu)化問題的啟發(fā)式算法，雖然被廣泛應用于實際問題，但仍存在求解精度較低、算法后期移動步長較小、局部搜索能力較差以及容易陷入局部最優(yōu)的缺點。為解決算法后期移動步長較小的問題，張宇楠提出蝙蝠個體隨著迭代次數(shù)的增加，步長自適應調(diào)整的策略；Bahman[10]則針對蝙蝠個體提出了四種更新方式，并根據(jù)每種更新方式的特點分配不同權重，有效改進了算法的求解性能。針對算法局部搜索能力差的缺陷，Cai[11]提出利用高斯分布代替均勻分布，有效地改進了算法的局部搜索能力；劉長平[12]利用混沌序列的隨機性和遍歷性，提出了基于混沌搜索策略的蝙蝠優(yōu)化算法。為解決蝙蝠算法容易陷入局部最優(yōu)的問題，楊曉琴[13]提出將Levy飛行引入蝙蝠速度更新公式，提出了融合Levy飛行的蝙蝠算法；同樣針對此問題，孫健[14]提出利用混沌變異的方式改進算法性能；同樣，郭旭[15]提出蝙蝠個體不再單一地向全局最優(yōu)蝙蝠學習,而是與鄰域內(nèi)所有蝙蝠進行信息共享與交流,并根據(jù)自身尋優(yōu)能力自適應地調(diào)節(jié)向其他蝙蝠學習的力度；上述幾種方式有效地改進了蝙蝠算法跳出局部最優(yōu)的能力。為將蝙蝠算法應用于離散化的優(yōu)化問題，李枝勇[16]將遺傳算法中的變異思想融入蝙蝠算法，并引入誘變因子進一步提升算法的求解精度。

為了進一步提升蝙蝠算法求解精度，改進蝙蝠算法過早收斂的缺陷，本文詳細分析了缺陷產(chǎn)生了的原因，并針對性地提出基于慣性權重的蝙蝠算法。在實驗部分，本文詳細分析了慣性權重采用不同分布函數(shù)時算法的性能，并與其他算法做了詳細比較，驗證了本文所提算法的有效性。

1 標準蝙蝠算法

蝙蝠是唯一一種具有翅膀的哺乳類動物，其在夜間視線較差的情況下，利用其回聲定位能力能夠輕易且有效地地捕捉食物和躲避障礙物。受蝙蝠此種行為的啟發(fā)，Yang提出了模擬蝙蝠回聲定位行為的蝙蝠算法(Bat algorithm, BA).為簡化BA模型，Yang提出了三條假設：

(1)食物與障礙物之間的差異依靠蝙蝠的回聲定位判斷；

(2)在位置Xi處，以速度Vi飛行的蝙蝠個體，通過波長(頻率fi)和脈沖(響度Ai)搜索獵物；而且，蝙蝠個體可以根據(jù)與搜索目標的接近程度自適應調(diào)整波長。

(3)脈沖隨著不同情境變化也不同，本文假設脈沖隨著代數(shù)增加而減少，即在Amax到Amin之間變化。

根據(jù)上述條件，可定義蝙蝠個體i在t+1時刻位置和速度全局更新方式，如下：

(1)

(2)

fi=fmin+(fmax-fmin)×β

(3)

式中，β∈[0,1]，fmax和fmin分別是脈沖頻率上限和下限。

局部搜索方式可定義如下：

(4)

為模擬蝙蝠個體在搜索前期以較大脈沖強度搜索目標，后期發(fā)現(xiàn)獵物后逐漸減少脈沖頻率的過程，本文采用以下方式描述此過程：

(5)

(6)

標準蝙蝠算法偽代碼如下所示：

算法1：標準蝙蝠算法

Begin

初始化蝙蝠個體位置，速度以及其它基本參數(shù)；

While (未滿足結束條件)

用式(3)更新蝙蝠個體頻率；

用式(1)更新蝙蝠個體速度；

用式(2)更新蝙蝠個體位置；

用式(4)更新蝙蝠個體位置；

End

計算每個蝙蝠個體適應值；

End

選擇當前最優(yōu)個體;

End

輸出最優(yōu)個體;

End

2 基于慣性權重的蝙蝠算法

(7)

式中w為隨機數(shù)。本文采用常見的三種隨機數(shù)生成方式，即r=randn為服從標準高斯分布的隨機數(shù)(即期望為0，方差為1)、r=rand在[0,1]區(qū)間變化的隨機數(shù), 以及r=λe-λx(在實驗部分用exp表示)為服從指數(shù)分布的隨機數(shù)，其中指數(shù)分布對應率參數(shù)λ設置為1.0，x=1-Gcurrent/Gmax,Gcurrent為當前代數(shù)，Gmax為算法最大代數(shù)。上述三種方式將在后續(xù)實驗中詳細驗證其性能, 本文所提算法命名為基于慣性權重的蝙蝠算法(Bat Algorithm with Inertia Weight, IWBA).

圖1 標準蝙蝠算法速度更新示意圖
Fig.1 Illustration of velocity update in BA

圖2 改進速度更新示意圖
Fig.2 Illustration of improved velocity update

基于慣性權重的蝙蝠算法偽代碼如下所示：

算法2：基于慣性權重的蝙蝠算法

Begin

初始化蝙蝠個體位置，速度以及其它基本參數(shù)；

While (未滿足結束條件)

用式(3)更新蝙蝠個體頻率；

用式(7)更新蝙蝠個體速度；

用式(2)更新蝙蝠個體位置；

用式(4)更新蝙蝠個體位置；

End

計算每個蝙蝠個體適應值；

End

選擇當前最優(yōu)個體;

End

輸出最優(yōu)個體;

End

3 仿真分析

為驗證本文所提算法性能，本文采用微粒群算法(Particle Swarm Optimization algorithm, PSO)和標準BA作為對比算法，其中每個算法相應參數(shù)按照開發(fā)者建議設置。測試函數(shù)采用CEC2013測試集[17-18]，如表1所示，括5個單峰函數(shù)、15個多峰函數(shù)以及8個復合函數(shù)。種群數(shù)量設置為100，每個算法獨立運行51次，個體維度為30維，算法最大運行代數(shù)為3 000次。算法評價指標為平均值誤差(Mean Error)：

(8)

式中f*為理論最優(yōu)適應值，fbest為算法所求最優(yōu)適應值。

3.1 慣性權重w所采用不同分布策略討論

表2所示為慣性權重w采用不同分布策略時對應IWBA算法的求解結果，其中最優(yōu)結果用黑體顯示, 最后一行“w/l/t”表示慣性權重采用均勻分布或者指數(shù)分布的算法與采用高斯分布的算法相比分別在w個函數(shù)上較優(yōu)，在l個函數(shù)上較差以及在t個函數(shù)上相等。從最后一行統(tǒng)計結果可以看出，慣性權重w采用高斯分布時對應算法比采用均勻分布和指數(shù)分布對應的算法性能較優(yōu)。

表1 CEC2013測試函數(shù)
Tab.1 CEC2013 test suit

函數(shù)函數(shù)名稱最優(yōu)值(無單位)F1Sphere Function-1 400F2Rotated High Conditioned Elliptic Function-1 300F3Rotated Bent Cigar Function-1 200F4Rotated Discus Function-1 100F5Different Powers Function-1 000F6Rotated Rosenbrock’s Function-900F7Rotated Schaffers F7 Function-800F8Rotated Ackley’s Function-700F9Rotated Weierstrass Function-600F10Rotated Griewank’s Function-500F11Rastrigin’s Function-400F12Rotated Rastrigin’s Function-300F13Non-Continuous Rotated Rastrigin’s Function-200F14Schwefel's Function-100F15Rotated Schwefel's Function100F16Rotated Katsuura Function200F17Lunacek bi-Rastrigin Function300F18Rotated Lunacek bi-Rastrigin Function400F19Expanded Griewank’s plus Rosenbrock’s Function500F20Expanded Scaffer’s F6 Function600F21Composition Function 1700F22Composition Function 2 800F23Composition Function 3 900F24Composition Function 4 1 000F25Composition Function 5 1 100F26Composition Function 6 1 200F27Composition Function 7 1 300F28Composition Function 8 1 400搜索空間[-100,100]D

表2 不同分布策略對應算法實驗結果對比
Tab.2 Comparison of IWBA with different distribution strategies

函數(shù)IWBAw=randn(無單位)w=rand(無單位)w=exp(無單位)?F15.00E-011.95E+002.04E+00F25.39E+052.70E+063.52E+06F34.63E+072.22E+083.13E+08F42.80E+023.60E+042.16E+04F52.94E-015.55E-015.73E-01F65.29E+014.67E+016.22E+01F71.49E+022.61E+021.78E+02F82.09E+012.09E+012.09E+01F93.56E+013.38E+013.42E+01F101.24E+001.31E+001.32E+00F114.53E+024.60E+024.18E+02F124.55E+024.54E+023.66E+02F133.94E+024.83E+024.31E+02F144.70E+034.85E+035.09E+03F154.63E+034.80E+034.56E+03F169.96E-012.08E+002.31E+00F173.88E+024.65E+027.61E+02F183.78E+024.25E+027.99E+02F192.68E+013.04E+015.79E+01F201.45E+011.47E+011.44E+01F212.49E+023.40E+023.67E+02F225.52E+036.00E+035.97E+03F235.60E+036.14E+035.82E+03F243.20E+023.22E+023.13E+02F253.50E+023.60E+023.37E+02F262.28E+022.97E+022.00E+02F271.36E+031.34E+031.27E+03F283.35E+034.17E+032.87E+03w/l/t4/24/09/19/0

表3為上述采用不同分布策略的算法Friedman測試結果。從表3測試結果可以看出，慣性權重w采用高斯分布時對應算法具有較小的秩均值，即慣性權重采用標準高斯分布時對應算法具有較優(yōu)性能。

表3 Friedman測試結果
Tab.3 Friedman test results

算法秩均值(無單位)BA(w=randn)1.75BA(w=rand)2.96BA(w=exp)2.64

3.2 不同算法性能對比

為進一步測試本文所提算法性能，本部分將IWBA(慣性權重w采用高斯分布)與PSO, 混沌BA以及標準BA做進一步對比。表4列出了多個對比算法實驗結果。從表4最有一行對比結果可以看出，IWBA相比于標準BA以及PSO具有較大的優(yōu)勢。在F23-F27測試函數(shù)上，IWBA結果略差于標準BA, 其原因是本文所設計的改進機制旨在使算法跳出局部最優(yōu)，使得對部分局部最優(yōu)或者全局最優(yōu)無法充分地搜索，這也從側(cè)面說明了本文所提算法在跳出局部最優(yōu)方面的有效性。

表4 不同算法對比
Tab.4 Comparison of different algorithms

函數(shù)IWBA(無單位)BA(無單位)PSO(無單位)F15.00E-011.83E+002.96E+04F25.39E+053.26E+064.02E+08F34.63E+072.26E+081.65E+14F42.80E+023.44E+045.25E+04F52.94E-014.74E-011.04E+04F65.29E+015.99E+014.54E+03F71.49E+021.75E+021.60E+04F82.10E+012.10E+012.10E+01F93.56E+013.57E+014.05E+01F101.24E+001.32E+003.98E+03F114.53E+023.81E+025.72E+02F124.55E+024.04E+025.18E+02F133.94E+024.73E+025.43E+02F144.70E+034.61E+038.21E+03F154.63E+035.17E+037.19E+03F169.96E-012.30E+002.59E+00F173.88E+029.31E+027.25E+02F183.78E+029.49E+027.12E+02F192.68E+016.15E+019.52E+04F201.45E+011.46E+011.50E+01F212.49E+023.70E+022.28E+03F225.52E+035.66E+038.55E+03F235.60E+035.73E+038.38E+03F243.20E+023.12E+023.76E+02F253.50E+023.43E+023.92E+02F262.28E+022.00E+022.44E+02F271.36E+031.26E+031.49E+03F283.35E+033.79E+034.43E+03w/l/t8/20/00/28/0

表5列出了不同算法 Friedman檢驗結果，從對比數(shù)據(jù)可以看出本文所提算法具有最小秩均值。綜合以上實驗結果可以得出，本文所提改進算法有效地改進了個體陷入局部最優(yōu)的難題，提升了算法搜索性能。

表5 不同對比算法Friedman測試結果
Tab.5 Friedman test results of different comparison algorithms

算法秩均值(無單位)BA1.93IWBA1.29PSO3.73

4 結論

在對蝙蝠算法速度更新方式詳細分析的基礎上，本文發(fā)現(xiàn)標準蝙蝠算法原有速度更新方式有利于發(fā)掘當前全局最優(yōu)解附近個體；然而，當個體陷入局部最優(yōu)時，此時全局速度更新方式無法有效地跳出局部最優(yōu)解。針對此缺陷，本文提出了基于慣性權重的蝙蝠算法，即對速度添加慣性權重。實驗結果顯示，本文所提IWBA有效地提高了蝙蝠算法的性能。