協(xié)同智能的蝙蝠差分混合算法

趙志剛，曾 敏，莫海淼，李智梅，溫 泰

(廣西大學 計算機與電子信息學院，廣西 南寧 530004)

0 引 言

差分進化算法[1](differential evolution algorithm，DE)是由R.tSorn和K.irPec提出的一種基于群體差異的啟發(fā)式并行搜索方法。作為一種簡單、高效的連續(xù)空間內(nèi)全局優(yōu)化方法，有著和其它基于群體的啟發(fā)式搜索算法一樣的結(jié)構(gòu)簡單、易于實現(xiàn)的優(yōu)點。廣泛應用在工程優(yōu)化問題[2]、大數(shù)據(jù)分析[3]、云計算[4]、數(shù)據(jù)分類[5]等領(lǐng)域。

隨著進化代數(shù)的增加，個體之間的差異化信息逐漸縮小，DE到后期收斂速度變慢，有時會陷入局部最優(yōu)。為了提高DE的性能，改進的主要方法有：控制參數(shù)的改進、差分策略的改進、選擇策略的改進、種群重構(gòu)、混合算法等。拓守恒等[6]將和聲算法和差分算法結(jié)合，提出了一種混合算法，并用于求解多模態(tài)復雜問題；賀軍義等[7]基于和聲差分進化算法對UKF算法進行改進，并應用于濾波器設(shè)計；鄒華福等[8]將反向?qū)W習的思想引入到差分算法中，提出了一種算法，擴大算法的全局勘探范圍；李志敏等[9]以云計算時間最少為優(yōu)化目標提出了差分人工蜂群算法，以解決云計算資源調(diào)度問題；徐俊等[10]提出一種混合差分粒子群算法，來求解任務(wù)調(diào)度的問題，以更充分利用共享資源；張新明等[11]提出了一種灰狼算法和差分算法的混合優(yōu)化算法，使用嵌入趨優(yōu)算子的GWO算法搜索。

為了更好平衡差分算法的全局搜索和局部開發(fā)能力，利用蝙蝠算法有較好的局部搜索效果的特點，本文提出了一種蝙蝠算法與差分算法的混合算法。為了驗證算法的有效性，使用9個測試函數(shù)和5個0-1背包問題，與標準粒子群算法、帶高斯擾動的粒子群算法、蝙蝠算法、差分算法、煙花算法相對比。

1 差分進化算法

差分進化算法模擬生物進化，經(jīng)過一代代循環(huán)迭代，保留最優(yōu)個體，尋找最優(yōu)解。主要包含了變異、交叉、選擇3部分操作。

1.1 參數(shù)向量初始化

在D維向量空間里隨機產(chǎn)生滿足約束條件的M個向量初始化為

(1)

1.2 基于差分向量的變異

(2)

1.3 交 叉

通過交叉操作生成實驗向量，增加種群多樣性

(3)

其中， 〈〉D表示函數(shù)“對D取?！?。

2 蝙蝠算法

蝙蝠算法(bat algorithm，BA)[12]模擬蝙蝠覓食來實現(xiàn)算法的迭代和尋優(yōu)。蝙蝠在捕食過程中利用回聲來定位，將各個蝙蝠個體看作可行解，捕食過程看作搜索過程。

2.1 蝙蝠的移動

每個蝙蝠有擁有自己的位置、速度、飛行頻率，并可以發(fā)出聲波。利用所在的位置的目標函數(shù)值來評估位置的優(yōu)劣。蝙蝠種群個體通過速度和飛行頻率的變化來進行位移，通過響度和脈沖的變化，來靠近最優(yōu)解。標準蝙蝠算法使用式(4)至式(6)對飛行頻率、速度和位置進行更新

fi=fmin+(fmax-fmin)β

(4)

(5)

(6)

Xnew=Xold+εAVt,ε∈[-1,1]

(7)

其中，ε是[-1,1]范圍內(nèi)的隨機數(shù)，AVt是當前蝙蝠種群的平均響度。

2.2 響度和脈沖

響度和脈沖會隨著尋優(yōu)過程而發(fā)生改變，當蝙蝠逐漸靠近獵物的時候，響度會越來越小，同時脈沖頻率會越來越大。蝙蝠算法的響度和脈沖是根據(jù)式(8)、式(9)進行更新

(8)

對于任何0<α<1和β>0的情況下都有

(9)

3 差分蝙蝠混合算法

3.1 協(xié)同智能

協(xié)同智能[13]是指差分種群和蝙蝠種群信息交互、相互協(xié)作。蝙蝠覓食時距離獵物越近，其發(fā)出的脈沖逐漸大，響度逐漸小，對應算法尋優(yōu)時越接近最優(yōu)解，從全局搜索轉(zhuǎn)換為局部搜索。利用蝙蝠算法這一特點，將其與差分算法結(jié)合起來，以期動態(tài)平衡算法的全局搜索與局部開發(fā)的能力。

具體操作為：當?shù)趇個蝙蝠種群個體發(fā)出的脈沖r(i)小于隨機脈沖且響度A(i)大于隨機響度時，對差分種群得到的當前最優(yōu)解gbest進行高斯擾動產(chǎn)生局部解Batx(i)，相當于在gbest附近進行一次詳細搜索。并對Batx(i)進行評價，并與差分種群的第i個個體X(i)的適應度值相對比，如果蝙蝠個體更優(yōu)，則被選入下一代。產(chǎn)生局部解的具體操作如下

Batx(i)=gbest*(N(0,1)+1),asr(i)

(10)

其中，N(0,1) 是服從均值為0，方差為1的高斯分布函數(shù)；r(i) 是第i個蝙蝠發(fā)出的脈沖；rand是[0,1]內(nèi)生成的隨機數(shù)。

以適應度值來判斷局部解的優(yōu)劣，并以脈沖和響度條件作為約束，當滿足式(11)時，局部解將加入下一次迭代，完成蝙蝠種群和差分種群的信息交互

x(i)=Batx(i),asf(Batx(i))rand

(11)

其中，AV(i)是第i個蝙蝠發(fā)出的響度。

差分種群與蝙蝠種群協(xié)同尋優(yōu)的偽代碼如 Algorithm 1所示：

步驟1 在當前最優(yōu)解附近產(chǎn)生一個局部解，根據(jù)式(10)；

步驟2 對局部解進行越界處理，并計算其適應度值；

步驟3 根據(jù)式(8)、式(9)更新響度和脈沖；

步驟4 按照式(11)判斷是否將局部解加入下一代；

步驟5 若該局部解優(yōu)于gbest，則將gbest替換。

3.2 混合算法

綜合第1小節(jié)的差分算法，以及3.1小節(jié)的協(xié)同尋優(yōu)，本文提出了蝙蝠差分混合算法(hybrid bat and differential evolution algorithm，BADE)，BADE混合算法的偽代碼如Algorithm 2所示：

步驟1 初始化蝙蝠種群、差分種群；

步驟2 差分種群分別根據(jù)式(1)、式(2)、式(3)進行變異、交叉、選擇操作；

步驟3 蝙蝠種群協(xié)同尋優(yōu)：Algorithm 1；

步驟4 判斷是否接受新解，如果接受，更新gbest；

步驟5 重復步驟2～步驟4的步驟，達到終止條件之后，終止迭代。

4 仿真實驗

4.1 測試函數(shù)

選用了表1中的9個基準測試來測試混合算法BADE在解決連續(xù)型優(yōu)化問題上的能力，這9個基準測試函數(shù)均來自全局優(yōu)化測試函數(shù)庫。其中f1～f5的維度為30dim，f6～f9維度為2dim?！?”表示該函數(shù)的最優(yōu)點不止一個。并與標準粒子群算法(SPSO)[14]、帶高斯擾動的粒子群算法(GPSO)[15]、蝙蝠算法(BA)[12]、差分算法(DE)[1]、標準煙花算法(FWA)[16]進行對比分析。

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

4.2 與其它算法對比

為了避免參數(shù)設(shè)置的差異對于實驗結(jié)果產(chǎn)生的影響，保證實驗公平與公正，設(shè)置種群大小pop=40；尋優(yōu)精度λ=10-5；最大迭代次數(shù)Max_Ite=1000。設(shè)置BADE的最大飛行頻率fmax=100；最小飛行頻率fmin=0.1；其它參數(shù)設(shè)置參照差分算法與蝙蝠算法。尋優(yōu)過程中的搜索上界upperBound和搜索下界lowerBound根據(jù)不同測試函數(shù)具體設(shè)置；對比算法的參數(shù)設(shè)置參考了對應的參考文獻。獨立重復實驗進行100次。

表2給出了6種算法在9個測試函數(shù)上進行100次對比實驗后的平均結(jié)果，worst為最壞值，avg為平均值、std為標準方差。表3給出了6種算法在9個測試函數(shù)上的尋優(yōu)成功率。其中f1～f5維度為30dim，f6～f9維度為2dim。

表2 6種算法對比的實驗結(jié)果

為了更加直觀地觀察到收斂情況，給出尋優(yōu)進化曲線，圖1至圖5給出了f1～f5的尋優(yōu)進化曲線；圖6至圖9給出了f6～f9的尋優(yōu)進化曲線。圖中的縱坐標均為log10(Fitness)，取適應度值的對數(shù)，由于Six-Hump Camel-Back測試函數(shù)的最優(yōu)值為負數(shù)，因此不取對數(shù)，為適應度原始值。

4.3 收斂性分析

在測試函數(shù)f1、f3、f4、f8的優(yōu)化過程中，分析圖1、圖3、圖4、圖8：在尋優(yōu)前期，在相同迭代次數(shù)情況下，BADE算法的收斂速度和收斂精度均優(yōu)于其它5種算法。分析表2對應的平均解avg：BADE找到了最優(yōu)值，且不亞于其它5種算法。

表3 f1～f9:6種算法尋優(yōu)成功率

圖1 f1尋優(yōu)進化曲線

圖2 f2尋優(yōu)進化曲線

圖3 f3尋優(yōu)進化曲線

圖4 f4尋優(yōu)進化曲線

圖5 f5尋優(yōu)進化曲線

圖6 f6尋優(yōu)進化曲線

圖7 f7尋優(yōu)進化曲線

圖8 f8尋優(yōu)進化曲線

圖9 f9尋優(yōu)進化曲線

在測試函數(shù)f2、f5的尋優(yōu)過程中，分析圖2、圖5：在尋優(yōu)前期，迭代次數(shù)相同，BADE的收斂速度和收斂精度均優(yōu)于其它5種對比算法；在尋優(yōu)后期，6種算法均陷入局部最優(yōu)。分析表2對應的平均解avg：迭代結(jié)束時，對于f2， BADE尋找到的平均解avg優(yōu)于其它5種算法；對于f5， BADE尋找到的平均解avg不亞于其它5種算法。

在測試函數(shù)f7的尋優(yōu)過程中，分析圖7：BADE在尋優(yōu)前期的收斂速度和收斂精度不亞于其它5種算法；分析表2對應的平均解avg：在迭代結(jié)束時，尋找到的平均解也不亞于其它5種算法。

在測試函數(shù)f6、f9的尋優(yōu)過程中，分析圖6、圖9：在尋優(yōu)前期，BADE的收斂速度和收斂精度略優(yōu)于其它5種算法。分析表2對應的平均解avg：迭代結(jié)束時，BADE算法的平均解avg不亞于其它5種算法。

綜上，BADE算法的總體收斂性能優(yōu)于其它5種算法。

4.4 尋優(yōu)成功率分析

設(shè)置尋優(yōu)精度λ=10-5，尋優(yōu)成功定義為：尋找到的最優(yōu)解與理論最優(yōu)解差值小于該尋優(yōu)精度。由表3的尋優(yōu)成功率可知：對于f2和f9， 6種算法均沒有找到理論最優(yōu)解。對于f1、f3、f4、f5、f6、f7、f8， BADE的尋優(yōu)成功率均為100%優(yōu)于其它5種對比算法。

綜上，BADE的總體尋優(yōu)成功率優(yōu)于其它5種對比算法。

4.5 魯棒性分析

算法魯棒性可從標準方差std的大小反映出來，方差越小，魯棒性越好；反之，算法的魯棒性也就越差。分析表2中標準方差std一欄，在f1、f3、f4、f5、f8的尋優(yōu)過程中，BADE算法的標準方差std均為0，表現(xiàn)出較好的魯棒性。在f2尋優(yōu)過程中，標準方差std比BA、DE、SPSO、GPSO小，略大于FWA；在f6尋優(yōu)過程中，BADE的標準方差std比BA、SPSO、FWA小，略大于DE和GPSO；在f7、f9尋優(yōu)過程中，標準方差std比BA、FWA小，略大于DE、SPSO、GPSO。

綜上，BADE的總體魯棒性優(yōu)于其它5種對比算法。

4.6 討 論

BADE混合算法表現(xiàn)出較好的性能主要是由于以下原因：

第一，利用蝙蝠回聲定位的特點，加強對當前最優(yōu)解附近的局部搜索，加快了收斂速度;

第二，差分種群與蝙蝠種群個體在整個尋優(yōu)過程中，協(xié)同交互，及時反饋，加強了信息交互，做到協(xié)同智能；

第三，高斯擾動提高了種群多樣性，有效防止了迭代過程中因陷入局部最優(yōu)而導致的更新停滯，有利于跳出局部最優(yōu)。

本文提出了一種蝙蝠差分混合算法，其主要思想是利用蝙蝠回聲定位的特點，在當前最優(yōu)解附近進行詳細的局部搜索，同時高斯擾動的加入提高了種群多樣性。雙種群在尋優(yōu)過程中，可以信息交流，優(yōu)勢互補，有效平衡了全局搜索和局部開發(fā)能力，在求解精度和穩(wěn)定性表現(xiàn)出較好的性能。

5 算法應用

5.1 0-1背包問題

鑒于BADE在連續(xù)優(yōu)化問題上有較好的表現(xiàn)，將BADE應用于離散優(yōu)化問題是個合理的方向，離散優(yōu)化是最優(yōu)化領(lǐng)域的一個非常重要的方面，是應用數(shù)學和計算機科學中優(yōu)化問題的重要分支。0-1背包問題(knapsack problem，KP)是典型的整型優(yōu)化問題，數(shù)學模型如下

(12)

(13)

其中，n是物品數(shù)量，pi是第i個物品的價值，vi是第i個物品的體積，Vmax是背包的最大容量，xi是第i個物品的狀態(tài)，0表示不被裝進背包，1表示被裝進背包。不允許部分裝入也不允許重復裝入。

0-1背包問題求解的是在背包最大容量限制下，使得裝入物品的總價值最大。將問題轉(zhuǎn)換成最小化問題[18]，目標函數(shù)為

(14)

5.2 算法離散化設(shè)計

0-1背包問題屬于離散類型問題，在算法應用時應將差分種群個體以及蝙蝠種群個體的位置信息進行離散化

(15)

其中，x′(i,j) 是離散前位置，x(i,j) 是離散后位置。

BADE混合算法求解0-1背包問題的具體操作如Algorithm 3所示：

步驟1 初始化蝙蝠種群、差分種群；

步驟2 差分種群分別根據(jù)式(1)、式(2)、式(3)進行變異、交叉、選擇操作；

步驟3 按照式(15)對當前位置信息進行離散化處理之后，按照式(14)評估適應度值；

步驟4 按照式(10)在gbest附近高斯擾動，產(chǎn)生局部解，按照式(15)離散化處理，按照式(14)評估適應度值；

步驟5 更新響度和脈沖；

步驟6 判斷是否接受新解，如果接受，更新gbest；

步驟7 重復步驟2～步驟6，達到終止條件，則終止迭代。

5.3 對比實驗

對于其它5種對比算法(BA，DE，SPSO，GPSO，F(xiàn)WA)進行同樣的離散化處理之后，對實驗結(jié)果進行比較。選用了表4中的5個常見0-1背包問題[17]。

表4 5個常見背包問題

5.4 實驗結(jié)果與分析

參數(shù)設(shè)置：最大迭代次數(shù)max_it=500；獨立重復運行次數(shù)run_num=50；其它參數(shù)設(shè)置參照4.3小節(jié)，對比實驗的結(jié)果見表5。

表5的實驗結(jié)果顯示：由max這一欄可知，6種算法對于這5個0-1背包問題都能找到最優(yōu)解f*； 由std這一欄可知：只有BADE對于這5個0-1背包問題對應的標準方差值均為0，這反映了BADE對于其它5種算法具有更優(yōu)的魯棒性；由SR這一欄可知：BADE對于其它5種算法具有更高的尋優(yōu)正確率。綜上，BADE算法在求解表5中給出的5個常見的0-1背包問題時，總體性能優(yōu)于其它5種對比算法。

6 結(jié)束語

利用蝙蝠種群和差分種群的協(xié)同智能，本文提出了一種混合算法——蝙蝠差分混合算法。高斯擾動能夠增加種群的多樣性，避免算法陷入局部最優(yōu)。協(xié)同智能能夠有效的平衡全局搜索和局部開發(fā)能力。通過仿真對比實驗，我們驗證了蝙蝠差分混合算法具有較好的尋優(yōu)能力，有著更快的收斂速度和更好的收斂精度。在未來研究工作中，將嘗試從理論研究角度對將蝙蝠差分混合算法的收斂性進行分析，并與其它工程應用相結(jié)合。

表5 5個0-1背包問題的實驗對比結(jié)果