一種結合貪婪因子求解0-1背包問題的分布估計算法

譚 陽 周 虹

(湖南網絡工程職業學院，湖南 長沙 410004)

一種結合貪婪因子求解0-1背包問題的分布估計算法

譚 陽 周 虹

(湖南網絡工程職業學院，湖南 長沙 410004)

針對0-1背包問題，在分布估計算法的基礎上提出了一種結合傳統貪婪方法的新算法。通過計算物品的重量價值比后獲得物品的貪婪因子值，并將貪婪因子融入基本的分布估計算法之中，在保證收斂速度的基礎上進一步平衡了個體間的競爭，相較對比算法而言取得了更好的優化結果。

分布估計算法；貪婪因子；0-1背包問題；概率模型

1．引言

背包問題又稱子集合問題，運籌學中一個典型的組合優化難題，有著廣泛的應用背景，如倉庫貨物裝載問題、選址問題等。不失一般性背包問題的描述通常如下：給定n個物品和1個背包，物品i的重量為wi，其價值為vi，i=1，2，…，n。且該背包的最大容量為 C，要從給定的n個物品中挑選若干個物品放入背包中，要滿足挑選的物品總重量不超過 C，且總價值達到最大。背包問題的解采用向量X=(x1，x2，…，xn)T，xi∈{0，1}表示。其數學模型為：

xi∈{0，1} i=1，2，…，n

背包問題屬于NP難題，目前求解的方法有精確方法(如動態規劃、遞歸法、回溯法、分支限界法等[1])，近似算法(如貪婪法[1]，Lagrange法等)以及智能優化算法(如模擬退火算法[2]、遺傳算法[2]、遺傳退火進化算法[3]、蟻群算法[4-5])、粒子群優化算法[6]。精確方法雖然可以得到準確解，但時間復雜性與物品數目成指數關系。近似算法和智能優化算法雖然不一定得到準確解，但可得到比較有效解，并且時間復雜性比較低。

2．結合貪婪因子的分布估計算法

2．1 貪婪因子

貪婪算法通過一系列的選擇得到問題的解，在每一次總是做出在當前狀態下看來是最好的選擇，也就是希望通過局部的最優來達到一個全局的最優。這種啟發式的策略并不總能獲得最優解，然而在許多情況下確能達到預期的目的。通常對于0-1背包問題采用價值密度貪婪準則：每次都選取vi/wi值最大的物品放入背包之中，這種選擇準則通常需要對所有物品進行一次掃描，并按照物品的vi/wi值的大小進行一次降序排列。因此本文在對0-1背包問題的處理上采用將物品的vi/wi值作為該物品的加權因子，以作為在分布估計算法中該物品被選擇的參考因素。

2．2 分布估計算法

分布估計算法(EDA)是一種新興的基于統計學原理的隨機優化算法最初由Baluja[7]在1994年提出，分布估計算法是一種全新的進化方法。分布估計算法首先構造描述解空間的概率模型，通過對種群的評估，從中選擇優秀的個體集合，然后采用統計學習等方法根據優秀的個體構造概率模型；然后由這個概率模型隨機采樣產生新的種群，如此反復迭代，實現種群的進化，直到滿足終止條件。標準的EDA的算法流程如下：

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

Step 2：依據適應值，從群體中選擇優秀的個體；

Step 3：根據所選擇的個體的分布，構建概率模型；

Step 4：根據概率模型進行隨機采樣，生成下一代群體，并對新個體計算適應值；

Step 5：判斷是否符合終止條件，符合則算法結束并輸出結果；否則轉Step2。

本文采用二進制表達，分布估計算法中的種群個體，每個個體采用長度為n的0-1字符串表達對物品的選取情況，X=x1，x2，…，xn，xi=0，1，i=1，2，…，n當xi=0時則表示第i個物品沒有被選擇。

2．3 算法的概率模型及更新機制

通過建立一個包含n個分量的概率向量p(x)=[p(x1)，p(x2)，…，p(xn)]來表示在解空間中分布的概率模型，其中p(xi)為物品i被選取的概率。通常在算法開始時會將初始概率p(x)設置為[0.5，0.5，…，0.5]的均勻分布狀態，隨著算法迭代進化，新個體的產生則基于概率向量p(x)的分布情況來產生。即個體中對于物品i的選取是通過一個0～1間的隨機數r來決定的，若有r＜p(xi)則選取該物品，記為xi=1；否則不選取該物品，記為xi=0。如此反復，直至產生全部M個個體。通過計算所有個體的目標值，通過排序并選擇其中價值最高的前N個個體N＜M，以機器學習中的PBIL法則[7]來更新概率向量p (x)。

其中t為算法當前進化的代數，pt(x)為第t代時的概率向量，α，(0＜α＜1)為機器學習的速率為第t代時被選擇的第j個個體。

計算機出物品i的貪婪價值vi/wi，并對所有物品的貪婪

2．4 修復非可行解

在解決背包問題中EDA是根據當前的概率模型來產生新個體，但是新個體未必是可行解，為了能保證所有產生的新個體都是可行解，就必需對所有新個體掃描并對非可行解進行修復。本文采用貪婪價值修復法，修復流程如下：

Step 1：判斷個體是否為可行解，若可行則轉Step 3，否則繼續下一步；

Step 2：找到該個體向量中貪婪價值vi/wi最小的，且數值為“1”的位；并將其置為“0”后轉Step 1；

Step 3：判斷是否滿足退出條件，滿足則退出，否則繼續判斷下一個個體。

2．5 結合貪婪因子的分布估計算法（GEDA）

結合以上設計，在引入貪婪因子后，在算法將初始概率p(x)以物品的貪婪因子值來進行設置[β1，β2，…，βn]，同時還需對PBIL概率向量更新法則進行一些調整，其主要目的是降低機器學習的速率，平衡個體間的競爭壓力，調整后的PBIL法則如下：

由式(3)可知，在引入(1-β)后權重因子后，可以有效減小由超級個體帶來的極值效應，其βi貪婪因子值越高反而在向量概率更新的權重越小，從而有效降低了早熟收斂的發生。

通過改進后，結合貪婪因子的分布估計算法的流程如下：

Step 2：以p(x)進行隨機采樣生成M個個體，并轉Step 4；

Step 3：以p(x)進行隨機采樣，并生成M-N個個體；

Step 4：檢測所有新生成個體，并以“貪婪價值修復法”對非可行個體進行修復；

Step 5：計算新個體的適應值，并依據適應值的大小進行降序排序，同時劃分出的前N個最優個體；

Step 6：依據最優的N個個體的分布情況，以式(3)來更新向量概率p(x)；

Step 7：判斷是否符合終止條件，符合則算法結束并輸出結果；否則轉Step 3。

由此可見，在分布估計算法中引入貪婪因子可以更好地在算法初期體現“性價比”較高個體，在此基礎上通過設立保留機制使得在算法迭代過程中產生的優秀個體得以傳承，從而保證算法可以進行有效的搜索。同時為了防止貪婪因子引發極值效應，在機器學習的環節中通過加入貪婪因子來平衡個體間的競爭關系，進而獲得更好的搜索性能。

3．仿真測試

3．1 搜索能力的仿真對比測試

本文選取文獻[8]中物品數目為50的實例背包問題（最優解為：3103）來驗證GEDA算法的有效性。其中GEDA和EDA的參數均為：學習速率α=0.1，種群規模M=100，N=20。文獻[9]中提出以微粒群算法(PSO)來求解0-1背包問題，其中PSO列的數據直接取自于文獻[9]。每種算法均獨立運行50次。

表1 幾種對比算法的優化統計結果

由表1可知GEDA在平均值和成功次數上均優于對比算法，具備較好的尋優能力。同時通過對GEDA算法的分析可知，只是在EDA的基礎上增加了對所有物品的貪婪因子計算量O(n)，以及在PBIL法則中的因子系數相乘的計算機量O(n)，相較EDA而言其算法的時間復雜度只是線性的增加開銷不大，基本可以等同于EDA。

3．2 搜索效率的仿真對比測試

本文選取文獻[10]中物品數目為100的實例（最優解為：4142）來做對比測試。三種對比算法分別獨立運行10次取平均值，最大迭代次數為500代，其它參數保持不變。

圖1 三種對比算法對實例優化的情況

通過圖1可以看出，相對于使用隨機初始化種群的EDA和PSO而言，使用貪婪因子值初始化種群的GEDA在一開始就具備較好的種群優勢。在后續的搜索過程中GEDA的收斂效率也明顯優于其它對比算法，可以看出GEDA在第250代左右時就已經非常接近最優解，與此相對EDA和PSO分別是在第450代和第400代時才接近最優解。

因此，GEDA是一種有效解決0-1背包問題的方法，相較對比算法而言GEDA在搜索能力和搜索效率方面具備更好的性能。

4．結語

在解決0-1背包的問題上，本文通過結合傳統貪婪算法提取物品的貪婪價值，并以此生成物品的貪婪因子值。通過在EDA算法中使用貪婪因子，使得算法在尋優性能上得到了提升，同時還較好地限制了計算開銷的增長。后續的仿真實驗也證明GEDA是一種有效解決0-1背包的方法。

[1]王曉東．計算機算法設計與分析[M]．北京：電子工業出版社，2001：92-168．

[2]王凌．智能優化算法及其應用[M]．北京：清華大學出版社，2001：17-59．

[3]金慧敏，馬良．遺傳退火進化算法在背包問題中的應用[J]．上海理工大學學報，2004，26(6)：561-564．

[4]馬良，王龍德．背包問題的螞蟻優化算法[J]．計算機應用，2001，21(8)：4-5．

[5]于永新，張新榮．基于蟻群系統的多選擇背包問題優化算法[J].計算機工程，2003，29(20)：75-76，84．

[6]高尚，楊靜宇．背包問題的混合粒子群優化算法[J]．中國工程科學，2006，8(11)：94-98．

[7]Baluja S．Population—Based Incremental Learning：A method for Integrating Genetic Search Based Function Optimization and Competitive Learning[R]． C MU- CS-94-163．Available via Anonymous ftp at reports，Adm． CS．cmu．Edu，，1994Technical Report， Carnegie Mellon University.

[8]李娟，方平，周明．一種求解背包問題的混合遺傳算法[J]．南昌航空工業學院學報，1998，12(3)：31-35．

[9]沈顯君，王偉武，鄭波盡等．基于改進的微粒群優化算法的0-1背包問題求解[J]．計算機工程，2006，32(18)：23-38．

[10]ZHUANG Zhong-wen，QIAN Shu-qu．Immune algorithm with antibody-repaired and its application for high-dimensional 0/1 knapsack problem[J]．Application Research of Computers，2009，26(8)：2921-2923．

An Estimation of DistributionAlgorithm Solving the 0-1 Knapsack Problem with Greed Factors

Tan Yang Zhou Hong
(Hunan Network Engineering Vocational College， Changsha 410004,Hunan)

Aiming at the 0-1 knapsack problem,this paper proposes a new algorithm combined with traditional greedy approach based on estimation of distribution algorithm.It obtains the greedy factor values of the goods by calculating the weight-to-value ratio.It also integrates the greedy factor into the basic estimation of distribution algorithm.While ensuring the rate of convergence,it keeps the competition between individuals in balance,making better optimization results compared with the comparison algorithm.

estimation of distribution algorithm(EDA);greed factor;0-1 knapsack problem;probabilistic model

譚陽，男，湖南望城人，碩士，副教授，研究方向：智能計算，信息安全，數據挖掘。

本文受湖南省教育廳重點項目資助，項目編號：10A074。