貪心二進制獅群優(yōu)化算法求解多維背包問題

楊 艷，劉生建，周永權(quán)

（1.廣州大學(xué)華軟軟件學(xué)院，廣州510990； 2.廣西民族大學(xué)信息科學(xué)與工程學(xué)院，南寧530006）（?通信作者電子郵箱yangyan_08@yeah.net）

0 引言

多維背包問題（Multidimensional Knapsack Problem,MKP）是一類典型的組合優(yōu)化問題，有著廣泛的實際應(yīng)用價值，如項目決策與規(guī)劃、資源分配、資金預(yù)算、貨物裝載等，對其求解方法的研究無論是在理論上還是實踐中都具有一定的意義［1］。求解MKP主要有精確算法和啟發(fā)式算法兩大類：精確算法的時間復(fù)雜性都是呈指數(shù)增長的，主要用于求解規(guī)模相對較小的問題，對大規(guī)模問題依賴智能優(yōu)化算法解決，常見的算法有粒子群優(yōu)化算法、煙花算法、狼群算法、布谷鳥搜索算法、蟻群算法等［2-9］；進化算法多采用精英策略，在具有高進化效率的同時，存在易陷入局部最優(yōu)解的局限性。文獻［2-3］提出將連續(xù)的粒子群優(yōu)化算法通過轉(zhuǎn)換函數(shù)生成離散粒子群算法，并用于求解MKP，為求解離散問題提供了一種新方法。二進制反向煙花算法求解MKP具有良好的尋優(yōu)效果，尤其是在背包維度高、物品數(shù)量多的問題中具有良好的尋優(yōu)能力［6］；二進制狼群算法求解MKP時減小了陷入局部極值的概率［7］；二進制布谷鳥算法求解背包問題時提高了算法求解精度和收斂速度［8］；二進制蟻群算法求解背包問題時提高了算法的全局搜索能力［9］。本文受以上算法思想的啟發(fā)，通過改進獅群算法求解MKP。

受獅群協(xié)作捕獵的啟發(fā)，文獻［10］提出一種新的群智能優(yōu)化算法——獅群算法，并驗證其良好的計算魯棒性和全局搜索能力，但其主要用于連續(xù)函數(shù)優(yōu)化問題。本文在基本獅群算法的基礎(chǔ)上，引入二進制編碼，加入貪心算法增強局部搜索能力，提出一種基于貪心算法的二進制獅群算法并求解多維背包問題，通過經(jīng)典算例仿真對比實驗驗證了算法的有效性。

1 多維背包問題描述

多維背包問題（KMP）可以看作多個0-1背包問題，一個m維0-1背包問題可以描述如下：

已知n個價值為，2，…，n）的物品，m個容量大小為，2，…，m）的容器，第i個物品所占第j個容器的容積大小為wij。KMP要解決的就是如何選擇物品裝入這m個容器，使得裝入容器的物品總價值最大。問題的數(shù)學(xué)模型為：

其中：f(x1，x2，…，xn)為目標(biāo)函數(shù)；n為物品的編號；m為容器的編號；pi為第i個物品的價值；Cj為第j個容器的容積；wi j為第i個物品所占第j個容器的容積大?。粁i為0-1決策變量，當(dāng)物品i為選擇裝入時xi=1，否則xi=0。

通過引入懲罰系數(shù)將帶約束的離散化的多維背包問題轉(zhuǎn)化成無約束最優(yōu)化問題，轉(zhuǎn)化后的無約束優(yōu)化問題模型如下：其中懲罰系數(shù)μ是一個很大的常數(shù)，取值為1010，以保證可行解的最差值都要優(yōu)于不可行解的最優(yōu)值。

2 貪心二進制獅群算法求解多維背包問題

2.1 獅群位置數(shù)據(jù)的離散化

將獅群領(lǐng)地抽象為一個N×m的歐氏空間，N為人工獅的總數(shù)量，m為編碼長度；第i個人工獅在第t代的位置為為位置X i在第t代時第j維的分量值，且只能取0或1；人工獅感受到的獵物優(yōu)劣即為目標(biāo)函數(shù)值，通過式（2）求得。

基本的獅群算法主要適用于求解連續(xù)空間優(yōu)化問題，二進制獅群算法求解多維背包問題時需將獅子的位置設(shè)為1或0，而獅子個體進行位置更新后產(chǎn)生的位置分量xtij不一定是1或0，使得獅群算法無法對其進行求解。由于獅子下一個位置由位置改變量ΔX i決定，ΔX i=-，ΔX i反映了的各個分量取1的概率。為了使概率值在［0，1］區(qū)間，貪心二進制獅群優(yōu)化（Greedy Binary Lion Swarm Optimization,GBLSO）算法采用式（3）的轉(zhuǎn)換函數(shù)對ΔX i進行處理，然后采用式（4）對獅子位置分量置1或0操作［2，4］：

其中：t為當(dāng)前代數(shù)，rand()為［0，1］上均勻分布的隨機數(shù)。

2.2 獅群位置更新規(guī)則

2.2.1 獅王位置更新規(guī)則

獅王位置是當(dāng)前群體最優(yōu)位置，其下一個位置通過反置移動算子計算。反置移動算子Θ(X i，M，r)表示X i在集合M指定的位置上隨機抽出r個位置進行反置運算。獅王通過在可行位置中隨機找一個位置進行取反，從而實現(xiàn)位置的更新，位置更新如式（5）：

其中：t為當(dāng)前代數(shù)；gBest t是當(dāng)前獅群發(fā)現(xiàn)的最佳獵物的位置。

2.2.2 母獅位置更新規(guī)則

2.2.3 幼獅位置更新規(guī)則

幼獅向下一個位置移動的方向由一個隨機值rand（）決定：若rand（）＜0.5，幼獅在獅王附近移動進食，下一個位置由當(dāng)前位置和獅王位置共同決定；若0.5≤rand()＜0.8，幼獅跟隨母獅學(xué)習(xí)捕獵，移動的位置由當(dāng)前位置和所跟隨母獅的歷史最優(yōu)位置決定，而所跟隨母獅由幼獅編號與母獅數(shù)量求模的方法確定；否則幼獅將被逐出獅群，即幼獅向獅群當(dāng)前最優(yōu)位置的相反方向移動。幼獅位置更新如式（7）所示：

2.3 貪心算法修正處理

由于獅子的初始位置是隨機產(chǎn)生的，在解空間會產(chǎn)生一部分不滿足約束條件的無效解，若直接使用式（2）計算適應(yīng)度，其結(jié)果必然會小于零，從而造成大量的無效試探。為了縮短尋優(yōu)時間，可對任意一個潛在解使用貪心算法進行修正，使其轉(zhuǎn)換為一個可行解。使用貪心算法修正會增加算法的計算量，但能夠使搜索有一定的導(dǎo)向而不再盲目，反而能在總體上縮短處理時間。設(shè)第i個潛在解的位置為Xi=(xi1，xi2，…，xij，…，xim)（1≤i≤N，1≤j≤m），貪心算法修正潛在解的實現(xiàn)步驟如下：

步驟1 對任意一個容器j，用式（1）檢測輸入值Xi表示的物品體積是否超過Cj，若否，則直接轉(zhuǎn)入步驟3。

步驟2 循環(huán)處理（總體積＞Cj時）：

1）從袋中取出價值最小的物品xij；

2）實際總體積減去該項物品體積，置xij=0。

步驟3 循環(huán)處理（總體積＜Cj時）：

1）從候選物品中選擇價值最大的物品xij；

2）若該物品的體積加上袋內(nèi)物品總體積＞Cj則結(jié)束循環(huán)；

3）把該物品加入袋中，并更新總體積，置xij=1。

步驟4 返回修正后的X i。

步驟5 檢測下一個容器，直到m個容器中的物品全部檢測完成。

3 GBLSO算法

GBLSO算法步驟如下：

步驟1 初始化。設(shè)定獅群數(shù)目N，最大迭代次數(shù)T，維度空間m，母獅占獅群比例因子β，隨機產(chǎn)生獅子的初始位置X i，貪婪因子Qi。

步驟2 計算適應(yīng)度值。根據(jù)適應(yīng)度值排序獅王、母獅及幼獅的位置，適應(yīng)度最佳的位置設(shè)為群最優(yōu)位置，即獅王位置。

步驟3 判斷終止條件：若達(dá)到終止條件，則輸出問題最優(yōu)解，即獅王的位置；否則，轉(zhuǎn)步驟4。

步驟4 根據(jù)式（5）、（6）、（7）更新獅王、母獅及幼獅的位置。

步驟5 根據(jù)獅子的位置計算適應(yīng)度值，并對無效位置進行糾正處理。

步驟6 更新獅子自身歷史最優(yōu)位置及獅群歷史最優(yōu)位置。當(dāng)有獅子發(fā)現(xiàn)最優(yōu)解時，其他獅子調(diào)整自己的貪婪因子為自身因子和最佳因子的均值。

步驟7 每隔一定迭代次數(shù)（10次）重新排序獅王、母獅及幼獅的位置。

步驟8 計算適應(yīng)度值，并判斷算法是否達(dá)到終止條件，若達(dá)到則輸出問題最優(yōu)解，否則轉(zhuǎn)步驟4。

4 仿真實驗與分析

本文選取經(jīng)典的離散二進制粒子群優(yōu)化（Discrete binary Particle Swarm Optimization，DPSO）算法［11］和二進制蝙蝠算法（Binary Bat Algorithm，BBA）［12］，并按照本文中的修復(fù)機制進行改進，和本文算法進行比較。本文算法的實驗硬件環(huán)境為Intel Xeon E3-1230V2@3.30 GHz和16 GBDDR3內(nèi)存，操作系統(tǒng)為Win10，使用python3.7，NumPy進行實驗仿真。

4.1 常用算例測試

為了驗證二進制獅群群算法求解多維背包問題的有效性，本文選用參考文獻［11］中的5類10個算例，每個算例的背包維度和物品數(shù)量如表1所示。

表1 選用算例測試表Tab.1 Test tableof selected examples

4.2 算法參數(shù)設(shè)置

實驗中種群規(guī)模N=50，最大迭代次數(shù)T=200。各算法的特定參數(shù)設(shè)置如表2所示。

表2 算法參數(shù)設(shè)置表Tab.2 Settingsof parameters of different algorithms

4.3 仿真實驗及結(jié)果分析

對每個算例獨立運行20次，記錄20次實驗中獲優(yōu)次數(shù)、最優(yōu)解、最差解、平均解和尋優(yōu)成功迭代次數(shù)，如表3所示。

表3 三種算法性能比較Tab.3 Performancecomparison of threealgorithms

從表3的對比數(shù)據(jù)可以看出，本文算法在大多數(shù)算例上都要優(yōu)于BBA和DPSO。本文算法每次迭代都能獲得最優(yōu)解，且尋優(yōu)平均迭代數(shù)較參考文獻算法少；說明本文算法收斂速度快，效率高。

圖1是GBLSO、BBA和DPSO三種算法獨立運行20次實驗的平均尋優(yōu)曲線。限于篇幅，僅給出三種算法對不同維數(shù)的背包問題部分算例的平均尋優(yōu)曲線圖。從圖中可以看出，本文算法的平均尋優(yōu)收斂速度快，能更好地找到全局最優(yōu)解。

圖1 典型測試算例尋優(yōu)曲線Fig.1 Optimization curves of typical test examples

5 結(jié)語

本文在獅群算法的基礎(chǔ)上引入貪心算法的思想，利用二進制編碼，提出了一種基于貪心算法的二進制獅群算法，并用于求解多維背包問題。通過10個經(jīng)典多維背包算例的仿真對比實驗表明本文算法具有較好的求解穩(wěn)定性、收斂性和全局搜索能力，同時改進算法也為其他二進制的離散優(yōu)化問題提供了一種有效的方法。