自適應(yīng)細(xì)菌覓食算法求解折扣{0-1}背包問(wèn)題

劉雪靜，賀毅朝，吳聰聰，李 靚

1.河北地質(zhì)大學(xué) 信息工程學(xué)院，石家莊 050031

2.中國(guó)郵政集團(tuán)公司 河北省郵政信息技術(shù)局，石家莊 050011

1 引言

0-1背包問(wèn)題（0-1 Knapsack Problem，0-1KP）[1]是典型的組合優(yōu)化問(wèn)題，屬于NP-complete問(wèn)題，資源分配、材料切割、貨物裝載等領(lǐng)域里的許多問(wèn)題均可建模成0-1KP進(jìn)行研究。0-1KP有許多不同的形式，折扣{0-1}背包問(wèn)題（Discount{0-1}Knapsack Problem，D{0-1}KP）是新型的0-1KP。2007年Guldan[2]首先提出了D{0-1}KP，給出了其第一數(shù)學(xué)模型，賀毅朝等[3]給出了其第二數(shù)學(xué)模型，兩個(gè)數(shù)學(xué)模型描述如下。

定義1[2]給定n個(gè)項(xiàng)集，每一項(xiàng)集(0≤i≤n-1)中均含項(xiàng)3i、3i+1和3i+2，項(xiàng)3i的價(jià)值系數(shù)為 p3i，重量系數(shù)為w3i，項(xiàng)3i+1的價(jià)值系數(shù)為 p3i+1，重量系數(shù)為w3i+1，項(xiàng)3i+2的價(jià)值系數(shù)為 p3i+2=p3i+p3i+1，折扣重量系數(shù)為 w3i+2，且滿(mǎn)足 w3i+2＞w3i、w3i+2＞w3i+1和w3i+2

其中，xk(0≤k≤3n-1)的取值表示項(xiàng)k是否被裝入背包，xk=1表示項(xiàng)k裝入背包，xk=0表示項(xiàng)k未裝入。顯然，任意的二進(jìn)制向量X=[x0,x1,…,x3n-1]僅是D{0-1}KP的一個(gè)潛在解，只有同時(shí)滿(mǎn)足約束條件（2）～（4）的X才是D{0-1}KP的一個(gè)可行解。

D{0-1}KP的第二數(shù)學(xué)模型[3]描述如下：

其中，X=[x0,x1,…,xn-1]∈{0,1,2,3}n是n維整型向量為不小于x的最小整數(shù)，xi=0表示項(xiàng)集i中沒(méi)有項(xiàng)裝入背包，xi=1表示項(xiàng)3i被裝入背包，xi=2表示項(xiàng)3i+1被裝入背包，xi=3表示項(xiàng)3i+2被裝入背包。整型向量X僅表示D{0-1}KP的一個(gè)潛在解，只有滿(mǎn)足約束條件（6）和（7）的X 才是D{0-1}KP的一個(gè)可行解。

2 相關(guān)研究工作

細(xì)菌覓食（Bacterial Foraging Optimization，BFO）算法[4]是Passino在研究大腸桿菌吞噬食物行為的基礎(chǔ)上提出來(lái)的一種仿生隨機(jī)搜索算法。目前，BFO已被廣泛應(yīng)用于許多領(lǐng)域。崔靜靜等[5]將BFO進(jìn)行改進(jìn)，將其用于求解車(chē)間作業(yè)調(diào)度；王雪松等[6]將細(xì)菌的趨化性運(yùn)動(dòng)引入到分布估計(jì)算法中，提出一種基于細(xì)菌覓食行為的分布估計(jì)算法；Panda等[7]提出一種基于細(xì)菌覓食的面部識(shí)別算法；李珺等[8]將多種策略應(yīng)用到BFO算法中求解高維優(yōu)化問(wèn)題；Manikandan等[9]通過(guò)將BFO算法與遺傳算法相結(jié)合求解多目標(biāo)問(wèn)題。總之，當(dāng)前對(duì)BFO算法的研究主要體現(xiàn)在對(duì)原算法的改進(jìn)和實(shí)際的應(yīng)用，而改進(jìn)主要是在趨化操作中引入自適應(yīng)機(jī)制或與其他智能算法相結(jié)合。

Guldan[2]首先利用動(dòng)態(tài)規(guī)劃法進(jìn)行求解D{0-1}KP的第一數(shù)學(xué)模型；Rong等[10]將動(dòng)態(tài)規(guī)劃法與D{0-1}KP的core相結(jié)合求解D{0-1}KP。確定性算法求解D{0-1}KP是偽多項(xiàng)式時(shí)間的，當(dāng)各項(xiàng)的重量系數(shù)和價(jià)值系數(shù)較大時(shí)，算法不可行。目前，進(jìn)化算法求解D{0-1}KP取得了許多可以借鑒的研究成果。賀毅朝等[3]提出了D{0-1}KP的第二數(shù)學(xué)模型和第三數(shù)學(xué)模型，并率先利用遺傳算法進(jìn)行求解，雖然不能得到最優(yōu)解，但求得了較好的近似解；吳聰聰?shù)萚11]利用改進(jìn)的蝙蝠算法求解D{0-1}KP，得到較優(yōu)近似解；劉雪靜等[12]利用細(xì)菌覓食算法求解D{0-1}KP，得到近似比接近1的近似解，但是耗費(fèi)時(shí)間較多；He等[13]提出了求解D{0-1}KP的二進(jìn)制粒子群算法；Feng等[14]利用改進(jìn)的帝王蝶算法求解D{0-1}KP，得到較好的求解結(jié)果；劉雪靜等[15]利用烏鴉算法求解D{0-1}KP，取得較優(yōu)解；Zhu等[16]利用差分演化算法求解該問(wèn)題，并給出了三個(gè)高效離散演化算法，求得較好解。由此可見(jiàn)，如何利用進(jìn)化算法高效、快速求解D{0-1}KP非常值得研究。

3 自適應(yīng)細(xì)菌覓食算法求解D{0-1}KP

3.1 細(xì)菌覓食算法

BFO算法是一種新型仿生優(yōu)化算法，其求解優(yōu)化問(wèn)題的一般過(guò)程為：產(chǎn)生初始解種群，計(jì)算適應(yīng)度函數(shù)值，群體間通過(guò)趨化、復(fù)制、遷徙進(jìn)行迭代優(yōu)化，直至產(chǎn)生最終解。算法如圖1所示，其中，S為種群大小，Ned為遷徙次數(shù)，Nre為復(fù)制次數(shù)，Nc為趨化次數(shù)，Ns為游動(dòng)次數(shù)，Ped為遷徙概率。圖1的一個(gè)趨化步驟內(nèi)，每個(gè)細(xì)菌按照如下步驟進(jìn)行：

（1）翻轉(zhuǎn)。產(chǎn)生隨機(jī)方向向量Δ(i)，進(jìn)行方向調(diào)整，按式（8）、（9）更新細(xì)菌的位置，重新計(jì)算適應(yīng)度值。

Pi(j,k,l)代表第i個(gè)細(xì)菌個(gè)體的當(dāng)前位置，其中，j表示第 j次趨向行為，k代表第k次復(fù)制行為，l代表第l次遷徙行為，C(i)為細(xì)菌i的趨化步長(zhǎng)，V(i,j)為細(xì)菌i翻轉(zhuǎn)時(shí)的單位隨機(jī)方向向量。

（2）游動(dòng)。如果細(xì)菌翻轉(zhuǎn)后適應(yīng)值得到改善，則沿當(dāng)前方向繼續(xù)游動(dòng)，直至適應(yīng)度值不再改善或在該方向達(dá)到預(yù)定的最大游動(dòng)步數(shù)。

復(fù)制操作是對(duì)所有細(xì)菌個(gè)體按照適應(yīng)度值降序排序，將排在后面的一半個(gè)體刪除，剩下的個(gè)體進(jìn)行再生。遷徙操作是對(duì)每個(gè)細(xì)菌以Ped概率隨機(jī)生成一個(gè)新個(gè)體并替換原個(gè)體，增強(qiáng)細(xì)菌的全局搜索能力。

算法1 BFO（其流程圖見(jiàn)圖1）。

圖1 BFO流程圖

3.2 自適應(yīng)趨化策略

BFO算法中，趨化操作對(duì)算法來(lái)說(shuō)至關(guān)重要。選擇較大的步長(zhǎng)值，有助于個(gè)體快速向著最優(yōu)位置移動(dòng)，收斂速度快，但易跳過(guò)最優(yōu)值；選擇較小的步長(zhǎng)值，細(xì)菌個(gè)體向最優(yōu)位置移動(dòng)的速度過(guò)慢，算法效率較低?；诖?，本文將BFO的趨化操作加以改進(jìn)，使改進(jìn)BFO隨著迭代次數(shù)的增加，細(xì)菌個(gè)體選取其中的某一部分維度進(jìn)行趨化操作，且其趨化范圍隨著迭代次數(shù)的增加而減小，以提高算法的收斂速度和適應(yīng)度精度。

（1）自適應(yīng)趨化策略1

針對(duì)D{0-1}KP的第一數(shù)學(xué)模型，假定當(dāng)前細(xì)菌個(gè)體編碼為（0，0，1，0，1，0，1，0，0，0，0，1，0，1，0），如圖2所示，在當(dāng)前個(gè)體上隨機(jī)選取兩個(gè)點(diǎn) p和q，p、q之間的區(qū)域作為趨化范圍，兩側(cè)的兩個(gè)區(qū)域?yàn)榉€(wěn)定區(qū)域。選擇 p、q時(shí)使| |

p-q的值隨著迭代次數(shù)的增加而減小，利于迭代初期在全局范圍內(nèi)搜索最優(yōu)解，迭代后期在局部范圍內(nèi)搜索最優(yōu)解。新的游動(dòng)為p、q范圍內(nèi)的編碼在后續(xù)操作中逆序存放，穩(wěn)定區(qū)域的編碼在后續(xù)操作中不變。經(jīng)過(guò)上述變換之后，個(gè)體相當(dāng)于向前游動(dòng)了一步，對(duì)新個(gè)體的適應(yīng)度進(jìn)行評(píng)估，如果新個(gè)體適應(yīng)度值更優(yōu)，則新個(gè)體取代舊個(gè)體，并繼續(xù)下一次操作。

圖2 第一種趨化操作

（2）自適應(yīng)趨化策略2

針對(duì)D{0-1}KP的第二數(shù)學(xué)模型，假定當(dāng)前編碼為（0，2，3，3，1，0，2，3，3），如圖3所示，隨機(jī)選取兩個(gè)點(diǎn) p和 q，且的值隨著迭代次數(shù)的增加而減小。新的游動(dòng)操作為趨化范圍內(nèi)的編碼在后續(xù)操作中隨機(jī)取值，穩(wěn)定區(qū)域的編碼在后續(xù)操作中不發(fā)生改變，其他同上。

圖3 第二種趨化操作

將自適應(yīng)趨化策略引入BFO算法中，得到自適應(yīng)BFO（Adapative BFO，ABFO）算法。

3.3 求解D{0-1}KP的FirABFO

算法2 FirABFO

1.初始化參數(shù)S,Nc,Ns,Nre,Ned,Ped

2. H[i]←Quicksort(pi/wi)(0≤i≤3n-1)

3.生成初始種群P(Xi)(1≤i≤S)并轉(zhuǎn)化為二進(jìn)制種群B(Xi)，計(jì)算適應(yīng)度 f(B(Xi))

4.forl=1toNed

5. fork=1toNre

6. forj=1toNc

7. fori=1toS

8. 對(duì)Xi執(zhí)行自適應(yīng)趨化操作1并用GROA優(yōu)化

9. endfor

10. endfor

11. 復(fù)制

12.endfor

13.個(gè)體遷徙并利用GROA優(yōu)化

14.endfor

15.返回最優(yōu)個(gè)體及其適應(yīng)度

在第2步中，Quicksort為快排序，時(shí)間復(fù)雜度O(nlbn)，第3步生成初始種群并優(yōu)化，時(shí)間復(fù)雜度為O(S×n)，第5步至第14步的時(shí)間復(fù)雜度為O(S×Nc×Nre×Ned×Ns×n)，故FirABFO的時(shí)間復(fù)雜度為多項(xiàng)式時(shí)間。

3.4 求解D{0-1}KP的SecABFO

針對(duì)D{0-1}KP的第二數(shù)學(xué)模型，隨機(jī)產(chǎn)生值在[0，4）之間的實(shí)型細(xì)菌個(gè)體，整數(shù)編碼中的 xi由對(duì)應(yīng)的映射得來(lái)。參照文獻(xiàn)[3]中新的貪心修復(fù)和優(yōu)化算法（NROA）對(duì)X進(jìn)行處理，將所有的潛在解修正為可行解。故利用ABFO和NROA對(duì)D{0-1}KP的第二數(shù)學(xué)模型求解，得到SecABFO算法。

算法3 SecABFO

1.初始化參數(shù)S,Nc,Ns,Nre,Ned,Ped

2. H[i]←Quicksort(pi/wi)(0≤i≤3n-1)

3. 生成初始種群P(Xi)(1≤i≤S)轉(zhuǎn)為整數(shù)種群B(Xi)并優(yōu)化

4.forl=1toNed

5. fork=1toNre

6. forj=1toNc

7. fori=1toS

8. 對(duì)Xi執(zhí)行自適應(yīng)趨化操作2后利用NROA處理

9. endfor

10. endfor

11. 復(fù)制

12. endfor

13. 個(gè)體遷徙后利用NROA修復(fù)與優(yōu)化

14.endfor

15.返回最優(yōu)個(gè)體及其適應(yīng)度

第3步生成初始種群并用貪心策略進(jìn)行優(yōu)化，時(shí)間復(fù)雜度為O(S×n)，第5步至第14步的時(shí)間復(fù)雜度為O(S×Nc×Nre×Ned×Ns×n)，故SecABFO的時(shí)間復(fù)雜度為多項(xiàng)式時(shí)間。

4 仿真實(shí)驗(yàn)與分析

本文仿真實(shí)驗(yàn)的四類(lèi)D{0-1}KP實(shí)例分別為：不相關(guān)D{0-1}KP實(shí)例（Uncorrelated instances of D{0-1}KP，UDKP）、弱相關(guān)D{0-1}KP實(shí)例（Weakly correlated instances of D{0-1}KP，WDKP）、強(qiáng)相關(guān)D{0-1}KP實(shí)例（Strongly correlated instances of D{0-1}KP，SDKP）和逆向強(qiáng)相關(guān)D{0-1}KP實(shí)例（Inversestrongly correlated instances of D{0-1}KP，IDKP），每一類(lèi)實(shí)例中含規(guī)模大小為300、600、900、1 200、1 500、1 800、2 100、2 400、2 700、3 000的10個(gè)實(shí)例，實(shí)例生成參照http：//pan.baidu.com/s/1o6MJVEq。

利用FirABFO和SecABFO求解四類(lèi)D{0-1}KP實(shí)例時(shí)，參數(shù)設(shè)置如下：S為30，迭代次數(shù)Miter為40，Nc為20，Ns為4，Nre為4，Ned 為2，Ped 為0.25。每個(gè)算法分別獨(dú)立運(yùn)行100次，結(jié)果見(jiàn)表1～表4。其中，Opt為動(dòng)態(tài)規(guī)劃法（DPDKP）[2]計(jì)算出的實(shí)例最優(yōu)值；Best、Worst和Mean分別為100次計(jì)算得到最好值、最差值及數(shù)學(xué)期望，F(xiàn)irEGA算法的數(shù)據(jù)來(lái)自文獻(xiàn)[3]，文獻(xiàn)[12]中選取每類(lèi)實(shí)例的最優(yōu)算法FirBFO或SecBFO，MMBO算法的數(shù)據(jù)來(lái)自文獻(xiàn)[14]，F(xiàn)DDE算法的數(shù)據(jù)來(lái)自文獻(xiàn)[16]。

表1為各算法求解UDKP類(lèi)實(shí)例的結(jié)果，圖4為6種算法的近似比比較圖。由圖4（a）可以看出，SecABFO的最優(yōu)近似比值最小，接近1，是6種算法中最好的；FirABFO在求解UDKP1-UDKP5時(shí)與FDDE算法不相上下，在求解UDKP6-UDKP10時(shí)近似比值逐漸增大，與其他算法相比，優(yōu)勢(shì)逐漸減弱。圖4（b）、圖4（c）與圖4（a）區(qū)別不大。總的來(lái)說(shuō)，SecABFO對(duì)UDKP類(lèi)實(shí)例的求解性能在6種算法中是最好的，F(xiàn)irABFO的求解性能在大部分實(shí)例上優(yōu)于FirEGA、SecBFO、MMBO，與FDDE算法相比，兩種算法各有優(yōu)劣。

表1 求解UDKP實(shí)例的結(jié)果

表2 求解WDKP實(shí)例的結(jié)果

圖5為6種算法求解WDKP類(lèi)實(shí)例時(shí)的近似比比較圖。由圖5（a）可以看出，SecABFO的最優(yōu)近似比值最小，且接近1，是6種算法中最好的；FirABFO在求解WDKP1-WDKP8時(shí)僅次于SecABFO，在求解WDKP9-WDKP10時(shí)比SecABFO和MMBO略差，且FirABFO的最優(yōu)近似比值小于1.002。由圖5（b）可以看出FirABFO和SecABFO的曲線變化不大，近似比值仍然最小，算法性能最好，但其他算法的曲線都有變化，值略有增大。由圖5（c）可以看出，各算法曲線浮動(dòng)較大，但FirABFO和SecABFO的值仍然最小。故求解WDKP類(lèi)實(shí)例時(shí)，F(xiàn)irABFO和SecABFO的求解性能最好，優(yōu)于其他4種算法。

圖6是6種算法求解SDKP類(lèi)實(shí)例的近似比比較圖。由圖6（a）可以看出，SecABFO的最優(yōu)近似比值最小，是6種算法中最好的；FirABFO在求解SDKP1-SDKP7時(shí)僅次于SecABFO，在求解SDKP8-SDKP10時(shí)優(yōu)于FirEGA和FirBFO，劣于SecABFO和FDDE，與MMBO不相上下。由圖6（b）和圖6（c）可以看出6種算法的平均近似比值和最差近似比值比圖6（a）都略有增大，曲線稍有浮動(dòng)，但FirABFO和SecABFO算法性能最好。故FirABFO和SecABFO是求解SDKP類(lèi)實(shí)例的最優(yōu)算法。

圖4 6種算法求解UDKP實(shí)例的近似比比較圖

圖5 6種算法求解WDKP實(shí)例的近似比比較圖

圖6 6種算法求解SDKP實(shí)例的近似比比較圖

圖7 5種算法求解IDKP實(shí)例的近似比比較圖

圖8 FirABFO和SecABFO在四類(lèi)實(shí)例上的最優(yōu)近似比

由于文獻(xiàn)[14]中未提供MMBO求解IDKP類(lèi)實(shí)例的結(jié)果，故圖7為5種算法的近似比值比較圖。由圖7可以看出，除FirEGA和FDDE外，其余3種算法近似比值相對(duì)比較集中，F(xiàn)irBFO、FirABFO和SecABFO近似比值非常接近1，這3條曲線基本重合。故FirBFO、FirABFO和SecABFO的求解性能在5種算法中最好。

圖9 FirABFO和SecABFO的平均收斂曲線比較

圖8 更直觀地顯示出FirABFO和SecABFO在4組實(shí)例上的求解性能。由圖8（a）～（c）可以看出，SecABFO的近似比值小于FirABFO，故在求解UDKP、WDKP和SDKP類(lèi)實(shí)例時(shí)SecABFO求解性能優(yōu)于FirABFO；圖8（d）的縱坐標(biāo)取值最小，兩種算法的最優(yōu)近似比的最大值遠(yuǎn)遠(yuǎn)小于1.000 1，基本等于1，即兩種算法在IDKP類(lèi)實(shí)例上的求解性能都很好，且僅在IDKP7、IDKP8和IDKP10上FirABFO優(yōu)于SecABFO?？偟膩?lái)說(shuō)，F(xiàn)irABFO和SecABFO在4組實(shí)例上的求解性能IDKP最優(yōu)，WDKP次之，SDKP第三，UDKP最差，但是最差的近似比值也在1.066以下。由圖8還可以看出 SecABFO在對(duì)4類(lèi)D{0-1}KP實(shí)例求解時(shí)，近似比值更小，更接近1，因此更適合求解D{0-1}KP。

結(jié)論：對(duì)于規(guī)模大且項(xiàng)的價(jià)值系數(shù)和重量系數(shù)均在大范圍內(nèi)隨機(jī)取值的4類(lèi)D{0-1}KP實(shí)例，F(xiàn)irABFO和SecABFO均能夠快速求得一個(gè)近似比接近于1的近似解，因此它們都是適于求解大規(guī)模難D{0-1}KP的有效且實(shí)用的進(jìn)化算法。從算法求得的最好結(jié)果和算法的平均求解性能來(lái)看，SecABFO的求解效果明顯優(yōu)于FirABFO。

5 結(jié)束語(yǔ)

本文研究如何利用改進(jìn)的自適應(yīng)趨化策略的細(xì)菌覓食算法求解D{0-1}KP問(wèn)題。針對(duì)細(xì)菌個(gè)體的兩種編碼方法，給出了求解D{0-1}KP的FirABFO和SecABFO算法。通過(guò)對(duì)4類(lèi)大規(guī)模D{0-1}KP實(shí)例的計(jì)算結(jié)果分析表明：FirABFO和SecABFO的求解性能非常好，均不受實(shí)例中各項(xiàng)的價(jià)值系數(shù)、重量系數(shù)和背包載重的大小影響，能夠快速求得一個(gè)近似比接近于1的近似解，因此均為求解D{0-1}KP實(shí)例的實(shí)用進(jìn)化算法。