劉夢(mèng)佳，向鳳紅，郭 寧，毛劍琳

(昆明理工大學(xué) 信息工程與自動(dòng)化學(xué)院，云南 昆明 650500)

多維背包問題(Multidimensional Knapsack Problem，MKP)又名多約束背包問題，是著名的整數(shù)規(guī)劃問題之一。在實(shí)際應(yīng)用中，許多問題都可以用多維背包問題來描述，如材料切割、資源分配、貨物裝載、投資決策等[1]。在近幾十年里世界上許多研究機(jī)構(gòu)和個(gè)人對(duì)它做了大量的研究，已有的求解方法可分為精確方法(如分支定界法、回溯法、動(dòng)態(tài)規(guī)劃法等[2])，近似算法(如貪婪法、拉格朗日法、蟻群優(yōu)化算法[3-5]、粒子群算法[6]、遺傳算法[7]、布谷鳥算法[8]等)以及混合算法3大類。

遺傳算法[7]是受生物進(jìn)化啟發(fā)發(fā)展起來的一種智能優(yōu)化算法，它模擬生命進(jìn)化機(jī)制，即模擬自然選擇和遺傳進(jìn)化中發(fā)生的繁殖、交配和突變現(xiàn)象，從任意一個(gè)初始種群出發(fā)，通過選擇、交叉和變異操作，產(chǎn)生一群新的更適應(yīng)環(huán)境的個(gè)體，一代代不斷繁殖、進(jìn)化，最后收斂到最適應(yīng)環(huán)境的個(gè)體上，求得問題的最優(yōu)解。遺傳算法具有較強(qiáng)的全局搜索能力，但收斂速度較慢，求解精度不高。蟻群算法[9]求解多維背包問題時(shí)，每只螞蟻主要根據(jù)積累在物品上的信息素量的大小來依次選擇是否生產(chǎn)該物品，被螞蟻選擇的物品就是要消耗資源所生產(chǎn)的物品。在蟻群算法進(jìn)行過程中，信息素正反饋的思想使其能較快收斂到局部最優(yōu)解，但其全局搜索能力較低，易陷入局部最優(yōu)，產(chǎn)生早熟現(xiàn)象。近年來，遺傳蟻群混合算法得以快速發(fā)展，涌現(xiàn)出多種混合方式[10-13]。

本文針對(duì)原有的遺傳蟻群混合算法求解精度低、收斂速度慢等缺陷，設(shè)計(jì)了一種改進(jìn)的遺傳蟻群混合算法，對(duì)傳統(tǒng)遺傳算法的交叉和變異算子進(jìn)行了改進(jìn)，并在蟻群算法的運(yùn)行過程中引入了概率和為u的輪盤賭方式、禁忌表交換策略以及信息素的混沌更新策略。實(shí)驗(yàn)結(jié)果表明該算法在搜索能力和收斂速度方面都有明顯提高。

1 多維背包問題

具有多類資源限制的背包問題，如投資決策問題中受到資金、人力、原材料等多維約束的限制，即多維背包問題(MKP)[14]。多維背包問題可描述為：給定n個(gè)價(jià)值為Pj(j=1,2,…,n)的物品，m種有限數(shù)量的資源約束ci(i=1,2,…,m),物品j對(duì)資源i的消耗為wij(i=1,2,…,m;j=1,2,…,n)；從n個(gè)物品中選出一組滿足所有資源約束的物品組合使得所選物品價(jià)值總和最大。數(shù)學(xué)模型為

(1)

2 改進(jìn)遺傳蟻群混合算法求解

鑒于遺傳算法可通過交叉操作、變異操作產(chǎn)生新的個(gè)體增強(qiáng)種群多樣性，提高算法的全局搜索能力，蟻群算法可增強(qiáng)尋優(yōu)精度。在此挑選d只較優(yōu)螞蟻進(jìn)行遺傳算法尋優(yōu)，并利用該尋優(yōu)結(jié)果對(duì)蟻群進(jìn)行全局信息素更新，引導(dǎo)螞蟻向最優(yōu)方向?qū)?yōu)。其它螞蟻進(jìn)行蟻群算法尋優(yōu)，并利用其尋優(yōu)結(jié)果對(duì)蟻群進(jìn)行信息素的局部更新，對(duì)下一個(gè)螞蟻尋優(yōu)的方向進(jìn)行指引。算法可具體描述為：每次進(jìn)行迭代時(shí)，螞蟻總數(shù)目為size，選擇d(d=size/4)只較優(yōu)螞蟻進(jìn)行遺傳算法尋優(yōu)，該尋優(yōu)過程結(jié)束后進(jìn)行信息素的全局更新，其余的螞蟻進(jìn)行蟻群算法尋優(yōu)，此尋優(yōu)過程結(jié)束后進(jìn)行局部信息素的更新。每一代整體尋優(yōu)過程結(jié)束后，將當(dāng)代size只螞蟻尋覓到的解和前一代的d個(gè)較優(yōu)解進(jìn)行混合降序排列，選取排序后的前d只螞蟻?zhàn)鳛橄乱淮蔚鷷r(shí)進(jìn)行遺傳算法的初始種群。

2.1 算法流程

步驟1初始化，設(shè)置最大迭代次數(shù)Gmax，交叉概率Pc，變異概率Pm，種群大小size；

步驟2隨機(jī)生成初始種群P(d,n)，并按適應(yīng)值進(jìn)行降序排列；

步驟3對(duì)d只螞蟻采用遺傳算法尋優(yōu)。

(1)復(fù)制P(A=P)；

(2)按個(gè)體適應(yīng)度選擇兩個(gè)解，通過交叉操作對(duì)P產(chǎn)生新的解；

(3)每條染色體以概率Pm對(duì)P進(jìn)行變異操作；

(4)對(duì)種群進(jìn)行最大化利率修復(fù)策略；

(5)進(jìn)行信息素的全局更新；

步驟4對(duì)size-d只螞蟻進(jìn)行蟻群算法尋優(yōu)。

(1)參數(shù)初始化。令時(shí)間t=0，候選物品序號(hào)集allowed=[1:n]，螞蟻個(gè)體禁忌表tabuk=0,信息素量τj(t)=1,信息揮發(fā)素ρ=0.7；

(2)生成B=zeros((size-d),n)，將各螞蟻的初始出發(fā)點(diǎn)設(shè)在當(dāng)前解集中，螞蟻的禁忌表指針k=1；

(3)對(duì)于size-d只螞蟻。

②每只螞蟻獨(dú)立尋得一個(gè)解，令臨時(shí)向量temp(j)=Pj(1≤j≤n)。螞蟻k按物品被選擇的概率以概率之和為u的輪盤賭方法選擇下一個(gè)物品j+1，然后令u=u-temp(j+1),temp(j+1)=0。若選擇物品j未超出所需消耗資源的限制，則xkj=1, 轉(zhuǎn)步驟4-(3)-③；否則xkj=0，j=j+1。若j

③將所選生產(chǎn)物品序號(hào)加入到tabuk中，修改禁忌表指針。

(4)采用禁忌表交換策略；

(5)對(duì)局部信息素進(jìn)行更新；

(6)若k

步驟5對(duì)蟻群B、P、A按適應(yīng)值降序排列，選擇前d只螞蟻組成P；

步驟6保留當(dāng)代最優(yōu)個(gè)體；

步驟7判斷g>Gmax是否成立，若成立則循環(huán)結(jié)束輸出最優(yōu)結(jié)果；否則清空禁忌表，令Δτj=0，g=g+1,轉(zhuǎn)步驟3；

步驟8若G

步驟9g=g+1，判斷g>Gmax是否成立，若否，重復(fù)步驟3～步驟8；若是，輸出最優(yōu)解，結(jié)束程序。

2.2 算法具體策略

(1)交叉操作。采用均勻交叉法，父代利用掩碼進(jìn)行交叉，采用“優(yōu)、優(yōu)交叉”和“差、差交叉”策略可以有效地保持群體的多樣性，使算法具有較強(qiáng)的搜索能力。交叉規(guī)則：掩碼為1表示父代A為子代提供變量值，掩碼為0表示父代B為子代提供變量值；

(2)變異操作。變異個(gè)體根據(jù)變異概率Pm隨機(jī)產(chǎn)生，變異基因位個(gè)數(shù)隨機(jī)生成，所需變異個(gè)體的每個(gè)基因位變異的概率由當(dāng)前種群中所有個(gè)體相同基因位上1和0所占比例之差的絕對(duì)值(在此定義為Ca)決定，Ca越大該基因位進(jìn)行變異的概率越小，反之Ca越小該基因位進(jìn)行變異的概率就越大。例如：1010，1011，1101，1100，1110，0011，各基因位上Ca值分別為Ca1=2/3,Ca2=0,Ca3=1/3,Ca4=0,Ca2=Ca4

(3)最大化利率修復(fù)策略。搜索出不滿足資源消耗上限的解，對(duì)于該選擇策略下被放入的物品，按價(jià)值密度升序排列的先后次序依次刪除物品(即令相應(yīng)物品對(duì)應(yīng)的xj=0)；對(duì)xj=0的物品按價(jià)值密度降序排列的先后次序依次選擇具有最大剩余的那一維資源，直到所消耗資源達(dá)到約束上限為止；

(4)輪盤賭法路徑選擇策略。為增加蟻群搜索的隨機(jī)性，本文提出根據(jù)概率和為u的輪盤賭方式選擇物品。蟻群算法在求解多維背包問題時(shí)，每一個(gè)物品相當(dāng)于一個(gè)有信息素累積的信息單位，螞蟻k根據(jù)選擇概率對(duì)下一個(gè)物品進(jìn)行選擇，由于選擇操作只涉及到概率比較問題，為減少計(jì)算量，將選擇概率的公式定義為

(2)

此時(shí)選擇概率之和不為1，在此設(shè)為u。其中τj(t)為隨時(shí)間不斷更新的信息素量，α為信息素啟發(fā)因子，Sk(t)為第k只螞蟻在t時(shí)刻已選擇的物品序號(hào)集，啟發(fā)函數(shù)ηj表示選擇物品j的期望程度，β為期望啟發(fā)式因子。

信息素量

τj(t+1)=(1-ρ)·τj(t)+Δτj(t)

(3)

信息素量揮發(fā)系數(shù)ρ表示信息素量τj(t)隨時(shí)間的變化而衰減的程度。1-ρ為信息素殘留因子。信息素增量Δτj(t)為t時(shí)刻螞蟻選擇物品j并留在該物品上的信息素，Δτj(t)∈[0,1]。

(4)

其中

(5)

信息素強(qiáng)度

(6)

fk為本次迭代中第k只螞蟻所尋解的適應(yīng)度值，即螞蟻k所選物品的總價(jià)值。上文中的步驟4-(5)是按照式(3)～式(5)進(jìn)行的信息素局部更新。

(5)禁忌表交換策略。本文采用禁忌啟發(fā)式局部?jī)?yōu)化算法，在滿足各維資源約束的條件下，將禁忌表中所選物品的序號(hào)與非禁忌表的物品序號(hào)進(jìn)行交換。在擴(kuò)大搜索范圍的同時(shí)，避免陷入局部最優(yōu)。步驟4-(4)的禁忌表交換策略具體操作如下：

①計(jì)算本次迭代中的最優(yōu)解fk；

②在禁忌表中任意選出某個(gè)物品序號(hào)i，再選出一個(gè)非禁忌表中的物品序號(hào)j；

(6)信息素的混沌更新策略?；煦缡欠蔷€性確定系統(tǒng)產(chǎn)生的外在復(fù)雜表現(xiàn)，具有對(duì)初始條件的敏感性、偽隨機(jī)性、遍歷性、混合性、規(guī)律性和不可預(yù)測(cè)性等優(yōu)點(diǎn)[15]。利用混沌變量進(jìn)行優(yōu)化能夠跳出局部最優(yōu)，但在尋優(yōu)過程中進(jìn)行盲目搜索的次數(shù)較多，耗時(shí)長(zhǎng)。鑒于此，本文引入混沌更新策略在較大范圍內(nèi)充分發(fā)揮混沌更新的全局搜索優(yōu)勢(shì)，增強(qiáng)種群多樣性。同時(shí)利用信息素正反饋思想指導(dǎo)混沌搜索的區(qū)域和方向，克服混沌搜索的盲目性。

步驟8的具體步驟為：當(dāng)判斷出種群出現(xiàn)局部收斂時(shí)，將所選物品按適應(yīng)值升序排列，并將物品上的信息素引入混沌更新策略，改變種群的搜索方向。本文將Logistic映射公式定義為

(7)

3 算例及結(jié)果分析

為驗(yàn)證算法的有效性，本文采用Matlab編碼實(shí)現(xiàn)算法程序，并將本文改進(jìn)的遺傳蟻群混合算法與文獻(xiàn)[10]和文獻(xiàn)[12]中的遺傳蟻群混合算法進(jìn)行了對(duì)比。測(cè)試算例來源于http://elib.zib.de/pub/Packages/mp-testdata/ip/sac94-suite/index.html中規(guī)模為10～28的多維背包問題。其中，螞蟻數(shù)size=200，最大迭代次數(shù)Gmax=200，交叉概率取Pc=0.8，變異概率取Pm=0.15，信息素啟發(fā)因子α=2，期望啟發(fā)式因子β=1，信息素量揮發(fā)系數(shù)ρ=0.7。

現(xiàn)將3種算法(算法1是本文的改進(jìn)算法，算法2采用文獻(xiàn)[10]的混合算法，算法3采用文獻(xiàn)[12]的混合算法)在此問題上各運(yùn)行50次的解性能進(jìn)行比較，結(jié)果如表1、表2和圖1所示。

表1 3種算法最優(yōu)解對(duì)比結(jié)果

表2 3種算法50次達(dá)到最優(yōu)解所運(yùn)行迭代次數(shù)

由表1可知，3種算法均可以在有限的迭代次數(shù)中達(dá)到最優(yōu)，其中算法1的平均波動(dòng)率最小(平均波動(dòng)率=(最優(yōu)值-平均最優(yōu)值)/最優(yōu)值)，且算法1求得的平均最優(yōu)值比算法2、算法3更接近最優(yōu)值，說明算法1在解決多維背包問題時(shí)尋優(yōu)能力有所提高。從表2看，算法1在50次尋優(yōu)過程中達(dá)到最優(yōu)解時(shí)的最短、最長(zhǎng)、平均迭代次數(shù)均為最小，表明該算法的收斂性能要優(yōu)于其它兩種算法。由圖1可看出算法1在40多代時(shí)已趨于收斂，而算法2和算法3分別在100多代和60多代時(shí)才達(dá)到最優(yōu)，由此可見本文算法的收斂性和搜索能力明顯有所提高。

圖1 3種算法進(jìn)化曲線圖

4 結(jié)束語

本文設(shè)計(jì)了一種改進(jìn)的遺傳蟻群混合算法，對(duì)傳統(tǒng)遺傳算法的交叉和變異算子進(jìn)行了改進(jìn)，以提高尋優(yōu)性能。并在蟻群算法的運(yùn)行過程中引入概率和為u的輪盤賭方式降低算法復(fù)雜度，采用禁忌表交換策略以及信息素的混沌更新策略避免陷入局部最優(yōu)，增強(qiáng)了種群多樣性。通過對(duì)測(cè)試用例的仿真，證明本文提出的改進(jìn)混合算法在求解多維背包問題時(shí)，算法的尋優(yōu)性能、求解精度、收斂性得到了大幅改善。目前，本文只研究了待選物品數(shù)較少的情況，今后將對(duì)大規(guī)模及其他背包問題進(jìn)行深入研究。