資源描述：
《一種求解三維集裝箱裝箱問題的混合遺傳算法new》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、2002007,43(26)ComputerEngineeringandApplications計(jì)算機(jī)工程與應(yīng)用一種求解三維集裝箱裝箱問題的混合遺傳算法江寶釧,熊偉清JIANGBao-chuan,XIONGWei-qing寧波大學(xué)信息與科學(xué)工程學(xué)院,浙江寧波315211CollegeofInformationScienceandEngineering,NingboUniversity,Ningbo,Zhejiang315211,ChinaE-mail:jiangbaochuan@nbu.edu.cnJIANGBao-chuan,XIONGWei-qing.Hybridgeneticalgori
2、thmsolvingforthree-dimensionalcontainerloadingproblem.ComputerEngineeringandApplications,2007,43(26):200-202.Abstract:Thispaperpresentsahybridgeneticalgorithmforthecontainerloadingproblem,witchconsiderbasicheuristicinitscoreloadingprocedure.Thisalgorithminheritgeneticalgorithm’sglobalsearchingexcell
3、ence,andenhancedthegeneticalgorithm’slocalsearchingability.Thisalgorithmcancommendablyfigureoutthethree-dimensionalloadingproblemwithmultiaimsandmultilimits.Keywords:containerloadingproblem;hybridgeneticalgorithm;heuristicsearch;three-dimensionalloadingproblem摘要:在遺傳算法的基礎(chǔ)上結(jié)合傳統(tǒng)啟發(fā)式裝箱算法,設(shè)計(jì)了一個(gè)混合遺傳算法,該算法既
4、繼承了遺傳算法的全局搜索好的優(yōu)點(diǎn),也克服了遺傳算法局部搜索能力差的缺點(diǎn),能夠較好地解決集裝箱這類多目標(biāo)多約束的空間三維分布的問題。關(guān)鍵詞:集裝箱裝箱問題;混合遺傳算法;啟發(fā)式搜索;三維空間背包問題文章編號(hào):1002-8331(2007)26-0200-03文獻(xiàn)標(biāo)識(shí)碼:A中圖分類號(hào):TP3911引言2算法的詳細(xì)設(shè)計(jì)三維裝箱問題廣泛存在于商品的包裝、裝載、運(yùn)輸之中,特本文在遺傳算法的基礎(chǔ)上結(jié)合傳統(tǒng)啟發(fā)式裝箱算法,設(shè)計(jì)別是在集裝箱裝載貨物方面起著重要的作用。三維裝箱問題是成一個(gè)混合遺傳算法。該算法既繼承遺傳算法的全局搜索好的一個(gè)具有復(fù)雜約束條件的組合優(yōu)化問題,在理論上屬于NP優(yōu)點(diǎn),也克服了遺傳算法局
5、部搜索能力差的缺點(diǎn),能夠較好地hard問題,在實(shí)際中更有許多約束條件需要考慮,因此復(fù)雜性解決集裝箱這類多目標(biāo)多約束的空間三維分布的問題。其主要和難度大。目前國內(nèi)較好的裝箱軟件幾乎寥寥無幾[1]。思想是:在整個(gè)裝箱過程中,將產(chǎn)生的子空間按照容積從小到集裝箱裝載問題是:將一批待布箱體(長方體)裝入長方體大進(jìn)行排序;對(duì)某一物品,它總是裝到第一個(gè)能裝下它的箱子容器中,目標(biāo)是使容器空間利用率和重量利用率達(dá)到最高;同中;裝完一個(gè)物品后,將根據(jù)這個(gè)物品產(chǎn)生上、左、前3個(gè)子空時(shí)要考慮到的約束有:箱體本身的承重性、易碎性、箱體搬運(yùn)的間,如果子空間容積不小于剩余物品的最小體積,則將子空間難易、一些貨物必須隔離、不
6、允許超過最大承重量、重心與幾何按容積從小到大重新排序,否則作為空隙排除。這樣的裝箱方形心偏差不應(yīng)太大、貨物碼放的穩(wěn)定性等等。由于存在多目標(biāo)、案既符合最佳適應(yīng)近似算法的思想,同時(shí),物品對(duì)空間的分割多約束的空間規(guī)劃問題的計(jì)算復(fù)雜性,利用數(shù)學(xué)規(guī)劃法和圖論方式采用三叉樹分割法,可以保證貨物的邊沒有懸空現(xiàn)象。法不太有效,A啟發(fā)式方法雖然較為有效,但大多只能解一類在上述算法的基礎(chǔ)上,貨物的序號(hào)被排列成一個(gè)序列作為問題,局限性較大[2]。因此,開發(fā)實(shí)用的綜合考慮多種約束、多種遺傳個(gè)體的基因,由遺傳群體對(duì)基因群體進(jìn)行變異、交叉等演目標(biāo)的集裝箱空間規(guī)劃算法有待于進(jìn)一步加以研究。繹,并按一定規(guī)則產(chǎn)生下一代。當(dāng)遺傳
7、的代數(shù)足夠大的時(shí)候,遺遺傳算法作為一種隨機(jī)化搜索算法,具有很強(qiáng)的全局搜索傳群體中的幾個(gè)最優(yōu)遺傳個(gè)體就可以被近似地當(dāng)作指定裝箱能力,比較適合求解集裝箱裝載問題,目前以遺傳算法為基礎(chǔ)問題的最優(yōu)解。并加以改進(jìn),可以成為解決集裝箱問題的可行思路[3]。本文針對(duì)基本遺傳算法可定義為一個(gè)八元組[4]具有多目標(biāo)約束的裝箱問題,在單一集裝箱裝箱算法的基礎(chǔ)SGA=(C,E,P0,M,!,",#,T)上,提出了一種適
