集裝箱裝載問(wèn)題的模擬退火遺傳算法 [日期：2005-12-19] 來(lái)源：電子技術(shù)應(yīng)用 作者：江 娜 丁香乾 劉同義 張紅蘭 [字體：容器中，以獲得某種最佳的效益。從計(jì)算復(fù)雜性理論來(lái)講，裝箱問(wèn)題屬于NP完全問(wèn)題，求解極為困難。

遺傳算法采用了生物進(jìn)化論的思想，通過(guò)自然選擇和適者生存的競(jìng)爭(zhēng)策略來(lái)解優(yōu)化問(wèn)題；模擬退火起源于統(tǒng)計(jì)物理方法，并首先被Kirkpatrick等引入組合優(yōu)化領(lǐng)域。遺傳算法的全局搜索性能較強(qiáng)，便是其容易過(guò)早收斂，而且在進(jìn)化后期搜索效率較低，種群的進(jìn)化緩慢；需模擬退火算法具有較強(qiáng)的局部搜索能力，并且能使搜索過(guò)程避免陷入局部最優(yōu)解，但是把握搜索過(guò)程的能力不強(qiáng)，運(yùn)行效率不高。本文通過(guò)將模擬退火的思想引入遺傳算法，使兩者有效地結(jié)合，緩解了遺傳算法的選擇壓力，增強(qiáng)了遺傳算法的全局收斂性，避免在搜索過(guò)程中陷入局部最優(yōu)。

1 遺傳算法

遺傳算法最早由美國(guó)Michigan大學(xué)的J.Holland教授提出，起源于上世紀(jì)60年代人們自然和人工自適應(yīng)系統(tǒng)的研究，是基于Darwin進(jìn)化論和Mendel的遺傳學(xué)說(shuō)的一種全局優(yōu)化概率搜索算法，它模擬了生物界中的生命進(jìn)化機(jī)制，在人工系統(tǒng)中實(shí)現(xiàn)特定目標(biāo)的優(yōu)化。對(duì)于復(fù)雜的優(yōu)化問(wèn)題，遺傳算法無(wú)需建模和進(jìn)行復(fù)雜的運(yùn)算。與傳統(tǒng)的搜索算法不同，遺傳算法把優(yōu)化問(wèn)題的解的搜索空間轉(zhuǎn)化為遺傳空間，從代表問(wèn)題可能潛在問(wèn)題的解的搜索空間轉(zhuǎn)化為遺傳空間，從代表問(wèn)題可能潛在解集的一個(gè)種群開(kāi)始，其中種群中的每一個(gè)體對(duì)應(yīng)問(wèn)題的一個(gè)解，稱(chēng)為染色體。初代種群產(chǎn)生后，按照適者生存和優(yōu)勝劣汰的原理，逐代演化產(chǎn)生出越來(lái)越好的近似解。在每一代，按預(yù)先根據(jù)目標(biāo)函數(shù)確定的適應(yīng)度函數(shù)計(jì)算各個(gè)體對(duì)問(wèn)題環(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)估；遺傳算法僅使用問(wèn)題的目標(biāo)函數(shù)進(jìn)行工作，不需要其他的先決條件或輔助信息；遺傳算法不是采用確定性規(guī)則進(jìn)行工作，而是采用概率的變化遷規(guī)則來(lái)指導(dǎo)其搜索方法；遺傳算法具有隱形并行性，可以在較大的解空間迅速尋優(yōu)。

標(biāo)準(zhǔn)的遺傳算法求解過(guò)程如下：

（1）初始化遺傳算法的控制參數(shù)，如群體規(guī)模N、變異概率pm、交叉概率pc；

(2)隨機(jī)產(chǎn)生初始解群p(t)={p0p1p2…pn}，個(gè)體的數(shù)目一定，每個(gè)個(gè)體表示為染色體的基因編碼；

（3）計(jì)算群體中每個(gè)個(gè)體的適應(yīng)函數(shù)值；

遺傳算法在搜索過(guò)程中基本不利于外部信息，僅以適應(yīng)度函數(shù)為依據(jù)，利用種群中每個(gè)個(gè)體的適應(yīng)度值進(jìn)行搜索。因此適應(yīng)度函數(shù)的選取至關(guān)重要，將直接影響遺傳算法的收斂速度以及能否找到最優(yōu)解。解的好壞用適宜度函數(shù)值的大小評(píng)估，適應(yīng)度的函數(shù)值越大，解的質(zhì)量越好。

（4）根據(jù)個(gè)體的適應(yīng)度選擇復(fù)制再生個(gè)體，適應(yīng)函數(shù)值大的個(gè)體的復(fù)制概率大；

選擇是指以一定的概率從種群中選擇優(yōu)勝個(gè)體，淘汰質(zhì)個(gè)體的操作。選擇的過(guò)程是一種基于適應(yīng)的優(yōu)勝劣汰的過(guò)程，是用來(lái)確定得組或交叉?zhèn)�體，以及被選個(gè)體將產(chǎn)生多少個(gè)子代個(gè)體。

（5）按照一定的交叉概率和交叉方法，對(duì)現(xiàn)有解群中的個(gè)體體交叉操作,生成新個(gè)體。

交叉是指對(duì)兩個(gè)相互配對(duì)的染色體以某種方式相互交換部分基因，從而形成兩個(gè)新的個(gè)體，交叉是遺傳算法的核心。

（6）按照一定的變異概率和變異方法，對(duì)交叉后的個(gè)體進(jìn)行變異操作；

變異運(yùn)算是指將個(gè)體染色體編碼串中的某些基因座上的基因值用該基因座的其他等位基因替換，從而形成一個(gè)新的個(gè)體。

（7）由交叉和變異產(chǎn)生了一新一代種群，若滿(mǎn)足收斂條件，遺傳進(jìn)化過(guò)程結(jié)束；否則轉(zhuǎn)（3）。

2 模擬退火算法

模擬退火算法是基于Monte Carlo迭代求解法后種啟發(fā)式隨機(jī)搜索算法，它模擬固體物質(zhì)退火過(guò)程的熱平衡問(wèn)題與隨機(jī)搜索尋優(yōu)問(wèn)題的相似性來(lái)達(dá)到尋找全局最優(yōu)或近似全局最優(yōu)的目的。在搜索最優(yōu)解的過(guò)程中，模擬退火法除了可以接受優(yōu)化解外，還有一個(gè)隨機(jī)接受準(zhǔn)則（Metropolis