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

余典　吳勇　余山

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

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

DOI：10. 11907/rjdk. 191598

中圖分類號：TP301 ? 文獻(xiàn)標(biāo)識碼：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）是著名的整數(shù)規(guī)劃問題之一，屬于NP-hard問題[1]。它的實際應(yīng)用場景很多，如工廠中的資源分配形式、數(shù)據(jù)加密、投資組合、機臺調(diào)度等。近幾十年研究出各種各樣的解決方法，其中精確算法有分支限界法、動態(tài)規(guī)劃法等，近似算法有貪婪方法、蟻群算法等[2]。近幾年對該問題的研究主要集中于以遺傳、蟻群算法為代表的元啟發(fā)式算法[3]。

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

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

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

無論是新的元啟發(fā)式算法還是在現(xiàn)有算法基礎(chǔ)上進(jìn)行改進(jìn)，都是為了更快地尋找到更優(yōu)的解。

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

1 0/1多維背包問題數(shù)學(xué)模型

一般將0/1MKP問題構(gòu)建數(shù)學(xué)模型如下：

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

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

2.1 算法設(shè)計思想

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

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

2.2 算法流程

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

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

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

步驟四：進(jìn)入算法第二步（ACO為主）：

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

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

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

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

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

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

（7）按照蟻周系統(tǒng)對物體上的信息素進(jìn)行更新。

（8）保留當(dāng)代最優(yōu)解。

（9）如果迭代次數(shù)小于等于N，則轉(zhuǎn)到步驟四之（2）;否則輸出最優(yōu)解并結(jié)束程序。

步驟五：對得到的結(jié)果利用交換鄰域的爬山法進(jìn)行優(yōu)化。

2.3 算法策略

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

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

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

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

交叉操作（步驟三之①，步驟四之（6））中，循環(huán)size次，每次生成一個隨機數(shù)random∈[0，1]。當(dāng)random

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

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

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

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

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

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

3 數(shù)據(jù)分析

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

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

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

表1結(jié)果顯示，算法1和算法2求得的最優(yōu)解好于算法3和算法4，對于采用的測試?yán)蛹s高出10%。

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

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

4 結(jié)語

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

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

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

參考文獻(xiàn)：

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

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

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

[4][日]玄光男，林林. 網(wǎng)絡(luò)模型與多目標(biāo)遺傳算法[M]. 梁承姬，于歆杰，譯.北京：清華大學(xué)出版社， 2017.

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

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

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

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

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

[10]AZAD M A K，ROCHA A M A C，F(xiàn)ERNANDES 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]郭麗萍， 申秋慧. 利用改進(jìn)螢火蟲算法求解0-1背包問題[J]. 軟件導(dǎo)刊，2016（1）：54-56.

（責(zé)任編輯：杜能鋼）

收稿日期：2019-04-24

作者簡介：余典（1995-），男，電信科學(xué)技術(shù)研究院碩士研究生，研究方向為工廠排程優(yōu)化。