具有動態(tài)方差高斯變異的蝴蝶優(yōu)化算法*

張小萍, 譚歡

(1. 廣西大學 計算機與電子信息學院， 廣西 南寧，530004;2.中國移動通信集團廣西有限公司，廣西 南寧 530022)

1 引言

優(yōu)化問題是工程數(shù)學中的普遍適用性問題，由于其使用的廣泛性和多樣性一直都是研究領(lǐng)域中的熱點.優(yōu)化的方法大致可以分為兩類：確定性優(yōu)化方法和隨機優(yōu)化方法.確定性優(yōu)化方法對應用條件的要求非常嚴格，只能用于小規(guī)模的優(yōu)化問題，對于大規(guī)模的優(yōu)化問題一般使用的是隨機優(yōu)化方法[1].在隨機優(yōu)化方法中，群智能優(yōu)化算法近年來得到了快速的發(fā)展，出現(xiàn)了許多優(yōu)秀的算法，包括粒子群算法(PSO)[2]、樹種算法(TSA)[3]、灰狼算法(GWO)[4]和烏鴉算法(CSA)[5]等，這些算法被廣泛應用到圖像分割[6]、軟件工程測試數(shù)據(jù)生成[7]和SVM參數(shù)優(yōu)化[8]等領(lǐng)域，獲得了良好的效果.

蝴蝶優(yōu)化算法(BOA)[9]的基本思想是模擬蝴蝶覓食的過程，該算法的參數(shù)較少，迭代過程簡單易于實現(xiàn)，而且可以獲得較高的求解精度；但蝴蝶優(yōu)化算法存在收斂速度較慢，容易陷入局部最優(yōu)解的問題，因此需對其進行改進，以提高算法的全局搜索能力和收斂速度.文獻[10]提出的改進算法(AGSABOA)在全局位置更新處融入收斂因子并結(jié)合黃金正弦指引機制來改善迭代后期種群多樣性的下降，提高全局搜索的范圍.文獻[11]使用cubic混沌映射初始化種群，并將粒子群算法和蝴蝶算法結(jié)合(HBOAPSO).上述算法的種群多樣性和全局搜索能力都獲得了提高，但仍存在迭代后期種群多樣性不足和難以平衡全局搜索和局部搜索的問題，可進行進一步的優(yōu)化研究.本文提出一種改進的蝴蝶優(yōu)化算法，首先引入線性函數(shù)的動態(tài)切換概率來平衡全局搜索和局部搜索，然后使用方差動態(tài)變化的高斯隨機數(shù)來改進局部搜索和全局搜索的公式，提高局部搜索能力的同時避免陷入局部最優(yōu)解.

2 基本蝴蝶優(yōu)化算法(BOA)

蝴蝶優(yōu)化算法是模擬蝴蝶在覓食和求偶時行為的群智能優(yōu)化算法，在該算法中每只蝴蝶都可以發(fā)出一定濃度的香味，這些香味可以被一定范圍內(nèi)的其他蝴蝶所感知，每只蝴蝶散發(fā)香味的濃度和適應度有關(guān)，當蝴蝶從一個位置移動到另一個位置，對應的適應度也發(fā)生改變；當蝴蝶感知到香味濃度最大蝴蝶(最優(yōu)蝴蝶)的香味時，就朝最優(yōu)蝴蝶的方向移動，這個階段叫作全局搜索階段；當感知不到比自己更濃香味時，則隨機移動，這個階段叫作局部搜索階段.香味的計算公式為

fi=cIα;

(1)

其中，fi是其他蝴蝶對香味的感知濃度；c是感官模態(tài)因子；I是刺激強度；α是由感官模態(tài)決定的冪指數(shù)參數(shù).

全局搜索和局部搜索通過切換概率p來控制，在全局搜索階段，蝴蝶向最優(yōu)蝴蝶g*方向移動，可表示為

(2)

在局部搜索階段，蝴蝶進行隨機移動，可表示為

(3)

3 具有動態(tài)方差高斯變異的蝴蝶優(yōu)化算法(DGBOA)

針對BOA存在著收斂速度慢，尋優(yōu)精度不高，容易陷入局部最優(yōu)解的問題，對其進行了兩點改進，一是使用線性函數(shù)的動態(tài)切換概率來取代常數(shù)切換概率，二是使用動態(tài)方差的高斯變異來改進局部搜索和全局搜索的公式.

3.1 線性函數(shù)的動態(tài)切換概率

在BOA中，切換概率p是一個常數(shù)，決定了每次迭代全局搜索和局部搜索的相對比例，是平衡算法勘探和開發(fā)能力的重要參數(shù).對于一個優(yōu)秀的尋優(yōu)算法，在算法迭代初期往往需進行全局搜索，在迭代后期主要進行局部搜索，因此常數(shù)的切換概率p無法適應BOA迭代的要求，使用線性函數(shù)的動態(tài)切換概率，在迭代的不同階段p的值是不同的，為

圖1 μ=0，σ=0.5，1,2的高斯曲線Fig.1 Gaussian curve of μ=0，σ=0.5,1,2

(4)

其中，t是當前迭代次數(shù)；tmax是算法的最大迭代次數(shù)；pmax和pmin是切換概率的最大和最小值.在公式(4)中，迭代初期p(t)比較大，主要進行全局搜索以便盡快確定全局最優(yōu)解的位置，提高搜索速度，在迭代后期，p(t)比較小，主要進行局部搜索以便提升算法的尋優(yōu)精度.

3.2 動態(tài)方差的高斯變異

高斯概率密度函數(shù)可以表示為

(5)

其中，μ表示均值；σ表示標準方差；當μ=0，σ=0.5,1，2時函數(shù)曲線如圖1所示.

顯然當方差越小時，函數(shù)值集中在均值附近的概率越大，函數(shù)曲線也會越向均值靠攏，當產(chǎn)生高斯隨機數(shù)時，計算發(fā)現(xiàn)μ=0,當σ=0.5時，產(chǎn)生的隨機數(shù)在[-0.5,0.5]范圍概率達到68.3%，而當σ=2時，產(chǎn)生隨機數(shù)在[-0.5,0.5]范圍概率只有19.7%.由于BOA容易陷入局部最優(yōu)解，在迭代前期需要在較大的范圍內(nèi)進行探索以便快速定位到全局最優(yōu)解，在迭代后期需要在優(yōu)化精度和避免早熟而進入局部最優(yōu)解之間進行平衡，因此可以利用高斯隨機數(shù)中方差的變化來達到目的，在初始時設(shè)置方差比較大，使種群在一個變化范圍大的區(qū)間進行搜索，在迭代后期方差逐漸變小，種群大概率在一個變化范圍比較小的區(qū)間進行探索，以提高尋優(yōu)的精確度，同時也有機會跳出局部最優(yōu)解.設(shè)置方差的最大值σmax和最小值σmin.方差計算公式為

σ(t)=σmax-(σmax-σmin)×t/tmax;

(6)

其中，t是當前迭代次數(shù)；tmax是算法的最大迭代次數(shù).

BOA的局部搜索公式改進為

(7)

其中normrnd(0,σ(t))表示均值為0、方差為σ(t)的隨機數(shù).

為了增加種群的多樣性，全局搜索采用兩種方式進行，全局搜索的公式改進為

(8)

其中pg是全局搜索兩種更新方式的轉(zhuǎn)換概率，是(0,1)之間的一個常數(shù).

3.3 DGBOA算法描述

Step 1.初始化系統(tǒng)相關(guān)參數(shù)和種群；

Step 2.計算種群中每個個體的適應度，并使用公式(1)計算香味的濃度，然后根據(jù)適應度得到最佳蝴蝶的位置g*；

Step 3.使用公式(4)計算轉(zhuǎn)換概率p(t)；

Step 4.生成一個隨機數(shù)rand,若rand

Step 5.否則，使用公式(7)進行局部位置更新；

Step 6.檢查更新后的位置的適應度值是否比原來更新前的值更優(yōu)，如果更優(yōu)，則用更新后的位置取代更新前的位置，并更新全局最優(yōu)蝴蝶的位置和適應度值；

Step 7.判斷是否滿足結(jié)束條件，不滿足就轉(zhuǎn)到Step 2，否則輸出全局最優(yōu)解和相應的適應度，算法結(jié)束.

4 實驗仿真測試結(jié)果和分析

4.1 實驗環(huán)境與測試函數(shù)

實驗環(huán)境為64位的Windows 7，CPU為Inter(R) Xeon(R)E5645主頻雙核2.4 GHz,內(nèi)存8 G,仿真實驗軟件為MATLAB 2020b.選擇了6個基準函數(shù)作為測試函數(shù)，函數(shù)的具體情況如表1所示，其中‘U’表示單峰值函數(shù)，‘M’表示多峰值函數(shù).

表1 基準測試函數(shù)

4.2 實驗參數(shù)設(shè)置和仿真結(jié)果

在實驗中DGBOA設(shè)置的參數(shù)為pmax=0.8,pmin=0.3,a=0.1,c=0.01,σmax=1.5,σmin=0.4，pg=0.5,將DGBOA和HBOAPSO、AGSABOA、BOA、PSO和GWO共6種算法作對比試驗，設(shè)置最大迭代次數(shù)為500次，種群中的個體數(shù)為30，在每個函數(shù)上單獨運行50次，計算它們的最大值、最小值、平均值、方差和運行時間，得到的實驗結(jié)果如表2所示.

表2 實驗結(jié)果

從表2可以看出在使用的6個測試函數(shù)中，DGBOA在5個測試函數(shù)中都找到了理論最優(yōu)解，并且在6個函數(shù)中方差為0，具有較強的穩(wěn)定性.使用平均絕對誤差[12](Mean Absolute Error,MAE)作為定量標準來分析6個算法，計算各算法的MAE值，HBOAPSO是1.480E-16,AGSABOA是1.320，BOA是2.233E-2,PSO是2.243E2，GWO是7.877E-1，DGBOA是1.355E-18，顯然，DGBOA的MAE值是所有算法中最小的，說明引入的改進策略是有效的.

為了進一步分析DGBOA算法的有效性，圖2-5給出了4個多峰值函數(shù)在6個算法下的收斂曲線.

圖2 f3的收斂曲線 圖3 f4的收斂曲線

圖4 f5的收斂曲線 圖5 f6的收斂曲線

從收斂曲線圖中可以看出，PSO和BOA在f5當中無法迭代到理論最優(yōu)解，PSO和GWO在f6當中無法迭代到理論最優(yōu)解，AGSABOA和HBOAPSO曲線的波動在f3與f5中都比DGBOA要大，收斂到理論最優(yōu)值需要更多的迭代次數(shù)，而DGBOA算法在四個函數(shù)的迭代初期就可以接近理論最優(yōu)解，比其他5個算法的迭代次數(shù)要少，尋優(yōu)能力更強.

通過實驗數(shù)據(jù)對比可以看出，DGBOA對于所給的測試基準函數(shù)都有較好的尋優(yōu)效果，具有較強的穩(wěn)定性和較快的尋優(yōu)能力，有效緩解BOA算法尋優(yōu)精度不高，難以獲得全局最優(yōu)解的問題.