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

譚 陽 周 虹

(湖南網(wǎng)絡(luò)工程職業(yè)學院，湖南 長沙 410004)

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

譚 陽 周 虹

(湖南網(wǎng)絡(luò)工程職業(yè)學院，湖南 長沙 410004)

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

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

1．引言

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

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

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

2．結(jié)合貪婪因子的分布估計算法

2．1 貪婪因子

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

2．2 分布估計算法

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

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

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

Step 3：根據(jù)所選擇的個體的分布，構(gòu)建概率模型；

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

Step 5：判斷是否符合終止條件，符合則算法結(jié)束并輸出結(jié)果；否則轉(zhuǎn)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)設(shè)置為[0.5，0.5，…，0.5]的均勻分布狀態(tài)，隨著算法迭代進化，新個體的產(chǎn)生則基于概率向量p(x)的分布情況來產(chǎn)生。即個體中對于物品i的選取是通過一個0～1間的隨機數(shù)r來決定的，若有r＜p(xi)則選取該物品，記為xi=1；否則不選取該物品，記為xi=0。如此反復(fù)，直至產(chǎn)生全部M個個體。通過計算所有個體的目標值，通過排序并選擇其中價值最高的前N個個體N＜M，以機器學習中的PBIL法則[7]來更新概率向量p (x)。

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

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

2．4 修復(fù)非可行解

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

Step 1：判斷個體是否為可行解，若可行則轉(zhuǎn)Step 3，否則繼續(xù)下一步；

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

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

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

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

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

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

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

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

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

Step 5：計算新個體的適應(yīng)值，并依據(jù)適應(yīng)值的大小進行降序排序，同時劃分出的前N個最優(yōu)個體；

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

Step 7：判斷是否符合終止條件，符合則算法結(jié)束并輸出結(jié)果；否則轉(zhuǎn)Step 3。

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

3．仿真測試

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

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

表1 幾種對比算法的優(yōu)化統(tǒng)計結(jié)果

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

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

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

圖1 三種對比算法對實例優(yōu)化的情況

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

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

4．結(jié)語

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

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

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

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

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

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

[6]高尚，楊靜宇．背包問題的混合粒子群優(yōu)化算法[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]．南昌航空工業(yè)學院學報，1998，12(3)：31-35．

[9]沈顯君，王偉武，鄭波盡等．基于改進的微粒群優(yōu)化算法的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

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

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