實驗五用遺傳算法解決旅行商問題

--好好學習，每天向上--2試驗五：用遺傳算法解決旅行商問題MPI編寫一個并行程序，利用遺傳算法來解決旅行商問題。旅行商問題概述旅行商問題，即TSP問題〔TravelingSalesmanProblem〕是數(shù)學領域中著名問題之一。假設有一個旅行商人要訪問N個城市，他必需選擇所要走的路徑，路徑的限制是每個城市只能訪問一次，而且最終要回到原來動身的城市。路徑的選擇目標是要求得的路徑路程為全部路徑之中的最小值。旅行商問題可以歸納為查找加權(quán)圖中的最短回路問題。TSPNP問題，我們無法對該問題查找多項式時間算法，因此只能構(gòu)造一些啟發(fā)式近似算法來求得問題的較優(yōu)解。在這里，我們承受遺傳算法來找出近似最正確路徑。遺傳算法概述〔GeneticAlgorithm〕是模擬達爾文的遺傳選擇和自然淘汰的生物進化過程的計算模型，是一種通過模擬自然進化過程搜尋最優(yōu)解的方法。遺傳算法是從代表問題可能潛在的解集的一個種群〔population〕開頭的，而一個種群則由經(jīng)過基因〔gene〕編碼的肯定數(shù)目的個體(individual)組成。每個個體實際上是染色體(chromosome)帶有特征的實體。染色體作為遺傳物質(zhì)的主要載體，即多個基因的集合，其內(nèi)部表現(xiàn)〔即基因型〕是某種基因組合，它打算了個體的外形的外部表現(xiàn)。初代種群產(chǎn)生之后，依據(jù)適者生存和優(yōu)勝劣汰的原理，逐代〔generation〕〔fitness〕selection〔genetic進展組合穿插crossove〕和變異〔mutatio，產(chǎn)生出代表的解集的種群。這個過程將導致種群像自然進化一樣的后生代種群比前代更加適應于環(huán)境，末代種群中的最優(yōu)個體經(jīng)過解碼〔decoding，可以作為問題近似最優(yōu)解。遺傳算法并行化MPI進展并行化程序設計。三．實現(xiàn)方法設計思路程序開頭初始化種群進化完畢？Y程序開頭初始化種群進化完畢？YN輸出最優(yōu)解突變進程完畢進化次數(shù)是 10的倍數(shù)？Y給其它進程N接收其它進程發(fā)來的個體產(chǎn)生下一代種群--好好學習，每天向上--3圖3-1 每個進程的根本流程實現(xiàn)細節(jié)種群：每個種群由一個鏈表表示，每個結(jié)點表示一個個體，個體的構(gòu)造如下：structgroup_member{intorder[node_num+1]; //首元素記錄回路的路徑長度，1為起始結(jié)點group_member*pointer;}存儲空間，操作敏捷，缺點在于與數(shù)組相比其訪問速度較慢。適應度：長度越短，其適應度就越強。的設計承受由DavisOX另一個親體的城市相對次序來構(gòu)造后代。例如，兩個親體〔|”標記par=〔123|4567|89〕1par=〔452|1876|93〕2將依據(jù)下面的方式產(chǎn)生后代。首先，切割點之間的片段被拷貝到后代里：chd=〔xxx|4567|xx〕1chd=〔xxx|1876|xx〕2o

4、5、671 2 12—1—8—9—3chd中：1chd

=〔218|4567|93〕1相像地，我們可以得到另一個后代：chd

=〔234|1876|59〕2〔不是它們的位置〕是重要的，即兩個旅行5—1—7—8—9—4—6—2—38—9—4—6—2—3—5—1—7--好好學習，每天向上--5是一樣的。的設計將兩點間的子串反轉(zhuǎn)。說明如下：原個體：〔123456789〕隨機選擇兩點：〔12|3456|789〕倒置后的個體：〔12|6543|789〕四．結(jié)果分析運行結(jié)果如下所示：4-1第一次運行結(jié)果4-2其次次運行結(jié)果4-3