摘 要: 將模擬退火的思想引入遺傳算法" title="遺傳算法">遺傳算法中,將兩者結(jié)合起來,探討了模擬退火遺傳算法在復(fù)雜集裝箱裝載" title="集裝箱裝載">集裝箱裝載中的應(yīng)用,以此達(dá)到縮小搜索區(qū)域,增強(qiáng)算法的收斂性的目的。該算法充分發(fā)揮了遺傳操作中交叉算子的作用,并通過實(shí)例仿真表明該算法優(yōu)于傳統(tǒng)的計(jì)算方法。
關(guān)鍵詞: 集裝箱裝載 模擬退火遺傳算法 啟發(fā)式算法
目前,物流業(yè)正處在快速發(fā)展的時(shí)期,集裝箱運(yùn)輸將會(huì)有大幅度的增長(zhǎng)。集裝箱裝載作為物流配送過程中的一個(gè)關(guān)鍵性環(huán)節(jié),可提高配送業(yè)務(wù)的自動(dòng)化水平、提高貨物裝載的優(yōu)化程度、提高配送業(yè)務(wù)的工作效率和規(guī)范業(yè)務(wù)流程等。
從二十世紀(jì)70年代初開始,集裝箱裝載問題就引起了廣泛的研究和探討[1]。裝箱問題就是將不同尺寸的物品擺放入有一定容量的容器中,以獲得某種最佳的效益。從計(jì)算復(fù)雜性理論來講,裝箱問題屬于NP完全問題[2],求解極為困難。
遺傳算法采用了生物進(jìn)化論的思想,通過自然選擇和適者生存的競(jìng)爭(zhēng)策略來求解優(yōu)化問題[3];模擬退火起源于統(tǒng)計(jì)物理學(xué)方法,并首先被Kirkpatrick等引入組合優(yōu)化領(lǐng)域[4]。遺傳算法的全局搜索性能較強(qiáng),但是其容易過早收斂,而且在進(jìn)化后期搜索效率較低,種群的進(jìn)化緩慢;而模擬退火算法" title="模擬退火算法">模擬退火算法具有較強(qiáng)的局部搜索能力,并且能使搜索過程避免陷入局部最優(yōu)解,但是把握搜索過程的能力不強(qiáng),運(yùn)行效率不高。本文通過將模擬退火的思想引入遺傳算法,使兩者有效地結(jié)合,緩解了遺傳算法的選擇壓力,增強(qiáng)了遺傳算法的全局收斂性,避免在搜索過程中陷入局部最優(yōu)。
1 遺傳算法
遺傳算法最早由美國(guó)Michigan大學(xué)的J. Holland教授提出,起源于上世紀(jì)60年代人們對(duì)自然和人工自適應(yīng)系統(tǒng)的研究[5],是基于Darwin進(jìn)化論和Mendel的遺傳學(xué)說的一種全局優(yōu)化概率搜索算法,它模擬了生物界中的生命進(jìn)化機(jī)制,在人工系統(tǒng)中實(shí)現(xiàn)特定目標(biāo)的優(yōu)化。對(duì)于復(fù)雜的優(yōu)化問題,遺傳算法無需建模和進(jìn)行復(fù)雜的運(yùn)算。與傳統(tǒng)的搜索算法不同,遺傳算法把優(yōu)化問題的解的搜索空間轉(zhuǎn)化為遺傳空間,從代表問題可能潛在解集的一個(gè)種群開始,其中種群中的每一個(gè)體對(duì)應(yīng)問題的一個(gè)解,稱為染色體。初代種群產(chǎn)生后,按照適者生存和優(yōu)勝劣汰的原理,逐代演化產(chǎn)生出越來越好的近似解。在每一代,按預(yù)先根據(jù)目標(biāo)函數(shù)確定的適應(yīng)度函數(shù)計(jì)算各個(gè)體對(duì)問題環(huán)境的適應(yīng)值,再根據(jù)個(gè)體的適應(yīng)值對(duì)個(gè)體對(duì)應(yīng)的染色體進(jìn)行選擇,使適應(yīng)性好的染色體比適應(yīng)性差的染色體有更多的繁殖機(jī)會(huì);然后進(jìn)行交叉、變異等遺傳操作產(chǎn)生新一代群體。如此循環(huán),逐步向優(yōu)化的種群進(jìn)化。
遺傳算法的主要特點(diǎn)是:遺傳算法的處理對(duì)象不是參數(shù)本身,而是對(duì)參數(shù)集進(jìn)行編碼的個(gè)體;遺傳算法采用同時(shí)處理群體中多個(gè)個(gè)體的方法,即同時(shí)對(duì)搜索空間中的多個(gè)解進(jìn)行評(píng)估;遺傳算法僅使用問題的目標(biāo)函數(shù)進(jìn)行工作,不需要其他的先決條件或輔助信息;遺傳算法不是采用確定性規(guī)則進(jìn)行工作,而是采用概率的變遷規(guī)則來指導(dǎo)其搜索方向;遺傳算法具有隱形并行性,可以在較大的解空間迅速尋優(yōu)。
標(biāo)準(zhǔn)的遺傳算法求解過程如下:
(1) 初始化遺傳算法的控制參數(shù),如群體規(guī)模N、變異概率pm、交叉概率pc;
(2) 隨機(jī)產(chǎn)生初始解群p(t)={p0 p1 p2…pn},個(gè)體的數(shù)目一定,每個(gè)個(gè)體表示為染色體的基因編碼;
(3) 計(jì)算群體中每個(gè)個(gè)體的適應(yīng)函數(shù)" title="適應(yīng)函數(shù)">適應(yīng)函數(shù)值;
遺傳算法在搜索過程中基本不利用外部信息,僅以適應(yīng)度函數(shù)為依據(jù),利用種群中每個(gè)個(gè)體的適應(yīng)度值進(jìn)行搜索。因此適應(yīng)度函數(shù)的選取至關(guān)重要,將直接影響遺傳算法的收斂速度以及能否找到最優(yōu)解。解的好壞用適宜度函數(shù)值的大小評(píng)價(jià),適應(yīng)度函數(shù)值越大,解的質(zhì)量越好。
(4) 根據(jù)個(gè)體的適應(yīng)度選擇復(fù)制再生個(gè)體,適應(yīng)函數(shù)值大的個(gè)體的復(fù)制概率大;
選擇是指以一定的概率從種群中選擇優(yōu)勝個(gè)體,淘汰劣質(zhì)個(gè)體的操作。選擇的過程是一種基于適應(yīng)度的優(yōu)勝劣汰的過程,是用來確定重組或交叉?zhèn)€體,以及被選個(gè)體將產(chǎn)生多少個(gè)子代個(gè)體。
(5) 按照一定的交叉概率和交叉方法,對(duì)現(xiàn)有解群中的個(gè)體實(shí)施交叉操作,生成新個(gè)體;
交叉是指對(duì)兩個(gè)相互配對(duì)的染色體以某種方式相互交換部分基因,從而形成兩個(gè)新的個(gè)體,交叉是遺傳算法的核心。
(6) 按照一定的變異概率和變異方法,對(duì)交叉后的個(gè)體進(jìn)行變異操作;
變異運(yùn)算是指將個(gè)體染色體編碼串中的某些基因座上的基因值用該基因座的其他等位基因替換,從而形成一個(gè)新的個(gè)體。
(7) 由交叉和變異產(chǎn)生了新一代種群,若滿足收斂條件,遺傳進(jìn)化過程結(jié)束;否則轉(zhuǎn)(3)。
2 模擬退火算法
模擬退火算法是基于Monte Carlo迭代求解法的一種啟發(fā)式隨機(jī)搜索算法,它模擬固體物質(zhì)退火過程的熱平衡問題與隨機(jī)搜索尋優(yōu)問題的相似性來達(dá)到尋找全局最優(yōu)或近似全局最優(yōu)的目的。在搜索最優(yōu)解的過程中,模擬退火法除了可以接受優(yōu)化解外,還用一個(gè)隨機(jī)接受準(zhǔn)則(Metropolis準(zhǔn)則)有限度地接受惡化解,并且接受惡化解的概率慢慢趨向于0,這使得算法有可能從局部極值區(qū)域中跳出,即可能找到全局最優(yōu)解,并保證了算法的收斂性。
模擬退火算法的求解過程如下:
(1) 隨機(jī)產(chǎn)生初始解x0;
(2) 初始化退火溫度T0;
(3) 在溫度TK下執(zhí)行如下操作:
·產(chǎn)生新的可行解x′,x′為x的鄰解;
·計(jì)算評(píng)價(jià)函數(shù)f(x′)和f(x)的差值△f=f(x′)-f(x);
·以min{1,exp(-△f/Tk)}>random[0,1]的概率接收新解,其中random[0,1]是[0,1]之間的隨機(jī)數(shù)。若達(dá)到溫度Tk的平衡狀態(tài)轉(zhuǎn)(4),否則轉(zhuǎn)(3);
(4) 按一定方式降低溫度,可定義下降函數(shù)為Tk+1=αTK,k+1→k,其中α∈[0,1];
(5) 若滿足收斂判據(jù),退火過程結(jié)束;否則轉(zhuǎn)(3)。
通過以上分析可知,在模擬退火過程中,其退火溫度控制著求解過程向最小值的優(yōu)化方向進(jìn)行,同時(shí)它又以概率exp(-△f/Tk)接收劣質(zhì)解,因此算法可以跳出局部極值點(diǎn)。只要初始溫度足夠高,退火過程足夠慢,算法能夠收斂到全局最優(yōu)解。
3 模擬退火遺傳算法
雖然遺傳算法使用簡(jiǎn)單、魯棒性強(qiáng)、應(yīng)用范圍甚廣,但是它本身也存在著許多不足,尤其是容易過早收斂,使搜索陷入局部最優(yōu)解,因此本文把模擬退火引入到遺傳算法中。本文的模擬退火遺傳算法如下:
(1) 初始化控制參數(shù):
N為群體規(guī)模;pm為變異概率;T0為退火初始溫度;α為溫度冷卻參數(shù);
(2) 隨機(jī)產(chǎn)生初始解群;
(3) 對(duì)現(xiàn)有解群實(shí)施如下操作,直至產(chǎn)生出下一代新的群體:
· 評(píng)價(jià)群體中每個(gè)個(gè)體的適應(yīng)函數(shù)值f(xi),i=1,2,…,N,本文中以空間利用率作為適應(yīng)度函數(shù);
· 采用輪盤賭選擇法對(duì)個(gè)體進(jìn)行選擇;
輪盤賭選擇法的基本思想是:生成一個(gè)隨機(jī)數(shù)γ∈[0,1],并且計(jì)算個(gè)體的相對(duì)適應(yīng)度值pi=fi/∑fi,如果p0+p1+…+pi-1<γ≤p0+p1+…+pi,則第i個(gè)個(gè)體被選擇到下一代。可見,個(gè)體的適應(yīng)度值越大被選擇到下一代的機(jī)會(huì)也越多。
·對(duì)選擇復(fù)制后的個(gè)體實(shí)施交叉操作,隨機(jī)選擇兩個(gè)個(gè)體xi和xj進(jìn)行交叉操作,并且計(jì)算兩個(gè)新個(gè)體x′i和x′j的適應(yīng)函數(shù)值f(x′i)和f(x′j);生成一個(gè)[0,1]之間的隨機(jī)數(shù)random,以min1,exp(-△f/Tk)>random[0,1]的概率接受新的解,即接受新個(gè)體。
·對(duì)交叉后的個(gè)體進(jìn)行變異操作,按第三步中的方法決定是否接收變異后的解;
(4) 若滿足收斂條件,進(jìn)化過程結(jié)束;否則Tk+1=αTK,轉(zhuǎn)(3)。
模擬退火遺傳算法首先利用輪盤賭選擇方法,淘汰了適應(yīng)度較低的個(gè)體。而交叉操作是遺傳算法中的核心,尋優(yōu)過程主要通過它實(shí)現(xiàn),模擬退火遺傳算法吸取了這一思想,對(duì)選擇后的個(gè)體均實(shí)施交叉操作,并且把交叉和變異后的子代與父代競(jìng)爭(zhēng),通過Boltzmann機(jī)制來接收子代,不但有利于優(yōu)良個(gè)體的保留,同時(shí)防止了早熟收斂的問題。隨著進(jìn)化過程的進(jìn)行,溫度逐漸下降,接收劣質(zhì)解的概率也逐漸減小,有效地利用了模擬退火算法的爬山特性,提高了算法的收斂速度。
4 集裝箱裝載實(shí)例與算法分析
在實(shí)際應(yīng)用中,為了求解的快速性和實(shí)用性,人們通常采用一些啟發(fā)式算法" title="啟發(fā)式算法">啟發(fā)式算法[6]來求解裝箱問題。為了評(píng)價(jià)模擬退火遺傳算法的性能,將模擬退火算法和啟發(fā)式算法進(jìn)行比較,分別用來求解裝箱問題。
本文使用DELPHI程序進(jìn)行模擬裝箱,所使用的模擬退火遺傳算法的控制參數(shù)選取如下:群體規(guī)模N=100,變異概率pm=0.01,初始溫度T0=1000,冷卻參數(shù)α=0.9;待裝物品為洗衣機(jī)散件,單位為毫米,其體積以及數(shù)量如表1所示;布局空間采用規(guī)格為11.96×2.35×2.69的集裝箱,單位為米。物品裝箱過程中,充分考慮到物品的擺放方式,以及是否可以置底,分別利用啟發(fā)式算法以及本文的模擬退火遺傳算法進(jìn)行裝箱,得到的結(jié)果如表2、表3所示,裝載效果如圖1、圖2所示。其中X0,Y0,Z0表示物品在集裝箱中的位置。
本例中的待裝物品共有712件,其中需要裝載500臺(tái)主機(jī),7臺(tái)30#,1臺(tái)17#,45臺(tái)11#,6臺(tái)9#,10臺(tái)3#,139臺(tái)2#,4臺(tái)8#。
啟發(fā)式算法使用知識(shí)規(guī)則,搜索速度快,搜索方向相對(duì)明確,但是知識(shí)規(guī)則的使用使得搜索空間的范圍急劇縮小,因此求解結(jié)果通常會(huì)有很大的局限。利用文獻(xiàn)[7]中的啟發(fā)式算法裝載物品,共布入645件物品,空間利用率為88.3%。裝箱結(jié)果如表 2、圖1所示。
?
模擬退火遺傳算法把模擬退火和遺傳算法有效地結(jié)合起來,既加速了算法的收斂速度又避免陷入局部最優(yōu)解。利用模擬退火遺傳算法裝載物品,物品全部布入,空間利用率為92.6%。裝箱結(jié)果如表 3、圖2所示。
從表2和表3的數(shù)據(jù)以及裝箱效果圖可以看出:模擬退火遺傳算法的空間利用率比較高而且布入物品的個(gè)數(shù)和種類較多;啟發(fā)式算法空間利用率比較低,布入的物品也較少。利用模擬退火遺傳算法解決裝箱問題還是行之有效的。
本文針對(duì)集裝箱貨物裝載問題提出了一種模擬退火遺傳算法,將模擬退火和遺傳算法有效地結(jié)合。通過具體試驗(yàn)可以看出,該算法充分發(fā)揮了交叉算子的作用,不僅縮小了可行域的搜索范圍,而且避免搜索陷入局部最優(yōu)解。采用該算法進(jìn)行求解,不僅提高了集裝箱的利用率,而且提高了工人的裝載效率,從而提高了企業(yè)的競(jìng)爭(zhēng)力。
參考文獻(xiàn)
1 Coffman E G, Garey M R, Johnson D S.Approximation algorithms for bin packing: A survey.In:Hochbaum Ded. Approximation Algorithms for NP-Hard problems. Boston: PWS publishing, 1996: 46~93
2 M.R.Garey,D.S.Johnson著.張立昂,沈 泓,畢源章譯.計(jì)算機(jī)和難解性-NP完全性理論導(dǎo)論.北京:科學(xué)出版社, 1990
3 GoldbergDE.Geneticalgorithmsinsearch,optimizationandma-chinelearning.MA:Addison-Wesley,1989
4 KirkpatrickS,GelattCD,VecchiMP.Optimizationbysimulated-annealing.Science,1983;220:671~680
5 周 明,孫樹棟.遺傳算法原理及應(yīng)用[M].北京:國(guó)防出版社,1999
6 Fuh-Hwa, Fliu, C-Jhsiao. A three-dimensional pallet loading method for single-size boxes. Journal of the Opera-tional Re-search Society, 1997; 48:726~735
7 丁香乾,韓運(yùn)實(shí),張曉麗. 多約束條件下的一種啟發(fā)式集裝箱裝箱算法[C].第十三屆全國(guó)神經(jīng)網(wǎng)絡(luò)學(xué)術(shù)年會(huì)文集,2003;453~457