并行遺傳算法在裝箱問(wèn)題中的應(yīng)用研究.pdf

1、裝箱問(wèn)題是最經(jīng)典的組合優(yōu)化問(wèn)題之一，同時(shí)也是算法分析理論中研究的重點(diǎn)。裝箱問(wèn)題源于現(xiàn)實(shí)生活，有著極為廣泛和深厚的應(yīng)用背景。例如裝箱問(wèn)題在多處理器調(diào)度、資源分配和日常生活中的計(jì)劃、包裝、調(diào)度等各領(lǐng)域有著廣泛的應(yīng)用。而且裝箱問(wèn)題理論的形成也有著深刻的意義，作為一種最早研究的NP難解問(wèn)題，為其它NP難解問(wèn)題的研究提供了理論性研究平臺(tái)和諸多借鑒的典范。該問(wèn)題已經(jīng)有四十多年的研究歷史，在此期間，許多著名的組合優(yōu)化方面的學(xué)者為裝箱問(wèn)題創(chuàng)建了比較完善

2、的理論和豐富的算法，但是關(guān)于裝箱問(wèn)題及其算法的研究仍遠(yuǎn)未結(jié)束。 本文利用并行遺傳算法來(lái)求解一維裝箱問(wèn)題，針對(duì)一維裝箱問(wèn)題，圍繞如何提高并行算法的效率以及求解的精度提出了一些關(guān)鍵性的技術(shù)。主要內(nèi)容如下： 1、本文比較了解決一維裝箱問(wèn)題較好的組遺傳算法，針對(duì)組遺傳算法交叉算子的不足，在叉的過(guò)程中增加了一種“替換”機(jī)制，從而提出了一種改進(jìn)的交叉算子。此交叉算子能夠保證染色體在交叉的過(guò)程中盡量的減少箱子的個(gè)數(shù)，同時(shí)盡可能使能箱子

3、裝滿(mǎn)物品。 2、為了提高種群的多樣性，在進(jìn)化的過(guò)程中跳出局部最優(yōu)解，本文設(shè)計(jì)了新的變異算子，在變異的過(guò)程中主要采取增加一個(gè)箱子，減少一個(gè)箱子，箱子數(shù)不變但箱子所裝物品進(jìn)行恰當(dāng)重組的操作。 3、從“多群體粗粒度”并性遺傳算法模型入手，受“金字塔”模型的啟發(fā)，本文提出了一種并行遺傳算法的“金字塔層次模型”，根據(jù)種群的平均適應(yīng)度將各個(gè)種群分成不同的層次，每一層具有不同交叉和變異概率。層次較高的種群具有較低的交叉和變異概率，遷移

4、時(shí)只是從低層次向高層次遷移。 4、在遷移策略上，為了盡可能降低通信費(fèi)用，本文提出了“雙閾值”的遷移策略，根據(jù)相鄰兩層之間種群的適應(yīng)度方差設(shè)置雙閾值，將遷移分為三種情況：小于最小閩值時(shí)不遷移；介于兩個(gè)閡值之間用下層的優(yōu)秀個(gè)體去替換上層的較差個(gè)體；大于最大的閾值，進(jìn)行層次調(diào)整。 5、在遷移周期上，本文采用的不固定間隔的遷移周期，當(dāng)進(jìn)化緩慢時(shí)才進(jìn)行遷移的申請(qǐng)。 基于上述的研究，最后本文給出了實(shí)現(xiàn)并行遺傳算法求解裝箱問(wèn)題