求解帶有利用率懲罰背包問題的參數自適應差分進化算法

劉靜宜　韓海燕

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

【關鍵詞】背包問題；利用率懲罰；參數自適應；差分進化算法

0 引言

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

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

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

1 問題描述

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

2 性質分析

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

3 參數自適應差分進化算法

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

3.1 解的表達

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

3.2 變異操作

3.7 非可行解修復方法

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

4 實驗結果

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

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

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

5 結論

針對帶有背包利用率的凸型罰函數的新型背包問題，建立了數學模型，分析了線性松弛最優解性質和揭示了整數最優解結構，并提出了一個求解該問題的參數自適應差分進化算法。該算法中提出變異和交叉參數的自適應選擇方法，在進化的過程中可以動態評估每組被選參數的性能，并用于指導下一個迭代過程的參數配置，從而避免了基本差分進化算法中參數選擇的困難。通過對不同規模算例的計算實驗，表明所提出的改進差分進化算法在求解這類新型背包問題上具有良好的優化潛力和穩定性，將來可以擴展到求解其他類型的背包問題。

【參考文獻】

[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]李若平，歐陽海濱，高立群，等.學習型和聲搜索算法及其在0-1 背包問題中的應用[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.

[責任編輯：湯靜]