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

陳建榮

(右江民族醫(yī)學(xué)院 公共衛(wèi)生與管理學(xué)院,廣西 百色 533000)

0 引 言

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

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

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

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

1 捕魚算法

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

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

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

2.1 問題描述

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

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

其中,xk∈{0,1}。

引入罰函數(shù)法,可將上述問題轉(zhuǎn)化為:

(1)

2.2 漁夫編碼及相關(guān)定義

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

定義1:設(shè)兩個位置向量分別為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。

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

2.3 搜索方法

(2)

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

(1)移動搜索。

(2)收縮搜索。

(3)隨機搜索。

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

2.4 算法流程

算法設(shè)置有公告板,輸入?yún)?shù)為:漁夫個體數(shù)量N、撒網(wǎng)半徑L、撒網(wǎng)次數(shù)ξ、收縮系數(shù)β、收縮搜索閾值η和迭代次數(shù)T。

算法流程:

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

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

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

步驟4:找到更優(yōu)值則更新公告板;轉(zhuǎn)Step 2。

3 改進二進制捕魚算法

3.1 分析與說明

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

3.2 貪心輪盤賭

3.3 自適應(yīng)半徑

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

R=εn

(3)

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

3.4 隨機比例

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

3.5 靠近搜索

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

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

3.6 算法流程

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

4 實驗與對比

4.1 軟硬件環(huán)境與說明

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

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

4.2 常用算例測試與結(jié)果對比

常用算例測試中的九個經(jīng)典算例均來自參考文獻[3],各算法運行參數(shù)見表1。測試時,所有算法都連續(xù)運行30次,并記錄包括最優(yōu)值、最差值、平均值、標(biāo)準(zhǔn)差等指標(biāo)在內(nèi)的數(shù)據(jù)以便后續(xù)對比。七種不同算法的測試結(jié)果見表2。其中,對比算法的運行結(jié)果均來自文獻[3]。

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

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

表1 各算法運行參數(shù)設(shè)置

表2 七種不同算法的測試結(jié)果對比

續(xù)表2

4.3 高維算例測試與結(jié)果對比

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

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

表3 高維算例測試結(jié)果

從表3中的數(shù)據(jù)可以看到,對于這六個高維背包問題而言,IBFA算法能找到的解是最優(yōu)的,且其標(biāo)準(zhǔn)差均為零,說明該算法性能穩(wěn)定,魯棒性強,不易陷入局部極值。

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

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

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

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

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

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

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

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

5 結(jié)束語

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