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