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

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

0 引言

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

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

1 多維背包問(wèn)題描述

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

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

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

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

2 貪心二進(jìn)制獅群算法求解多維背包問(wèn)題

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

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

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

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

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

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

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

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

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

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

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

2.3 貪心算法修正處理

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

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

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

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

2）實(shí)際總體積減去該項(xiàng)物品體積，置xij=0。

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

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

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

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

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

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

3 GBLSO算法

GBLSO算法步驟如下：

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

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

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

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

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

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

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

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

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

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

4.1 常用算例測(cè)試

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

表1 選用算例測(cè)試表Tab.1 Test tableof selected examples

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

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

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

4.3 仿真實(shí)驗(yàn)及結(jié)果分析

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

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

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

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

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

5 結(jié)語(yǔ)

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