（應(yīng)用數(shù)學(xué)專業(yè)論文）搬家公司的選址問(wèn)題.pdf

北京郵電大學(xué)碩士研究生畢業(yè)論文 搬家公司的選址問(wèn)題 摘要 選址問(wèn)題研究的是如何選定一個(gè)或多個(gè)設(shè)施的地理位置使得所 考慮的目標(biāo)達(dá)到最優(yōu)的問(wèn)題。搬家公司試圖選擇若干個(gè)居住區(qū)開設(shè) 公司的店面，店面的選擇需要考慮的因素很多，除了該市的不同區(qū) 劃間的相對(duì)地理位置以及與之相關(guān)的交通條件外，還有各居住區(qū)的 人口數(shù)以及不同居住區(qū)間的人口流動(dòng)情況。 本文主要研究了搬家公司選址問(wèn)題的模型建立和求解，結(jié)合搬 家公司具體問(wèn)題，逐一分析搬家公司行車時(shí)所產(chǎn)生的運(yùn)輸成本和開 設(shè)店面的成本費(fèi)用等。以開設(shè)店面的費(fèi)用和行車費(fèi)用總和最小為目 標(biāo)，根據(jù)搬家公司各個(gè)店面之間的聯(lián)系情況和車輛調(diào)度方法的不同， 提出了三種不同的數(shù)學(xué)模型。并利用遺傳算法對(duì)三個(gè)模型進(jìn)行求解； 其次把簡(jiǎn)化的拋物線法作為局部搜索算子，融入實(shí)數(shù)編碼遺傳算法， 構(gòu)成適用于求解全局優(yōu)化問(wèn)題的混合遺傳算法，對(duì)模型進(jìn)行求解。 最后通過(guò)算例應(yīng)用和敏感度分析，以驗(yàn)證本文所構(gòu)建的模型的合理 性及可行性。 關(guān)鍵詞：選址問(wèn)題遺傳算法混合遺傳算法拋物線法 北京郵電大學(xué)碩上研究生畢業(yè)論文 t h el o c a t i o np r o b l e mo f m o n gco m p a n y a b s t r a c t t h es t u d yo fl o c a t i o np r o b l e mi sh o wt os e l e c to n eo rm o r ef a c i l i t i e sb y c o n s i d e r i n gt h eg e o g r a p h i cl o c a t i o nm a k e st h eg o a lo fr e a c h i n go p t i m a l m o v i n g c o m p a n i e s a lea t t e m p t i n gt os e l e c tan u m b e ro fr e s i d e n t i a la l e a st oo p e nt h e c o m p a n y ss t o r e s ，t h ec h o i c eo fs t o r e sn e e d st oc o n s i d e ran u m b e ro ff a c t o r s ，a p a r t f r o mt h ec i t y sd i f f e r e n td i v i s i o n sa sw e l la st h er e l a t i v eg e o g r a p h i c a ll o c a t i o n a s s o c i a t e d 、) i ，i t ht h et r a f f i cc o n d i t i o n s ，t h e r ea r ev a r i o u sr e s i d e n t i a la r e a so f p o p u l a t i o na sw e l la st h er a n g eo ft h ep o p u l a t i o nl i v i n gi nd i f f e r e n tf l o w s t h i sp a p e rs t u d i e st h el o c a t i o np r o b l e mo ft h em o v i n g c o m p a n y , a b o u tg i v i n g i t sm a t h e m a t i cm o d e l sa n dh o wt os o l v et h em o d e l s i nt h i sp a p e r , w ec o n s i d e rt h e s p e c i f i ci s s u e so ft h em o v i n gc o m p a n i e sa n dd i s c u s st h ei n f l u e n c ef a c t o r s ，s u c ha s t h ec o s to ft r a n s p o r t a t i o na n dt h ec o s to fo p e n i n gs t o r e s t h e nw ee s t a b l i s ht h r e e c o s t so p t i m i z a t i o nm o d e l sf o rt h el o c a t i o np r o b l e mo ft h em o v i n gc o m p a n y , a c c o r d i n gt ot h ed i f f e r e n tv e h i c l es c h e a u l i n gw a y s ，c o m b i n a t i o nt h el i n k a g e s b e t w e e nt h ev a r i o u ss t o r e s t h e nu s i n gt h ei m p r o v e dg e n e t i ca l g o r i t h mt os o l v et h e t h r e em o d e l s ，w eo b t a i na no p t i m a la n dp r a c t i c a ll o c a t i o n s e c o n d l y , t h es i m p l i f i e d p a r a b o l am e t h o di si n t e g r a t e di n t ot h eg e n e t i ca l g o r i t h r na sa l o c a ls e a r c ho p e r a t o r t h e nan o v e lh y b r i dg e n e t i ca l g o r i t h mf o rg l o b a lo p t i m i z a t i o np r o b l e m si sp r o p o s e d t os o l v et h em o d e lt w o 。f i n a l l y , t h r o u g ht h es e n s i t i v i t ya n a l y s i sa n dt h ef e a s i b i l i t yo f t h ec o n c r e t em o d e lh a sp r o v e nt h er a t i o n a l i t ya n dt h ef e a s i b i l i t yo ft h em o d e l k e yw o r d s ：l o c a t i o np r o b l e m ；g e n e t i ca l g o r i t h m ；h y b r i dg e n e t i ca l g o r i t h m ； p a r a b o l am e t h o d i i 獨(dú)創(chuàng)性( 或創(chuàng)新性) 聲明 本人聲明所呈交的論文是本人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作及 取得的研究成果。盡我所知，除了文中特別加以標(biāo)注和致謝中所羅 列的內(nèi)容以外，論文中不包含其他人已經(jīng)發(fā)表或撰寫過(guò)的研究成果， 也不包含為獲得北京郵電大學(xué)或其他教育機(jī)構(gòu)的學(xué)位或證書而使用 過(guò)的材料。與我一同工作的同志對(duì)本研究所做的任何貢獻(xiàn)均已在論 文中作了明確的說(shuō)明并表示了謝意。 申請(qǐng)學(xué)位論文與資料若有不實(shí)之處，本人承擔(dān)一切相關(guān)責(zé)任口 本人簽名：蕊莛遮 日期： 絲芻! 堡圣丑垡璺 關(guān)于論文使用授權(quán)的說(shuō)明 學(xué)位論文作者完全了解北京郵電大學(xué)有關(guān)保留和使用學(xué)位論文 的規(guī)定，即：研究生在校攻讀學(xué)位期間論文工作的知識(shí)產(chǎn)權(quán)單位 屬北京郵電大學(xué)。學(xué)校有權(quán)保留并向國(guó)家有關(guān)部門或機(jī)構(gòu)送交論 文的復(fù)印件和磁盤，允許學(xué)位論文被查閱和借閱；學(xué)校可以公布 學(xué)位論文的全部或部分內(nèi)容，可以允許采用影印、縮印或其它復(fù) 制手段保存、匯編學(xué)位論文。( 保密的學(xué)位論文在解密后遵守此 規(guī)定) 保密論文注釋：本學(xué)位論文屬于保密在一年解密后適用本授權(quán) 書。非保密論文注釋：本學(xué)位論文不屬于保密范圍，適用本授權(quán)書。 本人簽名：氆疊查日期：2 塑生墨旦竺旦 導(dǎo)師簽名：礅盆塑。f 毛1日期：1 壁2 聾三團(tuán)! 蘭盈! 北京郵電人學(xué)碩士研究生畢業(yè)論文 1 1 研究的背景和意義 第一章緒論弟一早珀下匕 選址問(wèn)題是一個(gè)復(fù)雜的綜合性決策過(guò)程，既需要定性考慮，又需要定量分 析。目前已有很多學(xué)者對(duì)物流配送中心選址問(wèn)題進(jìn)行研究，總結(jié)他們的研究方 法大致可以分為定性法和定量法兩大類。其中，定性的方法主要是層次分析法 和模糊綜合評(píng)價(jià)相結(jié)合的方法，對(duì)各方案進(jìn)行指標(biāo)評(píng)價(jià)，來(lái)確定最終地址；定 量的方法主要包括重心法，運(yùn)輸規(guī)劃法，c l u s t e r 法，c f l p 法，0 1 整數(shù)規(guī)劃 法，遺傳算法等，松弛算法和啟發(fā)式算法以及兩者的結(jié)合應(yīng)用。 總體來(lái)說(shuō)，這些物流配送中心選址方法大致可分為以下三類： ( 1 ) 應(yīng)用連續(xù)型模型選址： 連續(xù)模型選址方法認(rèn)為物流配送中心的地點(diǎn)可以在平面上取任意點(diǎn)，代表 性的方法是重心法和交叉中值法。該方法不限于對(duì)特定的備選點(diǎn)的選擇，靈活 性較大，特別是在單個(gè)物流配送中心選址的應(yīng)用中，已經(jīng)得到多數(shù)人的接受和 認(rèn)可。但是，由于這個(gè)地址可能位于河流、建筑物或其他無(wú)法實(shí)現(xiàn)的地點(diǎn)，實(shí) 際上找到的最優(yōu)地點(diǎn)可能很難實(shí)現(xiàn)。 ( 2 ) 應(yīng)用離散型模型選址 離散模型選址方法認(rèn)為物流配送中心的備選地點(diǎn)是有限的幾個(gè)場(chǎng)所，最合 適的地址只能按照預(yù)定的目標(biāo)從有限個(gè)可行點(diǎn)中選取。代表性的方法有：整數(shù) 或混合整數(shù)規(guī)劃問(wèn)題的分制定界法、鮑姆爾一沃爾夫( b o u m o l w o l f e ) 法、 庫(kù)恩一漢姆布利爾( h u e h n - h a m b u r e e r ) 、反盯氏法、逐次逼近模型法等等。如 果基礎(chǔ)數(shù)據(jù)完備，該類方法得出的解是較符合實(shí)際情況的。但是這種方法所需 要的基礎(chǔ)資料相當(dāng)多，而且這類方法所建立的模型多數(shù)已經(jīng)被證明為n p 問(wèn)題， 無(wú)法用線性模型的方法來(lái)處理，算法相當(dāng)復(fù)雜計(jì)算量較大。 ( 3 ) 應(yīng)用德爾菲( d e l p h i ) 專家咨詢法選址 d e l p h i 方法選址的中心思想是將專家憑經(jīng)驗(yàn)專業(yè)知識(shí)做出的判斷以數(shù)值的 形式表示出來(lái)，從而經(jīng)過(guò)綜合分析后對(duì)選址進(jìn)行決策。由于前兩類的選址研究 很難將選址中的所有影響因素考慮周全，如：地理，地形，環(huán)境，交通，城市 用地等等，或者即使想把這些因素考慮全面，也很難量化形成模型中的約束條 件。因此，建立起一套物流配送中心的選址評(píng)價(jià)指標(biāo)體系，應(yīng)用層次分析法、 灰色關(guān)聯(lián)理論、變權(quán)綜合及模糊評(píng)價(jià)等數(shù)學(xué)方法進(jìn)行綜合評(píng)價(jià)，進(jìn)而確定物流 配送中心的最優(yōu)位置就顯得十分有效。但是，這類方法專家的主觀判斷占有主 北京郵電大學(xué)碩士研究生畢業(yè)論文 導(dǎo)地位，決策結(jié)果往往受到專家的知識(shí)結(jié)構(gòu)，經(jīng)驗(yàn)以及他們所處的地位、時(shí)代 和社會(huì)環(huán)境等諸多因素的限制和影響。所以，對(duì)于有限的備選地點(diǎn)，該類方法 盡管比較有效，則必須具備足夠的基礎(chǔ)資料，輔助以定量分析，否則會(huì)缺乏足 夠的說(shuō)服力。 國(guó)內(nèi)外物流配送中心選址問(wèn)題的研究已有幾十年的歷史，對(duì)各種類型物流 配送中心的選址問(wèn)題在理論和實(shí)踐方面都取得了令人矚目的成就，形成了許多 可行的模型和方法。 但是對(duì)于具體的搬家公司選址問(wèn)題卻沒(méi)有相應(yīng)的資料和文獻(xiàn)，為了更好地 為居民服務(wù)，也為了實(shí)現(xiàn)搬家公司節(jié)省費(fèi)用，實(shí)現(xiàn)利益最大化，店面的選址就 成為一個(gè)值得深入研究的問(wèn)題。對(duì)于搬家公司來(lái)說(shuō)，利潤(rùn)的最大化是其追求的 目標(biāo)，為實(shí)現(xiàn)這一目標(biāo)，搬家公司最關(guān)心的問(wèn)題是在何處建店面，建多大的店 面才能實(shí)現(xiàn)利潤(rùn)的最大化，也即是實(shí)現(xiàn)搬家公司成本最小化，因此需要結(jié)合搬 家公司的具體問(wèn)題。 搬家公司的選址模型所考慮的因素與一般的選址問(wèn)題不同，配送中心或者 工廠倉(cāng)庫(kù)的選址模型，只需要考慮建店的費(fèi)用和配送中心到達(dá)顧客地址的單程 距離，實(shí)現(xiàn)其運(yùn)輸費(fèi)用和店面費(fèi)用的最小化；但是，搬家公司的選址問(wèn)題，根 據(jù)其實(shí)際運(yùn)營(yíng)過(guò)程及其所提供的服務(wù)類型，需要考慮搬家公司從搬遷任務(wù)開始， 到任務(wù)的完成，回到店面的整個(gè)路程實(shí)現(xiàn)，這也是其它選址模型里面所沒(méi)有探 討的問(wèn)題，結(jié)合搬家公司具體問(wèn)題和實(shí)現(xiàn)過(guò)程，綜合考慮不同區(qū)劃間的相對(duì)地 理位置以及與之相關(guān)的交通條件外，還有各居住區(qū)的人口數(shù)以及不同居住區(qū)間 的人口流動(dòng)情況，根據(jù)搬家公司車輛不同的調(diào)度方法建立相應(yīng)的選址模型，應(yīng) 用最優(yōu)化方法對(duì)模型求解，給出搬家公司最佳的店面選擇方案，這也是本文的 意義所在。 隨著人們生活水平的提高，搬遷日趨頻繁，搬家公司的業(yè)務(wù)也有相應(yīng)的增 加，搬家公司往往在一定地區(qū)范圍內(nèi)開設(shè)多個(gè)分店。為了更好地為居民服務(wù)， 也為了節(jié)省費(fèi)用，店面的選址就成為一個(gè)值得研究的問(wèn)題。 1 2 本文主要工作 本文主要研究搬家公司的選址問(wèn)題及其算法實(shí)現(xiàn)，在第一章探討了選址問(wèn) 題的研究情況和背景，闡述了研究搬家公司選址問(wèn)題的實(shí)際意義。 在第二章對(duì)幾種經(jīng)典的選址模型及算法進(jìn)行了概述，在對(duì)這些比較經(jīng)典的 選址模型的分析研究基礎(chǔ)上，結(jié)合搬家公司具體問(wèn)題和實(shí)現(xiàn)過(guò)程，綜合考慮不 同區(qū)劃間的相對(duì)地理位置以及與之相關(guān)的交通條件，還有各居住區(qū)的人口數(shù)以 及不同居住區(qū)間的人口流動(dòng)情況，根據(jù)搬家公司車輛不同的調(diào)度方法，店面數(shù) 2 北京郵電人學(xué)碩士研究生畢業(yè)論文 目的不同以及各個(gè)店面之間的聯(lián)系情況，提出了三種不同的數(shù)學(xué)模型。 在第三章中完成了模型的算法實(shí)現(xiàn)，首先介紹了遺傳算法，并結(jié)合實(shí)例用 遺傳算法對(duì)模型進(jìn)行求解；其次，把簡(jiǎn)化的拋物線法作為局部搜索算子，融入 實(shí)數(shù)編碼遺傳算法，構(gòu)成適用于求解全局優(yōu)化問(wèn)題的混合遺傳算法，結(jié)合實(shí)例 對(duì)第二章所建立的模型二進(jìn)行求解；最后通過(guò)算例應(yīng)用和敏感度分析，以驗(yàn)證 本文所構(gòu)建的模型的合理性及可行性。 3 北京郵電大學(xué)碩士研究生畢業(yè)論文 第二章搬家公司選址問(wèn)題和模型 2 1 幾種經(jīng)典的選址模型 選址問(wèn)題多種多樣，按決策變量的特征，將其分為兩類：一類是連續(xù)選址 問(wèn)題，決策變量可以在某一平面連續(xù)取值；一類是離散選址問(wèn)題，決策變量是 在有限的點(diǎn)中組取值。 1 連續(xù)選址問(wèn)題 平面上的連續(xù)選址模型主要有兩點(diǎn)特征：一是決策變量是連續(xù)的，即可以將 工廠建在平面上的任何一點(diǎn)；二是采用適合的度量方法度量距離。比較常用的 有厶距離( 也稱直角距離) ，三：距離( 也稱歐氏距離) 和厶距離。 最早的連續(xù)選址問(wèn)題是單工廠靜態(tài)選址的韋伯( w e b e r ) 問(wèn)題，將加權(quán)距離作 為唯一的選址決策因素。問(wèn)題可以這樣描述：選擇一個(gè)工廠的坐標(biāo) ( x , y ) r r ，使得給定的需求點(diǎn)0 i ，釓) 到該設(shè)施的加權(quán)距離以k y ) 的和最 小?？梢杂孟旅娴臄?shù)學(xué)模型表示： ( 嘲卿心以o ，y ) ( 1 ) ”i e j l ： 這里畋o ，y ) = ( x - - a i ) 2 + ( y - b k ) 2 ， 將韋伯問(wèn)題推廣：選擇p 個(gè)工廠，1 ， o ，1 ) ( 3 - 1 ) ( 3 2 ) c 擴(kuò)= m i n d 硅 + m i n d 玎) ix i = 1 ，z ，= 1 ；k ，= 1 ，m ( 3 3 ) 其中：旯為常數(shù) 以表示是否在居住區(qū)k 開設(shè)店面 c 。表示在k 點(diǎn)開設(shè)店面的費(fèi)用 目標(biāo)函數(shù)( 3 ) 是要求開設(shè)店面的費(fèi)用，從搬遷起點(diǎn)到搬遷終點(diǎn)的行車費(fèi)用 和空載車費(fèi)在內(nèi)的總費(fèi)用最?。? 3 1 ) 表示開設(shè)的店面數(shù)目的約束條件限制； 北京郵電大學(xué)碩十研究生畢業(yè)論文 ( 3 2 ) 以為o ，1 變量；只考慮開設(shè)了店面的居民區(qū)，即黽= 1 的點(diǎn)k ；( 3 3 ) 店面選擇的使得店面k 到搬家起點(diǎn)f 的距離最小，搬家終點(diǎn)j f 到搬家店面r2 _ 間 的距離最小。 1 2 北京郵電大學(xué)碩上研究生畢業(yè)論文 第三章模型的算法實(shí)現(xiàn) 工廠選址問(wèn)題已經(jīng)形成了多種求解方法，大致可分為定性和定量?jī)深悾憾ㄐ?的方法主要是結(jié)合層次分析法和模糊綜合法對(duì)各方案進(jìn)行指標(biāo)評(píng)價(jià)，找出最優(yōu) 選址；定量的常用方法包括松弛算法和啟發(fā)式算法以及兩者的結(jié)合。 線性松弛算法和拉格朗日松弛算法的基本原理是：將造成問(wèn)題難的約束吸 收到目標(biāo)函數(shù)中，并使得目標(biāo)函數(shù)依舊保持線性，由此使得問(wèn)題易于求解。一 些組合優(yōu)化問(wèn)題在現(xiàn)有的約束條件下很難求得最優(yōu)解，但在原問(wèn)題減少某些約 束后，求解問(wèn)題的難度就大大減少，達(dá)到在多項(xiàng)式時(shí)間內(nèi)求得減少約束后問(wèn)題 的最優(yōu)解。由于拉各朗日松弛算法的實(shí)現(xiàn)比較簡(jiǎn)單且有較好的性質(zhì)，因此它不 僅可以用來(lái)評(píng)價(jià)算法的效果，同時(shí)也可以用在其它算法中，提高算法的效率。 拉各朗日算法主要包括次梯度算法和拉各朗日松弛啟發(fā)式算法。它們兩個(gè)的主 要應(yīng)用是給出混合整數(shù)規(guī)劃問(wèn)題的下界和構(gòu)造基于拉各朗日松弛的啟發(fā)式算 法。 在介紹啟發(fā)式算法之前我們先介紹狀態(tài)空間搜索。狀態(tài)空間搜索就是將問(wèn) 題求解過(guò)程表現(xiàn)為從初始狀態(tài)到目標(biāo)狀態(tài)尋找路徑的過(guò)程。由于求解問(wèn)題的過(guò) 程中分枝有很多，主要是求解過(guò)程中求解條件的不確定性、不完備性造成的， 這使得求解的路徑很多，這些路徑構(gòu)成了一個(gè)圖，這個(gè)圖就是狀態(tài)空間。問(wèn)題 的求解就是在圖中找到一條從開始到目標(biāo)的路，尋找的過(guò)程叫做搜索。常用的 狀態(tài)空間搜索有深探法和廣探法口射，深探法是按照一定的順序查找完一個(gè)分枝， 再查找另一分枝，直到找到目標(biāo)為止。廣探法是從初始狀態(tài)按某種順序一層一 層往下找，找到目標(biāo)為止。這兩種搜索方式的缺陷在于都是在一個(gè)給定的狀態(tài) 空間窮舉。這在狀態(tài)空間不大的情況下是很合適的算法，但是在空間很大又不 可預(yù)測(cè)的情況下就不可取了。這就要用到啟發(fā)式搜索。 啟發(fā)式搜索就是指在狀態(tài)空間中對(duì)每一個(gè)要搜索的位置按照某種方式進(jìn)行 評(píng)估，得到最優(yōu)的位置，再?gòu)倪@個(gè)位置進(jìn)行搜索直到達(dá)到目標(biāo)。這樣可以省略 大量的無(wú)謂的搜索路徑，提高了效率。不同的位置評(píng)估方式，得到不同的算法。 常用的啟發(fā)式算法包括禁忌搜索、遺傳算法、進(jìn)化算法、模擬退火算法、蟻群 算法、人工神經(jīng)網(wǎng)絡(luò)等等。 3 1 遺傳算法 遺傳算法( g e n e t i ca l g o r i t h m s ) 是模擬生物在自然界中的遺傳和進(jìn)化過(guò)程 1 3 北京郵電大學(xué)碩上研究生畢業(yè)論文 而形成的一種自適應(yīng)全局優(yōu)化搜索算法洶1 。它最早由美國(guó)密執(zhí)安大學(xué)的h o l l a n d 教授提出，起源于6 0 年代對(duì)自然和人工自適應(yīng)系統(tǒng)的研究。遺傳算法產(chǎn)生的開 始階段并沒(méi)有引起人們的關(guān)注，一方面是因?yàn)樗旧磉€不成熟；另一方面，當(dāng) 時(shí)的計(jì)算機(jī)容量小，計(jì)算速度慢，也使得需要較大計(jì)算量的遺傳算法難以實(shí)際 應(yīng)用。7 0 年代d ej o n g 基于遺傳的思想在計(jì)算機(jī)上進(jìn)行了大量的純數(shù)值函數(shù)優(yōu) 化計(jì)算試驗(yàn)。在一系列研究工作的基礎(chǔ)上，8 0 年代由g o l d b e r g 進(jìn)行歸納總結(jié)， 形成了遺傳算法的基本框架，遺傳算法也迎來(lái)了興盛發(fā)展時(shí)期。這包括“早熟” 現(xiàn)象的研究和對(duì)“收斂 的證明啪1 ，同時(shí)針對(duì)遺傳算法的不足提出了改進(jìn)方 法，取得了一定的成績(jī)。 3 1 1 基本遺傳算法概述 生物在自然界中的生存繁衍，顯示出了其對(duì)自然環(huán)境的優(yōu)異自適應(yīng)能力。 受其啟發(fā)，人們致力于對(duì)生物各種生存特性的機(jī)理研究和行為模擬，為人工自 適應(yīng)系統(tǒng)的設(shè)計(jì)和開發(fā)提供了廣闊的前景。遺傳算法就是這種生物行為的計(jì)算 機(jī)模擬鐘令人矚目的重要成果?；趯?duì)生物遺傳和進(jìn)化過(guò)程的計(jì)算機(jī)模擬，遺 傳算法使得各種人工系統(tǒng)具有優(yōu)良的自適應(yīng)能力和優(yōu)化能力。遺傳算法所借鑒 的生物學(xué)基礎(chǔ)就是生物的遺傳和進(jìn)化。 生物的遺傳物質(zhì)的主要載體是染色體( c h r o m o s o m e ) ，脫氧核糖核酸( d n a ) 是 其中最主要的遺傳物質(zhì)，而基因( g e n e ) 又是控制生物性狀的遺傳物質(zhì)的功能單 位和結(jié)構(gòu)單位。復(fù)數(shù)個(gè)基因組成染色體，染色體中基因的位置稱為基因座 ( l o c u s ) ，同一個(gè)基因座可能有的全部基因稱為等位基因( a l l e l e ) 。基因和基因 座決定了染色體的特征，也就決定了生物個(gè)體的性狀。此外，染色體有兩種相 應(yīng)的表示模式，即基因型( g e n o t y p e ) 和表現(xiàn)型( p h e n o t y p e ) 。所謂表現(xiàn)型是指生 物個(gè)體表現(xiàn)出來(lái)的性狀，而基因型指與表現(xiàn)型密切相關(guān)的基因組成。同一種基 因型的生物個(gè)體在不同的環(huán)境下可以有不同的表現(xiàn)型，因此表現(xiàn)型是基因型與 環(huán)境條件相互作用的結(jié)果。在遺傳算法中，染色體對(duì)應(yīng)的是數(shù)據(jù)或數(shù)組，在標(biāo) 準(zhǔn)的遺傳算法中，這通常是由一維的串結(jié)構(gòu)數(shù)據(jù)來(lái)表現(xiàn)的。串上各個(gè)位置對(duì)應(yīng) 上述的基因座，而各位置上所取的值對(duì)應(yīng)上述的等位基因。遺傳算法處理的是 染色體，或者叫基因型個(gè)體( i n d i v i d u a l ) 。一定數(shù)量的個(gè)體組成了群體 ( p o p u l a t i o n ) 。群體中個(gè)體的數(shù)目成為群體的大小( p o p u l a t i o ns i z e ) ，也叫群 體規(guī)模。而各個(gè)體對(duì)環(huán)境的適應(yīng)程度叫做適應(yīng)度( f i t n e s s ) 啪1 。 此外，執(zhí)行遺傳算法時(shí)包含兩個(gè)必需的數(shù)據(jù)轉(zhuǎn)換操作，一個(gè)是表現(xiàn)型到基 因型的轉(zhuǎn)換，另一個(gè)是基因型到表現(xiàn)型的轉(zhuǎn)換。前者是把搜索空間中的參數(shù)或 解轉(zhuǎn)換成遺傳空間中的染色體或個(gè)體，此過(guò)程又叫做編碼( c o d i n g ) 操作；后者 1 4 北京郵電大學(xué)碩l ：研究生畢業(yè)論文 是前者的一個(gè)相反操作，叫做解碼( d e c o d i n g ) 操作。 基于對(duì)自然界中生物遺傳與進(jìn)化機(jī)理的模仿，針對(duì)不同的問(wèn)題，很多學(xué)者 設(shè)計(jì)了許多不同的編碼方法來(lái)表示問(wèn)題的可行解，并開發(fā)出了許多不同的遺傳 算子來(lái)模仿不同環(huán)境下的生物遺傳特性。這樣，由不同的編碼方法和不同的遺 傳算子就構(gòu)成了各種不同的遺傳算法。但這些遺傳算法都有共同的特點(diǎn)，即通 過(guò)對(duì)生物遺傳和進(jìn)化過(guò)程中選擇、交叉和變異機(jī)理的模仿，來(lái)完成對(duì)問(wèn)題最優(yōu) 解的自適應(yīng)搜索過(guò)程。基于這個(gè)共同特點(diǎn)，g o l d b e r g 總結(jié)出了一種統(tǒng)一的最基 本的遺傳算法一一基本遺傳算法( s i m p l eg e n e t i ca l g o r i t h m s ，簡(jiǎn)稱s g a ) 1 。 基本遺傳算法只使用選擇算子、交叉算子和變異算子這三種基本遺傳算子，其 遺傳進(jìn)化操作過(guò)程簡(jiǎn)單，容易理解，是其它一些遺傳算法的雛形和基礎(chǔ)，它不 僅給各種遺傳算法提供了一個(gè)基本框架，同時(shí)也具有一定的應(yīng)用價(jià)值。 盡管遺傳算法本身在理論和應(yīng)用方法上仍有許多待進(jìn)一步研究的問(wèn)題，由 于它具有簡(jiǎn)單、通用、魯棒性強(qiáng)，適用于并行分布處理等特點(diǎn)，遺傳算法在下 面領(lǐng)域中已展現(xiàn)了其特色和魅力：函數(shù)優(yōu)化、組合優(yōu)化問(wèn)題、生產(chǎn)調(diào)度問(wèn)題、 自適應(yīng)控制、結(jié)構(gòu)性優(yōu)化、圖像處理、軍事應(yīng)用、規(guī)劃設(shè)計(jì)、遺傳編程、機(jī)器 學(xué)習(xí)和人工生命等。 3 1 1 1 基本遺傳算法實(shí)現(xiàn) 基本遺傳算法( 也稱為標(biāo)準(zhǔn)遺傳算法或簡(jiǎn)單遺傳算法，s i m p l eg e n e t i c a l g o r i t h m s ，簡(jiǎn)稱s g a ) 是一種群體型操作，該操作以群體中的所有個(gè)體為對(duì) 象，只使用基本遺傳算子( g e n e t i co p e r a t o r ) ：選擇算子( s e l e c t i o no p e r a t o r ) 、 交叉算子( c r o s s o v e ro p e r a t o r ) 和變異算子( m u t a t i o no p e r a t o r ) ，其遺傳進(jìn) 化操作過(guò)程簡(jiǎn)單，容易理解。選擇、交叉和變異是遺傳算法的3 個(gè)主要操作算 子，它們構(gòu)成了所謂的遺傳操作，使遺傳算法具有了其他傳統(tǒng)算法沒(méi)有的特點(diǎn)。 基本遺傳算法可表示為： s g a = ( c ，e ，r ，m ，f ，甲，d ( 3 一卜1 ) 式中：c 個(gè)體的編碼方法； e 個(gè)體適應(yīng)度評(píng)價(jià)函數(shù)； 只初始種群； m 種群大?。?選擇算子； r 交叉算子； 甲變異算子； r 遺傳運(yùn)行終止條件。 圖3 1 所示為基本遺傳算法的流程圖： 1 5 北京郵電大學(xué)碩上研究生畢業(yè)論文 圖3 - 1 遺傳算法的基本流程圖 3 1 1 2 基本遺傳算法的步驟 1 染色體的編碼( c h r o m o s o m ec o d i n g ) 與解碼( d e c o d e ) 遺傳算法進(jìn)化過(guò)程是建立在編碼機(jī)制基礎(chǔ)上的，編碼對(duì)于算法的性能如搜 索能力和種群多樣性等影響很大。它的工作對(duì)象是可行解的個(gè)體編碼，通過(guò)對(duì) 編碼的選擇，交叉，變異操作來(lái)達(dá)到優(yōu)化目的，這也是遺傳算法的特點(diǎn)之一。 遺傳算法通過(guò)這種對(duì)個(gè)體編碼的操作，不斷搜索出適應(yīng)度較高的個(gè)體，并在群 體中逐步增加其數(shù)量，最終尋求出問(wèn)題的最優(yōu)解或近似最優(yōu)解。在遺傳算法中 如何描述問(wèn)題的可行解，即把一個(gè)問(wèn)題的可行解從其解空間轉(zhuǎn)換到遺傳算法所 能處理的搜索空間的轉(zhuǎn)換方法就稱為編碼。而由遺傳算法的解空間向問(wèn)題空間 的轉(zhuǎn)換稱為解碼。 編碼是應(yīng)用遺傳算法時(shí)要解決的首要問(wèn)題，也是設(shè)計(jì)遺傳算法時(shí)的一個(gè)關(guān)鍵 步驟。由于遺傳算法應(yīng)用的廣泛性，迄今為止人們已經(jīng)提出了許多種不同的編 碼方法?？偟膩?lái)說(shuō)，這些編碼方法可以分為三大類：二進(jìn)制編碼、浮點(diǎn)數(shù)編碼、 符號(hào)編碼方法。 浮點(diǎn)數(shù)編碼方法嘲：對(duì)于一些多維，高精度要求的連續(xù)優(yōu)化算法，使用二 進(jìn)制編碼來(lái)表示個(gè)體時(shí)將會(huì)有一些不利之處。人們?cè)谝恍┙?jīng)典優(yōu)化算法的研究 中的一些寶貴經(jīng)驗(yàn)也就無(wú)法在這里加以利用，也不便于處理非平凡約束條件。 為了克服二進(jìn)制編碼方法的缺點(diǎn)，人們提出了個(gè)體的浮點(diǎn)編碼方法。所謂浮點(diǎn) 1 6 北京郵電大學(xué)碩士研究生畢業(yè)論文 數(shù)編碼方法，是指?jìng)€(gè)體的每個(gè)基因值用某一范圍內(nèi)的一個(gè)浮點(diǎn)數(shù)來(lái)表示，個(gè)體 的編碼長(zhǎng)度等于其決策變量的位數(shù)，因?yàn)檫@種編碼方法使用的是決策變量的真 實(shí)值，所以浮點(diǎn)數(shù)編碼方法也叫做真值編碼方法。 浮點(diǎn)數(shù)編碼方法有以下幾個(gè)優(yōu)點(diǎn)： ( 1 ) 適合于在遺傳算法中表示范圍較大的數(shù)； ( 2 ) 適合于精度要求較高的遺傳算法； ( 3 ) 便于較大空間的遺傳搜索； ( 4 ) 改善了遺傳算法的計(jì)算復(fù)雜度，提高了運(yùn)算效率； ( 5 ) 便于遺傳算法與經(jīng)典優(yōu)化算法的混合使用； ( 6 ) 便于設(shè)計(jì)針對(duì)問(wèn)題的專門知識(shí)的知識(shí)型遺傳算子； ( 7 ) 便于處理復(fù)雜的決策變量約束條件。 2 個(gè)體適應(yīng)度函數(shù) 在遺傳算法中，使用適應(yīng)度( f i t n e s s ) 這個(gè)概念來(lái)度量群體中各個(gè)個(gè)體在優(yōu) 化計(jì)算中能達(dá)到或接近于或有助于找到最優(yōu)解的優(yōu)良程度。適應(yīng)度較高的個(gè)體 遺傳到下一代的概率就較大；而適應(yīng)度較低的個(gè)體遺傳到下一代的概率就相對(duì) 小一些。度量個(gè)體適應(yīng)度的函數(shù)就稱為適應(yīng)度函數(shù)( f i t n e s sf u n c t i o n ) 。 適應(yīng)度函數(shù)也稱為評(píng)價(jià)函數(shù)，是根據(jù)目標(biāo)函數(shù)確定的用于區(qū)分群體中個(gè)體 好壞的標(biāo)準(zhǔn)，是算法演化過(guò)程中的驅(qū)動(dòng)力，也是進(jìn)行自然選擇的唯一依據(jù)。適 應(yīng)度函數(shù)總是非負(fù)的，任何情況下都希望其值越大越好。而目標(biāo)函數(shù)可能有正 有負(fù)，即有時(shí)求最大值，有時(shí)求最小值，因此需要在目標(biāo)函數(shù)與適應(yīng)度函數(shù)之 間進(jìn)行變換。 遺傳算法的一個(gè)特點(diǎn)是它僅使用所求問(wèn)題的目標(biāo)函數(shù)值就可以得到下一步 的有關(guān)搜索信息。而對(duì)目標(biāo)函數(shù)值的使用是通過(guò)評(píng)價(jià)個(gè)體的適應(yīng)度來(lái)體現(xiàn)的。 評(píng)價(jià)適應(yīng)度函數(shù)的一般過(guò)程為： ( 1 ) 對(duì)個(gè)體編碼串進(jìn)行解碼處理后，可得到個(gè)體的表現(xiàn)型； ( 2 ) 由個(gè)體的表現(xiàn)型可計(jì)算出對(duì)應(yīng)個(gè)體的目標(biāo)函數(shù)值； ( 3 ) 根據(jù)最優(yōu)化問(wèn)題的類型，由目標(biāo)函數(shù)值按一定的轉(zhuǎn)換規(guī)則求出個(gè)體的適 應(yīng)度。 3 選擇算子 選擇算子或是復(fù)制算子是遺傳算法的基本算子，它的作用是從當(dāng)前代群體 中選擇出一些比較優(yōu)良的個(gè)體，并將其復(fù)制到下一代群體中。體現(xiàn)了“適者生 存 的自然選擇原則。它的主要目的是為了避免基因缺失、提高全局收斂性和 計(jì)算效率。 目前所適應(yīng)的選擇算子有以下幾種： 1 7 北京郵電人學(xué)碩士研究生畢業(yè)論文 最常用和最基本的選擇算子是比例選擇算子( p r o p o r t i o n a lm o d e l ) 。所謂 比例選擇算子，是指被選中并遺傳到下一代群體中的概率與該個(gè)體的適應(yīng)度大 小成正比。比例選擇實(shí)際上是一種有退還隨機(jī)選擇，也叫做賭盤( r o u l e t t e w h e e l ) 選擇，因?yàn)檫@種選擇方式與賭博中的賭盤操作原理頗為相似。但是這種 操作容易產(chǎn)生較大的抽樣誤差。 最優(yōu)保留策略( e l i t i s tm o d e l ) ，即當(dāng)前群體中適應(yīng)度最高的個(gè)體不參與交 叉運(yùn)算和變異運(yùn)算，而是用它來(lái)替換掉本代群體中經(jīng)過(guò)交叉變異等遺傳操作后 所產(chǎn)生的適應(yīng)度最低的個(gè)體。 確定式采樣選擇( d e t e r m i n i s t i cs a m p l i n g ) ，它的基本思想是按照一種確 定的方式來(lái)進(jìn)行選擇操作。它能保證適應(yīng)度較大的一些個(gè)體一定能被保留在下 一代群體中，并且操作簡(jiǎn)單。 無(wú)回放隨機(jī)選擇( e x p e c t e dv a l u em o d e l ) ，它的基本思想是根據(jù)每個(gè)個(gè)體 在下一代群體中的生存期望值來(lái)進(jìn)行選擇運(yùn)算。這種操作可以降低選擇誤差， 但操作不便。 無(wú)回放余數(shù)隨機(jī)選擇( r e m a i n d e rs t o c h a s t i cs a m p l i n gw i t hr e p l a c e m e n t ) 它的主要思想是取每個(gè)個(gè)體在下一代群體中的生存期望的整數(shù)部分做比例選 擇。它能確保適應(yīng)度比平均適應(yīng)度大的一些個(gè)體一定能夠被遺傳到下一代群體 中，因此選擇誤差比較小。 排序選擇( r a n k - b a s e dm o d e l ) ，其主要思想是對(duì)群體中所有個(gè)體按照其適 應(yīng)度大小進(jìn)行排序，基于這個(gè)排序來(lái)分配各個(gè)個(gè)體被選中的概率。它著眼于各 個(gè)適應(yīng)度之間的大小關(guān)系，隨機(jī)性很強(qiáng)，有較大的誤差，當(dāng)選擇群體很大時(shí)， 計(jì)算量也很大的。 隨機(jī)聯(lián)賽選擇( s t o c h a s t i ct o u r n a m e n tm o d e l ) 是一種基于個(gè)體適應(yīng)度之間 大小關(guān)系的選擇方法。它的基本思想是每次選取幾個(gè)個(gè)體之中適應(yīng)度最高的一 個(gè)個(gè)體遺傳到下一代群體中。 4 交叉算子 在生物的自然進(jìn)化過(guò)程中，兩個(gè)同源染色體通過(guò)交叉而形成新的染色體， 從而產(chǎn)生出新的個(gè)體和物種。交叉重組是生物遺傳和進(jìn)化過(guò)程中的一個(gè)主要環(huán) 節(jié)。模仿這個(gè)環(huán)節(jié)，在遺傳算法中也使用交叉算子來(lái)產(chǎn)生新的個(gè)體。 遺傳算法中所謂交叉運(yùn)算，是指對(duì)兩個(gè)相互配對(duì)的染色體按某種方式相互 交換其部分基因，從而形成兩個(gè)新的個(gè)體。它在遺傳算法中起著關(guān)鍵作用，是 產(chǎn)生新個(gè)體的主要方法，決定了遺傳算法的全局搜索能力。 交叉算子的設(shè)計(jì)和實(shí)現(xiàn)與所研究的問(wèn)題密切相關(guān)，一般要求它既不要太多 地破壞個(gè)體編碼串中表示優(yōu)良性狀的優(yōu)良模式，又要能夠有效地生產(chǎn)出一些比 較好的新個(gè)體模式。另外，交叉算子的設(shè)計(jì)要和個(gè)體編碼實(shí)際統(tǒng)一考慮。 1 8 北京郵電人學(xué)碩士研究生畢業(yè)論文 最常用的交叉算子有如下幾種： ( 1 ) 單點(diǎn)交叉( o n e - p o i n tc r o s s o v e r ) ，又成為簡(jiǎn)單交叉，它是在個(gè)體編碼 串隨機(jī)設(shè)置一個(gè)交叉點(diǎn)，然后在該點(diǎn)相互交換兩個(gè)配對(duì)個(gè)體的部分染色體。單 點(diǎn)交叉的重要特點(diǎn)是：若鄰接基因座之間的關(guān)系能提供較好的個(gè)體性狀和較高 的個(gè)體適應(yīng)度的話，則這種單點(diǎn)交叉操作破壞這