【正文】 ://部分匹配交叉 { partially_matched_crossover(parent1,parent2,child1,child2)。 case ID_ORDER_CROSSOVER ://順序交叉 { order_crossover(parent1,parent2,child1,child2)。 case ID_CYCLE_CROSSOVER ://循環(huán)交叉 { cycle_crossover(parent1,parent2,child1,child2)。 case { greed_crossover(parent1,parent2,child1,child2)。 default : break。本設(shè)計實現(xiàn)了三種變異：基于次序的變異，基于位置的變異，倒位變異。 chr) { switch (TempMutationStyle) { case ID_ORDER_MUTATION ://基于次 序的變異 { order_oriented_mutation(chr)。 case ID_POSITION_MUTATION ://基于位置的變異 { position_oriented_mutation(chr)。 case { reverse_mutation(chr)。 default : break。信息顯示模塊包括：計算結(jié)果模塊，算法運行時間模塊，所選遺傳算子模塊。城市總數(shù)信息是用戶設(shè)置的城市數(shù)目。 ? 算法運行時間模塊：包括算法啟動前時間，它是用 戶設(shè)置完城市，進行求解時刻的時間；算法結(jié)束時間，它是程序運行完成，正確輸出 TSP結(jié)果時刻的時間；算法耗費時間，它是進行遺傳算法求解 TSP時算法所消耗的時間。 具體的顯示如圖 ： 圖 各種信息顯示圖 設(shè)計中主要的類和函數(shù)的功能 1. Map類， DefaultMap類， RoundMap類 這三個類均為畫圖相關(guān)的類，其繼承關(guān)系為： 繼承 基類 繼承 圖 畫圖類繼承關(guān)系 其中， DefaultMap 類主要是與直角坐標地圖有關(guān)， RoundMap 類主要是與圓形地圖有關(guān)。 DefaultMap 類 Map 類 RoundMap 類 2. CGA類 這個類主要是為遺傳算法設(shè)置的，在這個類中定義了基因結(jié)構(gòu)體代表一個城市，染色體結(jié)構(gòu)體代表到各城市去的一種組合，還定義了種群結(jié)構(gòu)體表示各種不同基因的組合。這個類中的主要函數(shù)有：遺傳算法參數(shù)設(shè)置函數(shù)： preSet，遺傳算法啟動函數(shù)： start，交叉類型選擇函數(shù)： SetCrossoverStyle，變異類型選擇函數(shù)： Set MutationStyle，世代進化函數(shù)： generation，染色體適應(yīng)度計算函數(shù)： chromCost，種群個體 適應(yīng)度計算函數(shù)： popCost，初始化染色體函數(shù)： initChrom，初始化種群函數(shù)： initpop，輪盤賭選擇函數(shù)： selectChrom等等。它提供的函數(shù)主要有：歡迎窗口顯示函數(shù)： wele，遺傳算法接口函數(shù)： SetGaInformation，信息顯示函數(shù)： DisPlay等等。 5. 這是一個主程序文件，是整個程序啟動，操作的主控文件。 此外，程序還有頭文件類，資源類等等。 5 軟件測試及實驗結(jié)果分析 軟件測試 以下是軟件測試的步驟： ，彈出歡迎消息，如圖 ： 圖 遺傳算法解 TSP問題歡迎窗口 ，進入主程 序模塊，點擊選擇地圖，可以選擇直角坐標地圖和圓形地圖，默認地圖為直角坐標地圖，下面的演示以直角坐標地圖為主，如圖 ： 圖 遺傳算法解 TSP問題直角坐標演示地圖 3. 在屏幕上點擊鼠標左鍵可設(shè)置城市，也可以點擊菜單欄設(shè)置城市，彈出設(shè)置城市數(shù)目對話框，在對話框中輸入城市數(shù)目，可以在屏幕上隨機生成城市，具體情況如圖 ，： 圖 設(shè)置城市數(shù)目 圖 設(shè)置城市 4. 點擊菜單欄遺傳算法 設(shè)置按鈕，彈出遺傳算法參數(shù) 設(shè)置對話框，如圖 ： 圖 遺傳算法參數(shù)設(shè) 置對話框 在遺傳算法參數(shù)設(shè)置對話框中，可以設(shè)置交叉率，變異率，種群大小，世代數(shù)以及選擇進化設(shè)置等。 6. 點擊菜單欄變異類 型按鈕，可以選擇變異算法，如圖 ，可供選擇的變異類型有：基于次序的變異，基于位置 的變異，倒位變異。至于圓形地圖的測試過程與直角坐標地圖相似。其中，城市的數(shù)目，坐標和最優(yōu)解均可以參照國內(nèi)外專家的文獻，然后對比本程序計算的結(jié)果。測試的十組數(shù)據(jù)如下： 時間 (s) 72 28 8 65 88 44 50 44 87 54 最優(yōu)解 517 492 505 515 492 509 519 526 549 491 計算平均值有平均最優(yōu)解為： ，平均時間為： 。由于本設(shè)計使用的是強制進化方式，所以平均最優(yōu)解和平均時間均有一定的改進。其中， TSP旅程長度為屏幕上象素點之間的距離，時間為算法所消耗的 CPU時間。 表 各種遺傳操作組合求解 TSP問題模擬實驗結(jié)果比較 算法 最佳解 時間 (s) 算法 最佳解 時間 (s) GA0 GA6 GA1 GA7 GA2 GA8 GA3 GA9 GA4 GA10 GA5 GA11 實驗結(jié)果分析 由表 ： GA1與 GA2以及 GA3與 GA4與 GA5， GA6與 GA7與 GA8， GA9與 GA10與 GA11的優(yōu)化結(jié)果無大的差異， 這說明變異算子在優(yōu)化過程中所起的作用相對小一些 。這也符合自然進化的規(guī)律，畢竟，變異的發(fā)生概率是極其微小的。也就是說，循環(huán)了一周，子代和父代卻沒有大的改變。 (循環(huán)貪心交叉 )和其它算子作比較可知，雖然改進的交叉算子所求的旅程長度有一定的改觀，但耗費了不少時間。因此對于改進的交叉算子不宜處理太多城市的 TSP問題。 改進算法與原算法的比較 對于下面各比較算法，分別進行了計算機模擬實驗，計算中采用的有關(guān)數(shù)據(jù)如下：城市數(shù)為 30，群體規(guī)模為 100，交叉概率為 ，變異概率為 ，群體更新 100代結(jié)束，采用強制進化方式進化，每個算法采集了 10組數(shù)據(jù)。 30個城市的坐標如表 ： 表 30個城市坐標 城市編號 坐標 城市編號 坐標 城市編號 坐標 1 (87,7) 11 (58,69) 21 (4,50) 2 (91,83) 12 (54,62) 22 (13,40) 3 (83,46) 13 (51,67) 23 (18,40) 4 (71,44) 14 (37,84) 24 (24,42) 5 (64,60) 15 (41,94) 25 (25,38) 6 (68,58) 16 (2,99) 26 (41,26) 7 (83,69) 17 (7,64) 27 (45,21) 8 (87,76) 18 (22,60) 28 (44,35) 9 (74,78) 19 (25,62) 29 (58,35) 10 (71,71) 10 (18,54) 30 (62,32) 改進循環(huán)交叉算法與循環(huán)交叉算法的數(shù)值比較 對于循環(huán)交叉測試的十組數(shù)據(jù)如下： 時間 (s) 72 28 8 65 88 44 50 44 87 54 最優(yōu)解 684 717 705 715 692 709 669 676 689 691 對于改進的循環(huán)交叉測試的十組數(shù)據(jù)如下： 時間 (s) 69 03 28 65 88 44 50 44 87 54 最優(yōu)解 615 621 640 632 609 651 603 621 630 612 對于循環(huán)交叉平均最優(yōu)解為： ，平均時間為： 。通過對比可知，改進后的算法明顯優(yōu)于改進前的算法。對于循環(huán)貪心交叉平均最優(yōu)解為： ，平均時間為： 。主要是減少了隨機查找數(shù)據(jù)的時間，但由于改進后的算法是循環(huán)查找未擴展的城市，因 此使得種群的多樣性減少了，即使得平均最優(yōu)解要比改進前差一些，但對于大量城市的 TSP問題來說，節(jié)省時間是很值得考慮的。 TSP搜索空間隨著城市數(shù)的增加而增大，在龐大的空間中尋找最優(yōu)解，對于現(xiàn)有的常規(guī)方法和現(xiàn)有的計算工具而言，存在著諸多的困難。本設(shè)計在深入分析和研究遺傳算法基本理論與方法的基礎(chǔ)上，不但編程實現(xiàn)了國內(nèi)外專家提出的一些優(yōu)秀的算法 ，而且結(jié)合具體的編程情況，對其中的一些算法作了必要的改進 。 在本文研究基礎(chǔ)上，還可以進一步開拓以下幾個方向的研究工作 : ； (如印制電路板的鉆孔路線方案、連鎖店的貨物陪送路線等 )建模為 TSP問題，并應(yīng)用遺傳算法來解決； 。 遺傳算法是新發(fā)展起來的一門學(xué)科，各種理論、方法尚未成熟，需要進一步地發(fā)展和完善，但它已為解決許多復(fù)雜問題提供了希望。隨著研究工作的進一步深入和發(fā)展，遺傳算法必將在智能計算領(lǐng)域中起到關(guān)鍵的作用。//命名空間 ///////////////////////////////////////////////////////////////////////////// 三 ．地圖類 ////////////////pragma once include //////////////////MapControl 控制地圖以及左右鍵點擊后對的處理 /////////////// class Map { public: virtual void DrawMap(HWND hwnd,HDC hdc)=0。//保存格式為地圖中的位置 virtual void DelAllPoint()=0。)=0。)=0。)=0。)=0。 protected: POINT beginpoint。//地圖中的位置 }。 _val):val(_val) { } bool operator()(const POINTamp。amp。 } bool operator()(const POINTamp。 point2) { return (==)amp。(==)。 }。//畫地圖 //void SaveClickPoint( )。//清除 vecpoin 所有點 //在地圖上畫點 (參數(shù)為實際位置 ) void DrawPonit(HWND hwnd,const POINTamp。 //將地圖上已存在的點 (參數(shù)為實際位置 )刪除 void SmearPonit(HWND hwnd,const POINTamp。 void AddPoint(const POINTamp。//保存 POINT(參數(shù)為實際位置 )到向量 void SubPoint(const POINTamp。//刪除 POINT(參數(shù)為實際位置 )到向量 //獲得所有已點擊的點的位置 (實際值 ) vectorPOINT GetAllClickPoint( )。 point)。 point)。 point,int iarea)。 ///////////////////////////////////////////////////////////////////////////// //////////////////////////include /////////////////////畫地圖 ////////////////////////////////////////////////// void DefaultMap::DrawMap(HWND hwnd,HDC hdc ) { HPEN hpen。 ///創(chuàng)建畫筆 SelectObject(hdc,hpen)。 x DIVISIONS1 。 y DIVISIONS2 。 } DeleteObject(hpen)。 } ///////////////////////////////////////////////////////////////////////////// //////////////////////保存刪除 POINT(在地圖位置 )到向量 //////////////////////// /*void DefaultMap::SaveClickPoint() { fstream outFile( , ios_base::out )。 return 。 } outFil