下載本文檔
版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、遺傳算法及其在 TSP 問(wèn)題中的應(yīng)用摘要: 本文首先介紹了遺傳算法的基本理論與方法,從應(yīng)用的角度對(duì)遺傳算法做了認(rèn)真的分析和研究,總結(jié)了用遺傳算法提出求解組合優(yōu)化問(wèn)題中的典型問(wèn)題一一TSP問(wèn)題的最優(yōu)近似解的算法。 其次,本文在深入分析和研究了遺傳算法基本理論與方法的基礎(chǔ) 上,針對(duì)旅行商問(wèn)題的具體問(wèn)題,設(shè)計(jì)了基于TSP的遺傳算法的選擇、交叉和變異算子等遺傳算子,提出了求解旅行商問(wèn)題的一種遺傳算法,并用 Matlab 語(yǔ)言編程實(shí)現(xiàn)其算 法,最后繪出算法的仿真結(jié)果,并對(duì)不同結(jié)果作出相應(yīng)的分析。然后,本文還針對(duì)遺傳算法求解TSP時(shí)存在的一些問(wèn)題對(duì)該算法進(jìn)行了適當(dāng)?shù)母倪M(jìn)。如針對(duì)初始群體、遺傳算子作出適當(dāng)改
2、進(jìn), 或者將遺傳算法與其他方法相結(jié)合, 以及在編程過(guò)程中對(duì)算法流程 的改進(jìn)。本人在用計(jì)算機(jī)模擬遺傳算法求解TSP問(wèn)題時(shí),首先分析了用 Matlab語(yǔ)言設(shè)計(jì)遺傳算法程序的優(yōu)越性,接著以遺傳算法求解 TSP問(wèn)題為例,深入討論了各個(gè)遺傳算子的程序?qū)崿F(xiàn), 并通過(guò)分析實(shí)驗(yàn)數(shù)據(jù),得到各個(gè)遺傳算子在搜索尋優(yōu)過(guò)程中所起的作 用,最后指出了用 Matlab 語(yǔ)言編程同用其它高級(jí)程序語(yǔ)言編程的差異所在,以及運(yùn)用 Matlab 編寫(xiě)遺傳算法程序的一些注意事項(xiàng)。 最后,本文提出將遺傳算法與其它算法相 結(jié)合來(lái)求解一般問(wèn)題的想法; 并將遺傳算法的應(yīng)用范圍擴(kuò)展,提出可以運(yùn)用遺傳算法求 解由TSP衍生出的各類(lèi)TSP擴(kuò)展問(wèn)題,
3、如求解配送/收集旅行商問(wèn)題的遺傳算法 (TSPD、 遺傳算法在貨物配送問(wèn)題中的應(yīng)用(ST TSP、多旅行商問(wèn)題(MTSP等。引言:優(yōu)化問(wèn)題可以自然地分為兩類(lèi):一類(lèi)是連續(xù)變量的優(yōu)化問(wèn)題;另一類(lèi)是離散變量 的優(yōu)化問(wèn)題,即所謂組合優(yōu)化問(wèn)題。對(duì)于連續(xù)變量的優(yōu)化問(wèn)題,一般是求一組實(shí)數(shù)或一 個(gè)函數(shù); 而在組合優(yōu)化問(wèn)題中, 一般是從一個(gè)無(wú)限集或有限的幾個(gè)無(wú)限集中尋找一個(gè)對(duì) 象它可以是一個(gè)整數(shù),一個(gè)集合,一個(gè)排列或者一個(gè)圖,也即是從可行解中求出最 優(yōu)解的問(wèn)題。TSP問(wèn)題就是其中的典型例子,就本質(zhì)上而言它可抽象為數(shù)學(xué)上的組合優(yōu) 化,它描述的是旅行商經(jīng) N個(gè)城市的最短路徑問(wèn)題,因而對(duì) TSP問(wèn)題的求解是數(shù)學(xué)上,
4、同時(shí)也是優(yōu)化問(wèn)題中普遍關(guān)注的。旅行商問(wèn)題(Traveling Salesman Problem,簡(jiǎn)稱TSP也稱為貨擔(dān)郎問(wèn)題,是一個(gè)較古的問(wèn)題,最早可以追溯到 1759年Euler提出的騎 士旅行問(wèn)題 9 。旅行商問(wèn)題可以解釋為,一位推銷(xiāo)員從自己所在城市出發(fā),必須邀訪 所有城市且每個(gè)城市只能訪問(wèn)一次之后又返回到原來(lái)的城市,求使其旅行費(fèi)用最?。ê吐眯芯嚯x最短)的路徑。TSP是一個(gè)典型的組合優(yōu)化問(wèn)題,并且是一個(gè)NP難題,所以一般很難精確地求出其最優(yōu)解, 因而尋找出其有效的近似求解算法就具有重要的理論意 義。另一方面,很多實(shí)際應(yīng)用問(wèn)題,如公安執(zhí)勤人員的最優(yōu)巡回路線、流水作業(yè)生產(chǎn)線 的順序問(wèn)題、車(chē)輛調(diào)度
5、問(wèn)題、網(wǎng)絡(luò)問(wèn)題、切割問(wèn)題以至機(jī)組人員的輪班安排、教師任課 班級(jí)負(fù)荷分配等問(wèn)題,經(jīng)過(guò)簡(jiǎn)化處理后,都可建模為T(mén)SP問(wèn)題,因而對(duì)旅行商問(wèn)題求解方法的研究也具有重要的應(yīng)用價(jià)值。再者,在各種遺傳算法應(yīng)用實(shí)例中,其個(gè)體編碼方 法大多都是采用二進(jìn)制編碼方法或浮點(diǎn)數(shù)編碼方法,而TSP問(wèn)題是一種典型的需要使用符號(hào)編碼方法的實(shí)際問(wèn)題,所以,研究求解TSP問(wèn)題的遺傳算法,對(duì)促進(jìn)遺傳算法本身的發(fā)展也具有重要意義。 在過(guò)去的 20 年里,在求解旅行商問(wèn)題的最優(yōu)解方面取得了 極大的進(jìn)展。盡管有這些成就,但旅行商問(wèn)題還遠(yuǎn)未解決,問(wèn)題的許多方面還要研究, 很多問(wèn)題還在期待滿意的回答。另外, 遺傳算法就其本質(zhì)來(lái)說(shuō), 主要是解決
6、復(fù)雜問(wèn)題的一種魯棒性強(qiáng)的啟發(fā)式隨機(jī)搜索算法。早在1983年,就有學(xué)者用GA求解組合優(yōu)化中著名的 TSP問(wèn)題。Wetzel、 Brady、Grefenstette等人都曾用遺傳算子來(lái)討論 TSP問(wèn)題6,7,8。實(shí)踐也證明,遺傳算法對(duì)于組合優(yōu)化中的 NP完全問(wèn)題非常有效。因此遺傳算法在TSP問(wèn)題求解方面的應(yīng)用研究,對(duì)于構(gòu)造合適的遺傳算法框架、建立有效的遺傳操作以及有效地解決TSP問(wèn)題等有著多方面地重要意義。3.TSP 問(wèn)題的數(shù)學(xué)模型和基本解法遺傳算法的主要應(yīng)用領(lǐng)域就包括組合優(yōu)化問(wèn)題,而組合優(yōu)化中主要是TSP問(wèn)題等。TSP問(wèn)題是一個(gè)NP完全問(wèn)題,近幾年來(lái),基于遺傳算法求解TSP問(wèn)題的研究相當(dāng)活躍,在
7、遺傳算法研究中,TSP問(wèn)題已被廣泛地用于評(píng)價(jià)不同的遺傳操作及選擇機(jī)制的性能14,15 。TSP問(wèn)題的提出最早可追溯到 18世紀(jì)的歐拉時(shí)代,但直到 20司世紀(jì)中葉才由于優(yōu)化技 術(shù)的興起逐漸為人所認(rèn)識(shí)而著名。 1948年,由美國(guó)蘭德公司推動(dòng),TSP成為近代組合優(yōu) 化領(lǐng)域的一個(gè)典型難題。它是一個(gè)具有廣泛應(yīng)用背景和重要理論價(jià)值的組合優(yōu)化問(wèn)題。TSP的搜索空間隨著城市規(guī)模數(shù) n的增加而增大,這類(lèi)組合優(yōu)化問(wèn)題稱之為 NP完全問(wèn)題 16 。3.1TSP 問(wèn)題的數(shù)學(xué)模型TSP問(wèn)題可以簡(jiǎn)單地描述成:一名旅行商從一個(gè)城市出發(fā),欲遍訪 n個(gè)城市推銷(xiāo)商品, 每個(gè)城市到一次且僅到一次后返回原出發(fā)城市,求總距離最短的巡回
8、路徑。旅行商問(wèn)題可分為兩類(lèi):(1) 對(duì)稱旅行商問(wèn)題( dij dji, i, j 1,2, ,n);(2) 非對(duì)稱旅行商問(wèn)題( dij dji, i, j 1,2, ,n)。TSP問(wèn)題的數(shù)學(xué)模型如下:設(shè)有 n個(gè)城市,尋找一條巡回路徑 T (t,t2, ,tn),使得下列目標(biāo)函數(shù)最?。簄1f(T)d(ti,ti 1) d(tn,t1)i1其中 ti 為城市號(hào),取值為 1 到 n 之間的自然數(shù), d(i, j) 為城市 i 和城市 j 之間的距離,對(duì)于對(duì)稱式TSF,有d(i, j) d(j,i)。旅行商問(wèn)題屬于典型的組合優(yōu)化問(wèn)題,并且是一個(gè)NP完全問(wèn)題,其可能的路徑數(shù)目為(n-1)!/211 ,至
9、今尚未找到有效的解決方法。在理論上一些方法是可以解這一問(wèn)題,但 當(dāng) n 較大時(shí),解題的時(shí)間消耗會(huì)使這些方法顯得沒(méi)有任何實(shí)際價(jià)值,所以設(shè)計(jì)一種 有效算法以獲得問(wèn)題的最優(yōu)解或近似解是具有重要意義的。目前已有很多求解 TSP近似最優(yōu)解的算法,主要包括:分枝定界法( branch and bound )、最近鄰法( nearest neighbor )、貪婪法( greedy algorithm )、最近插入法( nearest insertion )、最 遠(yuǎn)插入法( farthest insertion )、雙最小生成樹(shù)法( double mining spaning tree )、剝脫法( str
10、ip )、空間填空曲線法( space-filling curve)、 Karp 法、 Litke 法、Christofides 法、2-交叉法(2-opt )、k-交叉法及 Lin-Kernighan 法等11,17,18。 正是由于TSP問(wèn)題在實(shí)際應(yīng)用中所具有的典型意義,如可用來(lái)解決分配問(wèn)題、路徑問(wèn)題、 車(chē)輛調(diào)度問(wèn)題等 , 以及算法理論研究上的價(jià)值 , 所以它一直吸引著各個(gè)領(lǐng)域的研究人員 去研究各種新的算法。3.2 TSP 的傳統(tǒng)解決方法幾十年來(lái)對(duì)于求解TSP問(wèn)題出現(xiàn)了很多傳統(tǒng)方法,其中有精確算法如線性規(guī)劃方法、動(dòng) 態(tài)規(guī)劃方法、 分枝定界法, 近似優(yōu)化算法如最近插入法、 最近鄰法、 Cla
11、rk&Wright 算法、 雙最小生成樹(shù)法、 Christofides 算法、 r-opt 算法、混合算法、概率算法等。其中,線性規(guī)劃方法是求解TSP的最早的一種算法,主要是采用整數(shù)規(guī)劃中的割平面 法。 動(dòng)態(tài)規(guī)劃方法一般用于很小規(guī)模的問(wèn)題。 分枝定界算法是一種應(yīng)用范圍很廣的搜索 算法,它通過(guò)有效的約束界限來(lái)控制搜索進(jìn)程使之能向著空間狀態(tài)樹(shù)上有最優(yōu)解的分支 推進(jìn),以便盡快找出一個(gè)最優(yōu)解, 該方法的關(guān)鍵在于約束界限的選取, 不同的約束界限, 可形成不同的分支定界法;但分枝定界算法對(duì)于解大規(guī)模問(wèn)題不是很有效。近似算法都是適用于對(duì)稱 TSP問(wèn)題的。其中r-opt方法是一種局部改進(jìn)搜速算法?;?合算法是
12、用某個(gè)近似算法求得初始解, 然后借助一個(gè)或者若干個(gè) r-opt 算法對(duì)解加以改 進(jìn),這種混合型算法往往能獲得較好的解,但也很耗時(shí)。總而言之,傳統(tǒng)的優(yōu)化算法是一種局部搜索算法,一般得到局部最優(yōu)解,很難達(dá)到全 局最優(yōu)解,并且很難適用于大規(guī)模的最優(yōu)化問(wèn)題。3.3 TSP 的智能優(yōu)化算法近年來(lái),有很多解決TSP問(wèn)題的較為有效的智能優(yōu)化方法不斷被推出,例如禁忌搜索方法、模擬退火算法、遺傳算法等。禁忌搜索方法(TS)是對(duì)局部領(lǐng)域搜索的一種擴(kuò)展,是一種全局逐步尋優(yōu)算法,是對(duì) 人類(lèi)智力過(guò)程的一種模擬。TS算法通過(guò)引入一個(gè)靈活的存儲(chǔ)結(jié)構(gòu)和相應(yīng)的禁忌準(zhǔn)則來(lái)避 免迂回搜索, 并通過(guò)藐視準(zhǔn)則來(lái)赦免一些被禁忌的優(yōu)良狀態(tài)
13、,進(jìn)而保證多樣化的有效搜 索以實(shí)現(xiàn)全局優(yōu)化。模擬退火算法的出發(fā)點(diǎn)是基于物理中固體物質(zhì)的退火過(guò)程與一般組合優(yōu)化問(wèn)題之間 的相似性。模擬退火算法是在某一初溫下,伴隨溫度參數(shù)的不斷下降,結(jié)合概率突跳性 在解空間中隨機(jī)尋找目標(biāo)函數(shù)的全局最優(yōu)解, 使得局部最優(yōu)解能概率性的跳出并最終趨 于全局最優(yōu)解。這兩種方法是從一個(gè)解進(jìn)行局域搜索,雖然都有其各自的長(zhǎng)處,但卻存在著全局搜 索能力差的弱點(diǎn), 極有可能找到的是局部最優(yōu)解; 盡管可以采用一定機(jī)制有效避免陷入 局部極小并最終趨于全局最優(yōu),但是時(shí)間效率比較低。而遺傳算法具有良好的全局搜索能力,是目前解決各種優(yōu)化問(wèn)題的最有效方法,已 經(jīng)形成研究熱點(diǎn)。因此,遺傳算法在
14、 TSP問(wèn)題求解方面的應(yīng)用研究,對(duì)于構(gòu)造合適的遺 傳算法框架、建立有效的遺傳操作以及有效地解決TSP問(wèn)題等有著多方面地重要意義。傳算法是按并行方式搜索一個(gè)種群數(shù)目的點(diǎn), 而不是單個(gè)點(diǎn) 16 。它的并行性表現(xiàn)在兩 個(gè)方面,一是遺傳算法的內(nèi)在并行性,即可以多臺(tái)機(jī)器各自進(jìn)行獨(dú)立種群的演化計(jì)算, 運(yùn)行過(guò)程中可以進(jìn)行信息交換也可以不進(jìn)行信息交換。二是遺傳算法的內(nèi)含并行性,這 是由于遺傳算法采用種群的方式組織搜索。此外, 遺傳算法還可以很好地與其它算法如 上面講到的禁忌搜索方法和模擬退火方法相結(jié)合,從而使得遺傳算法更加有效。圖 3-1 就是傳統(tǒng)優(yōu)化方法與遺傳算法的比較, 從圖中我們可以很直觀的看出傳統(tǒng)方
15、法與遺傳算法在求解具體問(wèn)題時(shí)的區(qū)別。傳統(tǒng)方法單初始點(diǎn)遺傳算法改進(jìn)(依賴問(wèn)題)No終止嗎?NNYes終止改進(jìn)(不依賴問(wèn)題)No終止嗎?NNYes匕 終止圖3 1傳統(tǒng)優(yōu)化方法與遺傳算法的比較4.基于TSP問(wèn)題的遺傳算法4.1基本算法編碼如何將問(wèn)題的解轉(zhuǎn)換為編碼表達(dá)的染色體是遺傳算法的關(guān)鍵問(wèn)題。對(duì)于任何應(yīng)用問(wèn)題, 都必須將解的表達(dá)方法和適用于問(wèn)題的遺傳算子結(jié)合起來(lái)分析考慮。Holla nd的編碼方法是二進(jìn)制串表達(dá),但對(duì)于許多遺傳算法的應(yīng)用,這種簡(jiǎn)單的編碼方法很難直接描述出 問(wèn)題的性質(zhì),這種簡(jiǎn)單的表達(dá)方法尤其不能較好的適用于TSP和其它組合優(yōu)化問(wèn)題。因此,為T(mén)SP提出了以下幾種染色體編碼方法。TSP的
16、編碼策略主要包括近鄰(adjacency)表示、次序(ordinal) 表示、路徑(path)表 示、矩陣表示、邊表示和隨機(jī)鍵表達(dá)等11,13。(1) 近鄰表示近鄰表示是指巡回旅行路線所經(jīng)過(guò)的連接兩個(gè)城市的路線的順序排列。即:將路徑表示成n個(gè)城市的一個(gè)排列,且在第i位城市為j當(dāng)且僅當(dāng)路徑中從i所到達(dá)的下一個(gè)城 市為j,其中每一條路徑都唯一對(duì)應(yīng)一個(gè)近鄰表示。例如:(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個(gè)城市的一個(gè)排列,該排列的第i個(gè)元素在1至n-i+1間取 數(shù)。其表示方法為:先取城市集合 C的順序排列作為次序排列的一個(gè)參照點(diǎn),然后按路 徑中城市處在C的位置確定表示串中的點(diǎn),且每確定一個(gè)則從C中刪除相應(yīng)的城市。次序表示的主要優(yōu)點(diǎn)是可以使用傳統(tǒng)的雜交算子。即以次序表示的任兩條路徑,從某 點(diǎn)截?cái)嗪蠼粨Q相應(yīng)的子串所得到的兩個(gè)后代仍是合法路徑。(3)路徑表示 路徑表示可能是TSP的最自然、最直接的表示方式,大多數(shù)求解旅行 商問(wèn)題的遺傳算法都是以它為描述方法的。 路徑表示直接采用城市在路徑中的相當(dāng)位置 來(lái)進(jìn)行表示,即巡回旅行線路所經(jīng)過(guò)的各個(gè)城市的順序排列。例如:( 1 2 3 4 5 6 7 8
18、 9 )表示路徑 1-2-3-4-5-6-7-8-9??傊?,選擇適當(dāng)?shù)暮蜻x解的表達(dá)方法是遺傳算法解決實(shí)際問(wèn)題的基礎(chǔ)。對(duì)于任何應(yīng)用 問(wèn)題,都必須將解的表達(dá)方法和適于問(wèn)題的遺傳算子結(jié)合起來(lái)分析考慮。4.1.2 適應(yīng)度函數(shù)用遺傳算法求解TSP時(shí),可用費(fèi)用函數(shù)或距離作為問(wèn)題的適應(yīng)值度量。通常我們?nèi)∵m應(yīng)度函數(shù)為路徑長(zhǎng)度Td的倒數(shù),即f 1/Td。若結(jié)合TSP的約束條件(每個(gè)城市且經(jīng)過(guò)一次),則適應(yīng)度函數(shù)可表示成:f 1/(TdNt),其中Nt是對(duì)TSP路徑不合法的度量(如取Nt為未遍歷的城市的個(gè)數(shù)),為懲罰系數(shù)5??梢?jiàn),若取每條旅行路線的總行程的倒數(shù)為適應(yīng)值,則適應(yīng)值越大,方案越優(yōu)。4.1.3 選擇算子
19、用遺傳算法求解TSP問(wèn)題時(shí),最常用的選擇算子是比例選擇算子,即賭輪策略;其次,還有最優(yōu)保存選擇策略和期望值策略。4.1.4 交叉算子旅行商問(wèn)題對(duì)交叉算子的設(shè)計(jì)要求是:對(duì)任意兩條巡回路線進(jìn)行交叉操作之后,都能夠得到另外兩條新的并且具有實(shí)際意義的巡回路線。經(jīng)過(guò)實(shí)驗(yàn)表明,傳統(tǒng)的雜交算子并不適合求解TSP問(wèn)題11。下面介紹常用的幾種用于旅行商問(wèn)題求解的交叉算子。( 1 ) 部分映射交叉PMX 操作的主要思想是:整個(gè)交叉操作過(guò)程由兩步來(lái)完成,首先對(duì)個(gè)體編碼串進(jìn)行常 規(guī)的雙點(diǎn)交叉操作, 然后根據(jù)交叉區(qū)域內(nèi)各個(gè)基因值之間的映射關(guān)系來(lái)修改交叉區(qū)域之 外的各個(gè)基因座的基因值。PMX 步驟:Step1 :在字串上
20、均勻隨機(jī)地選擇兩點(diǎn),由這兩點(diǎn)定義的子串稱為映射段;Step2 :交換雙親的兩個(gè)子串,產(chǎn)生原始后代;Step3 :確定兩映射之間的映射關(guān)系;Step4 :根據(jù)映射關(guān)系將后代合法化。pmX操作保留了部分城市的絕對(duì)訪問(wèn)順序,但是它更多的產(chǎn)生出了父代巡回路線中 所沒(méi)有的新路線,所以這種操作方法的性狀遺傳特性不太好。(2)順序交叉OX 的主要思想是:先進(jìn)行常規(guī)的雙點(diǎn)交叉,然后進(jìn)行個(gè)體巡回路線的有效順序修改, 修改時(shí),要盡量的維持各城市原有的相對(duì)訪問(wèn)順序。0X步驟:Step1 :從第一雙親中隨機(jī)選一個(gè)子串;Step2 :將子串復(fù)制到一個(gè)空字串的相應(yīng)位置,產(chǎn)生一個(gè)原始后代;Step3 :刪去第二雙親中子串已
21、有的城市,得到原始后代需要的其它城市的順序;Step4 :按照這個(gè)城市順序,從左到右將這些城市定位到后代的空缺位置上。0X操作保留了部分城市的相對(duì)訪問(wèn)順序,但是它也更多的城市出了父代巡回路線中所沒(méi)有的部分新路線,所以這種操作方法的性狀遺傳特性不太好。(3)循環(huán)交叉CX的基本思想是:任意兩條巡回路線都可能組成一些互補(bǔ)相交的巡回回路,相互交換其中一個(gè)循環(huán)回路的基因就有可能產(chǎn)生出新的巡回路線。CX 步驟:Stepl :根據(jù)雙親相應(yīng)的城市位置找出一個(gè)循環(huán);Step2 :把一個(gè)雙親的循環(huán)上的城市復(fù)制到一個(gè)后代上;Step3 :刪去另一個(gè)雙親的已在循環(huán)上的城市,剩下的城市即可用來(lái)確定剩余城市 的位置;St
22、ep4 :用這些剩余城市填滿后代剩余的位置。(4)基于位置的交叉步驟:Step1 :從一個(gè)雙親上隨機(jī)地選一組位置;Step2 :將這些位置復(fù)制到一個(gè)空字串的相應(yīng)位置,產(chǎn)生一個(gè)原始后代;Step3 :刪去第二雙親上該組中已有的城市,剩下的城市構(gòu)成了原始后代需要的順 序;Step4 :按照這個(gè)城市順序,從左到右將這些城市定位到后代的空缺位置上。除此之外,還有一些交叉算子:基于順序的交叉,該方法實(shí)際上是基于位置的交叉 的變型, 其中一個(gè)雙親選定位置上的城市的順序強(qiáng)制被另一雙親的相應(yīng)城市所替代;邊 重組交叉(Edge Recomb in ation Crossover, 簡(jiǎn)稱EX),其主要思想是重點(diǎn)強(qiáng)
23、調(diào)了對(duì)父 代巡回路線上的邊之間的鄰接關(guān)系的遺傳,它考慮了旅行商問(wèn)題性狀的遺傳特點(diǎn);啟發(fā)式雜交,選擇由現(xiàn)行城市出發(fā)的不構(gòu)成循環(huán)的最短邊。4.1.5 變異算子旅行商問(wèn)題對(duì)變異算子的設(shè)計(jì)要求是:對(duì)任意一個(gè)個(gè)體編碼串進(jìn)行變異操作后,所產(chǎn)生的新個(gè)體應(yīng)該能夠?qū)?yīng)于一條具有實(shí)際意義的巡回路線。針對(duì)TSP問(wèn)題,變異算子主要包括位點(diǎn)變異、 逆轉(zhuǎn)變異( inversion mutation )、插入變異( insertion mutation )、 移位變異(displacement mutation )、互換變異(s) 等。(1)位點(diǎn)變異: 變異僅以一定的概率(通常較?。?duì)串的某些位作值的變異。(2)逆轉(zhuǎn)變異:
24、 逆轉(zhuǎn)變異是先在父體中隨機(jī)地選擇兩截?cái)帱c(diǎn),然后將該兩點(diǎn)所夾 的子串中的城市進(jìn)行反序。( 3)插入變異: 插入變異是隨機(jī)選擇一個(gè)城市,并將它插入到一個(gè)隨機(jī)的位置中。(4) 移位變異: 移位變異是隨機(jī)選擇一子路徑,并將其插入到一個(gè)隨機(jī)的位置中。( 5)互換變異: 也稱基于次序的變異( order-based mutation ),它是隨機(jī)地選 擇兩個(gè)位置,并將這兩個(gè)位置上的城市相互交換。其它還有一些變異算子:基于位置的變異( position-based mutation )是隨機(jī)選 擇兩城市,將第二個(gè)城市放在第一個(gè)之前;打亂變異(scramble mutation )是隨機(jī)選擇一子路徑, 打亂其
25、次序, 重新插入; 啟發(fā)式變異采用了鄰域技術(shù), 以獲得后代的改進(jìn), 即對(duì)于一個(gè)染色體按它的鄰域交換不多于 個(gè)基因, 可獲得一族染色體, 選擇其中最好 的一個(gè)作為變異產(chǎn)生的后代。對(duì)于變異操作還有一些變體形式,如 Sushil J.Louis 提出的貪心對(duì)換變異 (greedy-s)9 ,其基本思想是從一個(gè)染色體中隨機(jī)的選擇兩個(gè)城市(即兩個(gè)碼值 ) ,然后交換它們, 得到新的染色體, 以旅程長(zhǎng)度為依據(jù)比較交換后的染色體與原來(lái)的染色體 的大小,保留旅程長(zhǎng)度值小的染色體。這種算子實(shí)際上是互換變異算子的改進(jìn)算子。求解TSP問(wèn)題時(shí),變異算子的設(shè)計(jì)要比雜交算子的設(shè)計(jì)靈活的多,任何具有局部搜 索功能的算子都可
26、以作為它的變異算子。4.2 算法設(shè)計(jì)基于以上理論,本人先采用經(jīng)典的遺傳算法理論及個(gè)體整數(shù)編碼方法設(shè)計(jì)了算法。但從算法的實(shí)現(xiàn)結(jié)果分析發(fā)現(xiàn), 算法的運(yùn)行結(jié)果雖然得到了相對(duì)最優(yōu)解,但是當(dāng)群體規(guī) 模較大時(shí), 算法在運(yùn)行過(guò)程中出現(xiàn)了局部早熟的現(xiàn)象。所以本人對(duì)算子的選取進(jìn)行了改 進(jìn)重組,重新設(shè)計(jì)了各個(gè)算子,試圖進(jìn)一步探索TSP組合優(yōu)化問(wèn)題的有效解決方案。4.2.1 編碼在求解TSP問(wèn)題的各種遺傳算法中,多采用以遍歷城市的次序排列進(jìn)行編碼的方法, 本文也采用這種最自然的編碼方式,即以 n 個(gè)城市的遍歷次序作為遺傳算法的編碼。每 一個(gè)解的碼串形如:Vi,V2,, Vn,其中,Vi表示遍歷城市的序號(hào)。程序中的解
27、定義為一維數(shù)組A(N) , N表示TSP問(wèn)題中的城市數(shù)目,數(shù)組中的各個(gè)元素A(i)(i 1,2, , ,N)的取值為1至N間的整數(shù),分別表示城市的序號(hào),根據(jù)問(wèn)題的約束條件,每一整數(shù)內(nèi)的 各元素值互不相同。4.2.2 初始群體 在遺傳算法中,初始群體一般是隨機(jī)產(chǎn)生的,通過(guò)種群的進(jìn)化最終達(dá)到最優(yōu)值。但在實(shí) 際操作時(shí),這樣進(jìn)化的速度太慢,且進(jìn)化效果往往不太好。因此,本人對(duì)初始種群的選 取方式做了改進(jìn)。在這里,初始群體也是隨機(jī)產(chǎn)生的,但所不同的是這里的隨機(jī)是有一 定前提條件的。具體操作是:設(shè)群體規(guī)模是 popsize ,首先用貪婪法( Greedy Method ) 產(chǎn)生n (nvpopsize )個(gè)
28、個(gè)體,這n個(gè)個(gè)體的起點(diǎn)城市分別是 1,2,n,再隨機(jī)產(chǎn)生剩 余的城市個(gè)體。 貪婪法是將每一步都取局部最優(yōu)的求解方法,這種用貪婪法產(chǎn)生的個(gè)體 在一定程度上具有有效的基因模式,有利于提高尋優(yōu)能力。在次算法中,隨機(jī)生成規(guī)模為 popsize 的初始群體, n 取為城市個(gè)數(shù) lchrom 。4.2.3 適應(yīng)度函數(shù)由于本算法在可行解群體的初始化、 交叉操作及變異操作中均隱含 TSP問(wèn)題的合法性 約束條件(即對(duì)所有城市要做到不重不漏),故適應(yīng)度函數(shù)取為哈密頓圈(Hamilton )的長(zhǎng)度的倒數(shù)(無(wú)懲罰函數(shù)) 5,21 。用路徑倒數(shù)作為適應(yīng)值是 Glodberg.D.E. 首先提出的 4 。適應(yīng)度函數(shù)取路徑
29、長(zhǎng)度(即哈密頓圈長(zhǎng))Td 的倒數(shù),即Fitness(i ) 1/Td (i)其中 Td(i) 表示第 i 個(gè)解所表示的遍歷城市的路徑長(zhǎng)度,即: 1 111),(),()(jnnjjdvvdvvdiT 4.2.4 選擇算子 遺傳算法采用的選擇算子一般有賭輪 法、最優(yōu)保存方法和期望值選擇方法等。賭輪選擇個(gè)體的方法是,先把群體中的每個(gè)個(gè) 體的適應(yīng)值按比例轉(zhuǎn)化為選中概率 ip ,將輪盤(pán)分成 popsize 個(gè)扇區(qū);產(chǎn)生一個(gè) 0,1 之 間的隨機(jī)數(shù) r ,如果從第一個(gè)個(gè)體的選中概率開(kāi)始累加, 直到累加概率之和 iq 大于或等 于 r ,則將最后一個(gè)被累加選中概率的個(gè)體挑選出來(lái),并復(fù)制到子代中。隨著遺傳算
30、法 的執(zhí)行,我們始終保留 popsize 個(gè)較優(yōu)的個(gè)體作為樣本群體,以供選擇。但是對(duì)于賭輪 選擇算子,由于是隨機(jī)操作的原因,這種選擇方法的選擇誤差比較大,有時(shí)甚至連適應(yīng) 度較高的個(gè)體也選擇不上。 遺傳算法的理論已經(jīng)證明了賭輪法選擇算子不能收斂到全局 最優(yōu)解, 而最優(yōu)保存方法相比之下則能收斂到全局最優(yōu)解。 遺傳算法中一個(gè)要求解決 的問(wèn)題是如何防止“早熟”收斂現(xiàn)象。 為了保證遺傳算法的全局收斂性,就要維持群體 中個(gè)體的多樣性,避免有效基因的丟失。因此,作為改進(jìn),本文將引入最優(yōu)選擇策略即 保持群體中最好的個(gè)體不丟失, 以保證算法的收斂性。 采用最優(yōu)保存選擇方法的優(yōu)點(diǎn) 是,進(jìn)化過(guò)程中某一代的最優(yōu)解可不
31、被交叉和變異操作所破壞。但是,這也隱含了一種 危機(jī),即如果只選用最優(yōu)選擇策略,則局部最優(yōu)個(gè)體的遺傳基因會(huì)急速增加而使進(jìn)化有 可能限于局部解。所以此方法一般都與其它選擇方法結(jié)合使用 5 。因此,我改進(jìn)了遺 傳算法的選擇算子, 采用賭輪選擇策略和最優(yōu)保存策略相結(jié)合的方法。 本文所采用的 賭輪和最優(yōu)保存相結(jié)合的方法,具體描述如下: Stepl :求出 pop(t )中適應(yīng)度最大 的 1 個(gè)個(gè)體,記為 best ,將 best 作為下一代的個(gè)體,即最優(yōu)個(gè)體必遺傳到下一代中。 Step2 :令p(k)為個(gè)體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 個(gè)0,1 )中的均勻分布的隨機(jī)數(shù)ir,i=1,2, ,N-1,依次判斷這N-1個(gè)隨機(jī)數(shù),若q(k-1) vir vq(k),則選 個(gè)體 k 為下一代的個(gè)體。 4.2.5 交叉算子 算法思想:通過(guò)賭輪策略,從父代中選擇 兩個(gè)個(gè)體, 利用如下操作, 通過(guò)從一個(gè)親體中挑選一個(gè)城市子序列并保存另一個(gè)親體的 城市相對(duì)次序來(lái)構(gòu)造兩個(gè)新的個(gè)體,然后將這兩個(gè)新個(gè)體添加到子代中去?;诨蚱伪P蛟谇蠼釺SP問(wèn)題中的應(yīng)用21,本文采用了一種改進(jìn)的交叉
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 玉器買(mǎi)賣(mài)定金合同范例
- 勞動(dòng)合同范例簡(jiǎn)約版
- 美容院合伙人合同范例
- 醫(yī)療儀器維修合同范例
- 業(yè)務(wù)績(jī)效合同范例
- 跟多人合作合同范例
- 電力施工追加合同范例
- 空置房租裝修合同范例
- 建筑咨詢服務(wù)合同范例
- 聘用學(xué)員合同范例
- 玉溪大紅山鐵礦二期北采區(qū)采礦施工組織設(shè)計(jì)
- 必刷題2024六年級(jí)英語(yǔ)上冊(cè)語(yǔ)法規(guī)則專(zhuān)項(xiàng)專(zhuān)題訓(xùn)練(含答案)
- 2024新教科版四年級(jí)上冊(cè)科學(xué)知識(shí)點(diǎn)總結(jié)精簡(jiǎn)版
- 人工智能在礦產(chǎn)勘探中的應(yīng)用分析篇
- 中西文化鑒賞智慧樹(shù)知到答案2024年鄭州大學(xué)
- 2024國(guó)開(kāi)大學(xué)《經(jīng)濟(jì)學(xué)基礎(chǔ)》形考任務(wù)2答案
- 2024山東省招聘社區(qū)工作者試題及答案
- 14《答謝中書(shū)書(shū)》對(duì)比閱讀-2024-2025中考語(yǔ)文文言文閱讀專(zhuān)項(xiàng)訓(xùn)練(含答案)
- DL∕T 5494-2014 電力工程場(chǎng)地地震安全性評(píng)價(jià)規(guī)程
- 顱腦外傷病人的急救和護(hù)理
- 大型儲(chǔ)罐制作安裝施工方案
評(píng)論
0/150
提交評(píng)論