求解帶有利用率懲罰背包問(wèn)題的參數(shù)自適應(yīng)差分進(jìn)化算法

劉靜宜　韓海燕

【摘 要】本文研究一類(lèi)新型的背包問(wèn)題，特征主要體現(xiàn)在目標(biāo)函數(shù)不僅要最大化裝載物品的價(jià)值，同時(shí)還包含關(guān)于背包利用率的凸型罰函數(shù)。首先分析該問(wèn)題的線性松弛最優(yōu)解性質(zhì)，以揭示整數(shù)最優(yōu)解的結(jié)構(gòu)特征。為了有效求解該問(wèn)題，設(shè)計(jì)了一種參數(shù)自適應(yīng)差分進(jìn)化算法。該算法中提出變異和交叉參數(shù)的自適應(yīng)選擇方法，在進(jìn)化的過(guò)程中可以動(dòng)態(tài)評(píng)估每組被選參數(shù)的性能，并用于指導(dǎo)下一個(gè)迭代過(guò)程的參數(shù)配置，從而避免了基本差分進(jìn)化算法中參數(shù)選擇的困難。實(shí)驗(yàn)結(jié)果顯示提出的參數(shù)自適應(yīng)差分進(jìn)化算法性能顯著優(yōu)于基本差分進(jìn)化算法，說(shuō)明新算法在求解懲罰背包及類(lèi)似問(wèn)題上的有效性和穩(wěn)定性。

【關(guān)鍵詞】背包問(wèn)題；利用率懲罰；參數(shù)自適應(yīng)；差分進(jìn)化算法

0 引言

背包問(wèn)題是運(yùn)籌學(xué)和管理科學(xué)領(lǐng)域中一類(lèi)重要的NP-難組合最優(yōu)化問(wèn)題，對(duì)其研究具有重要的理論意義。背包問(wèn)題在工業(yè)生產(chǎn)管理與物流作業(yè)中有著廣泛的應(yīng)用，例如資源分配，貨物裝載等，因此對(duì)其研究也具有重要的應(yīng)用價(jià)值。本文研究一類(lèi)新型的背包問(wèn)題，特征主要體現(xiàn)在目標(biāo)函數(shù)不僅要最大化裝載物品的價(jià)值，同時(shí)還包含關(guān)于背包利用率的凸型罰函數(shù)。該問(wèn)題最早作為子問(wèn)題出現(xiàn)在動(dòng)態(tài)環(huán)境下物流配送網(wǎng)絡(luò)的運(yùn)輸與庫(kù)存集成問(wèn)題中[1]。文獻(xiàn)[1]將動(dòng)態(tài)環(huán)境下物流配送網(wǎng)絡(luò)的運(yùn)輸與庫(kù)存集成問(wèn)題建模為非線性的廣義分配問(wèn)題，并將原問(wèn)題重新建模問(wèn)集合劃分模型，提出基于列生成的分支-定價(jià)算法求解，列生成算法的價(jià)格子問(wèn)題就是帶有利用率懲罰背包問(wèn)題。

針對(duì)背包問(wèn)題及相關(guān)擴(kuò)展問(wèn)題，已經(jīng)有大量的研究。文獻(xiàn)[2-4]提出改進(jìn)的聲搜索算法求解0-1背包問(wèn)題， 改進(jìn)點(diǎn)在于提出新的操作和引入學(xué)習(xí)和自適應(yīng)機(jī)制等，文獻(xiàn)[5-8]提出了求解多維背包問(wèn)題的提出了遺傳算法（GA）、二進(jìn)制螞蟻算法、分散搜索算法和分布估計(jì)算法。

本文分析帶有利用率懲罰背包問(wèn)題的線性松弛最優(yōu)解性質(zhì)，以揭示整數(shù)最優(yōu)解的結(jié)構(gòu)特征。針對(duì)帶有利用率懲罰背包問(wèn)題的特征，設(shè)計(jì)了一種基于參數(shù)自適應(yīng)的差分進(jìn)化算法。實(shí)驗(yàn)結(jié)果顯示提出的算法性能顯著優(yōu)于常規(guī)的差分進(jìn)化算法，說(shuō)明該算法在求解懲罰背包及類(lèi)似問(wèn)題上的有效性和魯棒性。

1 問(wèn)題描述

其中n為物品的數(shù)量，pj和wj為物品j的價(jià)值和重量，W為背包的容量，G（u）表示背包利用率為u時(shí)的懲罰，并且G（·）是凸函數(shù)。物品j被裝入背包時(shí)，決策變量zj取1，否則取0。PKP的目標(biāo)是在滿足背包容量約束的前提下，選取若干個(gè)物品裝入背包，使得裝入物品的總價(jià)值同背包利用率的懲罰值之差最大化。由于所有重量為0且價(jià)值不小于0的物品一定被裝入背包，因此，不失一般性，假設(shè)pj≥0，wj>0。

2 性質(zhì)分析

將PKP問(wèn)題的決策變量z從二元變量松弛為[0，1]間的連續(xù)變量，即可得到PKP問(wèn)題的線性松弛問(wèn)題，記為R（PKP）。文獻(xiàn)[1]指出R（PKP）問(wèn)題的最優(yōu)解同PKP的最優(yōu)解具有相同的結(jié)構(gòu)，下文將首先分析R（PKP）的最優(yōu)解性質(zhì)。

3 參數(shù)自適應(yīng)差分進(jìn)化算法

在最優(yōu)求解松弛問(wèn)題R（PKP）的同時(shí)可以得到原問(wèn)題PKP的一個(gè)可行解，但該可行解不能保證最優(yōu)性，因此，需要針對(duì)PKP問(wèn)題設(shè)計(jì)有效的求解算法。基于PKP問(wèn)題的特點(diǎn)，提出一種改進(jìn)的參數(shù)自適應(yīng)差分進(jìn)化算法來(lái)求解PKP問(wèn)題，分別就算法設(shè)計(jì)中問(wèn)題解的表達(dá)、變異操作、變異率參數(shù)自適應(yīng)設(shè)計(jì)、交叉操作、交叉率參數(shù)自適應(yīng)設(shè)計(jì)、選擇操作、非可行解修復(fù)方法進(jìn)行闡述。

3.1 解的表達(dá)

種群中每一個(gè)體對(duì)應(yīng)PKP的一個(gè)解，每一個(gè)體用一個(gè)長(zhǎng)度為n的向量z表示，每個(gè)分量zi是區(qū)間[0， 1]上的實(shí)數(shù)。zi≥0.5表示選擇物品i放入背包中，zi<0.5表示物品i沒(méi)有被選擇。

3.2 變異操作

3.7 非可行解修復(fù)方法

如果新產(chǎn)生的個(gè)體是非可行解，即不滿足背包容量約束，則采用一種隨機(jī)修復(fù)機(jī)制對(duì)此個(gè)體進(jìn)行修復(fù)。根據(jù)背包裝載的超出量，隨機(jī)選擇多被裝載的物品，將其從背包中刪除，最后判斷是否滿足背包容量約束，如果滿足則停止修復(fù)，否則重新進(jìn)行隨機(jī)修復(fù)。

4 實(shí)驗(yàn)結(jié)果

針對(duì)文獻(xiàn)[9]給出的0-1背包問(wèn)題的算例，采用文獻(xiàn)[1]定義的背包利用率的罰函數(shù)G（·），對(duì)提出的參數(shù)自適應(yīng)差分進(jìn)化算法進(jìn)行性能測(cè)試。所有算法均利用Microsoft Visual studio編程實(shí)現(xiàn)， 在Intel（R） Core（TM） i5-4210M CPU @ 2.60GHz，4.00GB內(nèi)存物理地址擴(kuò)展， Microsoft Windows 8.1系統(tǒng)電腦上運(yùn)行.

文獻(xiàn)[9]中算例的產(chǎn)生方法如下： 假設(shè)任意物品的重量wj和價(jià)值pj獨(dú)立均勻分布在區(qū)間[1， 100]內(nèi)，背包容量W=σ∑wj。按照N=100， 200， 500和σ=0.3， 0.5， 0.7的組合，生成9組算例。求解的參數(shù)設(shè)置保持不變的條件下， 針對(duì)每組算例，分別使用標(biāo)準(zhǔn)差分進(jìn)化算法和參數(shù)自適應(yīng)差分進(jìn)化算法獨(dú)立運(yùn)行50次，得到的優(yōu)化結(jié)果如表1所示。

由表1可見(jiàn)，對(duì)于所有算例，參數(shù)自適應(yīng)差分進(jìn)化算法都能獲得更好的最好解、均值和最差解，對(duì)于大部分算例，參數(shù)自適應(yīng)差分進(jìn)化算法能獲得更好的標(biāo)準(zhǔn)差。這說(shuō)明了參數(shù)自適應(yīng)差分進(jìn)化算法具有更好的有效性和穩(wěn)定性，顯示出良好的優(yōu)化潛力。

5 結(jié)論

針對(duì)帶有背包利用率的凸型罰函數(shù)的新型背包問(wèn)題，建立了數(shù)學(xué)模型，分析了線性松弛最優(yōu)解性質(zhì)和揭示了整數(shù)最優(yōu)解結(jié)構(gòu)，并提出了一個(gè)求解該問(wèn)題的參數(shù)自適應(yīng)差分進(jìn)化算法。該算法中提出變異和交叉參數(shù)的自適應(yīng)選擇方法，在進(jìn)化的過(guò)程中可以動(dòng)態(tài)評(píng)估每組被選參數(shù)的性能，并用于指導(dǎo)下一個(gè)迭代過(guò)程的參數(shù)配置，從而避免了基本差分進(jìn)化算法中參數(shù)選擇的困難。通過(guò)對(duì)不同規(guī)模算例的計(jì)算實(shí)驗(yàn)，表明所提出的改進(jìn)差分進(jìn)化算法在求解這類(lèi)新型背包問(wèn)題上具有良好的優(yōu)化潛力和穩(wěn)定性，將來(lái)可以擴(kuò)展到求解其他類(lèi)型的背包問(wèn)題。

【參考文獻(xiàn)】

[1]Freling R， Romeijn H E， Romero Morales D， Wagelmans A P M. A branch-and-price algorithm for the multiperiod single-sourcing problem [J]. Operations Research， 2003，51（6）：922-939.

[2]李若平，歐陽(yáng)海濱，高立群，等.學(xué)習(xí)型和聲搜索算法及其在0-1 背包問(wèn)題中的應(yīng)用[J].控制與決策，2013，28（2）：205-210.

[3]歐陽(yáng)海濱，高立群，孔祥勇，等.一種求解0-1 背包問(wèn)題的二進(jìn)制修正和聲搜索算法[J].控制與決策，2014，29（7）：1174-1180.

[4]Tung K T， Li K L， Xua Y M. Chemical reaction optimization with greedy strategy for the 0-1 knapsack problem [J]. Applied Soft Computing， 2013，13（4）：1774-1780.

[5]Chu P C， Beasley J E. A genetic algorithm for the multidimensional knapsack problem[J]. Journal of Heuristics， 1998，4（1）：63-86.

[6]Kong M， Tian P， Kao Y C. A new ant colony optimization algorithm for the multidimensional knapsack problem [J]. Computers & Operations Research， 2008，35（8）：2672-2683.

[7]Hanafi S， Wilbaut C. Scatter search for the 0-1 multidimensional knapsack problem[J]. Journal of Mathematical Modelling and Algorithms， 2008， 7（2）：143-159.

[8]王凌，王圣堯，方晨.一種求解多維背包問(wèn)題的混合分布估計(jì)算法控制與決策[J].2011，26（8）：1121-1125.

[9]Martello， S， Toth P. Knapsack Problems， Algorithms and Computer Implementations[M]. 1990 John Wiley and Sons， New York.

[責(zé)任編輯：湯靜]