遺傳算法及其在TSP問題中的應(yīng)用

1、遺傳算法及其在 TSP 問題中的應(yīng)用摘要： 本文首先介紹了遺傳算法的基本理論與方法，從應(yīng)用的角度對遺傳算法做了認(rèn)真的分析和研究，總結(jié)了用遺傳算法提出求解組合優(yōu)化問題中的典型問題一一TSP問題的最優(yōu)近似解的算法。 其次，本文在深入分析和研究了遺傳算法基本理論與方法的基礎(chǔ) 上，針對旅行商問題的具體問題，設(shè)計了基于TSP的遺傳算法的選擇、交叉和變異算子等遺傳算子，提出了求解旅行商問題的一種遺傳算法，并用 Matlab 語言編程實(shí)現(xiàn)其算 法，最后繪出算法的仿真結(jié)果，并對不同結(jié)果作出相應(yīng)的分析。然后，本文還針對遺傳算法求解TSP時存在的一些問題對該算法進(jìn)行了適當(dāng)?shù)母倪M(jìn)。如針對初始群體、遺傳算子作出適當(dāng)改

2、進(jìn)， 或者將遺傳算法與其他方法相結(jié)合， 以及在編程過程中對算法流程 的改進(jìn)。本人在用計算機(jī)模擬遺傳算法求解TSP問題時，首先分析了用 Matlab語言設(shè)計遺傳算法程序的優(yōu)越性，接著以遺傳算法求解 TSP問題為例，深入討論了各個遺傳算子的程序?qū)崿F(xiàn)， 并通過分析實(shí)驗(yàn)數(shù)據(jù)，得到各個遺傳算子在搜索尋優(yōu)過程中所起的作 用，最后指出了用 Matlab 語言編程同用其它高級程序語言編程的差異所在，以及運(yùn)用 Matlab 編寫遺傳算法程序的一些注意事項(xiàng)。 最后，本文提出將遺傳算法與其它算法相 結(jié)合來求解一般問題的想法； 并將遺傳算法的應(yīng)用范圍擴(kuò)展，提出可以運(yùn)用遺傳算法求 解由TSP衍生出的各類TSP擴(kuò)展問題，

3、如求解配送/收集旅行商問題的遺傳算法 （TSPD、 遺傳算法在貨物配送問題中的應(yīng)用（ST TSP、多旅行商問題（MTSP等。引言：優(yōu)化問題可以自然地分為兩類：一類是連續(xù)變量的優(yōu)化問題；另一類是離散變量 的優(yōu)化問題，即所謂組合優(yōu)化問題。對于連續(xù)變量的優(yōu)化問題，一般是求一組實(shí)數(shù)或一 個函數(shù)； 而在組合優(yōu)化問題中， 一般是從一個無限集或有限的幾個無限集中尋找一個對 象它可以是一個整數(shù)，一個集合，一個排列或者一個圖，也即是從可行解中求出最 優(yōu)解的問題。TSP問題就是其中的典型例子，就本質(zhì)上而言它可抽象為數(shù)學(xué)上的組合優(yōu) 化，它描述的是旅行商經(jīng) N個城市的最短路徑問題，因而對 TSP問題的求解是數(shù)學(xué)上，

4、同時也是優(yōu)化問題中普遍關(guān)注的。旅行商問題（Traveling Salesman Problem，簡稱TSP也稱為貨擔(dān)郎問題，是一個較古的問題，最早可以追溯到 1759年Euler提出的騎 士旅行問題 9 。旅行商問題可以解釋為，一位推銷員從自己所在城市出發(fā)，必須邀訪 所有城市且每個城市只能訪問一次之后又返回到原來的城市，求使其旅行費(fèi)用最?。ê吐眯芯嚯x最短）的路徑。TSP是一個典型的組合優(yōu)化問題，并且是一個NP難題，所以一般很難精確地求出其最優(yōu)解， 因而尋找出其有效的近似求解算法就具有重要的理論意 義。另一方面，很多實(shí)際應(yīng)用問題，如公安執(zhí)勤人員的最優(yōu)巡回路線、流水作業(yè)生產(chǎn)線 的順序問題、車輛調(diào)度

5、問題、網(wǎng)絡(luò)問題、切割問題以至機(jī)組人員的輪班安排、教師任課 班級負(fù)荷分配等問題，經(jīng)過簡化處理后，都可建模為TSP問題，因而對旅行商問題求解方法的研究也具有重要的應(yīng)用價值。再者，在各種遺傳算法應(yīng)用實(shí)例中，其個體編碼方 法大多都是采用二進(jìn)制編碼方法或浮點(diǎn)數(shù)編碼方法，而TSP問題是一種典型的需要使用符號編碼方法的實(shí)際問題，所以，研究求解TSP問題的遺傳算法，對促進(jìn)遺傳算法本身的發(fā)展也具有重要意義。 在過去的 20 年里，在求解旅行商問題的最優(yōu)解方面取得了 極大的進(jìn)展。盡管有這些成就，但旅行商問題還遠(yuǎn)未解決，問題的許多方面還要研究， 很多問題還在期待滿意的回答。另外， 遺傳算法就其本質(zhì)來說， 主要是解決

6、復(fù)雜問題的一種魯棒性強(qiáng)的啟發(fā)式隨機(jī)搜索算法。早在1983年，就有學(xué)者用GA求解組合優(yōu)化中著名的 TSP問題。Wetzel、 Brady、Grefenstette等人都曾用遺傳算子來討論 TSP問題6,7,8。實(shí)踐也證明，遺傳算法對于組合優(yōu)化中的 NP完全問題非常有效。因此遺傳算法在TSP問題求解方面的應(yīng)用研究，對于構(gòu)造合適的遺傳算法框架、建立有效的遺傳操作以及有效地解決TSP問題等有著多方面地重要意義。3.TSP 問題的數(shù)學(xué)模型和基本解法遺傳算法的主要應(yīng)用領(lǐng)域就包括組合優(yōu)化問題，而組合優(yōu)化中主要是TSP問題等。TSP問題是一個NP完全問題，近幾年來，基于遺傳算法求解TSP問題的研究相當(dāng)活躍，在

7、遺傳算法研究中，TSP問題已被廣泛地用于評價不同的遺傳操作及選擇機(jī)制的性能14,15 。TSP問題的提出最早可追溯到 18世紀(jì)的歐拉時代，但直到 20司世紀(jì)中葉才由于優(yōu)化技 術(shù)的興起逐漸為人所認(rèn)識而著名。 1948年，由美國蘭德公司推動，TSP成為近代組合優(yōu) 化領(lǐng)域的一個典型難題。它是一個具有廣泛應(yīng)用背景和重要理論價值的組合優(yōu)化問題。TSP的搜索空間隨著城市規(guī)模數(shù) n的增加而增大，這類組合優(yōu)化問題稱之為 NP完全問題 16 。3.1TSP 問題的數(shù)學(xué)模型TSP問題可以簡單地描述成：一名旅行商從一個城市出發(fā)，欲遍訪 n個城市推銷商品， 每個城市到一次且僅到一次后返回原出發(fā)城市，求總距離最短的巡回

8、路徑。旅行商問題可分為兩類：(1) 對稱旅行商問題( dij dji, i, j 1,2, ,n)；(2) 非對稱旅行商問題( dij dji, i, j 1,2, ,n)。TSP問題的數(shù)學(xué)模型如下：設(shè)有 n個城市，尋找一條巡回路徑 T (t,t2, ,tn)，使得下列目標(biāo)函數(shù)最?。簄1f(T)d(ti,ti 1) d(tn,t1)i1其中 ti 為城市號，取值為 1 到 n 之間的自然數(shù)， d(i, j) 為城市 i 和城市 j 之間的距離，對于對稱式TSF，有d(i, j) d(j,i)。旅行商問題屬于典型的組合優(yōu)化問題，并且是一個NP完全問題，其可能的路徑數(shù)目為(n-1)!/211 ,至

9、今尚未找到有效的解決方法。在理論上一些方法是可以解這一問題，但 當(dāng) n 較大時，解題的時間消耗會使這些方法顯得沒有任何實(shí)際價值，所以設(shè)計一種 有效算法以獲得問題的最優(yōu)解或近似解是具有重要意義的。目前已有很多求解 TSP近似最優(yōu)解的算法，主要包括：分枝定界法( branch and bound )、最近鄰法( nearest neighbor )、貪婪法( greedy algorithm )、最近插入法( nearest insertion )、最 遠(yuǎn)插入法( farthest insertion )、雙最小生成樹法( double mining spaning tree )、剝脫法（ str

10、ip ）、空間填空曲線法（ space-filling curve）、 Karp 法、 Litke 法、Christofides 法、2-交叉法（2-opt ）、k-交叉法及 Lin-Kernighan 法等11,17,18。 正是由于TSP問題在實(shí)際應(yīng)用中所具有的典型意義，如可用來解決分配問題、路徑問題、 車輛調(diào)度問題等 , 以及算法理論研究上的價值 , 所以它一直吸引著各個領(lǐng)域的研究人員 去研究各種新的算法。3.2 TSP 的傳統(tǒng)解決方法幾十年來對于求解TSP問題出現(xiàn)了很多傳統(tǒng)方法，其中有精確算法如線性規(guī)劃方法、動 態(tài)規(guī)劃方法、 分枝定界法， 近似優(yōu)化算法如最近插入法、 最近鄰法、 Cla

11、rk&Wright 算法、 雙最小生成樹法、 Christofides 算法、 r-opt 算法、混合算法、概率算法等。其中，線性規(guī)劃方法是求解TSP的最早的一種算法，主要是采用整數(shù)規(guī)劃中的割平面 法。 動態(tài)規(guī)劃方法一般用于很小規(guī)模的問題。 分枝定界算法是一種應(yīng)用范圍很廣的搜索 算法，它通過有效的約束界限來控制搜索進(jìn)程使之能向著空間狀態(tài)樹上有最優(yōu)解的分支 推進(jìn)，以便盡快找出一個最優(yōu)解， 該方法的關(guān)鍵在于約束界限的選取， 不同的約束界限， 可形成不同的分支定界法；但分枝定界算法對于解大規(guī)模問題不是很有效。近似算法都是適用于對稱 TSP問題的。其中r-opt方法是一種局部改進(jìn)搜速算法?；?合算法是

12、用某個近似算法求得初始解， 然后借助一個或者若干個 r-opt 算法對解加以改 進(jìn)，這種混合型算法往往能獲得較好的解，但也很耗時?？偠灾瑐鹘y(tǒng)的優(yōu)化算法是一種局部搜索算法，一般得到局部最優(yōu)解，很難達(dá)到全 局最優(yōu)解，并且很難適用于大規(guī)模的最優(yōu)化問題。3.3 TSP 的智能優(yōu)化算法近年來，有很多解決TSP問題的較為有效的智能優(yōu)化方法不斷被推出，例如禁忌搜索方法、模擬退火算法、遺傳算法等。禁忌搜索方法（TS）是對局部領(lǐng)域搜索的一種擴(kuò)展，是一種全局逐步尋優(yōu)算法，是對 人類智力過程的一種模擬。TS算法通過引入一個靈活的存儲結(jié)構(gòu)和相應(yīng)的禁忌準(zhǔn)則來避 免迂回搜索， 并通過藐視準(zhǔn)則來赦免一些被禁忌的優(yōu)良狀態(tài)

13、，進(jìn)而保證多樣化的有效搜 索以實(shí)現(xiàn)全局優(yōu)化。模擬退火算法的出發(fā)點(diǎn)是基于物理中固體物質(zhì)的退火過程與一般組合優(yōu)化問題之間 的相似性。模擬退火算法是在某一初溫下，伴隨溫度參數(shù)的不斷下降，結(jié)合概率突跳性 在解空間中隨機(jī)尋找目標(biāo)函數(shù)的全局最優(yōu)解， 使得局部最優(yōu)解能概率性的跳出并最終趨 于全局最優(yōu)解。這兩種方法是從一個解進(jìn)行局域搜索，雖然都有其各自的長處，但卻存在著全局搜 索能力差的弱點(diǎn)， 極有可能找到的是局部最優(yōu)解； 盡管可以采用一定機(jī)制有效避免陷入 局部極小并最終趨于全局最優(yōu)，但是時間效率比較低。而遺傳算法具有良好的全局搜索能力，是目前解決各種優(yōu)化問題的最有效方法，已 經(jīng)形成研究熱點(diǎn)。因此，遺傳算法在

14、 TSP問題求解方面的應(yīng)用研究，對于構(gòu)造合適的遺 傳算法框架、建立有效的遺傳操作以及有效地解決TSP問題等有著多方面地重要意義。傳算法是按并行方式搜索一個種群數(shù)目的點(diǎn)， 而不是單個點(diǎn) 16 。它的并行性表現(xiàn)在兩 個方面，一是遺傳算法的內(nèi)在并行性，即可以多臺機(jī)器各自進(jìn)行獨(dú)立種群的演化計算， 運(yùn)行過程中可以進(jìn)行信息交換也可以不進(jìn)行信息交換。二是遺傳算法的內(nèi)含并行性，這 是由于遺傳算法采用種群的方式組織搜索。此外， 遺傳算法還可以很好地與其它算法如 上面講到的禁忌搜索方法和模擬退火方法相結(jié)合，從而使得遺傳算法更加有效。圖 3-1 就是傳統(tǒng)優(yōu)化方法與遺傳算法的比較， 從圖中我們可以很直觀的看出傳統(tǒng)方

15、法與遺傳算法在求解具體問題時的區(qū)別。傳統(tǒng)方法單初始點(diǎn)遺傳算法改進(jìn)(依賴問題)No終止嗎？NNYes終止改進(jìn)(不依賴問題)No終止嗎？NNYes匕 終止圖3 1傳統(tǒng)優(yōu)化方法與遺傳算法的比較4.基于TSP問題的遺傳算法4.1基本算法編碼如何將問題的解轉(zhuǎn)換為編碼表達(dá)的染色體是遺傳算法的關(guān)鍵問題。對于任何應(yīng)用問題， 都必須將解的表達(dá)方法和適用于問題的遺傳算子結(jié)合起來分析考慮。Holla nd的編碼方法是二進(jìn)制串表達(dá)，但對于許多遺傳算法的應(yīng)用，這種簡單的編碼方法很難直接描述出 問題的性質(zhì)，這種簡單的表達(dá)方法尤其不能較好的適用于TSP和其它組合優(yōu)化問題。因此，為TSP提出了以下幾種染色體編碼方法。TSP的

16、編碼策略主要包括近鄰(adjacency)表示、次序(ordinal) 表示、路徑(path)表 示、矩陣表示、邊表示和隨機(jī)鍵表達(dá)等11,13。(1) 近鄰表示近鄰表示是指巡回旅行路線所經(jīng)過的連接兩個城市的路線的順序排列。即：將路徑表示成n個城市的一個排列，且在第i位城市為j當(dāng)且僅當(dāng)路徑中從i所到達(dá)的下一個城 市為j，其中每一條路徑都唯一對應(yīng)一個近鄰表示。例如：(2 4 8 3 9 7 1 5 6)表示路徑 1-2-4-3-8-5-9-6-7。采用近鄰表示的優(yōu)點(diǎn)之一是它比較適合模式分析；缺點(diǎn)是操作比較復(fù)雜，且遺傳算子打斷好路徑的概率較大，因此，算法的性能較差。（2）次序表示次序表示仍將路徑表示

17、成 n個城市的一個排列，該排列的第i個元素在1至n-i+1間取 數(shù)。其表示方法為：先取城市集合 C的順序排列作為次序排列的一個參照點(diǎn)，然后按路 徑中城市處在C的位置確定表示串中的點(diǎn)，且每確定一個則從C中刪除相應(yīng)的城市。次序表示的主要優(yōu)點(diǎn)是可以使用傳統(tǒng)的雜交算子。即以次序表示的任兩條路徑，從某 點(diǎn)截斷后交換相應(yīng)的子串所得到的兩個后代仍是合法路徑。（3）路徑表示 路徑表示可能是TSP的最自然、最直接的表示方式，大多數(shù)求解旅行 商問題的遺傳算法都是以它為描述方法的。 路徑表示直接采用城市在路徑中的相當(dāng)位置 來進(jìn)行表示，即巡回旅行線路所經(jīng)過的各個城市的順序排列。例如：（ 1 2 3 4 5 6 7 8

18、 9 ）表示路徑 1-2-3-4-5-6-7-8-9?？傊x擇適當(dāng)?shù)暮蜻x解的表達(dá)方法是遺傳算法解決實(shí)際問題的基礎(chǔ)。對于任何應(yīng)用 問題，都必須將解的表達(dá)方法和適于問題的遺傳算子結(jié)合起來分析考慮。4.1.2 適應(yīng)度函數(shù)用遺傳算法求解TSP時，可用費(fèi)用函數(shù)或距離作為問題的適應(yīng)值度量。通常我們?nèi)∵m應(yīng)度函數(shù)為路徑長度Td的倒數(shù)，即f 1/Td。若結(jié)合TSP的約束條件（每個城市且經(jīng)過一次），則適應(yīng)度函數(shù)可表示成：f 1/（TdNt），其中Nt是對TSP路徑不合法的度量（如取Nt為未遍歷的城市的個數(shù)），為懲罰系數(shù)5?？梢?，若取每條旅行路線的總行程的倒數(shù)為適應(yīng)值，則適應(yīng)值越大，方案越優(yōu)。4.1.3 選擇算子

19、用遺傳算法求解TSP問題時，最常用的選擇算子是比例選擇算子，即賭輪策略；其次,還有最優(yōu)保存選擇策略和期望值策略。4.1.4 交叉算子旅行商問題對交叉算子的設(shè)計要求是：對任意兩條巡回路線進(jìn)行交叉操作之后，都能夠得到另外兩條新的并且具有實(shí)際意義的巡回路線。經(jīng)過實(shí)驗(yàn)表明，傳統(tǒng)的雜交算子并不適合求解TSP問題11。下面介紹常用的幾種用于旅行商問題求解的交叉算子。（ 1 ） 部分映射交叉PMX 操作的主要思想是：整個交叉操作過程由兩步來完成，首先對個體編碼串進(jìn)行常 規(guī)的雙點(diǎn)交叉操作， 然后根據(jù)交叉區(qū)域內(nèi)各個基因值之間的映射關(guān)系來修改交叉區(qū)域之 外的各個基因座的基因值。PMX 步驟：Step1 ：在字串上

20、均勻隨機(jī)地選擇兩點(diǎn)，由這兩點(diǎn)定義的子串稱為映射段；Step2 :交換雙親的兩個子串，產(chǎn)生原始后代；Step3 :確定兩映射之間的映射關(guān)系；Step4 ：根據(jù)映射關(guān)系將后代合法化。pmX操作保留了部分城市的絕對訪問順序，但是它更多的產(chǎn)生出了父代巡回路線中 所沒有的新路線，所以這種操作方法的性狀遺傳特性不太好。（2）順序交叉OX 的主要思想是：先進(jìn)行常規(guī)的雙點(diǎn)交叉，然后進(jìn)行個體巡回路線的有效順序修改， 修改時，要盡量的維持各城市原有的相對訪問順序。0X步驟：Step1 ：從第一雙親中隨機(jī)選一個子串；Step2 ：將子串復(fù)制到一個空字串的相應(yīng)位置，產(chǎn)生一個原始后代；Step3 :刪去第二雙親中子串已

21、有的城市，得到原始后代需要的其它城市的順序；Step4 :按照這個城市順序，從左到右將這些城市定位到后代的空缺位置上。0X操作保留了部分城市的相對訪問順序，但是它也更多的城市出了父代巡回路線中所沒有的部分新路線，所以這種操作方法的性狀遺傳特性不太好。（3）循環(huán)交叉CX的基本思想是：任意兩條巡回路線都可能組成一些互補(bǔ)相交的巡回回路，相互交換其中一個循環(huán)回路的基因就有可能產(chǎn)生出新的巡回路線。CX 步驟：Stepl :根據(jù)雙親相應(yīng)的城市位置找出一個循環(huán)；Step2 ：把一個雙親的循環(huán)上的城市復(fù)制到一個后代上；Step3 :刪去另一個雙親的已在循環(huán)上的城市，剩下的城市即可用來確定剩余城市 的位置；St

22、ep4 :用這些剩余城市填滿后代剩余的位置。（4）基于位置的交叉步驟:Step1 :從一個雙親上隨機(jī)地選一組位置；Step2 :將這些位置復(fù)制到一個空字串的相應(yīng)位置，產(chǎn)生一個原始后代；Step3 :刪去第二雙親上該組中已有的城市，剩下的城市構(gòu)成了原始后代需要的順 序；Step4 :按照這個城市順序，從左到右將這些城市定位到后代的空缺位置上。除此之外，還有一些交叉算子:基于順序的交叉，該方法實(shí)際上是基于位置的交叉 的變型， 其中一個雙親選定位置上的城市的順序強(qiáng)制被另一雙親的相應(yīng)城市所替代；邊 重組交叉（Edge Recomb in ation Crossover, 簡稱EX）,其主要思想是重點(diǎn)強(qiáng)

23、調(diào)了對父 代巡回路線上的邊之間的鄰接關(guān)系的遺傳，它考慮了旅行商問題性狀的遺傳特點(diǎn)；啟發(fā)式雜交,選擇由現(xiàn)行城市出發(fā)的不構(gòu)成循環(huán)的最短邊。4.1.5 變異算子旅行商問題對變異算子的設(shè)計要求是:對任意一個個體編碼串進(jìn)行變異操作后,所產(chǎn)生的新個體應(yīng)該能夠?qū)?yīng)于一條具有實(shí)際意義的巡回路線。針對TSP問題，變異算子主要包括位點(diǎn)變異、 逆轉(zhuǎn)變異（ inversion mutation ）、插入變異（ insertion mutation ）、 移位變異（displacement mutation ）、互換變異（s） 等。（1）位點(diǎn)變異: 變異僅以一定的概率（通常較小）對串的某些位作值的變異。（2）逆轉(zhuǎn)變異:

24、 逆轉(zhuǎn)變異是先在父體中隨機(jī)地選擇兩截斷點(diǎn),然后將該兩點(diǎn)所夾 的子串中的城市進(jìn)行反序。（ 3）插入變異: 插入變異是隨機(jī)選擇一個城市,并將它插入到一個隨機(jī)的位置中。(4) 移位變異： 移位變異是隨機(jī)選擇一子路徑，并將其插入到一個隨機(jī)的位置中。( 5)互換變異： 也稱基于次序的變異( order-based mutation )，它是隨機(jī)地選 擇兩個位置，并將這兩個位置上的城市相互交換。其它還有一些變異算子：基于位置的變異( position-based mutation )是隨機(jī)選 擇兩城市，將第二個城市放在第一個之前；打亂變異(scramble mutation )是隨機(jī)選擇一子路徑， 打亂其

25、次序， 重新插入； 啟發(fā)式變異采用了鄰域技術(shù)， 以獲得后代的改進(jìn)， 即對于一個染色體按它的鄰域交換不多于 個基因， 可獲得一族染色體， 選擇其中最好 的一個作為變異產(chǎn)生的后代。對于變異操作還有一些變體形式，如 Sushil J.Louis 提出的貪心對換變異 (greedy-s)9 ，其基本思想是從一個染色體中隨機(jī)的選擇兩個城市(即兩個碼值 ) ，然后交換它們， 得到新的染色體， 以旅程長度為依據(jù)比較交換后的染色體與原來的染色體 的大小，保留旅程長度值小的染色體。這種算子實(shí)際上是互換變異算子的改進(jìn)算子。求解TSP問題時，變異算子的設(shè)計要比雜交算子的設(shè)計靈活的多，任何具有局部搜 索功能的算子都可

26、以作為它的變異算子。4.2 算法設(shè)計基于以上理論，本人先采用經(jīng)典的遺傳算法理論及個體整數(shù)編碼方法設(shè)計了算法。但從算法的實(shí)現(xiàn)結(jié)果分析發(fā)現(xiàn)， 算法的運(yùn)行結(jié)果雖然得到了相對最優(yōu)解，但是當(dāng)群體規(guī) 模較大時， 算法在運(yùn)行過程中出現(xiàn)了局部早熟的現(xiàn)象。所以本人對算子的選取進(jìn)行了改 進(jìn)重組，重新設(shè)計了各個算子，試圖進(jìn)一步探索TSP組合優(yōu)化問題的有效解決方案。4.2.1 編碼在求解TSP問題的各種遺傳算法中，多采用以遍歷城市的次序排列進(jìn)行編碼的方法， 本文也采用這種最自然的編碼方式，即以 n 個城市的遍歷次序作為遺傳算法的編碼。每 一個解的碼串形如：Vi，V2，, Vn，其中，Vi表示遍歷城市的序號。程序中的解

27、定義為一維數(shù)組A(N) , N表示TSP問題中的城市數(shù)目，數(shù)組中的各個元素A(i)(i 1,2, , ,N)的取值為1至N間的整數(shù)，分別表示城市的序號，根據(jù)問題的約束條件，每一整數(shù)內(nèi)的 各元素值互不相同。4.2.2 初始群體 在遺傳算法中，初始群體一般是隨機(jī)產(chǎn)生的，通過種群的進(jìn)化最終達(dá)到最優(yōu)值。但在實(shí) 際操作時，這樣進(jìn)化的速度太慢，且進(jìn)化效果往往不太好。因此，本人對初始種群的選 取方式做了改進(jìn)。在這里，初始群體也是隨機(jī)產(chǎn)生的，但所不同的是這里的隨機(jī)是有一 定前提條件的。具體操作是：設(shè)群體規(guī)模是 popsize ，首先用貪婪法( Greedy Method ) 產(chǎn)生n (nvpopsize )個

28、個體，這n個個體的起點(diǎn)城市分別是 1,2,n，再隨機(jī)產(chǎn)生剩 余的城市個體。 貪婪法是將每一步都取局部最優(yōu)的求解方法，這種用貪婪法產(chǎn)生的個體 在一定程度上具有有效的基因模式，有利于提高尋優(yōu)能力。在次算法中，隨機(jī)生成規(guī)模為 popsize 的初始群體， n 取為城市個數(shù) lchrom 。4.2.3 適應(yīng)度函數(shù)由于本算法在可行解群體的初始化、 交叉操作及變異操作中均隱含 TSP問題的合法性 約束條件(即對所有城市要做到不重不漏)，故適應(yīng)度函數(shù)取為哈密頓圈(Hamilton )的長度的倒數(shù)(無懲罰函數(shù)) 5,21 。用路徑倒數(shù)作為適應(yīng)值是 Glodberg.D.E. 首先提出的 4 。適應(yīng)度函數(shù)取路徑

29、長度(即哈密頓圈長)Td 的倒數(shù)，即Fitness(i ) 1/Td (i)其中 Td(i) 表示第 i 個解所表示的遍歷城市的路徑長度，即： 1 111),(),()(jnnjjdvvdvvdiT 4.2.4 選擇算子 遺傳算法采用的選擇算子一般有賭輪 法、最優(yōu)保存方法和期望值選擇方法等。賭輪選擇個體的方法是，先把群體中的每個個 體的適應(yīng)值按比例轉(zhuǎn)化為選中概率 ip ，將輪盤分成 popsize 個扇區(qū)；產(chǎn)生一個 0,1 之 間的隨機(jī)數(shù) r ，如果從第一個個體的選中概率開始累加， 直到累加概率之和 iq 大于或等 于 r ，則將最后一個被累加選中概率的個體挑選出來，并復(fù)制到子代中。隨著遺傳算

30、法 的執(zhí)行，我們始終保留 popsize 個較優(yōu)的個體作為樣本群體，以供選擇。但是對于賭輪 選擇算子，由于是隨機(jī)操作的原因，這種選擇方法的選擇誤差比較大，有時甚至連適應(yīng) 度較高的個體也選擇不上。 遺傳算法的理論已經(jīng)證明了賭輪法選擇算子不能收斂到全局 最優(yōu)解， 而最優(yōu)保存方法相比之下則能收斂到全局最優(yōu)解。 遺傳算法中一個要求解決 的問題是如何防止“早熟”收斂現(xiàn)象。 為了保證遺傳算法的全局收斂性，就要維持群體 中個體的多樣性，避免有效基因的丟失。因此，作為改進(jìn)，本文將引入最優(yōu)選擇策略即 保持群體中最好的個體不丟失， 以保證算法的收斂性。 采用最優(yōu)保存選擇方法的優(yōu)點(diǎn) 是，進(jìn)化過程中某一代的最優(yōu)解可不

31、被交叉和變異操作所破壞。但是，這也隱含了一種 危機(jī)，即如果只選用最優(yōu)選擇策略，則局部最優(yōu)個體的遺傳基因會急速增加而使進(jìn)化有 可能限于局部解。所以此方法一般都與其它選擇方法結(jié)合使用 5 。因此，我改進(jìn)了遺 傳算法的選擇算子， 采用賭輪選擇策略和最優(yōu)保存策略相結(jié)合的方法。 本文所采用的 賭輪和最優(yōu)保存相結(jié)合的方法，具體描述如下： Stepl ：求出 pop(t )中適應(yīng)度最大 的 1 個個體，記為 best ，將 best 作為下一代的個體，即最優(yōu)個體必遺傳到下一代中。 Step2 :令p(k)為個體k的輪轉(zhuǎn)法選擇概率，則201 1 )(/)()(Niifkfkp k= 1,2, , ,N Step3 :令 q(0)=0 ,q(k)=q(1) + q(2)+ +q(k), k=1,2, ,N Step 4:產(chǎn)生 N-1 個0,1 )中的均勻分布的隨機(jī)數(shù)ir，i=1,2, ,N-1，依次判斷這N-1個隨機(jī)數(shù)，若q(k-1) vir vq(k)，則選 個體 k 為下一代的個體。 4.2.5 交叉算子 算法思想:通過賭輪策略，從父代中選擇 兩個個體， 利用如下操作， 通過從一個親體中挑選一個城市子序列并保存另一個親體的 城市相對次序來構(gòu)造兩個新的個體，然后將這兩個新個體添加到子代中去。基于基因片段保序在求解TSP問題中的應(yīng)用21,本文采用了一種改進(jìn)的交叉