??? 摘? 要： 提出了一種新的求解0-1背包問(wèn)題的自適應(yīng)算法——改進(jìn)郭濤算法IGT,。新算法實(shí)現(xiàn)了真正意義上的子空間搜索過(guò)程,，引入了變維子空間,，加入了變異算子,，同時(shí)還與貪心算法相結(jié)合,，并引入啟發(fā)式修正算子,，以保證算法的局部搜索能力和群體多樣性,。
??? 關(guān)鍵詞： 0-1背包問(wèn)題? 改進(jìn)郭濤算法? 貪心算法? 局部搜索? 啟發(fā)式修正算子

?

??? 0-1背包問(wèn)題是一類(lèi)經(jīng)典的組合優(yōu)化問(wèn)題,，它已被證明是一類(lèi)NP完全問(wèn)題。因此,，用通常的數(shù)學(xué)方法求解很難在有效的時(shí)間內(nèi)找出全局最優(yōu)解,。對(duì)0-1背包問(wèn)題的研究具有現(xiàn)實(shí)意義，它可以廣泛運(yùn)用于資源分配,、投資決策,、貨物裝載等方面。例如：處理機(jī)和數(shù)據(jù)庫(kù)在分布式計(jì)算機(jī)系統(tǒng)上的分配問(wèn)題,；項(xiàng)目選擇的貨物裝載問(wèn)題,；削減庫(kù)存問(wèn)題等。目前,，對(duì)此類(lèi)問(wèn)題的研究已出現(xiàn)了不少有價(jià)值的方法,。這些方法主要分兩大類(lèi)：一類(lèi)是精確方法，如：分支－定界法,、動(dòng)態(tài)規(guī)劃法,、隱枚舉法等；另一類(lèi)是啟發(fā)式方法,，如：貪心算法,、遺傳算法、模擬退火算法,、Tabu搜索算法等,。
??? 由于0-1背包問(wèn)題的復(fù)雜性,，因此，在求解此類(lèi)問(wèn)題時(shí)容易陷入局部最優(yōu)解,。為此,，本文對(duì)基本的郭濤算法進(jìn)行了一些改進(jìn)，并結(jié)合貪心算法對(duì)這一類(lèi)問(wèn)題進(jìn)行了研究,。通過(guò)大量的數(shù)據(jù)模擬實(shí)驗(yàn),，證明了新算法在求解0-1背包問(wèn)題時(shí)具有很好的有效性和穩(wěn)定性。同時(shí),，由于算法采用了“群體爬山策略”,，所以很容易找出全局最優(yōu)解。
1? 0-1背包問(wèn)題
??? 0-1背包問(wèn)題可以形式化地描述為：
???
??? 其中：式(1)為目標(biāo)函數(shù),，式(2)和(3)為約束條件,，X為一個(gè)n維的向量，c_i表示第i個(gè)物品的價(jià)值,，w_i表示第i個(gè)物品的重量,，n為物品的數(shù)量。如果第i個(gè)物品放入背包中,，則x_i=1,，否則x_i=0。問(wèn)題的目標(biāo)就是要在背包盡量裝滿(mǎn)但又不超過(guò)其容量的情況下,，使所裝入背包中的物體價(jià)值最大,。此問(wèn)題的復(fù)雜度為O(2ⁿ)。
2? 郭濤算法簡(jiǎn)介
??? 郭濤算法^[4]是由郭濤等提出的一種啟發(fā)式演化算法,，主要是為了解決帶不等式約束的函數(shù)優(yōu)化問(wèn)題,。實(shí)踐證明，郭濤算法在求解帶等式或(和)不等式約束的函數(shù)優(yōu)化問(wèn)題中取得了很好的效果,。本文把郭濤算法加以改進(jìn)后應(yīng)用到0-1背包問(wèn)題求解中,，取得了很好的效果。
??? 郭濤算法的特點(diǎn)為：
??? (1)采用了演化算法中的群體搜索策略,，保證了搜索空間的全局性,，有利于搜索問(wèn)題的最優(yōu)解。
??? (2)采用了隨機(jī)子空間的隨機(jī)搜索,，并采用多父體雜交和非凸子空間搜索策略,，保證了隨機(jī)搜索的遍歷性。
??? (3)采用了“劣汰策略”,，每次只淘汰群體中最壞的個(gè)體,，淘汰壓力小，從而保證了群體的多樣性,。同時(shí),，這樣的策略也可以保證上一個(gè)群體的最好個(gè)體始終完好無(wú)缺地在下一個(gè)群體中出現(xiàn),。而這樣做就可以保證算法以概率1收斂到全局最優(yōu)解^[3]。
??? (4)算法采用的是群體爬山策略,，保證了整個(gè)群體最后集體登上最高峰（深谷）,。當(dāng)最優(yōu)解不惟一時(shí)，該算法還可能一次同時(shí)找到多個(gè)最優(yōu)解^[6],。
3? 改進(jìn)郭濤算法及問(wèn)題處理
3.1 編? 碼
??? 由于郭濤算法很適合用實(shí)數(shù)編碼,，因此，本文在求解0-1背包問(wèn)題時(shí)也采用了實(shí)數(shù)編碼,。具體作法是：首先使x_i在[0,，1.999999]之間隨機(jī)取值，在進(jìn)行多父體雜交形成新的個(gè)體時(shí)就利用這些實(shí)數(shù)數(shù)據(jù)進(jìn)行計(jì)算,；其次,，在求解函數(shù)適應(yīng)度的時(shí)候，利用函數(shù)y_i=INT(x_i)把x_i整型化,，從而使y_i取值為0或1,，即表示物品是否裝入背包中。
3.2 適應(yīng)度函數(shù)設(shè)計(jì)
??? 由于0-1背包問(wèn)題有約束條件的限制,，因此,，在計(jì)算個(gè)體適應(yīng)度值時(shí)，該個(gè)體必須滿(mǎn)足約束條件,。為此，本文把適應(yīng)度函數(shù)分為目標(biāo)適應(yīng)度函數(shù)和約束適應(yīng)度函數(shù)兩類(lèi),。
??? 約束適應(yīng)度函數(shù)為：
???
3.3 比較函數(shù)Better(X₁,，X₂)的處理
??? 由于要比較兩個(gè)個(gè)體的優(yōu)劣，因此,，在郭濤算法中設(shè)計(jì)了一個(gè)布爾型比較函數(shù)Better(X₁,，X₂)，通過(guò)這個(gè)函數(shù)來(lái)比較兩個(gè)個(gè)體的優(yōu)劣,。由于問(wèn)題求解的需要,，本文對(duì)這個(gè)函數(shù)作了一些修改，具體如下：
???
3.4 對(duì)基本郭濤算法的幾點(diǎn)改進(jìn)
??? (1)子空間搜索策略,。原算法在張成的子空間V中只是通過(guò)雜交選出一個(gè)個(gè)體,。本文采用文獻(xiàn)[6]中的方法：先從子空間V中選出S個(gè)個(gè)體，然后在這S個(gè)個(gè)體中找出一個(gè)最好的個(gè)體X′,。這樣做就實(shí)現(xiàn)了真正意義的子空間搜索策略,。
??? (2)變維子空間策略。當(dāng)群體接近最優(yōu)解時(shí),，可以縮小搜索空間,，即減小子空間的維數(shù),。
??? (3)引入變異算子。這是因?yàn)樽儺愃阕涌梢栽鰪?qiáng)算法的局部搜索能力,，同時(shí),，還可以保證群體的多樣性，防止早熟,。
??? (4)與貪心算法結(jié)合,，引入啟發(fā)式修正算子。為了更進(jìn)一步地增強(qiáng)算法的局部搜索能力（因?yàn)楣鶟惴ǖ娜炙阉髂芰軓?qiáng)）,，本文把基本郭濤算法與貪心算法相結(jié)合,，使用啟發(fā)式修正算子，用它來(lái)保證解的可行性,，使得搜索總能在可行解的空間上進(jìn)行,，并在保證解可行性的前提下，盡量增加適應(yīng)度值,。具體做法是從每次執(zhí)行完雜交和變異后形成的新群體中隨機(jī)地選擇不包括最好個(gè)體在內(nèi)的T個(gè)個(gè)體,，然后對(duì)這些個(gè)體作一定的修正。該算子分為刪除和增加兩個(gè)階段,。首先是刪除階段,，按c_i/w_i由小到大的方向把x_i由1變?yōu)?，直到把不合法的解變成合法的解,，若個(gè)體原本是合法個(gè)體,，則不進(jìn)行刪除操作；接著是增加階段,，在保證解的可行性前提下,，按c_i/w_i從大到小的方向把x_i由0變?yōu)?，盡量增加適應(yīng)度值,，這就使個(gè)體得到了改良,。
3.5 改進(jìn)的郭濤算法
??? 改進(jìn)郭濤算法可以描述為：
???
??? 改進(jìn)的郭濤算法除繼承了基本郭濤算法的優(yōu)點(diǎn)之外，還具有如下特點(diǎn)：(1)實(shí)現(xiàn)了真正的子空間搜索策略,；(2)變維子空間的引入使算法收斂更快,；(3)加入了變異操作和使用啟發(fā)式修正算子，從而增強(qiáng)了算法的局部搜索能力,；(4)修正算子對(duì)新產(chǎn)生的群體中的部分個(gè)體進(jìn)行了修正,，不僅可以保證搜索總能在可行解的空間上進(jìn)行，而且還可以使群體保持多樣性,。
4? 數(shù)值實(shí)驗(yàn)
??? 為了能夠驗(yàn)證改進(jìn)郭濤算法的有效性和穩(wěn)定性,，本文首先通過(guò)數(shù)據(jù)實(shí)驗(yàn)對(duì)基本郭濤算法和改進(jìn)郭濤算法進(jìn)行對(duì)比，然后，在改進(jìn)郭濤算法的基礎(chǔ)上,，采用了兩種方式來(lái)進(jìn)行模擬實(shí)驗(yàn),。一種方式的數(shù)據(jù)來(lái)源于目前國(guó)內(nèi)比較常見(jiàn)的遺傳算法書(shū)籍中關(guān)于0-1背包問(wèn)題的示例；另一種方式的數(shù)據(jù)則是通過(guò)隨機(jī)產(chǎn)生的十組數(shù)據(jù),，每組數(shù)據(jù)w_i的取值范圍是[0,，999]，各組中數(shù)據(jù)的個(gè)數(shù)分別是20,，20,，50，50,，60,，60，80,，80,，100，100個(gè),。這樣可以通過(guò)比較來(lái)測(cè)試算法的收斂性,、穩(wěn)定性以及有效性。
??? 實(shí)驗(yàn)環(huán)境：CPU——P-IV 1.7GB,；內(nèi)存——256MB,；操作系統(tǒng)——Windows 2000 Server；開(kāi)發(fā)程序——VC++ .net 2003,。
4.1 測(cè)試1：基本郭濤算法與改進(jìn)郭濤算法的對(duì)比
??? 參數(shù)設(shè)置：群體規(guī)模N=50,；初始子空間大小M=8；變異概率p_mutation=0.001,；通過(guò)雜交新產(chǎn)生個(gè)體數(shù)目S=8,；修正個(gè)體數(shù)目T=5，每次實(shí)驗(yàn)運(yùn)行100次,。實(shí)驗(yàn)Data1、Data2的數(shù)據(jù)來(lái)源于文獻(xiàn)[12],，最大演化代數(shù)MaxGen=2000,；實(shí)驗(yàn)Data3的數(shù)據(jù)來(lái)源于文獻(xiàn)[13]，最大演化代數(shù)MaxGen=10 000,；實(shí)驗(yàn)Data4的數(shù)據(jù)來(lái)源于文獻(xiàn)[14],，最大演化代數(shù)MaxGen=10000?；竟鶟惴ㄅc改進(jìn)郭濤算法實(shí)驗(yàn)結(jié)果比較見(jiàn)表1,。

?

4.4 結(jié)果分析
??? 表2中的數(shù)據(jù)由于物品的數(shù)量相對(duì)比較少,，因此,，在利用本文中的算法進(jìn)行計(jì)算時(shí)穩(wěn)定性很好，而且收斂得也比較快,，基本上都能求出問(wèn)題的最優(yōu)解,。從表3和表4中數(shù)據(jù)的計(jì)算結(jié)果可以看出，隨著物品數(shù)量的不斷增加,，計(jì)算時(shí)間基本上在不斷增大,，但是由于問(wèn)題的復(fù)雜性是成指數(shù)性增長(zhǎng)的，而本文中的計(jì)算時(shí)間并沒(méi)有快速增加,，所以這種時(shí)間的增加是可以接受的,。并且，計(jì)算結(jié)果的相對(duì)誤差率都在10-4左右,。通過(guò)對(duì)兩個(gè)表中的數(shù)據(jù)進(jìn)行分析可以看出,，新算法具有很好的穩(wěn)定性和有效性,。
5? 結(jié)? 論
??? 本文為了求解0-1背包問(wèn)題，在基本郭濤算法的基礎(chǔ)上對(duì)其作了一些修改,，形成了改進(jìn)的郭濤算法（IGT）,。通過(guò)大量的數(shù)值模擬實(shí)驗(yàn)證明了改進(jìn)郭濤算法在求解0-1背包問(wèn)題時(shí)是很有效的，而且具有很好的穩(wěn)定性,。當(dāng)然,，在隨著物品的數(shù)目不斷增加時(shí)，新算法收斂的還不是很快,，這將在今后的工作中做進(jìn)一步的研究,。
參考文獻(xiàn)
1?? 康立山，謝云,，尤矢勇等.非數(shù)值并行算法(第一冊(cè))——模擬退火算法.北京：科學(xué)出版社,，1995
2?? 王小平，曹立明.遺傳算法——理論,、應(yīng)用與軟件實(shí)現(xiàn).西安：西安交通大學(xué)出版社,，2004
3?? 胡欣，汪紅星,，康立山.求解多維0-1背包問(wèn)題的混合遺傳算法.計(jì)算機(jī)工程與應(yīng)用,，1999；(11)
4?? 郭濤,，康立山,，李艷.一種求解不等式約束下函數(shù)優(yōu)化問(wèn)題的新算法.武漢大學(xué)學(xué)報(bào)(自然科學(xué)版)，1999,；5(45)
5?? 李艷,，康卓，劉溥.郭濤算法及其應(yīng)用.武漢汽車(chē)工業(yè)大學(xué)學(xué)報(bào),，2000,；3(22)
6?? 康卓，李艷,，劉溥等.一種通用的混合非線性規(guī)劃問(wèn)題的演化算法.計(jì)算機(jī)研究與發(fā)展,，2002；11(39)
7?? GAO HP,，XIAO XH,，YANG ZQ et al.A mixed evolutionary algorithm consisting of global and local search to solve?multi-modal function optimization ptoblem.Journal of?Huanggang Normal University，2003,；6(23)
8?? 潘正君，康立山,，陳毓屏.演化計(jì)算.北京：清華大學(xué)出版社,，廣西科學(xué)技術(shù)出版社，2000
9?? Freville A，Plateau G.Hard 0-1 test problems for size reduction methods.Investigation Operativa,，1990,；(1)
10? Hanafi S，F(xiàn)reville A.An efficient tabu search approach for the 0-1 multidimensional knapsack problem.European Journal of Operational Research,，1997
11? 陳國(guó)良,，王煦法，莊鎮(zhèn)泉等.遺傳算法及其應(yīng)用.北京：人民郵電出版社,，2001
12? 馬良,，王龍德.背包問(wèn)題的螞蟻優(yōu)化算法.計(jì)算機(jī)應(yīng)用，2001,；21(8)
13? 張鈴,，張鈸.佳點(diǎn)集遺傳算法.計(jì)算機(jī)學(xué)報(bào)，2001,；24(9)
14? 金慧敏,，馬良.遺傳退火進(jìn)化算法在背包問(wèn)題中的應(yīng)用.上海理工大學(xué)報(bào)，2004,；26(6)