實(shí)驗(yàn)五用遺傳算法解決旅行商問(wèn)題

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

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

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

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