融合差異進化的混合算法求解多選擇背包問題*

蔣 妍 潘大志

（西華師范大學數學與信息學院 南充 637009）

1 引言

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

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

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

為進一步提高求解MCKP問題的精度和效率，本文提出了一種融合差異進化的混合算法求解MCKP問題。算法將個體分為三個階級，每個階級對應特定的進化方法；同時設計了隨機貪心修復策略，用于解的修復和優化。

2 多選擇背包問題

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

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

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

3 融合差異進化的混合算法

3.1 正整數編碼

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

3.2 階級劃分

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

算法1：階級劃分算子

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

步驟2：將所有個體按照適應度值進行降序排列，并將第k個個體對應的排名記為ind exk；

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

3.3 個體差異進化

3.3.1 底層階級

當個體處于底層時，往往很難有大的提升，反而可能往錯誤的方向移動。因此應該放棄當前位置，向全局最優學習或重新初始化位置。基于此，對于底層階級的個體，設置了重啟策略，按照物品的類別依次進行，促使其往好的方向移動。重啟算子的具體操作如下：

算法2：重啟算子

步驟1：生成一個隨機數rand，并與概率參數P進行比較；

步驟2：若rand＜P則學習全局最優個體，若rand≥P則重新生成初始個體，即：

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

3.3.2 中層階級

對于中層階級的個體而言，可以從個體和社會的經驗中進行學習。基于此，針對中層階級的個體，本文融合了遺傳算法和魚群算法的思想，設計了自我學習和社會學習兩個算子。

1）自我學習

自我學習融入了遺傳算法的思想，將當前個體與歷史最優進行交叉，通過向自身經驗學習來進行更新。自我學習算子的具體操作如下。

算法3：自我學習算子

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

步驟2：用歷史最優個體中k1到k2維的基因段替換當前個體中k1到k2維的基因段。得到新個體

2）社會學習

社會學習融入了人工魚群算法的思想，先給個體設定一個可視范圍，并計算出可視范圍內所有個體的重心和最優值，再通過交叉的方式分別向重心和局部最優個體學習，實現更新。以第k個個體為例，社會學習算子的具體操作如下。

算法4：社會學習算子

步驟1：設置個體的可視范圍vision；

3.3.3 高層階級

當個體處于高層時，若變動太大可能會導致直接越過最優值，因此局部搜索更有利。基于此，針對高層階級，本文設置了擾動算子，進行小范圍搜索。擾動算子的具體操作如下。

算法5：擾動算子

3.4 精英庫

鑒于優個體周圍出現優個體的可能性很大，因此本文設置了一個精英庫，用于存儲第3.3.3節中未被選中的個體。在各個子群均更新完畢后，依次將精英庫中個體與種群的最差個體進行比較，擇優放入種群中。

3.5 隨機貪心修復策略

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

算法6：隨機貪心修復算子

步驟1：隨機選取一個維度j，記錄對應的

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

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

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

操作中每個維度最多被選取一次，不會出現重復選取的情況。

3.6 算法步驟

融合差異進化的混合算法的具體步驟如下。

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

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

步驟3：生成子群。按照算法1，進行階級劃分；

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

步驟5：解的修復。按照算法6，對不可行解進行修復；

步驟6：貪心裝載。依次將精英庫中的個體與種群的最差個體進行比較，擇優納入種群；

步驟7：重復步驟3～步驟6，直到達到最大迭代次數NI。

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

圖1 算法流程圖

4 仿真結果分析

4.1 測試算例

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

算例的理論最優值為34。

4.2 參數設定

4.2.1 通用參數

種群規模N P越大，算法得到最優值的可能性越大，但當NP達到一定值時，算法將停滯，反而會浪費很多的運算時間。在本文中，統一設定NP=40。

4.2.2 智能算法非通用參數

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

表1 智能算法非通用參數設置

4.3 算法對比

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

由表2分析可得：

表2 智能進化算法求解典型測試算例性能分析

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

2）當NI=30、NI=20、NI=10時，隨著迭代次數的減小，算法IDEHA依舊維持著最優解和100%的準確率，而算法DWPA出現了不能完全求得最優解的情況，算法BSGA和PSO的平均值和準確率也進一步變差，表明算法IDEHA的收斂速度相較之下更快、穩定性更強。

總體看來，算法IDEHA無論是在尋優能力還是穩定性、收斂速度，都優于其他算法。

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

圖2 測試算例優化求解收斂圖

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

綜合以上的仿真實驗結果、迭代圖及分析，可得DEAIEF算法尋優能力強、求解精度高、穩定性和魯棒性強、收斂速度快，適合求解MCKP問題。

5 結語

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