背包問題的分布估計算法

高尚

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

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

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

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

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

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

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

2 分布估計算法

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

Step 1：初始化群體，對每一個個體計算適應(yīng)值；

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

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

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

Step 5：符合終止條件，算法結(jié)束，否則轉(zhuǎn)到Step2。

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

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

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

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

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

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

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

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

Step 3：按適應(yīng)度從高到低的順序?qū)ΨN群進(jìn)行排序，并從中選出最優(yōu)的m個個體(m≤N)；

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

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

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

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

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

采用文獻(xiàn)[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。

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

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

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

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

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

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

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

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

5 結(jié)論

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

[1] 王曉東. 計算機(jī)算法設(shè)計與分析[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)化算法及其應(yīng)用[M]. 北京: 清華大學(xué)出版社,2001: 17?59.WANG Ling. Intelligent optimization algorithms with applications[M]. Beijing: Tsinghua University Press, 2001:17?59.

[3] 金慧敏, 馬良. 遺傳退火進(jìn)化算法在背包問題中的應(yīng)用[J].上海理工大學(xué)學(xué)報, 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]. 計算機(jī)應(yīng)用,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]. 計算機(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]. 中國工程科學(xué), 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].自動化學(xué)報, 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.

[11] 高尚. 武器?目標(biāo)分配問題的分布估計算法及參數(shù)設(shè)計[J]. 東南大學(xué)學(xué)報: 自然科學(xué)版, 2012, 42(S1): 178?181.GAO Shang. An estimation of distribution algorithm applied to weapon-target assignment problem and its parameter design[J].Journal of Southeast University: Natural Science Edition, 2012,42(S1): 178?181.