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

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