吳虎勝, 張鳳鳴, 戰(zhàn)仁軍, 李　浩, 梁曉龍

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

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

3. 空軍工程大學(xué)空管領(lǐng)航學(xué)院, 陜西 西安 710051)

?

利用改進(jìn)的二進(jìn)制狼群算法求解多維背包問題

吳虎勝1,2, 張鳳鳴2, 戰(zhàn)仁軍1, 李浩2, 梁曉龍3

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

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

3. 空軍工程大學(xué)空管領(lǐng)航學(xué)院, 陜西 西安 710051)

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

關(guān)鍵詞：進(jìn)化計算; 群體智能; 二進(jìn)制狼群算法; 組合優(yōu)化; 多維背包問題

0引言

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

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

(1)

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

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

1改進(jìn)的二進(jìn)制狼群算法

1.1一些定義

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

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

定義 2運(yùn)動算子[18]。設(shè)人工狼i的位置為Xi={xi1,xi2,…,xim},M表示進(jìn)行反置的編碼位集合且不為空集,可理解為人工狼的可活動范圍;r表示進(jìn)行反置的編碼位的數(shù)目,可理解為人工狼的行走步長;運(yùn)動算子Θ(Xi,M,r)表示在M中隨機(jī)選擇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二進(jìn)制狼群算法簡介

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

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

步驟 1設(shè)置相應(yīng)算法參數(shù),初始化人工狼位置。

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

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

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

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

步驟 6判斷是否結(jié)束。判斷是否達(dá)到優(yōu)化精度要求或最大迭代次數(shù)kmax,若達(dá)到則輸出頭狼的位置,即所求問題的最優(yōu)解,否則轉(zhuǎn)步驟2。

1.3狼群繁衍方式啟發(fā)的新人工狼產(chǎn)生方式

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

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

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

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

(2)

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

(3)

圖1　L與k的關(guān)系曲線

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

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

L的這樣設(shè)計體現(xiàn)狼群通過進(jìn)化使得后代生育質(zhì)量逐漸提高,后代的適應(yīng)能力逐漸增強(qiáng)。同時也有利于算法以較快的速度收斂。

新狼產(chǎn)生后即可采用“強(qiáng)者生存”的狼群更新機(jī)制對狼群進(jìn)行更新。即在算法中去除目標(biāo)函數(shù)值最差的R匹人工狼,同時依照上述方法新產(chǎn)生R匹人工狼。同樣,R的設(shè)定方法同BWPA算法計算步驟5所述。

1.4目標(biāo)函數(shù)

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

(4)

這樣的目標(biāo)函數(shù)設(shè)計減小了由于懲罰參數(shù)過大而導(dǎo)致算法陷入局部最優(yōu)的風(fēng)險,將人工狼導(dǎo)向MKP問題的可行解域或可行解邊界附近的不可行解域,防止算法深陷不可行解域。

1.5試探裝載式的修復(fù)機(jī)制

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

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

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

(5)

步驟 2按照序列T的順序?qū)Σ豢尚薪獾木幋a位設(shè)為1,即試探性地逐個裝入物品,并判斷是否滿足所有的約束。若滿足則編碼位j為1得以保留,物品j被裝入背包；否則置為0。

步驟 3試探性地依T的逆序?qū)⑸喜剿每尚薪庵芯幋a位為0的置為1,即載入該物品,直到不滿足某背包約束。

如此,即可得到修復(fù)后的可行解。

1.6算法流程

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

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

2實驗與分析

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

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

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

實驗環(huán)境為:WindowsXP系統(tǒng),2GB內(nèi)存,CPU2.00GHz,算法基于Matlab2008a實現(xiàn)。

2.1實驗1——修復(fù)機(jī)制的有效性測試

(6)

隨機(jī)產(chǎn)生10 000個隨機(jī)解作為初始解,采用3種方法分別對初始解中的不可行解進(jìn)行修復(fù),并統(tǒng)計經(jīng)修復(fù)后10 000個解的物品總價值的均值和計算平均耗時,實驗結(jié)果如表1所示。

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

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

2.2實驗2——10個來自ELIB數(shù)據(jù)庫的算例

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

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

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

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

表2　各算法計算ELIB數(shù)據(jù)庫10個MKP算例的結(jié)果

續(xù)表2

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

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

2.3實驗3——9個來自O(shè)R_LIB數(shù)據(jù)庫的算例

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

表3　IBWPA計算OR-LIB數(shù)據(jù)庫9個MKP算例的結(jié)果

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

由表3可見,在50次計算中,IBWPA找到的最優(yōu)解與已知最優(yōu)解的相對偏差很小。其中OR5x100-25-1和OR5x100-50-2這2組算例所得的最優(yōu)解分別為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組所得的結(jié)果要優(yōu)于文獻(xiàn)[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對于大規(guī)模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%。觀察可以發(fā)現(xiàn)MAPE具有隨緊度減小而增大的趨勢,且問題規(guī)模大趨勢更明顯。分析認(rèn)為:當(dāng)問題規(guī)模相同時,緊度值越小則可行解空間也相對越小。而MKP問題的規(guī)模越大則其對應(yīng)的解空間也就越大。自然地,當(dāng)面對更大規(guī)模、較小緊度值的MKP問題時,算法就需要在相對更大的解空間中尋找相對更小的可行解,從而導(dǎo)致了算法求解質(zhì)量的下降。另外,由9個算例的ESD可知,IBWPA計算得到的最佳ESD和最差ESD分別為5.40e-4和0.003 1,由此也可見IBWPA具有較好的求解穩(wěn)定性。

3結(jié)論

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

參考文獻(xiàn)：

[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.(喻學(xué)才, 張?zhí)镂? 多維背包問題的一個蟻群優(yōu)化算法[J]. 計算機(jī)學(xué)報, 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.(熊小華,寧愛兵,馬良.基于多變換領(lǐng)域搜索的多維0/1背包問題競爭決策算法[J].系統(tǒng)工程理論與實踐,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].系統(tǒng)工程與電子技術(shù),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.(吳虎勝,張鳳鳴,戰(zhàn)仁軍,等.求解0-1背包問題的二進(jìn)制狼群算法[J].系統(tǒng)工程與電子技術(shù),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.(林耿, 朱文興. 多維背包問題的變鄰域填充函數(shù)算法[J]. 福州大學(xué)學(xué)報(自然科學(xué)版), 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ìn)型粒子群算法解決多維背包問題[J]. 微電子學(xué)與計算機(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-),男,博士研究生,主要研究方向為信息系統(tǒng)工程與智能決策、智能優(yōu)化算法、智能數(shù)據(jù)挖掘。

E-mail:wuhusheng0421@163.com

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

E-mail:zfmwenzhang007@163.com

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

E-mail:zrwenzhang007@163.com

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

E-mail:lwdwenzhang007@163.com

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

E-mail:xiaolong.liang@hotmail.com

網(wǎng)絡(luò)優(yōu)先出版地址：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

文獻(xiàn)標(biāo)志碼：ADOI:10.3969/j.issn.1001-506X.2015.05.17

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

收稿日期：2014-04-25；修回日期：2014-10-20；網(wǎng)絡(luò)優(yōu)先出版日期：2014-11-19。