混合遺傳模擬退火算法求解背包問題

林 耿

(閩江學院 數學系，福建 福州 350108)

背包問題是運籌學中一個著名的問題，它是指從n個不同價值和重量的物品集合中選擇若干個物品裝入指定容量C的背包，使得被選物品的總重量不超過背包容量且價值總和最大.假設第i個物品的價值和重量分別為pi和wi,引入向量x∈{0,1}n，當物品i被選擇放入背包時,xi=1；否則xi=0.背包問題可以建模為如下的整數規劃模型：

背包問題屬于帶約束的NP困難問題[1]，在現實生活中有著廣泛的應用背景，比如貨物裝載、工廠下料、電子商務和軟硬件劃分等[2].并且背包問題往往作為子問題出現在許多復雜的組合優化問題中，所以研究背包問題的有效求解算法具有重要的理論和實際意義.

常見的求解背包問題的算法有精確算法和智能優化算法[3-6].精確算法具有指數時間的算法復雜度，難以應用于求解大規模問題.智能優化算法能夠較快地求得精度較高的近似解，特別是遺傳算法和模擬退火算法操作簡單實用，受到了學者們的廣泛關注.然而，每種算法都有其自身的優勢和缺陷.遺傳算法[7]是一種基于自然選擇和自然遺傳學機制上的隨機搜索算法，具有較強的全局搜索性能，但是遺傳算法在搜索過程中容易出現早熟現象.模擬退火算法模擬固體退火的過程，不僅能夠向目標函數優化的方向迭代，而且通過引入接受準則，能夠以一定概率接受較差的解，從而避免陷入局部最優解，但當問題規模較大時，收斂速度較慢.

本研究將模擬退火算法有效地融入遺傳算法，結合遺傳算法和模擬退火算法的優點，提出了一種求解背包問題的混合遺傳模擬退火算法，有效地避免陷入局部最優解.與單純的遺傳算法比較，實驗結果表明了該混合算法求解背包問題的有效性和適用性.

1 混合遺傳模擬退火算法

遺傳算法具有很強的全局搜索能力，但是局部搜索能力較差，容易陷入局部最優解.模擬退火算法具有較強的局部搜索能力，但搜索速度較慢.本研究將這兩個算法結合起來，提出混合的遺傳模擬退火算法，隨機構造種群，采用模擬退火對種群中的解進行局部搜索，引入新的種群更新策略，保持種群的多樣性，避免早熟現象發生.

1.1 適應度函數

1.2 改進的模擬退火局部搜索算法

傳統模擬退火算法能夠有效避免陷入局部最優解，但當問題的規模較大時，模擬退火算法的收斂速度較慢.本研究基于模擬退火的思想，提出了一個改進模擬退火局部搜索算法SALS，加快了局部搜索的速度.設x為初始解，N(x)為x的某個鄰域結構，T>0為SALS算法的參數，則SALS算法可描述為：

(1)初始化，down=0,xmax=x.

(2)計算N(x)中所有解的適應度函數值，假設y是N(x)中適應度函數值最大的解，令Δf=f(y)-f(x).

(3)如果Δf>0，則令x=y，轉(2)；否則，如果f(y)>f(xmax)，令xmax=y，轉(4).

(4)如果down

1.3 交叉算子

假設x和y是從種群中選擇到的兩個解，本研究采用fixed交叉算子[8]來產生新的解向量z.fixed交叉算子的基本思想是：如果第i個物品在x和y中都是處于裝入狀態，則在新的解中將該物品裝入背包，即zi=1；如果第i個物品在x和y中都是處于未裝入狀態，則在新的解中不將該物品裝入背包，即zi=0；如果第i個物品在x和y中的狀態不一樣，那么在新的解中以50%的概率裝入背包.

1.4 種群更新策略

良好的種群更新策略應當既能維持高質量的解，又能保持種群的多樣性. 采用如下的種群更新策略：一個解如果能夠插入種群中，那么它要么提高了種群中解的質量，要么使種群中的解更多樣化.假設x1和x2分別為種群中適應度函數值最大和最小的解，y為新產生的解.如果y的適應度函數值比x1大，即f(y)>f(x1)，則將y插入種群，并將x2從種群中刪除.假設函數H(y,x1)表示解y和x1間的海明距離，函數H(x2,x1)表示解x2和x1間的海明距離,如果H(y,x1)+f(y)>H(x2,x1)+f(x1)，則將y插入種群，并將x2從種群中刪除.否則，不改變種群的結構.

2 算法求解步驟

基于以上分析，提出了混合遺傳模擬退火算法，算法的具體步驟如下：

(1)隨機產生s個解向量構造出初始種群{x1,…,xs}.

(2)對種群中的每個解xi應用改進的模擬退火局部搜索算法SALA進行局部搜索，所得結果仍記為xi.

(3)隨機選出種群中的兩個解，應用fixed交叉算子構造新解z，并利用SALA算法對z進行優化，優化結果仍記為z.

(4)應用更新策略更新種群.如果算法已經持續NO次未找到更好的解，則停機，輸出種群中適應度函數值最大的解；否則轉(3).

其中，NO為算法的停止參數.

3 仿真實驗

為了驗證本算法的有效性，選取文獻[6]中的實例來測試本算法，并將結果與文獻[6]中的結果進行對比.采用Visual C++進行編程實驗，實驗環境為AMD 2.11 GHz處理器，1 GB內存，Windows XP 操作系統,實驗例子的數據如下：

P={p1,…,p25}={350，310，300，295，290，287，283，280，272，270，265，251，230，220，215，212，207，203，202，200，198，196，190，182，181}，

W={w1,…,w25}={135，133，130，11，128，123，20，75，9，66，105，43，18，5，37，90，22，85，9，80，70，17，60，35，57}，C=1 400.文獻[6]采用遞歸算法求得該問題的最優解，最優解的目標函數值和總質量分別為5 686和1 398.

表1 實驗結果

由表1可得，混合遺傳模擬退火算法能夠找到比單純的遺傳算法更好的解，能夠避免早熟現象并有效地提高背包的利用率.

4 結論

提出了一種求解背包問題的混合遺傳模擬退火算法，該算法發揮了遺傳算法和模擬退火算法的優勢，采用同時考慮解的質量和種群多樣性的種群更新策略，有效地避免了早熟現象，并且加快了局部搜索速度.與單純的遺傳算法比較，實驗結果證明了算法的有效性.

參考文獻：

[1]Garey M,Johnson D.Computers and intractability:a guide to the theory of NP-completeness[M].Freeman:San Francisco,1979:71-72.

[2]Ray A,Wu J G,Thambipillai S. Knapsack model and algorithm for HW/SW partitioning problem[J].Lecture Notes in Computer Science,2004(3036):200-205.

[3]趙新超，韓宇，艾文寶.求解背包問題的一種改進遺傳算法[J].計算機工程與應用，2011，47(24):34-36.

[4]苗世清，高岳林.求解0/1背包問題的離散差分進化算法[J].小型微型計算機系統,2009，30(9):1828-1830.

[5]錢淑渠，武慧虹，涂歆.動態免疫優化算法及其在背包問題中的應用[J].計算機工程，2011，37(20):216-218.

[6]程春英，張玉春.利用遺傳算法求解0/1背包問題[J].內蒙古民族大學學報，2010,25(6):637-639.

[7]陳國良，王煦法，莊鎮泉，等.遺傳算法及其應用[M].北京:人民郵電出版社，2001.

[8]Chardaire P,Barake M, McKeown G P.A probe-based heuristic for graph partitioning[J].IEEE Transactions on Computers,2007,56(12):1707-1720.