??? 摘? 要： 提出了一種新的求解0-1背包問題的自適應(yīng)算法——改進郭濤算法IGT。新算法實現(xiàn)了真正意義上的子空間搜索過程，引入了變維子空間，加入了變異算子，同時還與貪心算法相結(jié)合，并引入啟發(fā)式修正算子，以保證算法的局部搜索能力和群體多樣性。
??? 關(guān)鍵詞： 0-1背包問題? 改進郭濤算法? 貪心算法? 局部搜索? 啟發(fā)式修正算子
?
??? 0-1背包問題是一類經(jīng)典的組合優(yōu)化問題，它已被證明是一類NP完全問題。因此，用通常的數(shù)學(xué)方法求解很難在有效的時間內(nèi)找出全局最優(yōu)解。對0-1背包問題的研究具有現(xiàn)實意義，它可以廣泛運用于資源分配、投資決策、貨物裝載等方面。例如：處理機和數(shù)據(jù)庫在分布式計算機系統(tǒng)上的分配問題；項目選擇的貨物裝載問題；削減庫存問題等。目前，對此類問題的研究已出現(xiàn)了不少有價值的方法。這些方法主要分兩大類：一類是精確方法，如：分支－定界法、動態(tài)規(guī)劃法、隱枚舉法等；另一類是啟發(fā)式方法，如：貪心算法、遺傳算法、模擬退火算法、Tabu搜索算法等。
??? 由于0-1背包問題的復(fù)雜性，因此，在求解此類問題時容易陷入局部最優(yōu)解。為此，本文對基本的郭濤算法進行了一些改進，并結(jié)合貪心算法對這一類問題進行了研究。通過大量的數(shù)據(jù)模擬實驗，證明了新算法在求解0-1背包問題時具有很好的有效性和穩(wěn)定性。同時，由于算法采用了“群體爬山策略”，所以很容易找出全局最優(yōu)解。
1? 0-1背包問題
??? 0-1背包問題可以形式化地描述為：
??? 
??? 其中：式(1)為目標函數(shù)，式(2)和(3)為約束條件，X為一個n維的向量，ci表示第i個物品的價值，wi表示第i個物品的重量，n為物品的數(shù)量。如果第i個物品放入背包中，則xi=1，否則xi=0。問題的目標就是要在背包盡量裝滿但又不超過其容量的情況下，使所裝入背包中的物體價值最大。此問題的復(fù)雜度為O(2n)。
2? 郭濤算法簡介
??? 郭濤算法[4]是由郭濤等提出的一種啟發(fā)式演化算法，主要是為了解決帶不等式約束的函數(shù)優(yōu)化問題。實踐證明，郭濤算法在求解帶等式或(和)不等式約束的函數(shù)優(yōu)化問題中取得了很好的效果。本文把郭濤算法加以改進后應(yīng)用到0-1背包問題求解中，取得了很好的效果。
??? 郭濤算法的特點為：
??? (1)采用了演化算法中的群體搜索策略，保證了搜索空間的全局性，有利于搜索問題的最優(yōu)解。
??? (2)采用了隨機子空間的隨機搜索，并采用多父體雜交和非凸子空間搜索策略，保證了隨機搜索的遍歷性。
??? (3)采用了“劣汰策略”，每次只淘汰群體中最壞的個體，淘汰壓力小，從而保證了群體的多樣性。同時，這樣的策略也可以保證上一個群體的最好個體始終完好無缺地在下一個群體中出現(xiàn)。而這樣做就可以保證算法以概率1收斂到全局最優(yōu)解[3]。
??? (4)算法采用的是群體爬山策略，保證了整個群體最后集體登上最高峰（深谷）。當最優(yōu)解不惟一時，該算法還可能一次同時找到多個最優(yōu)解[6]。
3? 改進郭濤算法及問題處理
3.1 編? 碼
??? 由于郭濤算法很適合用實數(shù)編碼，因此，本文在求解0-1背包問題時也采用了實數(shù)編碼。具體作法是：首先使xi在[0，1.999999]之間隨機取值，在進行多父體雜交形成新的個體時就利用這些實數(shù)數(shù)據(jù)進行計算；其次，在求解函數(shù)適應(yīng)度的時候，利用函數(shù)yi=INT(xi)把xi整型化，從而使yi取值為0或1，即表示物品是否裝入背包中。
3.2 適應(yīng)度函數(shù)設(shè)計
??? 由于0-1背包問題有約束條件的限制，因此，在計算個體適應(yīng)度值時，該個體必須滿足約束條件。為此，本文把適應(yīng)度函數(shù)分為目標適應(yīng)度函數(shù)和約束適應(yīng)度函數(shù)兩類。
??? 約束適應(yīng)度函數(shù)為：
??? 
3.3 比較函數(shù)Better(X1，X2)的處理
??? 由于要比較兩個個體的優(yōu)劣，因此，在郭濤算法中設(shè)計了一個布爾型比較函數(shù)Better(X1，X2)，通過這個函數(shù)來比較兩個個體的優(yōu)劣。由于問題求解的需要，本文對這個函數(shù)作了一些修改，具體如下：
??? 
3.4 對基本郭濤算法的幾點改進
??? (1)子空間搜索策略。原算法在張成的子空間V中只是通過雜交選出一個個體。本文采用文獻[6]中的方法：先從子空間V中選出S個個體，然后在這S個個體中找出一個最好的個體X′。這樣做就實現(xiàn)了真正意義的子空間搜索策略。
??? (2)變維子空間策略。當群體接近最優(yōu)解時，可以縮小搜索空間，即減小子空間的維數(shù)。
??? (3)引入變異算子。這是因為變異算子可以增強算法的局部搜索能力，同時，還可以保證群體的多樣性，防止早熟。
??? (4)與貪心算法結(jié)合，引入啟發(fā)式修正算子。為了更進一步地增強算法的局部搜索能力（因為郭濤算法的全局搜索能力很強），本文把基本郭濤算法與貪心算法相結(jié)合，使用啟發(fā)式修正算子，用它來保證解的可行性，使得搜索總能在可行解的空間上進行，并在保證解可行性的前提下，盡量增加適應(yīng)度值。具體做法是從每次執(zhí)行完雜交和變異后形成的新群體中隨機地選擇不包括最好個體在內(nèi)的T個個體，然后對這些個體作一定的修正。該算子分為刪除和增加兩個階段。首先是刪除階段，按ci/wi由小到大的方向把xi由1變?yōu)?，直到把不合法的解變成合法的解，若個體原本是合法個體，則不進行刪除操作；接著是增加階段，在保證解的可行性前提下，按ci/wi從大到小的方向把xi由0變?yōu)?，盡量增加適應(yīng)度值，這就使個體得到了改良。
3.5 改進的郭濤算法
??? 改進郭濤算法可以描述為：
??? 
??? 改進的郭濤算法除繼承了基本郭濤算法的優(yōu)點之外，還具有如下特點：(1)實現(xiàn)了真正的子空間搜索策略；(2)變維子空間的引入使算法收斂更快；(3)加入了變異操作和使用啟發(fā)式修正算子，從而增強了算法的局部搜索能力；(4)修正算子對新產(chǎn)生的群體中的部分個體進行了修正，不僅可以保證搜索總能在可行解的空間上進行，而且還可以使群體保持多樣性。
4? 數(shù)值實驗
??? 為了能夠驗證改進郭濤算法的有效性和穩(wěn)定性，本文首先通過數(shù)據(jù)實驗對基本郭濤算法和改進郭濤算法進行對比，然后，在改進郭濤算法的基礎(chǔ)上，采用了兩種方式來進行模擬實驗。一種方式的數(shù)據(jù)來源于目前國內(nèi)比較常見的遺傳算法書籍中關(guān)于0-1背包問題的示例；另一種方式的數(shù)據(jù)則是通過隨機產(chǎn)生的十組數(shù)據(jù)，每組數(shù)據(jù)wi的取值范圍是[0，999]，各組中數(shù)據(jù)的個數(shù)分別是20，20，50，50，60，60，80，80，100，100個。這樣可以通過比較來測試算法的收斂性、穩(wěn)定性以及有效性。
??? 實驗環(huán)境：CPU——P-IV 1.7GB；內(nèi)存——256MB；操作系統(tǒng)——Windows 2000 Server；開發(fā)程序——VC++ .net 2003。
4.1 測試1：基本郭濤算法與改進郭濤算法的對比
??? 參數(shù)設(shè)置：群體規(guī)模N=50；初始子空間大小M=8；變異概率p_mutation=0.001；通過雜交新產(chǎn)生個體數(shù)目S=8；修正個體數(shù)目T=5，每次實驗運行100次。實驗Data1、Data2的數(shù)據(jù)來源于文獻[12]，最大演化代數(shù)MaxGen=2000；實驗Data3的數(shù)據(jù)來源于文獻[13]，最大演化代數(shù)MaxGen=10 000；實驗Data4的數(shù)據(jù)來源于文獻[14]，最大演化代數(shù)MaxGen=10000。基本郭濤算法與改進郭濤算法實驗結(jié)果比較見表1。
?
??? 從表1的比較結(jié)果中可以看出：改進的郭濤算法比基本郭濤算法表現(xiàn)出更好的性能，特別是在物品的數(shù)目很大時，它的優(yōu)越性（如：達到最優(yōu)解的次數(shù)和計算時間）得到了更好的體現(xiàn)。
4.2 測試2：數(shù)據(jù)來源于常見的遺傳算法文獻
??? 參數(shù)設(shè)置：群體規(guī)模N=50；初始子空間大小M=8；最大演化代數(shù)MaxGen=2000；變異概率p_mutation=0.001；通過雜交新產(chǎn)生個體數(shù)目S=8；修正個體數(shù)目T=5，每次實驗運行100次。計算結(jié)果見表2。其中數(shù)據(jù)1、數(shù)據(jù)2來源于文獻[11]，數(shù)據(jù)3、數(shù)據(jù)4來源于文獻[1]。
?
4.3 測試3：通過隨機產(chǎn)生10組數(shù)據(jù)的結(jié)果
??? 參數(shù)設(shè)置：群體規(guī)模N=100；初始子空間大小M=8；最大演化代數(shù)MaxGen=10000；變異概率p_mutation=0.005；通過雜交新產(chǎn)生個體數(shù)目S=8；修正個體數(shù)目T=10，每次實驗運行50次。表3為隨機產(chǎn)生的5組強關(guān)聯(lián)性(Strongly correlated instances)數(shù)據(jù)的計算結(jié)果；表4為隨機產(chǎn)生的5組一般強關(guān)聯(lián)性(Almost strongly correlated instances)數(shù)據(jù)的計算結(jié)果。注：相對誤差率＝（最好適應(yīng)度－最壞適應(yīng)度）/平均適應(yīng)度×100％；相對誤差＝最好適應(yīng)度-最壞適應(yīng)度。
?
4.4 結(jié)果分析
??? 表2中的數(shù)據(jù)由于物品的數(shù)量相對比較少，因此，在利用本文中的算法進行計算時穩(wěn)定性很好，而且收斂得也比較快，基本上都能求出問題的最優(yōu)解。從表3和表4中數(shù)據(jù)的計算結(jié)果可以看出，隨著物品數(shù)量的不斷增加，計算時間基本上在不斷增大，但是由于問題的復(fù)雜性是成指數(shù)性增長的，而本文中的計算時間并沒有快速增加，所以這種時間的增加是可以接受的。并且，計算結(jié)果的相對誤差率都在10-4左右。通過對兩個表中的數(shù)據(jù)進行分析可以看出，新算法具有很好的穩(wěn)定性和有效性。
5? 結(jié)? 論
??? 本文為了求解0-1背包問題，在基本郭濤算法的基礎(chǔ)上對其作了一些修改，形成了改進的郭濤算法（IGT）。通過大量的數(shù)值模擬實驗證明了改進郭濤算法在求解0-1背包問題時是很有效的，而且具有很好的穩(wěn)定性。當然，在隨著物品的數(shù)目不斷增加時，新算法收斂的還不是很快，這將在今后的工作中做進一步的研究。
參考文獻
1?? 康立山，謝云，尤矢勇等.非數(shù)值并行算法(第一冊)——模擬退火算法.北京：科學(xué)出版社，1995
2?? 王小平，曹立明.遺傳算法——理論、應(yīng)用與軟件實現(xiàn).西安：西安交通大學(xué)出版社，2004
3?? 胡欣，汪紅星，康立山.求解多維0-1背包問題的混合遺傳算法.計算機工程與應(yīng)用，1999；(11)
4?? 郭濤，康立山，李艷.一種求解不等式約束下函數(shù)優(yōu)化問題的新算法.武漢大學(xué)學(xué)報(自然科學(xué)版)，1999；5(45)
5?? 李艷，康卓，劉溥.郭濤算法及其應(yīng)用.武漢汽車工業(yè)大學(xué)學(xué)報，2000；3(22)
6?? 康卓，李艷，劉溥等.一種通用的混合非線性規(guī)劃問題的演化算法.計算機研究與發(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?? 潘正君，康立山，陳毓屏.演化計算.北京：清華大學(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? 陳國良，王煦法，莊鎮(zhèn)泉等.遺傳算法及其應(yīng)用.北京：人民郵電出版社，2001
12? 馬良，王龍德.背包問題的螞蟻優(yōu)化算法.計算機應(yīng)用，2001；21(8)
13? 張鈴，張鈸.佳點集遺傳算法.計算機學(xué)報，2001；24(9)
14? 金慧敏，馬良.遺傳退火進化算法在背包問題中的應(yīng)用.上海理工大學(xué)報，2004；26(6)