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

余典　吳勇　余山

摘 要：針對傳統啟發式算法難以平衡求解收斂次數與求解精度問題，通過充分分析GA和ACO兩種算法的優缺點，設計了一種改進的遺傳蟻群算法。將算法分為上下兩步，分別以GA和ACO為主。在GA中引入信息素更新機制連接上下兩部分算法;在ACO中引入遺傳變異操作盡可能擴大解的范圍。同時結合兩種算法各自解的繼承方式，采用合適的方法分別處理這兩部分產生的不可行解。獲得解后，通過引入交換鄰域的爬山法思想進一步嘗試優化解。最終在保證求解精度的前提下，減少求解所需的迭代次數。實驗結果表明，在需要保證求解精度的前提下，相比傳統GA，該方法的求解效率提高了一個量級。

關鍵詞：0/1多維背包;遺傳蟻群混合算法;交換鄰域爬山算法

DOI：10. 11907/rjdk. 191598

中圖分類號：TP301 ? 文獻標識碼：A??????????????? 文章編號：1672-7800（2020）003-0087-04

Modified Genetic Ant Colony Hybrid Algorithm for Solving

Multidimensional 0-1 Knapsack Problem

YU Dian1，WU Yong2，YU Shan2

（1. China Academy of Telecommunication Technology，Beijing 100083，China;

2. Semiconductor Manufacturing International Corporation （Beijing），Beijing 100176，China）

Abstract：Aiming at the problem that traditional heuristic algorithm is difficult to balance the solution of convergence times and solution precision， we design an modified genetic and ant colony hybrid algorithm by analyzing the advantages and disadvantages between GA and ACO algorithms. The algorithm is divided into two steps which are based on GA and ACO respectively. The pheromone update method is introduced in the step based on GA to connect with the next step. Meanwhile， mutation operation and crossover operation are introduced in the step based on ACO for getting more solutions. Besides， the appropriate method is used to deal with the infeasible solutions generated in these two steps. Finally， in order to optimize the solution further， hill-climbing algorithm of exchange neighborhood search is introduced after the solution is obtained. Finally， under the premise of ensuring the accuracy of the solution， the number of iterations required for the solution is shortened. The experimental results show that the efficiency of the proposed method is increased by an order of magnitude compared with the traditional GA under the premise of ensuring the accuracy of the solution.

Key Words：multidimensional knapsack problem; genetic ant colony hybrid algorithm; hill-climbing algorithm of exchange neighborhood search

0 引言

多維背包問題（Multidimensional Knapsack Problem， MKP）是著名的整數規劃問題之一，屬于NP-hard問題[1]。它的實際應用場景很多，如工廠中的資源分配形式、數據加密、投資組合、機臺調度等。近幾十年研究出各種各樣的解決方法，其中精確算法有分支限界法、動態規劃法等，近似算法有貪婪方法、蟻群算法等[2]。近幾年對該問題的研究主要集中于以遺傳、蟻群算法為代表的元啟發式算法[3]。

遺傳算法[4]（Genetic Algorithm，GA）由美國學者Holand于1975年首先提出，是一種模擬達爾文遺傳選擇和自然淘汰的生物進化論計算模型。它通過模擬自然界的遺傳、變異以及適者生存進化機制獲取所求問題的解。這種算法優點是簡單、通用、魯棒性強，適用并行分布處理，應用范圍廣。它是一種隨機的、以交叉操作為核心的全局多點搜索算法，在運算前期能很快達到最優解的90%左右[5]。但是在之后，由于交叉編譯操作獲得的解會大量重復于之前獲得的解集，導致要花費很長時間才能對解的質量作進一步優化。蟻群算法（Ant Colony Optimization，ACO）是Dorigo[6]于1991年提出的一種基于螞蟻種群的新型優化算法，使用單純的蟻群算法求解背包問題主要通過不斷重復放置螞蟻，依據信息素尋找一串可行的解集。更新信息素，通過信息素的不斷積累逐漸收斂到最優解。由于ACO算法中，前面的解通過更新信息素的方式能對后面的解產生正反饋，因此使ACO的收斂速度加快，避免了類似GA后期大量的重復搜索過程。但是ACO存在以下幾個問題：①前期信息素濃度較低且分布平均時，整體算法收斂較慢;②算法容易出現停滯現象，也就是當搜索到一定程度后，少數幾個節點上積累的信息素濃度足夠大，使得尋找到的解都集中在這幾個節點上，不能對解空間進一步搜索，最終導致算法過早收斂在一個較優的解上。

MKP發展至今，相關問題有多種不同的表現形式，王熙照、賀毅朝[7]對此作了比較系統的歸納。0/1背包問題是其中最基本的背包問題，一直以來都有不少學者對其進行研究。

近年來，對類似MKP這種NP-hard類型問題的求解方法主要分為兩類：①尋找新的啟發式算法求解此類問題，如劉雪靜、賀毅朝[8]等采用細菌覓食算法求解0/1背包問題。這種算法具有局部搜索、并行搜索能力強等優點，但這種算法在每輪循環中需要經過趨化、遷移和復制3個步驟，而其中趨化又包含翻轉和游動等，會造成算法需要調整的變量數量多、不易控制等問題。高思奇、邢玉軒等[9]提出通過改進蛙跳算法求解背包問題，這種算法具有比較好的求解效率，但就原始蛙跳算法而言，算法容易收斂到局部最優解。此外，近幾年出現了人工魚群算法（AFSA）[10]和聲搜索算法（HS）[11]、螢火蟲算法[12]、二進制蝙蝠算法（BBA）[13]等研究熱點;②通過優化或混合原有算法求解問題。如趙學武， 劉向嬌等提出一種改進的遺傳算法求解背包問題。這種改進算法通過每輪獲得的解集適應值，自動調整變異概率。通過算法調整，保證每次裝入的物體單位質量價值大以加快算法收斂速度。這種改進算法減少了收斂到最終結果的迭代輪次，加快了算法的收斂速度，但是犧牲了解的多樣性，且沒有很好地解決后期無用搜索量大的問題。羅星星等在原有遺傳算法基礎上引入了3種新的變異方式：散播變異、移位變異和插入變異，豐富了解的種類，但并沒有很好地解決在算法后期收斂慢的問題。劉夢佳和王娜等在主要思路上都采用了遺傳蟻群混合算法，通過每輪迭代將解集分為兩類：一類適應度較高的用于遺傳算法，其余的用于蟻群算法，混合解集按照適應度獲取下一階段的解集，這種混合算法能獲得優于普通GA的收斂速度和優于普通ACO的尋解范圍。但是每輪用于蟻群算法的那些解都是重新構建的，實際上浪費了計算資源。另外，由于設定用于GA的解數量是固定的，因而這種算法會有類似于普通GA或普通ACO的缺陷。除此之外，劉夢佳等通過綜合遺傳算法和模擬退火算法，提出了改進的Memetic算法用于求解多維0/1背包問題。

無論是新的元啟發式算法還是在現有算法基礎上進行改進，都是為了更快地尋找到更優的解。

針對傳統啟發式算法難以平衡求解收斂次數與求解精度問題，本文通過分析GA和ACO兩種算法之間的優缺點，設計了一種改進的遺傳蟻群算法，將整個算法分為上下兩步，分別以GA和ACO為主。在GA中引入信息素更新機制連接上下兩部分算法;在ACO中引入遺傳變異操作盡可能地擴大解的范圍，同時采用合適的方法處理這兩部分中產生的不可行解。在最后獲得解后，通過引入爬山法思想進一步嘗試優化解，最終在保證求解精度的前提下減少求解所需的迭代次數。實驗結果表明，在保證求解精度的前提下，相比傳統GA，該方法的求解效率提高了一個量級。

1 0/1多維背包問題數學模型

一般將0/1MKP問題構建數學模型如下：

其中：[Np]表示背包數目，No表示物體數目，Pi（i=1，2，…Np）表示物體i的價格，Cj（j=1，2…Np）表示每個背包的最大資源量，Wij（i=1，2，…No， j=1，2…Np）表示每個物體i對背包j的資源占用。

2 改進的混合遺傳蟻群算法

2.1 算法設計思想

（1）考慮到遺傳算法在運行前期求解效率高，而且比蟻群算法更容易生成一組解，所以在混合算法前期采用遺傳算法以快速獲得較優解;同時由于蟻群算法的解集生成并不直接依賴于上一組解的解值，而是前面積累的信息素，所以在遺傳算法中引入信息素更新機制，讓遺傳算法的解能影響到后面蟻群算法求解，加快算法收斂速度。

（2）蟻群算法在信息素濃度高時，由于正反饋效應及收斂速度快的特點，可在后期采用蟻群算法加快收斂速度。為防止最后收斂到局部最優解，引入變異交叉操作增大尋解范圍，通過對普通遺傳算法的結果分析能較容易地找到這兩步的切換節點。

2.2 算法流程

步驟一：變量初始化。設置最大迭代次數N，第一步的循環次數N1，變異概率Pm ，交叉概率Pc，解集大小size，初始信息素濃度矩陣ph（Np·1），每條路線信息素更新總量Q，信息素揮發因子ρ，計算能見度矩陣Me。

步驟二：獲取初始解集。通過隨機生成0或1得到一組（NO·size）的矩陣Mg作為初始解集，其中的每一列就是一個初始解。

步驟三：進入算法第一步（GA為主）。①通過交叉操作獲得一組交叉矩陣Mc;②通過變異操作獲得一組變異矩陣Mm;③將Mg、Mc、Mm組合為新矩陣Mg;④獲得Mg解集對應的價格序列Ap;⑤對Mg中超重的解集對應的價格進行懲罰;⑥對解集中滿足限制條件的解，按照蟻周模型更新信息素;⑦按照輪盤賭思想得到下一組解集Mg;⑧當循環次數≤N1時，返回步驟三①。

步驟四：進入算法第二步（ACO為主）：

（1）參數初始化：清空解集Mg，啟發因子α，能見度因子β。

（2）將size只螞蟻盡量分散放置在各個物體上。

（3）計算每個物體被選擇的概率。

（4）依次為每只螞蟻s生成一組解集：①設置指示標志a=0，該螞蟻當前對資源占用的總量為Ac;②通過輪盤賭選擇該螞蟻下一個可能選擇的物體b;③將b占用的資源加到Ac上，如果此時仍然滿足下式：[？j=1，2，？NP，AcjCj]，則設置Mc（s，b）為1（代表選上），否則設置為-1（代表不可選）;④如果a≤No，就返回步驟四之（2）。

（5）對目前獲得的解集Mg進行變異操作，并對不滿足約束條件的解進行修正，獲得Mam。

（6）對目前獲得的解集Mg進行交叉操作，并對不滿足約束條件的解進行修正，獲得Mac。

（7）按照蟻周系統對物體上的信息素進行更新。

（8）保留當代最優解。

（9）如果迭代次數小于等于N，則轉到步驟四之（2）;否則輸出最優解并結束程序。

步驟五：對得到的結果利用交換鄰域的爬山法進行優化。

2.3 算法策略

步驟一中，計算能見度矩陣Me。這里的能見度矩陣用于在ACO算法中計算不同物體的選擇概率，見步驟四之（3）。具體算法如下：

其中：ph是No×1維矩陣，表示各物體上的信息素濃度;Me是No×1維矩陣，選擇概率[Pkij]表示第k只螞蟻在物體i上選擇物體j的概率。

由式（2）及MKP可知，價格越高消耗資源越少的物品更應該被選中。對于KMP，本文采用按背包容量比值進行加權的價格/占重比確定每個物體的能見度，實現公式見式（3）和式（4）。

其中：[Me（i）]表示物體i的能見度，[percj]表示背包j的占比。

交叉操作（步驟三之①，步驟四之（6））中，循環size次，每次生成一個隨機數random∈[0，1]。當random

步驟三之（5）通過將不可行（超背包容量）的解的價格設置為當前解集的最小價格對其進行懲罰。這里不采用人為修復為可行解方法，在GA中該輪解集會繼承到下一輪中，如果采用修改為可行解的方法實際上會降低后續解的多樣性。步驟四之（6）采用修正的方法在于ACO中當前輪的解集不能繼承到下一輪，而信息素的更新只會采用可行解，所以這里采用修復方法以增加求解速率。

本文采用依次刪除不可行解中可見度最小的元素直到滿足約束條件的方法對不可行解進行修復。

根據信息素更新策略不同，一般將蟻群模型分為蟻周模型（antcycle system）、蟻量系統（ant-quantity system）、蟻密系統（ant-density system），這里采用性能最好的蟻周模型。蟻周模型更新信息素方式如下：

其中，[phki（t）]代表在第t輪第k只螞蟻尋找解時，物體i上的信息素濃度;[Δphki（t，t+1）]代表第t輪結束后螞蟻k在物體i上更新的信息素，number表示螞蟻i選擇的物體數目。

步驟五中，采用交換鄰域的爬山搜索算法。所謂交換領域，就是把背包問題（ KP）的解x中的某一個裝入物品從背包中取出，同時把某一未裝入背包的物品放入背包，這樣形成的解的集合就是解x的交換鄰域N2（x），用數學描述如下：

其中：[I0（x）]表示未裝入背包的物品合集，[I1（x）]表示裝入背包的物品合集。

3 數據分析

為了驗證算法設計的有效性，采用Python3.7以及NumPy科學計算庫對算法進行編程實現，同時將本文的改進算法與一般的GA、ACO算法以及文獻[16]說明的混合算法進行程序編寫、結果測試和對比。本文采用的測試算例來自http：//elib.zib.de/pub/mp-testdata/ip/sac94-suite/index.html中的部分例子。文中算法采用參數如下：最大迭代次數N=200，變異概率Pm=0.05，交叉概率Pc=0.45，解集大小size=15，初始信息素濃度矩陣ph=[1，1…，1]，每條路線信息素更新總量Q=1，信息素揮發因子ρ=0.5，啟發因子α=2，能見度因子β=3。

此外，為確定一個較好的循環次數N1的值，通過對一般GA運行10次后得到的結果，分析斜率突變前后的值，選取N1=50，如圖1所示。

將4種算法（算法1是本文的改進算法，算法2是普通GA算法，算法3是普通ACO算法，算法4是采用文獻[16]的混合算法）運行100次后得到的結果進行對比，如表1、表2所示。

表1結果顯示，算法1和算法2求得的最優解好于算法3和算法4，對于采用的測試例子約高出10%。

表2結果顯示，算法3和算法4的收斂速度比算法1和算法2更快。其中算法4最快，算法3次之，而算法2最慢，基本上與其它3種算法相差1～3個數量級。

以上仿真結果表明，在求解0/1 MKP問題上，在保證解精度的前提下，本文提出的方法在求解效率上比傳統的GA提高了一個數量級。而在求解速度上，雖然本文提出的方法與算法3和算法4相比收斂速度較慢，但還在一個數量級內。所以，如果對所求解的質量要求很高，本文提出的改進算法會是一個很好的選擇。

4 結語

通過充分分析遺傳算法和蟻群算法之間的優缺點，以及一些混合算法的不足，本文提出了一種新的混合方式，通過采用這種混合方式設計了一種算法。本文在充分發揮遺傳算法和蟻群算法優點的同時，基于生成解的特點，采用不同的方法處理每輪迭代中的不可行解。此外，為了優化最終解的穩定性，引入了交換鄰域的爬山法。對比實驗表明，在保證求解精度的前提下，本文算法能夠更好地減少求解的迭代次數。

本文使用的測試參數在中低維度（5個背包，30個物體）的背包上表現較好，但在高維度問題上需要另外設定相關參數。今后將對如何自動依照求解規模調整參數這一課題進行研究。

本文研究了0/1背包問題的一種求解算法，而現實環境中還存在一個背包選擇同一個物體多次的問題（比如工廠同一類型的產品有多個，而且機臺也可以同時處理同類型的多個產品）。在這種更普適的情況下，解的元素會有除0，1以外的其它值。如何將背包問題與實際生產問題相結合，合理設計和改進解的結構與算法（比如GA中的變異操作），以改進求解效率和求解質量，也是需要進一步研究的課題。

參考文獻：

[1]KARP R M. Reducibility among combinatorial problems[M]. New York：Plenum Press，1972.

[2]田烽楠，王于. 求解0-1背包問題算法綜述[J]. 軟件導刊，2009（1）：59-61.

[3]HASSANIEN A E，EMARY E. Swarm intelligence principles， advances， and applications[M]. Boca Raton：CRC Press， Inc. 2015.

[4][日]玄光男，林林. 網絡模型與多目標遺傳算法[M]. 梁承姬，于歆杰，譯.北京：清華大學出版社， 2017.

[5]武廣號，文毅，樂美峰. 遺傳算法及其應用[J]. 應用力學學報， 2000， 23（6）：9-10.

[6]李士勇，陳永強，李研. 蟻群算法及其應用[M]. 哈爾濱：哈爾濱工業大學出版社，2004.

[7]王熙照，賀毅朝. 求解背包問題的演化算法[J]. 軟件學報，2017（1）：391-399.

[8]劉雪靜，賀毅朝，吳聰聰，等. 基于細菌覓食算法求解折扣0-1背包問題的研究[J]. 計算機工程與應用，2018（8）：1204-1210.

[9]高思齊，邢玉軒，肖儂，等. 求解01背包問題的貪婪蛙跳算法[J]. 計算機科學，2018，45（7）：79-83.

[10]AZAD M A K，ROCHA A M A C，FERNANDES E M G P. Improved binary artificial fish swarm algorithm for the 0-1 multidimensional knapsack problems[J]. Swarm & Evolutionary Computation， 2014（14）：66-75.

[11]ZOU D，GAO L，LI S，et al. Solving 0-1 knapsack problem by a novel global harmony search algorithm[J]. Applied Soft Computing， 2011， 11（2）：1556-1564.

[12]郭麗萍， 申秋慧. 利用改進螢火蟲算法求解0-1背包問題[J]. 軟件導刊，2016（1）：54-56.

（責任編輯：杜能鋼）

收稿日期：2019-04-24

作者簡介：余典（1995-），男，電信科學技術研究院碩士研究生，研究方向為工廠排程優化。