求解多重二次背包問題的改進遺傳算法

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

摘要：

多重二次背包問題，旨在將具有單獨價值與協(xié)作價值的對象分配到一組容量有限的背包中，使總利潤最大化，是一種具有廣泛應(yīng)用的NP難組合優(yōu)化問題。針對該問題提出一種引入自適應(yīng)模式替換和貪心算法思想的改進遺傳算法（IGA）。首先對初始種群進行自適應(yīng)模式替換，使每代種群中的最好基因個體保存下來形成模式，替換原種群中質(zhì)量較差的個體，通過設(shè)計貪婪算子改進貪心思想對問題進行排序，然后進行擾動交叉操作和雙重選擇變異操作，最后采用最大化修復策略以保證解的可行性。標準算例仿真結(jié)果表明，相比傳統(tǒng)算法，IGA具有較強的尋優(yōu)能力。

關(guān)鍵詞：多重二次背包問題；自適應(yīng)模式替換；貪心算法；遺傳算法；最大化修復策略

DOIDOI：10.11907/rjdk.171999

中圖分類號：TP312

文獻標識碼：A文章編號文章編號：16727800（2018）001004904

Abstract：The quadratic multiple knapsack problem （QMKP） consists in assigning objects with both individual and pairwise profits to a set of limited knapsacks in order to maximize the total profit. QMKP is a NPhard combinatorial optimization problem with a number of applications.To solve the problem，an improved genetic algorithm （IGA） introduced adaptive model of replacement and greedy algorithm is proposed.First， the algorithm used selfadaptive model of replacement to initial population so that made the best gene from each generation population individuals survived and formed model to replace the poor quality individuals of the original population.Then sorted the problem by changing the greedy thought through designing greedy operator. After that performed the disturbance cross operation and double selection mutation operation. Finally， to ensure the feasibility of the solution by using maximized repair strategy. In the numerical computation results on standard quadratic multiple knapsack problem instances，the IGA has stronger optimizing capacity than the traditional algorithms.

Key Words：quadratic multiple knapsack problem； selfadaptive replacement model； greedy algorithm； genetic algorithm； maximize repair strategies

0概述

多重二次背包問題（Quadratic Multiple Knapsack Problem，QMKP）是二次背包問題（Quadratic Knapsack Problem，QKP）與多重背包問題（Multiple Knapsack Problem， MKP）兩個經(jīng)典NP難題融合后的一個新問題，由Hiley和Julstrom[1]于2006年提出。目前，QMKP廣泛應(yīng)用于金融、庫存管理、生產(chǎn)計劃調(diào)度、機場車站布局、密碼設(shè)計、通訊基站優(yōu)化、集成電路設(shè)計等方面，在最近幾年也得到了學者的廣泛關(guān)注[2]。現(xiàn)有兩種求解方法為精確方法和啟發(fā)式方法。較具代表性的精確算法有2012年Quadri等[3]提出的分支定界精確算法及Wang等[4]提出的具有線性表示的分支定界法，精確算法都只能求解小規(guī)模QMKP，難以滿足實際需求，所以啟發(fā)式法通常用于在合理的計算時間內(nèi)找到多重二次背包的近似解[5]。如Hiley和Julstrom[1]提出了3種用于解決多重二次背包的方法，即貪婪啟發(fā)式算法、隨機爬山算法和具有爬山算子的遺傳算法（其中對所選父節(jié)點交叉算子通常保留對象到背包的分配）。Singh和Baghel[6]提出了一種穩(wěn)態(tài)分組遺傳算法解決QMKP。算法思想反復選擇兩個父代交叉產(chǎn)生子代去替代種群中較差個體，將具有最大利潤值的背包從所選父代遺傳到子代，種群每次迭代并不完全被替換，始終保持擁有較優(yōu)個體。另外，Sarac和Sipahioglu[7]使用另一種遺傳算法解決QMKP，此算法使用互相交換兩個隨機選擇的父代對象分配特殊交叉方式。2010年Sipahioglu等[7]提出了一種基于可行解的次梯度遺傳算法（MSGGA），次梯度方法在處理約束時不必考慮懲罰參數(shù)，處理相對簡單。另外，2010年Sundar[8]針對QMKP引入了人工蜂群算法與局部搜索（SSABC）的組合。人工蜂群算法由于編碼特點使其更適合處理連續(xù)優(yōu)化問題，在處理組合優(yōu)化問題上并不占優(yōu)勢。從上述文獻看，出現(xiàn)的啟發(fā)式算法多采用遺傳算法，這些遺傳算法中雖融入了不同算子用于改進性能，但隨著迭代次數(shù)的增加，最優(yōu)解變得越來越少，導致交叉和變異操作往往只能在最優(yōu)解內(nèi)部進行，遺傳速度大大放緩，使其處理QMKP效果并不理想[9]。endprint

本文算法首先重新設(shè)計傳統(tǒng)的貪心算子，將問題用改進后的貪婪算法排序，為求解大規(guī)模QMKP奠定基礎(chǔ)；然后引入自適應(yīng)模式替換，使每代種群中的最好基因個體保存下來形成模式，引導種群的搜索方向，提高了搜索性能，避免了早熟現(xiàn)象的出現(xiàn)；接著進行選擇、擾動交叉操作、雙重選擇變異操作；最后引入最大化修復策略，對不可行解進行修復，對可行解進行修正，最終更加有效地解決多重二次背包問題。

2.4自適應(yīng)模式替代

為了提高遺傳算法的搜索速度和尋找最優(yōu)解的能力，本文在進行選擇操作之前引入自適應(yīng)模式替換操作。

模式是基于三值字符集{0，1，*}所產(chǎn)生的能描述某些結(jié)構(gòu)相似的0、1字符串集的模板[10]。例如模式1**1（長度為4的串）描述了在位置1和位置4為“1”的字符串，即{1001，1011，1101，1111}。

模式替代就是通過記錄每代種群中最好的幾個個體生成模式采樣空間，然后利用種群中的不確定字符“*”生成新個體，用生成的新個體替換原種群中質(zhì)量較差的個體，使這些替換后的新個體經(jīng)過交叉、變異之后仍能以較大的概率存活下來，從而保證優(yōu)良基因的繁殖，引導種群的搜索方向[11]。傳統(tǒng)模式替代的模式固定率是固定的，隨著迭代次數(shù)的增加，較優(yōu)個體越來越集中，模式中確定基因位越來越多，其結(jié)構(gòu)也越來越相似，這就影響了迭代后期種群的多樣性及新個體的生成[12]。鑒于此，為保證模式中確定位數(shù)和不確定位數(shù)在整個迭代過程中保持相對穩(wěn)定，本文結(jié)合自適應(yīng)思想，采用自適應(yīng)模式替代，規(guī)定了確定基因位和不確定基因位的產(chǎn)生方式，即設(shè)置自適應(yīng)模式比Ra，若模式中確定基因位太多，可以提高Ra，減少確定的位數(shù)；若模式中確定基因位太少，則降低比例數(shù)Ra，增加確定的位數(shù)，以此對模式進行評估和校正。具體操作如下：

（1）考慮到計算量，本文設(shè)置每隔20代進行一次模式生成。

（2）將種群適應(yīng)值按降序排列的個體集中前ML個（模式采樣空間的個體數(shù)，本文取50）個體記錄下來進行統(tǒng)計，形成模式候選集。

（3）在模式采樣空間里，計算種群中所有個體相同基因位上1和0所占比例之差的絕對值，記為基因差別比例Ca[12]。對各基因位的基因差別比例進行非升序排序。按照給定自適應(yīng)模式比的初始值選出前r個基因位作為確定基因位，剩余基因位均為不確定基因位，將確定基因位與個體長度之比定義為自適應(yīng)模式比Ra。

例如：模式空間的較優(yōu)個體為：11 010，01 110，10 010，11 001， 10 110，那么各基因位上0和1所占比例分別為：0.2、0.8，0.4、0.6，0.6、0.4，0.2、0.8，0.8、0.2，0和1所占比例之差的絕對值分別為0.6，0.2，0.2，0.6，0.6，若給定的自適應(yīng)模式比的初始值為Ra=0.5，則確定基因位是1、4、5，不確定基因位為2和3，更新后的Ra=0.6。

計算被記錄個體每一基因位上0（或1）的個數(shù)占當前種群此基因位總字符數(shù)的比例，若超過Ra，則該基因位值為0（或1），否則為*，由此得到采樣空間的模式，如上例中生成模式為1**10，其中被確定為0或1的基因位稱為個體的優(yōu)良基因。

（4）將具有優(yōu)良基因的新個體加入到原種群中，計算所有個體的適應(yīng)度，并按適應(yīng)度進行降序排列。然后取前PopSize個個體作為當前種群，由此替代原種群中質(zhì)量較差的個體。在保證提高尋優(yōu)能力的同時防止早熟。

2.5擾動交叉與雙重選擇變異操作

在遺傳算法中，交叉和變異操作主要是產(chǎn)生新的個體，維持種群多樣性。為增強種群多樣性，提高算法的局部搜索能力，必須對交叉操作產(chǎn)生的新個體進行篩選，防止模式相差較小的個體過多地進入候選集。具體操作如下：

傳統(tǒng)的變異操作根據(jù)變異概率Pm進行按位隨機變異，當Pm決定了變異個體后，該個體所變異的基因位是隨機的。對于二進制編碼的個體來說，就是隨機對某一基因位0變1或1變0，這對遺傳算法的局部搜索性能并沒有較好的提高。本文按照基因差別比例Ca進行變異。變異概率Pm決定變異個體后，由Ca決定進行變異的基因位，在此定義為雙重選擇的變異操作。首先，計算種群中各基因位上0和1所占比例之差的絕對值。例如：1 010，1 011，1 101，1 100，1 110，0 011，各基因位上的Ca分別為Ca1=2/3，Ca2=0，Ca3=1/3，Ca4=0。然后比較Ca值，Ca值越大的基因位進行變異的概率越大，這就在一定程度上決定了進行變異的基因位，避免早熟現(xiàn)象。

2.6最大化利用率修復策略

在遺傳算法中，每一次的迭代都需要進行選擇、交叉和變異操作，產(chǎn)生新個體，提高種群多樣性，盡可能獲得全局最優(yōu)解。但是，經(jīng)過這樣一系列的操作后，生成的解可能超出約束條件，對此問題的處理方法通常有懲罰函數(shù)法和修復操作法。本文采用既考慮價值重量比又兼顧各背包容量利用率的最大化利用率修復策略，修復不可行解的同時修正可行解。首先對違反約束條件的解，按照價值密度遞增的順序依次減掉背包中的物品，直到滿足約束條件為止。然后，對滿足約束條件的解，按照價值密度遞減的順序?qū)⑽锲贩湃胧Ｓ嗳萘孔畲蟮谋嘲校钡奖嘲荒茉傺b為止。這樣既可以保證種群中每一個個體是正常編碼的個體，又可以使其對應(yīng)較優(yōu)的可行解。

3改進的遺傳算法具體流程

改進的遺傳算法的具體流程如圖1所示，其中g(shù)為迭代次數(shù)，G為最大迭代數(shù)。

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

在本文使用的算例中，群體規(guī)模取PopSize=100，模式采樣空間個體數(shù)取ML=50，自適應(yīng)模式比的初始值取Ra=0.5，交叉概率取Pc=0.8，變異概率取Pm=0.2，最大迭代次數(shù)G=1 000，算法程序由MATLAB編碼實現(xiàn)。

為驗證本文算法的性能，將IGA與隨機爬山算法（SHC）、具有爬山算子的遺傳算法（HCGA）、人工蜂群算法（SSABC）進行比較，分別對30個測試用例獨立運行40次，對比結(jié)果如表1及表2，其中Best表示40次求解所獲最好的最優(yōu)解在此稱為最佳解，Avg表示40次最優(yōu)解的平均值，SD為40次結(jié)果的標準偏差，4種算法中最好的平均值和最佳解用粗體突出顯示。endprint

由表1可以看出，4種算法對100維的15個標準實例求得的最佳解和平均值中，IGA求解的最佳解僅有2個不是最

優(yōu)的，平均值僅有1個不是最好的，剩下的12個問題在最優(yōu)值、平均值、標準偏差都優(yōu)于其它算法。

由表2可以看出，200維測試中IGA求解的平均值和最優(yōu)解各有4個比其它算法略低或相當，另9個測試問題的最優(yōu)值、平均值、標準偏差都優(yōu)于其它算法。

綜合表1、表2，4種算法對30個標準實例求得的最佳解和平均值中，IGA求解的最佳解有24個是最優(yōu)的，占所有最優(yōu)解的80%，平均值有25個是最好的，占所有最好平均值的83.33%。且IGA算法的標準偏差更小一些，說明IGA算法在求解多重二次背包問題時具有一定的可行性和有效性。

5結(jié)語

本文提出了一種改進的遺傳算法，首先設(shè)計了貪婪算子，引入價值密度，然后加入自適應(yīng)模式替代操作，進行擾動交叉和雙重選擇變異，最后使用最大化利用率修復策略。提出的IGA算法局部搜索能力和全局搜索能力較強，能很好地保持種群多樣性，避免了早熟現(xiàn)象的發(fā)生。通過實驗仿真，驗證了IGA算法具有較好的性能，說明了IGA的有效性和可行性。目前，本文只優(yōu)化了協(xié)作價值非零比例為25%的情況，今后將對協(xié)作價值非零比例較大的多重二次背包問題繼續(xù)研究。

參考文獻：

[1]HILEY A， JULSTROM B A. The quadratic multiple knapsack problem and three heuristic approaches to it[C]. Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation.New York，2006.

[2]錢潔，王保華，鄭建國，等.多重二次背包問題的量子進化求解算法[J].計算機學報， 2015（8）：15181529.

[3]DELLA CROCE F，QUADRI D.Improving an exact approach for solving separable integer quadratic knapsack problems[J].Journal of Combinatorial Optimization，2012，23（1）：2128.

[4]WANG H，KOCHENBERGER G，GLOVER F.A computational study on the quadratic knapsack problem with multiple constraints[J].Computers&Operations Research，2012，39（1）：311.

[5]J QIN， X XU， Q WU， TCE CHENG. Hybridization of tabu search with feasible and infeasible local searches for the quadratic multiple knapsack problem[J]. Computers & Operations Research，2016，66：199214.

[6]Y CHEN，JK HAO，F(xiàn) GLOVER. An evolutionary path relinking approach for the quadratic multiple knapsack problem[J].Elsevier Science Publishers B.V. 2016，92（C）：2334.

[7]SIPAHIOGLU A，SARAC T.Solving the generalizad quadratic multiple knapsack problem by using FMSG algorithm[C].Proceeding of the 24th Mini EURO Conference on Continuous Optimization and Informationbased Technologies in the Financial Sector，Izmir，Turkety，2010.

[8]SUNDAR S， SINGH A. A swarm intelligence approach to the quadratic multiple knapsack problem[J]. Lect Notes Comput Science，2010，6443：626633.

[9]X LIU，F(xiàn) XIANG，J MAO.An improved method for solving the largescale multidimensional 01 knapsack problem[C].International Conference on Electronics & Communication Systems. Coimbatore， INDIA，2014.

[10]于惠.遺傳算法的改進研究及在背包問題中的應(yīng)用[D].濟南：山東師范大學，2009.

[11]李康順，賈玉珍，張文生.一種基于模式替代的遺傳算法解0/1背包問題[J].計算機應(yīng)用研究，2009，26（2）：470471.

[12]王娜，向鳳紅，毛劍琳.改進的自適應(yīng)遺傳算法求解0/1背包問題[J].計算機應(yīng)用，2012，32（6）：16821684.

（責任編輯：何麗）endprint