折扣{0-1}背包問題的簡化新模型及遺傳算法求解

楊洋 潘大志 劉益 譚代倫

摘 要：當(dāng)前折扣{0-1}背包問題（D{0-1}KP）模型將折扣關(guān)系作為一個新的個體，導(dǎo)致求解過程必需采取修復(fù)法對個體編碼進(jìn)行修復(fù)，求解方式較少。針對求解方法單一的問題，通過改變模型中二進(jìn)制的編碼表達(dá)方式，提出折扣關(guān)系不在個體編碼中的表達(dá)方法。該方法首先，設(shè)定對任意折扣關(guān)系，當(dāng)且僅當(dāng)所涉及個體編碼值同時為1（即其乘積為1）時，折扣關(guān)系成立，據(jù)此建立簡化折扣{0-1}背包問題（SD{0-1}KP）模型;然后，針對SD{0-1}KP模型，基于杰出者保留策略（EGA），結(jié)合貪心策略（GRE），提出改進(jìn)遺傳算法——第一遺傳算法（FG）;最后，再結(jié)合罰函數(shù)法，提出求解SD{0-1}KP高精度罰函數(shù)法——第二遺傳算法（SG）。結(jié)果表明，SD{0-1}KP能夠完全覆蓋D{0-1}KP問題領(lǐng)域，與FirEGA相比，所提出的兩類算法在求解速度方面優(yōu)勢明顯，且SG算法首次引入罰函數(shù)法，有效地豐富了該問題的求解算法。

關(guān)鍵詞：折扣{0-1}背包問題;簡化折扣{0-1}背包問題;貪婪策略;近似計(jì)算;數(shù)學(xué)模型;遺傳算法

中圖分類號： TP18

文獻(xiàn)標(biāo)志碼：A

文章編號：1001-9081（2019）03-0656-07

Abstract： Current Discounted {0-1} Knapsack Problem （D{0-1}KP） model takes the discounted relationship as a new individual， so the repair method must be adopted in the solving process to repair the individual coding， making the model have less solving methods. In order to solve the problem of single solving method， by changing the binary code expression in the model， an expression method with discounted relationship out of individual code was proposed. Firstly， if and only if each involved individual encoding value was one （which means the product was one）， the discounted relationship was established. According to this setting， a Simplified Discounted {0-1} Knapsack Problem （SD{0-1}KP） model was established. Then， an improved genetic algorithm — FG （First Gentic algorithm） was proposed based on Elitist Reservation Strategy （EGA） and GREedy strategy （GRE） for SD{0-1}KP model. Finally， combining penalty function method， a high precision penalty function method — SG （Second Genetic algorithm） for SD{0-1}KP was proposed. The results show that the SD{0-1}KP model can fully cover the problem domain of D{0-1}KP. Compared with FirEGA （First Elitist reservation strategy Genetic Algorithm）， the two algorithms proposed have obvious advantages in solving speed. And SG algorithm introduces the penalty function method for the first time， which enriches the solving methods of the problem.

Key words： Simplified Discounted {0-1} Knapsack Problem （SD{0-1}KP）; greedy strategy; approximate calculation; mathematical model; Genetic Algorithm （GA）

0 引言

0-1背包問題（{0-1} Knapsack Problem， {0-1}KP）[1]作為一種在實(shí)際社會生產(chǎn)生活中應(yīng)用廣泛的數(shù)學(xué)模型，雖然{0-1}KP屬于NP-complete問題，但通過近似算法等元啟發(fā)式算法對于{0-1}KP模型刻畫的下料問題、資源調(diào)度、拆料切割方面有著優(yōu)異的求解效果[2-5]。在此類{0-1}KP中，物品的價值及質(zhì)量恒定為一個常量，不隨時間及個體選取產(chǎn)生任何變化。但在實(shí)際問題中，{0-1}KP中個體的價值及質(zhì)量不一定始終為一個定值，因而將{0-1}KP中個體價值質(zhì)量隨著時間變化而隨機(jī)變化的問題刻畫為隨機(jī)時變背包問題（Randomized Time-Varying Knapsack Problem， RTVKP）[6]，對于個體價值質(zhì)量隨著其他物品的選擇而變化的問題刻畫為折扣{0-1}背包問題（Discounted {0-1} Knapsack Problem， D{0-1}KP） [7-8]。

D{0-1}KP可以認(rèn)為是經(jīng)典{0-1}KP的一個拓展形式[7-11]，它刻畫了商業(yè)活動中物品銷售的捆綁銷售及折扣營銷等現(xiàn)象。因而在商業(yè)活動中，面對大量采購物品存在此類關(guān)系時，D{0-1}KP是一個更好地使商業(yè)價值最大化且具備廣闊應(yīng)用前景的數(shù)學(xué)模型。

D{0-1}KP模型由于約束條件過多，且編碼個體易于出現(xiàn)非正常編碼個體等原因，導(dǎo)致研究成果相對較少。Guder[7]和Guldan[8]兩人對基于單目標(biāo)和多目標(biāo)的D{0-1}KP模型進(jìn)行了刻畫及基礎(chǔ)性求解，但并未給出大規(guī)模實(shí)例的求解方式，同樣也未能對模型進(jìn)行進(jìn)一步的完善和簡化。此后，較多文獻(xiàn)利用算法在求解精度上對問題進(jìn)行了改進(jìn)[9-19]。對于啟發(fā)式算法則主要集中在如：核（core）算法[9] 及動態(tài)規(guī)劃[11]兩種算法;元啟發(fā)算法[10，12-18]則主要有遺傳算法[10]、帝王蝶算法[12-13]、烏鴉算法[15-16]等成果。而在優(yōu)化策略方面，則主要對貪婪算子進(jìn)行改進(jìn)[10，19]。

當(dāng)前D{0-1}KP模型由于將折扣關(guān)系作為獨(dú)立個體在編碼個體中進(jìn)行體現(xiàn)，非正常編碼過多，導(dǎo)致除修復(fù)法方法之外，如罰函數(shù)法等可以用于求解{0-1}KP的加速算法無法適用于D{0-1}KP[10]。為改變這一現(xiàn)狀，本文為D{0-1}KP模型設(shè)計(jì)新的二進(jìn)制編碼方式，簡化數(shù)學(xué)模型，擴(kuò)大求解方法，從而得到更優(yōu)良的解值。本文在第2章中，給出傳統(tǒng)D{0-1}KP模型的定義，針對模型存在的缺陷進(jìn)行分析。第3章中，通過給出相關(guān)基本定義，設(shè)計(jì)新的二進(jìn)制編碼方法，建立簡化折扣{0-1}背包問題（Simplified Discounted {0-1} Knapsack Problem， SD{0-1}KP）模型。在第4章中介紹基于杰出者保留策略（Elitist Reservation Strategy， EGA）遺傳算法求解機(jī)制。結(jié)合加速貪心算法（Greedy， GRE），給出第一遺傳算法（First Genetic Algorithm， FG）算法偽代碼。再結(jié)合罰函數(shù)法，首次提出可適用于SD{0-1}KP問題的混合罰函數(shù)法，給出SG算法偽代碼。在第5章中，給出四類大規(guī)模D{0-1}KP實(shí)例各10個，并轉(zhuǎn)化為SD{0-1}KP實(shí)例，進(jìn)行求解。結(jié)果表明：SD{0-1}KP能夠完全覆蓋D{0-1}KP在實(shí)際商業(yè)折扣活動的模型功能，同時通過減少對于額外修復(fù)的GROA（Greedy Repair Optimization Algorithm） [10]的使用，算法速度提升明顯。且第一遺傳（First Gentic algorithm， FG）算法和第二遺傳（Second Genetic algorithm， SG）算法對于求解SD{0-1}KP均能夠有效應(yīng)用，且在綜合性能上FG算法更優(yōu)于SG算法。

1.2 D{0-1}KP模型缺陷

在傳統(tǒng)D{0-1}KP模型中，雖然刻畫商品之間的“折扣”關(guān)系，但整體系統(tǒng)略顯復(fù)雜，其約束條件過多，甚至因?yàn)閭€體的編碼問題，導(dǎo)致傳統(tǒng){0-1}KP中的加速算法無法有效利用，對于問題求解造成較大影響。針對D{0-1}KP模型中個體編碼方式，以下主要從兩方面進(jìn)行缺陷分析。

一方面，D{0-1}KP個體非正常編碼過多。在傳統(tǒng)二進(jìn)制個體編碼情況下，物品A、物品B及假設(shè)出來的物品C至多只能取一個。這種方式直接導(dǎo)致元啟發(fā)式算法中，在n個物體及m（m≤2n-n-1）個折扣關(guān)系問題中，正常編碼個體的概率僅為（（m+1）/2m）n[10]，求解過程中必須對產(chǎn)生的個體進(jìn)行大量的編碼修復(fù)工作，保證算法收斂。所以對于求解D{0-1}KP，任意元啟發(fā)式算法中的迭代尋優(yōu)都必須要采取編碼修復(fù)，有些算法甚至需要采取多次個體編碼修復(fù)。如遺傳算法中，在變異算子和交叉算子對個體進(jìn)行處理后，都必須要采取編碼修復(fù)，大大增加了算法收斂所需要的迭代時間。

另一方面，求解D{0-1}KP加速方法受限。對于{0-1}KP模型中常見的加速求解方式，如罰函數(shù)法等，基本無法在D{0-1}KP對問題進(jìn)行有效求解，其結(jié)果誤差無法接受[10，20]。這使得求解D{0-1}KP模型可選方法大為減少，對于模型的求解存在不利。

綜上，對于現(xiàn)有D{0-1}KP模型，由約束條件（2）可知，同一項(xiàng)集內(nèi)的物品至多只能選擇一個，這一特性導(dǎo)致在求解過程中，非正常個體編碼過多，進(jìn)而必須通過采取修復(fù)操作對個體編碼進(jìn)行修復(fù)，最終大幅度增加計(jì)算時長。對于這一難點(diǎn)，本文通過提出SD{0-1}KP模型對問題進(jìn)行求解。

當(dāng)然，雖然D{0-1}KP模型存在明顯不足，但卻是當(dāng)前唯一可以對{0-1}KP模型中對于“折扣”關(guān)系刻畫的有效模型。故考慮針對D{0-1}KP模型設(shè)計(jì)新的編碼方法，對原模型進(jìn)行簡化，構(gòu)建模型的求解方法。

2 D{0-1}KP問題的簡化數(shù)學(xué)模型

傳統(tǒng)D{0-1}KP模型中由于將物品A和B的折扣關(guān)系假設(shè)為物品C，從而導(dǎo)致模型缺陷，故考慮在新數(shù)學(xué)模型中，通過設(shè)計(jì)新的編碼方式，避免出現(xiàn)物品C的情況，克服原模型出現(xiàn)的缺陷。

2.1 兩個物品折扣關(guān)系的新編碼方式

對于物品A和B的折扣關(guān)系，在原有的D{0-1}KP模型中，通過虛構(gòu)物品C來表示，得到3個選擇項(xiàng)，通過一個三元組二進(jìn)制向量X=[x1，x2，x3]∈{0，1}3來表示物品的選擇情況。其中，分量xj（1≤j≤3）表示對應(yīng)的項(xiàng)是否被裝入背包中。在向量X的所有8種組合中，只有[0，0，0]、[1，0，0]、[0，1，0]和[0，0，1]是正常編碼，分別表示全部不選、選擇物品A、選擇物品B和選擇物品C，而其余4種組合均是非正常編碼，在M個這個關(guān)系對應(yīng)的編碼中，其正常編碼率極低，這導(dǎo)致用遺傳算法求解時必須大量采用編碼修復(fù)操作。

為提正常編碼率，減少編碼修復(fù)操作，就需要對物品折扣關(guān)系重新設(shè)計(jì)編碼方式。在新的編碼方式中并不將物品A和B同時選擇的折扣關(guān)系虛構(gòu)成一個物品，其定義如下。

根據(jù)定義2，在新的編碼方式中，兩個物品的折扣關(guān)系只需要一個二元組的二進(jìn)制向量來表示，對應(yīng)的四種編碼組合全是正常編碼，因而在求解模型時，不需要采用修復(fù)操作。

針對定義1中D{0-1}KP模型給出了折扣關(guān)系R中物品A和B對應(yīng)的折扣重量系數(shù)，為了便于新編碼方法的實(shí)施，需要給出折扣關(guān)系對應(yīng)的折扣量d。

2.2 D{0-1}KP問題的簡化模型

根據(jù)D{0-1}KP問題的描述，每個折扣關(guān)系中只包含兩個物品，為采用定義2的新編碼方式，我們需要利用定義3給出的折扣量計(jì)算方式，對定義1中的D{0-1}KP模型進(jìn)行重新刻畫，可得到折扣0-1背包問題的簡化數(shù)學(xué)模型（記為：SD{0-1}KP）。

由定義2可知，通過采用SD{0-1}KP模型刻畫問題，在求解過程中，個體編碼始終保持為正常編碼;因此，新模型中的編碼個體不再需要使用修復(fù)操作，大大減少了問題的求解時長。同時，SD{0-1}KP模型的求解可采用此前不能使用的罰函數(shù)法、分離法、純正法[21-22]等算法，使得SD{0-1}KP相對于D{0-1}KP在算法求解的選擇上進(jìn)行了大規(guī)模的延伸拓展。

3 用遺傳算法求解SD{0-1}KP

遺傳算法（Genetic Algorithm， GA）[20-29]是一種借鑒“適者生存”這一理念的迭代進(jìn)化算法，由Holland教授于1975年提出。因該算法在函數(shù)約束條件上要求少、限值弱，且具備全局搜索能力[28-29]，因而在生產(chǎn)調(diào)度、圖像處理、數(shù)值計(jì)算與優(yōu)化等領(lǐng)域[24-29]應(yīng)用廣泛延伸拓展性強(qiáng)且算法相對成熟完善。Rudolph[23]通過對馬爾可夫鏈討論支出傳統(tǒng)CGA（Canonical Genetic Algorithm）無法保證全局收斂的性質(zhì)，而在引入杰出者保留策略后，能夠?qū)崿F(xiàn)EGA（Genetic Algorithm based on Elitist Reservation Strategy）在全局收斂性。為盡可能達(dá)到算法求解的精度，本文沿用杰出者保留策略遺傳算法（EGA）對SD{0-1}KP求解。

遺傳算法通過選擇算子（SElection Operator， SEO）、交叉算子（CRossover Operator， CRO）和變異算子（MUtation Operator， MUO）三類基本算子實(shí)現(xiàn)種群擇優(yōu)、更替等功能。有關(guān)遺傳算法的具體內(nèi)容可參考文獻(xiàn)[26-29]，此處限于篇幅不再贅述。

基于SD{0-1}KP模型，本文提出兩種分別混合貪婪算法和罰函數(shù)法的遺傳算法，記為第一遺傳（FG）算法和第二遺傳（SG）算法。因?yàn)閮深愃惴ㄔ谇蠼膺^程中始終保持個體編碼正常，因而大大減少求解時長。

3.1 求解SD{0-1}KP第一遺傳算法

對于遺傳算法在交叉操作和變異操作時，往往導(dǎo)致個體編碼所對應(yīng)的重量不能有效利用完背包容量或超出背包容量，不能達(dá)到最優(yōu)解，這使得遺傳算法種群中較多個體不能有效投入使用，影響算法迭代收斂。在運(yùn)用遺傳算法對問題進(jìn)行求解時，往往通過混合其他算子可以對問題進(jìn)行加速算法收斂或者提升計(jì)算精度，通常有罰函數(shù)法、修復(fù)法、純正法和分離法等[6-7]。對于不同情況，不同算法各有優(yōu)勢和劣勢，但彼此互斥。本文采取貪婪算法和罰函數(shù)法對算法作出改進(jìn)。

3.1.1 貪婪策略

貪婪算法（GREedy algorithm， GRE）[30-31]作為一種求解{0-1}KP的一種重要加速算子，因?yàn)槠渌惴ê唵沃苯?，對于KP適應(yīng)度高[24]而受到廣泛的使用。針對遺傳算法，基于貪心策略提出一種優(yōu)化編碼個體的貪心修復(fù)與優(yōu)化算法GRE。本文所針對的問題為單一目標(biāo)，不考慮多目標(biāo)情況，故而相對簡單。

貪婪算法應(yīng)用于背包問題，以非增序列的價值效率ei=pi/wi作為物品選取的優(yōu)先級指標(biāo)。對于SD{0-1}KP模型而言，雖然相對于D{0-1}KP模型，不將折扣關(guān)系作為獨(dú)立個體在編碼中進(jìn)行體現(xiàn)，但在貪心加速的時候，仍然需要將任意折扣關(guān)系作為一個獨(dú)立的個體進(jìn)行價值效率的排序。

由定義4知，n個折扣關(guān)系對應(yīng)的項(xiàng)（或物品）組合對應(yīng)價值密度編號范圍為2n+1～3n，與2n個單一項(xiàng)（或物品）的價值密度一起共有3n項(xiàng)。通過對ek（1≤k≤3n）排序，確定組合的優(yōu)先選擇順序，并按照價值密度進(jìn)行從高到低選擇。

在GRE算法中，首先通過1）～3）步生成折扣關(guān)系的價值和重量向量，其時間復(fù)雜度為O（T），并利用4）步進(jìn)行儲存，然后利用5）～6）步按照價值密度對折扣選擇進(jìn)行排序，其時間復(fù)雜度為O（3n）。通過6）步生成選擇矩陣。通過7）～17）步對個體未能有效利用的背包容量進(jìn)行物品選擇，其時間復(fù)雜度為O（3nK）。所以GRE的算法時間復(fù)雜度為O（n2）。

3.1.2 第一遺傳算法

在FG中，首先利用第1）～3）步設(shè)定初始參數(shù)，利用4）步對初代個體進(jìn)行貪心修復(fù)。在5）～14）步的循環(huán)過程中，通過6）步進(jìn)行交叉操作、7）步進(jìn)行變異操作。并通過8）～12）步在上一代的最優(yōu)個體和新產(chǎn)生的群體進(jìn)行最優(yōu)值篩選，隨后通過13）步進(jìn)行選擇操作產(chǎn)生下一代新的群體。最后15）步輸出最優(yōu)個體編碼及其價值。不難得到FG的算法時間復(fù)雜度為O（n3）。

3.2 求解SD{0-1}KP第二遺傳算法

求解D{0-1}KP，現(xiàn)有求解方法較多運(yùn)用貪婪加速情況[5-6]。為突出SD{0-1}KP模型的廣泛性，本文首次提出混合罰函數(shù)優(yōu)化的遺傳算法，記為第二遺傳算法（SG）。

3.2.1 罰函數(shù)法

3.2.2 第二遺傳算法

罰函數(shù)加速算法能夠廣泛應(yīng)用于個體編碼算法中，但需要保障個體編碼盡可能為正常編碼個體[32]。在傳統(tǒng)D{0-1}KP模型中，n個項(xiàng)集規(guī)模的個體編碼正常概率僅為（1/2）n，導(dǎo)致罰函數(shù)法求解D{0-1}KP誤差不可接受?；赟D{0-1}KP，首次提出混合罰函數(shù)的遺傳算法SG。

在PSEO中，首先利用1）步實(shí)現(xiàn)EGA過程。2）～3）步對個體編碼進(jìn)行折扣計(jì)算。4）步混合罰函數(shù)。5）～15）步進(jìn)行輪盤賭操作，實(shí)現(xiàn)選擇操作過程。最后利用16）步輸出子代。類比于算法FG，不難得到PSEO的算法時間復(fù)雜度為O（n2）。因SG算法與FG僅在SEO和PSEO的選擇操作過程略有不同，其余完全一樣，此處限于篇幅對SG算法偽代碼不再贅述。

4 實(shí)例計(jì)算與比較

在本章中，沿用文獻(xiàn)[10]中所提出的四類D{0-1}KP實(shí)例數(shù)據(jù)，且每種數(shù)據(jù)各有規(guī)模依次等量遞增的數(shù)據(jù)10種。關(guān)于數(shù)據(jù)的具體闡述可參考文獻(xiàn)[10]。通過前述簡易算法，將經(jīng)過折扣后的整個折扣關(guān)系組合價值Wi（1≤i≤n）轉(zhuǎn)化為折扣量di（1≤i≤n），因方法簡單，限于文章篇幅不再贅述。將轉(zhuǎn)化得到實(shí)例記為不相關(guān)SD{0-1}KP實(shí)例（Uncorrelated instances of SD{0-1}KP， SUDKP），弱相關(guān)SD{0-1}KP實(shí)例（Weakly correlated instances of SD{0-1}KP， SWDKP），強(qiáng)相關(guān)SD{0-1}KP實(shí)例（Strongly correlated instances of SD{0-1}KP， SSDKP）和逆向強(qiáng)相關(guān)SD{0-1}KP實(shí)例（Inverse Strongly correlated instances of SD{0-1}KP， SIDKP）。

由于本文所提出新算法FG和SG與文獻(xiàn)[10]中FirEGA（First Elitist reservation strategy Genetic Algorithm）選擇算法框架基本一致，通過GRE算法求解SD{0-1}KP的形式未發(fā)生改變，故而在遺傳算法中的交叉算子pc和變異算子pm具體數(shù)值的設(shè)定對于問題的求解而言，沿用文獻(xiàn)[10]中所求得參量，即pc=0.8，pm=0.01，同時設(shè)定種群規(guī)模為50。對于SG算法中懲罰因子的設(shè)定pe=2。

本文使用計(jì)算機(jī)基本配置為：Intel Core i7-8700 CPU @3.2GHz，8GB DDR4L，Microsoft Windows 10家庭版。利用Matlab 7.0進(jìn)行問題進(jìn)行求解，并將結(jié)果繪制成圖。

4.1 FG和SG求解結(jié)果

通過運(yùn)用FG和SG對上述所有數(shù)據(jù)進(jìn)行計(jì)算，所得結(jié)果見表1。其中Opt為通過動態(tài)規(guī)劃法（Dynamic Programming of Discounted Knapsack Problem， DPDKP）求解得到所給數(shù)據(jù)的實(shí)際最優(yōu)解值，也即問題的理想最優(yōu)解。此外，為了有效體現(xiàn)模型改進(jìn)后的結(jié)果比對，引用文獻(xiàn)[10]實(shí)驗(yàn)數(shù)據(jù)FirEGA。Best、Worst和Mean分別為FG和SG在30次獨(dú)立計(jì)算中所得最優(yōu)解、最差解及期望。本文考慮比較上述三種算法在求解SD{0-1}KP中的具體求解精度，為了更為明顯地展示兩種算法在算法精度方面的比較，通過計(jì)算近似比差率來作為分析數(shù)據(jù)結(jié)果主要參數(shù)。其中，1-Best/Opt、1-Mean/Opt、1-Worst/Opt為最優(yōu)解近似差率、期望值近似差率和最差解近似差率。Time1、Time2、Time3分別表示FirEGA、FG和SG三類算法在求解實(shí)例時，30次重復(fù)獨(dú)立計(jì)算的運(yùn)行總時間（單位：秒）。

4.2 FG和SG求解精度及求解速度分析

表1數(shù)據(jù)表明：FirEGA求解SUDKP實(shí)例最優(yōu)值近似比差異率在7.040%～12.610%，平均值和最差值的近似比差異率在8.090%～14.410%，為可接受范圍內(nèi);FG求解SUDKP實(shí)例的最優(yōu)值近似比差異率在0.604%～1.287%，平均值和最差值的近似比差異率在0.874%～2.193%。SG算法求解SUDKP實(shí)例最優(yōu)值近似比差異率在0.604%～1.287%，平均值和最差值的近似比差異率在0.699%～2.243%。

FirEGA求解SWDKP實(shí)例的最優(yōu)值近似比差異率在0.237%～0.928%，平均值的近似比差異率在0.671%～2.745%;FG算法求解SWDKP實(shí)例的最優(yōu)值近似比差異率在0.044%～0.180%，平均值和最差值的近似比差異率在0.091%～0.363%;SG算法求解SWDKP實(shí)例的最優(yōu)值、平均值和最差值的近似比差異率在0.044%～0.180%和0.093%～0.418%。

用FirEGA求解SSDKP1-SSDKP10實(shí)例的最優(yōu)值近似比差異率在1.050%～2.559%，平均值和最差值的近似比差異率在1.162%～4.056%;FG算法求解SSDKP實(shí)例的最優(yōu)值近似比差異率在0.244%～0.437%，平均值和最差值的近似比差異率在0.572%～1.420%;SG算法求解SSDKP實(shí)例的最優(yōu)值近似比差異率在0.244%～0.437%，平均值和最差值的近似比差異率在0.440%～1.519%。

對于SIDKP1～SIDKP10共10類SD{0-1}KP實(shí)例求解，F(xiàn)irEGA算法的最優(yōu)值近似比差異率在0.000%～0.508%，平均值的近似比差異率在0.040%～5.071%;FG算法求解SIDKP實(shí)例的最優(yōu)值近似比差異率在0.000%～0.020%，平均值和最差值的近似比差異率在0.001%～0.083%;SG算法求解SIDKP實(shí)例的最優(yōu)值近似比差異率在0.000%～0.020%，平均值和最差值的近似比差異率為0.001%～0.120%。

為了更加直觀展示計(jì)算結(jié)果精度，將三種算法求解SUDKP等四類SD{0-1}KP實(shí)例的最優(yōu)值和平均值近似比差異率以曲線圖形式刻畫出來，如圖1～8。綜合圖1～8可知，F(xiàn)G算法與SG算法在最優(yōu)值方面基本一致，個體實(shí)例所得略有不同，但相對于FirEGA算法而言，有顯著性提升。

通過表1所得數(shù)據(jù)，不難發(fā)現(xiàn)，對于算例規(guī)模較小實(shí)例，三類算法計(jì)算時長較為接近，但隨著算例規(guī)模的增長，F(xiàn)irEGA算法與FG、SG算法相比，計(jì)算時長太長。

由實(shí)驗(yàn)結(jié)果對比可得，SD{0-1}KP模型通過采用定義2中的編碼方式，使同一項(xiàng)集中的個體在編碼中不相互影響，減少求解過程中的修復(fù)操作，大大減少求解時長，同時對于求解精度有小幅度提升。

5 結(jié)語

本文通過改進(jìn)D{0-1}KP中個體編碼的表達(dá)方式，進(jìn)而提出SD{0-1}KP模型?；贓GA算法、混合貪婪算法與罰函數(shù)法，提出FG和SG兩類算法對SD{0-1}KP實(shí)例進(jìn)行求解。數(shù)據(jù)結(jié)果綜合表明：FG和SG對于SD{0-1}KP在求解精度、計(jì)算效率兩方面有顯著性提升?？傮w看來，通過SD{0-1}KP簡化D{0-1}KP，減少約束條件，從而加速求解、提升求解精度是確實(shí)可行的一種方法。此外，通過SD{0-1}KP拓展了D{0-1}KP的加速求解方法，但是較多數(shù)據(jù)未能跳出貪心算法最優(yōu)解，下一步不妨考慮通過其他方法對此類問題進(jìn)行有效求解，如改進(jìn)其他元啟發(fā)式算法對SD{0-1}KP進(jìn)行求解。同時，無論SD{0-1}KP還是D{0-1}KP，其模型與實(shí)際情況相比，條件假設(shè)過強(qiáng)，也可考慮削減模型假設(shè)方面條件，尤其是考慮盡可能削弱“項(xiàng)集”這一假設(shè)，使得模型更加貼合實(shí)際問題。

參考文獻(xiàn) （References）

[1] DANTZIG G B. Discrete-variable extremum problems [J]. Operations Research， 1957， 5（2）： 266-277.

[2] KELLERER H， PFERSCHY U， PISINGER D. Knapsack Problems [M]. Berlin： Springer， 2004： 1-445.

[3] KARP R M， MILLER R E， THATCHER J W. Reducibility among combinatorial problems [J]. Journal of Symbolic Logic， 2010， 40（4）： 618-619.

[4] MARTELLO S， TOTH P. Knapsack Problems： Algorithms and Computer Implementations [M]. New York： John Wiley & Sons， 1990： 13-102.

[5] 王熙照，賀毅朝.求解背包問題的演化算法[J].軟件學(xué)報，2017，28（1）：1-16.（WANG X Z， HE Y C. Evolutionary algorithms for knapsack problems [J]. Journal of Software， 2017， 28（1）： 1-16.）

[6] 賀毅朝，王熙照，李文斌，等.求解隨機(jī)時變背包問題的精確算法與進(jìn)化算法[J].軟件學(xué)報，2017，28（2）：185-202.（HE Y C， WANG X Z， LI W B， et al. Exact algorithms and evolutionary algorithms for randomized time-varying knapsack problem [J]. Journal of Software， 2017， 28（2）：185-202.）

[7] GUDER J. Discounted knapsack problems for pairs of items [D]. Diplomarbeit， University of Erlangen-Nrnberg

Erlangen： Friedrich-Alexander-Universitt Erlangen-Nürnberg， 2005.

[8] GULDAN B. Heuristic and exact algorithms for discounted knapsack problems [D]. Nuremberg： University of Erlangen-Nuremberg

Erlangen： Friedrich-Alexander-Universitt Erlangen-Nürnberg， 2007.

[9] RONG A. FIGUEIRA J R. KLAMROTH K. Dynamic programming based algorithms for the discounted {0-1} knapsack problem [J]. Applied Mathematics and Computation， 2012， 218（12）： 6921-6933.

[10] 賀毅朝，王熙照，李文斌，等.基于遺傳算法求解折扣{0-1}背包問題的研究[J].計(jì)算機(jī)學(xué)報，2016，39（12）：2614-2630.（HE Y C， WANG X Z， LI W B， et al. Research on genetic algorithms for the discounted {0-1} knapsack problem [J]. Chinese Journal of Computers， 2016，39（12）：2614-2630.）

[11] HE Y-C， WANG X-Z， HE Y-L， et al. Exact and approximate algorithms for discounted {0-1} knapsack problem [J]. Information Sciences， 2016， 369： 634-647.

[12] FENG Y， WANG G-G， LI W， et al. Multi-strategy monarch butterfly optimization algorithm for discounted {0-1} knapsack problem [J]. Neural Computing and Applications， 2018， 30（10）：3019-3036.

[13] 馮艷紅，楊娟，賀毅朝，等.差分進(jìn)化帝王蝶優(yōu)化算法求解折扣{0-1}背包問題[J].電子學(xué)報，2018，46（6）：1343-1350.（FENG Y H， YANG J， HE Y C， 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.）

[14] FENG Y， WANG G-G. Binary moth search algorithm for discounted {0-1} knapsack problem [J]. IEEE Access， 2018， 6（99）：10708-10719.

[15] 劉雪靜，賀毅朝，路鳳佳，等.基于Lévy飛行的差分烏鴉算法求解折扣{0-1}背包問題[J].計(jì)算機(jī)應(yīng)用，2018，38（2）：433-442.（LIU X J， HE Y C， LU F J， et al. Differential crow search algorithm based on Lévy flight for solving discount {0-1} knapsack problem [J]. Journal of Computer Applications， 2018， 38（2）： 433-442.）

[16] 劉雪靜，賀毅朝，路鳳佳，等.基于差分演化策略的混沌烏鴉算法求解折扣{0-1}背包問題[J].計(jì)算機(jī)應(yīng)用，2018，38（1）：137-145.（LIU X J， HE Y C， LU F J， et al. Chaotic crow search algorithm based on differential evolution strategy for solving discount {0-1} knapsack problem [J]. Journal of Computer Applications， 2018，38（1）：137-145.）

[17] 吳聰聰，賀毅朝，陳嶷瑛，等.變異蝙蝠算法求解折扣{0-1}背包問題[J].計(jì)算機(jī)應(yīng)用，2017，37（5）：1292-1299.（WU C C， HE Y C， CHEN Y Y， et al. Mutated bat algorithm for solving discounted {0-1} knapsack problem[J]. Journal of Computer Applications， 2017， 37（5）： 1292-1299.）

[18] 劉雪靜，賀毅朝，吳聰聰，等.基于細(xì)菌覓食算法求解折扣{0-1}背包問題的研究[J].計(jì)算機(jī)工程與應(yīng)用，2018，54（2）：155-162.（LIU X J， HE Y C， WU C C， et al. Research on bacterial foraging optimization algorithm for discounted {0-1} knapsack problem [J]. Computer Engineering and Applications， 2018， 54（2）： 155-162.）

[19] 楊洋，潘大志，賀毅朝.改進(jìn)修復(fù)策略遺傳算法求解折扣{0-1}背包問題 [J/OL].計(jì)算機(jī)工程與應(yīng)用，2018 [2018-07-30].http：//kns.cnki.net/ kcms/detail/11.2127.TP.20180319.1806.006.html.

（YANG Y， PAN D Z， HE Y C. Improved repair strategy genetic algorithm solve discount {0-1} knapsack problem [J]. Computer Engineering and Applications， 2018 [2018-07-30]. http：//kns.cnki.net/kcms/detail/11.2127.TP.20180319.1806.006.html.）

[20] MICHALEWICZ Z， SCHOENAUER M. Evolutionary algorithms for constrained parameter optimization problems [J]. Evolutionary Computation， 1996， 4（1）：1-32.

[21] RUNARSSON T P， YAO X. Stochastic ranking for constrained evolutionary optimization [J]. IEEE Transactions on Evolutionary Computation， 2000， 4（3）： 284-294.

[22] COELLO C A. Theoretical and numerical constraint-handling techniques used with evolutionary algorithm： a survey of the state of art [J]. Computer Methods in Applied Mechanics and Engineering， 2002， 191（11/12）： 1245-1287.

[23] RUDOLPH G. Convergence analysis of canonical genetic algorithms [J]. IEEE Transactions on Neural Networks， 1994， 5（1）： 96-101.

[24] GOLDBERG D E. Genetic algorithms in search [J]. Optimization and Machine Learning， 1989， 13（7）： 2104-2116.

[25] Sampson J R. Adaptation in Natural and Artificial Systems （John H. Holland）[J]. SIAM Review， 1976， 18（3）：53.

HOLLAND J H. Adaptation in Natural and Artificial Systems [M]. Cambridge， MA： MIT Press， 1992： 1-13.

[26] SCHMITT L M. Theory of genetic algorithms [J]. Amsterdam， Netherlands. Elsevier Science Publishers Ltd. 2001： 1-13.

SCHMITT L M. Theory of genetic algorithms [J]. Theoretical Computer Science， 2001， 259（1/2）： 1-61.

[27] SIVANANDAM S N， DEEPA S N. Introduction to Genetic Algorithms [M]. Berlin： Springer， 2008： 1-19.

[28] 陳國良，王熙法，莊鎮(zhèn)泉，等.遺傳算法及其應(yīng)用[M].北京：人民郵電出版社，1999：1-25.（CHEN G L， WANG X F， ZHUANG Z Q， et al. Genetic Algorithm and Its Application [M]. Beijing： Posts & Telecom Press， 1999： 1-25.）

[29] 劉勇.非數(shù)值并行算法.第二冊，遺傳算法[M]. 北京：科學(xué)出版社，1995：36-45.（LIU Y. Non-numerical Parallel Algorithm. Book 2， Genetic Algorithm [M]. Beijing： Science Press， 1995： 36-45.）

[30] PIRKUL H. A heuristic solution procedure for the multiconstraint zero-one knapsack problem [J]. Naval Research Logistics， 1987， 34（2）： 161-172.

[31] LV J， WANG X， HUANG M， et al. Solving 0-1 knapsack problem by greedy degree and expectation efficiency [J]. Applied Soft Computing， 2016， 41（C）：94-103.

[32] TESSEMA B， YEN G G. An adaptive penalty formulation for constrained evolutionary optimization [J]. IEEE Transactions on Systems， Man and Cybernetics—Part A： Systems and Humans， 2009， 39（3）： 565-578.