求解裝箱問題的遺傳算法

《求解裝箱問題的遺傳算法》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在學術論文-天天文庫。

1、南昌航空工業(yè)學院學報1998年第2期JournalofNanchangInstituteofAeronauticalTechnology№21998求解裝箱問題的遺傳算法方平李娟(南昌航空工業(yè)學院)(西北工業(yè)大學)摘要:本文提出了兩種求解裝箱問題(BinPacking)的遺傳算法。一種是簡單遺傳算法,它采用等長度字符代碼編碼方法,使用常規(guī)的遺傳操作算子。另一種是混合遺傳算法,它綜合運用解裝箱問題的FFD(FirstFitDe2creasing)近似算法和簡單遺傳算法。試算結果表明,由這兩種遺傳算法所得到的裝箱方案較一些近似算法所得到的裝箱方案都要

2、好。關鍵詞:遺傳算法;裝箱問題;組合;優(yōu)化中圖分類號:TP30116前言管理工程、工業(yè)工程等領域中的一些問題(例如人力資源分配、運輸計劃等)均可建議為裝箱(BinPacking),對其求解方法的研究具有一定的應用價值。裝箱問題的一般提法如下所述:設有n個物品u1,u2,?,un要裝箱發(fā)送,已知每個物品的體積為v(ui)∈(0,1],(i=1,2,?,n)現(xiàn)規(guī)定每個箱子的容量為1,問如何確定裝箱方案可使得裝完這n個物品所需要用的箱子數(shù)目為最小?從計算復雜性理論來講,裝箱問題是一個NP難題,很難精確求解。目前的求解方法主要是一些近似算法,如NF(Ne

3、xtFit)近似算法、FF(FirstFit)近似算法、FFD(FirstFitDecreas2[1]ing)近似算法等。近似算法的求解結果與物品的體積數(shù)據(jù)有較大關系,有時在極端情況下的求解結果很不理想。本文分別用二種遺傳算法對該問題進行了求解,一種是用簡單遺傳算法,另一種是用由簡單遺傳算法和FFD近似算法組成的混合遺傳算法。1求解裝箱問題的簡單遺傳算法111染色體編碼方法假設k個箱子的編號分別為B1,B2,?,Bk,(K≤n)。n件物品要裝入這k個箱子中,要說明的是,有時幾件物品可以裝入同一個箱子中,所以不一定要全部用完這k個箱子。各個物品ui

4、(i=1,2,?,n)所裝入箱子之編號的順序排列就構成該問題的染色體編碼,即我們使用的收稿日期:1988-04-10第一作者:方平,男,1962年出生,講師21是等長度的字符代碼編碼方法。例如:B3B1B8B1??????B3B1n就代表一個裝箱方案(群體中的一個個體),表示將第1、n-1件物品裝入B3箱;第2、4、n件物品裝入B1箱;第3件物品裝入B8箱,等等。初始種群可以由B1,B2,?,Bk的隨機排列產(chǎn)生。由個體的染色體編碼串可統(tǒng)計出某一裝箱方案用了幾只箱子。112目標函數(shù)和適應函數(shù)設m為某一裝箱方案中所用箱子的數(shù)目,B(ui)為物品ui所

5、裝入箱子的編號,Sj為考慮了罰函數(shù)之后的Bj箱所裝物品的體積之和。要使所用箱子數(shù)目最少,可以取下式為優(yōu)化目標函數(shù):mmf(X)=m?(m-∑sj)=m?{m-∑[∑v(ui)-A?max(0,∑v(ui)-1)]}j=1j=1B(u)=BB(u)=Bijij式中A為某一箱子Bj中所裝物品的體積之和超出箱子規(guī)定容積時的懲罰因子。該目標函數(shù)既考慮了使用箱子的數(shù)目最小,又考慮了使每個箱子裝完物品后所剩余的容積盡可能的小。適應函數(shù)取為下式:Cmax-f(X),f(X)

6、總取非負值。113遺傳算子的選用[2]可使用通過的一些遺傳操作算子,如交叉操作使用單點交叉算子或雙叉算子;變異操作使用字符集范圍內(nèi)均勻變異算子;選擇操作使用比例選擇算子。2求解裝箱問題的混合遺傳算法上述解裝箱問題的簡單遺傳算法的缺點是,初始種群和進化過程中可能會產(chǎn)生一些無效染色體,這些無效染色體所表示的裝箱方案中,某一箱子所裝物品的體積之和超過箱子的規(guī)定容量,從而使得運算效率降低,也會導致得不到好的運算結果。這里我們將求解裝箱問題的FFD近似算法與簡單遺傳算法相結合,構成一種混合遺傳算法,使得進化過程能夠借鑒FFD近似算法的思想,修正無效染色體為

7、合理的染色體,從而提高遺傳算法的運行效率和解的質(zhì)量。FFD近似算法的主要思想是:將物品按體積大小降序排列,然后依該秩序來對各個物品裝箱;對某一物品,它總是裝到第一個能裝下它的箱子中。將上述思想應用到遺傳算法的解碼過程中。這個具有FFD思想的解碼過程的主要步驟可描述如下:(1)將物品按體積大小降序排列。(2)依上秩序處理各個箱子中的所有物品。若箱子Bi中所裝物品的體積之和超出限制,則將超出部分裝到Bi+1箱子中。22(3)若Bm箱中所裝物品的體積之和已超出其規(guī)定的容量,則取一只新的箱子裝入超出部分的物品,且m←m+1。對染色體編碼串使用上述解碼過程

8、之后,所表示的裝箱方案既符合FFD近似算法的思想,同時各個箱子所裝物品的體積之和也不會超過其規(guī)定的容積。這樣,計算目標函數(shù)時,無需再引入