求解子集問題的鯰魚效應蝙蝠蟻群優化

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

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

?

求解子集問題的鯰魚效應蝙蝠蟻群優化

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

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

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

基于圖的螞蟻系統; 蝙蝠算法; 鯰魚效應; 混沌映射

0　引　言

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

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

為了求解子集問題,本文提出一種新的基于圖的螞蟻系統——鯰魚效應蝙蝠蟻群優化(catfish bat algorithm-ant colony optimization, CBA-ACO)?；谧蛹瘑栴}的構造圖,采用路徑概率轉移公式進行路徑搜索,利用等效路徑對信息素進行增強更新;在迭代過程中,動態維護一定數量較好路徑作為檔案信息;使用混沌映射并結合鯰魚效應對BA算法進行改進,在全局最優解多次未更新時,利用檔案信息初始化鯰魚效應增強搜索,返回較好路徑解;采用本次迭代最優更新和增強搜索更新兩種方式更新信息素,兼顧算法的收斂速度和搜索能力。對采用的鯰魚效應,鯰魚效應增強搜索進行實驗,并進行參數敏感性分析,驗證CBA-ACO的有效性以及在尋優能力和獲得解的穩定性上的優越性。

1　相關理論簡介

1.1基于圖的螞蟻系統

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

(1) 針對具體問題的構造圖:一般包括一個有向圖和若干個從有向圖到具體問題的映射,構造圖實現了問題到有向圖表示的映射;

(2) 智能蟻群:每個智能螞蟻依據所給定的狀態轉移概率,在有向圖中進行依次隨機行走,構造滿足約束條件的可行解,所有螞蟻均完成一次行走過程后,一次迭代結束,智能螞蟻死亡;

(3) 螞蟻隨機移動的狀態轉移概率:通過有向圖邊上的信息素量和啟發式信息量計算狀態轉移概率,螞蟻依據概率信息進行獨立的隨機行走;

(4) 構造圖中有向圖邊上的信息素量:信息素量隨迭代次數變化,一次迭代完成后,按照一定的規則對信息素進行更新;

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

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

1.2BA算法

蝙蝠是一種特別的生物,其中微型蝙蝠使用回聲定位來躲避障礙和探測獵物。多數微型蝙蝠使用調頻信號,而其他一些則使用固定頻率的信號,但是它們原理都是基于回聲定位的聲學原理。文獻[11]受到微型蝙蝠這種回聲定位的飛行行為方式啟發,于2010年提出了BA算法。BA算法包括信號頻率的變化,速度和位置的更新以及響度的變化,而蝙蝠的速度和位置的更新策略與標準粒子群算法(particle swarm optimization,PSO)更新速度和位置的策略有很多相似之處。實質上,PSO與和聲搜索都是BA在適當簡化下的特殊情況[15],結合了兩種方法的優點。本文在算法全局最優解多次未更新的情況下使用BA,在更廣闊的空間中尋找較好解,提高算法的全局搜索能力。

1.3鯰魚效應

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

2　CBA-ACO優化

2.1路徑搜索和信息素更新

求解子集問題的基于圖的螞蟻系統具體模型如圖1所示[10]。

圖1　子集問題構造圖的有向圖Fig.1　Directed graph of subset problem’s structure graph

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

在GBAS中使用的路徑概率轉移公式為[8]

(1)

式中,禁忌表tabum(m=1,2,…,M)記錄第m只螞蟻走過的邊;α和β分別為信息素量和啟發式因子的重要程度;τij為當前時刻邊eij上的信息素量;ηi是啟發式因子,表示選擇第i個元素的期望程度,表達式視具體問題而定。

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

(2)

2.2交互機制

為了提高GBAS求解子集問題的性能,在GBAS的全局最優解多次未更新的情況下,啟動鯰魚效應增強搜索提高算法收斂到全局最優的概率。在此過程中,需要將GBAS的當前信息傳遞給鯰魚效應增強搜索,在增強搜索結束后,也需要將結果返回給蟻群算法,因此GBAS和增強搜索的交互分為兩個階段:信息傳遞和結果返回。

(1) 信息傳遞

鯰魚效應增強搜索中,一個重要的階段是蝙蝠種群的初始化,它決定了增強搜索算法的初始狀態和搜索能力,因此優秀的蝙蝠初始種群對算法的性能及運行結果至關重要。本文采用GBAS更新中動態選取螞蟻搜索出的一定數量的較好路徑作為檔案,檔案規模取1～2倍的螞蟻數,使個體具有一定多樣性又不使檔案規模過大。啟動鯰魚效應增強搜索時,將檔案信息作為參數初始化蝙蝠種群進行搜索。

(2) 結果返回

為了提高算法的運行效率,除了設定增強搜索算法迭代次數上限,GBAS也要將當前全局最優值作為參數同時傳遞給增強搜索,當增強搜索發現比蟻群算法的當前全局最優解更好的路徑時即停止搜索返回結果。

2.3鯰魚效應增強搜索

本節提出使用混沌搜索且具有鯰魚效應的BA對GBAS的性能進行提升,使得算法具有更強的全局搜索能力。

2.3.1頻率變化區間混沌搜索

在基本的BA算法中,每只蝙蝠個體利用自身的回聲定位系統,計算出自身與群體當前最優解之間的距離,通過使用脈沖頻率來調節自己在下一代運行時的速度, 在t+1時刻蝙蝠的位置和速度更新公式[11]如下:

(3)

(4)

(5)

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

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

(6)

(7)

2.3.2算法描述

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

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

(8)

式中,ε∈[-1,1]是一個隨機數;At是所有蝙蝠在同一個時間段的平均音量。

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

(9)

式中,α和γ為常量。結合第2.2.1節對BA的混沌搜索改進,鯰魚效應增強搜索的偽代碼如下：

Begin

接受檔案信息和GBAS當前全局最優解,初始化蝙蝠種群;

WHILE(增強搜索算法全局最優解小于GBAS當前全局最優解或者未達到最大迭代次數)

FORi=1∶AN

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

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

IF 脈沖發射率小于隨機產生的隨機數

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

END IF

利用評價函數計算個體適應度值;

IF 音量大于隨機產生的隨機數且新的個體適應度小于當前個體適應度

接受該解作為當前個體最新解;

更新當前蝙蝠個體最優值;

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

END IF

更新增強搜索算法的當前全局最優解及其對應參數;

IF 增強搜索算法的當前全局最優解大于G次未更新

對蝙蝠種群按照適應度值從最差到最好排列;

選擇最差的10%蝙蝠個體,隨機選擇當前蝙蝠種群中的最大最小極值點對蝙蝠個體的解向量進行替換,并將速度置為0;

END IF

END FOR

END WHILE

End

鯰魚效應增強搜索偽代碼中的WHILE判定為算法運行的結束條件,通常在啟發式算法中,算法運行的結束條件有兩種:一種是設定算法運行迭代次數的上限;另一種是設定算法評估函數的結果需要達到的精度。本文選擇第一種方式來設定結束條件。同時,為了兼顧算法運行效率,當增強搜索發現比蟻群算法的當前全局最優解更好的路徑時即停止搜索返回結果。

2.4信息素更新策略

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

(1) 本次迭代最優更新

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

(2) 增強搜索更新

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

2.5算法描述

在GBAS基礎上,在算法主體迭代中最優解更新出現停滯的情況下,啟動鯰魚效應增強搜索對更廣闊的問題空間進行搜索,尋找較好的路徑,利用較好解對等效路徑上的信息素更新,使得螞蟻在下次迭代中以較大概率選擇較好路徑,提高算法的全局探測能力。

GBAS是用來解決組合優化問題,而組合優化是一種離散優化問題,需要對應用在連續優化領域中的BA算法進行離散化,離散方法采用文獻[17]提出的策略。綜上,本文提出的CBA-ACO的偽代碼如下：

Begin

初始化

WHILE(未達到最大迭代次數)

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

FORa=1∶M

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

更新本次迭代最優解;

動態刷新檔案記錄

END FOR

IF 本次迭代最優解好于當前全局最優解或全局最優解小于G次未更新

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

ELSE 傳遞檔案信息以及GBAS的當前全局最優解,并運行鯰魚效應增強搜索,輸出算法運行最優解;

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

END IF

輸出最優結果

END WHILE

End

2.6算法復雜度分析

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

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

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

3　實驗結果與分析

3.1CBA-ACO實驗分析

為了驗證CBA-ACO優化的有效性和優越性,以多維背包問題為例,對算法進行仿真和測試。同時,將不包含鯰魚效應增強搜索的CBA-ACO(算法1)和包含增強搜索但未加鯰魚效應的CBA-ACO(算法2)與本文提出的完整CBA-ACO優化(算法3)進行對比實驗。

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

(10)

(11)

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

測試實例來自網站:http:∥elib.zib.de/pub/Packages/mp-testdata/ip/sac94-suite/index.html。

實例 1weish06.dat,背包個數為5,背包維度為40,最優解為5 557。

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

(3) 算法3參數設置如下:鯰魚效應啟動條件g=10,其他與算法2一致。

實例 2weish14.dat,背包個數為5,背包維度為60,最優解為6 954。

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

(3) 算法3參數設置如下:鯰魚效應啟動條件g=10,其他與算法2一致;

實例 3weish28.dat,背包個數為5,背包維度為90,最優解為9 492。

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

(3) 算法3參數設置如下:鯰魚效應啟動條件g=10,其他與算法2一致。

測試過程中對算法的迭代次數取MC=[10∶10∶200],每個實例各運行20次,計算所得解的均值和方差,測試結果如圖2～圖7所示,并將算法發現所提供最優解的次數列于表1～表3(部分)。

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

圖3　實例1解的標準差Fig.3　Standard deviation of solutions of instance 1

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

圖5　實例2解的標準差Fig.5　Standard deviation of solutions of instance 2

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

圖7　實例3解的標準差Fig.7　Standard deviation of solutions of instance 3

迭代次數實例1算法1算法2算法330005502610705121390610121105101613011111615071416170517151905131620081217

表2　實例2發現所提供最優解的次數

表3　實例3發現所提供最優解的次數

首先分析測試實例中的均值。通過對比圖2、圖4和圖6中的均值能夠發現,在實例2和實例3的測試條件下,算法2和算法3都要好于算法1,這是由于在GBAS的全局最優解多次未更新的情況下,啟動了增強搜索,由于不受算法中信息素的限制,使得增強搜索能夠在更廣闊的搜索空間中尋找更好的最優解,再使用等效路徑進行信息素更新,提高了算法的全局探測能力,驗證了增強搜索具有提高算法全局搜索性能的能力。但是，在實例1的測試條件下,算法2的均值與算法1相比沒有明顯的提高,算法3的均值與算法2和算法1相比具有明顯的優勢,這是因為算法2在蝙蝠尋優的過程中會陷入局部最優,導致尋找的結果不穩定,在這種情況下具有鯰魚效應的算法3就能夠跳出局部最優值,這就使得算法3算法能夠以較大的概率發現比算法2更好的最優解,這也驗證了鯰魚效應具有解決過早收斂問題的能力。

對比圖3、圖5和圖7中的標準差,能夠發現在實例2和實例3的測試條件下,算法2和算法3都要好于算法1,這是由于在GBAS全局最優解多次未更新的情況下,啟動了增強搜索尋找到更好的最優解并進行信息素更新,提高了算法獲得較好解的能力。而在實例1的測試條件下,算法3比算法2和算法1具有更小的標準差,算法2與算法1相比在標準差的比較中并沒有明顯的優勢,這是由于BA算法陷入局部最優,產生過早收斂問題,導致尋優結果不穩定。而包含鯰魚效應的算法3則很好的解決了該問題。

觀察表1～表3提供的最優解出現次數,算法2與算法1相比,能夠提供更多次最優解,而算法3的優勢要比算法2更為明顯,這是由于算法3包含解決過早收斂問題的鯰魚效應,使得算法3擁有更強的全局搜索能力,增加了發現最優解的概率。

同時,為了驗證算法的運行耗時,記錄下3個算法的運行時間,并以算法1作為基準,對運行時間作歸一化處理,得到的結果如表4所示。

表4　算法2和算法3的相對運行時間

從表4中觀察可以看出,算法3和算法2的運行時間隨著迭代次數的增加而增加,算法3由于增加了鯰魚效應,因此在時間上要比算法2更加耗時。算法3和算法2的運行時間都沒有超過算法1運行時間的2倍,這是由于在增強搜索中除了設定運行次數的上限,還將發現當前全局最優解作為停止的條件,一旦發現比當前全局最優解更好的解時,算法2和算法3都停止運行,返回發現的更好解,有效降低了運行時間。

綜上,鯰魚效應增強搜索對提高算法的尋優和收斂能力具有有效性。同時表明包含鯰魚效應增強搜索的CBA-ACO具有更強的發現較好解的能力,解的穩定性也較好,是一種很好的混合啟發式方法。

3.2CBA-ACO參數敏感性分析

分析過程中G和g的取值均為[1 3 5 7 9 11 13 20],對算法的迭代次數取MC=80,在一次實驗中,對設定的G和g值,算法運行20次,計算所得解的均值和方差以及運行時間。其中一次的測試結果如表5和表6所示。

表5　G=7時不同g的運行結果

表6　g=11時不同G的運行結果

從表5中可以看出,在G=7時,不同的g值條件下,算法運行的均值、標準差和運行時間是呈現一定變化趨勢的。這是由于當g較小時,鯰魚效應啟動次數較多,造成算法的收斂能力下降,導致均值降低并增大了標準差,而較差的全局最優值也會使得增強搜索的次數增加,提高了算法運行時間;隨著g的增加,算法的收斂能力也趨于增強,運行結果也逐漸變好;當g增加到一定程度之后,鯰魚效應啟動次數減少甚至不會啟動,這就減小了鯰魚效應對算法的增強作用,使得算法獲取較好解的能力下降,導致運行結果變差,使得增強搜索的運行次數再次增加,提高了算法的運行時間。在其他的G值條件下測試能夠得到相同的結論。通過實驗分析,g取值在7～11之間時,算法運行結果較好。

分析表6,在g=11時,G值不同,算法的均值、標準差也有所不同。當G較小時,鯰魚效應增強搜索運行次數較多,導致算法的全局搜索能力下降,均值降低,標準差增加;隨著G值逐漸趨近較好范圍,算法的全局搜索能力和局部開采能力達到較好的結合狀態,算法的運行結果也較好;進一步增加G值時,算法的增強搜索啟動次數減少,局部開采能力逐漸減弱,導致均值和標準差呈現較差趨勢;分析算法的運行時間,可以看出,算法運行時間對G值的變化并不敏感,這也驗證了鯰魚效應增強搜索的優越性。在其他的g值條件下測試能夠得到相同的結論。通過實驗分析,G取值在5～9之間時,算法運行結果較好。

4　結　論

為了求解子集問題,提出一種基于圖的螞蟻系統CBA-ACO。

針對BA算法過早收斂的問題,采用混沌映射對頻率搜索區間進行改進,一定程度上改善了BA的搜索能力;通過引入鯰魚效應,使得BA算法能夠跳出陷入局部最優的情況,進一步增強了BA算法全局搜索能力。

將改進后的鯰魚效應增強搜索加入GBAS中,在全局最優解多次未更新的情況下,通過保存較好路徑的檔案信息初始化并啟動增強搜索尋找更好的最優解,提高了算法的全局探測能力。對采用的鯰魚效應和增強搜索進行實驗,并對參數敏感性進行了分析,結果表明了改進的有效性,同時驗證了本文提出CBA-ACO具有更好的穩定性和獲取較好解的能力。

[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.(王會穎,賈瑞玉,章義剛,等.一種求解0-1背包問題的快速蟻群算法[J].計算機技術與發展,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.(胡小兵,黃席樾.基于蟻群優化算法的0-1背包問題求解[J].系統工程學報,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.(曹建軍, 張培林, 王艷霞, 等. 一種求解子集問題的基于圖的螞蟻系統[J].系統仿真學報, 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.(趙玉新, 楊新社, 劉利強. 新興元啟發式優化方法[M]. 北京:科學出版社, 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-),通信作者,男,工程師,博士,主要研究方向為進化算法、數據質量控制與數據治理。

E-mail:jianjuncao@yeah.net

丁鯤(1978-),男,高級工程師,碩士,主要研究方向為網絡管理。

E-mail:njdingkun@163.com

許永平(1979-),男,工程師,博士,主要研究方向為數據質量控制與數據治理。

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；網絡優先出版日期：2016-07-20。

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

TP 301.6

A

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

劉藝(1990-),男,博士研究生,主要研究方向為數據質量、進化算法。

E-mail:albertliu20th@sohu.com

刁興春(1964-),男,研究員,碩士,主要研究方向為數據工程。

E-mail:diaoxch640222@163.com

網絡優先出版地址：http://www.cnki.net/kcms/detail/11.2422.TN.20160720.1114.002.html