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

(廣西大學(xué) 計算機與電子信息學(xué)院，廣西 南寧 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īng)用在工程優(yōu)化問題[2]、大數(shù)據(jù)分析[3]、云計算[4]、數(shù)據(jù)分類[5]等領(lǐng)域。

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

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

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ā)出聲波。利用所在的位置的目標(biāo)函數(shù)值來評估位置的優(yōu)劣。蝙蝠種群個體通過速度和飛行頻率的變化來進行位移，通過響度和脈沖的變化，來靠近最優(yōu)解。標(biāo)準(zhǔn)蝙蝠算法使用式(4)至式(6)對飛行頻率、速度和位置進行更新

fi=fmin+(fmax-fmin)β

(4)

(5)

(6)

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

(7)

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

2.2 響度和脈沖

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

(8)

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

(9)

3 差分蝙蝠混合算法

3.1 協(xié)同智能

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

具體操作為：當(dāng)?shù)趇個蝙蝠種群個體發(fā)出的脈沖r(i)小于隨機脈沖且響度A(i)大于隨機響度時，對差分種群得到的當(dāng)前最優(yōu)解gbest進行高斯擾動產(chǎn)生局部解Batx(i)，相當(dāng)于在gbest附近進行一次詳細(xì)搜索。并對Batx(i)進行評價，并與差分種群的第i個個體X(i)的適應(yīng)度值相對比，如果蝙蝠個體更優(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īng)度值來判斷局部解的優(yōu)劣，并以脈沖和響度條件作為約束，當(dāng)滿足式(11)時，局部解將加入下一次迭代，完成蝙蝠種群和差分種群的信息交互

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

(11)

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

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

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

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

步驟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 重復(fù)步驟2～步驟4的步驟，達(dá)到終止條件之后，終止迭代。

4 仿真實驗

4.1 測試函數(shù)

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

表1 基準(zhǔn)測試函數(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è)置參考了對應(yīng)的參考文獻。獨立重復(fù)實驗進行100次。

表2給出了6種算法在9個測試函數(shù)上進行100次對比實驗后的平均結(jié)果，worst為最壞值，avg為平均值、std為標(biāo)準(zhǔn)方差。表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)進化曲線。圖中的縱坐標(biāo)均為log10(Fitness)，取適應(yīng)度值的對數(shù)，由于Six-Hump Camel-Back測試函數(shù)的最優(yōu)值為負(fù)數(shù)，因此不取對數(shù)，為適應(yīng)度原始值。

4.3 收斂性分析

在測試函數(shù)f1、f3、f4、f8的優(yōu)化過程中，分析圖1、圖3、圖4、圖8：在尋優(yōu)前期，在相同迭代次數(shù)情況下，BADE算法的收斂速度和收斂精度均優(yōu)于其它5種算法。分析表2對應(yīng)的平均解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對應(yīng)的平均解avg：迭代結(jié)束時，對于f2， BADE尋找到的平均解avg優(yōu)于其它5種算法；對于f5， BADE尋找到的平均解avg不亞于其它5種算法。

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

在測試函數(shù)f6、f9的尋優(yōu)過程中，分析圖6、圖9：在尋優(yōu)前期，BADE的收斂速度和收斂精度略優(yōu)于其它5種算法。分析表2對應(yīng)的平均解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 魯棒性分析

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

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

4.6 討 論

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

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

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

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

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

5 算法應(yīng)用

5.1 0-1背包問題

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

(12)

(13)

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

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

(14)

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

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

(15)

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

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

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

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

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

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

步驟5 更新響度和脈沖；

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

步驟7 重復(fù)步驟2～步驟6，達(dá)到終止條件，則終止迭代。

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；獨立重復(fù)運行次數(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背包問題對應(yīng)的標(biāo)準(zhǔn)方差值均為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)能力，有著更快的收斂速度和更好的收斂精度。在未來研究工作中，將嘗試從理論研究角度對將蝙蝠差分混合算法的收斂性進行分析，并與其它工程應(yīng)用相結(jié)合。

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