背包問題的分布估計算法

2013-01-07 05:19高尚

中南大學學報（自然科學版） 2013年2期

高尚

(江蘇科技大學計算機科學與工程學院，江蘇鎮(zhèn)江，212003 )

背包問題是運籌學中一個典型的組合優(yōu)化難題，有著廣泛的應用背景，如貨物裝載問題、選址問題等。由于此問題比較簡單典型，因此，評價算法優(yōu)劣常常以此問題作為的測試對象進行研究。背包問題屬于NP問題，目前求解的方法有精確方法(如動態(tài)規(guī)劃、遞歸法、回溯法、分支限界法等[1])，近似算法(如貪心法[1]，Lagrange法等)以及智能優(yōu)化算法(如模擬退火算法[2]、遺傳算法[2]、遺傳退火進化算法[3]、蟻群算法[4?5])、粒子群優(yōu)化算法[6]。精確方法雖然可以得到準確解，但時間復雜性與物品數(shù)目成指數(shù)關系。近似算法和智能優(yōu)化算法雖然不一定得到準確解，但可得到比較有效解，并且時間復雜性比較低。本文作者嘗試采用分布估計算法解決此問題。分布估計算法是進化計算領域新興起的一類隨機優(yōu)化算法，是當前國際進化計算領域的研究熱點[7]。試驗分析表明分布估計算法在求解問題時表現(xiàn)出了比一般遺傳算法更好的性能，應用分布估計算法解決工程和科學中的復雜優(yōu)化問題具有很大的潛力。目前分布估計算法己經(jīng)在眾多領域得到了成功的應用[8?11]，如在汽車齒輪機械結構的優(yōu)化設計、特征選擇、不精確圖形的模式匹配、軟件測試、癌癥分類、生物信息學中的特征提取、軍事天線的優(yōu)化設計等方面均有應用，使用分布估計算法解決科學研究和工程應用中的優(yōu)化問題將是未來幾年的研究熱點。

1 背包問題數(shù)學模型

背包問題的描述有許多種形式，最典型的是 0?1背包問題。0?1背包問題[1]是指：給定n種物品和一個背包，物品i的質量是ci，其價值為pi，背包的質量容量為C，如何選擇物品，使得裝入背包中物品的總價值最大。背包問題的解用向量X= (x1,x2, …,xn)T表示，其數(shù)學模型為：

帶限制的背包問題(bounded knapsack problem)模型是指物品的數(shù)量可多取，但受到限制，其模型如下：

無限制的背包問題(unbounded knapsack problem)模型是指物品的數(shù)量可多取，數(shù)量不受到限制，其模型如下：

還有許多其他不同類型的背包問題，本文重點討論模型(1)的解法。

2 分布估計算法

分布估計算法的概念[7]最初由Baluja在1994年提出，分布估計算法是一種全新的進化方法。分布估計算法首先構造描述解空間的概率模型，通過對種群的評估，從中選擇優(yōu)秀的個體集合，然后采用統(tǒng)計學習等方法根據(jù)優(yōu)秀的個體構造概率模型；然后由這個概率模型隨機采樣產生新的種群，一般采用隨機方法，如此反復迭代，實現(xiàn)種群的進化，直到滿足終止條件。分布估計算法根據(jù)分布函數(shù)的不同而產生了很多算法，這些算法可以分成離散的和連續(xù)的兩大類，在隨機變量之間的依賴關系上又可以分為幾類不同的算法。這些算法的基本框架如下：

Step 1：初始化群體，對每一個個體計算適應值；

Step 2：依據(jù)適應值，從群體中選擇優(yōu)秀的個體；

Step 3：估計所選擇的個體的概率分布；

Step 4：根據(jù)分布，采樣獲得新的個體構成下一代群體，對新個體計算適應值；

Step 5：符合終止條件，算法結束，否則轉到Step2。

算法如圖1所示。在傳統(tǒng)的遺傳算法(GA)中，優(yōu)化問題的候選解用種群個體表示，計算種群中的每個個體的適應值，根據(jù)個體適應值進行選擇操作，適應值大的個體以較大的概率被選擇，然后進行交叉操作和變異等操作，反復進化迭代，直到滿足終止條件。而分布估計算法(DEA)沒有遺傳算法的傳統(tǒng)交叉、變異等操作，取而代之的是概率模型的學習。對于遺傳算法來說，其交叉和變異操作有可能會破壞已經(jīng)進化好的個體，而分布估計算法利用概率模型和采樣兩大操作取代了遺傳算法中的交叉算子和變異算子，以一種帶有“全局操控性”的操作模式，可以解決遺傳算法存在的這一弊端。而且分布估計算法不需要太多的參數(shù)設置，程序實現(xiàn)比遺傳算法簡單。

圖1 分布估計算法基本流程Fig.1 Illustrates flowchart of EDA

3 解0?1背包問題的分布估計算法

首先把原約束方程作為罰函數(shù)項加入到原目標中，變成無約束的優(yōu)化問題，即

其中：M為一充分大的正數(shù)。

解0?1背包問題的分布估計算法如下：

Step 1：以概率(p1,p2, …,pn)T=(0.5, 0.5, …, 0.5)T隨機產生N個(取1的概率為0.5)個體組成一個初始種群；

Step 2：評估初始種群中所有個體的適應度，保留最好解；

Step 3：按適應度從高到低的順序對種群進行排序，并從中選出最優(yōu)的m個個體(m≤N)；

Step 4：分析產生的m個個體所包含的信息，估計每個變量取1的 (p1,p2, …,pn)T；

Step 5：從構建的概率模型(p1,p2, …,pn)T中采樣，得到N個新樣本，構成新種群；

Step 6：若達到算法的終止條件則結束(如達到規(guī)定迭代次數(shù)nmax)，否則執(zhí)行Step 2。

該分布估計算法的時間復雜性估算如下：以計算適應度操作花費最多，所以，時間復雜性大約為O(N·nmax)。

4 數(shù)值仿真與分析

采用文獻[4]的一個典型的背包問題數(shù)據(jù)，n= 10，C= 269 g，{p1,p2, …,p10}={55, 10, 47, 5, 4, 50, 8, 61,85, 87}元，{c1,c2, …,c10}={95, 4, 60, 32, 23, 72, 80, 62,65, 46} g。

當N=1 000，m=0.4N時，統(tǒng)計滿足背包的質量容量為C要求下的最好值與平均值的迭代過程如圖2所示。迭代一定次數(shù)后均收斂到最優(yōu)解。

影響分布估計算法的性能的主要參數(shù)是種群的個數(shù)N和選出的種群個數(shù)m。以達到最優(yōu)目標值為295所需要的迭代次數(shù)評價標準，N取不同值，m=N/2，各種算法各測試100次，統(tǒng)計數(shù)據(jù)如表1所示。

圖2 最好值與平均值的迭代過程Fig.2 Iterative process of best values and average values

表1 N取不同值結果比較Table 1 Comparison results of different N

當N=100時，有時算法進入局部最優(yōu)解，達不到全局最優(yōu)值295，無法統(tǒng)計。從表1可知：N越小，樣本數(shù)量不足，效果不好；N越大，效果越好，當然需要的時間也越大。因此，N取適中即可，如N取800。

當N=800時，選出的種群個數(shù)m占N的比例不同，結果也不一樣。對于不同的m/N，算法各測試100次，統(tǒng)計數(shù)據(jù)如表2所示。

從表2可以看出：m/N越大，不能體現(xiàn)出選優(yōu)的優(yōu)勢，效果越不好；當然，m/N太小，也容易陷入局部極值。m/N取10%～30%時效果比較好。

表2 m/N取不同值結果比較Table 2 Comparison results of different m/N

5 結論

本文的分布估計算法不僅可以解決背包問題，對于整數(shù)規(guī)劃問題，對該算法作適當修改，也可適用。分布估計算法研究處于初期，還有許多問題值得研究，如算法的收斂性、理論依據(jù)等。但從當前的分布估計算法的應用效果來看，這種新型的尋優(yōu)思想無疑具有十分廣闊的前景。

[1] 王曉東. 計算機算法設計與分析[M]. 北京: 電子工業(yè)出版社,2001: 92?168.WANG Xiaodong. Design and analysis of computer algorithms[M]. Beijing: Publishing House of Electronics Industry, 2001:92?168.

[2] 王凌. 智能優(yōu)化算法及其應用[M]. 北京: 清華大學出版社,2001: 17?59.WANG Ling. Intelligent optimization algorithms with applications[M]. Beijing: Tsinghua University Press, 2001:17?59.

[3] 金慧敏, 馬良. 遺傳退火進化算法在背包問題中的應用[J].上海理工大學學報, 2004, 26(6): 561?564.JIN Huimin, MA Liang. Genetic annealing evolutionary algorithm applied to the knapsack problem[J]. Journal of University of Shanghai for Science and Technology, 2004, 26(6):561?564.

[4] 馬良, 王龍德. 背包問題的螞蟻優(yōu)化算法[J]. 計算機應用,2001, 21(8): 4?5.MA Liang, WANG Longde. Ant optimization algorithm for knapsack problem[J]. Computer Applications, 2001, 21(8): 4?5.

[5] 于永新, 張新榮. 基于蟻群系統(tǒng)的多選擇背包問題優(yōu)化算法[J]. 計算機工程, 2003, 29(20): 75?76, 84.YU Yongxin, ZHANG Xinrong. Optimization algorithm for multiple-choice knapsack problem based on ant colony system[J].Computer Engineering, 2003, 29(20): 75?76, 84.

[6] 高尚, 楊靜宇. 背包問題的混合粒子群優(yōu)化算法[J]. 中國工程科學, 2006, 8(11): 94?98.GAO Shang, YANG Jingyu. Solving knapsack problem by hybrid particle swarm optimization algorithm[J]. Engineering Science, 2006, 8(11): 94?98.

[7] 周樹德, 孫增圻. 分布估計算法綜述[J].自動化學報, 2007,33(2): 113?124.ZHOU Shude, SUN Zengqi. A survey on estimation of distribution algorithm[J]. Acta Automatica Sinica, 2007, 33(2):113?124.

[8] Muhliebe H, Paass G. From recombination of genes to the estimation of distributions. Ⅰ: Binary parameters[C]// Lecture Notes in Computer Science. Berlin, Germany: Springer Verlag,1996: 178?187.

[9] Pelikan M, Godberg D E, Paz E C. Linkage problem, distribution estimation, and Bayesian networks[J]. Evolutionary Computation, 2000, 8(3): 311?340.

[10] Paul T K, Iba H. Linear and combinatorial optimizations by estimation of distribution algorithms[C]// 9th MPS Symposium on Evolutionary Computation, IPSJ. Kyotanabe, Kyoto, Japan,2002: 99?106.