改進的遺傳蟻群混合算法求解多維0/1背包問題

劉夢佳，向鳳紅，郭 寧，毛劍琳

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

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

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

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

1 多維背包問題

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

(1)

2 改進遺傳蟻群混合算法求解

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

2.1 算法流程

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

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

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

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

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

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

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

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

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

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

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

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

②每只螞蟻獨立尋得一個解，令臨時向量temp(j)=Pj(1≤j≤n)。螞蟻k按物品被選擇的概率以概率之和為u的輪盤賭方法選擇下一個物品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)物品序號加入到tabuk中，修改禁忌表指針。

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

(5)對局部信息素進行更新；

(6)若k

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

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

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

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

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

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

(2)

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

信息素量

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

(3)

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

(4)

其中

(5)

信息素強度

(6)

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

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

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

②在禁忌表中任意選出某個物品序號i，再選出一個非禁忌表中的物品序號j；

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

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

(7)

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

為驗證算法的有效性，本文采用Matlab編碼實現(xiàn)算法程序，并將本文改進的遺傳蟻群混合算法與文獻[10]和文獻[12]中的遺傳蟻群混合算法進行了對比。測試算例來源于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是本文的改進算法，算法2采用文獻[10]的混合算法，算法3采用文獻[12]的混合算法)在此問題上各運行50次的解性能進行比較，結(jié)果如表1、表2和圖1所示。

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

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

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

圖1 3種算法進化曲線圖

4 結(jié)束語

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