求解0-1背包問題的改進二進制捕魚算法

陳建榮

(右江民族醫學院 公共衛生與管理學院,廣西 百色 533000)

0 引 言

背包問題(Knapsack Problem,KP)[1-3]是經典的NP難問題,其目標是尋找在給定背包容量的限制條件下價值量最大的物品選擇方案。當涉及資源或任務分配等工作時,可使用背包問題的相關理論去處理和解決,如投資決策等。背包問題有多個變體,最基本的是0-1背包問題,其它類型問題能轉換成該問題而順利求解[3]。

求解0-1背包問題的方法包括精確算法和啟發式算法這兩類[2-3]。其中,精確算法包括貪心算法、動態規劃法、分支定界法、窮舉法、回溯法等。這些算法普遍存在計算效率低、計算量隨問題維數的增加而呈指數級增長等缺點,因而難以有效處理高維背包問題。另一類算法是啟發式算法,其本質上屬于近似搜索算法,能在合理時間內找到問題的最優解或者滿意解。常見的有遺傳算法[2]、模擬退火算法[4]、粒子群算法[5]、蟻群算法[6]、布谷鳥算法[7]、蝙蝠算法[8]等。但這些算法在求解0-1背包問題時,仍存在全局搜索能力不強、收斂速度慢等不足。

陳建榮等人[9]通過觀察漁夫在江面上捕魚的行為習慣而提出了捕魚算法(Fishing Algorithm)。目前,該算法及其改進或結合算法已被應用于解決各類優化問題,并獲得良好的效果[10-13]。

捕魚算法是針對連續問題提出的,無法直接應用于求解0-1背包問題,所以該文首先對漁夫編碼及搜索方法進行重新定義和描述,稱之為二進制捕魚算法(Binary Fishing Algorithm,BFA)。然后,在對其分析的基礎上,提出改進二進制捕魚算法(Improved Binary Fishing Algorithm,IBFA)。最后,使用不同維度的背包問題對算法進行性能測試。

1 捕魚算法

捕魚算法對漁夫捕魚行為的模擬主要包括7個假設和3類搜索方法[12]。7個假設分別是:(1)水中魚的分布保持不變;(2)漁夫不知道魚在水里的分布情況;(3)漁夫總是向魚多的方向前進;(4)漁夫傾向于停留在魚密度大的位置捕魚;(5)漁夫希望通過使用網眼更小的漁網將魚打盡;(6)漁夫會離開沒有魚的位置前往其它地方捕魚;(7)漁夫之間避免碰撞。3類搜索方法包括移動搜索、收縮搜索和隨機搜索。

算法運行過程中,漁夫在給定的尋優區域(問題的定義域)內撒網捕魚,并通過漁夫之間的通力合作最終找到水中魚密度最高的位置(問題的最優解)。

2 問題描述及二進制捕魚算法

2.1 問題描述

0-1背包問題可描述為:給定一個最大容量為C的背包和n個物品,第k個物品的價值和體積分別為pk和wk。在不超過背包最大容量的條件下,將物品盡可能地裝進背包,使得背包中物品的總價值達到最大。

若假定xi的取值0和1分別表示第k個物品沒有裝入背包和裝入背包兩種狀態,則該問題用數學模型可表示為:

其中,xk∈{0,1}。

引入罰函數法,可將上述問題轉化為:

(1)

2.2 漁夫編碼及相關定義

對于n維的0-1背包問題,第i個漁夫的位置向量表示為Xi=(xi1,…,xik,…,xin)。其中,xik是Xi的第k個分量,取值為0或1。該漁夫對應位置的目標函數值可通過(1)式求得。

定義1:設兩個位置向量分別為Xi1和Xi2,則它們之間的距離定義為D=sum(|Xi1-Xi2|)。其中,|·|表示對向量中的每一個分量取絕對值,sum(·)表示將向量的所有分量相加。

例1:給定位置X1=(1,0,1,0)和X2=(0,1,1,0),那么兩位置間的距離D=|1-0|+|0-1|+|1-1|+|0-0|=2。

由定義可知,當漁夫撒網時,其所在位置和撒網點之間的距離剛好等于撒網半徑。

2.3 搜索方法

(2)

下面給出三類搜索方法的具體描述。

(1)移動搜索。

(2)收縮搜索。

(3)隨機搜索。

若漁夫i不滿足前兩類搜索的執行條件,且連續執行收縮搜索的次數達到算法給定的閾值,則對該漁夫進行隨機初始化,并按式(2)構造撒網點集。

2.4 算法流程

算法設置有公告板,輸入參數為:漁夫個體數量N、撒網半徑L、撒網次數ξ、收縮系數β、收縮搜索閾值η和迭代次數T。

算法流程:

步驟1:對漁夫進行隨機初始化;

步驟2:算法迭代次數達到T(或找到已知最優解)則停機,并輸出最優值和最優解;

步驟3:各漁夫根據當前情況,選擇執行相應的搜索方法(移動搜索、收縮搜索和隨機搜索);

步驟4:找到更優值則更新公告板;轉Step 2。

3 改進二進制捕魚算法

3.1 分析與說明

首先,在BFA算法中,使用隨機函數生成并給漁夫個體位置賦初值,由于受到隨機性的影響可能會使得算法收斂速度偏慢。其次,漁夫的撒網半徑對算法收斂速度影響較大,而所求解問題的維數不盡相同,若撒網半徑設置為固定值,則會出現對于不同問題需要頻繁設置不同半徑值的尷尬局面。最后,為提高漁夫之間的信息共享,避免陷入局部最優,增加了一種名為靠近搜索的搜索方法。

3.2 貪心輪盤賭

3.3 自適應半徑

通過下式給出初始半徑值:

R=εn

(3)

其中,ε∈(0,1]為給定的自適應半徑系數;n是所求問題的維數,即0-1背包問題中物品的總數。

3.4 隨機比例

為避免因出現早熟而陷入局部最優,算法設置有隨機比例參數Υ用于控制采用隨機函數進行初始化漁夫位置的比例,其取值范圍是[0,1]。當Υ=0時,全部采用隨機函數進行初始化;當Υ=1時,則全部使用貪心輪盤賭的方法對漁夫位置進行初始化。

3.5 靠近搜索

定義3:設漁夫位置和目標位置分別為Xi和XG,且Xi與XG之間的距離D>R。從|Xi-XG|中隨機選出R個非零分量,并將Xi中位于該非零分量位置的R個分量值用其二進制反碼替換,則稱漁夫Xi以步長R向位置XG隨機靠近一次。

靠近搜索可描述為:若漁夫i連續執行收縮搜索的次數達到算法給定的閾值η,且其當前所處的位置并非群體最優,則該漁夫以步長?R×rand」向群體最優位置靠近(?·」表示向上取整);漁夫每向群體最優位置隨機靠近一次,都重新按式(2)構造撒網點集。

3.6 算法流程

與BFA算法相比,IBFA算法取消了撒網半徑L,新增自適應半徑系數ε和隨機比例參數Υ,其它參數保持不變。IBFA算法使用自適應半徑和隨機比例對漁夫進行初始化,并在搜索方法中增加了靠近搜索,其余操作和流程均與原算法相同。

4 實驗與對比

4.1 軟硬件環境與說明

實驗電腦是華為MateBook X Pro超極本,配置為:Intel Core i7-1165G7 CPU @2.8 GHz,16 GB LPDDR4X內存;64位Windows 11家庭版操作系統,MATLAB版本是2020a。

實驗分為常用算例測試和高維算例測試兩部分。除另有說明外,各算法均使用固定的參數,并且連續運行一定次數,以降低隨機性對結果的影響,同時也能在一定程度上反映不同算法在穩定性方面的差異。

4.2 常用算例測試與結果對比

常用算例測試中的九個經典算例均來自參考文獻[3],各算法運行參數見表1。測試時,所有算法都連續運行30次,并記錄包括最優值、最差值、平均值、標準差等指標在內的數據以便后續對比。七種不同算法的測試結果見表2。其中,對比算法的運行結果均來自文獻[3]。

BFA與IBFA算法測試結果對比:從表2中的數據可以看出,IBFA算法能找到全部九個背包問題的最優解,且標準差均為零,說明算法適應性強、穩定性好;而BFA算法只能找到前三個問題的最優解,這說明對于維數相對較高的問題(KP4-KP9)來說,IBFA算法的性能有較明顯的改善。

IBFA算法與其它算法測試結果對比:從最差值指標可知,對比算法中的ACPSO、BBA和HBA算法,在最差的情況下,未能找到全部九個背包問題(KP1-KP9)的最優解。對于IBFA、DPSPO和BLSO這三個能找到九個問題最優解的算法來說,它們的測試結果數據各有優勢。值得注意的是,從100維的五個問題(KP5-KP9)的測試結果來看,除KP6外,IBFA在最小迭代次數指標上是最優的,均優于其它對比算法;特別是對于KP5和KP7這兩個問題,在連續的30次運行中,IBFA算法在每一次初始化時都能找到問題的最優解,其對比指標均優于其它算法,這說明本文的改進方法在獲得優秀初始值方面有較好的效果。注意到,IBFA算法的種群數量只有20,而其它對比算法均為50,這表明該算法的全局搜索能力較強,即使在種群數量較少的情況下,也不容易陷入局部極值點。此外,IBFA在求解背包問題時的運行耗時非常短,只需要不足0.04秒的時間就能找到問題的最優解。

表1 各算法運行參數設置

表2 七種不同算法的測試結果對比

續表2

4.3 高維算例測試與結果對比

為進一步驗證算法性能,本節進行了高維算例的測試,這些算例使用下面的公式隨機產生[7]:

其中,wi、pi和C分別表示算例中的物品體積、價值和背包容量;randint[1,10]表示隨機地從集合{1,2,…,10}中抽取一個整數。根據上述公式,隨機產生維數為100、200、400、600、800和1 000的六個高維0-1背包問題,每個算例產生后就保持不變。測試時,算法均連續運行50次,最大迭代次數均設置為500代。BBA算法參數取表1中的對應值;BFA和IBFA算法除η=20和θ=70外,其余參數均與表1保持一致。測試結果見表3。

表3 高維算例測試結果

從表3中的數據可以看到,對于這六個高維背包問題而言,IBFA算法能找到的解是最優的,且其標準差均為零,說明該算法性能穩定,魯棒性強,不易陷入局部極值。

從各項對比指標上看,BBA和BFA算法性能基本相當,且這兩種算法均因陷入局部極值而未能找到全局最優解。此外,隨著問題維數的提高,各對比算法的運行耗時都相應地增加了:BBA算法耗時增加最快,其次是IBFA,最后是BFA。從最小迭代次數、最大迭代次數和平均迭代次數上看,問題維數的變化(提高)對IBFA算法收斂速度的影響不大,對于這六個高維問題,該算法最多只需要23次迭代就能找到最優解。

圖1至圖6展示的是BBA、BFA和IBFA算法連續運行50次的平均進化曲線。從圖中可以看出,IBFA算法的收斂速度很快,僅需要20次左右的迭代就能收斂到最優值,而BBA和BFA算法經歷500次迭代后仍未能收斂到穩定值。

圖1 KP01(100維)問題平均進化曲線

圖2 KP02(200維)問題平均進化曲線

圖3 KP03(400維)問題平均進化曲線

圖4 KP04(600維)問題平均進化曲線

圖5 KP05(800維)問題平均進化曲線

圖6 KP06(1 000維)問題平均進化曲線

5 結束語

為求解0-1背包問題,首先對捕魚算法進行修改,即引入二進制編碼而提出二進制捕魚算法。并在此基礎上,對其進行優化和改進,提出了改進二進制捕魚算法。數值實驗結果表明,與其它群智能算法相比,改進二進制捕魚算法具有收斂速度快、全局搜索能力強、求解結果穩定、魯棒性好等優點。特別是對于高維背包問題,與經典二進制蝙蝠算法相比,改進二進制捕魚算法的綜合性能明顯占優。在未來的研究中,擬將該算法應用于車間調度等問題,以進一步測試其性能。