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

《遺傳算法及其在tsp問題中的應(yīng)用》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

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

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

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

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

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

6、的啟發(fā)式隨機搜索算法。早在1983年，就有學(xué)者用GA求解組合優(yōu)化中著名的TSP問題[5]。Wetzel、Brady、Grefenstette等人都曾用遺傳算子來討論TSP問題[6,7,8]。實踐也證明，遺傳算法對于組合優(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問題已被廣泛地用于評價不同的遺傳操作及選擇機制的性能[14,15]。TSP問題的提出最早可追溯到18世紀(jì)的歐拉時代，但直到20司世紀(jì)中葉才由于優(yōu)化技術(shù)的興起逐漸為人所認識而著名。1948年，由美國蘭德公司推動，TSP成為近代組合優(yōu)化領(lǐng)域的一個典型難題。它是一個具有廣泛應(yīng)用背景和重要理論價值的組合優(yōu)化問題。TSP的搜索空間隨著城市規(guī)模數(shù)n的增加而增大，這類組合優(yōu)化問題稱之為NP完全問題[16]。3.1TSP問題的數(shù)學(xué)模型TSP問題可以簡單地描述成：一名旅行商從一個城市