自適應細菌覓食算法求解折扣{0-1}背包問題

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

1.河北地質大學 信息工程學院，石家莊 050031

2.中國郵政集團公司 河北省郵政信息技術局，石家莊 050011

1 引言

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

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

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

D{0-1}KP的第二數學模型[3]描述如下：

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

2 相關研究工作

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

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

3 自適應細菌覓食算法求解D{0-1}KP

3.1 細菌覓食算法

BFO算法是一種新型仿生優化算法，其求解優化問題的一般過程為：產生初始解種群，計算適應度函數值，群體間通過趨化、復制、遷徙進行迭代優化，直至產生最終解。算法如圖1所示，其中，S為種群大小，Ned為遷徙次數，Nre為復制次數，Nc為趨化次數，Ns為游動次數，Ped為遷徙概率。圖1的一個趨化步驟內，每個細菌按照如下步驟進行：

（1）翻轉。產生隨機方向向量Δ(i)，進行方向調整，按式（8）、（9）更新細菌的位置，重新計算適應度值。

Pi(j,k,l)代表第i個細菌個體的當前位置，其中，j表示第 j次趨向行為，k代表第k次復制行為，l代表第l次遷徙行為，C(i)為細菌i的趨化步長，V(i,j)為細菌i翻轉時的單位隨機方向向量。

（2）游動。如果細菌翻轉后適應值得到改善，則沿當前方向繼續游動，直至適應度值不再改善或在該方向達到預定的最大游動步數。

復制操作是對所有細菌個體按照適應度值降序排序，將排在后面的一半個體刪除，剩下的個體進行再生。遷徙操作是對每個細菌以Ped概率隨機生成一個新個體并替換原個體，增強細菌的全局搜索能力。

算法1 BFO（其流程圖見圖1）。

圖1 BFO流程圖

3.2 自適應趨化策略

BFO算法中，趨化操作對算法來說至關重要。選擇較大的步長值，有助于個體快速向著最優位置移動，收斂速度快，但易跳過最優值；選擇較小的步長值，細菌個體向最優位置移動的速度過慢，算法效率較低。基于此，本文將BFO的趨化操作加以改進，使改進BFO隨著迭代次數的增加，細菌個體選取其中的某一部分維度進行趨化操作，且其趨化范圍隨著迭代次數的增加而減小，以提高算法的收斂速度和適應度精度。

（1）自適應趨化策略1

針對D{0-1}KP的第一數學模型，假定當前細菌個體編碼為（0，0，1，0，1，0，1，0，0，0，0，1，0，1，0），如圖2所示，在當前個體上隨機選取兩個點 p和q，p、q之間的區域作為趨化范圍，兩側的兩個區域為穩定區域。選擇 p、q時使| |

p-q的值隨著迭代次數的增加而減小，利于迭代初期在全局范圍內搜索最優解，迭代后期在局部范圍內搜索最優解。新的游動為p、q范圍內的編碼在后續操作中逆序存放，穩定區域的編碼在后續操作中不變。經過上述變換之后，個體相當于向前游動了一步，對新個體的適應度進行評估，如果新個體適應度值更優，則新個體取代舊個體，并繼續下一次操作。

圖2 第一種趨化操作

（2）自適應趨化策略2

針對D{0-1}KP的第二數學模型，假定當前編碼為（0，2，3，3，1，0，2，3，3），如圖3所示，隨機選取兩個點 p和 q，且的值隨著迭代次數的增加而減小。新的游動操作為趨化范圍內的編碼在后續操作中隨機取值，穩定區域的編碼在后續操作中不發生改變，其他同上。

圖3 第二種趨化操作

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

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

算法2 FirABFO

1.初始化參數S,Nc,Ns,Nre,Ned,Ped

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

3.生成初始種群P(Xi)(1≤i≤S)并轉化為二進制種群B(Xi)，計算適應度 f(B(Xi))

4.forl=1toNed

5. fork=1toNre

6. forj=1toNc

7. fori=1toS

8. 對Xi執行自適應趨化操作1并用GROA優化

9. endfor

10. endfor

11. 復制

12.endfor

13.個體遷徙并利用GROA優化

14.endfor

15.返回最優個體及其適應度

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

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

針對D{0-1}KP的第二數學模型，隨機產生值在[0，4）之間的實型細菌個體，整數編碼中的 xi由對應的映射得來。參照文獻[3]中新的貪心修復和優化算法（NROA）對X進行處理，將所有的潛在解修正為可行解。故利用ABFO和NROA對D{0-1}KP的第二數學模型求解，得到SecABFO算法。

算法3 SecABFO

1.初始化參數S,Nc,Ns,Nre,Ned,Ped

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

3. 生成初始種群P(Xi)(1≤i≤S)轉為整數種群B(Xi)并優化

4.forl=1toNed

5. fork=1toNre

6. forj=1toNc

7. fori=1toS

8. 對Xi執行自適應趨化操作2后利用NROA處理

9. endfor

10. endfor

11. 復制

12. endfor

13. 個體遷徙后利用NROA修復與優化

14.endfor

15.返回最優個體及其適應度

第3步生成初始種群并用貪心策略進行優化，時間復雜度為O(S×n)，第5步至第14步的時間復雜度為O(S×Nc×Nre×Ned×Ns×n)，故SecABFO的時間復雜度為多項式時間。

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實例（Inversestrongly correlated instances of D{0-1}KP，IDKP），每一類實例中含規模大小為300、600、900、1 200、1 500、1 800、2 100、2 400、2 700、3 000的10個實例，實例生成參照http：//pan.baidu.com/s/1o6MJVEq。

利用FirABFO和SecABFO求解四類D{0-1}KP實例時，參數設置如下：S為30，迭代次數Miter為40，Nc為20，Ns為4，Nre為4，Ned 為2，Ped 為0.25。每個算法分別獨立運行100次，結果見表1～表4。其中，Opt為動態規劃法（DPDKP）[2]計算出的實例最優值；Best、Worst和Mean分別為100次計算得到最好值、最差值及數學期望，FirEGA算法的數據來自文獻[3]，文獻[12]中選取每類實例的最優算法FirBFO或SecBFO，MMBO算法的數據來自文獻[14]，FDDE算法的數據來自文獻[16]。

表1為各算法求解UDKP類實例的結果，圖4為6種算法的近似比比較圖。由圖4（a）可以看出，SecABFO的最優近似比值最小，接近1，是6種算法中最好的；FirABFO在求解UDKP1-UDKP5時與FDDE算法不相上下，在求解UDKP6-UDKP10時近似比值逐漸增大，與其他算法相比，優勢逐漸減弱。圖4（b）、圖4（c）與圖4（a）區別不大。總的來說，SecABFO對UDKP類實例的求解性能在6種算法中是最好的，FirABFO的求解性能在大部分實例上優于FirEGA、SecBFO、MMBO，與FDDE算法相比，兩種算法各有優劣。

表1 求解UDKP實例的結果

表2 求解WDKP實例的結果

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

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

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

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

圖6 6種算法求解SDKP實例的近似比比較圖

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

圖8 FirABFO和SecABFO在四類實例上的最優近似比

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

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

圖8 更直觀地顯示出FirABFO和SecABFO在4組實例上的求解性能。由圖8（a）～（c）可以看出，SecABFO的近似比值小于FirABFO，故在求解UDKP、WDKP和SDKP類實例時SecABFO求解性能優于FirABFO；圖8（d）的縱坐標取值最小，兩種算法的最優近似比的最大值遠遠小于1.000 1，基本等于1，即兩種算法在IDKP類實例上的求解性能都很好，且僅在IDKP7、IDKP8和IDKP10上FirABFO優于SecABFO。總的來說，FirABFO和SecABFO在4組實例上的求解性能IDKP最優，WDKP次之，SDKP第三，UDKP最差，但是最差的近似比值也在1.066以下。由圖8還可以看出 SecABFO在對4類D{0-1}KP實例求解時，近似比值更小，更接近1，因此更適合求解D{0-1}KP。

結論：對于規模大且項的價值系數和重量系數均在大范圍內隨機取值的4類D{0-1}KP實例，FirABFO和SecABFO均能夠快速求得一個近似比接近于1的近似解，因此它們都是適于求解大規模難D{0-1}KP的有效且實用的進化算法。從算法求得的最好結果和算法的平均求解性能來看，SecABFO的求解效果明顯優于FirABFO。

5 結束語

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