一種求解裝箱問題的混合算法

摘要：針對一維裝箱問題，在考慮遺傳算法早熟收斂問題和禁忌搜索算法自適應優點的基礎上，將遺傳算法和禁忌搜索法結合起來，提出了基于遺傳和禁忌搜索的裝箱優化算法，與簡單遺傳算法相比，該算法具有更好的收斂性能。最后通過實例驗證了算法的有效性。

關鍵詞：裝箱問題；遺傳算法；禁忌搜索；混合算法

中圖分類號：F224文獻標識碼：A文章編號：1002-3100(2008)12-0029-03

Abstract: This paper presents a new hybrid algorithm based on genetic algorithm and tabu search for bin packing problem. It combines the advantage of global search ability of genetic algorithm with the adaptability of tabu search and has better convergence performance than simple genetic algorithm. At last， an practical example is applied to prove the efficiency of this algorithm.

Key words: bin packing problem; genetic algorithm; tabu search; hybrid algorithm

0引言

裝箱問題（Bin Packing Problem， BPP）是一類重要的組合優化問題，在現實生活中有著廣泛的應用背景，特別在現代物流中，許多問題都抽象化為裝箱問題或其變形，如貨物如何裝載，才能提高運載器具的利用率，從而降低運輸成本；物流任務應如何調度，才能提高運行效率，等等。但在理論上，裝箱問題是一個NP難題[1]，很難精確求解。因此對其求解進行研究具有重要的理論價值和實際意義。

到目前為止，針對該問題人們提出了許多算法，但都有其局限性：枚舉法和分支定界等精確算法在箱子數目稍大時，會出現“組合爆炸”；一些近似算法如下次適應NF、首次適應FF、降序首次適應FFD、最佳適應BF等，在解決復雜的裝箱問題時結果與物品的體積數據有較大關系，在極端情況下很不理想；遺傳算法能在合理的時間內求得最優解或滿意解，但易陷入局部最優。

本文針對以上算法的不足，提出一種混合算法，該算法結合遺傳算法良好的全局搜索能力和禁忌搜索具有記憶能力的全局逐步優化特性，增強全局和局部意義下的搜索能力和效率。實例證明，在求解裝箱問題時，該算法性能明顯優于單純遺傳算法。

1問題描述

式（1）是裝箱問題的目標函數；式（2）保證裝入箱子的物體重量之和不超過其容量限制；式（3）保證每個物體都被放入箱子中；式（4）與式（5）是決策變量的整數約束。

2遺傳禁忌混合策略

遺傳算法（Genetic Algorithm， GA）是Holland教授于20世紀60年代受生物進化論的啟發而提出的一種基于生存遺傳和進化機制的隨機優化方法。它將問題的求解表示成染色體適者生存的過程，通過染色體群的一代代不斷進化，包括復制、交叉和變異等操作，最終收斂到最適應環境的個體，從而求得問題的最優解或滿意解[2]。遺傳算法開創了在解空間中從多出發點搜索問題的先河[4]，能從概率的意義上以隨機的方式尋求到問題的最優解，具有并行性，很強的通用性，良好的全局性和魯棒性等特點。但是，在實際應用中，由于受選擇壓力、交叉和變異操作等因素的影響，容易出現早熟現象，局部搜索能力差。

禁忌搜索（Tabu Search，TS）最早是由Glover提出的，是對局部鄰域搜索的一種擴展，通過引入一個靈活的存儲結構和相應的禁忌準則來避免迂回搜索，并通過藐視準則來赦免一些被禁忌的優良狀態，進而保證多樣化的有效探索以最終實現全局優化。但禁忌搜索時搜索效率低，并且禁忌搜索對初始解具有較強的依賴性[3]。

鑒于以上兩種算法各自的優缺點，本文設計了一種混合算法，將遺傳算法和禁忌搜索結合起來，相互取長補短，這樣混合算法具有遺傳算法多出發點和禁忌搜索的記憶功能及爬山能力強的特點[4]。混合算法結構如圖1所示，具體來講，就是將禁忌搜索作為遺傳算法的變異算子，初始群體經過選擇、交叉操作后產生的新個體作為禁忌搜索的初始解，然后禁忌搜索每一個參與變異的個體，搜索后的新個體與未變異的個體形成新的種群，再對新種群中的個體進行上述混合操作，直至算法終止。

3遺傳禁忌混合算法設計

3.1算法步驟

步驟7如果t＜T，令t=t+1，轉步驟3，否則轉步驟8。

步驟8輸出最優解，終止算法。

禁忌搜索算法操作步驟如下：

（1）按照變異概率從當前代中隨機選擇部分個體進入禁忌搜索集合，給定算法參數。

（2）從禁忌搜索中隨機選取一個個體作為當前解，置禁忌表為空。

（3）利用當前解的鄰域函數產生所有（或若干）鄰域解，并從中選擇部分候選解。

（4）對候選解判斷藐視準則是否滿足? 若是，則用滿足藐視準則的最佳狀態y代替x成為新的當前解，即x=y，并用與y對應的禁忌對象替換最早進入禁忌表的禁忌對象，修改禁忌表中各禁忌對象的任期，同時用y替換“best so far”狀態，然后轉步驟（6）；否則，繼續以下步驟。

（5）判斷候選解對應的各對象的禁忌屬性。將候選解集中非禁忌對象對應的最佳狀態作為新的當前解，同時用與之對應的禁忌對象替換最早進入禁忌表的禁忌對象，并修改禁忌表中各禁忌對象的任期。

（6）判斷對該解的禁忌搜索是否滿足終止條件，若是，則結束搜索，轉步驟（7）；否則返回步驟（3）。

（7）判斷禁忌搜索集合中的每個解是否都搜索完畢，若是結束該過程；否則轉步驟（2）。

3.2參數設計

（1）編碼方案。本文采用自然數編碼。把所有物體按順序進行編號，隨機生成一個序列，從而組成一個染色體。例如有5個物體需要裝箱，生成的染色體可能有（1，2，3，4，5）和（2，5，4，1，3）等。用這種編碼方法，沒有把箱子編入染色體中，染色體的結構僅和物體有關[5]。

（2）適應度函數。因為本文中研究的裝箱問題，是以所用箱子數最少為目標函數，即目標函數是求問題的最小解。假設某一染色體對應的箱子數是Fx，則適應度函數可表示為fx=K-Fx，其中K是一足夠大的正數。

Fx由下次適應法NF確定。具體步驟是依次從每個隨機生成的染色體中按順序取出每個基因（即物體）放入一個箱子中，如果該箱子放滿了，則放入下一個箱子，直到所有物品放完為止，此時所用的箱子數即為Fx。

（3）選擇算子。在這里使用輪盤賭選擇算子，也叫比例選擇算子，即個體被選中并遺傳到下一代群體中的概率與該個體的適應度大小成正比。同時，在選擇的過程中引入最優保存策略，用上一代適應值最大的染色體代替新一代適應值最低的染色體，可保證當前的最優個體不會被破壞，加速算法向最優解收斂。

（4）交叉算子。交叉是指對兩個相互配對的染色體以某種方式相互交換部分基因，從而形成兩個新的個體。本文選擇最基本兩點交叉算子，其具體執行過程如下：①群體中的個體進行兩兩配對。②對每一對相互配對的個體，隨機設置兩個位置為交叉點。③對每一對相互配對的個體，依設定的交叉概率的交叉點相互交換兩個交叉點之間的染色體，從而產生出兩個新的個體。

（5）變異算子。采用禁忌搜索算法作為變異算子，把一個要變異的染色體作為禁忌搜索的輸入，把禁忌搜索得到的解作為變異的新個體，在這里以染色體本身為禁忌對象，采用兩點互換操作構造鄰域并從中選擇部分個體作為候選解，以目標函數值作為藐視準則。

4仿真試驗

4.1算例一

采用以上算法步驟，作者試算了文獻[5]中的一組數據，這是一個由15個物體和足夠多的單位箱子（容量為1）組成的裝箱問題，物品重量w=0.3， 1≤i≤90.2， 10≤i≤15。設定混合算法的運行參數為{迭代次數，種群大小，交叉概率，變異概率，禁忌長度}

={100，100，0.7，0.1，4}進行試算，運行20次，以100%的概率找到最優解4，與文獻[5]中的計算結果比較如表1所示。

由以上數據可以看出，與文獻[5]中采用的混合遺傳算法和簡單遺傳算法相比，本文算法能在較短的時間內收斂到最優解，其效率要優于以上兩種算法。

4.2算例二

為了進一步測試本混合算法的性能，作者對另外19組數據進行試驗并和簡單遺傳算法比較，這些數據由隨機方法產生，箱子數從10到100個，算法由Matlab編程實現。實驗結果如圖2所示。

通過以上比較圖，我們可以看到，當物品數量較少10≤n≤30時，兩種算法最終收斂到相同的解。隨著問題規模的擴大，簡單遺傳算法的裝箱方案所使用的箱子數要比混合算法的多。用△表示多用的箱子，當物品數n=50，△=2，△隨n的增大而逐漸增大，當n=100，△=5。由此可見，當箱子數量增大的一定規模時，簡單遺傳算法因其固有的缺點，在運行過程中可能會過早收斂到非滿意解，不適合用來求解；而此時混合算法卻能在較短的時間內求得較優的裝箱方案，表現出明顯的優越性。

5結論

本文為求解裝箱問題提出了一種基于遺傳算法和禁忌搜索的混合算法，該算法具有多點出發和爬山能力強等特點，有效地解決了傳統遺傳算法的早熟收斂問題。通過實例計算，證明遺傳禁忌混合算法是一種行之有效的算法，對解決裝箱問題有很好的實用價值。

參考文獻：

[1]Garey M R， Johnson D S. Computers and intractabililty: a guide to the theory of NP-completeness[M]. San Francisco:Freeman，1979.

[2]Coffman E G， Garey M R， Johnson D S. Approximation Algorithms for Bin packing: A survey[C]//In: D Hochbaumed.Approximation Algorithms for NP-Hard problems. Boston: PWS Publishing，1996，46-93.

[3] 王凌. 智能優化算法及其應用[M]. 北京：清華大學出版社，施普林格出版社，2001.

[4] 李大衛，王莉，王夢光. 遺傳算法與禁忌搜索算法的混合策略[J]. 系統工程學報，1998，13(3):28-34.

[5] 湯巖，賈紅雨，廖潔君. 混合遺傳算法在裝箱問題中的應用研究[J]. 計算機與現代化，2004(11):13-14，18.