1、-580-1引言隨著市場(chǎng)經(jīng)濟(jì)體制的日臻完善和我國(guó)加入WTO ,我國(guó)的物流業(yè)得到了迅猛發(fā)展。在物流系統(tǒng)中,配送中心或流通中心、倉(cāng)庫(kù)、銷售店等設(shè)施設(shè)置地點(diǎn)的選擇是物流系統(tǒng)優(yōu)化的一個(gè)具有戰(zhàn)略意義的問(wèn)題,其中配送中心的位置顯得更加重要。物流配送中心是貨物從制造商、廠商至零售商之間的中間貯存據(jù)點(diǎn),是集中和分散、促進(jìn)貨物迅速流轉(zhuǎn)的倉(cāng)庫(kù)。不同地區(qū)、不同品種的貨物通過(guò)物流中心的調(diào)節(jié)與保管,按不同需求重新組合,發(fā)往收貨者手中。配送中心地址的合理選擇,不僅可以縮短配送距離,加快配送速度,降低配送成本,提高服務(wù)質(zhì)量,而且可以促進(jìn)生產(chǎn)和消費(fèi)兩種流量的有機(jī)協(xié)調(diào)與配合,使整個(gè)物流系統(tǒng)處于平衡發(fā)展的狀態(tài)。由于配送中心在物流

2、系統(tǒng)中所處的重要地位,大批科研人員對(duì)這一問(wèn)題展開(kāi)了深入細(xì)致的研究,建立了一系列的選址模型與算法,這些模型及算法實(shí)現(xiàn)起來(lái)相當(dāng)復(fù)雜。因此,在解決實(shí)際配送中心選址問(wèn)題時(shí),往往借助于啟發(fā)式算法來(lái)達(dá)到或非常接近最優(yōu)解。在運(yùn)用遺傳算法進(jìn)行選址的研究中,現(xiàn)有的研究成果大都運(yùn)用傳統(tǒng)的遺傳算法,使用PMX 、CX 、OX 等交叉算子,這些算子不僅實(shí)施起來(lái)很困難,而且要求要有多樣性的種群,很容易在最優(yōu)解附近早熟收斂。鑒于這種原因,本文使用一種新的改進(jìn)遺傳算法單親進(jìn)化遺傳算法,提出對(duì)備選地址已定的選址模型,使用單親進(jìn)化遺傳算法,實(shí)現(xiàn)各點(diǎn)間往返路徑最優(yōu)化,使備選的任意兩點(diǎn)彼此到達(dá)對(duì)方的總費(fèi)用最少;然后以優(yōu)化的路徑表示

3、為父體,從各基因所在的結(jié)點(diǎn)為起點(diǎn),截取所有基因片段,求以各基因?yàn)槠瘘c(diǎn)的基因片段值總和,選取最佳基因片段組合,結(jié)合各點(diǎn)固定建設(shè)費(fèi),確定配送中心最佳地址。這一算法對(duì)于改進(jìn)物流系統(tǒng)布局,提高物流系統(tǒng)科學(xué)決策水平具有一定意義。2PEGA 簡(jiǎn)介近年來(lái),TGA (traditional genetic algorithm 即傳統(tǒng)遺傳算法發(fā)展迅速,具有運(yùn)算簡(jiǎn)單、收斂速度快等優(yōu)點(diǎn),但仍存在對(duì)復(fù)雜問(wèn)題搜索效率低,易陷入“早熟收斂”等缺點(diǎn)。本文使用的遺傳算法是一種改進(jìn)的單親遺傳算法,所有的進(jìn)化過(guò)程均在一條染色體上進(jìn)行,它采用“路徑表達(dá)”的序號(hào)編碼方式,利用父體所提供的有效邊的信息,使用保留最小邊的方法進(jìn)行個(gè)體進(jìn)化

4、。收稿日期:2004-06-07。基金項(xiàng)目:國(guó)家自然科學(xué)基金項(xiàng)目(10171095;國(guó)家863計(jì)劃基金項(xiàng)目(2002AA103061。作者簡(jiǎn)介:祝延軍(1973-,男,山東臨清人,碩士,研究方向?yàn)榻扑惴?胡純德(1973-,男,湖北洪湖人,碩士,研究方向?yàn)榻扑惴?高隨祥(1962-,男,陜西延安人,教授,博士,研究方向?yàn)榻M合最優(yōu)化。2005年3月計(jì)算機(jī)工程與設(shè)計(jì)Mar.2005第26卷第3期Vol.26No.3單親進(jìn)化遺傳算法在配送中心選址中的應(yīng)用祝延軍,胡純德,高隨祥(中國(guó)科學(xué)院研究生院,北京100039摘要:為更好地實(shí)現(xiàn)配送中心優(yōu)化選址,在分析物流配送中心的作用及現(xiàn)存的用傳統(tǒng)遺傳算法進(jìn)

5、行選址的基礎(chǔ)上,提出應(yīng)用單親進(jìn)化遺傳算法求解選址模型。首先,利用父體所提供的有效邊的信息,使用保留最小邊的方法對(duì)個(gè)體進(jìn)行進(jìn)化,求得費(fèi)用最低的優(yōu)化路徑;然后以優(yōu)化路徑作為父體,求解從各基因?yàn)槭键c(diǎn)的基因片段值之和,選擇最佳基因片段組合,得到問(wèn)題的解,該算法可以有效、快速地求得配送中心選址問(wèn)題的全局最優(yōu)解。關(guān)鍵詞:單親進(jìn)化遺傳算法;基因片段組合;配送中心;優(yōu)化選址中圖法分類號(hào):TP301文獻(xiàn)標(biāo)識(shí)碼:A 文章編號(hào):1000-7024(200503-0580-03Application of partheno evolution genetic algorithm in location of dist

6、ribution centerZHU Yan-jun,HU Chun-de,GAO Sui-xiang(Graduate School of Chinese Academy of Sciences,Beijing 100039,China Abstract :To better optimize location of physical distribution center.On the basis of analyzing the function and existed location method of physical distribution centre by TGA (tra

7、ditional genetic algorithm ,it is put forward to use PEGA (partheno evolution genetic algorithm to solve location model.At first,PEGA utilizes effective limbic information from father-body,uses the way of preserving the least limbic to evolution and gains optimal path which transport costs is the lo

8、west.Secondly,using the gained optimal path as father -body,the sum of genetic paragraphs is worked out which comes from the same gene,the best combination of genetic paragraph is selected and reachs the solution of the problem is given.It can effectively and fast get the best overall solution.Key w

9、ords :PEGA;combination of genetic paragraph;distribution centre;optimal locationComputer Engineering and Design-581-我們引用文獻(xiàn)5中的兩個(gè)概念,對(duì)PEGA 算法基本思想闡述如下。概念1在PEGA 中,按一定方式移動(dòng)一條染色體上某些位置的基因過(guò)程,被移動(dòng)的基因的位置是隨機(jī)產(chǎn)生的,稱為基因換位操作。概念2基因分組定界操作:按一定的閾值,進(jìn)行路徑拆鏈,形成一個(gè)個(gè)子串,各子串之間的路徑長(zhǎng)度一定大于閾值。傳統(tǒng)遺傳算法中的交叉算子和變異算子,主要考慮結(jié)點(diǎn)(區(qū)域的相對(duì)位置與次序,而忽略了連接結(jié)

10、點(diǎn)的邊。根據(jù)文獻(xiàn)11,結(jié)點(diǎn)所處的位置并不重要,而它與其它結(jié)點(diǎn)相連所組成的邊可以為我們構(gòu)造更好的解指明方向?？梢?jiàn),連接結(jié)點(diǎn)之間的邊非常重要。PEGA 算法盡可能地利用父體所提供的有效邊的信息,使用保留最小邊信息的方法進(jìn)行個(gè)體優(yōu)化。3配送中心選址模型及選址實(shí)現(xiàn)3.1問(wèn)題描述給定某一地區(qū)備選物流配送中心及其所屬倉(cāng)庫(kù)的地址集合,要求選出一定數(shù)目的地址建立配送中心,其它剩余地址設(shè)置配送中心所屬倉(cāng)庫(kù),從而建立一個(gè)完備優(yōu)化的配送區(qū)域,實(shí)現(xiàn)配送中心到倉(cāng)庫(kù)間的物品配送,使得在選出地點(diǎn)建立的配送中心與各倉(cāng)庫(kù)形成的配送系統(tǒng)總配送費(fèi)最低。其中假設(shè)系統(tǒng)滿足如下一些條件:所有設(shè)定的地址區(qū)域都具備優(yōu)越的交通、運(yùn)輸、信息等條

11、件;所設(shè)各區(qū)域的配送資源情況一樣;物流中心容量可以滿足各倉(cāng)庫(kù)的需求;倉(cāng)庫(kù)需求的物品一次運(yùn)輸完成,所在點(diǎn)對(duì)間運(yùn)輸速度一樣,均為常數(shù);系統(tǒng)總費(fèi)用只考慮固定設(shè)施建設(shè)費(fèi)用及管理費(fèi)用、運(yùn)輸途中的運(yùn)輸費(fèi)用。假定有n 個(gè)備選地址,已確定從中選出m 個(gè)配送中心S 1,S 2,S m 現(xiàn)欲求m 個(gè)最佳地址作為配送中心,以使總配送費(fèi)用最小,則有規(guī)劃模型如下4:min+ 1=+2,+ 1=1,2, ,+1, 容量+1+1=1,2,= 設(shè)置費(fèi)+1¿ªÊ¼YN設(shè)置進(jìn)化代數(shù),并定為終止條件(如N=5000N>5000按以下步驟獲得運(yùn)輸費(fèi)用最少的優(yōu)化路徑Step1機(jī)產(chǎn)生初始種,

12、并機(jī)產(chǎn)生未匹配的父體;Step2在父體中機(jī)產(chǎn)生子串,進(jìn)行基因們操作;Step3基因分組定界;Step4基因換位,定最優(yōu)后代輸出最佳染色體,即獲得運(yùn)輸費(fèi)用最低的優(yōu)化路徑按以下步驟的定配送中心的最佳地址Step1最優(yōu)后代為父體,求各基因?yàn)辄c(diǎn)基因片段值之和;Step2選擇最佳基因片段組合,定配送中心最佳地址輸出最佳基因所在的結(jié)點(diǎn),獲得問(wèn)題的解表111個(gè)區(qū)域之間的運(yùn)輸費(fèi)用表示12345678910111020192982033821222922302321252737125140402119372210717332730802121379049261001211徑表示”的序號(hào)編碼方式如下:步驟2在父體

13、中隨機(jī)產(chǎn)生一個(gè)子串,進(jìn)行基因換位操作。如:P:125|6983|471011生成的子代為C:6983125471011步驟3基因分組定界。首先根據(jù)表1,判斷父體染色體中各個(gè)基因(區(qū)域所構(gòu)成的邊的大小,選出最大邊長(zhǎng)(MAX、最小邊長(zhǎng)(MIN并算出平均邊長(zhǎng)(AVE,按公式ave=(MAX+4AVE+MIN/6對(duì)這3類邊長(zhǎng)進(jìn)行加權(quán)平均,所得值作為閾值。然后,保留最小邊,并將大于閾值的邊進(jìn)行破壞,即基因分組定界操作。在此例中,最大邊長(zhǎng)是37,最小邊長(zhǎng)是10,平均邊長(zhǎng)是23,所以得閾值ave=23 (這里做取整計(jì)算,以下同。所以破壞6和9、8和3、5和4、4和7、7和10之間的邊。P1:6|98|312

14、5|4|7|1011步驟4基因換位,確定最優(yōu)后代。鑒于傳統(tǒng)遺傳變異算子常常收斂于最優(yōu)點(diǎn)附近,而達(dá)不到最優(yōu)點(diǎn),導(dǎo)致種群早熟、進(jìn)化陷于停滯的情況,很自然的想法就是在最優(yōu)點(diǎn)附近采樣,從中找到新的點(diǎn),其適值比當(dāng)前最優(yōu)點(diǎn)往往要好。所以,在這一步驟中,對(duì)標(biāo)記后的染色體,我們采用鄰域技術(shù),將各個(gè)子串作為新的基因(或基因片段進(jìn)行換位,產(chǎn)生不同的基因組合,評(píng)估所有的新個(gè)體,選出最好的作為后代。步驟5返回步驟3,循環(huán)直到滿足結(jié)束條件(即達(dá)到進(jìn)化代數(shù)或得到最優(yōu)解為止。步驟6得到最優(yōu)后代。所得路徑上總的運(yùn)輸費(fèi)用為157。步驟7指定所得最優(yōu)后代為父體,求解以各基因?yàn)槠瘘c(diǎn)截取的基因片段值總和。求解基因片段總和的方法,如表

15、2所示。步驟8選取最佳基因片段組合,結(jié)合各點(diǎn)固定建設(shè)費(fèi),確定配送中心最佳地址。經(jīng)步驟7,選擇基因片段總值與固定建設(shè)費(fèi)之和(見(jiàn)表3最小的基因所在的地址,作為配送中心最佳地址。如在本例中,要從11個(gè)地址中選擇1個(gè)配送中心,我們就從父體P2中選擇基因7;如果要選擇3個(gè)配送中心,我們就從中選擇基因7、2、4;其余各基因所在的結(jié)點(diǎn)可設(shè)置為配送中心所屬倉(cāng)庫(kù)的地址。4.2實(shí)驗(yàn)分析為了說(shuō)明該算法的可靠性和有效性,并能夠直觀反映出它的遺傳進(jìn)化特征,我們對(duì)文獻(xiàn)4運(yùn)用的算例進(jìn)行了測(cè)試。算例如下:有一物流網(wǎng)絡(luò),從12個(gè)結(jié)點(diǎn)中選出3個(gè)作為配送中心的地址,各點(diǎn)(從1到12設(shè)置配送中心的費(fèi)用各為11、16、14、14、15

16、、13、18、12、11、14、16、11個(gè)單位;各結(jié)點(diǎn)的距離如表4所示。用本文的算法,與用文獻(xiàn)4運(yùn)行得到同樣的結(jié)果相比,本文運(yùn)行速度比文獻(xiàn)4快數(shù)十倍;再仍用其算例,將上述數(shù)據(jù)隨機(jī)產(chǎn)生20組10到20之間的數(shù)作為結(jié)點(diǎn)之間的運(yùn)輸費(fèi)用,每組用本文算法進(jìn)化20代,有97%達(dá)到最優(yōu)解;同樣的運(yùn)算操作,文獻(xiàn)4的算法僅有50%達(dá)到最優(yōu)。可以看出,PEGA是一種更有效的求解物流配送中心選址問(wèn)題的全局最優(yōu)解的更好算法。5結(jié)論物流配送中心在物流網(wǎng)絡(luò)中起著非常重要的作用,合理選擇物流中心地址,可以節(jié)約費(fèi)用,促進(jìn)系統(tǒng)優(yōu)化,提高服務(wù)質(zhì)量,能使綜合效益不斷提升。本文應(yīng)用單親進(jìn)化遺傳算法,結(jié)合確定性配送模型構(gòu)造了求解配送

17、中心優(yōu)化選址的新方法,這一方法所有的進(jìn)化過(guò)程均在一條染色體(單親父體上進(jìn)行,表2以基因3為起點(diǎn)的基因片段統(tǒng)計(jì)基因片段基因片段值3119391239530395448395425639542764395427881395427861003954278611110 395427861110122 3954278611101138基因片段值總和780表3統(tǒng)計(jì)綜合費(fèi)用247611001576378012001980449211001592556417002264658611001686747610001476851011001610964812001848表4配送點(diǎn)間距2056545771091050

18、7810101312960649106670295498010627904613100491105120(下轉(zhuǎn)第662頁(yè)-582-tHandlerNextNext先用SQL語(yǔ)句將實(shí)驗(yàn)標(biāo)準(zhǔn)的實(shí)驗(yàn)?zāi)康膹臄?shù)據(jù)庫(kù)中搜出來(lái),這樣我們就可以得到實(shí)驗(yàn)?zāi)康牡臄?shù)目,NumRows就是這個(gè)數(shù)目;同時(shí)可以算出表格的行數(shù)(因?yàn)楸砀竦牧袛?shù)是兩列。然后用兩個(gè)FOR循環(huán),分別添加TableRow和TableCell,這樣我們就可以把表格動(dòng)態(tài)畫(huà)好。然后我們又用兩個(gè)FOR循環(huán)對(duì)畫(huà)好的每個(gè)單元格動(dòng)態(tài)添加CheckBox控件,每個(gè)CheckBox控件的Text屬性就是每個(gè)實(shí)驗(yàn)?zāi)康捻?xiàng)。根據(jù)需要,每按壓一下CheckBox控件就要在表

19、格的右端顯示本實(shí)驗(yàn)?zāi)康膶?duì)應(yīng)的實(shí)驗(yàn)項(xiàng)目,也就是說(shuō)要對(duì)每個(gè)Check-Box控件編寫(xiě)Click事件。因?yàn)镃heckBox控件是動(dòng)態(tài)添加的,因此對(duì)應(yīng)的Click事件不能自動(dòng)生成。我們可以用AddHandler objCB.CheckedChanged、AddressOf EventHandler語(yǔ)句動(dòng)態(tài)添加Click事件,當(dāng)點(diǎn)擊CheckBox控件時(shí),系統(tǒng)會(huì)自動(dòng)運(yùn)行這一段代碼。Click事件要完成的功能由方法EventHandler來(lái)完成,我們只需編寫(xiě)方法EventHandler的代碼。5結(jié)束語(yǔ)本文介紹的冰箱測(cè)試管理系統(tǒng)現(xiàn)正用于海爾企業(yè)內(nèi)部網(wǎng),極大地方便了研發(fā)部門、質(zhì)量管理部門、實(shí)驗(yàn)部門之間的溝通和

20、協(xié)作,滿足了國(guó)際化大企業(yè)高速發(fā)展的需要。該系統(tǒng)借鑒了以往管理系統(tǒng)與測(cè)試系統(tǒng)的優(yōu)點(diǎn),在性能和功能上都有很大改進(jìn),為同類系統(tǒng)提供了良好的范例。該系統(tǒng)不僅可用于電冰箱、家電產(chǎn)品的測(cè)試管理,而且可用于大型工廠、釀酒廠、食品加工廠的溫度測(cè)試管理,有著很廣闊的應(yīng)用前景。參考文獻(xiàn):1甘勇,宋寅卯.全數(shù)字網(wǎng)絡(luò)化冰箱制冷性能分布式計(jì)算機(jī)測(cè)試系統(tǒng)的設(shè)計(jì)J.鄭州輕工業(yè)學(xué)院學(xué)報(bào),2002,17(2:79.2劉勇,郭忠文.一種C/S與B/S相結(jié)合的電冰箱抽樣測(cè)試系統(tǒng)J.計(jì)算機(jī)工程與設(shè)計(jì),2003,24(9:14-15.3郭忠文,賈忠偉,唐功友.基于Intranet的冰箱抽樣測(cè)試系統(tǒng)J.計(jì)算機(jī)工程,2002,28(9:1

21、79-181.擺脫了傳統(tǒng)遺傳算法運(yùn)用交叉算子的麻煩,利用父體所提供的有效邊的信息,使用保留最小邊的方法進(jìn)行個(gè)體優(yōu)化。與傳統(tǒng)的遺傳算法相比,彌補(bǔ)了不足,簡(jiǎn)化了算法。實(shí)驗(yàn)證明了該算法應(yīng)用于物流配送中心優(yōu)化選址問(wèn)題上的有效性。參考文獻(xiàn):1金若南,張文杰.現(xiàn)代綜合物流管理M.北京:中國(guó)鐵道出版社,1994.167.2許哲榮,胡黃德.國(guó)際物流研討會(huì)論文集:A集C.多產(chǎn)品配送中心場(chǎng)址規(guī)劃與選擇,1999.3Bagley J D.The behavior of adaptive system which employ ge-netic and correlation algorithmsJ.Dissertarion Abstracts Inter-national,1967,(28:2.4姜大立,杜文.基于遺傳算法的物流配送中心選址模型J.實(shí)用物流技術(shù),1997,(5:4.5馬欣,朱雙東,楊斐.旅行商問(wèn)題的一種改進(jìn)遺傳算法J.計(jì)算機(jī)仿真,2003,20(4:366潘正君,康立山,陳毓屏.演化計(jì)算M.北京:清華大學(xué)出版社,1998.7王戰(zhàn)權(quán),楊東援,汪超.配送中心選址的遺傳算法研究J.物流技術(shù),2001,(3:11-14.8賀國(guó)先,劉凱.優(yōu)化物流中心配送方案的遺傳算法J.系統(tǒng)工程理論與實(shí)踐