莫海淼,趙志剛,曾 敏,石 靜,溫 泰

(廣西大學(xué) 計(jì)算機(jī)與電子信息學(xué)院,南寧 530004)

1 前 言

煙花算法(Fireworks Algorithm,FWA)[1]是由Tan等人于2010年提出的,并且被廣泛應(yīng)用于JSP問題的求解[2]、聚類[3]、網(wǎng)絡(luò)規(guī)劃[4]、圖像識(shí)別[5]、函數(shù)優(yōu)化[6]等領(lǐng)域.

從此之后,煙花算法吸引了越來越多的學(xué)者對(duì)其進(jìn)行深入的研究.通過對(duì)原始煙花算法進(jìn)行深入的研究分析,并針對(duì)FWA的不足,一些研究者提出了相關(guān)的改進(jìn)方法.改進(jìn)煙花算法主要可以被分為兩類[7],一類是在基本煙花算法的基礎(chǔ)上進(jìn)行算子的分析和改進(jìn),另一類是與其他啟發(fā)式算法的混合算法的研究.第一類對(duì)煙花算法改進(jìn)的工作主要有:Liu等提出一種構(gòu)造型煙花算法(IFWA)[8],它引入一種新型的爆炸半徑和爆炸火花數(shù)目計(jì)算方式,讓擁有較好適應(yīng)度值的煙花在更小的爆炸半徑內(nèi)產(chǎn)生更多的爆炸火花.Zheng等[9]人針對(duì)算子存在的缺陷提出了相應(yīng)的改進(jìn)策略,最終提出EFWA.文獻(xiàn)[10]和文獻(xiàn)[11]均是對(duì)最優(yōu)的煙花個(gè)體引入了自適應(yīng)的爆炸半徑,并提高了算法的性能.李席廣等[12]將反向?qū)W習(xí)與動(dòng)態(tài)記憶反饋的思想引入煙花算法,提出了一種新的煙花算法,并得到不錯(cuò)的實(shí)驗(yàn)效果.Li 等[13]從信息利用的角度,在煙花算法中充分利用了爆炸火花的信息,并提出了 GFWA.方柳平等[14]通過嵌入一種利用歷史成功信息生成兩種不同的學(xué)習(xí)因子來改進(jìn)dynFWA,來平衡算法的局部搜索和全局搜索能力.第二類對(duì)煙花算法改進(jìn)的工作主要有:Gao 等[15]人將文化算法和煙花算法混合,改變了煙花算法中爆炸火花產(chǎn)生方式和選擇策略,提出了CA-FWA算法.Yu等[16]人將差分演化算法的差分變異算子替換煙花算法的高斯變異算子,并提出了FWA-DM.Zhang等[17]將生物地理學(xué)優(yōu)化算法的遷移算子引入煙花算法,提出了具有較強(qiáng)勘探能力的BBO-FWA算法.為了進(jìn)一步提高標(biāo)準(zhǔn)煙花算法的性能,本文將蝙蝠算法(Bat Algorithm,BA)[18]的局部搜索機(jī)制引入到煙花算法,以協(xié)助煙花算法尋優(yōu);并利用蝙蝠種群與煙花種群的位置信息構(gòu)造了新的爆炸半徑,使其能夠自適應(yīng)地調(diào)整步長(zhǎng);最后,使用“精英-隨機(jī)”策略選擇下一代煙花,以及對(duì)全局最優(yōu)個(gè)體進(jìn)行高斯擾動(dòng),來保證種群的多樣性,避免過快地陷入局部最優(yōu)解.基于以上的思想,本文提出了蝙蝠煙花混合算法,并使用十個(gè)常用的基準(zhǔn)函數(shù)以及五個(gè)0-1背包問題對(duì)蝙蝠煙花混合算法的性能進(jìn)行測(cè)試,并與經(jīng)典的蝙蝠算法、粒子群算法、煙花算法等五種算法進(jìn)行對(duì)比實(shí)驗(yàn).

2 混合算法

2.1 協(xié)同尋優(yōu)

蝙蝠個(gè)體根據(jù)回聲定位的原理,以及發(fā)出的脈沖和響度信息來判斷獵物的位置來定位獵物,即當(dāng)蝙蝠個(gè)體在當(dāng)前最優(yōu)解gbest附近進(jìn)行局部搜索時(shí),如果它所處的位置更接近獵物,則將脈沖調(diào)整變大,同時(shí)把響度調(diào)小,然后繼續(xù)搜尋和定位獵物,并不斷地靠近獵物.這就是蝙蝠算法局部搜索的基本原理.將蝙蝠算法的局部搜索引入煙花算法,并協(xié)助煙花算法尋優(yōu),把這個(gè)過程稱作協(xié)同尋優(yōu).協(xié)同尋優(yōu)是指在尋優(yōu)過程中,蝙蝠種群根據(jù)蝙蝠發(fā)出的脈沖和響度在最優(yōu)煙花gbest附近協(xié)助煙花種群尋優(yōu),并且加強(qiáng)兩個(gè)種群在尋優(yōu)過程中的信息交流,其主要操作是初始化一個(gè)蝙蝠種群BatX(用來存放全局最優(yōu)煙花gbest附近產(chǎn)生的局部解),假設(shè)第i個(gè)蝙蝠個(gè)體發(fā)出的脈沖r(i)小于隨機(jī)脈沖時(shí),則對(duì)gbest進(jìn)行高斯擾動(dòng)之后產(chǎn)生一個(gè)局部解BatX(i),然后對(duì)該蝙蝠個(gè)體的位置信息BatX(i)進(jìn)行評(píng)價(jià):假如該蝙蝠個(gè)體的適應(yīng)度值優(yōu)于煙花種群的第i個(gè)煙花X(i),且它產(chǎn)生的響度A(i)大于隨機(jī)生成的響度時(shí),則該蝙蝠個(gè)體被加入煙花種群中,其操作如公式(1)和公式(2)所示.

BatX(i)=gbest*(N(0,1)+1),as r(i)

(1)

其中,i=1,2,…,popsize;N(0,1)是服從均值為0,方差為1的高斯分布函數(shù);r(i)是第i個(gè)蝙蝠個(gè)體發(fā)出的脈沖;rand是[0,1]范圍內(nèi)服從均勻分布的隨機(jī)數(shù).

X(i)=BatX(i),asf(BatX(i))rand

(2)

其中,X(i)是第i個(gè)煙花所在的位置;A(i)是第i個(gè)蝙蝠發(fā)出的響度;rand是[0,1]范圍內(nèi)服從均勻分布的隨機(jī)數(shù).

蝙蝠種群通過發(fā)出的脈沖信息在全局最優(yōu)煙花gbest附近產(chǎn)生一個(gè)局部解;并使用蝙蝠個(gè)體發(fā)出的響度、脈沖與所處位置的優(yōu)劣來更新煙花種群.這樣,蝙蝠種群與煙花種群不斷地進(jìn)行交互,協(xié)同尋優(yōu),而公式(1)和公式(2)相結(jié)合則加強(qiáng)蝙蝠種群和粒子群在尋優(yōu)過程中的信息交互,協(xié)同尋優(yōu).協(xié)同尋優(yōu)的操作如算法1所示.

算法1.協(xié)同尋優(yōu).

輸入:蝙蝠種群的位置BatX.

輸出:煙花種群的位置X和全局最優(yōu)煙花個(gè)體gbest.

Begin

1. for i=1:popsize

2. if r(i)

3. 按公式(1)產(chǎn)生一個(gè)局部解;

4. endif

5. 越界處理;

6. 計(jì)算該局部解的適應(yīng)度值f(BatX(i));

7. iff(BatX(i))rand

8. X(i)= BatX(i);

9. 更新脈沖r(i)和響度A(i);

10. endif

11. iff(BatX(i))

12. gbest = BatX(i);

13. endif

14. endfor

End

2.2 自適應(yīng)步長(zhǎng)

當(dāng)煙花的爆炸火花數(shù)達(dá)到當(dāng)前最大時(shí),本文使用蝙蝠算法在最優(yōu)位置附近產(chǎn)生局部解的位置BatX、蝙蝠發(fā)出的頻率Q、煙花位置X、全局最優(yōu)煙花個(gè)體gbest來構(gòu)造新的爆炸半徑,其具體操作如公式(3)所示.

(3)

其中,X(i)是第i個(gè)煙花的位置;BatX(i)的含義與公式(1)相同;Si是指第i個(gè)煙花個(gè)體產(chǎn)生的爆米花數(shù)量;Qi是指第i個(gè)蝙蝠個(gè)體產(chǎn)生的頻率;AvgS是指此時(shí)煙花種群產(chǎn)生爆炸火花數(shù)量的平均值,即

(4)

其中,popsize是指煙花個(gè)體的數(shù)量.

將公式(3)代入公式(4)之后,可知:當(dāng)?shù)趇個(gè)煙花個(gè)體的爆炸火花數(shù)量大于平均爆炸火花數(shù)時(shí),則該煙花個(gè)體往全局最優(yōu)附近產(chǎn)生的一個(gè)局部解Batx(i)靠攏;當(dāng)煙花個(gè)體產(chǎn)生的爆炸火花數(shù)小于平均爆炸火花數(shù)時(shí),則該煙花個(gè)體往gbest靠攏.假設(shè)此時(shí)產(chǎn)生爆炸火花數(shù)量最多的煙花個(gè)體也往gbest靠攏,就相當(dāng)于該煙花個(gè)體沒有產(chǎn)生位移,這樣便浪費(fèi)了該煙花個(gè)體的資源;若該煙花個(gè)體向gbest附近的局部解BatX(i)靠攏時(shí),則充分發(fā)揮了該煙花個(gè)體的作用,并使它在全局最優(yōu)gbest附近進(jìn)行詳細(xì)的局部搜索,而蝙蝠發(fā)射出隨機(jī)的頻率Qi,則保證了該煙花個(gè)體在gbest附近搜索的隨機(jī)性.使用蝙蝠與煙花的位置信息來構(gòu)造新的爆炸半徑,這樣便能使粒子能夠自適應(yīng)地調(diào)整步長(zhǎng).此時(shí),煙花位移操作如下:

Xnew(i)=X(i)+R(i)

(5)

2.3 “精英-隨機(jī)”策略

本文采取 “精英-隨機(jī)”選擇策略來選擇下一代的煙花,即從煙花、煙花產(chǎn)生高斯變異之后的高斯煙花、煙花爆炸后產(chǎn)生的所有爆炸火花這三者共同組成候選集,從候選集中選取適應(yīng)度值最好的個(gè)體作為下一代煙花的“精英”(僅有一個(gè)),其他popsize-1個(gè)下一代的煙花則從候選集中隨機(jī)選取(可以重復(fù)選擇).選擇下一代煙花的具體操作為:將候選集以適應(yīng)度值進(jìn)行升序排序,然后選擇適應(yīng)度值最好的個(gè)體作為下一代的其中一個(gè)煙花,下一代其他煙花的選取則根據(jù)候選集的下標(biāo)進(jìn)行隨機(jī)選取.

2.4 混合算法

綜上所述,本文提出一種新的算法——蝙蝠煙花混合算法(the hybrid Bat and Fireworks Algorithm,BAFWA).BAFWA算法的偽代碼如算法2所示.

算法2.本文蝙蝠煙花混合算法的具體過程.

輸入:蝙蝠種群的位置、煙花種群的位置.

輸出:蝙蝠種群更新之后的位置、煙花種群更新之后的位置、全局最優(yōu)個(gè)體gbest.

Begin

1.初始化蝙蝠種群BatX、煙花種群X、最優(yōu)個(gè)體gbest以及兩個(gè)種群的相關(guān)參數(shù);

2.使用蝙蝠種群協(xié)助煙花種群尋優(yōu):具體參照算法1;

3.計(jì)算爆炸火花的數(shù)量;

4.按公式(3)和公式(4)來計(jì)算爆炸半徑;

5.產(chǎn)生爆炸火花,并按公式(5)進(jìn)行位移操作;

6.越界處理;

7.產(chǎn)生高斯煙花;

8.用2.3小節(jié)的“精英-隨機(jī)”策略來選擇下一代煙花;

9.重復(fù)步驟2至步驟8,若達(dá)到終止條件(一般為達(dá)到設(shè)定的尋優(yōu)精度或者達(dá)到最大的迭代次數(shù)),則停止迭代.

End

表1 基準(zhǔn)函數(shù)
Table 1 Benchmark functions

FunNameFuntionDomainDimOptimumSpheref1(x)=∑ni=1x2i[-100,100]d300Rosenbrockf2(x)=∑ni=1[100(xi+1-xi)2+(xi-1)2][-10,10]d300Griewankf3(x)=14000∑ni=1x2i-∏ni=1cos(xii)+1[-600,600]d300Rastriginf4(x)=∑ni=1(x2i-10cos(2πxi)+10)[-5.12,5.12]d300Ackleyf5(x)=-20exp(-0.2∑ni=1x2i)-exp(1n)∑ni=1cos(2πxi)+20+e[-32,32]d300Schwefelf6(x)=∑ni=1(∑nj=1xj)2[-100,100]d300Six-HumpCamel-Backf7(x)=4x21-2.1x41+13x61+x1x2-4x22+4x42[-5,5]22-1.0316285GoldsteinPricef8(x)=[1+(x1+x2+1)2(19-14x1+3x21-14x2+6x1x2+3x22)]·[30+(2x1-3x2)2(18-32x1+12x21+48x2-36x1x2+27x22)][-2,2]223Schaffer′sF6f9(x)=sin2x21+x22-0.5[1+0.001(x21+x22)]2+0.5[-100,100]220Braninf10(x)=(x2-5.14π2x21+5πx1-6)2+10(1-18π)cosx1+10-5

3 仿真實(shí)驗(yàn)

3.1 測(cè)試函數(shù)

本文選用了如表1所示的10個(gè)測(cè)試函數(shù)來測(cè)試BAWFA混合算法的性能,并與蝙蝠算法BA、煙花算法FWA、標(biāo)準(zhǔn)粒子群算法[19,20](Standard Particle Swarm Optimization,SPSO)、增強(qiáng)煙花算法(Enhanced Fireworks Algorithm,EFWA)[9]、 自適應(yīng)煙花算法(Adaptive Fireworks Algorithm,AFWA)[11]進(jìn)行對(duì)比實(shí)驗(yàn).

3.2 參數(shù)設(shè)置

本文對(duì)比實(shí)驗(yàn)的相關(guān)參數(shù)是根據(jù)相關(guān)文獻(xiàn)的建議來進(jìn)行設(shè)置的.其中,蝙蝠算法的參數(shù)設(shè)置參照文獻(xiàn)[18];標(biāo)準(zhǔn)粒子群算法的參數(shù)設(shè)置參照文獻(xiàn)[19,20];煙花算法的參數(shù)設(shè)置參照文獻(xiàn)[1];增強(qiáng)煙花算法的參數(shù)設(shè)置參照文獻(xiàn)[9];自適應(yīng)煙花算法的參數(shù)設(shè)置參照文獻(xiàn)[11];蝙蝠煙花混合算法的最小頻率設(shè)置為0.1,最大頻率設(shè)置為100,popsize設(shè)置為10,其他參數(shù)設(shè)置參照蝙蝠算法與煙花算法;六種算法的尋優(yōu)精度均設(shè)置為λ=10-5,即到達(dá)尋優(yōu)精度時(shí),則標(biāo)記成功尋優(yōu)一次.本文對(duì)表1的測(cè)試函數(shù)做了100次獨(dú)立重復(fù)實(shí)驗(yàn),最大迭代次數(shù)MaxIteration=1000.

3.3 收斂性分析

對(duì)表1的10個(gè)測(cè)試函數(shù)進(jìn)行測(cè)試得到最差值worst、最好值best、平均值avg、標(biāo)準(zhǔn)偏差std如表2所示;尋優(yōu)成功率SR如表3所示.為了縮減篇幅,本文只給出部分的演化曲線圖,如圖1-圖6(測(cè)試函數(shù)進(jìn)化曲線的適應(yīng)度值均取對(duì)數(shù)log10,即其縱坐標(biāo)為log10Fitness)所示.

圖1 f1尋優(yōu)演化曲線Fig.1 Evolution curve of f1

由圖1可知,在優(yōu)化f1函數(shù)的過程中,BA、SPSO、EFWA和AFWA的收斂曲線較平緩,說明這4種算法的種群多樣性較差,極易陷入局部最優(yōu)解;而BAFWA的收斂曲線較陡峭,其收斂速度優(yōu)于其他5種算法;在尋優(yōu)過程中,BAFWA不到100次迭代,就已經(jīng)尋找到最優(yōu)解0(由于尋優(yōu)曲線圖的縱坐標(biāo)是log10Fitness,而尋找到最優(yōu)解0時(shí),即Fitness=0,此時(shí)的尋優(yōu)曲線在圖上無法顯示);而其他5種算法在迭代終止時(shí)也沒有尋找到最優(yōu)解0.由表2中f1的實(shí)驗(yàn)數(shù)據(jù)可知,在迭代結(jié)束(iteration=1000)時(shí),BAFWA尋找到的平均解avg均優(yōu)于其他5種算法,故BAFWA的收斂精度優(yōu)于其他5種算法.綜上可知,在f1函數(shù)的尋優(yōu)過程中,BAFWA的收斂性能優(yōu)于其他5種算法.

圖2 f3尋優(yōu)演化曲線Fig.2 Evolution curve of f3

由圖2、圖3、圖5和圖6可知,在優(yōu)化函數(shù)f3、f4、f6和f9的過程中,在迭代結(jié)束之后BAFWA和FWA都尋找到最優(yōu)解,其他四種算法沒有尋找到最優(yōu)解且在尋優(yōu)后期陷入局部最優(yōu)解;在迭代次數(shù)相同時(shí),BAFWA的收斂速度和收斂精度均優(yōu)于其他5種算法.由表2中f3、f4、f6和f9的實(shí)驗(yàn)數(shù)據(jù)可知,在迭代結(jié)束時(shí),BAFWA和FWA尋找到的平均解均相同,且優(yōu)于其他4種算法.綜上可知,在f3、f4、f6和f9的尋優(yōu)過程中,BAFWA的收斂性能均優(yōu)于其他5種算法.

圖3 f4尋優(yōu)演化曲線Fig.3 Evolution curve of f4

圖4 f5尋優(yōu)演化曲線Fig.4 Evolution curve of f5

由圖4可知:在優(yōu)化f5函數(shù)的過程中,在迭代結(jié)束之后6種算法均沒有尋找到最優(yōu)解;在尋優(yōu)前期,迭代次數(shù)相同時(shí),BAFWA的收斂速度和收斂精度均優(yōu)于其他5種算法.由表2中f5的實(shí)驗(yàn)數(shù)據(jù)可知,在迭代結(jié)束后,BAFWA和FWA尋找到的平均解均相同,且優(yōu)于其他4種算法.綜上可知,在f5函數(shù)的尋優(yōu)過程中,BAFWA的收斂性能均優(yōu)于其他5種算法.

圖5 f6尋優(yōu)演化曲線Fig.5 Evolution curve of f6

由表2中f2的實(shí)驗(yàn)數(shù)據(jù)可知:在迭代結(jié)束之后,6種算法均沒有尋找到最優(yōu)解,但是BAFWA尋找到的平均解avg優(yōu)于其他5種算法.

圖6 f9尋優(yōu)演化曲線Fig.6 Evolution curve of f9

由表2中f7的實(shí)驗(yàn)數(shù)據(jù)可知:在迭代結(jié)束之后,BAFWA尋找到的平均解avg劣于SPSO、AFWA、EFWA,卻不亞于其他3種算法.

由表2中f8的實(shí)驗(yàn)數(shù)據(jù)可知:在迭代結(jié)束之后,BAFWA尋找到的平均解avg與SPSO、AFWA、EFWA相同,并且優(yōu)于其他2種算法.

由表2中f10的實(shí)驗(yàn)數(shù)據(jù)可知:在迭代結(jié)束之后,BAFWA尋找到的平均解avg優(yōu)于FWA,卻劣于其他4種算法.

3.4 魯棒性分析

標(biāo)準(zhǔn)偏差的大小反映了算法魯棒性的好壞,即標(biāo)準(zhǔn)偏差越小,則算法的魯棒性越好;反之,則算法的魯棒性越差.

由表2的實(shí)驗(yàn)數(shù)據(jù)std可知,在f1、f3、f4、f5和f9尋優(yōu)過程中,BAFWA和FWA的魯棒性一樣好(在f5的尋優(yōu)過程中,雖然EFWA的魯棒性與BAFWA相同,但它的平均解avg劣于BAFWA),且均優(yōu)于其他4種算法;在f2的尋優(yōu)過程中,BAFWA的魯棒性優(yōu)于其他5種算法;在f6的尋優(yōu)過程中,BAFWA和SPSO的魯棒性一樣好,且均優(yōu)于其他4種算法;在f7的尋優(yōu)過程中,BAFWA的魯棒性優(yōu)于BA、FWA,卻劣于其他3種算法;在f8的尋優(yōu)過程中,BAFWA的魯棒性優(yōu)于BA、FWA、EFWA,卻劣于其他2種算法;在f10的尋優(yōu)過程中,BAFWA的魯棒性優(yōu)于FWA,卻劣于其他4種算法.因此,綜上所述,在十個(gè)基準(zhǔn)函數(shù)的尋優(yōu)過程中,BAFWA的魯棒性總體較好.

表2 十種基準(zhǔn)函數(shù)的四種算法比較
Table 2 Comparison of four algorithms for ten benchmark functions

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

表3 十個(gè)基準(zhǔn)函數(shù)的尋優(yōu)成功率
Table 3 Success rate(%)for ten benchmark functions

由表3可知,將尋優(yōu)精度設(shè)置為λ=10-5,則在迭代結(jié)束后,6種算法在f2和f10的尋優(yōu)成功率均為0%,而BAFWA在剩余其他8個(gè)基準(zhǔn)函數(shù)的尋優(yōu)成功率均為100%;FWA尋優(yōu)成功率為100%的只有6個(gè)基準(zhǔn)函數(shù);BA、SPSO、EFWA和AFWA的整體尋優(yōu)成功率稍差.因此,在十個(gè)基準(zhǔn)函數(shù)的尋優(yōu)過程中,BAFWA總體的尋優(yōu)成功率優(yōu)于其他五種算法.

綜上所述,本文提出的混合算法比其他五種算法具有更好的優(yōu)化性能源自以下幾個(gè)方面:

1)煙花算法引入了蝙蝠算法的局部搜索機(jī)制.蝙蝠算法具有極強(qiáng)的局部搜索能力,并且利用蝙蝠算法在全局最優(yōu)個(gè)體gbest附近進(jìn)行詳細(xì)的局部搜索,以提高種群的收斂性能.

2)利用蝙蝠種群和煙花種群的位置信息構(gòu)造新的爆炸半徑,新的爆炸半徑不僅繼承了兩個(gè)種群的信息,而且能夠自適應(yīng)地調(diào)整步長(zhǎng).

3)“精英-隨機(jī)”策略和高斯擾動(dòng),使種群在尋優(yōu)過程中保持多樣性,避免過快地陷入局部最優(yōu)解.

4)蝙蝠種群和煙花種群協(xié)同尋優(yōu),并且加強(qiáng)了兩個(gè)種群之間的信息交互,也能提高混合算法的收斂性能.

4 算法應(yīng)用

4.1 0-1背包問題

背包問題是一個(gè)典型的NP完全問題.為了進(jìn)一步驗(yàn)證本文提出的算法的有效性,本文將其應(yīng)用于求解0-1背包問題(Knapsack Problem,KP).0-1背包問題的數(shù)學(xué)模型如下:

(6)

(7)

其中,n 為物品的數(shù)量,第i個(gè)物品擁有的價(jià)值和體積分別為pi和vi,背包的最大體積限制用Vmax表示,自變量xi用來表征物品的狀態(tài),有 0 和 1 兩個(gè)數(shù)值可選.當(dāng)xi的值為1時(shí),表示該物品i已經(jīng)被裝入包中,反之,如沒有裝入包中,xi取值為0.每個(gè)物品最多被裝入背包一次,只能全部裝入,不允許部分裝入.

0-1背包問題是具有復(fù)雜約束的最大化問題,對(duì)于這些約束,采用外部罰函數(shù)法進(jìn)行處理.同時(shí),將最大化問題轉(zhuǎn)化為最小化問題,將f(x)轉(zhuǎn)化為-f(x).這樣,0-1背包問題就轉(zhuǎn)化為:

(8)

4.2 混合算法離散化設(shè)計(jì)

由于0-1背包問題是離散問題,因此,需要將煙花個(gè)體和蝙蝠個(gè)體的位置進(jìn)行離散化處理,其具體操作如下:

(9)

其中,x′(i,j)是第i個(gè)個(gè)體第j維所在離散化處理之前的位置信息,x(i,j)是第i個(gè)個(gè)體的第j維所在離散化處理之后的位置信息.

混合算法求解0-1背包問題的偽代碼參照算法1和算法2,但是在計(jì)算個(gè)體的適應(yīng)度值之前,需要對(duì)其所在的位置進(jìn)行離散化處理(參照公式(9)).

4.3 對(duì)比實(shí)驗(yàn)

其他5種對(duì)比算法(BA、SPSO、FWA、EFWA、AFWA)的離散化處理操作具體如下:

(10)

在算法比較的過程中,選用了5個(gè)0-1背包問題[21],具體如表4所示.

表4 五個(gè)常見的背包問題
Table 4 Five common knapsack problems

問題dimf?參數(shù)f11435w=(6,5,9,7)Vmax=20p=(9,11,13,15)f12423w=(2,4,6,7)Vmax=11p=(6,10,12,13)f131052w=(30,25,20,18,17,11,5,2,1,1)Vmax=60p=(20,18,17,15,15,10,5,3,1,1)f147107w=(31,10,20,19,4,3,6)Vmax=50p=(70,20,39,37,7,5,10)f155130w=(15,20,17,8,31)Vmax=80p=(33,24,36,37,12)

4.4 實(shí)驗(yàn)結(jié)果與分析

在求解0-1背包問題的過程中,設(shè)置最大的迭代次數(shù)為500,其他參數(shù)設(shè)置則參照3.2小節(jié),并且進(jìn)行50次獨(dú)立重復(fù)實(shí)驗(yàn),其對(duì)比實(shí)驗(yàn)結(jié)果如表5所示.根據(jù)表5的實(shí)驗(yàn)結(jié)果:由max可知,6種算法均能尋找到最優(yōu)解f*;由方差std可知,在求解5個(gè)0-1背包問題的過程中,BAFWA的魯棒性不亞于其他5種算法;由尋優(yōu)成功率SR可知,BAFWA的總體尋優(yōu)成功率不亞于其他五種算法.因此,綜上可知,BAFWA算法在求解表4的0-1背包問題的整體性能不亞于其他五種算法.

表5 5個(gè)背包問題的對(duì)比實(shí)驗(yàn)結(jié)果
Table 5 Comparation results of 5 knapsack problems

algfmaxavgminstdSR(%)BAf113535350100SPSO3535350100FWA3532.82243.055E+0052AFWA3535350100EFWA3535350100BAFWA3535350100BAf122323230100SPSO2323230100FWA2322.74196.642E-0180AFWA2323230100EFWA2323230100BAFWA2323230100BAf135251.98511.141E-0198SPSO5251.44497.866E-0160FWA5246.94383.644E+006AFWA5252520100EFWA5252520100BAFWA5252520100BAf141071071070100SPSO107104.98933.133E+0050FWA107100.96746.960E+0034AFWA1071071070100EFWA1071071070100BAFWA1071071070100BAf151301301300100SPSO130129.341093.390E+0096FWA130109.8721.446E+0120AFWA1301301300100EFWA1301301300100BAFWA1301301300100

5 結(jié) 論

從本文的仿真對(duì)比實(shí)驗(yàn)中,可以得出這樣的結(jié)論:在求解本文仿真實(shí)驗(yàn)中的相關(guān)問題時(shí),相比其他五種對(duì)比算法,本文提出的蝙蝠煙花混合算法具有相對(duì)更快的收斂速度,更高的收斂精度以及更好的魯棒性.在未來的工作中,將對(duì)蝙蝠煙花混合算法進(jìn)行更深入的理論研究,并將其運(yùn)用到更多的具體工程實(shí)踐中.