蔣 妍 潘大志

（西華師范大學(xué)數(shù)學(xué)與信息學(xué)院 南充 637009）

1 引言

多選擇背包問題（Multiple-choice knapsack problem，MCKP）是運(yùn)籌學(xué)中的一個(gè)經(jīng)典的NP-hard問題，由于問題自身具有配套屬性，被廣泛地應(yīng)用于對(duì)組件串聯(lián)選取［1］、資本預(yù)算和菜單規(guī)劃［2］、廣義分配問題［3］等實(shí)際問題中，對(duì)該問題求解方法的研究無論在理論上還是實(shí)踐中都具有一定的意義。

目前，求解MCKP的算法主要分為兩類：一類是精確算法，主要包括動(dòng)態(tài)規(guī)劃、分支定界等，該類算法可以求出問題的精確解，但隨著問題規(guī)模和復(fù)雜度的增加，問題的求解難度和時(shí)間復(fù)雜度也會(huì)呈指數(shù)增長。另一類則是啟發(fā)式算法，例如狼群算法、蜂群算法、蝙蝠算法、粒子群算法、差異演化算法［4～8］等，該類算法的求解速度快，但往往僅能求出問題的次優(yōu)解。

近年來，國內(nèi)外學(xué)者在求解MCKP問題時(shí)，采用了很多的創(chuàng)新和改進(jìn)方式［4～16］來提升解的質(zhì)量。例如，Bednarczuk［4］借助于閉式公式，提出了一種近似解的方法，其精度與貪婪算法和精確算法的精度相當(dāng)，并且可以找到原始背包問題的相應(yīng)近似解；Adouani［5］等提出將可變鄰域搜索（VNS）與整數(shù)規(guī)劃（IP）有效地結(jié)合起來，解決了帶設(shè)置的多項(xiàng)選擇背包問題；Balashov［6］提出了一種求解該問題的分枝定界算法，以及一種提高算法性能的上估計(jì)計(jì)算和優(yōu)化方案；楊洋［7］基于凸帕累托算法（CPA），提出一種能夠快速求解線性支配子集的改進(jìn)帕累托算法，大大提升了求解的速度和精度；譚陽［8］構(gòu)建了待選物品價(jià)值權(quán)重因子，平衡了極值效應(yīng)對(duì)算法尋優(yōu)過程的影響，同時(shí)采用新的修復(fù)機(jī)制，進(jìn)而有效地優(yōu)化MMKP問題；董亞科［9］等設(shè)計(jì)了基于離散空間的狼群算法，給狼群設(shè)計(jì)了新的游走、奔襲、圍捕方式，進(jìn)而提高了算法的求解精度；吳迪［10］等通過設(shè)置兩個(gè)自適應(yīng)變化的雄蜂群和雌蜂群，差分進(jìn)化，有效地平衡了算法的全局搜索與局部搜索，進(jìn)而避免算法陷入局部最優(yōu)；李枝勇［11］等提出了一種改進(jìn)的蝙蝠算法，引入了慣性因子，并重新定義了蝙蝠的速度的更新方程，有效地將蝙蝠算法應(yīng)用于求解多選擇背包問題，拓展了蝙蝠算法的應(yīng)用領(lǐng)域；陳娟［12］等設(shè)計(jì)了一種離散粒子群優(yōu)化算法對(duì)問題進(jìn)行求解，通過仿真試驗(yàn)證明了算法的可行性和有效性；王研［13］等針對(duì)多選擇背包問題的離散性設(shè)計(jì)了離散的差異演化算法，有效的解決了問題等。

為進(jìn)一步提高求解MCKP問題的精度和效率，本文提出了一種融合差異進(jìn)化的混合算法求解MCKP問題。算法將個(gè)體分為三個(gè)階級(jí)，每個(gè)階級(jí)對(duì)應(yīng)特定的進(jìn)化方法；同時(shí)設(shè)計(jì)了隨機(jī)貪心修復(fù)策略，用于解的修復(fù)和優(yōu)化。

2 多選擇背包問題

有一個(gè)最大載重量為W的背包和一批具有物資消耗和重量的物品，現(xiàn)將物品分為m類，相互排斥，每一類含有ni(i=1，2，…，m)個(gè)不同的物品。多選擇問題可描述為在滿足背包載重的情況下，從每一類中選出一個(gè)物品，使得消耗之和最小。多選擇背包問題作為背包問題的一個(gè)推廣，與之不同之處在于，多選擇背包增加了一個(gè)約束條件，并且將極大值問題變?yōu)榱藰O小值問題。多選擇背包問題用數(shù)學(xué)模型描述為

式中，f(X)為所有選入背包的物品的總消耗；pij為第i類中第j個(gè)物品的物資消耗量；wij為第i類中第j個(gè)物品的重量；X={x11，x12，…，x1n1，x21，…，xm1，…，xmnm}為決策變量，其中xij=1時(shí)表示第i類中第j個(gè)物品被選擇，xij=0時(shí)表示不被選擇。

目標(biāo)函數(shù)為總消耗量最??；約束條件第一個(gè)為總重量不得超過背包容量；第二個(gè)為每一類選且只選一個(gè)物品；第三個(gè)為決策變量必須為0，1變量。

3 融合差異進(jìn)化的混合算法

3.1 正整數(shù)編碼

結(jié)合多選擇背包獨(dú)有的將物品進(jìn)行分類的特點(diǎn)，本文摒棄了背包問題常用的二進(jìn)制編碼方式，采用了更為適合的正整數(shù)編碼。以物品的類別數(shù)m作為解的維度，每一維以[1，ni](i=1，2，…，m)作為范圍，選取任意正整數(shù)，作為該類的選取方案。用數(shù)學(xué)公式表示為

3.2 階級(jí)劃分

在算法中，依照適應(yīng)度值，按一定的比例將種群分為三個(gè)階級(jí)，依次定義為底層階級(jí)、中層階級(jí)和高層階級(jí)三類。階級(jí)劃分算子的具體步驟如下。

算法1：階級(jí)劃分算子

步驟1：設(shè)置三個(gè)空集合L、M、U，分別記錄底層階級(jí)、中層階級(jí)和高層階級(jí)的個(gè)體；

步驟2：將所有個(gè)體按照適應(yīng)度值進(jìn)行降序排列，并將第k個(gè)個(gè)體對(duì)應(yīng)的排名記為ind exk；

步驟3：若indexk≤m1*N P，則第k個(gè)個(gè)體被放入集合L中；若m1*N P＜indexk≤m2*NP，則放入集合M中；若ind exk＞m2*N P，則放入集合U中。

3.3 個(gè)體差異進(jìn)化

3.3.1 底層階級(jí)

當(dāng)個(gè)體處于底層時(shí)，往往很難有大的提升，反而可能往錯(cuò)誤的方向移動(dòng)。因此應(yīng)該放棄當(dāng)前位置，向全局最優(yōu)學(xué)習(xí)或重新初始化位置?；诖?，對(duì)于底層階級(jí)的個(gè)體，設(shè)置了重啟策略，按照物品的類別依次進(jìn)行，促使其往好的方向移動(dòng)。重啟算子的具體操作如下：

算法2：重啟算子

步驟1：生成一個(gè)隨機(jī)數(shù)rand，并與概率參數(shù)P進(jìn)行比較；

步驟2：若rand＜P則學(xué)習(xí)全局最優(yōu)個(gè)體，若rand≥P則重新生成初始個(gè)體，即：

步驟3：重復(fù)步驟1～2，直至每一維都更新完畢。

3.3.2 中層階級(jí)

對(duì)于中層階級(jí)的個(gè)體而言，可以從個(gè)體和社會(huì)的經(jīng)驗(yàn)中進(jìn)行學(xué)習(xí)。基于此，針對(duì)中層階級(jí)的個(gè)體，本文融合了遺傳算法和魚群算法的思想，設(shè)計(jì)了自我學(xué)習(xí)和社會(huì)學(xué)習(xí)兩個(gè)算子。

1）自我學(xué)習(xí)

自我學(xué)習(xí)融入了遺傳算法的思想，將當(dāng)前個(gè)體與歷史最優(yōu)進(jìn)行交叉，通過向自身經(jīng)驗(yàn)學(xué)習(xí)來進(jìn)行更新。自我學(xué)習(xí)算子的具體操作如下。

算法3：自我學(xué)習(xí)算子

步驟1：在[1，m]間選取兩個(gè)隨機(jī)整數(shù)k1，k2(k1≠k2)，確定為交叉位置；

步驟2：用歷史最優(yōu)個(gè)體中k1到k2維的基因段替換當(dāng)前個(gè)體中k1到k2維的基因段。得到新個(gè)體

2）社會(huì)學(xué)習(xí)

社會(huì)學(xué)習(xí)融入了人工魚群算法的思想，先給個(gè)體設(shè)定一個(gè)可視范圍，并計(jì)算出可視范圍內(nèi)所有個(gè)體的重心和最優(yōu)值，再通過交叉的方式分別向重心和局部最優(yōu)個(gè)體學(xué)習(xí)，實(shí)現(xiàn)更新。以第k個(gè)個(gè)體為例，社會(huì)學(xué)習(xí)算子的具體操作如下。

算法4：社會(huì)學(xué)習(xí)算子

步驟1：設(shè)置個(gè)體的可視范圍vision；

3.3.3 高層階級(jí)

當(dāng)個(gè)體處于高層時(shí)，若變動(dòng)太大可能會(huì)導(dǎo)致直接越過最優(yōu)值，因此局部搜索更有利。基于此，針對(duì)高層階級(jí)，本文設(shè)置了擾動(dòng)算子，進(jìn)行小范圍搜索。擾動(dòng)算子的具體操作如下。

算法5：擾動(dòng)算子

3.4 精英庫

鑒于優(yōu)個(gè)體周圍出現(xiàn)優(yōu)個(gè)體的可能性很大，因此本文設(shè)置了一個(gè)精英庫，用于存儲(chǔ)第3.3.3節(jié)中未被選中的個(gè)體。在各個(gè)子群均更新完畢后，依次將精英庫中個(gè)體與種群的最差個(gè)體進(jìn)行比較，擇優(yōu)放入種群中。

3.5 隨機(jī)貪心修復(fù)策略

對(duì)于不可行解，無論其總價(jià)值有多大，都是無用的，還會(huì)讓搜索停滯不前。因此，對(duì)不可行解的修復(fù)，是求解多選擇背包問題的關(guān)鍵。鑒于多選擇背包每類選且只選一個(gè)物品的特殊約束，本文設(shè)計(jì)了隨機(jī)貪心修復(fù)策略，隨機(jī)保證了修復(fù)后解的多樣性，貪心保證了修復(fù)后解的質(zhì)量。策略按照維度依次修復(fù)，以第k個(gè)個(gè)體為例，算子的具體操作如下：

算法6：隨機(jī)貪心修復(fù)算子

步驟1：隨機(jī)選取一個(gè)維度j，記錄對(duì)應(yīng)的

步驟2：找出j類中所有重量比小的物品，放入集合A中；

步驟3：若A不為空集，則進(jìn)行貪心操作，找出A中物資消耗最小的物品，替換；反之，則重復(fù)步驟1～2；

步驟4：檢查替換后的新個(gè)體的總重量是否滿足背包載重要求，若滿足則修復(fù)完成，若不滿足則重復(fù)步驟1～3直至重量滿足要求為止。

操作中每個(gè)維度最多被選取一次，不會(huì)出現(xiàn)重復(fù)選取的情況。

3.6 算法步驟

融合差異進(jìn)化的混合算法的具體步驟如下。

步驟1：參數(shù)初始化。設(shè)定最大迭代次數(shù)N I，種群規(guī)模N P，可視范圍vision；

步驟2：種群初始化。按照3.1所提及的正整數(shù)編碼方式，生成初始種群；

步驟3：生成子群。按照算法1，進(jìn)行階級(jí)劃分；

步驟4：個(gè)體差異進(jìn)化。對(duì)于不同的階級(jí)，分別按照算法2～5進(jìn)行更新，并更新精英庫；

步驟5：解的修復(fù)。按照算法6，對(duì)不可行解進(jìn)行修復(fù)；

步驟6：貪心裝載。依次將精英庫中的個(gè)體與種群的最差個(gè)體進(jìn)行比較，擇優(yōu)納入種群；

步驟7：重復(fù)步驟3～步驟6，直到達(dá)到最大迭代次數(shù)NI。

算法的流程圖如圖1所示。

圖1 算法流程圖

4 仿真結(jié)果分析

4.1 測試算例

為測試融合差異進(jìn)化的混合算法求解多選擇背包問題的有效性，本文采用文獻(xiàn)［4］提出的一個(gè)含有八類物品的經(jīng)典多選擇背包實(shí)例來進(jìn)行仿真實(shí)驗(yàn)，問題實(shí)例具體如下。

算例的理論最優(yōu)值為34。

4.2 參數(shù)設(shè)定

4.2.1 通用參數(shù)

種群規(guī)模N P越大，算法得到最優(yōu)值的可能性越大，但當(dāng)NP達(dá)到一定值時(shí)，算法將停滯，反而會(huì)浪費(fèi)很多的運(yùn)算時(shí)間。在本文中，統(tǒng)一設(shè)定NP=40。

4.2.2 智能算法非通用參數(shù)

為驗(yàn)證融合差異進(jìn)化的混合算法的性能，本文選取了近年來改進(jìn)效果較好的兩個(gè)算法：離散狼群算法［4］（DWPA）、改進(jìn)的蜂群遺傳算法［5］（BSGA）以及一個(gè)基本算法：基本粒子群算法（PSO）與本文算法進(jìn)行比較，每個(gè)算法的非通用參數(shù)設(shè)置如表1。

表1 智能算法非通用參數(shù)設(shè)置

4.3 算法對(duì)比

為融合差異進(jìn)化的混合算法的性能，本文運(yùn)用選取的算例對(duì)IDEHA進(jìn)行測試，并將結(jié)果上述的DWPA、BSGA以及PSO進(jìn)行比較。算法均在處理器為Intel（R）Core（TM）i5-6200U CPU@2.30GHz 2.40 GHz，內(nèi)存為8GB，操作系統(tǒng)Windows 10的計(jì)算機(jī)上使用Matlab 2016b進(jìn)行仿真實(shí)驗(yàn)。實(shí)驗(yàn)中每個(gè)算法均獨(dú)立運(yùn)行100次取得平均值，實(shí)驗(yàn)結(jié)果如表2及圖2所示。

由表2分析可得：

表2 智能進(jìn)化算法求解典型測試算例性能分析

1）當(dāng)NI=100、NI=50時(shí)，迭代次數(shù)較大，算法IDEHA和DWPA能夠求得完全最優(yōu)解，但算法BSGA和PSO不能，說明算法BSGA和PSO存在陷入局部最優(yōu)的情況。表明算法IDEHA和DWPA的尋優(yōu)能力相較之下更強(qiáng)。

2）當(dāng)NI=30、NI=20、NI=10時(shí)，隨著迭代次數(shù)的減小，算法IDEHA依舊維持著最優(yōu)解和100%的準(zhǔn)確率，而算法DWPA出現(xiàn)了不能完全求得最優(yōu)解的情況，算法BSGA和PSO的平均值和準(zhǔn)確率也進(jìn)一步變差，表明算法IDEHA的收斂速度相較之下更快、穩(wěn)定性更強(qiáng)。

總體看來，算法IDEHA無論是在尋優(yōu)能力還是穩(wěn)定性、收斂速度，都優(yōu)于其他算法。

下面展示算法的迭代對(duì)比圖，如圖2所示。

圖2 測試算例優(yōu)化求解收斂圖

由圖2分析可得：算法IDEHA的迭代起始點(diǎn)普遍低于其他算法，曲線的下降幅度更明顯，最早到達(dá)最低點(diǎn)，表明算法的收斂行強(qiáng)，收斂速度快；其次，算法IDEHA的迭代終止點(diǎn)普遍低于其他算法，表明算法的尋優(yōu)能力強(qiáng)。

綜合以上的仿真實(shí)驗(yàn)結(jié)果、迭代圖及分析，可得DEAIEF算法尋優(yōu)能力強(qiáng)、求解精度高、穩(wěn)定性和魯棒性強(qiáng)、收斂速度快，適合求解MCKP問題。

5 結(jié)語

本文提出了求解多選擇背包問題的融合差異進(jìn)化的混合算法，算法通過差分進(jìn)化提高算法的動(dòng)態(tài)適應(yīng)性；提出了隨機(jī)貪心修復(fù)策略來修復(fù)和優(yōu)化解；引入精英庫加快算法的收斂速度。并通過經(jīng)典的多選擇背包算例進(jìn)行仿真實(shí)驗(yàn)，對(duì)比了近期提出的其他優(yōu)秀的啟發(fā)式算法（離散狼群算法、改進(jìn)的蜂群遺傳算法）以及基本算法（基本粒子群算法），實(shí)驗(yàn)表明本文算法具有較好的尋優(yōu)能力、穩(wěn)定性、收斂性，是一種更為有效的求解多選擇背包問題的算法。