資源描述:
《三維裝箱問題的遺傳算法研究.pdf》由會員上傳分享,免費在線閱讀,更多相關內容在行業(yè)資料-天天文庫。
1、2010年6月電腦學習第3期三維裝箱問題的遺傳算法研究***周昕紀穎摘要:本文以集裝箱自動裝載系統(tǒng)為例,根據貨物放置方向、裝載容積等約束條件,給出了有效的解碼算法,提出了一種改進遺傳算法,并通過實例數據進行了實驗結果分析。關鍵詞:三維裝箱遺傳算法優(yōu)化中圖分類號:TP301.6文獻標識碼:A文章編號:1002-2422(2010)03-0117-03ResearchonGeneticAlgorithmforThreeDimensionalContainer-PackingProblemZhouXinJiYingAbstract:Basedonautomati
2、ccontainer-packingsystem,thepapertakesintoaccountthedirectionofthegoods,loadingcapa-cityandotherconstraints,anditcontributesaneffectivedecodingalgorithmwithimprovedgeneticalgorithm,thereforeanalyzestheresultbasedonexperimentaldata.Keyword:Three-dimensionalContainer-PackingGeneticA
3、lgorithmOptimization1裝箱問題的數學模型(3)貨物裝載容積的約束:貨物裝載的總容積不得大集裝箱三維裝載優(yōu)化問題可描述為:在一定約束條件于集裝箱的最大裝載容積。限制下,將一批貨物按照適當的裝載方法裝入同一集裝箱(4)穩(wěn)定性的約束:貨物裝載應該使重心位于允許的中,使得集裝箱的容積利用率或裝載質量利用率最大,從范圍內而確保整體穩(wěn)定,以利于運輸安全。而增強對集裝箱的合理有效使用。為方便建模,約定如下:(5)承載能力的約束:在裝載中,貨物所能承受的最大貨物簡化為長方體,高度相等且均小于集裝箱尺寸;貨物壓力受限制。以水平方向放置于集裝箱中任位置而不
4、受配置位置限制。(6)貨物裝載順序:不同的貨物在裝載中應按不同的1.1目標函數及約束條件優(yōu)先順序裝載。1.1.1目標函數描述1.2貨物裝載遵循的方向次序原則裝箱的目標可描述為如下的最大化函數[6]:定義集裝箱箱門所在端為后端,集裝箱在坐標系中的nn位置關系如圖1所示。則在集裝箱中裝載貨物遵循以下原Maxz=λΣ(liwihi)/V+(1-λ)Σ(giδi)/G(1)則:i=1i=1其中l(wèi)i、wi、hi、gi分別表示貨物i(i=1,2,芽,n)(1)依次沿左側至右側方向(即y軸方向)、前端至后的長、寬、高和質量;V,G分別表示集裝箱的最大裝載容積端方向(即x
5、軸方向)放置每一層。和最大裝載質量。λ是0-1變量,當追求目標為容積利用(2)沿下端至上端方向(即z軸方向)逐層放置。率最大時λ=1,當追求目標為裝載質量利用率最大時λ=z上端前端0;δi是0-1變量,若貨物i裝載則δi=1,否則δi=0。H右端本文旨在確定一種集裝箱裝載方案,以便將所有貨物o裝入集裝箱中;如果不能完全裝入,則找到一個待裝子集,y左端或者使集裝箱的空間利用率最高。則問題的目標函數可描述為:下端Wnx后端Maxz=Σ(liwihi)/V(2)i=1圖1集裝箱在坐標系中的位置1.1.2約束條件2基于遺傳算法的問題求解裝箱約束條件如下:遺傳算法是
6、一種基于達爾文進化論思想的全局最優(yōu)化(1)貨物放置方向的約束:在裝載中,貨物只能水平放算法。在問題求解過程中,模仿自然界生物進化過程,以被置,不能旋轉。索空間中的每一個點表示每一個生物個體,從任一代初始(2)貨物裝載質量的約束:貨物裝載的總質量不得多群體出發(fā),通過隨機選擇、交叉、變異等過程,使群體進化到于集裝箱的最大裝載質量。搜索空間中越來越理想的區(qū)域。收稿日期:2010-03-31*周昕哈爾濱理工大學計算機科學與技術學院講師(黑龍江,哈爾濱150080)。**紀穎哈爾濱理工大學計算機科學與技術學院副教授(黑龍江,哈爾濱150080)?!?17·遺傳算法的
7、優(yōu)越性主要表現(xiàn)在搜索過程中不易陷入局協(xié)調。部最優(yōu),即使在所定義的適應度函數不連續(xù)的情況下,也能在交叉過程中,由[1,3n]間按均勻分布隨機產生兩個以極大的概率找到最優(yōu)解[7]。整數a,a(a<a)作為父代兩個個體S,S的交叉位,1212122.1編碼預處理若a1>n,則交叉僅在sn+1至s3n段間進行,直接交換交叉定義貨物水平放置方向為貨高與箱高相互平行的放置位間對應位置的基因而其余基因保持不變;若a2≤n,則交狀態(tài),則集裝箱最多裝載層數M計算:叉僅在s1至sn段間進行,采取序交叉方法;若a1≤n且a2>nM=H/hi(3),則交叉在兩段間分別進行,s1至
8、sn段采取序交叉方法對在進行個體編碼之前,做如下的編碼預處理:a1