利用改進的二進制狼群算法求解多維背包問題

吳虎勝, 張鳳鳴, 戰仁軍, 李　浩, 梁曉龍

(1. 武警工程大學裝備工程學院, 陜西 西安 710086;

2. 空軍工程大學裝備管理與安全工程學院, 陜西 西安 710051;

3. 空軍工程大學空管領航學院, 陜西 西安 710051)

?

利用改進的二進制狼群算法求解多維背包問題

吳虎勝1,2, 張鳳鳴2, 戰仁軍1, 李浩2, 梁曉龍3

(1. 武警工程大學裝備工程學院, 陜西 西安 710086;

2. 空軍工程大學裝備管理與安全工程學院, 陜西 西安 710051;

3. 空軍工程大學空管領航學院, 陜西 西安 710051)

摘要：狼群算法啟發于狼群群體生存智慧,已被用于復雜函數尋優和0-1普通背包問題求解。針對多維背包問題特點,設計了試探裝載式的修復機制有效修復和改進人工狼群中的不可行解,改進了傳統基于大懲罰參數的目標函數,減小了由于懲罰參數過大而導致算法陷入局部最優的風險;并受狼群的繁衍方式的啟發,在二進制狼群算法的基礎上提出了求解多維背包問題的改進二進制狼群算法(improve binary wolf pack algorithm, IBWPA)。通過求解19組不同規模的典型多維背包算例和與其他算法的對比分析,例證了算法的有效性和計算穩定性。

關鍵詞：進化計算; 群體智能; 二進制狼群算法; 組合優化; 多維背包問題

0引言

背包問題是經典的NP-hard問題,旨在尋求背包容積限制下具有最大價值的物品裝載方案。如金融產品組合投資、無人機任務分配、物料資源分配、貨運裝載等很多實際問題都可抽象為背包問題,應用非常廣泛[1]。背包問題有多種形式:如普通背包問題[2]、多維背包問題[3]、多選擇背包問題[4]、多選擇多維背包問題[5]、多目標背包問題[6]和二次背包問題[7]等。普通背包問題僅考慮裝入背包中的物品總重量不超過背包重量限制這一個約束。但實際中如經費預算和項目選擇、分布式計算機系統中處理器和數據庫的分配、資產證券化、生產計劃擬制等都需要考慮多個約束。學者們將這類具有多個約束的背包問題稱為多維背包問題(multidimensional knapsack problem,MKP),它是普通背包問題的一種推廣,同屬NP-hard問題但相對更為復雜[8],具有非常重要的理論和實際研究價值。

給定一待選物品集合Q={q1,q2,…,qn},MKP問題可描述為:從集合Q中選出一組滿足所有問題約束的物品組合并使得所選物品價值總和最大,MKP的數學表述如下:

(1)

目前,求解MKP的方法主要有精確法和啟發式算法2大類。前者諸如動態規劃法、分支界定法、統計分析法、廣義模糊算法等。這類算法對于小規模的MKP問題可求得精確解,但面對大規模MKP問題的龐大解空間卻盡顯乏力,表現為計算量大、迭代收斂慢、求解效果較差。于是,學者們研究了求解MKP問題的啟發式算法,諸如蟻群優化算法[9]、混合遺傳算法[10]、競爭決策算法[11]、二進制粒子群算法[12]、二進制果蠅優化算法[13]、二進制魚群算法[14]等。這些啟發式算法大都是在模擬自然界生物演化或集群行為的基礎上提出的,具有框架靈活,求解效率較高等特點,但同時也不同程度地存在易陷入局部最優解的缺點[15]。

狼群算法(wolfpackalgorithm,WPA)是一種借鑒狼群生存智慧,模擬狼群分工協作式捕獵行為、獵物分配規則的群體智能優化算法[16]。狼群算法具有較好的計算魯棒性和全局搜索能力,其衍生算法已成功應用于求解高維復雜函數優化問題[17]、0-1普通背包問題[18]和PID控制器參數整定[19]。本文結合狼群的繁衍方式對二進制狼群算法進行改進,并針對MKP問題的特點設計了修復機制,提出一種解決MKP問題的改進二進制狼群算法(improvedbinarywolfpackalgorithm,IBWPA),最后基于大量的算例仿真和算法比較驗證了所提方法的有效性。

1改進的二進制狼群算法

1.1一些定義

設在N×m的歐式空間,人工狼i的位置Xi=(xi1,xi2,…,xij,…,xim),其中xij={0,1}(i=1,2,…,N;j=1,2,…,m)。人工狼感知到的獵物氣味濃度Y=f(X),Y即是目標函數值;人工狼之間距離為兩者位置編碼的Manhattan距離。

定義 1反置。對xij反置即是對人工狼i的位置Xi中的第j個編碼位作相異賦值,原為1的設為0,原為0的設為1。

定義 2運動算子[18]。設人工狼i的位置為Xi={xi1,xi2,…,xim},M表示進行反置的編碼位集合且不為空集,可理解為人工狼的可活動范圍;r表示進行反置的編碼位的數目,可理解為人工狼的行走步長;運動算子Θ(Xi,M,r)表示在M中隨機選擇r個編碼位并將其值反置。例如Xi=(0,1,0,1,0,0),M={2,5},r=1,則Θ(Xi,M,r)=(0,0,0,1,0,0)或(0,1, 0,1,1,0)。

1.2二進制狼群算法簡介

二進制狼群算法(binarywolfpackalgorithm,BWPA)是在基本狼群算法的基礎上通過定義運動算子,對人工狼位置、步長和智能行為重新進行二進制編碼設計后提出的。BWPA由頭狼產生規則,游走行為、召喚行為、圍攻行為3種智能行為和狼群更新機制組成。BWPA保留了基本狼群算法基于職責分工的協作式搜索特性。同時,算法中的隨機操作和參數的限定范圍內隨機選取方法使得算法可接受一些退化解,同時使算法能更好地遍歷解空間,維持著較大的搜索區域。文獻[18]已通過大量仿真實驗驗證了BWPA相對于學習型和聲搜索算法、二進制粒子群算法、貪婪遺傳算法、量子遺傳算法等算法擁有較好的求解穩定性、收斂性和全局搜索能力。

為論述的完整性,下面首先給出BWPA具體算法的計算步驟。

步驟 1設置相應算法參數,初始化人工狼位置。

式中,j=1,2,…,m,k的初值為1；null表示空值。此時的集合Mb實際是猛狼位置Xi與頭狼位置Xd不相同編碼位的集合。若Mb為空集時執行運動算子Θ(Xi,Ma,1)。設Yi和Ylead分別為猛狼i和頭狼位置對應的目標函數值,若Yi>Ylead,則Ylead=Yi,猛狼i替代頭狼;若Yi

步驟 4圍攻行為。將頭狼所在位置Xd視為獵物的位置,參與圍攻的人工狼i的位置Xi依下式進行位置變換得到新位置:比較人工狼實施圍攻行為前后在新舊位置所感知到的獵物氣味濃度并進行貪婪決策。

上述智能行為所涉及的游走步長stepa、奔襲步長stepb、圍攻步長stepc皆為整數,表示人工狼搜索的精細程度。

步驟 5狼群更新。按“勝者為王”的頭狼產生規則對頭狼位置進行更新;再按照“強者生存”的狼群更新機制進行群體更新,即淘汰R匹人工狼,再隨機產生R匹新人工狼,R取[N/(2β),N/β]之間的隨機整數,β為更新比例因子。

步驟 6判斷是否結束。判斷是否達到優化精度要求或最大迭代次數kmax,若達到則輸出頭狼的位置,即所求問題的最優解,否則轉步驟2。

1.3狼群繁衍方式啟發的新人工狼產生方式

自然界狼群除了其協作式搜索、捕獵行為外,其繁衍方式也較為獨特。本文受自然界狼群繁衍方式的啟發改進了原有人工狼位置隨機生成的產生方式。下面將從自然界狼群的繁衍方式和算法中新人工狼產生2方面進行詳述。

(1) 自然界狼群的繁衍方式。成功的生產和幼崽撫育是動態維持狼群種群規模的關鍵。通常,每年11月末,狼開始發情追逐,經過一番較量和決斗,最終勝出的頭狼才有資格和母狼形成配偶而后交配和繁衍后代。狼群中其他狼都嚴格遵守著這一交配戒律,否則會受到嚴厲懲罰[20]。頭狼是狼群里體質最好、最具智慧的,是最好基因的擁有者。進而使得狼群后代擁有遺傳優勢,保證了后代的優秀,同時也控制了狼群的數量,有利于狼群的生存和繁衍。

幼狼出生后,在狼群的呵護下成長,逐漸學會行走、追逐和捕食獵物。需指出的是:從概率意義上講,頭狼和狼群越強,新生育的狼就能越快適應環境和參與捕獵。在此進化過程中,幼狼的適應能力和獨立生存能力越來越強,與頭狼的能力差距也逐漸縮小。其中少數狼成年后甚至可以打敗原有頭狼而成為狼群領袖。

(2) 算法中新人工狼的產生。通常,自然界狼群唯有頭狼擁有交配權,即新產生的幼狼都為頭狼的子女,擁有頭狼的優良基因。因此,算法中新的人工狼Xnew由式(2)計算得到

(2)

式中，Xd為頭狼所在位置；Ma={1,2,…,m}。L由式(3)計算得到

(3)

圖1　L與k的關系曲線

由1.1節中的定義可知,L表示對頭狼位置編碼Xd進行反置的編碼位數目,人工狼之間距離為兩者位置編碼的Manhattan距離,因此L也可表示頭狼與新人工狼之間的距離,即可理解為兩者的差異。由圖1可知,L由一定限值隨著k的減小而減小,表明根據式(2)所產生的新人工狼的位置與頭狼位置差異逐漸減小。

此種設計在原理上與自然界狼群的繁衍特點是一致的。同時,對于算法,在迭代進化初期,一方面新人工狼位置是以頭狼位置為基礎,使得頭狼的部分優良基因得以繼承;另一方面又對頭狼位置編碼賦予較多的反置,探索更廣域的解空間,有利于優秀新解的產生,并減小了陷入局部極值的概率;隨著人工狼群迭代進化,各人工狼逐漸處于優良解域,此時賦予較小的反置編碼位數有利于算法在優良解域內進行精細搜索。

L的這樣設計體現狼群通過進化使得后代生育質量逐漸提高,后代的適應能力逐漸增強。同時也有利于算法以較快的速度收斂。

新狼產生后即可采用“強者生存”的狼群更新機制對狼群進行更新。即在算法中去除目標函數值最差的R匹人工狼,同時依照上述方法新產生R匹人工狼。同樣,R的設定方法同BWPA算法計算步驟5所述。

1.4目標函數

MKP問題是典型的多約束組合優化問題。為方便尋優計算,通常利用一較大的懲罰參數對不滿足約束的變量進行懲罰并建立單目標無約束目標函數,進而將MKP問題轉化為無約束問題[21]。但文獻[22]的研究顯示懲罰參數過大會導致算法很容易陷入局部最優。這里采用一種動態懲罰函數的形式對式(1)中目標函數進行改進有

(4)

這樣的目標函數設計減小了由于懲罰參數過大而導致算法陷入局部最優的風險,將人工狼導向MKP問題的可行解域或可行解邊界附近的不可行解域,防止算法深陷不可行解域。

1.5試探裝載式的修復機制

求解背包問題時,算法產生的新個體有可能為不可行解,因此應該采用修復機制來處理。對于MKP問題,常采用的基于偽效用比率的修復方法的核心步驟需求解MKP對偶問題,進而引入較多的計算量,降低算法效率[23]。

這里采用一種相對更為簡便易于理解的、無需計算多維背包問題對偶問題的最優解的試探裝載式修復機制,其具體計算步驟如下。

步驟 1據{ρj}的值按降序產生序列T=(T1,T2,…,Tn),其中ρj由式(5)求得

(5)

步驟 2按照序列T的順序對不可行解的編碼位設為1,即試探性地逐個裝入物品,并判斷是否滿足所有的約束。若滿足則編碼位j為1得以保留,物品j被裝入背包；否則置為0。

步驟 3試探性地依T的逆序將上步所得可行解中編碼位為0的置為1,即載入該物品,直到不滿足某背包約束。

如此,即可得到修復后的可行解。

1.6算法流程

IBWPA算法同BWPA,也由頭狼產生規則,游走行為、召喚行為、圍攻行為3種智能行為和狼群更新機制組成。IBWPA是在BWPA的基礎上改進了新人工狼產生方式,并針對多維背包問題的特點,設計了試探裝載式的修復機制。具體地,給出求解MKP的IBWPA的算法流程如圖2所示。

圖2　求解MKP的IBWPA的算法流程圖

2實驗與分析

為充分驗證算法有效性,設計了3組實驗,算例分別來自于以下2組可選算例。

第1組可選算例來自ELIB數據庫(http:∥elib.zib.de/pub/mp-testdata/ip/sac94-suite/index.html)。該數據庫提供了hp、pb、pet、sent、weing、weish6類共55個MKP問題算例。

第2組可選算例來自OR_LIB數據庫(http:∥people.brunel.ac.uk/～mastjjb/jeb/info.html)。該數據庫提供了按照n～m～g方式組合產生了270個大規模難解的MKP問題算例,其中 n={100, 250, 500}為物品數,m={5,10,30}為背包約束維數,g={0.25,0.50,0.75}為緊度。

實驗環境為:WindowsXP系統,2GB內存,CPU2.00GHz,算法基于Matlab2008a實現。

2.1實驗1——修復機制的有效性測試

(6)

隨機產生10 000個隨機解作為初始解,采用3種方法分別對初始解中的不可行解進行修復,并統計經修復后10 000個解的物品總價值的均值和計算平均耗時,實驗結果如表1所示。

表1　判定距離dnear對IBWPA的影響

由表1可見,對于4個典型的MKP算例,方法1均能獲得相對較好的修復效果,修復后物品總價值的平均值要大于其他2種方法所得。且從計算時間上看,方法1所需時間也相對較短。分析認為:相對于方法1而言,方法2和方法3中都有大量的求和運算,且2種方法都是先取出其所定義的比值小的物品再放入比值大的物品,其間會產生較多的盲目操作,因而所需計算時間相對較少。綜上,可見試探裝載式的修復機制在計算耗時和修復效果方面的相對優勢。

2.2實驗2——10個來自ELIB數據庫的算例

在ELIB數據庫6類算例中每類選取1～2個典型的算例組成共10個算例進行實驗。實驗用算例物品個數為28 ～ 90,背包約束維數為2 ～ 30,屬于中小規模的MKP問題。

將IBWPA與BWPA、最新文獻[25]所提的具有時變加速度二進制粒子群算法(binary particle swarm optimization with time-varying acceleration coefficients, BPSOTVAC)和具有時變加速度的混沌二進制粒子群算法(chaotic binary swarm optimization with time-varying acceleration coefficients, CBPSOTVAC)進行對比。

BPSOTVAC和CBPSOTVAC的參數設置如下:粒子數目N=5n,n為MKP算例的物品數目;最大迭代次數kmax=20 000,學習因子c1i=c2f= 2.5,c2i=c1f= 0.5,慣性權重wmax=1.5,wmin=0.5,最大速度Vmax=4。另CBPSOTVAC采用logistic方程且初值y1(0)=y2(0)為[0,1]間的隨機數。對于BWPA和IBWPA,狼群規模也設置為N=5n,但為突出算法收斂效率,設Kmax=200。更新比例因子β僅決定淘汰人工狼的數量R的隨機選取范圍,最大游走次數Tmax僅決定可能的游走次數上限,因此,一般將兩者分別設置為β=3和Tmax=10即可。2個算法中的智能行為、更新規則也有大量的隨機操作。因此，2個算法對于參數設置并不敏感。判定距離dnear決定著人工狼何時由召喚行為進入圍攻行為,即在解域中算法由向當前種群最優位置逼近狀態轉入對全局最優解的精細搜索狀態;游走步長stepa決定探狼鄰域搜索精細程度;奔襲步長stepb決定猛狼向當前種群最優位置逼近的速度;經驗地,三者存在關系:dnear=stepb=2×stepa。一般而言對于較小規模的MKP問題,三者的取值都較小,本實驗中stepa=2。

利用BPSOTVAC、CBPSOTVAC、BWPA和IBWPA這4種算法對ELIB數據庫10個MKP問題分別進行100次獨立計算。結果從成功率(success rate, SR),平均絕對偏差(mean absolute deviation, MAD),平均絕對誤差率(mean absolute percentage error, MAPE),標準差(standard deviation, SD)共4個方面進行對比,如表2所示。SR即計算中得到已知最優解次數除以總計算次數,MAD即為100次計算中與所給最優值之差的平均值,MAPE即為100次計算結果相對于已知最優值的誤差率的平均值。

表2　各算法計算ELIB數據庫10個MKP算例的結果

續表2

從表2可看出,對于ELIB數據庫這10個MKP問題,IBWPA都能找到其參考最優解且成功率在90%以上。而其他3種方法在物品數量大于30時成功率就下降至70%以內,對于規模較大的weish22和weish26兩組算例成功率更降至50%以內。對于維數較小的weing3和pb4算例,在100次計算中,BWPA和IBWPA對于每個算例都能獲得已知最優解,而BPSOTVAC和CBPSOTVAC則不然,可見2種狼群算法對于小規模MKP問題的求解穩定性。

隨著問題規模的增大,在有限次迭代計算中,各算法的求解精度和穩定性均受到影響,表現為平均絕對誤差率MAD和SD增大、SR降低等。但從SR、MAD等4個指標來看,IBWPA算法無論從求解精度還是求解穩定性方面都要優于原BWPA、BPSOTVAC和CBPSOTVAC這3種算法。

2.3實驗3——9個來自OR_LIB數據庫的算例

為了進一步測試IBWPA算法性能,選取較實驗2規模更大的OR_LIB數據庫中的9組算例作為試驗用算例。利用IBWPA算法對每個算例獨立計算50次,如表3所示，結果從算例的已知最優解G,相對于G的最小偏差率(least error rate, LER)，偏差方差(error standard deviation，ESD)等4個方面進行對比。其中LER=(Y-Y*)/Y*,Y為算法所得最優解，Y*為已知最優解。

表3　IBWPA計算OR-LIB數據庫9個MKP算例的結果

同時算例名稱包含了背包約束維數m、物品數量n、緊度g和編號共4個信息,例如OR5x100-25_1就表示此MKP算例為m=5,n=100,g=0.25的第1個算例。對于BWPA和IBWPA算法,除Kmax=1 000,stepa=3外,Tmax,β,N的參數設置也同實驗2。

由表3可見,在50次計算中,IBWPA找到的最優解與已知最優解的相對偏差很小。其中OR5x100-25-1和OR5x100-50-2這2組算例所得的最優解分別為24 381(放入背包的物品集合為:2,4,7,9,11,19,24,26,27,29,30,32,44,50,57,62,63,66,69,71,74,77,79,85,86,92,93,96,99),42 545(放入背包的物品集合為:7,8,11,12,13,14,21,23,24,25,28,29,31,33,34,35,36,38,40,41,43,44,47,48,49,50,51,52,55,56,58,59,62,69,70,71,74,77,79,82,84,86,87,88,90,94,97,98,99,100)。這2組所得的結果要優于文獻[11]所得出的24 373(放入背包的物品集合為:2,7,8,9,11,16,18, 19,24,27,29,30,32,35,44,50,57,62,63,66,68,69,76,77,79,85,86,93,99),和42 471(放入背包的物品集合為:2,5,7,12,13,14,23,24,25,27,29,31,33,34,35,36, 38,40,41,43,44,46,47,48,49,50,51,52,55,56,58,59,62,69,70,71,72,74,77,79,82,84,86,87,88,90,94,97,98,99,100)。9個典型算例計算所得的最差的LER僅為0.004 7,最差MAPE僅為0.85%,由此可見IBWPA對于大規模MKP問題的求解精度。

由表3可知,算例OR5x100-75-3的緊度為0.75且其MAPE值為0.15%,OR5x100-50-2和OR5x100-25-1的緊度分別降至0.50和0.25,其MAPE值分別增加至0.26%和0.55%;而算例OR5x250-75-3的緊度也為0.75且其MAPE值為0.19%,OR5x250-25-1的緊度降至0.25，而且其MAPE值則增加至0.85%。觀察可以發現MAPE具有隨緊度減小而增大的趨勢,且問題規模大趨勢更明顯。分析認為:當問題規模相同時,緊度值越小則可行解空間也相對越小。而MKP問題的規模越大則其對應的解空間也就越大。自然地,當面對更大規模、較小緊度值的MKP問題時,算法就需要在相對更大的解空間中尋找相對更小的可行解,從而導致了算法求解質量的下降。另外,由9個算例的ESD可知,IBWPA計算得到的最佳ESD和最差ESD分別為5.40e-4和0.003 1,由此也可見IBWPA具有較好的求解穩定性。

3結論

在二進制狼群算法的基礎上,深入分析了狼群繁衍方式,改進了新人工狼產生方法,使得頭狼的部分優良基因得以繼承的同時新人工狼還可探索更廣的解域,減小了陷入局部極值的概率;針對MKP問題的特點,提出了無需求解MKP對偶問題的試探裝載式的修復機制,并通過對比實驗例證了修復方法的有效性;最終提出了求解MKP問題的改進二進制狼群算法,并通過與二進制狼群算法、新近文獻所提出的兩種粒子群算法的改進算法就19個不同規模、不同特點的經典算例進行了仿真對比計算,結果表明IBWPA算法具有相對較好的求解穩定性、收斂性和全局搜索能力。將來可進一步分析IBWPA算法的參數效應,設計新的參數設置方法以精簡參數,并將算法應用于裝備優化配置、無人機任務分配等組合優化問題中。

參考文獻：

[1] Zou D X, Gao L Q, Li S, et al. Solving 0-1 knapsack problem by a novel global harmony search algorithm[J].AppliedSoftComputing, 2011, 11(2):1556-1564.

[2] Kaushik K B, Sarmah S P. Shuffled frog leaping algorithm and its application to 0/1 knapsack problem[J].AppliedSoftComputing, 2014, 19(6):252-263.

[3] Yoon Y, Kim Y H, Moon B R. A theoretical and empirical investigation on the lagrangian capacities of the 0-1 multidimensional knapsack problem[J].EuropeanJournalofOperationalResearch, 2012, 218(2):366-376.

[4] Sharkey T C, Geunes J. A class of nonlinear non-separable continuous knapsack and multiple-choice knapsack problems[J].MathematicalProgramming, 2011, 126(1):69-96.

[5] Zhang X X, Tang L X. A new ACO&PR algorithm for multiple-choice multi-dimensional knapsack problem[J].ControlandDecision, 2009, 24(5):729-733.(張曉霞, 唐立新. 一種新的求解MMKP問題的ACO&PR算法[J]. 控制與決策, 2009, 24(5):729-733.)

[6] Gao J Q, He G X, Liang R H, et al. A quantum-inspired artificial immune system for the multi-objective 0-1 knapsack problem[J].AppliedMathematicsandComputation, 2014, 230(1):120-137.

[7] Azad M K, Rocha A M, Fernandes E M. A simplified binary artificial fish swarm algorithm for 0-1 quadratic knapsack problems[J].JournalofComputationalandAppliedMathematics, 2014, 259(3):897-904.

[8] Freville A. The multidimensional 0-1 knapsack problems:an overview[J].EuropeanJournalofOperationResearch, 2004, 155(1):1-21.

[9] Yu X C, Zhang T W. An improved ant algorithm for multidimensional knapsack problem[J].ChineseJournalofComputers, 2008, 31(5):810-819.(喻學才, 張田文. 多維背包問題的一個蟻群優化算法[J]. 計算機學報, 2008, 31(5):810-819.)

[10] Djannaty F, Doostdar S. A hybrid genetic algorithm for the multidimensional knapsack problem[J].InternationalJournalofContemporaryMathematicalSciences, 2008, 9(3):443-456.

[11] Xiong X H, Ning A B, Ma L. Competitive decision algorithm for multidimensional 0/1 knapsack problem based on multi-exchange neighborhood search[J].SystemsEngineeringTheory&Practice,2010,30(8):1448-1456.(熊小華,寧愛兵,馬良.基于多變換領域搜索的多維0/1背包問題競爭決策算法[J].系統工程理論與實踐,2010,30(8):1448-1456.)

[12] Bansal J C, Deep K. A modified binary particle swarm optimization for knapsack problems[J].AppliedMathematicsandComputation, 2012, 218(22):1042-1061.

[13] Wang L, Zheng X L, Wang S Y. A novel binary fruit fly optimization algorithm for solving the multidimensional knapsack problem[J].Knowledge-BasedSystems,2013,48(8):17-23.

[14] Azad M A, Rocha A M, Fernandes E M. Improved binary artificial fish swarm algorithm for the 0-1 multidimensional knapsack problems[J].SwarmandEvolutionaryComputation,2014,14(2):66-75.

[15] Chu S C, Huang H C, Roddick J F, et al. Overview of algorithms for swarm intelligence[C]∥Proc.ofthe3rdInternationalConferenceonComputationalCollectiveIntelligence,2011:28-41.

[16] Wu H S, Zhang F M, Wu L S. New swarm intelligence algorithm-wolf pack algorithm[J].SystemsEngineeringandElectronics, 2013, 35(11):3430-3438.(吳虎勝,張鳳鳴,吳廬山.一種新的群體智能算法——狼群算法[J].系統工程與電子技術,2013,35(11):3430-3438.)

[17] Wu H S, Zhang F M. Wolf pack algorithm for unconstrained global optimization[EB/OL]. [2014-03-09].http∥dx.doi.org/10.1155/20141465082.

[18] Wu H S, Zhang F M, Zhan R J, et al. A binary wolf pack algorithm for solving 0-1 knapsack problem[J].SystemsEngineeringandElectronics, 2014, 36(8):1660-1667.(吳虎勝,張鳳鳴,戰仁軍,等.求解0-1背包問題的二進制狼群算法[J].系統工程與電子技術,2014,36(8):1660-1667.)

[19] Wu H S, Zhang F M. A uncultivated wolf pack algorithm for high-dimensional functions and its application in parameters optimization of PID controller[C]∥Proc.oftheIEEECongressonEvolutionaryComputation, 2014:1477-1482.

[20] Michael L.Wolf:habitats,lifecycles,foodchains,threats[M]. London:Hodder Wayland, 2002.

[21] Ling G, Zhu W X. A filled function based variable neighborhood search method for the multidimensional knapsack problem[J].JournalofFuzhouUniversity(NaturalScienceEdition), 2012, 40(1):14-21.(林耿, 朱文興. 多維背包問題的變鄰域填充函數算法[J]. 福州大學學報(自然科學版), 2012, 40(1):14-21.)

[22] Unler A, Murat A. A discrete particle swarm optimization method for feature selection in binary classification problems[J].EuropeanJournalofOperationalResearch,2010,206(3):528-539.

[23] Wang L, Wang S Y, Fang C. A hybrid distribution estimation algorithm for solving multidimensional knapsack problem[J].ControlandDecision,2011,26(8):1121-1125.(王凌,王圣堯,方晨.一種求解多維背包問題的混合分布估計算法[J].控制與決策,2011,26(8):1121-1125.)

[24] Hao C M, Wu B. Improved particle swarm algorithm for the multi-dimensional knapsack problem[J].Microelectronics&Computer, 2012, 29(9):129-132.(郝春梅, 吳波. 改進型粒子群算法解決多維背包問題[J]. 微電子學與計算機, 2012, 29(9):129-132.)

[25] Chih M C, Lin C J, Chern M S, et al. Particle swarm optimization with time-varying acceleration coefficients for the multidimensional knapsack problem[J].AppliedMathematicalMo-deling, 2014, 38(4):1338-1350.

吳虎勝(1986-),男,博士研究生,主要研究方向為信息系統工程與智能決策、智能優化算法、智能數據挖掘。

E-mail:wuhusheng0421@163.com

張鳳鳴(1963-),男,教授,博士,主要研究方向為系統工程、數據挖掘、故障診斷。

E-mail:zfmwenzhang007@163.com

戰仁軍(1963-),男,教授,博士,主要研究方向為軍事裝備學、警用器材、非致命武器。

E-mail:zrwenzhang007@163.com

李浩(1981-),男,講師,博士,主要研究方向為軍事通信、數據挖掘。

E-mail:lwdwenzhang007@163.com

梁曉龍(1981-),男,副教授,博士,主要研究方向為武器控制系統、數據融合。

E-mail:xiaolong.liang@hotmail.com

網絡優先出版地址：http:∥www.cnki.net/kcms/detail/11.2422.TN.20141119.2214.006.html

Improved binary wolf pack algorithm for solving

multidimensional knapsack problem

WU Hu-sheng1,2, ZHANG Feng-ming2, ZHAN Ren-jun1, LI Hao2, LIANG Xiao-long3

(1.MaterielEngineeringCollege,ArmedPoliceForceEngineeringUniversity,Xi’an710086,China;

2.MaterielManagementandSafetyEngineeringCollege,AirForceEngineeringUniversity,

Xi’an710051,China;3.AirTrafficControlandNavigationCollege,AirForce

EngineeringUniversity,Xi’an710051,China)

Abstract:The wolf pack algorithm has been proposed based on inspiration by group survival swarm intelligence of the wolf pack, and successfully applied to complex function optimization problems and the normal 0-1 knapsack problem. To solve the multidimensional knapsack problem (MKP), a trying-loading repair operator based on the MKP specific knowledge is designed to effectively repair and improve infeasible solutions. Then, traditional objective function based on large penalty parameters has been improved so as to reduce the risk of easily trapping in the local optima. Meanwhile, inspired by the reproductive rule of the wolf pack, an improved binary wolf pack algorithm (IBWPA) is proposed for solving the MKP. Simulation results based on 19 benchmark MKP instances with different scales and comparative analysis between the IBWPA and other algorithms demonstrate the effectiveness and computational robustness of the proposed algorithm.

Keywords:evolutionary computation; swarm intelligence; binary wolf pack algorithm; combinatorial optimization; multidimensional knapsack problem

作者簡介：

中圖分類號：TP 18

文獻標志碼：ADOI:10.3969/j.issn.1001-506X.2015.05.17

基金項目：國家自然科學基金(71401178,61472443)；陜西省自然科學基金(2013JQ8042)資助課題

收稿日期：2014-04-25；修回日期：2014-10-20；網絡優先出版日期：2014-11-19。