TSP問題的遺傳算法求解方案--源程序清單旅行商問題包含算法介紹源程序測(cè)試結(jié)果講課講稿

1、Good is good, but better carries it.精益求精，善益求善。TSP問題的遺傳算法求解方案-源程序清單旅行商問題，包含算法介紹，源程序，測(cè)試結(jié)果-TSP問題的遺傳算法求解方案算法的軟件實(shí)現(xiàn)4.1開發(fā)環(huán)境介紹本文中的所有算法是在VisualC+6.0的操作平臺(tái)上進(jìn)行開發(fā)的，并結(jié)合STL進(jìn)行編程。1、VisualC+6.0簡(jiǎn)介VisualC+6.0是微軟公司最新出品的功能最為強(qiáng)大的可視化開放工具，是計(jì)算機(jī)界公認(rèn)的最優(yōu)秀的應(yīng)用開發(fā)工具之一。Microsoft的基本類庫使得開發(fā)Windows應(yīng)用程序比以往任何時(shí)候都要容易。VisualC+作為一種程序設(shè)計(jì)語言，它同時(shí)也是一

2、個(gè)集成開發(fā)工具，提供了軟件代碼自動(dòng)生成和可視化的資源編輯功能。2、VisualC+6.0的優(yōu)勢(shì)(1).擁有強(qiáng)大的編輯環(huán)境。(2).擁有強(qiáng)大的類庫的支持。(3).擁有強(qiáng)大的調(diào)試環(huán)境。(4).擁有較強(qiáng)的低層控制能力。(5).擁有強(qiáng)大的幫助系統(tǒng)MSDN的支持。(6).擁有一個(gè)高效的編譯器，產(chǎn)生的可執(zhí)行文件體積小巧、運(yùn)行速度快。3、STL簡(jiǎn)介STL（StandardTemplateLibrary），即標(biāo)準(zhǔn)模板庫，是一個(gè)具有工業(yè)強(qiáng)度的，高效的C+程序庫。它被容納于C+標(biāo)準(zhǔn)程序庫（C+StandardLibrary）中，是ANSI/ISOC+標(biāo)準(zhǔn)中最新的也是極具革命性的一部分。該庫包含了諸多在計(jì)算機(jī)科學(xué)領(lǐng)

3、域里所常用的基本數(shù)據(jù)結(jié)構(gòu)和基本算法。為廣大C+程序員們提供了一個(gè)可擴(kuò)展的應(yīng)用框架，高度體現(xiàn)了軟件的可復(fù)用性。這種現(xiàn)象有些類似于MicrosoftVisualC+中的MFC（MicrosoftFoundationClassLibrary），或者是BorlandC+Builder中的VCL(VisualComponentLibrary)，但是它比二者具有更強(qiáng)的優(yōu)勢(shì)。更加值得一提的是，它具備以下幾個(gè)區(qū)別于其它軟件庫的優(yōu)點(diǎn)：(1).經(jīng)過類屬編程方法精心組織的，可互換的編程模塊能夠提供比傳統(tǒng)組件設(shè)開始初始化遺傳算法的相關(guān)參數(shù)計(jì)算每個(gè)個(gè)體的適應(yīng)值產(chǎn)生城市對(duì)城市進(jìn)行編碼是否符合終止條件？輸出正確的TSP結(jié)果

4、是GEN=GEN+1選擇交叉變異否世代進(jìn)化輪盤賭選擇普通選擇GXCXOXPMX基于次序的變異基于位置的變異倒位變異圖4.1遺傳算法解TSP的具體流程圖計(jì)方法豐富得多的組合方式。(2).類屬編程方法設(shè)計(jì)也是將來為數(shù)據(jù)庫，用戶界面等專業(yè)領(lǐng)域開發(fā)組件的基礎(chǔ)。(3).通過使用某些編譯機(jī)制并根據(jù)不同的算法進(jìn)行具體的設(shè)計(jì)，可以在不損失效率的情況下實(shí)現(xiàn)對(duì)組件的概括。與此形成鮮明對(duì)照的是，其它一些具有復(fù)雜繼承層次和大量使用虛函數(shù)的C+庫結(jié)構(gòu)則通常會(huì)降低效率。4.2算法實(shí)現(xiàn)的流程圖本設(shè)計(jì)的具體流程圖如圖4.1所示：4.3算法的各個(gè)模塊及其詳細(xì)設(shè)計(jì)思路1城市生成模塊用戶可以點(diǎn)擊鼠標(biāo)左鍵產(chǎn)生城市，也可以選擇菜單欄的

5、設(shè)置城市選項(xiàng)，通過輸入城市數(shù)目來隨機(jī)生成城市。當(dāng)然，如果用戶選擇錯(cuò)了城市，可以在該城市上點(diǎn)擊鼠標(biāo)右鍵來清除城市。如果用戶要清除所有的城市，可以雙擊鼠標(biāo)右鍵或選擇菜單欄的結(jié)束選項(xiàng)，都可以清除所有的城市。其設(shè)計(jì)設(shè)計(jì)思路如圖4.2所示：調(diào)用畫圖函數(shù)畫點(diǎn)(即設(shè)置城市)程序?qū)Ⅻc(diǎn)的信息存入一個(gè)點(diǎn)向量中程序檢測(cè)鼠標(biāo)移動(dòng)的具體信息按下鼠標(biāo)左鍵用一個(gè)變量記入要產(chǎn)生的城市數(shù)按下鼠標(biāo)右鍵選擇菜單欄的設(shè)置城市選項(xiàng)將點(diǎn)向量中要除去的點(diǎn)找出來循環(huán)調(diào)用鼠標(biāo)左鍵點(diǎn)擊消息直到達(dá)到要求的城市數(shù)選擇菜單欄的結(jié)束選項(xiàng)重新畫點(diǎn)向量中的所有點(diǎn)(此時(shí)該刪除的點(diǎn)已從點(diǎn)向量中刪除)重新畫地圖(即清除了所有的點(diǎn))圖4.2城市生成模塊的設(shè)計(jì)思路最

6、后的效果如圖4.3所示：圖4.3TSP問題城市設(shè)置實(shí)現(xiàn)效果2.地圖選擇模塊根據(jù)具體的需要，用戶可以選擇不同的地圖，本設(shè)計(jì)提供的地圖有：基于直角坐標(biāo)系的地圖和圓形地圖，這兩個(gè)地圖由不同的類來產(chǎn)生。其中類DefaultMap產(chǎn)生直角坐標(biāo)地圖，類RoundMap產(chǎn)生圓形地圖。圖4.4所示的是直角坐標(biāo)地圖，圖4.5所示的是圓形地圖。圖4.4直角坐標(biāo)地圖圖4.5圓形地圖3.遺傳算法解TSP的參數(shù)設(shè)置模塊在具體的應(yīng)用中，用戶可以根據(jù)具體情況來設(shè)置遺傳算法的相關(guān)參數(shù)，這些參數(shù)包括：交叉率：控制程序進(jìn)行交叉的次數(shù)，在本設(shè)計(jì)中，先隨機(jī)生成一個(gè)數(shù)，如果這個(gè)數(shù)大于交叉率，則不交叉，如果這個(gè)數(shù)小于交叉率，則進(jìn)行交叉。

7、具體實(shí)現(xiàn)如下：pick=float(randomInt(0,1000)/1000;if(pickpcross)/進(jìn)行交叉操作else/不進(jìn)行交叉操作變異率：控制程序進(jìn)行變異的次數(shù)，在本設(shè)計(jì)中，先隨機(jī)生成一個(gè)數(shù)，如果這個(gè)數(shù)大于變異率，則不變異，如果這個(gè)數(shù)小于變異率，則進(jìn)行變異操作。具體實(shí)現(xiàn)如下：pick=float(randomInt(0,1000)/1000;if(pickpmutation)/進(jìn)行變異操作else/不進(jìn)行變異操作種群大?。杭捶N群中所含有的個(gè)體數(shù)量，選擇一個(gè)合理的種群值，不但會(huì)使得群體的多樣性增強(qiáng)，防止遺傳算法的“早熟現(xiàn)象”，還會(huì)使得遺傳操作收斂得更快。世代數(shù)：控制遺傳操作世代

8、進(jìn)化的次數(shù)，合理的世代數(shù)能夠使得計(jì)算結(jié)果的優(yōu)劣程度不同。圖4.6遺傳算法解TSP的參數(shù)設(shè)置進(jìn)化設(shè)置：根據(jù)子染色體與父染色體的關(guān)系，進(jìn)化設(shè)置又分為兩種：普通進(jìn)化：完全模仿自然進(jìn)化，子染色體可能比父染色體優(yōu)秀，也可能比父染色體差。強(qiáng)制進(jìn)化：選取子染色體中比父染色體優(yōu)秀的染色體，殺死子染色體中比父染色體差的染色體。使得進(jìn)化一直朝著優(yōu)秀染色體的方向進(jìn)化。具體的實(shí)現(xiàn)效果如圖4.6所示：4.交叉算子選擇模塊交叉操作是遺傳算法中最重要的一環(huán)，交叉算法的優(yōu)劣將最大限度地影響遺傳算法的結(jié)果。本設(shè)計(jì)先根據(jù)國外專家提出的解TSP的幾種經(jīng)典算法，然后編程將其實(shí)現(xiàn)，并在此基礎(chǔ)上，提出一種改進(jìn)的交叉算法。在具體的應(yīng)用中，

9、用戶可以根據(jù)自己的需要，選擇最符合實(shí)際情況的交叉算法。程序的具體選擇模塊如下：/交叉算子的選擇模塊inlinevoidCGA:crossover(Chrom&parent1,Chrom&parent2,Chrom&child1,Chrom&child2)switch(TempCrossoverStyle)caseID_PARTIALLY_MATCHED_CROSSOVER:/部分匹配交叉partially_matched_crossover(parent1,parent2,child1,child2);break;caseID_ORDER_CROSSOVER:/順序交叉order_crosso

10、ver(parent1,parent2,child1,child2);break;caseID_CYCLE_CROSSOVER:/循環(huán)交叉cycle_crossover(parent1,parent2,child1,child2);break;caseID_GREED_CROSSOVER:/循環(huán)貪心交叉greed_crossover(parent1,parent2,child1,child2);break;default:break;5.變異算子選擇模塊求解TSP時(shí)，變異算子的設(shè)計(jì)比交叉算子的設(shè)計(jì)靈活，任何具有局部搜索能力的算子都可以作為它的變異算子。本設(shè)計(jì)實(shí)現(xiàn)了三種變異：基于次序的變異，基于

11、位置的變異，倒位變異。程序的具體選擇模塊如下：/變異算子選擇模塊inlinevoidCGA:mutation(Chrom&chr)switch(TempMutationStyle)caseID_ORDER_MUTATION:/基于次序的變異order_oriented_mutation(chr);break;caseID_POSITION_MUTATION:/基于位置的變異position_oriented_mutation(chr);break;caseID_REVERSE_MUTATION:/倒位變異reverse_mutation(chr);break;default:break;6.具

12、體輸出信息顯示模塊為了使程序運(yùn)行時(shí)具體的算法和各種數(shù)據(jù)信息更加明確化，增加了信息顯示模塊，這樣，在程序運(yùn)行時(shí)用戶可以掌握具體的數(shù)據(jù)信息，以便對(duì)各種算法進(jìn)行比較。信息顯示模塊包括：計(jì)算結(jié)果模塊，算法運(yùn)行時(shí)間模塊，所選遺傳算子模塊。下面分別對(duì)各個(gè)顯示模塊進(jìn)行討論：計(jì)算結(jié)果模塊：輸出的信息包括當(dāng)前鼠標(biāo)的橫坐標(biāo)，當(dāng)前鼠標(biāo)的縱坐標(biāo)，這兩個(gè)信息是為了用戶設(shè)置城市時(shí)參考的。城市總數(shù)信息是用戶設(shè)置的城市數(shù)目?？偩嚯x信息是經(jīng)過計(jì)算的TSP問題的最優(yōu)路徑長度，它是屏幕上象素點(diǎn)間的距離。算法運(yùn)行時(shí)間模塊：包括算法啟動(dòng)前時(shí)間，它是用戶設(shè)置完城市，進(jìn)行求解時(shí)刻的時(shí)間；算法結(jié)束時(shí)間，它是程序運(yùn)行完成，正確輸出TSP結(jié)果時(shí)

13、刻的時(shí)間；算法耗費(fèi)時(shí)間，它是進(jìn)行遺傳算法求解TSP時(shí)算法所消耗的時(shí)間。所選遺傳算子模塊：它顯示的是用戶選擇了那種交叉算子，那種遺傳算子，以便于對(duì)各種算法比較時(shí)使用。具體的顯示如圖4.7所示：圖4.7各種信息顯示圖4.4設(shè)計(jì)中主要的類和函數(shù)的功能1.Map類，DefaultMap類，RoundMap類DefaultMap類這三個(gè)類均為畫圖相關(guān)的類，其繼承關(guān)系為：繼承Map類基類RoundMap類繼承圖4.8畫圖類繼承關(guān)系其中，DefaultMap類主要是與直角坐標(biāo)地圖有關(guān)，RoundMap類主要是與圓形地圖有關(guān)。這些類提供了畫地圖函數(shù)：DrawMap，保存地圖中的位置函數(shù)：SaveClickPo

14、int，清除點(diǎn)向量中所有城市點(diǎn)的函數(shù)：DelAllPoint，在地圖上畫點(diǎn)的函數(shù)：DrawPonit，將地圖上已存在的點(diǎn)刪除函數(shù)：SmearPonit等等。2.CGA類這個(gè)類主要是為遺傳算法設(shè)置的，在這個(gè)類中定義了基因結(jié)構(gòu)體代表一個(gè)城市，染色體結(jié)構(gòu)體代表到各城市去的一種組合，還定義了種群結(jié)構(gòu)體表示各種不同基因的組合。這個(gè)類主要是進(jìn)行遺傳算法操作的，包括各種進(jìn)化運(yùn)算，即選擇，交叉，變異等等。這個(gè)類中的主要函數(shù)有：遺傳算法參數(shù)設(shè)置函數(shù)：preSet，遺傳算法啟動(dòng)函數(shù)：start，交叉類型選擇函數(shù)：SetCrossoverStyle，變異類型選擇函數(shù)：Set-MutationStyle，世代進(jìn)化函數(shù)

15、：generation，染色體適應(yīng)度計(jì)算函數(shù)：chromCost，種群個(gè)體適應(yīng)度計(jì)算函數(shù)：popCost，初始化染色體函數(shù)：initChrom，初始化種群函數(shù)：initpop，輪盤賭選擇函數(shù)：selectChrom等等。3.Control類Control類主要是對(duì)程序進(jìn)行控制的，它為各個(gè)模塊的組合提供了接口，并且將必要的數(shù)據(jù)信息在屏幕上輸出。它提供的函數(shù)主要有：歡迎窗口顯示函數(shù)：welcome，遺傳算法接口函數(shù)：SetGaInformation，信息顯示函數(shù)：DisPlay等等。4.Line類Line類主要是計(jì)算TSP問題的具體操作，包括對(duì)城市點(diǎn)構(gòu)成矩陣的設(shè)置，計(jì)算城市點(diǎn)之間的距離，畫線，保存

16、城市點(diǎn)的矩陣信息，計(jì)算最終結(jié)果等。5.main.cpp這是一個(gè)主程序文件，是整個(gè)程序啟動(dòng)，操作的主控文件。是整個(gè)程序的框架部分。此外，程序還有頭文件類，資源類等等。這里就不詳細(xì)介紹，具體的源程序見程序文檔。5軟件測(cè)試及實(shí)驗(yàn)結(jié)果分析5.1軟件測(cè)試以下是軟件測(cè)試的步驟：1.運(yùn)行程序后，彈出歡迎消息，如圖5.1所示：圖5.1遺傳算法解TSP問題歡迎窗口2.點(diǎn)擊確定，進(jìn)入主程序模塊，點(diǎn)擊選擇地圖，可以選擇直角坐標(biāo)地圖和圓形地圖，默認(rèn)地圖為直角坐標(biāo)地圖，下面的演示以直角坐標(biāo)地圖為主，如圖5.2所示：圖5.2遺傳算法解TSP問題直角坐標(biāo)演示地圖3.在屏幕上點(diǎn)擊鼠標(biāo)左鍵可設(shè)置城市，也可以點(diǎn)擊菜單欄設(shè)置城市，

17、彈出設(shè)置城市數(shù)目對(duì)話框，在對(duì)話框中輸入城市數(shù)目，可以在屏幕上隨機(jī)生成城市，具體情況如圖5.3，5.4所示：圖5.3設(shè)置城市數(shù)目圖5.4設(shè)置城市4.點(diǎn)擊菜單欄遺傳算法設(shè)置按鈕，彈出遺傳算法參數(shù)設(shè)置對(duì)話框，如圖5.5所示：圖5.5遺傳算法參數(shù)設(shè)置對(duì)話框在遺傳算法參數(shù)設(shè)置對(duì)話框中，可以設(shè)置交叉率，變異率，種群大小，世代數(shù)以及選擇進(jìn)化設(shè)置等。5.點(diǎn)擊菜單欄交叉類型按鈕，可以選擇交叉算法，如圖5.6所示：圖5.6交叉類型選擇可供選擇的交叉類型有：部分匹配交叉，順序交叉，循環(huán)交叉，循環(huán)貪心交叉。6.點(diǎn)擊菜單欄變異類型按鈕，可以選擇變異算法，如圖5.7所示，可供選擇的變異類型有：基于次序的變異，基于位置的變

18、異，倒位變異。圖5.7變異類型選擇7然后點(diǎn)擊菜單欄開始，則進(jìn)行計(jì)算，最終結(jié)果如圖5.8所示：圖5.8遺傳算法解TSP問題計(jì)算結(jié)果8.點(diǎn)擊菜單欄結(jié)束可以清除所有點(diǎn)，點(diǎn)擊幫助，可以彈出幫助文件。至于圓形地圖的測(cè)試過程與直角坐標(biāo)地圖相似。5.2算法的正確性驗(yàn)證為了測(cè)試算法的正確性，我使用了固定城市測(cè)試模塊，該模塊中的城市坐標(biāo)，城市大小可以預(yù)先設(shè)置。其中，城市的數(shù)目，坐標(biāo)和最優(yōu)解均可以參照國內(nèi)外專家的文獻(xiàn)，然后對(duì)比本程序計(jì)算的結(jié)果。如圖5.9所示：圖5.9固定城市測(cè)試本設(shè)計(jì)中的參考文獻(xiàn)可見參考文獻(xiàn)1，城市坐標(biāo)見參考文獻(xiàn)1，36，交叉率為0.6，變異率為0.2，種群大小為100，世代數(shù)為100，采用強(qiáng)制

19、進(jìn)化方式，交叉類型為部分匹配交叉，變異類型為基于次序的變異。測(cè)試的十組數(shù)據(jù)如下：時(shí)間(s)12.67211.82812.7811.76512.68812.84411.25010.84410.68711.954最優(yōu)解517492505515492509519526549491計(jì)算平均值有平均最優(yōu)解為：511.5，平均時(shí)間為：11.9364s。與參考文獻(xiàn)1，37的部分匹配交叉數(shù)據(jù)，平均最優(yōu)解為：517.0，平均時(shí)間為：31.2s對(duì)比可知，本設(shè)計(jì)的算法符合要求。由于本設(shè)計(jì)使用的是強(qiáng)制進(jìn)化方式，所以平均最優(yōu)解和平均時(shí)間均有一定的改進(jìn)。5.3模擬實(shí)驗(yàn)結(jié)果與分析5.3.1不同遺傳操作組合的算法為了考察遺傳

20、算法組合優(yōu)化在求解TSP問題中的重要性,本文進(jìn)行了多種遺傳操作組合的模擬實(shí)驗(yàn)，各種遺傳操作組合成的算法如下:GA0：部分匹配交叉+基于次序的變異GA1：部分匹配交叉+基于位置的變異GA2：部分匹配交叉+倒位變異GA3：順序交叉+基于次序的變異GA4：順序交叉+基于位置的變異GA5：順序交叉+倒位變異GA6：循環(huán)交叉+基于次序的變異GA7：循環(huán)交叉+基于位置的變異GA8：循環(huán)交叉+倒位變異GA9：循環(huán)貪心交叉+基于次序的變異GA10：循環(huán)貪心交叉+基于位置的變異GA11：循環(huán)貪心交叉+倒位變異表5.130個(gè)城市位置坐標(biāo)城市編號(hào)坐標(biāo)城市編號(hào)坐標(biāo)城市編號(hào)坐標(biāo)1(40,406)11(190,323)2

21、1(2,290)2(33,39)12(401,152)22(521,92)3(268,183)13(291,201)23(172,43)4(277,377)14(620,235)24(440,150)5(361,103)15(117,154)25(252,147)6(104,4)16(546,305)26(346,343)7(180,26)17(70,197)27(461,416)8(160,70)18(468,171)28(436,258)9(194,181)19(466,258)29(322,80)10(626,395)10(234,233)30(228,357)5.3.2模擬實(shí)驗(yàn)結(jié)果對(duì)于

22、上述各算法，分別進(jìn)行了計(jì)算機(jī)模擬實(shí)驗(yàn)，計(jì)算中采用的有關(guān)數(shù)據(jù)如下：城市數(shù)為30，群體規(guī)模為100，交叉概率為0.8，變異概率為0.1，群體更新100代結(jié)束，采用強(qiáng)制進(jìn)化方式進(jìn)化，每個(gè)算法采集了10組數(shù)據(jù)。其中，TSP旅程長度為屏幕上象素點(diǎn)之間的距離，時(shí)間為算法所消耗的CPU時(shí)間。30個(gè)城市的坐標(biāo)如表5.1所示：對(duì)每個(gè)算法采集的數(shù)據(jù)，計(jì)算其平均結(jié)果，表5.2中的所有數(shù)據(jù)都是經(jīng)過10次測(cè)試得出的統(tǒng)計(jì)平均結(jié)果。表5.2各種遺傳操作組合求解TSP問題模擬實(shí)驗(yàn)結(jié)果比較算法最佳解時(shí)間(s)算法最佳解時(shí)間(s)GA02698.419.266GA62947.223.234GA12682.118.110GA729

23、18.619.250GA22675.918.234GA82903.919.360GA32524.816.125GA92521.624.695GA42524.316.187GA102523.924.685GA52523.516.309GA112522.723.8565.3.3實(shí)驗(yàn)結(jié)果分析由表5.2可見：1.GA0與GA1與GA2以及GA3與GA4與GA5，GA6與GA7與GA8，GA9與GA10與GA11的優(yōu)化結(jié)果無大的差異，這說明變異算子在優(yōu)化過程中所起的作用相對(duì)小一些。事實(shí)上，幾種算法結(jié)果的相對(duì)一致性,很大程度上是變異概率取的較小,使變異在整個(gè)搜索過程中發(fā)生次數(shù)甚微造成的。這也符合自然進(jìn)化的

24、規(guī)律，畢竟，變異的發(fā)生概率是極其微小的。2.排除變異算子所帶來的差異，只比較交叉算子可知，循環(huán)交叉算子的效果最差，這主要是因?yàn)榻?jīng)過循環(huán)之后，有可能到最后才完成循環(huán)。也就是說，循環(huán)了一周，子代和父代卻沒有大的改變。但由于進(jìn)行了一系列循環(huán)，耗費(fèi)了不少時(shí)間，因此，循環(huán)交叉所花費(fèi)的時(shí)間也比較多。3.通過改進(jìn)的交叉算子(循環(huán)貪心交叉)和其它算子作比較可知，雖然改進(jìn)的交叉算子所求的旅程長度有一定的改觀，但耗費(fèi)了不少時(shí)間。這主要是因?yàn)楦倪M(jìn)的交叉算子不但要循環(huán)，還要比較相鄰城市之間的距離，并且所比較的城市都被擴(kuò)展時(shí)，還要隨機(jī)選擇一個(gè)城市直到它不在所擴(kuò)展的城市中或者所有的城市都被擴(kuò)展，因此花費(fèi)了大量的時(shí)間。因此

25、對(duì)于改進(jìn)的交叉算子不宜處理太多城市的TSP問題。4.總體來說，順序交叉比較穩(wěn)定，沒有太多隨機(jī)選擇的情況，因此，對(duì)于多城市問題，不失為一種較理想的選擇。5.4改進(jìn)算法與原算法的比較對(duì)于下面各比較算法，分別進(jìn)行了計(jì)算機(jī)模擬實(shí)驗(yàn)，計(jì)算中采用的有關(guān)數(shù)據(jù)如下：城市數(shù)為30，群體規(guī)模為100，交叉概率為0.6，變異概率為0.2，群體更新100代結(jié)束，采用強(qiáng)制進(jìn)化方式進(jìn)化，每個(gè)算法采集了10組數(shù)據(jù)。其中，TSP旅程長度為屏幕上象素點(diǎn)之間的距離，時(shí)間為算法所消耗的CPU時(shí)間。30個(gè)城市的坐標(biāo)如表5.3所示：表5.330個(gè)城市坐標(biāo)城市編號(hào)坐標(biāo)城市編號(hào)坐標(biāo)城市編號(hào)坐標(biāo)1(87,7)11(58,69)21(4,50

26、)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)5.4.1改進(jìn)循環(huán)交叉算法與循環(huán)交叉算法的數(shù)值比較對(duì)于循環(huán)交叉測(cè)試的十組數(shù)據(jù)如下：時(shí)間(s)15.67214.82814.7814.

27、76515.68816.84414.65015.84414.68715.954最優(yōu)解684717705715692709669676689691對(duì)于改進(jìn)的循環(huán)交叉測(cè)試的十組數(shù)據(jù)如下：時(shí)間(s)11.96911.70312.32811.76512.18812.84411.25011.84410.48710.954最優(yōu)解615621640632609651603621630612對(duì)于循環(huán)交叉平均最優(yōu)解為：694.7，平均時(shí)間為：15.3712s。對(duì)于改進(jìn)循環(huán)交叉平均最優(yōu)解為：623.4，平均時(shí)間為：11.7332s。通過對(duì)比可知，改進(jìn)后的算法明顯優(yōu)于改進(jìn)前的算法。5.4.2改進(jìn)循環(huán)貪心交叉算法與循

28、環(huán)貪心交叉算法的數(shù)值比較對(duì)于改進(jìn)的循環(huán)貪心交叉測(cè)試的十組數(shù)據(jù)如下：時(shí)間(s)12.68713.35912.9312.42212.50012.28112.93811.50012.85912.953最優(yōu)解610616643644655643590699613617對(duì)于循環(huán)貪心交叉測(cè)試的十組數(shù)據(jù)如下：時(shí)間(s)14.25013.62514.75014.17213.75014.50013.40614.31213.98514.734最優(yōu)解580614626594624651626570694586對(duì)于改進(jìn)的循環(huán)貪心交叉平均最優(yōu)解為：633.0，平均時(shí)間為：12.6429s。對(duì)于循環(huán)貪心交叉平均最優(yōu)解為：

29、616.5，平均時(shí)間為：14.1484s。通過對(duì)比可知，改進(jìn)后的算法時(shí)間上明顯優(yōu)于改進(jìn)前的算法。主要是減少了隨機(jī)查找數(shù)據(jù)的時(shí)間，但由于改進(jìn)后的算法是循環(huán)查找未擴(kuò)展的城市，因此使得種群的多樣性減少了，即使得平均最優(yōu)解要比改進(jìn)前差一些，但對(duì)于大量城市的TSP問題來說，節(jié)省時(shí)間是很值得考慮的。6結(jié)論TSP是一個(gè)具有廣泛的應(yīng)用背景和重要理論價(jià)值的組合優(yōu)化問題，它已經(jīng)被證明屬NP難題。TSP搜索空間隨著城市數(shù)的增加而增大，在龐大的空間中尋找最優(yōu)解，對(duì)于現(xiàn)有的常規(guī)方法和現(xiàn)有的計(jì)算工具而言，存在著諸多的困難。借助遺傳算法的搜索能力解決TSP問題是很自然的想法。本設(shè)計(jì)在深入分析和研究遺傳算法基本理論與方法的基

30、礎(chǔ)上，不但編程實(shí)現(xiàn)了國內(nèi)外專家提出的一些優(yōu)秀的算法，而且結(jié)合具體的編程情況，對(duì)其中的一些算法作了必要的改進(jìn)。最后，本設(shè)計(jì)對(duì)各種算法的組合進(jìn)行了實(shí)驗(yàn)，并且對(duì)各種算法結(jié)果進(jìn)行了比較和分析。在本文研究基礎(chǔ)上，還可以進(jìn)一步開拓以下幾個(gè)方向的研究工作:1.將遺傳算法運(yùn)用于大規(guī)模的旅行商問題；2.將許多實(shí)際應(yīng)用問題(如印制電路板的鉆孔路線方案、連鎖店的貨物陪送路線等)建模為TSP問題，并應(yīng)用遺傳算法來解決；3.如何獲得更好的性能是遺傳算法研究中的重要課題。如何在保證求解質(zhì)量的同時(shí)降低時(shí)間的開銷，如何針對(duì)具體問題尋找優(yōu)化的并行計(jì)算策略和群體劃分策略，也是遺傳算法中需要進(jìn)一步深入研究的重要課題。遺傳算法是新發(fā)

31、展起來的一門學(xué)科，各種理論、方法尚未成熟，需要進(jìn)一步地發(fā)展和完善，但它已為解決許多復(fù)雜問題提供了希望。盡管在遺傳算法的研究和應(yīng)用過程中會(huì)出現(xiàn)許多難題，同時(shí)也會(huì)產(chǎn)生許多不同的算法設(shè)計(jì)觀點(diǎn)，然而，目前遺傳算法的各種應(yīng)用實(shí)踐已經(jīng)展現(xiàn)出了其優(yōu)異的性能和巨大的發(fā)展?jié)摿Γ陌l(fā)展前景激勵(lì)著各類專業(yè)技術(shù)人員把遺傳算法的理論和方法運(yùn)用于自己的專業(yè)領(lǐng)域中。隨著研究工作的進(jìn)一步深入和發(fā)展，遺傳算法必將在智能計(jì)算領(lǐng)域中起到關(guān)鍵的作用。程序核心代碼一資源類1.頭文件/NO_DEPENDENCIES/MicrosoftDeveloperStudiogeneratedincludefile./Usedbyresource

32、.rc#defineIDDefault3#defineIDR_MENU1101#defineIDI_ICON1104#defineIDD_GA_BOX105#defineIDD_HELP_BOX106#defineIDD_SETCITY107#defineIDC_EDIT21002#defineIDC_EDIT31003#defineIDC_EDIT41004#defineIDC_EDIT61008#defineIDC_RADIO11019#defineIDC_RADIO21020#defineIDI_TSP1022#defineIDC_ICON11023#defineIDC_ICON2102

33、3#defineIDC_CITYNUMBER1025#defineID_GA_SET40012#defineID_DefaultMap40020#defineID_RoundMap40021#defineID_CUSTOMMAP40023#defineID_HELP_BOX40024#defineID_GASET40026#defineID_END40027#defineID_EXIT40028#defineID_ORDER_MUTATION40030#defineID_POSITION_MUTATION40031#defineID_REVERSE_MUTATION40032#defineID

34、_PARTIALLY_MATCHED_CROSSOVER40033#defineID_ORDER_CROSSOVER40034#defineID_CYCLE_CROSSOVER40035#defineID_SET_CITY40036#defineID_GREED_CROSSOVER40037#defineID_FIXED_CITY40038/Nextdefaultvaluesfornewobjects/#ifdefAPSTUDIO_INVOKED#ifndefAPSTUDIO_READONLY_SYMBOLS#define_APS_NEXT_RESOURCE_VALUE108#define_A

35、PS_NEXT_COMMAND_VALUE40039#define_APS_NEXT_CONTROL_VALUE1027#define_APS_NEXT_SYMED_VALUE101#endif#endif二頭文件類1.頭文件/head.h/#pragmaonce#include#include#include#include#include#include#include#include#include#include#include#include#includeusingnamespacestd;/命名空間/三地圖類1.頭文件/map.h/#pragmaonce#includehead.

36、h/MapControl控制地圖以及左右鍵點(diǎn)擊后對(duì)的處理/classMappublic:virtualvoidDrawMap(HWNDhwnd,HDChdc)=0;/畫地圖/virtualvoidSaveClickPoint()=0;/保存格式為地圖中的位置virtualvoidDelAllPoint()=0;/清除vecpoin所有點(diǎn)/在地圖上畫點(diǎn)（參數(shù)為實(shí)際位置）virtualvoidDrawPonit(HWNDhwnd,constPOINT&)=0;/將地圖上已存在的點(diǎn)（參數(shù)為實(shí)際位置）刪除virtualvoidSmearPonit(HWNDhwnd,constPOINT&)=0;/保存

37、POINT(參數(shù)為實(shí)際位置)到向量virtualvoidAddPoint(constPOINT&)=0;/刪除POINT(參數(shù)為實(shí)際位置)到向量virtualvoidSubPoint(constPOINT&)=0;/獲得所有已點(diǎn)擊的點(diǎn)的位置(實(shí)際值)virtualvectorGetAllClickPoint()=0;protected:POINTbeginpoint;/實(shí)際位置vectorvecpoint;/地圖中的位置;/函數(shù)對(duì)象/classequal_pointpublic:equal_point()equal_point(constPOINT&_val):val(_val)boolope

38、rator()(constPOINT&point)return(point.x=val.x)&(point.y=val.y);booloperator()(constPOINT&point1,constPOINT&point2)return(point1.x=point2.x)&(point1.y=point2.y);private:POINTval;/四直角坐標(biāo)地圖類1.頭文件/defaultmap.h/#pragmaonce#includemap.h#defineDIVISIONS110#defineDIVISIONS26classDefaultMap:publicMappublic:vo

39、idDrawMap(HWNDhwnd,HDChdc);/畫地圖/voidSaveClickPoint();/保存格式為地圖中的位置voidDelAllPoint();/清除vecpoin所有點(diǎn)/在地圖上畫點(diǎn)(參數(shù)為實(shí)際位置)voidDrawPonit(HWNDhwnd,constPOINT&);/將地圖上已存在的點(diǎn)(參數(shù)為實(shí)際位置)刪除voidSmearPonit(HWNDhwnd,constPOINT&);voidAddPoint(constPOINT&);/保存POINT(參數(shù)為實(shí)際位置)到向量voidSubPoint(constPOINT&);/刪除POINT(參數(shù)為實(shí)際位置)到向量/獲

40、得所有已點(diǎn)擊的點(diǎn)的位置(實(shí)際值)vectorGetAllClickPoint();POINTGetMapPoint(constPOINT&point);/實(shí)際POINT在地圖位置POINTGetRealPoint(constPOINT&point);/地圖POINT實(shí)際位置protected:/找到該點(diǎn)附近的像素點(diǎn)iarea為該點(diǎn)的半徑vectorFindAroundPoint(constPOINT&point,intiarea);/2.源文件/defaultmap.cpp/#includedefaultmap.h/畫地圖/voidDefaultMap:DrawMap(HWNDhwnd,HDC

41、hdc)HPENhpen;hpen=CreatePen(PS_SOLID,1,RGB(0,128,128);/創(chuàng)建畫筆SelectObject(hdc,hpen);for(intx=0;xDIVISIONS1;x+)/10for(inty=0;yDIVISIONS2;y+)/6Rectangle(hdc,5+x*70,50+y*70,5+(x+1)*70,50+(y+1)*70);DeleteObject(hpen);/刪除畫筆return;/保存刪除POINT(在地圖位置)到向量/*voidDefaultMap:SaveClickPoint()fstreamoutFile(copy.text

42、,ios_base:out);/以寫方式打開文件if(!outFile)cerrunabletoopeninputfile:-bailingout!n;return;if(vecpoint.size()=0)return;outFile#DEFAULT_MAP_NAMEn;/以后有用outFile#vecpoint.size()n;for(intn=0;nvecpoint.size();n+)outFilevecpointn.x;outFile;outFilevecpointn.y;outFilen;return;*/刪除所有點(diǎn)/voidDefaultMap:DelAllPoint()if(v

43、ecpoint.size()=0)return;vecpoint.clear();return;/找到該點(diǎn)附近的點(diǎn)/vectorDefaultMap:FindAroundPoint(constPOINT&point,intiarea)/iarea為該點(diǎn)的半徑POINTtemppoint;vectorvecroundpoint;temppoint.x=point.x-6;/判斷點(diǎn)是否在有效區(qū)域/-51temppoint.y=point.y-51;/-51if(temppoint.x0|temppoint.y700|temppoint.y420)returnvecroundpoint;iarea=

44、abs(iarea);/防止iarea小于零for(intn=-iarea;n-1-iarea;m-)temppoint.x=point.x+m;temppoint.y=point.y+n;vecroundpoint.push_back(temppoint);temppoint.x=point.x+n;temppoint.y=point.y+m;vecroundpoint.push_back(temppoint);returnvecroundpoint;/在地圖上畫點(diǎn)/在地圖上畫點(diǎn)(參數(shù)為實(shí)際位置)/voidDefaultMap:DrawPonit(HWNDhwnd,constPOINT&po

45、int)intcx=point.x-6;/判斷點(diǎn)是否在有效區(qū)域intcy=point.y-51;if(cx0|cy700|cy420)return;AddPoint(point);HDChdc;hdc=GetDC(hwnd);HPENhpen;hpen=CreatePen(PS_DOT,5,RGB(255,0,0);SelectObject(hdc,hpen);/選擇對(duì)象進(jìn)DCEllipse(hdc,point.x+2,point.y+2,point.x-2,point.y-2);/畫圓點(diǎn)DeleteObject(hpen);ReleaseDC(hwnd,hdc);return;/添加和減少點(diǎn)

46、(在地圖位置)到向量/保存POINT(參數(shù)為實(shí)際位置)到向量/voidDefaultMap:AddPoint(constPOINT&point)POINTtempoint=point;if(vecpoint.size()!=0&find_if(vecpoint.begin(),vecpoint.end(),equal_point(tempoint)!=vecpoint.end()return;/保證點(diǎn)不重復(fù)vecpoint.push_back(tempoint);/清除一個(gè)指定的點(diǎn)/voidDefaultMap:SubPoint(constPOINT&point)if(vecpoint.siz

47、e()=0)return;vectorvecroundpoint;vector:iteratorIter1;vecroundpoint=FindAroundPoint(point,2);/獲得該點(diǎn)附近的像素點(diǎn)if(vecroundpoint.size()=0)return;Iter1=find_first_of(vecpoint.begin(),vecpoint.end(),vecroundpoint.begin(),vecroundpoint.end(),equal_point();if(Iter1=vecpoint.end()return;vecpoint.erase(Iter1);/將地

48、圖上已存在的點(diǎn)(參數(shù)為實(shí)際位置)刪除/擦掉該點(diǎn)(重畫所有的點(diǎn)和地圖)/voidDefaultMap:SmearPonit(HWNDhwnd,constPOINT&point)HDChdc;hdc=GetDC(hwnd);intn=vecpoint.size();SubPoint(point);if(n=vecpoint.size()/沒找到則向量大小不變r(jià)eturn;DrawMap(hwnd,hdc);ReleaseDC(hwnd,hdc);for(n=0;nvecpoint.size();n+)/重畫所有的點(diǎn)和地圖DrawPonit(hwnd,vecpointn);return;/獲得所有已

49、點(diǎn)擊的點(diǎn)的位置/vectorDefaultMap:GetAllClickPoint()returnvecpoint;/將地圖與實(shí)際位置之間轉(zhuǎn)換/POINTDefaultMap:GetRealPoint(constPOINT&point)/實(shí)際位置轉(zhuǎn)換為地圖位置POINTtemppoint;temppoint.x=point.x-6;temppoint.y=point.y-51;/判斷點(diǎn)是否在有效區(qū)域if(temppoint.x0|temppoint.y700|temppoint.y420)temppoint.x=-1;temppoint.y=-1;returntemppoint;temppoi

50、nt.x+=6;temppoint.y+=51;returntemppoint;/地圖位置轉(zhuǎn)換為實(shí)際位置/POINTDefaultMap:GetMapPoint(constPOINT&point)POINTtemppoint=point;temppoint.x-=6;temppoint.y-=51;if(temppoint.x0|temppoint.y0|700temppoint.x|420temppoint.y)temppoint.x=-1;/點(diǎn)在無效區(qū)域temppoint.y=-1;returntemppoint;returntemppoint;/點(diǎn)在有效區(qū)域/五圓形坐標(biāo)地圖類1.頭文件/

51、roundmap.h/#pragmaonce#includemap.hclassRoundMap:publicMappublic:RoundMap();voidDrawMap(HWNDhwnd,HDChdc);/畫地圖POINTFindAroundPoint(constPOINT&);/voidSaveClickPoint();/保存格式為地圖中的位置voidDelAllPoint();/清除vecpoin所有點(diǎn)/在地圖上畫點(diǎn)(參數(shù)為實(shí)際位置)voidDrawPonit(HWNDhwnd,constPOINT&);/將地圖上已存在的點(diǎn)(參數(shù)為實(shí)際位置)刪除voidSmearPonit(HWND

52、hwnd,constPOINT&);voidAddPoint(constPOINT&);/保存POINT(參數(shù)為實(shí)際位置)到向量voidSubPoint(constPOINT&);/刪除POINT(參數(shù)為實(shí)際位置)到向量vectorGetAllClickPoint();/獲得所有已點(diǎn)擊的點(diǎn)的位置(實(shí)際值)protected:vectormappoint;/2.源文件/roundmap.cpp/#includeroundmap.h/圓形地圖/RoundMap:RoundMap()/doinitializationstuffherevectorpoint60(60);intiallpoint120

53、=305,-21,324,-23,344,-23,365,-19,384,-13,402,-6,421,4,437,16,454,28,468,41,482,57,493,74,503,93,509,113,515,132,518,152,520,173,518,193,514,214,510,233,501,254,493,271,481,287,468,304,456,318,439,329,422,342,284,-16,263,-12,246,-4,225,3,210,17,194,28,178,42,166,56,156,74,145,93,137,112,133,131,129,1

54、53,127,173,128,195,132,213,137,233,146,255,155,272,165,290,180,307,194,318,208,331,227,343,244,352,265,360,282,365,303,366,326,369,343,368,368,365,385,360,404,353;for(intn=0;n60;n+)point60n.x=iallpoint2*n;point60n.y=iallpoint2*n+1;for(n=0;n60;n+)point60n.x=point60n.x+21;point60n.y=point60n.y+81;mapp

55、oint=point60;/畫地圖/voidRoundMap:DrawMap(HWNDhwnd,HDChdc)/n表示線的條數(shù)RECTrect;rect.bottom=450;/無效區(qū)域（背景區(qū)域）rect.left=100;rect.right=740;rect.top=0;HBRUSHhbrush;/擦除背景區(qū)域hbrush=CreateSolidBrush(RGB(255,255,255);FillRect(hdc,&rect,hbrush);SelectObject(hdc,GetStockObject(BLACK_PEN);for(intn=0;n60;n+)Ellipse(hdc,

56、mappointn.x-5,mappointn.y-5,mappointn.x+5,mappointn.y+5);/保存刪除POINT（在地圖位置)到向量/*voidRoundMap:SaveClickPoint()fstreamoutFile(copy.text,ios_base:out);if(!outFile)cerrunabletoopeninputfile:-bailingout!n;return;if(vecpoint.size()=0)return;outFile#Round_Map_NAMEn;/以后有用outFile#vecpoint.size()n;for(intn=0;n

57、vecpoint.size();n+)outFilevecpointn.x;outFile;outFilevecpointn.y;outFilen;return;*/刪除所有的點(diǎn)/voidRoundMap:DelAllPoint()if(vecpoint.size()=0)return;vecpoint.clear();return;/找到該點(diǎn)是否有所在區(qū)域的值/POINTRoundMap:FindAroundPoint(constPOINT&point)vectorvecroundpoint;POINTtemppoint;vector:iteratorIter;for(intn=-3;n-4

58、;m-)temppoint.x=point.x+m;temppoint.y=point.y+n;vecroundpoint.push_back(temppoint);/獲得該點(diǎn)附近的點(diǎn)temppoint.x=point.x+n;temppoint.y=point.y+m;vecroundpoint.push_back(temppoint);/獲得該點(diǎn)附近的點(diǎn)Iter=find_first_of(mappoint.begin(),mappoint.end(),vecroundpoint.begin(),vecroundpoint.end(),equal_point();if(Iter=mappo

59、int.end()temppoint.x=-1;temppoint.y=-1;returntemppoint;return(*Iter);/在地圖上畫點(diǎn)或?qū)⒌攸c(diǎn)上以存在的點(diǎn)從地圖上刪除/voidRoundMap:DrawPonit(HWNDhwnd,constPOINT&point)/在地圖上畫點(diǎn)(參數(shù)為實(shí)際位置)/HDChdc;POINTtemppoint,Drawpoint;temppoint.x=-1;temppoint.y=-1;Drawpoint=FindAroundPoint(point);if(Drawpoint.x=temppoint.x&Drawpoint.y=temppoi

60、nt.y)return;AddPoint(point);hdc=GetDC(hwnd);HBRUSHhbrush=CreateSolidBrush(RGB(255,0,0);SelectObject(hdc,hbrush);Ellipse(hdc,(Drawpoint).x-5,(Drawpoint).y-5,(Drawpoint).x+5,(Drawpoint).y+5);DeleteObject(hbrush);ReleaseDC(hwnd,hdc);/將地圖上已存在的點(diǎn)（參數(shù)為實(shí)際位置）重畫/voidRoundMap:SmearPonit(HWNDhwnd,constPOINT&poin