求解多重二次背包問(wèn)題的改進(jìn)遺傳算法

劉夢(mèng)佳+向鳳紅+毛劍琳+郭寧

摘要：

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

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

DOIDOI：10.11907/rjdk.171999

中圖分類(lèi)號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)文章編號(hào)：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概述

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

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

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

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

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

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

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

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

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

例如：模式空間的較優(yōu)個(gè)體為：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所占比例之差的絕對(duì)值分別為0.6，0.2，0.2，0.6，0.6，若給定的自適應(yīng)模式比的初始值為Ra=0.5，則確定基因位是1、4、5，不確定基因位為2和3，更新后的Ra=0.6。

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

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

2.5擾動(dòng)交叉與雙重選擇變異操作

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

傳統(tǒng)的變異操作根據(jù)變異概率Pm進(jìn)行按位隨機(jī)變異，當(dāng)Pm決定了變異個(gè)體后，該個(gè)體所變異的基因位是隨機(jī)的。對(duì)于二進(jìn)制編碼的個(gè)體來(lái)說(shuō)，就是隨機(jī)對(duì)某一基因位0變1或1變0，這對(duì)遺傳算法的局部搜索性能并沒(méi)有較好的提高。本文按照基因差別比例Ca進(jìn)行變異。變異概率Pm決定變異個(gè)體后，由Ca決定進(jìn)行變異的基因位，在此定義為雙重選擇的變異操作。首先，計(jì)算種群中各基因位上0和1所占比例之差的絕對(duì)值。例如：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值越大的基因位進(jìn)行變異的概率越大，這就在一定程度上決定了進(jìn)行變異的基因位，避免早熟現(xiàn)象。

2.6最大化利用率修復(fù)策略

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

3改進(jìn)的遺傳算法具體流程

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

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

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

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

由表1可以看出，4種算法對(duì)100維的15個(gè)標(biāo)準(zhǔn)實(shí)例求得的最佳解和平均值中，IGA求解的最佳解僅有2個(gè)不是最

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

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

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

5結(jié)語(yǔ)

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

參考文獻(xiàn)：

[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]錢(qián)潔，王保華，鄭建國(guó)，等.多重二次背包問(wèn)題的量子進(jìn)化求解算法[J].計(jì)算機(jī)學(xué)報(bào)， 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]于惠.遺傳算法的改進(jìn)研究及在背包問(wèn)題中的應(yīng)用[D].濟(jì)南：山東師范大學(xué)，2009.

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

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

（責(zé)任編輯：何麗）endprint