劉　藝, 刁興春, 曹建軍, 丁　鯤, 許永平

(1. 解放軍理工大學(xué)指揮信息系統(tǒng)學(xué)院, 江蘇 南京 210007;2. 中國(guó)人民解放軍總參謀部第六十三研究所, 江蘇 南京 210007)

?

求解子集問(wèn)題的鯰魚(yú)效應(yīng)蝙蝠蟻群優(yōu)化

劉藝1, 刁興春2, 曹建軍2, 丁鯤2, 許永平2

(1. 解放軍理工大學(xué)指揮信息系統(tǒng)學(xué)院, 江蘇 南京 210007;2. 中國(guó)人民解放軍總參謀部第六十三研究所, 江蘇 南京 210007)

為求解子集問(wèn)題,提出一種新的基于圖的螞蟻系統(tǒng)——鯰魚(yú)效應(yīng)蝙蝠蟻群優(yōu)化(catfish bat algorithm-ant colony optimization,CBA-ACO)?；谧蛹瘑?wèn)題的構(gòu)造圖,利用路徑概率轉(zhuǎn)移公式進(jìn)行路徑搜索,采用等效路徑信息素增強(qiáng)進(jìn)行信息素更新;動(dòng)態(tài)維護(hù)一定數(shù)量較好路徑作為檔案信息;使用混沌映射并結(jié)合鯰魚(yú)效應(yīng)對(duì)蝙蝠算法(bat algorithm,BA)進(jìn)行改進(jìn),在全局最優(yōu)解多次未更新時(shí),利用檔案信息初始化鯰魚(yú)效應(yīng)增強(qiáng)搜索,返回較好路徑解;采用本輪迭代最優(yōu)更新和增強(qiáng)搜索更新兩種方式更新信息素,兼顧算法的收斂速度和搜索能力。對(duì)算法進(jìn)行了描述并分析算法復(fù)雜度。結(jié)果表明，CBA-ACO具有更好的穩(wěn)定性和獲取較好解的能力。

基于圖的螞蟻系統(tǒng); 蝙蝠算法; 鯰魚(yú)效應(yīng); 混沌映射

0　引　言

優(yōu)化是具有普適性的工程數(shù)學(xué)問(wèn)題,通俗的說(shuō),就是如何尋找到最好的(或理想的)解決方案。背包問(wèn)題(knapsack problem,KP)是一個(gè)具有代表性的求解子集優(yōu)化問(wèn)題(無(wú)序組合優(yōu)化問(wèn)題)[1],它已經(jīng)應(yīng)用在諸多領(lǐng)域中,例如項(xiàng)目選擇、資金分配優(yōu)化、材料切割、貨物裝載等,因此求解背包問(wèn)題具有重要的理論和實(shí)際意義。蟻群優(yōu)化(ant colony optimization,ACO)是一種應(yīng)用廣泛的元啟發(fā)式算法,它是受自然界蟻群共同覓食行為的啟發(fā),由文獻(xiàn)[2]提出的一種啟發(fā)式算法。該算法具有并行分布式計(jì)算、信息正反饋、較強(qiáng)魯棒性、易于與其他算法結(jié)合等優(yōu)點(diǎn),近年來(lái)在各領(lǐng)域得到了快速發(fā)展[3]。它最早被用于解決旅行商問(wèn)題(有序組合優(yōu)化問(wèn)題),取得了較好的效果,隨后在其他組合優(yōu)化問(wèn)題中也得到了運(yùn)用,例如背包問(wèn)題和特征選擇等[4]。求解子集問(wèn)題蟻群算法的基本模型包含3種:第1種是文獻(xiàn)[5]提出的將信息素放在物品上,沒(méi)有路徑的概念,因此信息素的更新對(duì)螞蟻行為的影響具有不確定性,文獻(xiàn)[6-8]在信息素更新環(huán)節(jié)作了不同改進(jìn),但并未改變將信息素放在物品上這一基本模式;第2種是文獻(xiàn)[9]提出的將問(wèn)題轉(zhuǎn)化成帶權(quán)圖,帶權(quán)圖的邊上放置信息素,但該方法沒(méi)有對(duì)問(wèn)題本身的無(wú)序信息進(jìn)行充分利用;第3種是文獻(xiàn)[10]提出了一種基于圖的螞蟻系統(tǒng)(graph-based ant system,GBAS),算法在構(gòu)造圖的基礎(chǔ)上,提出了等效路徑的概念,將問(wèn)題的無(wú)序信息和有向圖的路徑聯(lián)系起來(lái),實(shí)現(xiàn)了將無(wú)序信息轉(zhuǎn)化為有序信息,算法性能得到有效提升。

蝙蝠算法(bat algorithm,BA)是文獻(xiàn)[11]受蝙蝠飛行行為啟發(fā)在2010年提出的一種新型啟發(fā)式算法,它結(jié)合了和聲算法和粒子群算法的優(yōu)點(diǎn),可以看作是兩種方法的混合算法。BA算法提出以來(lái),已經(jīng)有多篇研究將其應(yīng)用在連續(xù)函數(shù)的優(yōu)化問(wèn)題中[12-14],并取得了很好的效果。但是,目前用該算法解決組合優(yōu)化問(wèn)題的成果并不多見(jiàn)。

為了求解子集問(wèn)題,本文提出一種新的基于圖的螞蟻系統(tǒng)——鯰魚(yú)效應(yīng)蝙蝠蟻群優(yōu)化(catfish bat algorithm-ant colony optimization, CBA-ACO)。基于子集問(wèn)題的構(gòu)造圖,采用路徑概率轉(zhuǎn)移公式進(jìn)行路徑搜索,利用等效路徑對(duì)信息素進(jìn)行增強(qiáng)更新;在迭代過(guò)程中,動(dòng)態(tài)維護(hù)一定數(shù)量較好路徑作為檔案信息;使用混沌映射并結(jié)合鯰魚(yú)效應(yīng)對(duì)BA算法進(jìn)行改進(jìn),在全局最優(yōu)解多次未更新時(shí),利用檔案信息初始化鯰魚(yú)效應(yīng)增強(qiáng)搜索,返回較好路徑解;采用本次迭代最優(yōu)更新和增強(qiáng)搜索更新兩種方式更新信息素,兼顧算法的收斂速度和搜索能力。對(duì)采用的鯰魚(yú)效應(yīng),鯰魚(yú)效應(yīng)增強(qiáng)搜索進(jìn)行實(shí)驗(yàn),并進(jìn)行參數(shù)敏感性分析,驗(yàn)證CBA-ACO的有效性以及在尋優(yōu)能力和獲得解的穩(wěn)定性上的優(yōu)越性。

1　相關(guān)理論簡(jiǎn)介

1.1基于圖的螞蟻系統(tǒng)

基于圖的螞蟻系統(tǒng)(graph-based ant system, GBAS)包括以下幾個(gè)組成部分[10]:

(1) 針對(duì)具體問(wèn)題的構(gòu)造圖:一般包括一個(gè)有向圖和若干個(gè)從有向圖到具體問(wèn)題的映射,構(gòu)造圖實(shí)現(xiàn)了問(wèn)題到有向圖表示的映射;

(2) 智能蟻群:每個(gè)智能螞蟻依據(jù)所給定的狀態(tài)轉(zhuǎn)移概率,在有向圖中進(jìn)行依次隨機(jī)行走,構(gòu)造滿足約束條件的可行解,所有螞蟻均完成一次行走過(guò)程后,一次迭代結(jié)束,智能螞蟻死亡;

(3) 螞蟻隨機(jī)移動(dòng)的狀態(tài)轉(zhuǎn)移概率:通過(guò)有向圖邊上的信息素量和啟發(fā)式信息量計(jì)算狀態(tài)轉(zhuǎn)移概率,螞蟻依據(jù)概率信息進(jìn)行獨(dú)立的隨機(jī)行走;

(4) 構(gòu)造圖中有向圖邊上的信息素量:信息素量隨迭代次數(shù)變化,一次迭代完成后,按照一定的規(guī)則對(duì)信息素進(jìn)行更新;

(5) 構(gòu)造圖中有向圖邊上的啟發(fā)式信息:啟發(fā)式信息代表了螞蟻選擇該條邊的期望程度,啟發(fā)式信息為內(nèi)部信息,由問(wèn)題本身的特點(diǎn)決定。

文獻(xiàn)[10]提出的GBAS采用了等效路徑概念,對(duì)包含同一子集解的其他路徑同時(shí)更新信息素,這就增強(qiáng)了算法求解子集問(wèn)題的能力。因此,本文使用包含等效路徑的GBAS作為求解子集問(wèn)題的基本算法模型。

1.2BA算法

蝙蝠是一種特別的生物,其中微型蝙蝠使用回聲定位來(lái)躲避障礙和探測(cè)獵物。多數(shù)微型蝙蝠使用調(diào)頻信號(hào),而其他一些則使用固定頻率的信號(hào),但是它們?cè)矶际腔诨芈暥ㄎ坏穆晫W(xué)原理。文獻(xiàn)[11]受到微型蝙蝠這種回聲定位的飛行行為方式啟發(fā),于2010年提出了BA算法。BA算法包括信號(hào)頻率的變化,速度和位置的更新以及響度的變化,而蝙蝠的速度和位置的更新策略與標(biāo)準(zhǔn)粒子群算法(particle swarm optimization,PSO)更新速度和位置的策略有很多相似之處。實(shí)質(zhì)上,PSO與和聲搜索都是BA在適當(dāng)簡(jiǎn)化下的特殊情況[15],結(jié)合了兩種方法的優(yōu)點(diǎn)。本文在算法全局最優(yōu)解多次未更新的情況下使用BA,在更廣闊的空間中尋找較好解,提高算法的全局搜索能力。

1.3鯰魚(yú)效應(yīng)

鯰魚(yú)效應(yīng)是指在某個(gè)進(jìn)化群體中,個(gè)體的更新處于基本停滯的狀態(tài)下引入若干性能優(yōu)越的個(gè)體而激活整個(gè)群體進(jìn)化能力的負(fù)反饋策略,它最初是由販賣(mài)沙丁魚(yú)的商人通過(guò)加入鯰魚(yú)保持其活性的行為而被發(fā)現(xiàn),隨后在金融界和企業(yè)管理中,管理人員也通過(guò)使用鯰魚(yú)效應(yīng)引入競(jìng)爭(zhēng)機(jī)制,從而提高自身的競(jìng)爭(zhēng)力。文獻(xiàn)[16]將鯰魚(yú)效應(yīng)與粒子群算法相結(jié)合,通過(guò)使用具有優(yōu)秀性能的鯰魚(yú)粒子,改善了算法求解復(fù)雜優(yōu)化問(wèn)題的能力。本文借鑒鯰魚(yú)效應(yīng)對(duì)BA進(jìn)行改進(jìn),在BA即將陷入局部最優(yōu)時(shí)啟動(dòng)鯰魚(yú)效應(yīng),避免過(guò)早收斂,提高算法的全局探測(cè)能力。

2　CBA-ACO優(yōu)化

2.1路徑搜索和信息素更新

求解子集問(wèn)題的基于圖的螞蟻系統(tǒng)具體模型如圖1所示[10]。

圖1　子集問(wèn)題構(gòu)造圖的有向圖Fig.1　Directed graph of subset problem’s structure graph

圖1中,n為備選集的基數(shù);q為所求子集的最大可能基數(shù);eij表示在第j步選擇第i個(gè)元素。

在GBAS中使用的路徑概率轉(zhuǎn)移公式為[8]

(1)

式中,禁忌表tabum(m=1,2,…,M)記錄第m只螞蟻?zhàn)哌^(guò)的邊;α和β分別為信息素量和啟發(fā)式因子的重要程度;τij為當(dāng)前時(shí)刻邊eij上的信息素量;ηi是啟發(fā)式因子,表示選擇第i個(gè)元素的期望程度,表達(dá)式視具體問(wèn)題而定。

一次迭代完成后,擬對(duì)等效路徑上的信息素增強(qiáng),信息素更新公式[10]為

(2)

2.2交互機(jī)制

為了提高GBAS求解子集問(wèn)題的性能,在GBAS的全局最優(yōu)解多次未更新的情況下,啟動(dòng)鯰魚(yú)效應(yīng)增強(qiáng)搜索提高算法收斂到全局最優(yōu)的概率。在此過(guò)程中,需要將GBAS的當(dāng)前信息傳遞給鯰魚(yú)效應(yīng)增強(qiáng)搜索,在增強(qiáng)搜索結(jié)束后,也需要將結(jié)果返回給蟻群算法,因此GBAS和增強(qiáng)搜索的交互分為兩個(gè)階段:信息傳遞和結(jié)果返回。

(1) 信息傳遞

鯰魚(yú)效應(yīng)增強(qiáng)搜索中,一個(gè)重要的階段是蝙蝠種群的初始化,它決定了增強(qiáng)搜索算法的初始狀態(tài)和搜索能力,因此優(yōu)秀的蝙蝠初始種群對(duì)算法的性能及運(yùn)行結(jié)果至關(guān)重要。本文采用GBAS更新中動(dòng)態(tài)選取螞蟻搜索出的一定數(shù)量的較好路徑作為檔案,檔案規(guī)模取1～2倍的螞蟻數(shù),使個(gè)體具有一定多樣性又不使檔案規(guī)模過(guò)大。啟動(dòng)鯰魚(yú)效應(yīng)增強(qiáng)搜索時(shí),將檔案信息作為參數(shù)初始化蝙蝠種群進(jìn)行搜索。

(2) 結(jié)果返回

為了提高算法的運(yùn)行效率,除了設(shè)定增強(qiáng)搜索算法迭代次數(shù)上限,GBAS也要將當(dāng)前全局最優(yōu)值作為參數(shù)同時(shí)傳遞給增強(qiáng)搜索,當(dāng)增強(qiáng)搜索發(fā)現(xiàn)比蟻群算法的當(dāng)前全局最優(yōu)解更好的路徑時(shí)即停止搜索返回結(jié)果。

2.3鯰魚(yú)效應(yīng)增強(qiáng)搜索

本節(jié)提出使用混沌搜索且具有鯰魚(yú)效應(yīng)的BA對(duì)GBAS的性能進(jìn)行提升,使得算法具有更強(qiáng)的全局搜索能力。

2.3.1頻率變化區(qū)間混沌搜索

在基本的BA算法中,每只蝙蝠個(gè)體利用自身的回聲定位系統(tǒng),計(jì)算出自身與群體當(dāng)前最優(yōu)解之間的距離,通過(guò)使用脈沖頻率來(lái)調(diào)節(jié)自己在下一代運(yùn)行時(shí)的速度, 在t+1時(shí)刻蝙蝠的位置和速度更新公式[11]如下:

(3)

(4)

(5)

式中,Fi表示蝙蝠i在當(dāng)前時(shí)刻發(fā)出的聲波脈沖頻率;Fmax,Fmin分別表示脈沖頻率的最大值和最小值;β∈[0,1]是一個(gè)服從均勻分布的隨機(jī)向量;式(4)中的x*表示當(dāng)前全局最優(yōu)位置(解)。

然而從[Fmin,Fmax]隨機(jī)生成的脈沖頻率可能使得蝙蝠的速度變化局限在某個(gè)區(qū)間段內(nèi)。觀察式(5)可以看出,當(dāng)蝙蝠個(gè)體的搜索范圍靠近當(dāng)前最優(yōu)解時(shí),其速度的變化會(huì)逐漸趨于零,從而影響了蝙蝠的搜索能力。同時(shí),蝙蝠的脈沖信號(hào)發(fā)射速率的提升也使得其在鄰域內(nèi)搜索到更好解的能力下降,這就使得算法易陷入局部最優(yōu),增加蝙蝠群體搜尋的最終解與初始值的關(guān)聯(lián)性。

(6)

(7)

2.3.2算法描述

與多數(shù)群智能算法類似,在BA算法執(zhí)行過(guò)程中,如果最優(yōu)解和周圍蝙蝠的距離很小,那么每只蝙蝠就會(huì)成為圍繞在最優(yōu)解附近簇的一部分,在下一次迭代過(guò)程中,只能移動(dòng)很小的距離。此時(shí)算法就陷入了局部最優(yōu)。為了避免這種情況,當(dāng)BA算法陷入停滯,過(guò)早收斂時(shí),可以引入“鯰魚(yú)”蝙蝠來(lái)刺激其他“沙丁魚(yú)”蝙蝠進(jìn)行新的搜索。在算法具體執(zhí)行過(guò)程中,通過(guò)使用“鯰魚(yú)”蝙蝠來(lái)代替當(dāng)前蝙蝠種群中適應(yīng)度值最差的10%個(gè)體。

此外,在算法中,蝙蝠的局部搜索過(guò)程[11]為

(8)

式中,ε∈[-1,1]是一個(gè)隨機(jī)數(shù);At是所有蝙蝠在同一個(gè)時(shí)間段的平均音量。

音量和脈沖發(fā)射率的迭代更新公式[11]為

(9)

式中,α和γ為常量。結(jié)合第2.2.1節(jié)對(duì)BA的混沌搜索改進(jìn),鯰魚(yú)效應(yīng)增強(qiáng)搜索的偽代碼如下：

Begin

接受檔案信息和GBAS當(dāng)前全局最優(yōu)解,初始化蝙蝠種群;

WHILE(增強(qiáng)搜索算法全局最優(yōu)解小于GBAS當(dāng)前全局最優(yōu)解或者未達(dá)到最大迭代次數(shù))

FORi=1∶AN

利用式(6)更新混沌值;

采用式(7)、式(4)、式(5)產(chǎn)生新解;

IF 脈沖發(fā)射率小于隨機(jī)產(chǎn)生的隨機(jī)數(shù)

采用式(8)得到一個(gè)局部解;

END IF

利用評(píng)價(jià)函數(shù)計(jì)算個(gè)體適應(yīng)度值;

IF 音量大于隨機(jī)產(chǎn)生的隨機(jī)數(shù)且新的個(gè)體適應(yīng)度小于當(dāng)前個(gè)體適應(yīng)度

接受該解作為當(dāng)前個(gè)體最新解;

更新當(dāng)前蝙蝠個(gè)體最優(yōu)值;

通過(guò)式(9)更新音量和脈沖發(fā)生率;

END IF

更新增強(qiáng)搜索算法的當(dāng)前全局最優(yōu)解及其對(duì)應(yīng)參數(shù);

IF 增強(qiáng)搜索算法的當(dāng)前全局最優(yōu)解大于G次未更新

對(duì)蝙蝠種群按照適應(yīng)度值從最差到最好排列;

選擇最差的10%蝙蝠個(gè)體,隨機(jī)選擇當(dāng)前蝙蝠種群中的最大最小極值點(diǎn)對(duì)蝙蝠個(gè)體的解向量進(jìn)行替換,并將速度置為0;

END IF

END FOR

END WHILE

End

鯰魚(yú)效應(yīng)增強(qiáng)搜索偽代碼中的WHILE判定為算法運(yùn)行的結(jié)束條件,通常在啟發(fā)式算法中,算法運(yùn)行的結(jié)束條件有兩種:一種是設(shè)定算法運(yùn)行迭代次數(shù)的上限;另一種是設(shè)定算法評(píng)估函數(shù)的結(jié)果需要達(dá)到的精度。本文選擇第一種方式來(lái)設(shè)定結(jié)束條件。同時(shí),為了兼顧算法運(yùn)行效率,當(dāng)增強(qiáng)搜索發(fā)現(xiàn)比蟻群算法的當(dāng)前全局最優(yōu)解更好的路徑時(shí)即停止搜索返回結(jié)果。

2.4信息素更新策略

為兼顧算法收斂速度和全局搜索能力,分兩種情況更新信息素矩陣。

(1) 本次迭代最優(yōu)更新

若本次迭代最優(yōu)解好于當(dāng)前全局最優(yōu)解或者全局最優(yōu)解小于G次未更新,則對(duì)本次迭代最優(yōu)路徑tabut,由式(2)進(jìn)行信息素矩陣更新。

(2) 增強(qiáng)搜索更新

若全局最優(yōu)解大于G次未更新,則啟動(dòng)鯰魚(yú)效應(yīng)增強(qiáng)搜索,將檔案信息以及當(dāng)前全局最優(yōu)值傳遞給搜索算法,算法運(yùn)行結(jié)束后返回路徑tabut,由式(2)進(jìn)行信息素矩陣更新。需要特別說(shuō)明的是,如果增強(qiáng)搜索在到達(dá)迭代次數(shù)上限結(jié)束搜索后,仍未發(fā)現(xiàn)較好路徑,則算法依然返回搜索的最終結(jié)果,這樣可以增加信息素更新的多樣性,增強(qiáng)蟻群優(yōu)化算法的全局搜索能力。

2.5算法描述

在GBAS基礎(chǔ)上,在算法主體迭代中最優(yōu)解更新出現(xiàn)停滯的情況下,啟動(dòng)鯰魚(yú)效應(yīng)增強(qiáng)搜索對(duì)更廣闊的問(wèn)題空間進(jìn)行搜索,尋找較好的路徑,利用較好解對(duì)等效路徑上的信息素更新,使得螞蟻在下次迭代中以較大概率選擇較好路徑,提高算法的全局探測(cè)能力。

GBAS是用來(lái)解決組合優(yōu)化問(wèn)題,而組合優(yōu)化是一種離散優(yōu)化問(wèn)題,需要對(duì)應(yīng)用在連續(xù)優(yōu)化領(lǐng)域中的BA算法進(jìn)行離散化,離散方法采用文獻(xiàn)[17]提出的策略。綜上,本文提出的CBA-ACO的偽代碼如下：

Begin

初始化

WHILE(未達(dá)到最大迭代次數(shù))

生成M只螞蟻并初始化規(guī)模為AN的檔案記錄;

FORa=1∶M

螞蟻根據(jù)路徑上的信息素利用式(1)尋找最優(yōu)解;

更新本次迭代最優(yōu)解;

動(dòng)態(tài)刷新檔案記錄

END FOR

IF 本次迭代最優(yōu)解好于當(dāng)前全局最優(yōu)解或全局最優(yōu)解小于G次未更新

更新全局最優(yōu)解并利用式(2)更新信息素;

ELSE 傳遞檔案信息以及GBAS的當(dāng)前全局最優(yōu)解,并運(yùn)行鯰魚(yú)效應(yīng)增強(qiáng)搜索,輸出算法運(yùn)行最優(yōu)解;

更新全局最優(yōu)解并利用式(2)更新信息素;

END IF

輸出最優(yōu)結(jié)果

END WHILE

End

2.6算法復(fù)雜度分析

在鯰魚(yú)效應(yīng)增強(qiáng)搜索中,蝙蝠尋找最優(yōu)解上的時(shí)間復(fù)雜度(最壞情況)為O(NC×N),其中NC為BA算法最大迭代次數(shù),N為蝙蝠種群規(guī)模;運(yùn)行鯰魚(yú)效應(yīng)的時(shí)間復(fù)雜度為O(NC×nN),其中n為備選集的基數(shù),因此鯰魚(yú)效應(yīng)增強(qiáng)搜索在最壞情況下的時(shí)間復(fù)雜度為O(NC×nN)。

在CBA-ACO中,螞蟻搜索可行路徑的時(shí)間復(fù)雜度為O(MC×n2),其中MC為算法最大迭代次數(shù),n為備選集的基數(shù);CBA-ACO運(yùn)行鯰魚(yú)效應(yīng)增強(qiáng)搜索的時(shí)間復(fù)雜度為O(MC×NC×nN),這部分是CBA-ACO程序中耗時(shí)最長(zhǎng)的計(jì)算步驟,因此CBA-ACO在最壞情況下的時(shí)間復(fù)雜度為O(MC×NC×nN)。

鯰魚(yú)效應(yīng)增強(qiáng)搜索的空間復(fù)雜度為O(N×n),蟻群算法中信息素表是占用存儲(chǔ)資源最大的部分,空間復(fù)雜度為O(n2),因此CBA-ACO的空間復(fù)雜度為O(n2+N×n)。

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

3.1CBA-ACO實(shí)驗(yàn)分析

為了驗(yàn)證CBA-ACO優(yōu)化的有效性和優(yōu)越性,以多維背包問(wèn)題為例,對(duì)算法進(jìn)行仿真和測(cè)試。同時(shí),將不包含鯰魚(yú)效應(yīng)增強(qiáng)搜索的CBA-ACO(算法1)和包含增強(qiáng)搜索但未加鯰魚(yú)效應(yīng)的CBA-ACO(算法2)與本文提出的完整CBA-ACO優(yōu)化(算法3)進(jìn)行對(duì)比實(shí)驗(yàn)。

多維背包問(wèn)題(multidimensional knapsack problem, MKP)的形式化表示為

(10)

(11)

式中,n為物品的個(gè)數(shù);pi為第i個(gè)物品的價(jià)值;cbi(b=1,2,…,r)為第i個(gè)物品第b個(gè)約束向量;r為問(wèn)題的維數(shù);xi(i=1,2,…,n)為解向量。r維背包問(wèn)題可以表述為,在具有r個(gè)約束的條件下,從n個(gè)物品(候選解)中選擇一組物品(子集),使背包所含物品的價(jià)值最大。

測(cè)試實(shí)例來(lái)自網(wǎng)站:http:∥elib.zib.de/pub/Packages/mp-testdata/ip/sac94-suite/index.html。

實(shí)例 1weish06.dat,背包個(gè)數(shù)為5,背包維度為40,最優(yōu)解為5 557。

(1) 算法1參數(shù)設(shè)置[10]如下:α=0.8,β=0.2,ρ=0.2,τij(0)=100,M=20,Q=200。

(3) 算法3參數(shù)設(shè)置如下:鯰魚(yú)效應(yīng)啟動(dòng)條件g=10,其他與算法2一致。

實(shí)例 2weish14.dat,背包個(gè)數(shù)為5,背包維度為60,最優(yōu)解為6 954。

(1) 算法1參數(shù)設(shè)置[10]如下:α=1,β=0.2,ρ=0.2,τij(0)=100,M=20,Q=300。

(3) 算法3參數(shù)設(shè)置如下:鯰魚(yú)效應(yīng)啟動(dòng)條件g=10,其他與算法2一致;

實(shí)例 3weish28.dat,背包個(gè)數(shù)為5,背包維度為90,最優(yōu)解為9 492。

(1) 算法1參數(shù)設(shè)置[10]如下:α=1.2,β=0.2,ρ=0.2,τij(0)=100,M=20,Q=300。

(3) 算法3參數(shù)設(shè)置如下:鯰魚(yú)效應(yīng)啟動(dòng)條件g=10,其他與算法2一致。

測(cè)試過(guò)程中對(duì)算法的迭代次數(shù)取MC=[10∶10∶200],每個(gè)實(shí)例各運(yùn)行20次,計(jì)算所得解的均值和方差,測(cè)試結(jié)果如圖2～圖7所示,并將算法發(fā)現(xiàn)所提供最優(yōu)解的次數(shù)列于表1～表3(部分)。

圖2　實(shí)例1解的均值Fig.2　Mean value of solutions of instance 1

圖3　實(shí)例1解的標(biāo)準(zhǔn)差Fig.3　Standard deviation of solutions of instance 1

圖4　實(shí)例2解的均值Fig.4　Mean value of solutions of instance 2

圖5　實(shí)例2解的標(biāo)準(zhǔn)差Fig.5　Standard deviation of solutions of instance 2

圖6　實(shí)例3解的均值Fig.6　Mean value of solutions of instance 3

圖7　實(shí)例3解的標(biāo)準(zhǔn)差Fig.7　Standard deviation of solutions of instance 3

迭代次數(shù)實(shí)例1算法1算法2算法330005502610705121390610121105101613011111615071416170517151905131620081217

表2　實(shí)例2發(fā)現(xiàn)所提供最優(yōu)解的次數(shù)

表3　實(shí)例3發(fā)現(xiàn)所提供最優(yōu)解的次數(shù)

首先分析測(cè)試實(shí)例中的均值。通過(guò)對(duì)比圖2、圖4和圖6中的均值能夠發(fā)現(xiàn),在實(shí)例2和實(shí)例3的測(cè)試條件下,算法2和算法3都要好于算法1,這是由于在GBAS的全局最優(yōu)解多次未更新的情況下,啟動(dòng)了增強(qiáng)搜索,由于不受算法中信息素的限制,使得增強(qiáng)搜索能夠在更廣闊的搜索空間中尋找更好的最優(yōu)解,再使用等效路徑進(jìn)行信息素更新,提高了算法的全局探測(cè)能力,驗(yàn)證了增強(qiáng)搜索具有提高算法全局搜索性能的能力。但是，在實(shí)例1的測(cè)試條件下,算法2的均值與算法1相比沒(méi)有明顯的提高,算法3的均值與算法2和算法1相比具有明顯的優(yōu)勢(shì),這是因?yàn)樗惴?在蝙蝠尋優(yōu)的過(guò)程中會(huì)陷入局部最優(yōu),導(dǎo)致尋找的結(jié)果不穩(wěn)定,在這種情況下具有鯰魚(yú)效應(yīng)的算法3就能夠跳出局部最優(yōu)值,這就使得算法3算法能夠以較大的概率發(fā)現(xiàn)比算法2更好的最優(yōu)解,這也驗(yàn)證了鯰魚(yú)效應(yīng)具有解決過(guò)早收斂問(wèn)題的能力。

對(duì)比圖3、圖5和圖7中的標(biāo)準(zhǔn)差,能夠發(fā)現(xiàn)在實(shí)例2和實(shí)例3的測(cè)試條件下,算法2和算法3都要好于算法1,這是由于在GBAS全局最優(yōu)解多次未更新的情況下,啟動(dòng)了增強(qiáng)搜索尋找到更好的最優(yōu)解并進(jìn)行信息素更新,提高了算法獲得較好解的能力。而在實(shí)例1的測(cè)試條件下,算法3比算法2和算法1具有更小的標(biāo)準(zhǔn)差,算法2與算法1相比在標(biāo)準(zhǔn)差的比較中并沒(méi)有明顯的優(yōu)勢(shì),這是由于BA算法陷入局部最優(yōu),產(chǎn)生過(guò)早收斂問(wèn)題,導(dǎo)致尋優(yōu)結(jié)果不穩(wěn)定。而包含鯰魚(yú)效應(yīng)的算法3則很好的解決了該問(wèn)題。

觀察表1～表3提供的最優(yōu)解出現(xiàn)次數(shù),算法2與算法1相比,能夠提供更多次最優(yōu)解,而算法3的優(yōu)勢(shì)要比算法2更為明顯,這是由于算法3包含解決過(guò)早收斂問(wèn)題的鯰魚(yú)效應(yīng),使得算法3擁有更強(qiáng)的全局搜索能力,增加了發(fā)現(xiàn)最優(yōu)解的概率。

同時(shí),為了驗(yàn)證算法的運(yùn)行耗時(shí),記錄下3個(gè)算法的運(yùn)行時(shí)間,并以算法1作為基準(zhǔn),對(duì)運(yùn)行時(shí)間作歸一化處理,得到的結(jié)果如表4所示。

表4　算法2和算法3的相對(duì)運(yùn)行時(shí)間

從表4中觀察可以看出,算法3和算法2的運(yùn)行時(shí)間隨著迭代次數(shù)的增加而增加,算法3由于增加了鯰魚(yú)效應(yīng),因此在時(shí)間上要比算法2更加耗時(shí)。算法3和算法2的運(yùn)行時(shí)間都沒(méi)有超過(guò)算法1運(yùn)行時(shí)間的2倍,這是由于在增強(qiáng)搜索中除了設(shè)定運(yùn)行次數(shù)的上限,還將發(fā)現(xiàn)當(dāng)前全局最優(yōu)解作為停止的條件,一旦發(fā)現(xiàn)比當(dāng)前全局最優(yōu)解更好的解時(shí),算法2和算法3都停止運(yùn)行,返回發(fā)現(xiàn)的更好解,有效降低了運(yùn)行時(shí)間。

綜上,鯰魚(yú)效應(yīng)增強(qiáng)搜索對(duì)提高算法的尋優(yōu)和收斂能力具有有效性。同時(shí)表明包含鯰魚(yú)效應(yīng)增強(qiáng)搜索的CBA-ACO具有更強(qiáng)的發(fā)現(xiàn)較好解的能力,解的穩(wěn)定性也較好,是一種很好的混合啟發(fā)式方法。

3.2CBA-ACO參數(shù)敏感性分析

分析過(guò)程中G和g的取值均為[1 3 5 7 9 11 13 20],對(duì)算法的迭代次數(shù)取MC=80,在一次實(shí)驗(yàn)中,對(duì)設(shè)定的G和g值,算法運(yùn)行20次,計(jì)算所得解的均值和方差以及運(yùn)行時(shí)間。其中一次的測(cè)試結(jié)果如表5和表6所示。

表5　G=7時(shí)不同g的運(yùn)行結(jié)果

表6　g=11時(shí)不同G的運(yùn)行結(jié)果

從表5中可以看出,在G=7時(shí),不同的g值條件下,算法運(yùn)行的均值、標(biāo)準(zhǔn)差和運(yùn)行時(shí)間是呈現(xiàn)一定變化趨勢(shì)的。這是由于當(dāng)g較小時(shí),鯰魚(yú)效應(yīng)啟動(dòng)次數(shù)較多,造成算法的收斂能力下降,導(dǎo)致均值降低并增大了標(biāo)準(zhǔn)差,而較差的全局最優(yōu)值也會(huì)使得增強(qiáng)搜索的次數(shù)增加,提高了算法運(yùn)行時(shí)間;隨著g的增加,算法的收斂能力也趨于增強(qiáng),運(yùn)行結(jié)果也逐漸變好;當(dāng)g增加到一定程度之后,鯰魚(yú)效應(yīng)啟動(dòng)次數(shù)減少甚至不會(huì)啟動(dòng),這就減小了鯰魚(yú)效應(yīng)對(duì)算法的增強(qiáng)作用,使得算法獲取較好解的能力下降,導(dǎo)致運(yùn)行結(jié)果變差,使得增強(qiáng)搜索的運(yùn)行次數(shù)再次增加,提高了算法的運(yùn)行時(shí)間。在其他的G值條件下測(cè)試能夠得到相同的結(jié)論。通過(guò)實(shí)驗(yàn)分析,g取值在7～11之間時(shí),算法運(yùn)行結(jié)果較好。

分析表6,在g=11時(shí),G值不同,算法的均值、標(biāo)準(zhǔn)差也有所不同。當(dāng)G較小時(shí),鯰魚(yú)效應(yīng)增強(qiáng)搜索運(yùn)行次數(shù)較多,導(dǎo)致算法的全局搜索能力下降,均值降低,標(biāo)準(zhǔn)差增加;隨著G值逐漸趨近較好范圍,算法的全局搜索能力和局部開(kāi)采能力達(dá)到較好的結(jié)合狀態(tài),算法的運(yùn)行結(jié)果也較好;進(jìn)一步增加G值時(shí),算法的增強(qiáng)搜索啟動(dòng)次數(shù)減少,局部開(kāi)采能力逐漸減弱,導(dǎo)致均值和標(biāo)準(zhǔn)差呈現(xiàn)較差趨勢(shì);分析算法的運(yùn)行時(shí)間,可以看出,算法運(yùn)行時(shí)間對(duì)G值的變化并不敏感,這也驗(yàn)證了鯰魚(yú)效應(yīng)增強(qiáng)搜索的優(yōu)越性。在其他的g值條件下測(cè)試能夠得到相同的結(jié)論。通過(guò)實(shí)驗(yàn)分析,G取值在5～9之間時(shí),算法運(yùn)行結(jié)果較好。

4　結(jié)　論

為了求解子集問(wèn)題,提出一種基于圖的螞蟻系統(tǒng)CBA-ACO。

針對(duì)BA算法過(guò)早收斂的問(wèn)題,采用混沌映射對(duì)頻率搜索區(qū)間進(jìn)行改進(jìn),一定程度上改善了BA的搜索能力;通過(guò)引入鯰魚(yú)效應(yīng),使得BA算法能夠跳出陷入局部最優(yōu)的情況,進(jìn)一步增強(qiáng)了BA算法全局搜索能力。

將改進(jìn)后的鯰魚(yú)效應(yīng)增強(qiáng)搜索加入GBAS中,在全局最優(yōu)解多次未更新的情況下,通過(guò)保存較好路徑的檔案信息初始化并啟動(dòng)增強(qiáng)搜索尋找更好的最優(yōu)解,提高了算法的全局探測(cè)能力。對(duì)采用的鯰魚(yú)效應(yīng)和增強(qiáng)搜索進(jìn)行實(shí)驗(yàn),并對(duì)參數(shù)敏感性進(jìn)行了分析,結(jié)果表明了改進(jìn)的有效性,同時(shí)驗(yàn)證了本文提出CBA-ACO具有更好的穩(wěn)定性和獲取較好解的能力。

[1] Ishibuchi H, Akedo N, Nojima Y. Behavior of multiobjective evolutionary algorithms on many-objective knapsack problems[J].IEEETrans.onEvolutionaryComputation, 2015, 19(2): 264-283.

[2] Colorni A, Dorigo M, Maniezzo V. Distributed optimization by ant colonies[C]∥Proc.oftheFirstEuropeanConferenceonArtificialLife, 1991: 134-142.

[3] Liao T J, Socha K, A. Montes de Oca M, et al. Ant colony optimization for mixed-variable optimization problems[J].IEEETrans.onEvolutionaryComputation, 2014, 18(4): 503-518.

[4] Forsati R, Moayedikia A, Jensen R, et al. Enriched ant colony optimization and its application in feature selection[J].Neurocomputing, 2014, 142: 354-371.

[5] Leguizamon G, Michalewicz Z. A new version of ant system for subset problems[C]∥Proc.oftheCongressonEvolutionaryComputation, 1999: 1459-1464.

[6] Parra-Hernandez R, Dimopoulos N. On the performance of the ant colony system for solving the multidimensional knapsack problem[C]∥Proc.oftheIEEEPacificRimConferenceonCommunications,ComputersandsignalProcessing, 2003: 338-341.

[7] Shi H X. Solution to 0/1 knapsack problem based on improved ant colony algorithm[C]∥Proc.oftheIEEEInternationalConferenceonInformationAcquisition, 2006: 1062-1066.

[8] Wang H Y, Jia R Y, Zhang Y G, et al. A quick ant colony algorithm of solving 0-1 knapsack problem[J].ComputerTechnologyandDevelopment,2007,17(1):104-107.(王會(huì)穎,賈瑞玉,章義剛,等.一種求解0-1背包問(wèn)題的快速蟻群算法[J].計(jì)算機(jī)技術(shù)與發(fā)展,2007,17(1):104-107.)

[9] Hu X B, Huang X Y. Solving 0-1 knapsack problem based on ant colony optimization algorithm[J].JournalofSystemsEngineering, 2005, 20(5): 520-523.(胡小兵,黃席樾.基于蟻群優(yōu)化算法的0-1背包問(wèn)題求解[J].系統(tǒng)工程學(xué)報(bào),2005,20(5):520-523.)

[10] Cao J J, Zhang P L, Wang Y X, et al. A graph-based ant system for subset problems[J].JournalofSystemSimulation, 2008, 20(22): 6146-6150.(曹建軍, 張培林, 王艷霞, 等. 一種求解子集問(wèn)題的基于圖的螞蟻系統(tǒng)[J].系統(tǒng)仿真學(xué)報(bào), 2008, 20(22): 6146-6150.)

[11] Carlos C, Gonzalez J R,Natalio K, et al.NatureInspiredcooperativestrategiesforoptimization[M]. Yang X S.Anewmetaheuristicbat-inspiredalgorithm.Granada: Springer, 2010: 64-74.

[12] Yang X S.Bat algorithm for multi-objective optimization[J].InternationalJournalofBio-inspiredComputation,2011,3(5):267-274.

[13] Yang X S, Gandomi A H. Bat algorithm: a novel approach for global engineering optimization[J].EngineeringComputation, 2012, 29(5): 267-289.

[14] Gandomi A H, Yang X S, Alavi A H, et al. Bat algorithm for constrained optimization tasks[J].NeuralComputingandApplication, 2013, 22(6): 1239-1255.

[15] Zhao Y X, Yang X S, Liu L Q.Newlydevelopingmetaheuristicoptimizationmethods[M]. Beijing: Science Press, 2013.(趙玉新, 楊新社, 劉利強(qiáng). 新興元啟發(fā)式優(yōu)化方法[M]. 北京:科學(xué)出版社, 2013.)

[16] Chuang L Y, Tsai S W, Yang C H. Chaotic catfish particle swarm optimization for solving global numerical optimization problems[J].AppliedMathematicsandComputation, 2011, 217(16): 6900-6916.

[17] Mirjalili S, Mirjalili S M, Yang X S. Binary bat algorithm[J].NeuralComputingandApplications, 2014, 25(3): 663-681.

曹建軍(1975-),通信作者,男,工程師,博士,主要研究方向?yàn)檫M(jìn)化算法、數(shù)據(jù)質(zhì)量控制與數(shù)據(jù)治理。

E-mail:jianjuncao@yeah.net

丁鯤(1978-),男,高級(jí)工程師,碩士,主要研究方向?yàn)榫W(wǎng)絡(luò)管理。

E-mail:njdingkun@163.com

許永平(1979-),男,工程師,博士,主要研究方向?yàn)閿?shù)據(jù)質(zhì)量控制與數(shù)據(jù)治理。

E-mail:zuisanlang@163.com

Catfish bat algorithm-ant colony optimization for subset problems

LIU Yi1, DIAO Xing-chun2, CAO Jian-jun2, DING Kun2, XU Yong-ping2

(1. College of Command Information Systems, PLA University of Science and Technology, Nanjing 210007, China;2.The63rdResearchInstituteofPLAGeneralStaffHeadquarters,Nanjing210007,China)

In order to resolve subset problems, a new graph-based ant system called catfish bat algorithm-ant colony optimization (CBA-ACO) is proposed. Based on the subset problem’s structure graph, routes’ probability transition equation is used to search for solutions, equivalent routes’ pheromones strengthening is adopted to update pheromone. Some solutions are maintained in archive dynamically. The chaotic map and catfish effect are adopted to improve the bat algorithm (BA) for the enhanced exploration which is initialized by archive information and used to find better solution in case the global optimal solution is not updated after several runs. After one cycle, the best route of this cycle updating and the enhanced exploration updating are two cases of updating pheromone. As a result the convergence speed and searching capability of the algorithm are improved. The algorithm is described, and its complexity is analyzed. Experiments show that the CBA-ACO algorithm has a better stability and capability for obtaining the optimal solution.

graph-based ant system; bat algorithm; catfish effect; chaotic map

2015-11-23；

2016-06-20；網(wǎng)絡(luò)優(yōu)先出版日期：2016-07-20。

國(guó)家自然科學(xué)基金(61371196);中國(guó)博士后科學(xué)基金特別資助項(xiàng)目(201003797);解放軍理工大學(xué)預(yù)研基金(20110604,41150301)資助課題

TP 301.6

A

10.3969/j.issn.1001-506X.2016.10.31

劉藝(1990-),男,博士研究生,主要研究方向?yàn)閿?shù)據(jù)質(zhì)量、進(jìn)化算法。

E-mail:albertliu20th@sohu.com

刁興春(1964-),男,研究員,碩士,主要研究方向?yàn)閿?shù)據(jù)工程。

E-mail:diaoxch640222@163.com

網(wǎng)絡(luò)優(yōu)先出版地址：http://www.cnki.net/kcms/detail/11.2422.TN.20160720.1114.002.html