資源描述：
《利用遺傳算法求解裝箱問題》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、第24卷 第4期延安大學(xué)學(xué)報(bào)(自然科學(xué)版)Vol.24No.42005年12月JournalofYananUniversity(NaturalScienceEdition)Dec.2005a利用遺傳算法求解裝箱問題12李大可,楊花娥(1.西安建筑科技大學(xué)理學(xué)院,陜西西安710054;2.西安文理學(xué)院數(shù)學(xué)系,陜西西安710063)摘 要:遺傳算法通過(guò)編碼技術(shù),運(yùn)用繁殖、雜交和突變等遺傳算子,對(duì)染色體組成的初始種群,進(jìn)行適應(yīng)度分析,構(gòu)成優(yōu)勝劣汰、適者生存的自然環(huán)境,產(chǎn)生出新的更加優(yōu)良的種群.經(jīng)過(guò)若干代的進(jìn)化,最終求得適合問題的最優(yōu)解.關(guān)鍵詞:遺傳算法;裝箱
2、問題;遺傳算子中圖分類號(hào):TP301.6文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):10042602X(2005)04200322021 遺傳算法子總?cè)莘e條件下,如何使裝入裝子物體的總價(jià)值最大.這里wi、pi和W都是正整數(shù),i=1,2,?,n.遺傳算法是一種模仿生物遺傳與進(jìn)化過(guò)程而得問題的一個(gè)可行解可以用如下二進(jìn)制字符串表出的一種隨機(jī)優(yōu)化方法,它是“仿生學(xué)”在數(shù)學(xué)領(lǐng)域示:X=(x1,x2,?,xn),xi為如下021變量:xi=1,中的直接引用.它利用簡(jiǎn)單的編碼技術(shù)和進(jìn)化繁殖表示物品i被裝箱;xi=0表示物品i未被裝箱,i=機(jī)制來(lái)表現(xiàn)復(fù)雜的現(xiàn)象,進(jìn)而提供了一種求解復(fù)雜1,
3、2,?,n.從而向量X就是一個(gè)裝箱方案.系統(tǒng)優(yōu)化問題的通用框架.由于它不依賴問題的具裝箱問題可以用如下數(shù)學(xué)模型表述:n體領(lǐng)域,不受搜索空間的限制性假設(shè)的約束,不要求max∑pi×xi一定具有目標(biāo)函數(shù)的解析表達(dá)式,因此,遺傳算法應(yīng)i=1n用的領(lǐng)域十分廣泛.遺傳算法的主要過(guò)程如下.s.t.∑wixi≤W,xi∈{0,1},i=1,2,?,n.i=11)對(duì)研究的變量或?qū)ο筮M(jìn)行編碼形成染色體,并隨機(jī)地建立一個(gè)初始群體.2 應(yīng)用舉例2)計(jì)算群體中諸染色體的適應(yīng)度.3)執(zhí)行遺傳算子操作.包括:繁殖,將適應(yīng)度高下面我們通過(guò)一個(gè)經(jīng)濟(jì)活動(dòng)中常見的實(shí)際問的染色體進(jìn)行繁殖,
4、添入到群體中,刪除適應(yīng)度低的題,介紹如何利用遺傳算法解決裝箱問題,這是遺傳染色體;雜交,隨機(jī)選出染色體對(duì),基基因進(jìn)行片段算法最簡(jiǎn)單、最基本的應(yīng)用模式.交叉換位,產(chǎn)生新的染色體對(duì);突變,隨機(jī)改變某染例 現(xiàn)有100萬(wàn)元資金打算在5個(gè)不同的地方色體的某個(gè)基因,得到新染色體.修建某種工廠,由于條件不同,所需投資分別為:w14)根據(jù)某種條件判斷計(jì)算過(guò)程是否可以結(jié)束,=56,w2=20,w3=54,w4=42,w5=15(單位:萬(wàn)如果不滿足結(jié)束條件,則返回到步驟2,直到滿足結(jié)元),工廠建成后,每年能得到的利潤(rùn)分別為:p1=束條件為止.7,p2=5,p3=9,p4=
5、6,p5=3(單元:萬(wàn)元).問如裝箱問題也稱背包問題,它可以表述為一個(gè)單何確定投資地點(diǎn),使總投資不超過(guò)100萬(wàn)元,且使建約束的純整數(shù)規(guī)劃問題.設(shè)有一個(gè)箱子的總?cè)莘e為成后每年所獲總利潤(rùn)最多?W,另有n個(gè)不同的物品,其體積分別w1,w2,?,此問題可以看成是一種裝箱問題.其中裝箱數(shù)wn,其價(jià)值分別為p1,p2,?,pn,問題是在不超過(guò)箱學(xué)模型中的參數(shù)分別為:xi表示在第i個(gè)地方是否a 收稿日期:20050710作者簡(jiǎn)介:李大可(1958),男,陜西西安市人,西安建筑科技大學(xué)副教授.?1994-2007ChinaAcademicJournalElectron
6、icPublishingHouse.Allrightsreserved.http://www.cnki.net第4期 李大可,楊花娥:利用遺傳算法求解裝箱問題 33修建工廠(i=1,2,?,5),W=100,n=5,w1=56,代X.(1)w2=20,w3=54,w4=42,w5=15,p1=7,p2=5,利用解碼法對(duì)第一代染色體中的不可行解x1(2)p3=9,p4=6,p5=3,目標(biāo)函數(shù):maxf(X)=7x1進(jìn)行改造,使其轉(zhuǎn)化成可行解x1=[1;0;0;0;0],(1)(1)+5x2+9x3+6x4
7、+3x5,約束條件:g(X)=56x1f(x1=7,而g(x1)=56.(其中[1;0;1;0;0]還是+20x2+54x3+42x4+42x4+15x5≤100.不可行解)編碼是應(yīng)用遺傳算法首先要解決的問題,在遺需要說(shuō)明的是對(duì)種群實(shí)施各種遺傳運(yùn)算后,都傳算法的實(shí)際應(yīng)用中,根據(jù)所研究對(duì)象的不同性質(zhì),要檢驗(yàn)解X的可行性,凡是不可行的,都可按上述將問題的可行解設(shè)計(jì)成染色體.遺傳基因也可以取解碼法轉(zhuǎn)化成可行解.不同的表示形式,在下面的討論中,遺傳基因用0?1在對(duì)染色體進(jìn)行繁殖運(yùn)算時(shí),首先計(jì)算各個(gè)染(m)(m)(m)碼表示,這是一種最常用的編碼形式.遺傳算法操
8、作色體的生存概率.對(duì)于給定群體x1,x2,?,xn,(m)的對(duì)象是用遺傳基因表示的染色體,每個(gè)
