折扣{0-1}背包問(wèn)題粒子群算法的貪婪修復(fù)策略探究

摘要：群智能啟發(fā)式算法求解折扣{0-1}背包問(wèn)題（D{0-1}KP）時(shí)，為提升求解效率和求解質(zhì)量，需采用某種修復(fù)與優(yōu)化策略將非正常編碼個(gè)體轉(zhuǎn)換為符合解約束條件的編碼個(gè)體。在引入項(xiàng)集價(jià)值密度概念基礎(chǔ)上，以粒子群算法（PSO）為例，提出一組基于項(xiàng)集的貪婪修復(fù)與優(yōu)化方法（group greedy repair and optimization algorithm，GGROA），并進(jìn)一步構(gòu)造PSO-GGRDKP算法（PSO based GGROA for solving D{0-1}KP）以探究GGROA方法的可行性和性能。PSO-NGROADKP（PSO based NGROA for solving D{0-1}KP）和PSO-GRDKP（PSO based GROA for solving D{0-1}KP）是基于項(xiàng)貪心修復(fù)與優(yōu)化方法的粒子群算法。在D{0-1}KP標(biāo)準(zhǔn)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果表明：與PSO-NGROADKP和PSO-GRDKP相比，PSO-GGRDKP算法的解誤差率略高，但算法時(shí)間性能分別提升了13.8%、12.9%。

關(guān)鍵詞：折扣{0-1}背包問(wèn)題； 啟發(fā)式算法； 粒子群算法； 非正常編碼個(gè)體； 貪心修復(fù)與優(yōu)化； D{0-1}KP數(shù)據(jù)集

中圖分類號(hào)：TP391文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695（2022）08-021-2363-06

doi：10.19734/j.issn.1001-3695.2021.12.0701

Greedy repair strategy of particle swarm optimization for discounted {0-1} knapsack problem

Dai Zuhua， Zhou Bin， Long Yujing， Wang Zongquan

（College of Computer Science amp; Engineering， Northwest Normal University， Lanzhou 730070， China）

Abstract：Swarm intelligence heuristic algorithm is used to solve discounted {0-1} knapsack problem （D{0-1} KP）. In order to improve the solution efficiency and quality， a repair and optimization strategy is needed to convert abnormal coding individuals into coding individuals that meet the solution constraints. On the basis of introducing the concept of group value density， taking particle swarm optimization algorithm （PSO） as an example， this paper proposed a set of greedy repair and optimization methods based on group （GGROA）， and further constructed the PSO based GGROA for solving D{0-1}KP algorithm （PSO-GGRDKP） to explore the feasibility and performance of GGROA. PSO-NGROADKP and PSO-GRDKP were PSO algorithms based on item greedy repair and optimization method. The experimental results on D {0-1} KP standard data set show that compared with PSO-NGROADKP and PSO-GRDKP， PSO-GGRDKP has slightly higher error rate， but the time performance of the algorithm is improved by 13.8% and 12.9% respectively.

Key words：discount {0-1} knapsack problem; heuristic algorithm; particle swam optimization algorithm; non-normal coding individual; greedy repair and optimization; D{0-1}KP dataset

0引言

{0-1}背包問(wèn)題（{0-1}knapsack problem， {0-1}KP）是計(jì)算機(jī)科學(xué)一個(gè)重要的NP complete問(wèn)題，也是一類經(jīng)典組合優(yōu)化問(wèn)題，在商業(yè)、經(jīng)濟(jì)、管理、安全等領(lǐng)域有著廣泛應(yīng)用背景。{0-1}KP自提出后的幾十年里被反復(fù)研究，衍生出精確算法、非精確算法兩大類算法。精確算法有動(dòng)態(tài)規(guī)劃、回溯法和分支限界法等；非精確算法主要有隨機(jī)算法、近似算法、生物算法等。2005年，由GUDER首次提出的折扣{0-1}背包問(wèn)題（discount {0-1} knapsack problem， D{0-1}KP）［1，2］是{0-1}背包問(wèn)題的拓展形式，作為刻畫(huà)折扣銷售、捆綁銷售等商業(yè)活動(dòng)現(xiàn)象的經(jīng)典數(shù)學(xué)模型，是商家設(shè)計(jì)商業(yè)營(yíng)銷方案、消費(fèi)者購(gòu)買商品決策的科學(xué)計(jì)算依據(jù)。

D{0-1}KP實(shí)例由一組項(xiàng)集（item_group）組成，每個(gè)項(xiàng)集有三項(xiàng)物品（項(xiàng)，item）可供背包裝入選擇，定義1給出了D{0-1}KP第一數(shù)學(xué)模型。

定義1D{0-1}KP第一數(shù)學(xué)模型［3］。給定n個(gè)項(xiàng)集和載重為C的背包，每個(gè)項(xiàng)集i（i=0，1，…，n－1）由三個(gè)項(xiàng)（item）組成，編號(hào)記做3i、3i+1、3i+2，項(xiàng)對(duì)應(yīng)重量系數(shù)記做w3i、w3i+1、w3i+2，各項(xiàng)對(duì)應(yīng)價(jià)值系數(shù)記做p3i、p3i+1、p3i+2，其中p3i+2=p3i+p3i+1，w3i+2lt;w3i+w3i+1，

w3ilt;w3i+1lt;w3i+2，w3i+2≤C，∑n－1i=0w3i+2gt;C，pj，wj（0≤j≤3n－1），C都是正整數(shù)，項(xiàng)集i的各項(xiàng)價(jià)值密度記做e3i，e3i+1，e3i+2=p3i/w3i，p3i+1/w3i+1，p3i+2/w3i+2，每個(gè)項(xiàng)集至多有一項(xiàng)被選擇裝入背包。在不超過(guò)背包載重量C的條件下，從給定項(xiàng)集選擇滿足裝入背包要求的項(xiàng)，使得裝入背包所有項(xiàng)的價(jià)值系數(shù)之和達(dá)到最大。

D{0-1}KP是一個(gè)特殊整數(shù)規(guī)劃問(wèn)題，定義決策變量xj=1（0≤j≤3n－1）表示項(xiàng)j裝入背包，xj=0表示項(xiàng)j未裝入背包，對(duì)于決策向量（x0，x1，…，x3n－1）， D{0-1}KP的整數(shù)規(guī)劃模型為

max f（x）=max∑n－1i=0（x3ip3i+x3i+1p3i+1+x3i+2p3i+2）（1）

其中：x3i+x3i+1+x3i+2≤1，x3i，x3i+1，x3i+2∈{0，1}（2）

∑n－1i=0（x3iw3i+x3i+1w3i+1+x3i+2w3i+2）≤C（3）

D{0-1}KP的項(xiàng)集有四種選擇狀態(tài)，如果背包容量和項(xiàng)的價(jià)值系數(shù)取值范圍很大，則不選擇某個(gè)項(xiàng)集的約束條件較難確定，這意味著D{0-1}KP的算法難度要大于{0-1}KP ［4］。以{0-1}KP研究成果為基礎(chǔ)，學(xué)者們進(jìn)一步研究了D{0-1}KP的各類算法。其中基礎(chǔ)動(dòng)態(tài)規(guī)劃算法［5］（basic dynamic programming，BDP）是處理小規(guī)模數(shù)據(jù)的精確解算法。2016年He等人［4］以“所選擇項(xiàng)的價(jià)值系數(shù)之和使總重量最小”原則構(gòu)造動(dòng)態(tài)規(guī)劃目標(biāo)函數(shù)，提出一種新動(dòng)態(tài)規(guī)劃算法（new exact algorithm for D{0-1}KP， NE-DKP），當(dāng)背包容量大于所有的項(xiàng)集第三項(xiàng)價(jià)值累加和時(shí)，NE-DKP算法性能好于BDP算法。動(dòng)態(tài)規(guī)劃算法是偽多項(xiàng)式時(shí)間復(fù)雜度，一般不適用于大規(guī)模D{0-1}KP 實(shí)例的求解。

群智能啟發(fā)式算法是近年來(lái)求解D{0-1}KP的主流算法，對(duì)于解決大規(guī)模實(shí)例有突出性能優(yōu)勢(shì)。應(yīng)用D{0-1}KP第一數(shù)學(xué)模型設(shè)計(jì)啟發(fā)式算法，決策向量（x0，x1，…，x3n－1）的不同取值組合對(duì)應(yīng)不同個(gè)體，這種二元編碼法雖然便于個(gè)體演化算子的實(shí)現(xiàn)，但由于可行解約束條件式（2）（3）的限制，編碼空間中非正常編碼個(gè)體（即個(gè)體編碼不對(duì)應(yīng)問(wèn)題可行解）的概率至少為1－（1/2）n［3］。為此，需要采用某種策略將非正常編碼個(gè)體轉(zhuǎn)換為符合解約束條件的編碼個(gè)體，以提升求解效率和求解質(zhì)量。文獻(xiàn)［3，4，6］先后提出的貪心修復(fù)與優(yōu)化策略是消除非正常編碼個(gè)體效果較好的方法。文獻(xiàn)［4］在研究D{0-1}KP粒子群求解算法時(shí)，證明了給定項(xiàng)集中三個(gè)項(xiàng)目的價(jià)值重量比率關(guān)系只有四種情況，利用這一特性提出了GR-DKP（greedy repair algorithm for D{0-1}KP）算法，設(shè)計(jì)了基于GR-DKP的粒子群求解算法（PSO based greedy repair algorithm for solving D{0-1}KP，PSO-GRDKP）［4］。文獻(xiàn)［3］在研究D{0-1}KP第一遺傳算法（first genetic algorithm，F(xiàn)irEGA）中再次提出貪心修復(fù)與優(yōu)化算法（greedy repair and optimization algorithm， GROA）［3］，GROA與GR-DKP算法均按照非遞增項(xiàng)價(jià)值密度對(duì)項(xiàng)進(jìn)行貪心選取，若項(xiàng)集中有多項(xiàng)是選取狀態(tài)時(shí)，選擇價(jià)值密度最大項(xiàng)。楊洋等人［7］進(jìn)一步優(yōu)化了GROA算法，構(gòu)造了新貪心修復(fù)優(yōu)化算法（new greedy repair and optimization algorithm，NGROA），該算法也按照非遞增項(xiàng)價(jià)值密度對(duì)項(xiàng)進(jìn)行貪心選取，但當(dāng)項(xiàng)集中有多項(xiàng)是選取狀態(tài)時(shí)，選擇項(xiàng)集的價(jià)值最大項(xiàng)，應(yīng)用NGROA算法提出NFirEGA（new first genetic algorithm）的研究結(jié)果表明，較之FirEGA提升了D{0-1}KP求解質(zhì)量。最近，文獻(xiàn)［8］定義了項(xiàng)集價(jià)值密度概念，提出按非遞增項(xiàng)集價(jià)值密度對(duì)項(xiàng)進(jìn)行貪心選取的策略，當(dāng)項(xiàng)集中多項(xiàng)是選取狀態(tài)時(shí)，選擇滿足解約束條件的價(jià)值密度最大項(xiàng)。上述貪婪修復(fù)與優(yōu)化算法［3～8］的時(shí)間復(fù)雜度為O（n）。多數(shù)研究者采用文獻(xiàn)［3］提出的GROA設(shè)計(jì)D{0-1}KP的各類啟發(fā)式進(jìn)化算法，如差分進(jìn)化算法（differential evolution algorithm，DE）［9］、變異蝙蝠算法（mutated double codes binary bat algorithm，MDBBA）［10］、差分進(jìn)化帝王蝶優(yōu)化啟發(fā)式算法（monarch butterfly optimization with differential evolution，DEMBO） ［11］、飛蛾搜索算法（moth search algorithm，MS）［12］ 、基于Lagrange插值的學(xué)習(xí)猴群算法（lagrange interpolation based learning monkey algorithm，LSTMA）［13］、基于環(huán)論的演化算法 （ring theory based evolutionary algorithm，RTEA）［14］、基于離散混合教學(xué)的優(yōu)化算法（discrete hybrid teaching learning based optimization algorithm，HTLBO）［15］等，以上研究常選用FirEGA［3］和基本啟發(fā)式算法作為基線，通過(guò)對(duì)比求解質(zhì)量和收斂速度以論證所研究算法的優(yōu)化性能。

在采用第一數(shù)學(xué)模型和GROA算法構(gòu)造D{0-1}KP啟發(fā)式算法的研究中［10，11，14］，文獻(xiàn)［10］的仿真實(shí)驗(yàn)結(jié)果表明，在UDKP和SDKP實(shí)例上，雙重編碼二進(jìn)制蝙蝠算法（double codes binary bat algorithm，DBBA）的求解質(zhì)量比FirEGA差，在IDKP和WDKP實(shí)例上，DBBA的求解質(zhì)量好于FirEGA；帝王蝶優(yōu)化算法（monarch butter fly optimization，MBO）在best、mean及worst三個(gè)評(píng)價(jià)指標(biāo)上的求解結(jié)果要明顯差于FirEGA算法［11］；PSO-GRDKP算法求解精度和穩(wěn)定性優(yōu)于FirEGA［14］。這些研究結(jié)果表明，采用同一類貪婪修復(fù)與優(yōu)化方法的不同啟發(fā)式算法求解性能會(huì)有差異。本文基于項(xiàng)集價(jià)值密度［8］概念，構(gòu)造一組基于項(xiàng)集的貪婪修復(fù)和優(yōu)化方法，并探究其可行性和性能，進(jìn)一步討論貪婪修復(fù)方法與數(shù)據(jù)實(shí)例類型之間的適應(yīng)性關(guān)系。為避免啟發(fā)式算法差異對(duì)研究?jī)?nèi)容的影響，以粒子群算法為例來(lái)構(gòu)造D{0-1}KP求解算法。

1相關(guān)研究工作

1.1二元粒子群優(yōu)化算法

Kennedy等人［16］通過(guò)對(duì)鳥(niǎo)群捕食行為的研究，在1995年提出標(biāo)準(zhǔn)粒子群算法（particle swarm optimization，PSO）；BPSO（binary particle swarm optimization）是一種應(yīng)用于離散空間搜索的二元粒子群優(yōu)化算法［17］；Bansal等人［18］用粒子速度作為{0-1}KP中物品選擇為1或0的概率，提出了一種修正二元粒子群優(yōu)化（modified binary particle swarm optimization，MBPSO） 算法來(lái)解決背包問(wèn)題。MBPSO算法原理描述為：假設(shè)搜索空間為D維，定義D維向量xi=（xi1，xi2，…，xij，…，xiD）表示粒子群中第i個(gè)粒子的位置，對(duì)應(yīng)粒子速度為vi=（vi1，vi2，…，vij，…，viD），個(gè)體極值pbest=（pbest1，pbest2，…，pbestj，…，pbestD）表示粒子群某次迭代的最優(yōu)解，全局極值gbest=（gbest1，gbest2，…，gbestj，…，gbestD）表示種群在進(jìn)化過(guò)程中的全局最優(yōu)解，個(gè)體極值和全局極值由適應(yīng)度函數(shù)確定，粒子進(jìn)化公式為

vt+1ij=vtij+c1·r1·（ptbestj－xtij）+c2·r2·（gbestj－xtij）（4）

sig（vt+1ij）=11+e－vt+1ij（5）

xt+1ij=0ifr3≥sig（vt+1ij）1otherwise （6）

其中：t表示進(jìn)化迭代次數(shù)；vtij表示在t次進(jìn)化迭代中第i個(gè)粒子的第j維速度；xtij表示在t次進(jìn)化迭代中第i個(gè)粒子的第j維位置。式（4）為粒子群的進(jìn)化動(dòng)力方程，主要由三方面構(gòu)成：vtij屬于粒子個(gè)體的慣性勢(shì)；c1·r1·（ptbestj－xtij）來(lái)自粒子個(gè)體當(dāng)前歷史最好位置pbest的引力勢(shì)，代表粒子個(gè)體認(rèn)知；c2·r2·（gbestj－xtij）是來(lái)自群體當(dāng)前歷史最好位置gbest的引力勢(shì)，代表粒子社會(huì)認(rèn)知［19］。學(xué)習(xí)因子c1、c2作為粒子個(gè)體認(rèn)知和社會(huì)認(rèn)知的主要加權(quán)系數(shù)，表示進(jìn)化過(guò)程對(duì)粒子個(gè)體信息和社會(huì)信息的學(xué)習(xí)繼承程度，主要影響著粒子的優(yōu)化目標(biāo)識(shí)別能力。r1、r2、r3表示（0， 1）的隨機(jī)數(shù)。

PSO-GRDKP算法［4］是D{0-1}KP的一種粒子群求解算法，算法搜索空間維度D=3n－1，粒子適應(yīng)度函數(shù)對(duì)應(yīng)個(gè)體解的背包裝入價(jià)值，學(xué)習(xí)因子c1、c2的取值是2，算法時(shí)間復(fù)雜度是O（n3）。該算法利用貪婪修復(fù)與優(yōu)化算子對(duì)種群中不可行粒子進(jìn)行校正和優(yōu)化，有效提升種群中優(yōu)質(zhì)個(gè)體比率，增強(qiáng)算法尋優(yōu)能力。

1.2不可行個(gè)體貪婪修復(fù)與優(yōu)化算法

He等人［4］在研究D{0-1}KP問(wèn)題時(shí)先后提出GROA［3］ 、GR-DKP 兩種貪婪修復(fù)算法，其中GR-DKP在研究粒子群算法（PSO-GRDKP）時(shí)提出。以下給出GR-DKP算法偽代碼。

算法1GR-DKP

輸入：3n個(gè)項(xiàng)的價(jià)值向量P、重量向量W；背包容量C；按非遞增項(xiàng)價(jià)值密度次序保存各項(xiàng)下標(biāo)H［0，…，3n－1］；待修復(fù)粒子x［0，…，3n－1］。

輸出：修復(fù)優(yōu)化后的可行粒子x［0，…，3n－1］和適應(yīng)度值f（x）。

1fweight=0，fvalue=0

2for i in range（0，n－1）：

if （x3i+x3i+1+x3i+2≥1）：

x3i=0，x3i+1=0，x3i+2=0

j=arg maxj∈{3i，3i+1，3i+2}（pj/wj）

xj=1，fweight+=wj

3k=3n－1

4while weightgt;C andk≥0：

if （xH［k］==1）：

fweight－=wH［k］，xH［k］=0

k=k－1

5for j in range（0，3n－1）：

i=int（H［i］3）

if （x3i+x3i+1+x3i+2==0 and" fweight+wH［j］≤C）：

xH［j］==1，fweight+=wH［j］

6for i in range（0，3n－1）：

fvalue+=xi×pi

7return x， fvalue

算法1第2～4步是對(duì)粒子x的修復(fù)操作，第5步是對(duì)粒子x的優(yōu)化操作，算法時(shí)間復(fù)雜度是O（n）。將算法1第2步的j=arg maxj∈{3i，3i+1，3i+2}（pj/wj）置換為j=arg maxj∈{3i，3i+1，3i+2}（pj），則算法演化為NGROA［7］。

2基于項(xiàng)集的D{0-1}KP粒子群優(yōu)化算法

2.1基于項(xiàng)集的粒子修復(fù)與優(yōu)化算法貪婪策略

D{0-1}KP已有研究提出的不可行粒子貪婪修復(fù)策略［3，4，7］，均按照項(xiàng)價(jià)值密度大小對(duì)數(shù)據(jù)排序預(yù)處理。本文引入項(xiàng)集價(jià)值密度Ri（i∈{0，1，…，n－1}），按照Ri大小以項(xiàng)集為單位對(duì)數(shù)據(jù)進(jìn)行非遞增排列，之后按次序選取項(xiàng)集的項(xiàng)。文獻(xiàn)［8］給出了三種Ri算法如下：

R1i=max（e3i，e3i+1，e3i+2）（7）

R2i=∑2k=0e3i+k（8）

R3i=∑2k=0p3i+k∑2k=0w3i+k（9）

易見(jiàn)，R1i算法等效于GR-DKP［4］策略，結(jié)合NGROA算法思想，定義R4i如下：

R4i=e3i+2（10）

以下給出項(xiàng)集i兩種項(xiàng)選擇策略itemi：

item1i=maxj{ej|xj=1，j∈{3i，3i+1，3i+2}}（11）

item2i=3i+2如果 x3i+2=1

maxj{ej|xj=1，j∈{3i，3i+1}}其他

（12）

結(jié)合式（7）～（10）和（11）（12），得到八種D{0-1}KP基于項(xiàng)集的貪心修復(fù)優(yōu)化方法（group greedy repair and optimization algorithm，GGROA），如表1所示。

算法2第2～5步是對(duì)粒子x的修復(fù)操作，第6步是對(duì)粒子x的優(yōu)化操作，算法時(shí)間復(fù)雜度是O（n）。

2.2基于GGROA 的D{0-1}KP粒子群優(yōu)化算法

文獻(xiàn)［4］在構(gòu)造PSO-GRDKP算法中，采用了基礎(chǔ)離散粒子進(jìn)化式（4）～（6），學(xué)習(xí)因子c1、c2的取值是2。為避免粒子進(jìn)化公式和進(jìn)化參數(shù)對(duì)研究?jī)?nèi)容的影響，方便同一基準(zhǔn)條件下同類研究間的辨析，采用文獻(xiàn)［4］的方案構(gòu)造PSO-GGRDKP（PSO based GGROA for solving D{0-1}KP），偽代碼見(jiàn)算法3，其中參數(shù)m、z同算法2。

算法3PSO-GGRDKP（m，z）

輸入：3n項(xiàng)的價(jià)值向量P、重量向量W，背包容量C，種群規(guī)模N，進(jìn)化代數(shù)T， 學(xué)習(xí)常數(shù)c1=c2=2。

輸出：最佳粒子gbest和裝入背包總價(jià)值的近似最優(yōu)解fitness（gbest）。

1for i in range（0，n－1）：

Rmi=functionm（Pi，Wi）

2排列Rmi≥Rmi+1，i∈{0，…，n－1}，按項(xiàng)集價(jià)值密度Rmi非遞增次序?qū)㈨?xiàng)集下標(biāo)存入Hm［0，…，n－1］

3初始化種群population={（xi，vi）|i∈（1，…，N）}

4for i in range（1，N）：

xi，fitness（xi）=GGROA（Hm，itemz）

5best=index_max（{fitness（xi）|i∈{1，…，N}}）

6gbest=pbest=xbest

7t=0

8while tlt;T：

9for i in range（1，N）：

10for j in range（0，3n－1）：

vt+1ij=vtij+c1·r1·（ptbestj－xtij）+c2·r2·（gtbestj－xtij）

if （r3≥sig（vt+1ij））：xt+1ij=0

else： xt+1ij=1

11xt+1i，fitness（xt+1i）=GGROA（Hm，itemz）

12if （fitness（xt+1i）gt;fitness（pbest））：pbest=xt+1i

13if （fitness（pbest）gt;fitness（gbest））：gbest=pbest

14t=t+1

15return gbest，fitness（gbest）

算法3中r1、r2、r3是（0，1）的隨機(jī)數(shù)，第1步中functionm（m∈{1，2，3，4}）對(duì)應(yīng)四種項(xiàng)集價(jià)值密度計(jì)算函數(shù)，即式（7）～10），第10步sig（x）采用式（5），算法時(shí)間復(fù)雜度是O（n log n）+2O（n）+2O（nN）+T×［O（nN）+O（n）］，由于Nlt;n且Tlt;n，故PSO-GGRDKP算法時(shí)間復(fù)雜度是O（n3）。

3仿真實(shí)驗(yàn)與結(jié)果分析

3.1實(shí)驗(yàn)方案設(shè)計(jì)

D{0-1}KP數(shù)據(jù)集是觀察和評(píng)測(cè)算法性能的標(biāo)準(zhǔn)數(shù)據(jù)集［3］，數(shù)據(jù)集由逆強(qiáng)相關(guān)D{0-1}KP實(shí)例（IDKP）、強(qiáng)相關(guān)D{0-1}KP實(shí)例（SDKP）、弱相關(guān)D{0-1}KP實(shí)例（WDKP）和不相關(guān)D{0-1}KP實(shí)例（UDKP）四類數(shù)據(jù)組成，四類D{0-1}KP實(shí)例的數(shù)據(jù)規(guī)模分別為300≤ 3n≤3 000。為驗(yàn)證D{0-1}KP的各類貪婪修復(fù)策略性能特點(diǎn)，進(jìn)行兩組實(shí)驗(yàn)。實(shí)驗(yàn)1：采用八種基于項(xiàng)集貪婪修復(fù)優(yōu)化策略的D{0-1}KP粒子群算法實(shí)驗(yàn)，以探究八種基于項(xiàng)集貪婪修復(fù)優(yōu)化策略的可行性、性能以及與數(shù)據(jù)實(shí)例類型的適應(yīng)性關(guān)系。實(shí)驗(yàn)2：評(píng)測(cè)PSO-GRDKP［4］、PSO-NGROADKP、PSO-GGRDKP三種典型不可行個(gè)體貪婪修復(fù)方法的D{0-1}KP粒子群性能特點(diǎn)。兩組實(shí)驗(yàn)均以比較求解時(shí)間和解計(jì)算結(jié)果分析算法性能。所有實(shí)驗(yàn)均在ThinkStation P330計(jì)算機(jī)上進(jìn)行，電腦配置Intel CoreTM i7-8700 CPU-3.2 GHz、16 GB DDR4內(nèi)存、NVIDIA P2200顯卡，操作系統(tǒng)是Microsoft Windows 10 教育版，算法均使用Python3.6編碼。

記D{0-1}KP實(shí)例通過(guò)基本動(dòng)態(tài)規(guī)劃法計(jì)算得出的最優(yōu)解為opt、粒子群算法的粒子規(guī)模為200、進(jìn)化代數(shù)同項(xiàng)集數(shù)n，粒子群算法獨(dú)立運(yùn)算20次的近似最優(yōu)解最大值為best、平均值為mean、最差值為worst、平均時(shí)長(zhǎng)為T(mén)。

3.2實(shí)驗(yàn)1算法數(shù)據(jù)與分析

表3為數(shù)據(jù)規(guī)模3n=900和1 800的四類實(shí)例上運(yùn)行八種貪婪修復(fù)優(yōu)化方法的粒子群算法實(shí)驗(yàn)數(shù)據(jù)，PSO-GGRDKP算法名稱下標(biāo)編號(hào)對(duì)應(yīng)表2。

應(yīng)用八種貪婪修復(fù)策略對(duì)八個(gè)數(shù)據(jù)實(shí)例IDKP3、IDKP6、SDKP3、SDKP6、UDKP3、UDKP6、WDKP3、WDKP6分別獨(dú)立求解20次，20個(gè)求解結(jié)果分布情況箱線圖如圖1所示。

由表3和圖1可以看出，粒子群算法采用八種項(xiàng)集貪婪修復(fù)策略都是可行的，但不同的項(xiàng)集貪婪修復(fù)策略在同一類數(shù)據(jù)實(shí)例上存在顯著性能差異，相同的項(xiàng)集貪婪修復(fù)策略在不同類型實(shí)例上性能表現(xiàn)也有不同。同類數(shù)據(jù)的兩個(gè)實(shí)例，確定平均最優(yōu)近似解前三的貪心修復(fù)策略交集為該類數(shù)據(jù)較佳的算法，其中，IDKP：PSO-GGRDKP1、PSO-GGRDKP2，SDKP：PSO-GGRDKP1、PSO-GGRDKP5，

WDKP：PSO-GGRDKP1、PSO-GGRDKP8，UDKP：PSO-GGRDKP2、PSO-GGRDKP6。結(jié)合每種數(shù)據(jù)實(shí)例的平均時(shí)長(zhǎng)T，進(jìn)一步選擇各類數(shù)據(jù)實(shí)例時(shí)間性能較優(yōu)的求解算法，其中，IDKP：PSO-GGRDKP2，SDKP：PSO-GGRDKP5，WDKP：PSO-GGRDKP8，UDKP：PSO- GGRDKP2。

3.3實(shí)驗(yàn)2算法數(shù)據(jù)與分析

PSO-GRDKP、PSO-NGROADKP、PSO-GGRDKP算法實(shí)驗(yàn)數(shù)據(jù)如表4所示，其中PSO-GGRDKP算法根據(jù)實(shí)驗(yàn)1分析結(jié)果，選擇四類數(shù)據(jù)實(shí)例上的性能較優(yōu)的貪婪修復(fù)策略進(jìn)行實(shí)驗(yàn)。

從表4可以看出，三類貪婪修復(fù)優(yōu)化策略的粒子群算法求解質(zhì)量和時(shí)間性能各不相同。定義粒子群算法的解誤差率ERR=1－mean/opt，各數(shù)據(jù)實(shí)例的解誤差率平均值為ERR_AVE，該值越小，算法性能越優(yōu)。進(jìn)一步統(tǒng)計(jì)三類貪婪修復(fù)優(yōu)化粒子群算法四類數(shù)據(jù)實(shí)例的平均解誤差率與算法平均時(shí)長(zhǎng)如表5所示。表中三類貪婪修復(fù)優(yōu)化粒子群算法分別是PSO-GGRDKP、PSO-GRDKP、PSO-NGROADKP。

由表5可看出，在四類數(shù)據(jù)實(shí)例上，三類粒子群算法的平均解誤差率呈現(xiàn)一致趨勢(shì)：IDKPlt;WDKPlt;SDKPlt;UDKP ，即對(duì)IDKP實(shí)例求解誤差率最低，而UDKP實(shí)例的解誤差率最高。三類算法中，PSO-NGROADKP平均解誤差率最低，僅為0.2%，PSO-GGRDKP的平均解誤差率略高于PSO-NGROADKP、PSO-GRDKP分別是0.7%、0.4%。在四類數(shù)據(jù)實(shí)例上，PSO-GGRDKP的時(shí)間性能均顯著優(yōu)于PSO-GRDKP和PSO-NGROADKP，PSO-GGRDKP算法時(shí)間性能較PSO-GRDKP提升12.9%，較PSO-NGROADKP提升13.8%。三類粒子群算法的四類數(shù)據(jù)實(shí)例時(shí)間性能趨勢(shì)表現(xiàn)不一致，PSO-GGRDKP、PSO-NGROADKP、PSO-GRDKP算法時(shí)間性能表現(xiàn)最好的數(shù)據(jù)實(shí)例各自為WDKP、SDKP和IDKP。

進(jìn)一步探究算法解誤差率與數(shù)據(jù)類型之間的關(guān)聯(lián)性，表6給出了四類數(shù)據(jù)實(shí)例的項(xiàng)價(jià)值系數(shù)與項(xiàng)重量系數(shù)的相關(guān)系數(shù)ρ，項(xiàng)價(jià)值密度均值μ，項(xiàng)價(jià)值密度標(biāo)準(zhǔn)差σ。結(jié)合表5統(tǒng)計(jì)值，易見(jiàn)除SDKP實(shí)例外，在IDKP、WDKP、UDKP類型上，三種算法解誤差率與相關(guān)系數(shù)大小一致，即數(shù)據(jù)實(shí)例相關(guān)系數(shù)越大，則該實(shí)例上對(duì)應(yīng)算法的解誤差率越小。但SDKP相關(guān)系數(shù)略小于IDKP、略大于WDKP，其解誤差率卻高于WDKP。此外，SDKP與UDKP兩類數(shù)據(jù)實(shí)例的相關(guān)系數(shù)差異很大，但其算法解誤差率較為接近。從表6可以看出，項(xiàng)價(jià)值密度均值有IDKPμlt;WDKPμlt;SDKPμlt;UDKPμ，項(xiàng)價(jià)值密度標(biāo)準(zhǔn)差有IDKPσlt;WDKPσlt;SDKPσlt;UDKPσ， 這與四類數(shù)據(jù)對(duì)應(yīng)求解誤差率表現(xiàn)趨勢(shì)一致，說(shuō)明D{0-1}KP的貪婪修復(fù)優(yōu)化策略粒子群算法性能與項(xiàng)價(jià)值密度的均值、標(biāo)準(zhǔn)差等數(shù)據(jù)特征高度相關(guān)，這進(jìn)一步解釋了SDKP與UDKP性能表現(xiàn)較為相近的情況。

4結(jié)束語(yǔ)

本文在定義D{0-1}KP的項(xiàng)集價(jià)值密度概念基礎(chǔ)上，構(gòu)造了具有八種組合策略的不可行個(gè)體貪婪修復(fù)優(yōu)化方法（GGROA），以粒子群算法為例，進(jìn)一步構(gòu)造了PSO-GGRDKP算法以探究GGROA方法用于求解D{0-1}KP的可行性和性能。D{0-1}KP四類數(shù)據(jù)實(shí)例的算法運(yùn)行結(jié)果表明：

a）適合各類實(shí)例的GGROA算子分別為IDKP：PSO-GGRDKP2，SDKP：PSO-GGRDKP5，WDKP：PSO-GGRDKP8，UDKP：PSO- GGRDKP2；

b）與PSO-NGROADKP、PSO-GRDKP相比，PSO-GGRDKP平均解誤差率高于兩個(gè)算法，分別是0.7%、0.4%，而算法時(shí)間性能較兩個(gè)算法提升13.8%、12.9%；

c）PSO-GGRDKP、PSO-NGROADKP、PSO-GRDKP算法解誤差率與數(shù)據(jù)實(shí)例相關(guān)系數(shù)、項(xiàng)價(jià)值密度均值、項(xiàng)價(jià)值密度標(biāo)準(zhǔn)差等數(shù)據(jù)特征高度相關(guān)。

以上結(jié)果表明，PSO-GGRDKP算法的解誤差率略高于PSO-NGROADKP、PSO-GRDKP，但較顯著改善了D{0-1}KP的算法時(shí)間性能。

本文以粒子群算法為例，構(gòu)造D{0-1}KP的PSO-GGRDKP算法并驗(yàn)證其性能。受各類應(yīng)用GROA的改進(jìn)啟發(fā)式算法研究結(jié)果啟示，本文推斷在不同啟發(fā)式求解算法中使用GGROA的求解性能可能會(huì)有差異，限于篇幅，這將作為進(jìn)一步研究工作討論。近期，文獻(xiàn)［20］提出D{0-1}KP問(wèn)題粒子群算法的項(xiàng)集個(gè)體編碼方案，接下來(lái)考慮結(jié)合文獻(xiàn)［20］的工作改進(jìn)PSO-GGRDKP算法。

參考文獻(xiàn)：

［1］Guder J. Discounted knapsack problems for pairs of items ［D］. Nuremberg： University of Erlangen-Nurnberg， 2005.

［2］Guldan B. Heuristic and exact algorithms for discounted knapsack problems ［D］. Nuremberg： University of Erlangen-Nuremberg， 2007.

［3］賀毅朝， 王熙照， 李文斌， 等. 基于遺傳算法求解折扣{0-1}背包問(wèn)題的研究 ［J］. 計(jì)算機(jī)學(xué)報(bào)， 2016， 39（12）： 2614-2630. （He Yichao， Wang Xizhao， Li Wenbin， et al. Research on genetic algorithms for discounted{0-1}knapsack problem ［J］. China Journal of Computer， 2016， 39（12）： 2614-2630.）

［4］He Yichao， Wang Xizhao， He Yulin， et al. Exact and approximate algorithms for discounted{0-1}knapsack problem ［J］. Information Sciences， 2016， 369（11）： 634-647.

［5］Rong A， Figueira J R， Klamroth K. Dynamic programming based algorithms for the discounted{0-1}knapsack problem ［J］. Applied Mathematics amp; Computation， 2012， 218（12）： 6921-6933.

［6］Michalewicz Z， Schoenauer M. Evolutionary algorithms for constrained parameter optimization problems ［J］. Evolutionary Computation， 1996， 4（1）： 1-32.

［7］楊洋， 潘大志， 賀毅朝. 改進(jìn)修復(fù)策略遺傳算法求解折扣{0-1}背包問(wèn)題 ［J］. 計(jì)算機(jī)工程與應(yīng)用， 2018， 54（21）： 37-42. （Yang Yang， Pan Dazhi， He Yichao. Improved repair strategy genetic algorithm solve discount{0-1}knapsack problem ［J］. Computer Engineering and Applications， 2018， 54（21）： 37-42.）

［8］Wilbaut C， Todosijevic R， Hanafi S， et al. Heuristic and exact fixation-based approaches for the discounted 0-1 knapsack problem［EB/OL］. （2022-01-04）. http：//doi.org/10.48550/arxiv.2106.03438.

［9］Zhu Hong， He Yichao， Wang Xizhao， et al. Discrete differential evolutions for the discounted{0-1}knapsack problem ［J］. International Journal of Bio-Inspired Computation， 2017， 10（4）： 219-238.

［10］吳聰聰， 賀毅朝， 陳嶷瑛， 等. 變異蝙蝠算法求解折扣{0-1}背包問(wèn)題 ［J］. 計(jì)算機(jī)應(yīng)用， 2017， 37（5）： 1292-1299. （Wu Congcong， He Yichao， Chen Yiying， et al. Mutated bat algorithm for solving discounted{0-1}knapsack problem ［J］. Journal of Computer Applications， 2017， 37（5）： 1292-1299.）

［11］馮艷紅， 楊娟， 賀毅朝， 等. 差分進(jìn)化帝王蝶優(yōu)化算法求解折扣{0-1}背包問(wèn)題 ［J］. 電子學(xué)報(bào)， 2018， 46（6）： 1343-1350. （Feng Yanhong， Yang Juan， He Yichao， et al. Monarch butterfly optimization algorithm with differential evolution for the discounted{0-1 knapsack problem ［J］. Acta Electronica Sinica， 2018， 46（6）： 1343-1350.）

［12］Feng Yanhong， Wang Gaige. Binary moth search algorithm for discounted{0-1} knapsack problem ［J］. IEEE Access， 2018， 6： 10708-10719.

［13］徐小平， 徐麗， 王峰， 等. 基于Lagrange插值的學(xué)習(xí)猴群算法求解折扣{0-1}背包問(wèn)題 ［J］. 計(jì)算機(jī)應(yīng)用， 2020， 40（11）： 3113-3118. （Xu Xiaoping， Xu Li， Wang Feng， et al. Learning monkey algorithm based on Lagrange interpolation to solve discounted{0-1}knapsack problem ［J］. Journal of Computer Application， 2020， 40（11）： 3113-3118.）

［14］He Yichao， Wang Xizhao， Gao Suogang. Ring theory-based evolutionary algorithm and its application to D{0-1}KP ［J］. Applied Soft Computing， 2019， 77（4）： 714-722.

［15］Wu Congcong， Zhao Jianli， Feng Yanhong， et al. Solving discounted{0-1}knapsack problems by a discrete hybrid teaching-learning-based optimization algorithm ［J］. Applied Intelligence， 2020， 50（6）： 1872-1888.

［16］Kennedy J， Eberhart R C. Particle swarm optimization ［C］// Proc of IEEE International Conference On Neural Networks. Piscataway， NJ： IEEE Press， 1995： 1942-1948.

［17］Kennedy J， Eberhart R C. A discrete binary version of the particle swarm algorithm ［C］// Proc of IEEE International Conference on Systems， Man， and Cybernetics. Piscataway， NJ： IEEE Press，1997： 4104-4108.

［18］Bansal J C， Deep K. A modified binary particle swarm optimization for knapsack problems ［J］. Applied Mathematics and Computation， 2012， 218（22）： 11042-11061.

［19］麻榮永， 楊磊磊， 張智超. 基于粒子迭代位移和軌跡的粒子群算法C1、C2參數(shù)特性分析 ［J］. 數(shù)學(xué)計(jì)算： 中英文版， 2013， 2（4）： 109-115. （Ma Rongyong， Yang Leilei， Zhang Zhichao. Analysis the characteristic of C1、C2 based on the PSO of iterative shift and trajectory of particle ［J］. Mathematical Computation， 2013， 2（4）： 109-115）

［20］Truong T K. Different transfer functions for binary particle swarm optimization with a new encoding scheme for discounted{0-1}knapsack problem ［J］. Mathematical Problems in Engineering， 2021， 2021： article ID 2864607.

收稿日期：2021-12-18；修回日期：2022-02-14基金項(xiàng)目：蘭州市科技發(fā)展指導(dǎo)性計(jì)劃項(xiàng)目（2020-ZD-136）；西北師范大學(xué)研究生培養(yǎng)與課程改革項(xiàng)目（2020KGLX01009）；國(guó)家自然科學(xué)基金資助項(xiàng)目（61762080）

作者簡(jiǎn)介：代祖華（1971-），女，甘肅榆中人，副教授，碩導(dǎo)，博士，主要研究方向?yàn)榻M合優(yōu)化理論與算法、深度強(qiáng)化學(xué)習(xí)、自然語(yǔ)言處理（2812704000@qq.com）；周斌（1996-），男，湖南澧縣人，碩士研究生，主要研究方向?yàn)榻M合優(yōu)化理論與算法、深度強(qiáng)化學(xué)習(xí)；龍玉晶（1997-），女，湖南邵東人，碩士研究生，主要研究方向?yàn)榻M合優(yōu)化理論與算法、深度強(qiáng)化學(xué)習(xí)；王宗泉（1998-），男，河南范縣人，主要研究方向?yàn)榻M合優(yōu)化理論與算法、深度強(qiáng)化學(xué)習(xí).