目前，物流業(yè)正處在快速發(fā)展的時期，集裝箱運輸將會有大幅度的增長。集裝箱裝載作為物流配送過程中的一個關鍵性環(huán)節(jié)，可提高配送業(yè)務的自動化水平、提高貨物裝載的優(yōu)化程度、提高配送業(yè)務的工作效率和規(guī)范業(yè)務流程等。
　　從二十世紀70年代初開始，集裝箱裝載問題就引起了廣泛的研究和探討^[1]。裝箱問題就是將不同尺寸的物品擺放入有一定容量的容器中，以獲得某種最佳的效益。從計算復雜性理論來講，裝箱問題屬于NP完全問題^[2]，求解極為困難。
　　遺傳算法采用了生物進化論的思想，通過自然選擇和適者生存的競爭策略來求解優(yōu)化問題^[3]；模擬退火起源于統(tǒng)計物理學方法，并首先被Kirkpatrick等引入組合優(yōu)化領域^[4]。遺傳算法的全局搜索性能較強，但是其容易過早收斂，而且在進化后期搜索效率較低，種群的進化緩慢；而模擬退火算法" title="模擬退火算法">模擬退火算法具有較強的局部搜索能力，并且能使搜索過程避免陷入局部最優(yōu)解，但是把握搜索過程的能力不強，運行效率不高。本文通過將模擬退火的思想引入遺傳算法，使兩者有效地結合，緩解了遺傳算法的選擇壓力，增強了遺傳算法的全局收斂性，避免在搜索過程中陷入局部最優(yōu)。
1 遺傳算法
　　遺傳算法最早由美國Michigan大學的J. Holland教授提出，起源于上世紀60年代人們對自然和人工自適應系統(tǒng)的研究^[5]，是基于Darwin進化論和Mendel的遺傳學說的一種全局優(yōu)化概率搜索算法，它模擬了生物界中的生命進化機制，在人工系統(tǒng)中實現(xiàn)特定目標的優(yōu)化。對于復雜的優(yōu)化問題，遺傳算法無需建模和進行復雜的運算。與傳統(tǒng)的搜索算法不同，遺傳算法把優(yōu)化問題的解的搜索空間轉(zhuǎn)化為遺傳空間，從代表問題可能潛在解集的一個種群開始，其中種群中的每一個體對應問題的一個解，稱為染色體。初代種群產(chǎn)生后，按照適者生存和優(yōu)勝劣汰的原理，逐代演化產(chǎn)生出越來越好的近似解。在每一代，按預先根據(jù)目標函數(shù)確定的適應度函數(shù)計算各個體對問題環(huán)境的適應值，再根據(jù)個體的適應值對個體對應的染色體進行選擇，使適應性好的染色體比適應性差的染色體有更多的繁殖機會；然后進行交叉、變異等遺傳操作產(chǎn)生新一代群體。如此循環(huán)，逐步向優(yōu)化的種群進化。
　　遺傳算法的主要特點是：遺傳算法的處理對象不是參數(shù)本身，而是對參數(shù)集進行編碼的個體；遺傳算法采用同時處理群體中多個個體的方法，即同時對搜索空間中的多個解進行評估；遺傳算法僅使用問題的目標函數(shù)進行工作，不需要其他的先決條件或輔助信息；遺傳算法不是采用確定性規(guī)則進行工作，而是采用概率的變遷規(guī)則來指導其搜索方向；遺傳算法具有隱形并行性，可以在較大的解空間迅速尋優(yōu)。
　　標準的遺傳算法求解過程如下：
　　(1) 初始化遺傳算法的控制參數(shù)，如群體規(guī)模N、變異概率p_m、交叉概率p_c；
　　(2) 隨機產(chǎn)生初始解群p(t)={p₀ p₁ p₂…p_n}，個體的數(shù)目一定，每個個體表示為染色體的基因編碼；
　　(3) 計算群體中每個個體的適應函數(shù)" title="適應函數(shù)">適應函數(shù)值；
　　遺傳算法在搜索過程中基本不利用外部信息，僅以適應度函數(shù)為依據(jù)，利用種群中每個個體的適應度值進行搜索。因此適應度函數(shù)的選取至關重要，將直接影響遺傳算法的收斂速度以及能否找到最優(yōu)解。解的好壞用適宜度函數(shù)值的大小評價，適應度函數(shù)值越大，解的質(zhì)量越好。
　　(4) 根據(jù)個體的適應度選擇復制再生個體，適應函數(shù)值大的個體的復制概率大；
　　選擇是指以一定的概率從種群中選擇優(yōu)勝個體，淘汰劣質(zhì)個體的操作。選擇的過程是一種基于適應度的優(yōu)勝劣汰的過程，是用來確定重組或交叉?zhèn)€體，以及被選個體將產(chǎn)生多少個子代個體。
　　(5) 按照一定的交叉概率和交叉方法,對現(xiàn)有解群中的個體實施交叉操作,生成新個體；
　　交叉是指對兩個相互配對的染色體以某種方式相互交換部分基因，從而形成兩個新的個體，交叉是遺傳算法的核心。
　　(6) 按照一定的變異概率和變異方法,對交叉后的個體進行變異操作；
　　變異運算是指將個體染色體編碼串中的某些基因座上的基因值用該基因座的其他等位基因替換，從而形成一個新的個體。
　　(7) 由交叉和變異產(chǎn)生了新一代種群，若滿足收斂條件，遺傳進化過程結束；否則轉(zhuǎn)(3)。
2 模擬退火算法
　　模擬退火算法是基于Monte Carlo迭代求解法的一種啟發(fā)式隨機搜索算法，它模擬固體物質(zhì)退火過程的熱平衡問題與隨機搜索尋優(yōu)問題的相似性來達到尋找全局最優(yōu)或近似全局最優(yōu)的目的。在搜索最優(yōu)解的過程中，模擬退火法除了可以接受優(yōu)化解外，還用一個隨機接受準則(Metropolis準則)有限度地接受惡化解，并且接受惡化解的概率慢慢趨向于0，這使得算法有可能從局部極值區(qū)域中跳出，即可能找到全局最優(yōu)解，并保證了算法的收斂性。
　　模擬退火算法的求解過程如下：
　　(1) 隨機產(chǎn)生初始解x₀；
　　(2) 初始化退火溫度T₀；
　　(3) 在溫度TK下執(zhí)行如下操作:
　　·產(chǎn)生新的可行解x′,x′為x的鄰解；
　　·計算評價函數(shù)f(x′)和f(x)的差值△f=f(x′)-f(x)；
　　·以min{1,exp(-△f/T_k)}＞random[0,1]的概率接收新解，其中random[0,1]是[0,1]之間的隨機數(shù)。若達到溫度Tk的平衡狀態(tài)轉(zhuǎn)(4)，否則轉(zhuǎn)(3)；
　　(4) 按一定方式降低溫度,可定義下降函數(shù)為T_k+1=αT_K,k+1→k，其中α∈[0,1]；
　　(5) 若滿足收斂判據(jù),退火過程結束；否則轉(zhuǎn)(3)。
　　通過以上分析可知,在模擬退火過程中,其退火溫度控制著求解過程向最小值的優(yōu)化方向進行,同時它又以概率exp(-△f/T_k)接收劣質(zhì)解,因此算法可以跳出局部極值點。只要初始溫度足夠高,退火過程足夠慢,算法能夠收斂到全局最優(yōu)解。
3 模擬退火遺傳算法
　　雖然遺傳算法使用簡單、魯棒性強、應用范圍甚廣，但是它本身也存在著許多不足，尤其是容易過早收斂，使搜索陷入局部最優(yōu)解，因此本文把模擬退火引入到遺傳算法中。本文的模擬退火遺傳算法如下：
　　(1) 初始化控制參數(shù)：
　　N為群體規(guī)模；p_m為變異概率；T₀為退火初始溫度；α為溫度冷卻參數(shù)；
　　(2) 隨機產(chǎn)生初始解群；
　　(3) 對現(xiàn)有解群實施如下操作,直至產(chǎn)生出下一代新的群體：
　　· 評價群體中每個個體的適應函數(shù)值f(x_i)，i=1,2,…,N,本文中以空間利用率作為適應度函數(shù)；
　　· 采用輪盤賭選擇法對個體進行選擇；
　　輪盤賭選擇法的基本思想是：生成一個隨機數(shù)γ∈[0,1]，并且計算個體的相對適應度值pi=fi/∑fi，如果p₀+p₁+…+pi-1＜γ≤p₀+p₁+…+pi，則第i個個體被選擇到下一代?？梢姡瑐€體的適應度值越大被選擇到下一代的機會也越多。
　　·對選擇復制后的個體實施交叉操作，隨機選擇兩個個體x_i和x_j進行交叉操作，并且計算兩個新個體x′_i和x′_j的適應函數(shù)值f(x′_i)和f(x′_j)；生成一個[0,1]之間的隨機數(shù)random,以min1,exp(-△f/T_k)＞random[0,1]的概率接受新的解，即接受新個體。
　　·對交叉后的個體進行變異操作,按第三步中的方法決定是否接收變異后的解；
　　(4) 若滿足收斂條件,進化過程結束；否則T_k+1=αTK,轉(zhuǎn)(3)。
　　模擬退火遺傳算法首先利用輪盤賭選擇方法，淘汰了適應度較低的個體。而交叉操作是遺傳算法中的核心，尋優(yōu)過程主要通過它實現(xiàn)，模擬退火遺傳算法吸取了這一思想,對選擇后的個體均實施交叉操作,并且把交叉和變異后的子代與父代競爭，通過Boltzmann機制來接收子代，不但有利于優(yōu)良個體的保留，同時防止了早熟收斂的問題。隨著進化過程的進行，溫度逐漸下降，接收劣質(zhì)解的概率也逐漸減小，有效地利用了模擬退火算法的爬山特性，提高了算法的收斂速度。
4 集裝箱裝載實例與算法分析
　　在實際應用中，為了求解的快速性和實用性，人們通常采用一些啟發(fā)式算法" title="啟發(fā)式算法">啟發(fā)式算法^[6]來求解裝箱問題。為了評價模擬退火遺傳算法的性能，將模擬退火算法和啟發(fā)式算法進行比較，分別用來求解裝箱問題。
　　本文使用DELPHI程序進行模擬裝箱，所使用的模擬退火遺傳算法的控制參數(shù)選取如下：群體規(guī)模N=100，變異概率p_m=0.01，初始溫度T₀=1000，冷卻參數(shù)α=0.9；待裝物品為洗衣機散件，單位為毫米，其體積以及數(shù)量如表1所示；布局空間采用規(guī)格為11.96×2.35×2.69的集裝箱，單位為米。物品裝箱過程中，充分考慮到物品的擺放方式，以及是否可以置底，分別利用啟發(fā)式算法以及本文的模擬退火遺傳算法進行裝箱，得到的結果如表2、表3所示，裝載效果如圖1、圖2所示。其中X₀，Y₀,Z₀表示物品在集裝箱中的位置。
　　本例中的待裝物品共有712件，其中需要裝載500臺主機，7臺30#，1臺17#，45臺11#，6臺9#，10臺3#，139臺2#，4臺8#。
　　啟發(fā)式算法使用知識規(guī)則，搜索速度快，搜索方向相對明確，但是知識規(guī)則的使用使得搜索空間的范圍急劇縮小，因此求解結果通常會有很大的局限。利用文獻^[7]中的啟發(fā)式算法裝載物品，共布入645件物品，空間利用率為88.3%。裝箱結果如表 2、圖1所示。

?

　　模擬退火遺傳算法把模擬退火和遺傳算法有效地結合起來，既加速了算法的收斂速度又避免陷入局部最優(yōu)解。利用模擬退火遺傳算法裝載物品，物品全部布入，空間利用率為92.6%。裝箱結果如表 3、圖2所示。