吳聰聰，賀毅朝，陳嶷瑛，劉雪靜，才秀鳳

(河北地質大學 信息工程學院,石家莊 050031)

變異蝙蝠算法求解折扣{0-1}背包問題

吳聰聰*，賀毅朝，陳嶷瑛，劉雪靜，才秀鳳

(河北地質大學 信息工程學院,石家莊 050031)

(*通信作者電子郵箱hebwucongcong@126.com)

針對確定性算法難于求解規(guī)模大、數(shù)據范圍廣的折扣{0-1}背包問題(D{0-1}KP)，提出了基于蝙蝠算法的快速求解D{0-1}KP的變異蝙蝠算法(MDBBA)。首先，利用雙重編碼解決D{0-1}KP的編碼問題；其次，將貪心修復與優(yōu)化算法(GROA)應用于蝙蝠個體適應度計算中，使算法快速得到有效解；然后，選擇使用差分演化(DE)的變異策略提高算法的全局尋優(yōu)能力；最后，蝙蝠個體按一定概率進行Lévy飛行，增強算法探索能力和跳出局部極值的能力。對四類大規(guī)模實例的仿真計算表明：MDBBA非常適于求解大規(guī)模的D{0-1}KP，比第一遺傳算法(FirEGA)和雙重編碼蝙蝠算法(DBBA)求得的最優(yōu)值和平均值都更優(yōu)，MDBBA收斂速度明顯快于DBBA。

折扣{0-1}背包問題；蝙蝠算法；差分演化；Lévy飛行；貪心策略；非正常編碼

0 引言

折扣{0-1}背包問題(Discounted {0-1}Knapsack Problem, D{0-1}KP)是經典0-1背包問題的一個擴展形式[1-4]，其思想源于商業(yè)領域的打折，在項目決策、投資和預算控制等方面具有廣闊的應用背景[2]。基于動態(tài)規(guī)劃求解D{0-1}KP的確定性算法是偽多項式時間的[1-2,4]，當問題規(guī)模較大并且各項的價值系數(shù)與重量系數(shù)在較大范圍內取值時，耗費大量的求解時間，缺乏實用性。 因此，探討利用進化算法快速求解D{0-1}KP的可行方法是一個值得研究的問題。

目前，D{0-1}KP的研究成果還相對較少，其中Guldan[1]首先提出了D{0-1}KP 問題，給出了D{0-1}KP的一個數(shù)學模型，并基于動態(tài)規(guī)劃給出了一個精確算法；Rong等[2]研究了D{0-1}KP 的核(Core)問題，并將動態(tài)規(guī)劃與核相結合求解D{0-1}KP；賀毅朝等[3]給出了D{0-1}KP的兩個新的數(shù)學模型，并基于精英保留策略遺傳算法(Elitist Genetic Algorithm, EGA)提出了求解D{0-1}KP兩個算法：第一遺傳算法(First Genetic Algorithm, FirEGA)和第二遺傳算法(Second Genetic Algorithm, SecEGA)；隨后，又在文獻[4]中給出了一系列的求解算法。

本文基于新型啟發(fā)式算法——蝙蝠算法(Bat Alogrithm, BA)[5]求解D{0-1}KP，首先提出利用雙重編碼的二進制蝙蝠算法(Double codes Binary Bat Algorithm，DBBA)[6]求解D{0-1}KP；為了消除求解過程中產生的不可行解，利用文獻[3]中貪心修復與優(yōu)化算法(Greedy Repair and Optimization Algorithm, GROA)對蝙蝠個體進行修復和優(yōu)化處理并計算適應度。然后，為進一步提高算法的求解精度和收斂速度提出了變異蝙蝠算法(Mutated Double Codes Binary Bat Algorithm，MDBBA)。在DBBA基礎上，加入差分演化的變異策略來提高種群的多樣性，以增強算法的全局尋優(yōu)能力；同時，讓每只蝙蝠按照50%的概率進行Lévy飛行，以避免算法陷入局部最優(yōu)。最后，對四類大規(guī)模D{0-1}KP實例的計算結果表明：對于大規(guī)模的D{0-1}KP 實例，MDBBA能夠快速求得一個近似比接近于1的近似解，其效果優(yōu)于FirEGA[3]和DBBA。

1 D{0-1}KP定義

定義[1]給定n個均含有3個項(或物品)的項集，項集i(0≤i≤n-1)中含有的3個項分別記為3i,3i+1,3i+2，其中前兩項具有的價值系數(shù)分別為v3i和v3i+1，具有的重量系數(shù)分別為w3i和w3i+1；前兩項合并到一起構成第三項3i+2，它具有的價值系數(shù)為v3i+2=v3i+v3i+1，具有的折扣重量系數(shù)為w3i+2，滿足w3i+2w3i，w3i+2>w3i+1。對于每個項集i(0≤i≤n-1)，項3i,3i+1,3i+2最多有一個被選中裝入背包中。如何選擇各項裝入背包，使得被裝入背包的所有項的重量系數(shù)之和在不超過背包載重C的前提下價值系數(shù)和最大？

Guldan給出了D{0-1}KP的第一個數(shù)學模型，描述如下：

(1)

s.t.x3i+x3i+1+x3i+2≤1;i=0,1,…,n-1

(2)

(3)

x3i,x3i+1,x3i+2∈{0,1},i=0,1,…,n-1

(4)

其中: 二元變量xj(0≤i≤3n-1)表示項j是否被裝入背包中，即xj=1表示第j項被裝入了背包中，xj=0表示第j項未被裝入背包。顯然，任意向量X=[x0,x1,x2,…,x3n-1]∈{0,1}3n僅僅表示D{0-1}KP的一個潛在解，只有當它同時滿足了約束條件(2)和(3)時才是一個可行解。

2 雙重編碼的蝙蝠算法

蝙蝠算法(BA)是Yang[5]于2010年提出的一種新型啟發(fā)式算法，其思想源于蝙蝠尋找獵物過程中回聲定位原理。目前，該算法已引起國內外學者的廣泛關注，成為計算智能研究領域的一個新的研究熱點，學者們不但對算法的性能進行各種改進[7-10]，并將其成功地應用到工程設計[11-13]、分類[14]、神經網絡[15]和模糊聚類[16]等領域。

蝙蝠算法是解決連續(xù)變量的函數(shù)優(yōu)化問題，它將種群數(shù)量為N的蝙蝠飛行的位置映射成d維問題空間中的N個解向量，通過蝙蝠種群飛行的過程來進行問題的優(yōu)化求解，用求解問題的適應度函數(shù)值來衡量每個蝙蝠的位置Xi=[xi1,xi2,…,xid]的好壞，每只蝙蝠在種群最優(yōu)解影響下飛行，直至達到全局最優(yōu)解。為了將蝙蝠算法應用于折扣背包問題求解，這里為每只蝙蝠設置了雙重編碼[6,17]，即針對每只蝙蝠的實數(shù)位置Xi引入一個的二進制位置Bi=[bi1,bi2,…,bid]，映射關系如式(5)[6]：

(5)

其中xij∈[-1,1]是第i只蝙蝠在第j維的實數(shù)值。這樣每只蝙蝠可表示成一個二元組(Xi(t),Bi(t))，其中Xi(t)=[xi1(t),xi2(t),…,xid(t)] ∈[-1,1]d是第t代第i個蝙蝠的實數(shù)位置；Bi(t)=[bi1(t),bi2(t),…,bid(t)]∈{0,1}d是該蝙蝠的二進制位置。蝙蝠的適應度函數(shù)按它的二進制位置計算f(Bi(t))，蝙蝠的實數(shù)位置Xi(t)按式(6)～(8)更新:

fi(t)=fmin+(fmax-fmin)*β

(6)

Vi(t+1)=Vi(t)+(Xi(t)-Y)*fi(t)

(7)

Xi(t+1)=Xi(t)+Vi(t)

(8)

其中:fi(t)∈[fmin,fmax]是第t代第i個蝙蝠的頻度;β∈[0,1]是隨機數(shù);Vi(t)是第t代第i個蝙蝠的飛行速度;Y是第t代蝙蝠群體最優(yōu)實數(shù)位置。

設(hXi(t),hBi(t))為第t代第i個蝙蝠的歷史最優(yōu)個體；(Y,P)為蝙蝠群最優(yōu)個體。下面以求解最大約束優(yōu)化問題maxf(X)為例給出具有雙重編碼的二進制蝙蝠算法(DBBA)[6]的描述。

算法1 DBBA[6]。

輸入 maxf(X)，最大迭代次數(shù)MaxIt;

輸出 最優(yōu)解P，適應度函數(shù)值f(P)。

步驟1 隨機產生初始蝙蝠群實數(shù)位置，用式(3)計算得到蝙蝠的二進制位置，令迭代次數(shù)t=0。

步驟2 設置每只蝙蝠的初始速度Vi，脈沖發(fā)射速率fi、脈沖響度ai和脈沖頻率ri的初始值。

步驟3 計算每只蝙蝠適應度，令其歷史最好個體等于該蝙蝠個體，根據各個蝙蝠適應值找出最好的蝙蝠Xk，令全局最優(yōu)等于該蝙蝠。

步驟4

While(tf(hBi(t)) 更新該蝙蝠的歷史最優(yōu)個體EndIfIf(rand1>ri) 利用式(9)將蝙蝠更新到某較好蝙蝠的附近EndIf隨機產生一個新蝙蝠(Xnew,Bnew) if(rand2f(Bnew)>f(P))P=Bnew,Y=Xnew; 用式(10)和(11)減小ai和增大ri

EndIf

EndFor

找到種群中歷史適應度最好的蝙蝠，如果該歷史最優(yōu)個體好于全局最優(yōu)，則替代全局最優(yōu)個體(Y,P)

EndWhile

步驟5 輸出P和f(P)。

下面是算法中用到的公式。

Xnew=Xk(t) +εa；ε∈[0,1]是隨機數(shù)

(9)

ai=?ai

(10)

ri=ri[1-exp(-γt)]

(11)

式(9)中的a是所有蝙蝠響度ai的平均值；式(10)、(11)中00都是常數(shù)因子[5]，本文實驗中?=γ=0.9。關于蝙蝠算法中各公式詳細介紹請參考文獻[5],限于篇幅不再贅述。

3 變異蝙蝠算法求解折扣背包問題

3.1 編碼的處理

根據Guldan給出的數(shù)學模型，在利用雙重編碼的蝙蝠算法求解D{0-1}KP時，個體蝙蝠的十進制編碼X=[x0,x1,x2,…,x3n-1]∈[0,1]3n，對應的二進制編碼為B=[b0,b1,b2,…,b3n-1] ∈{0,1}3n，當bj=1(0≤j≤3n-1)時，表示項j被裝入背包，bj=0表示項j沒有被裝入。這種編碼方法雖然簡單易行，但也存在一個明顯的缺點，就是不可行解會非常多[3]。本文將GROA[3]應用到對蝙蝠個體適應度值的計算中，消除不可行解并對可行解進行優(yōu)化。設V={{v3i,v3i+1,v3i+2}|0≤i≤n-1}為D{0-1}KP的各項的價值集，W={{w3i,w3i+1,w3i+2}|0≤i≤n-1}為各項的重量集，C為背包載重。將3n個項根據價值密度vj/wj(0≤j≤3n-1)由大到小排序，并按照排序后的順序將各項的下標存入數(shù)組sort[0…3n-1]中。設置數(shù)組flag[0…n-1]∈{0,1}n標識各項集的狀態(tài)，flag[i]=0表示項集i中沒有項被裝入背包，flag[i]=1表示項集i中恰有一項被裝入背包，?i/3」表示對i/3向下取整。E=[e1,e2,…,e3n-1]∈{0,1}3n為修正優(yōu)化后的二進制編碼，G=[g1,g2,…,g3n-1]∈[0,1]3n為其對應的十進制編碼。f(E)為修正優(yōu)化后蝙蝠個體的適應度值。將GROA[3]應用到計算蝙蝠個體的適應度的函數(shù)GETFIT中，描述如下：

算法2 GETFIT。

輸入 原蝙蝠個體(X,B)和sort[0…3n-1]；

輸出 修正后的蝙蝠個體(G,E)及適應度值f(E)。

weight=0,value=0For(j=0; j<3n-1; j++) ej=0

For(i=0; i

For(j=0; j<3n-1; j++)If(bsort[j]=1 & weight+wsort[j]≤C & flag[?sort[j]/3」]=0) esort[j]=1，gsort[j]=xsort[j]， value=value+vsort[j]weight=weight+wsort[j]，flag[?sort[j]/3」]=1

EndIf

EndFor

For(j=0; j<3n-1; j++)If((weight+wsort[j]≤C) & flag[?sort[j]/3」]=0)) esort[j]=1，gsort[j]=rand(), rand()∈[0,1]weight=weight+wsort[j]， flag[?sort[j]/3」]=1value=value+vsort[j]

EndIf

EndFor

f(E)=value

return(G,E, f(E))

將GETFIT算法應用于算法DBBA求解適應度值，即可求解D{0-1}KP，第4章對比實驗中算法DBBA就是使用GETFIT后的DBBA。

3.2 基于差分的變異策略

差分演化的變異算子存在多種形式,其一般表示為DE/x/y/z[18]，x表示變異算子中差異向量進行重組的基準個體是隨機選取的還是當前群體的最優(yōu)個體；y表示參與重組的差異向量個數(shù)；z表示重組所采用的方式，主要有指數(shù)重組方式和二項式重組方式，這里使用二項式重組。文獻[19]把二項式重組變異算子分為3類：第1類為DE/rand/1/bin和DE/rand/2/bin；第2類為DE/best/1/bin和DE/best/2/bin；第3類是DE/rand-to-best/1/bin模式。為了提高蝙蝠算法種群的多樣性，本文從每類模式中選擇一種分別應用于蝙蝠算法中，測試其有效性。測試數(shù)據將在第4章給出。變異策略用算法DEM(DifferentEvolutionMutation)實現(xiàn)：

算法3DEM。

輸入 原蝙蝠個體，原適應度值；

輸出 經過變異策略后的蝙蝠個體，新適應度值。

1)應用差分變異算子產生子蝙蝠個體十進制位置；

2)根據式(3)計算子蝙蝠的二進制位置；

3)用GETFIT得到子蝙蝠的適應值；

4)如果子蝙蝠的適應度好于原蝙蝠；

5)用子蝙蝠替換原蝙蝠。

變異操作使得蝙蝠個體之間可以相互交流，增加了蝙蝠群體探索和尋優(yōu)能力，另外精英個體保留機制提高了算法的收斂速度。

3.3Lévy飛行

啟發(fā)式算法在尋優(yōu)過程中往往容易陷入局部極值，這里通過蝙蝠個體的Lévy飛行來降低算法陷入局部極值的可能性。Lévy飛行是一種隨機游走過程，它的步長是一種連續(xù)的重尾分布[20]。從數(shù)學角度看，Lévy飛行行為體現(xiàn)出的是一類非高斯隨機過程，其平穩(wěn)增量服從Lévy穩(wěn)定分布，Lévy飛行過程中會發(fā)生大的跳躍且方向多變，其典型軌跡表現(xiàn)為由較小跳躍組成的聚集被較大的跳躍分隔開的現(xiàn)象，可以借助大的跳躍逃離局部極值[21]。為了避免算法過早地陷入局部極值中，在算法中，每次迭代后個體蝙蝠按照一定概率(本文定為0.5)進行Lévy飛行，按式(12)產生飛行后的十進制位置[20]：

Xi′=Xi+a⊕Lévy(λ)

(12)

其中：Xi為原蝙蝠實數(shù)位置，Xi′為飛行后的實數(shù)位置,其中Lévy(λ)來自于Lévy分布[20]。用式(5)確定其二進制位置后通過GETFIT算法計算飛行后的適應度值，如果適應度優(yōu)于原蝙蝠則用新位置替代原蝙蝠的位置。

3.4 變異蝙蝠算法求解折扣背包問題流程

用算法MDBBA求解D{0-1}問題的蝙蝠算法流程如圖1所示。每只蝙蝠的適應度均由算法GETFIT求得；用式(6)～(8)、(5)更新蝙蝠的速度Vi(t)和實數(shù)位置Xi(t)和二進制位置Bi(t)。MP是蝙蝠進行變異操作的概率，本文設為0.8；rand1，rand2，rand3，rand4均為在[0,1]上產生的隨機數(shù)。

4 仿真實驗結果分析

使用文獻[3]給出的4類D{0-1}KP實例：不相關D{0-1}KP實例(Uncorrelated instances of D{0-1}KP，UDKP)、弱相關D{0-1}KP 實例(Weakly correlated instances of D{0-1}KP，WDKP)、強相關D{0-1}KP 實例(Strongly correlated instances of D{0-1}KP, SDKP)和逆向強相關D{0-1}KP實例(Inverse strongly correlated instances of D{0-1}KP，IDKP)，其中每類有10 個不同規(guī)模的實例。關于實例詳細介紹請參考文獻[3]。本文針對4類D{0-1}KP實例進行了兩組實驗：實驗1是將三種差分的變異算子分別與蝙蝠算法結合，通過對實例運行結果的箱圖(BOXPLOT)分析確定使用的變異算子; 實驗2是通過四類大規(guī)模D{0-1}KP 實例的各種計算結果,對MDBBA與DBBA和文獻[3]的FirEGA算法進行比較。仿真計算所使用微機的硬件環(huán)境為，操作系統(tǒng)Windows 10，編程環(huán)境VC++2010。MDBBA與DBBA各個參數(shù)的設置：Xmax=1.0；Xmin=-1.0；Vmax=1.0；fmin=0.01；fmax=0.071；蝙蝠個體初始脈沖頻率r0=0.05；初始化脈沖響度a0=1.0；脈沖音強衰減系數(shù)和脈沖頻率增強系數(shù)=0.9；變異概率MP=0.8，Lévy飛行概率為0.5；種群規(guī)模是40；迭代次數(shù)均等于實例的規(guī)模(即3n)。FirEGA算法數(shù)據來自文獻[3]。

圖1 變異蝙蝠算法求解折扣背包算法流程Fig. 1 Flowchart of mutated bat algorithm for solving D{0-1}KP

4.1 變異算子性能比較

這里將DE/rand/1/bin、DE/best/1/bin、DE/rand-to-best/1/bin(編號為1、2、3)三種變異算子分別應用于蝙蝠算法中，測試其有效性。抽取維數(shù)為100和500的8組實例進行測試。圖2、3是30次獨立運行各組合形式得到的最優(yōu)值的統(tǒng)計結果形成的箱圖。根據八個箱圖比較,第2類模式的變異算子(編號2)使得算法有較高的穩(wěn)定性，產生的最優(yōu)值也基本都高于另外兩類模式，所以本文確定使用DE/best/1/bin作為變異算子。實驗2中算法MDBBA變異部分使用該變異算子。

4.2 MDBBA、DBBA與FirEGA的實驗結果比較

利用FirEGA、DBBA與MDBBA求解四類D{0-1}KP 實例的計算結果見表1～4，其中Opt為由動態(tài)規(guī)劃法(記為DPDKP)計算出的實例最優(yōu)值；Best、Worst 和Mean 分別為FirEGA，DBBA與MDBBA在30次獨立計算中得到的所有結果的最好值、最差值以及所有結果的數(shù)學期望；Opt/Best、Opt/Worst 和Opt/Mean 分別表示以上各值的近似比[22-23]。

為更直觀地比較實驗結果，將FirEGA、DBBA與MDBBA求解四類D{0-1}KP 實例的最好值近似比和平均值近似比以曲線圖的形式展現(xiàn)出來，如圖4～11。

圖2 三種不同算子在100維四類實例下的比較Fig. 2 Comparison of 3 different operators in 4 types of 100 dimensions

圖3 三種不同算子在500維四類實例下的比較Fig. 3 Comparison of 3 different operators in 4 types of 500 dimensions

圖4 UDKP類實例最好值的近似比Fig. 4 Approximate ratio of the best value of UDKP

圖5 UDKP類實例平均值的近似比Fig.5 Approximate ratio of the average of UDKP

從表1中可以看出：FirEGA求解UDKP實例所得最好值的近似比基本在1.10左右，平均值和最差值的近似比均不超過1.144 1；DBBA所得最好值的近似比在1.16 左右，平均值和最差值的近似比都在1.213 6以下；MDBBA求解UDKP實例所得最好值的近似比在1.09左右，平均值和最差值的近似比均不超過1.148 3。圖4是三種算法求解UDKP1～UDKP10

實例的最好值的近似比比較，圖5是三種算法求解UDKP1～UDKP10實例平均值的近似比比較圖。從兩圖中可以看出，DBBA求解能力最差，經過加入變異和Lévy飛行后的MDBBA求解能力有很大的提高，最好值近似比和平均值近似比基本和FirEGA相當，有4個實例超出FirEGA。

表1 對實例UDKP1～UDKP10的實驗結果比較Tab. 1 Comparison of experimental results of examples UDKP1 ～ UDKP10

表2 對實例WDKP1～WDKP10的實驗結果對比Tab. 2 Comparison of Experimental Results of Examples WDKP1 ～ WDKP10

從表2中可以看出FirEGA求解WDKP實例所得到的最好值的近似比不超過1.009 4，平均值的近似比不超過1.013 1，最差值的近似比不超過1.028 2；DBBA求解WDKP實例所得到的最好值的近似比不超過1.009 2，平均值的近似比不超過1.009 6，最差值的近似比不超過1.034 0；MDBBA求解WDKP實例所得到的最好值的近似比不超過1.008 3，平均值的近似比不超過1.009 1，最差值的近似比不超過1.009 2。圖6是三種算法求解WDKP1～WDKP10實例的最好值的近似比比較，圖7是平均值的近似比比較。DBBA在求解WDKP實例中求得最優(yōu)值近似比，平均值近似比都好于FirEGA；而MDBBA的最好值近似比、平均值近似比在每個實例上都優(yōu)與DBBA。

表3 對實例IDKP1～IDKP10的實驗結果對比Tab. 3 Comparison of Experimental Results of Examples IDKP1 ～ IDKP10

圖6 WDKP類實例最好值的近似比Fig. 6 Approximate ratio of the best value of WDKP

圖7 WDKP類實例平均值的近似比Fig. 7 Approximate ratio of the average of WDKP

圖8 IDKP類實例最好值的近似比Fig. 8 Approximate ratio of the best value of IDKP

從表3中可以看出：FirEGA求解IDKP實例所得最好值的近似比不超過1.005 1，平均值的近似比不超過1.011 3，最差值的近似比不超過1.053 4；DBBA求解IDKP 實例所得到的最好值的近似比不超過1.000 7，平均值的近似比不超過1.002 5，最差值的近似比不超過1.026 4；MDBBA求解IDKP 實例所得到的最好值的近似比不超過1.000 4，平均值的近似比不超過1.001 4，最差值的近似比不超過1.003 7。圖8是三種算法求解IDKP1～IDKP10實例的最好值的近似比，圖9是平均值的近似比。從兩圖中明顯看出DBBA和MDBBA求解效果明顯優(yōu)于FirEGA；DBBA和MDBBA比較，MDBBA求解效果和平均求解能力都更好。

圖9 IDKP類實例平均值的近似比Fig. 9 Approximate ratio of the average of IDKP

圖10 SDKP類實例最好值的近似比Fig. 10 Approximate ratio of the best value of SDKP

從表4中可以看出：FirEGA求解SDKP 實例所得到的最好值的近似比均不超過1.026 3，平均值的近似比不超過1.035 1，最差值的近似比也均不超過1.042 3；DBBA求解SDKP 實例所得到的最好值的近似比不超過1.026 0，平均值的近似比不超過1.038 8，最差值的近似比不超過1.048 0；MDBBA求解SDKP 實例所得到的最好值的近似比不超過1.022 3，平均值的近似比不超過1.026 7，最差值的近似比不超過1.033 3。圖10是三種算法求解SDKP1～SDKP10實例的最好值的近似比比較，圖11是平均值的近似比比較圖，從兩圖中看出：雙重編碼蝙蝠算法DBBA求解SDKP實例能力比FirEGA略弱，MDBBA在求解能力上優(yōu)于FirEGA。

圖11 SDKP類實例平均值的近似比Fig. 11 Approximate ratio of the average of SDKP

為了進一步比較雙重編碼蝙蝠算法DBBA和變異雙重編碼蝙蝠算法MDBBA的平均求解性能，圖12給出它們30 次獨立運行實例UDKP5、WDKP5、SDKP5和IDKP5 的平均收斂曲線。由圖可以看出：MDBBA的平均收斂速度非?？?，基本上在不超過0.2*MaxIt 的迭代次數(shù)內即可獲得極好的結果；DBBA的平均收斂速度相對慢，并且它的平均求解結果也明顯比MDBBA的差。

圖12 對DBBA和MDBBA平均收斂曲線比較Fig. 12 Comparison of average convergence curve of DBBA and MDBBA

基于對四類D{0-1}KP實例的計算、比較和分析可以知，對于項的價值系數(shù)和重量系數(shù)均在大范圍內隨機取值的D{0-1}KP實例，MDBBA均能夠求得一個近似比接近于1 的近似解，是求解大規(guī)模難D{0-1}KP實例的有效且實用的進化算法。從算法求得的最好結果來看，DBBA、MDBBA和FirEGA的求解能力基本相當，DBBA在求解UDKP實例中效果明顯不如MDBBA和FirEGA；從算法的平均求解性能來看，MDBBA的求解效果優(yōu)于FirEGA和DBBA。

表4 對實例SDKP1～SDKP10的實驗結果對比Tab. 4 Comparison of experimental results of examples SDKP1 ～ SDKP10

5 結語

本文研究了如何利用變異蝙蝠算法求解D{0-1}KP，提出利用雙重編碼方式求解D{0-1}KP，將貪心和優(yōu)化策略應用于個體適應度求解中；針對蝙蝠算法易早熟、求解精度不高的缺陷，在蝙蝠群更新位置后利用差分變異增加種群多樣性，提高全局搜索能力；通過蝙蝠個體的Lévy飛行避免群體過早的陷入局部極值。對四類大規(guī)模D{0-1}KP實例的計算結果比較與分析，MDBBA不受實例中各項的價值系數(shù)、重量系數(shù)和背包載重的大小影響，對于大規(guī)模的難D{0-1}KP實例，能夠快速求得一個近似比接近于1的近似解。比基本雙重編碼的蝙蝠算法無論在收斂速度還是在尋優(yōu)能力上都有極大提高，是求解大規(guī)模難D{0-1}KP實例的實用進化算法。

)

[1]GULDANB.Heuristicandexactalgorithmsfordiscountedknapsackproblems[D].Nuremberg:UniversityofErlangen-Nuremberg, 2007.

[2]RONGA,FIGUEIRAJR,KLAMROTHK.Dynamicprogrammingbasedalgorithmsforthediscounted{0-1}knapsackproblem[J].AppliedMathematicsandComputation, 2012, 218(12): 6921-6933.

[3] 賀毅朝, 王熙照，李文斌, 等. 基于遺傳算法求解折扣{0-1}背包問題的研究[J].計算機學報,2016,39(12):2614-2630.(HEYC,WANGXZ,LIWB,etal.Researchongeneticalgorithmsforthediscounted{0-1}knapsackproblem[J].ChineseJournalofComputers, 2016,39(12):2614-2630.)

[4]HEY,WANGX,HEY,etal.Exactandapproximatealgorithmsfordiscounted{0-1}knapsackproblem[J].InformationSciences, 2016, 369(10): 634-647.

[5]YANGX.Anewmetaheuristicbat-inspiredalgorithm[C]//NICSO2010:NatureInspiredCooperativeStrategiesforOptimization.Berlin:Springer, 2010, 284: 65-74.

[6] 吳聰聰，賀毅朝，陳嶷瑛,等. 求解0-1背包問題的二進制蝙蝠算法[J].計算機工程與應用, 2015, 51(19):71-74.(WUCC,HEYC,CHENYY,etal.Binarybatalgorithmforsolving0-1knapsackproblem[J].ComputerEngineeringandApplications, 2015,51(19):71-74.)

[7] 賀興時，丁文靜，楊新社.基于模擬退火高斯擾動的蝙蝠優(yōu)化算法[J],計算機應用研究,2013, 31(2)：392-397.(HEXS,DINGWJ,YANGXS.BatalgorithmbasedonsimulatedannealingandGaussianperturbations[J].ApplicationResearchofComputers, 2013, 31(2):392-397.)

[8] 謝健，周永權，陳歡.一種基于Lévy飛行軌跡的蝙蝠算法[J].模擬識別與人工智能,2013,26(9): 829-837.(XIEJ,ZHOUYQ,CHENH.AbatalgorithmbasedonLévyflightstrajectory[J].PatternRecognitionandArtificialIntelligence, 2013,26(9)：829-837.)

[9] 劉長平，葉春明.具有混沌搜索策略的蝙蝠優(yōu)化算法及性能仿真[J].系統(tǒng)仿真學報,2013,25(6): 1183-1188.(LIUCP,YECM.Batalgorithmwithchaoticsearchstrategyandanalysisofitsproperty[J].JournalofSystemSimulation,2013,25(6): 1183-1188.)

[10]YANGX.Batalgorithmformultiobjectiveoptimization[J].InternationalJournalofBio-InspiredComputation, 2011, 3(5):267-274.

[11]YANGX,GANDOMIAH.Batalgorithm:anovelapproachforglobalengineeringoptimization[J]．EngineeringComputations，2012, 29(5): 464-483.

[12]LEMMATA,BINMHF.Useoffuzzysystemsandbatalgorithmforenergymodelinginagasturbinegenerator[C]//Proceedingsofthe2011IEEEColloquiumonHumanities,ScienceandEngineering.Piscataway,NJ:IEEE, 2011: 305-310.

[13] 盛曉華，葉春明.基于蝙蝠算法的PFSP調度干擾管理研究[J]. 計算機工程與應用, 2014,50(8):241-246. (SHENGXH,YECM.ResearchofbatalgorithmfordisruptionmanagementonPFSPscheduling[J].ComputerEngineeringandApplications, 2014,50(8): 241-246.)

[14]MISHRAS,SHAWK,MISHRAD.Anewmeta-heuristicbatinspiredclassificationapproachformicroarraydata[J].ProcediaTechnology, 2012, 4(1): 802-806.

[15]KHANK,SAHAIA.AcomparisonofBA，GA，PSO，BPandLMfortrainingfeedforwardneuralnetworksine-learningcontext[J]．InternationalJournalofIntelligentSystemsandApplications，2012,4(7) : 23-29.

[16]KHANK，NIKOVA，SAHAIA.Afuzzybatclusteringmethodforergonomicscreeningofofficeworkplaces[C]//Proceedingsofthe3rdInternationalConferenceonSoftware,ServicesandSemanticTechnologies.Berlin:Springer, 2011: 59-66.

[17] 賀毅朝，王彥祺，劉建芹．一種適于求解離散問題的二進制粒子群優(yōu)化算法[J]．計算機應用與軟件, 2007,24(1):157-159.(HEYC,WANGYQ,LIUJQ.Anewbinaryparticleswarmoptimizationforsolvingdiscreteproblems[J].ComputerApplicationsandSoftware, 2007,24(1):157-159.)

[18]NOMANN,IBAH.Enhancingdifferentialevolutionperformancewithlocalsearchforhighdimensionalfunctionoptimization[C]//Proceedingsofthe7thAnnualConferenceonGeneticandEvolutionaryComputation.NewYork:ACM, 2005: 967-974.

[19] 賀毅朝,王熙照, 劉坤起,等.差分演化的收斂性分析與算法改進[J]. 軟件學報,2010,21(5): 875-885.(HEYC,WANGXZ,LIUKQ,etal.Convergentanalysisandalgorithmicimprovementofdifferentialevolution[J].JournalofSoftware, 2010, 21(5): 875-885.)

[20]YANGX,DEBS.CuckoosearchviaLévyflights[C]//ProceedingsofWorldCongressonNature&BiologicallyInspiredComputing.Piscataway,NJ:IEEE, 2009: 210-214.

[21] 劉長平，葉春明.具有Lévy飛行特征的蝙蝠算法[J].智能系統(tǒng)學報，2013,8(3):240-246.(LIUCP,YECM.BatalgorithmwiththecharacteristicsofLévyflights[J].CAAITransactionsonIntelligentSystems,2013,8(3):240-246.)

[22]CORMENTH,LEISERSONCE,RIVESTRL,etal.IntroductiontoAlgorithms[M]. 3rded.Cambridge:MITPress, 2001:1117-1119.

[23]ALSUWAIYELMH.AlgorithmsDesignTechniquesandAnalysis[M].Singapore:WorldScientificPublishingCompany, 1999:410-418.

ThisworkispartiallysupportedbyScientificResearchProjectProgramofCollegesandUniversitiesinHebeiProvince(ZD2016005),theNaturalScienceFoundationofHebeiProvince(F2016403055).

WU Congcong, born in 1975, M. S., lecturer. Her research interests include intelligent computing, information retrieval, machine learning.

HE Yichao,born in 1969, M. S., professor. His interests include the theory and applications of evolutionary algorithm, design and analysis of algorithms,computational complexity theory and group testing theory.

CHEN Yiying,born in 1971, Ph.D., professor. Her research interests include machine learning, geographic information system.

LIU Xuejing,born in 1980, M. S., lecturer. Her research interests include intelligent computing, machine learning.

CAI Xiufeng,born in 1979, M. S., lecturer. Her research interests include intelligent computing, machine learning.

Mutated bat algorithm for solving discounted {0-1} knapsack problem

WU Congcong*, HE Yichao,CHEN Yiying, LIU Xuejing,CAI Xiufeng

(CollegeofInformationEngineering,HebeiGEOUniversity,ShijiazhuangHebei050031,China)

Since the deterministic algorithms are difficult to solve the Discounted {0-1} Knapsack Problem (D{0-1}KP) with large-scale and wide data range, a Mutated Double codes Binary Bat Algorithm (MDBBA) was proposed. Firstly, the coding problem of D{0-1} KP was solved by double coding. Secondly, the Greedy Repair and Optimization Algorithm (GROA) was applied to the individual fitness calculation of bats, and the algorithm was quickly and effectively solved. Then, the mutation strategy in Differential Evolution (DE) was selected to improve the global optimization ability. Finally, Lévy flight was carried out by the bat individual according to certain probability to enhance the ability of the algorithm to explore and jump out of local extrema. Simulation was tested on four large-scale instances. The result shows that MDBBA is very suitable for solving large-scale D {0-1} KP, which has better optimal value and mean value than FirEGA (First Genetic Algorithm) algorithm and Double Binary Bat Algorithm (DBBA), and MDBBA converges significantly faster than DBBA.

Discounted {0-1} Knapsack Problem (D{0-1}KP); Bat Algorithm (BA); differential evolution; Lévy flight; greedy strategy; non-normal coding

2016-10-24;

2016-12-08。

河北省高等學?？茖W研究計劃項目(ZD2016005);河北省自然科學基金資助項目(F2016403055)。

吳聰聰(1975—)，女，河北唐山人，講師，碩士，主要研究方向：智能計算、信息檢索、機器學習； 賀毅朝(1969—)，男，河北晉州人，教授， CCF高級會員，主要研究方向：進化算法理論與應用、算法設計與分析、計算復雜性理論與群測試理論； 陳嶷瑛(1971—)，女，湖南寧遠人，教授，博士，主要研究方向:機器學習、地理信息系統(tǒng)； 劉雪靜(1980—)，女，河北定州人，講師，碩士，主要研究方向:智能計算、機器學習；才秀鳳(1979—)，女，河北豐潤人，講師，碩士，主要研究方向:智能計算、機器學習。

1001-9081(2017)05-1292-08

10.11772/j.issn.1001-9081.2017.05.1292

TP18

A