并行遺傳算法在裝箱問題中的應用研究.pdf

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

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

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

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