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

劉靜宜　韓海燕

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

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

0 引言

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

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

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

1 問題描述

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

2 性質(zhì)分析

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

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

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

3.1 解的表達

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

3.2 變異操作

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

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

4 實驗結(jié)果

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

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

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

5 結(jié)論

針對帶有背包利用率的凸型罰函數(shù)的新型背包問題，建立了數(shù)學(xué)模型，分析了線性松弛最優(yōu)解性質(zhì)和揭示了整數(shù)最優(yōu)解結(jié)構(gòu)，并提出了一個求解該問題的參數(shù)自適應(yīng)差分進化算法。該算法中提出變異和交叉參數(shù)的自適應(yīng)選擇方法，在進化的過程中可以動態(tài)評估每組被選參數(shù)的性能，并用于指導(dǎo)下一個迭代過程的參數(shù)配置，從而避免了基本差分進化算法中參數(shù)選擇的困難。通過對不同規(guī)模算例的計算實驗，表明所提出的改進差分進化算法在求解這類新型背包問題上具有良好的優(yōu)化潛力和穩(wě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]李若平，歐陽海濱，高立群，等.學(xué)習(xí)型和聲搜索算法及其在0-1 背包問題中的應(yīng)用[J].控制與決策，2013，28（2）：205-210.

[3]歐陽海濱，高立群，孔祥勇，等.一種求解0-1 背包問題的二進制修正和聲搜索算法[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]王凌，王圣堯，方晨.一種求解多維背包問題的混合分布估計算法控制與決策[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é)任編輯：湯靜]