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

摘要：針對(duì)一維裝箱問題，在考慮遺傳算法早熟收斂問題和禁忌搜索算法自適應(yīng)優(yōu)點(diǎn)的基礎(chǔ)上，將遺傳算法和禁忌搜索法結(jié)合起來，提出了基于遺傳和禁忌搜索的裝箱優(yōu)化算法，與簡(jiǎn)單遺傳算法相比，該算法具有更好的收斂性能。最后通過實(shí)例驗(yàn)證了算法的有效性。

關(guān)鍵詞：裝箱問題；遺傳算法；禁忌搜索；混合算法

中圖分類號(hào)：F224文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：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）是一類重要的組合優(yōu)化問題，在現(xiàn)實(shí)生活中有著廣泛的應(yīng)用背景，特別在現(xiàn)代物流中，許多問題都抽象化為裝箱問題或其變形，如貨物如何裝載，才能提高運(yùn)載器具的利用率，從而降低運(yùn)輸成本；物流任務(wù)應(yīng)如何調(diào)度，才能提高運(yùn)行效率，等等。但在理論上，裝箱問題是一個(gè)NP難題[1]，很難精確求解。因此對(duì)其求解進(jìn)行研究具有重要的理論價(jià)值和實(shí)際意義。

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

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

1問題描述

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

2遺傳禁忌混合策略

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

禁忌搜索（Tabu Search，TS）最早是由Glover提出的，是對(duì)局部鄰域搜索的一種擴(kuò)展，通過引入一個(gè)靈活的存儲(chǔ)結(jié)構(gòu)和相應(yīng)的禁忌準(zhǔn)則來避免迂回搜索，并通過藐視準(zhǔn)則來赦免一些被禁忌的優(yōu)良狀態(tài)，進(jìn)而保證多樣化的有效探索以最終實(shí)現(xiàn)全局優(yōu)化。但禁忌搜索時(shí)搜索效率低，并且禁忌搜索對(duì)初始解具有較強(qiáng)的依賴性[3]。

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

3遺傳禁忌混合算法設(shè)計(jì)

3.1算法步驟

步驟7如果t＜T，令t=t+1，轉(zhuǎn)步驟3，否則轉(zhuǎn)步驟8。

步驟8輸出最優(yōu)解，終止算法。

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

（1）按照變異概率從當(dāng)前代中隨機(jī)選擇部分個(gè)體進(jìn)入禁忌搜索集合，給定算法參數(shù)。

（2）從禁忌搜索中隨機(jī)選取一個(gè)個(gè)體作為當(dāng)前解，置禁忌表為空。

（3）利用當(dāng)前解的鄰域函數(shù)產(chǎn)生所有（或若干）鄰域解，并從中選擇部分候選解。

（4）對(duì)候選解判斷藐視準(zhǔn)則是否滿足? 若是，則用滿足藐視準(zhǔn)則的最佳狀態(tài)y代替x成為新的當(dāng)前解，即x=y，并用與y對(duì)應(yīng)的禁忌對(duì)象替換最早進(jìn)入禁忌表的禁忌對(duì)象，修改禁忌表中各禁忌對(duì)象的任期，同時(shí)用y替換“best so far”狀態(tài)，然后轉(zhuǎn)步驟（6）；否則，繼續(xù)以下步驟。

（5）判斷候選解對(duì)應(yīng)的各對(duì)象的禁忌屬性。將候選解集中非禁忌對(duì)象對(duì)應(yīng)的最佳狀態(tài)作為新的當(dāng)前解，同時(shí)用與之對(duì)應(yīng)的禁忌對(duì)象替換最早進(jìn)入禁忌表的禁忌對(duì)象，并修改禁忌表中各禁忌對(duì)象的任期。

（6）判斷對(duì)該解的禁忌搜索是否滿足終止條件，若是，則結(jié)束搜索，轉(zhuǎn)步驟（7）；否則返回步驟（3）。

（7）判斷禁忌搜索集合中的每個(gè)解是否都搜索完畢，若是結(jié)束該過程；否則轉(zhuǎn)步驟（2）。

3.2參數(shù)設(shè)計(jì)

（1）編碼方案。本文采用自然數(shù)編碼。把所有物體按順序進(jìn)行編號(hào)，隨機(jī)生成一個(gè)序列，從而組成一個(gè)染色體。例如有5個(gè)物體需要裝箱，生成的染色體可能有（1，2，3，4，5）和（2，5，4，1，3）等。用這種編碼方法，沒有把箱子編入染色體中，染色體的結(jié)構(gòu)僅和物體有關(guān)[5]。

（2）適應(yīng)度函數(shù)。因?yàn)楸疚闹醒芯康难b箱問題，是以所用箱子數(shù)最少為目標(biāo)函數(shù)，即目標(biāo)函數(shù)是求問題的最小解。假設(shè)某一染色體對(duì)應(yīng)的箱子數(shù)是Fx，則適應(yīng)度函數(shù)可表示為fx=K-Fx，其中K是一足夠大的正數(shù)。

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

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

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

（5）變異算子。采用禁忌搜索算法作為變異算子，把一個(gè)要變異的染色體作為禁忌搜索的輸入，把禁忌搜索得到的解作為變異的新個(gè)體，在這里以染色體本身為禁忌對(duì)象，采用兩點(diǎn)互換操作構(gòu)造鄰域并從中選擇部分個(gè)體作為候選解，以目標(biāo)函數(shù)值作為藐視準(zhǔn)則。

4仿真試驗(yàn)

4.1算例一

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

={100，100，0.7，0.1，4}進(jìn)行試算，運(yùn)行20次，以100%的概率找到最優(yōu)解4，與文獻(xiàn)[5]中的計(jì)算結(jié)果比較如表1所示。

由以上數(shù)據(jù)可以看出，與文獻(xiàn)[5]中采用的混合遺傳算法和簡(jiǎn)單遺傳算法相比，本文算法能在較短的時(shí)間內(nèi)收斂到最優(yōu)解，其效率要優(yōu)于以上兩種算法。

4.2算例二

為了進(jìn)一步測(cè)試本混合算法的性能，作者對(duì)另外19組數(shù)據(jù)進(jìn)行試驗(yàn)并和簡(jiǎn)單遺傳算法比較，這些數(shù)據(jù)由隨機(jī)方法產(chǎn)生，箱子數(shù)從10到100個(gè)，算法由Matlab編程實(shí)現(xiàn)。實(shí)驗(yàn)結(jié)果如圖2所示。

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

5結(jié)論

本文為求解裝箱問題提出了一種基于遺傳算法和禁忌搜索的混合算法，該算法具有多點(diǎn)出發(fā)和爬山能力強(qiáng)等特點(diǎn)，有效地解決了傳統(tǒng)遺傳算法的早熟收斂問題。通過實(shí)例計(jì)算，證明遺傳禁忌混合算法是一種行之有效的算法，對(duì)解決裝箱問題有很好的實(shí)用價(jià)值。

參考文獻(xiàn)：

[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] 王凌. 智能優(yōu)化算法及其應(yīng)用[M]. 北京：清華大學(xué)出版社，施普林格出版社，2001.

[4] 李大衛(wèi)，王莉，王夢(mèng)光. 遺傳算法與禁忌搜索算法的混合策略[J]. 系統(tǒng)工程學(xué)報(bào)，1998，13(3):28-34.

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