遺傳算法求解tsp問題的計算機仿真畢業(yè)論文

1、<p>　　題目：遺傳算法求解旅行商問題的計算機仿真</p><p>　　遺傳算法求解TSP問題的計算機仿真</p><p><b>　　摘要</b></p><p>　　由于遺傳算法在整體搜索策略和優(yōu)化搜索方法上不依賴梯度信息或其他輔助知識，只需要影響搜索方向的目標(biāo)函數(shù)和相應(yīng)的適應(yīng)度函數(shù)，所以提供了一種求解復(fù)雜系統(tǒng)問題的通用框架，因

2、此遺傳算法廣泛應(yīng)用于數(shù)學(xué)問題、組合優(yōu)化、機械設(shè)計、人工智能等領(lǐng)域。</p><p>　　遺傳算法（Genetic Algorithms,簡稱GA）是模擬自然界生物自然選擇和進(jìn)化的機制而發(fā)展起來的一種高度并行、自適應(yīng)的隨機搜索算法。特別適合于求解傳統(tǒng)的搜索算法不好處理的復(fù)雜的最優(yōu)解問題。旅行商問題（Traveling Salesman Problem）就是要決定一條經(jīng)過路線中所有城市當(dāng)且僅當(dāng)一次且距離最短的路線，即

3、距離最短的Hamilton回路。旅行商問題是一個具有十分廣泛的實用背景和重要理論價值的組合優(yōu)化問題。目前求解TSP問題的主要方法有模擬退火算法、遺傳算法、Hopfield神經(jīng)網(wǎng)絡(luò)算法、啟發(fā)式搜索法、二叉樹描述算法。本文選用遺傳算法求解45個城市的TSP問題，基于Microsoft Visual C++環(huán)境,采用Grefenstette等提出的一種新的巡回路線編碼方法，變異算子采用了常規(guī)的基本位變異法，通過多組實驗和數(shù)據(jù)近似的求解出了45

4、個城市的最優(yōu)解，實現(xiàn)了計算機仿真求解TSP問題。</p><p>　　關(guān)鍵字：旅行商問題；遺傳算法；變異算法；編碼方式</p><p>　　The computer simulation of genetic algorithm to solve </p><p>　　TSP problem</p><p><b>　　Abstra

5、ct</b></p><p>　　Due to genetic algorithm on the overall search strategy and optimization search method does not depend on the gradient information or other auxiliary knowledge, only need to influence t

6、he search direction of the objective function and the corresponding fitness function, and so provides a generic framework for solving complicated system problem, so the genetic algorithm is widely used in mathematical pr

7、oblem, combinatorial optimization, mechanical design, artificial intelligence, etc </p><p>　　Genetic algorithm (based Algorithms, the GA) is mimic natural biological natural selection and evolution mechanism

8、 and developed a kind of highly parallel, adaptive random search algorithm. Particularly suitable for solving the traditional search algorithm is not good to deal with complex optimal solution of problem. Traveling Sales

9、man Problem ('ll Salesman Problem) is to determine a through route if and only if all cities in time and distance is the shortest route, the shortest distance of Hami</p><p>　　Key words: Traveling salesm

10、an problem. Genetic algorithm; Mutation algorithm; </p><p><b>　　1緒論</b></p><p>　　自20世紀(jì)60年代以來,一種模擬生物自然遺傳與進(jìn)化過程并將生物進(jìn)化原理、最優(yōu)化技術(shù)和計算機技術(shù)結(jié)合起來的優(yōu)化方法—遺傳算法（Genetic Algorithm,簡稱GA）被提出并得到廣泛研究，該算法特別

11、適用于處理傳統(tǒng)搜索方法難以解決的復(fù)雜和非線性問題，可以廣泛應(yīng)用于人工智能、機械設(shè)計、自適應(yīng)控制等領(lǐng)域。遺傳算法固有的并行性和并行計算的能力，使在搜索過程中不容易陷入局部最優(yōu)。即使在所定義的適應(yīng)度函數(shù)中是不連續(xù)的、不規(guī)則的情況下，也可以很大概率找到全局最優(yōu)解。采用自然進(jìn)化機制來表現(xiàn)復(fù)雜的現(xiàn)象，能夠快速可靠地解決求解非常困難的問題，非常適用于本課題涉及的TSP問題的求解與研究。</p><p>　　旅行商問題（Tra

12、veling Salesman Problem ,TSP）是一個非常經(jīng)典的組合優(yōu)化問題的NP難題，長期以來都沒有一個十分有效的算法來解決它，但TSP本身在許多領(lǐng)域有著重要的應(yīng)用，如連鎖店的貨物配送路線、計算機網(wǎng)絡(luò)路由器遍歷、印刷電路板的鉆孔路線等問題都可以建模為旅行商問題。TSP問題其實是“哈密頓回路問題”中的“哈密頓最短回路問題”。在本系統(tǒng)就是要應(yīng)用遺傳算法求解45個城市的TSP問題。因為遺傳算法本身是模擬生物自然選擇和遺傳的過程的，

13、所以用遺傳算法求解TSP最先要確定的是問題的建模，即如何用遺傳學(xué)的算子來表示旅行商問題中的變量。必需要非常的了解，并熟悉每一個遺傳學(xué)中的術(shù)語在遺傳學(xué)中的具體作用，然后應(yīng)用到求解具體問題當(dāng)中來。應(yīng)用遺傳算法求解旅行商問題最關(guān)鍵的是編碼方式、交叉、選擇、變異算子的設(shè)計，直接關(guān)系到算法能否求出最優(yōu)解或近似最優(yōu)解。所以要在編碼方式的確定上做好足夠的功夫，以確定程序求解的精確度。</p><p>　　本章主要論述本文所研究

14、的主要內(nèi)容，并對論文的章節(jié)結(jié)構(gòu)進(jìn)行規(guī)劃。</p><p><b>　　1.1 研究背景</b></p><p>　　旅行商問題（Traveling Salesman Problem, TSP）,也稱旅行推銷員問題，具體的數(shù)學(xué)模型可以這樣理解：現(xiàn)在給定以下幾個城市的位置，旅行商從其中的某一個城市出發(fā)，不重復(fù)地訪問其余的每一個城市，最后又返回到原出發(fā)點城市，要求找出這樣一

15、條路線，使旅行所付出的代價最小。雖然它是一個比較古老的問題，最早可以追溯到Euler提出的騎士旅行問題，但同時它也是一個新的問題，因為它的計算復(fù)雜度較高，雖然人們一直在嘗試用新的方法來改進(jìn)求解該問題的復(fù)雜度，但是這一類問題距今都沒有能找到一個有效的算法來解決。</p><p>　　TSP問題可以形式化描述為：設(shè)G=（V,A,D）是一個圖，其中V是n個頂點的集合，A是弧線或邊集,D=（）是與A關(guān)聯(lián)的距離或費用矩陣。

16、旅行商問題就是要解決一個最小回路問題，回路中所有頂點有且僅經(jīng)過一次。對于具有一個城市的旅行商問題，其可能的路徑數(shù)目為（n-1）！/2，5個城市的問題模型就對應(yīng)120/10=12條路線，10個城市的問題模型對應(yīng)3628800/20=181440條路線。所以當(dāng)輸入越大，則耗費的時間就是個天文數(shù)字了，因此旅行商問題至今都沒有能找到一種有效的求解方法。尋求一種能短時間求解出高精度解的算法，已成為此問題研究的熱門。盡管旅行商問題至今仍然沒有找到最

17、優(yōu)解，但求解它的算法已經(jīng)在不斷的改進(jìn)。目前，求解TSP問題常用的算法主要有遺傳算法和蟻群算法，另外還有爬山法、模擬退火算法、神經(jīng)網(wǎng)絡(luò)方法、貪婪算法、禁忌搜索算法等。1980Crowder和Padberg求解了318個城市的TSP問題；1987年P(guān)adberg和Rinaldi成功將城市數(shù)量增加到了2392個；最大的成功求解的旅行商問題已經(jīng)增加到24798個城市。</p><p><b>　　1.2研究意義

18、</b></p><p>　　首先旅行商問題是用于求解N個城市存在（N-1）條閉合路徑的排列方案，對于這一類問題很難用全局搜索法精確地求出最優(yōu)解，這一問題已經(jīng)困擾眾多學(xué)者許多年，因此研究相應(yīng)的算法尋找其最優(yōu)或近似最優(yōu)解是非常必要的。</p><p>　　其次，隨著旅游業(yè)的快速發(fā)展，大量的旅客在旅途中浪費了不必要的時間和金錢，而這些不必要的浪費完全可以通過對旅行路線的合理規(guī)劃來避

19、免。而在互聯(lián)網(wǎng)繼續(xù)擴大普及的時代，電子商務(wù)也迎來了期待已久的春天，同時物流產(chǎn)業(yè)也隨之水漲船高。毫無疑問，高效、低成本、低能耗成了各個物流企業(yè)追求的目標(biāo)，更加合理的配送路線能明顯地為物流公司增大利潤。再比如在裝配線的流程中，對每個工件為完成裝配過程節(jié)約的少許時間意味著一天的產(chǎn)量的相應(yīng)增加。由于旅行商問題在計算機網(wǎng)絡(luò)、物流、旅游業(yè)、交通運輸?shù)仍S多領(lǐng)域都有著十分廣泛的應(yīng)用，因此尋找一個求解這類問題的求解方法有很高的應(yīng)用價值</p>

20、<p>　　因此，對旅行商問題有效算法的研究不僅具有重要的理論意義，而且具有重大的實際應(yīng)用價值。</p><p><b>　　1.3研究內(nèi)容</b></p><p>　　本文采用遺傳算法求解45個城市的旅行商問題，并對其實現(xiàn)計算機仿真。遺傳算法（Genetic Algorithms,GA）又叫基因進(jìn)化算法或進(jìn)化算法，是一種通過模擬自然界生物適者生存、優(yōu)勝

21、劣汰的進(jìn)化過程而形成的一種自適應(yīng)、具有全局優(yōu)化能力的隨機搜索算法。應(yīng)用遺傳算法求解旅行商問題，最難得地方在于問題建模，如城市編碼方式以及交叉、變異、選擇算子的確定等。</p><p>　　本文采用的是Grefenstette等提出的一種新的巡回路線編碼方法，其可以在一定程度上克服常規(guī)巡回路線編碼方法在交異操作時易產(chǎn)生不滿足問題約束條件或無實際意義的巡回路線的缺點。交叉算法采用的是常規(guī)的單點交叉，之所以可以用這一常

22、規(guī)的交叉法，是因為在編碼方式上使用的是Grefenstette等提出的一種新的巡回路線編碼方法，它可以最大化交叉后后代與其父代的性狀差異，有利于算法的全局性。變異算法采用的是基本位變異法，即只是根據(jù)變異概率隨機改變?nèi)旧w中的某一段染色體，具體會在后文中做詳細(xì)說明。在遺傳算法中，以個體適應(yīng)度的大小來確定該個體被遺傳到下一代群體中的概率。本課題中以每條路徑長度的倒數(shù)作為適應(yīng)度函數(shù)值。在求出之后將其按照從大到小的順序排列，以便于后面找出路徑之

23、和最小的城市序列。</p><p><b>　　1.4 本文的結(jié)構(gòu)</b></p><p>　　本文一共分為5章，結(jié)構(gòu)如下：</p><p>　　第一章緒論。這一章主要論述旅行商問題的基本概念，以及本課題主要的研究方法及其研究意義，并對論文的章節(jié)結(jié)構(gòu)加以論述。</p><p>　　第二章遺傳算法理論概述。這一章主要論述遺

24、傳算法的起源發(fā)展及其實際應(yīng)用，重點介紹了遺傳算法的算法原理及步驟。</p><p>　　第三章基于遺傳算法求解TSP問題。本章主要介紹了本系統(tǒng)具體使用什么方式實現(xiàn)求解過程，包括編碼方式、選擇、交叉、變異算子的具體選取。</p><p>　　第四章45個城市旅行商問題的仿真軟件的設(shè)計。本章主要對系統(tǒng)模塊進(jìn)行了介紹，而且對應(yīng)用系統(tǒng)進(jìn)行了多組試算，最后得出結(jié)論。</p><p

25、>　　第五章結(jié)論。對本文的內(nèi)容進(jìn)行總結(jié)。</p><p>　　2 遺傳算法理論概述</p><p>　　2.1 遺傳算法的產(chǎn)生及發(fā)展</p><p>　　最早由美國Michigan(密執(zhí)安大學(xué))的Hollang教授提出，起源于60年代對自然和人工自適應(yīng)系統(tǒng)的研究。1967年，他的學(xué)生Bagley J.D.首次提出“遺傳算法”一詞，并發(fā)展了復(fù)制、交叉、變異、顯性

26、、倒位等遺傳算子。70年代De Jong基于遺傳算法的思想在計算機上進(jìn)行了大量純數(shù)值函數(shù)優(yōu)化計算實驗，建立了著名的De.Jong五函數(shù)測試平臺。在一系列研究工作的基礎(chǔ)上80年代Goldberg進(jìn)行總結(jié)歸納，形成了遺傳算法的基本框架；Smith將遺傳算法應(yīng)用于機械學(xué)習(xí)領(lǐng)域；Bethke對函數(shù)優(yōu)化的遺傳算法進(jìn)行了系統(tǒng)的研究。進(jìn)入90年代，遺傳算法進(jìn)入了興盛期，無論是理論研究還是實際應(yīng)用都成了十分熱門的課題。如今遺傳算法已經(jīng)被廣泛的應(yīng)用于計算

27、機科學(xué)、人工智能、機械設(shè)計、圖像處理等各個領(lǐng)域，不僅如此，利用遺傳算法進(jìn)行理論研究的優(yōu)化和最優(yōu)解問題的解決能力也顯著提高。</p><p>　　下面是一些在遺傳算法發(fā)展進(jìn)程中做出杰出貢獻(xiàn)的人物：</p><p>　　1 J.H.Holland</p><p>　　60年代提出在研究和設(shè)計人工自適應(yīng)系統(tǒng)時,可以借鑒生物遺傳的機制；</p><p&

28、gt;　　70年代初提出了遺傳算法的基本定理－模式定理(Schema Theorem)，從而奠定了遺傳算法的理論基礎(chǔ)；　</p><p>　　80年代實現(xiàn)了第一個基于遺傳算法的機器學(xué)系統(tǒng)－分類器系統(tǒng)(Classifier Systems),開創(chuàng)了基于遺傳算法的機器學(xué)習(xí)的新概念。</p><p>　　2 J.D.Bagley</p><p>　　1967年在其博士論

29、文中首次提出了：“遺傳算法”一詞，發(fā)展了復(fù)制、交叉、變異、顯性、倒位等遺傳算子，創(chuàng)立了自適應(yīng)遺傳算法的概念。</p><p>　　3 K.A.De Jong</p><p>　　1975年在其博士論文中結(jié)合模式定理進(jìn)行了大量的純數(shù)值函數(shù)優(yōu)化計算實驗，樹立了遺傳算法的工作框架，定義了評價遺傳算法性能的在線指標(biāo)和離線指標(biāo)。</p><p>　　4 D.J.Golgb

30、erg</p><p>　　1989年出版了專著《搜索、優(yōu)化和機器學(xué)習(xí)中的遺傳算法(Genetic Algorithms in Search，Optimization and Machine Learning)》，系統(tǒng)總結(jié)了遺傳算法的主要研究成果，全面而完整的論述了遺傳算法的基本原理及其應(yīng)用。</p><p>　　5 L.Davis</p><p>　　1991年

31、編輯出版了《遺傳算法手冊 (Handbook of Genetic Algorithms)》書中包括遺傳算法在科學(xué)計算、工程技術(shù)和社會經(jīng)濟中的大量應(yīng)用實例。</p><p><b>　　6J.R.Koza</b></p><p>　　1992年將遺傳算法應(yīng)用于計算機程序的優(yōu)化設(shè)計及自動生成，提出了遺傳編程 (Genetic Programming) 的概念，并成功的將

32、其提出的遺傳編程應(yīng)用于人工智能、機器學(xué)習(xí)符號處理等方面。</p><p>　　2.2 遺傳算法基本原理</p><p>　　遺傳算法是受大自然的啟發(fā)，模擬生物在自然環(huán)境中的遺傳和進(jìn)化過程而形成的一種自適應(yīng)、具有全局優(yōu)化能力的隨機搜索算法。</p><p>　　遺傳算法的思路是通過從給定一個初始群體出發(fā)，利用選擇算子、交叉算子以及變異算子來模擬自然進(jìn)化的三種原則，逐步

33、改進(jìn)種群，越來越逼近最優(yōu)解，以達(dá)到求解最優(yōu)化問題的目的。在遺傳算法中，種群中的每一個個體是問題的一個解，稱為“染色體”，染色體是一串符號，比如二進(jìn)制的01串。這些染色體在后續(xù)的迭代中不斷的進(jìn)化，稱為遺傳。在每一代中應(yīng)用適應(yīng)度（fitness）來測量染色體的優(yōu)越性，適應(yīng)度高的更容易在自然的選擇中存活下來。生存下來的染色體被稱為后代（offspring）。后代通常是前一代染色體通過交叉（crossover）或者變異（mutation ）形成

34、。新的下一代再重復(fù)根據(jù)適應(yīng)度選擇部分后代，淘汰一部分后代，這樣即可以保證種群染色體的優(yōu)越性，也保持了種群大小的穩(wěn)點性。遺傳算法中每一條染色體，對應(yīng)著遺傳算法的一個解決方案，一般我們用適應(yīng)性函數(shù)（fitness function）來衡量這個解決方案的優(yōu)劣。所以也可以把遺傳算法的過程看作是一個在多元函數(shù)里面求最優(yōu)解的過程。在這個多維曲面里面也有數(shù)不清的“山峰”，而這些最優(yōu)解所對應(yīng)的就是這些山峰，這些山峰就是局部最優(yōu)解。而其中也會有一個“山峰

35、”的海拔最高</p><p>　　下面給出生物學(xué)的幾個基本概念知識，這對于理解遺傳算法很重要：</p><p>　　1）遺傳因子（gene）:DNA長鏈結(jié)構(gòu)中占有一定位置的基本遺傳單位，也稱基因。生物的基因根據(jù)物種的不同而多少不一。</p><p>　　2）個體（individual）:指染色體帶有特征的實體。</p><p>　　3）種群（

36、population）:染色體帶有特征的個體的集合。</p><p>　　4）進(jìn)化（evolution）;生物在其延續(xù)生命的過程中，逐漸適應(yīng)其生存環(huán)境使得其品質(zhì)不斷得到改良，這種生命現(xiàn)象稱為進(jìn)化。生物的進(jìn)化是以種群的形式進(jìn)行的。</p><p>　　5）適應(yīng)度（fitness）:度量某個物種對于生存環(huán)境的適應(yīng)程度。</p><p>　　6）選擇（selection）

37、:指以一定的概率從種群中選擇若干個體的操作。</p><p>　　7）變異（musation）：復(fù)制時很小的概率產(chǎn)生的某些復(fù)制差錯。</p><p>　　8）編碼（coding）:DNA中遺傳信息在一個長鏈上按一定的模式排列，也即進(jìn)行了遺傳編碼。遺傳編碼可以看成是從表現(xiàn)型到遺傳子型的映射。</p><p>　　9）串（String）:它是個體的形式，在算法中為二進(jìn)制

38、串，并且對應(yīng)于遺傳學(xué)中的染色體。</p><p>　　10）串結(jié)構(gòu)空間（ss）：在串中，基因任意組合所構(gòu)成的串集合。基因操作是在結(jié)構(gòu)空間中進(jìn)行的。串結(jié)構(gòu)空間對應(yīng)用于遺傳學(xué)中的基因型的集合。</p><p>　　11）染色體：是生物細(xì)胞中含有的一種微小的絲狀化合物，是遺傳物質(zhì)的主要載體，由多個遺傳因子—基因組成。</p><p>　　2.3 遺傳算法基本步驟</

39、p><p>　　步驟一：編碼：把所需要選擇的群體進(jìn)行編號，每一個個體就是一條染色體，一個解就是一串基因的組合。</p><p>　　步驟二：初始化：隨機生成有N個個體的初始群體，這些個體一起組成了一個種群。遺傳算法就是以這個初始群體為起點開始迭代。參數(shù)N可以根據(jù)具體的情況而定。</p><p>　　步驟三：交叉算子：這是遺傳算法最重要的操作。所謂交叉是指把兩個父代個體的

40、部分結(jié)構(gòu)加以替換重組而生成新個體的操作。遺傳算法中起核心作用的就是交叉算子。</p><p>　　步驟四：適應(yīng)度：確定個體適應(yīng)度的量化評價方法，適應(yīng)度用于衡量種群中個體的優(yōu)劣性，是確定種群中個體留存的關(guān)鍵。</p><p>　　步驟五：選擇算子：選擇的目的是為了從交換后的群體中選出優(yōu)良的染色體攜帶者，使它們有機會作為父代繁殖出下一代群體。選擇操作是建立在適應(yīng)度之上的，適應(yīng)度高的被選中的幾率

41、就大，選擇操作體現(xiàn)出了生物適者生存的原則。</p><p>　　步驟六：變異算子：變異是根據(jù)生物遺傳中基因突變的原理，以變異概率對群體中的某一些個體的某些“位”執(zhí)行變異。變異操作可以保證算法過程中不會產(chǎn)生無法進(jìn)化的單一群體，避免算法早熟出現(xiàn)局部最優(yōu)。</p><p>　　步驟七：終止。給定最大的遺傳代數(shù)，算法在計算到最大的遺傳代數(shù)時，終止計算。</p><p>　　

42、2.4 遺傳算法算法流程圖</p><p>　　圖2-4遺傳算法算法流程圖</p><p>　　2.5 遺傳算法的特點</p><p>　　遺傳算法屬于進(jìn)化算法（Evolutionary Algorithms）的一種，它通過模仿自然界的選擇與遺傳的原理來求出最優(yōu)解，遺傳算法有三個最基本的算子：選擇、交叉、變異。數(shù)值方法求解這一問題的主要手段是迭代運算。一般的迭代方法

43、容易陷入局部極小的陷阱而出現(xiàn)“死循環(huán)”現(xiàn)象，使迭代無法進(jìn)行。遺傳算法很好地克服了這個缺點，是一種全局優(yōu)化算法。</p><p>　　遺傳算法與傳統(tǒng)的優(yōu)化方法（枚舉，啟發(fā)式等）相比較，以生物進(jìn)化為原型，具有很多的優(yōu)點。主要有以下幾點：</p><p>　?。?）遺傳算法的本質(zhì)并行性。首先，遺傳算法并行的方式是從問題解的串集開始搜索，而不是從單個解開始。這是遺傳算法與傳統(tǒng)優(yōu)化算法的最大區(qū)別。傳

44、統(tǒng)優(yōu)化算法從單個初始值迭代求最優(yōu)解，容易早熟陷入局部最優(yōu)解。遺傳算法從串集開始搜索，覆蓋面大，有利于全局最優(yōu)。其次，算法內(nèi)含并行性，遺傳算法采用種群方式組織搜索，因而可同時搜索解空間的多個區(qū)域，并相互交流信息，能以較小的計算獲得較大收益。</p><p>　　（2）遺傳算法求解時使用特定問題的信息極少，容易形成通用算法程序.僅用適應(yīng)度函數(shù)值來評估個體，在此基礎(chǔ)上進(jìn)行遺傳操作。適應(yīng)度函數(shù)不僅不受連續(xù)可微的約束，而且

45、其定義域可以任意的設(shè)定，故幾乎可處理任何問題。</p><p>　?。?）遺傳算法不是采用確定性規(guī)則，而是采用概率的變遷規(guī)則來指導(dǎo)它的搜索方向，具有自組織、自適應(yīng)和自學(xué)習(xí)性。遺傳算法利用進(jìn)化過程獲得信息自行組織搜索時，適應(yīng)度高的個體具有較高的生存率，并獲得更加適應(yīng)環(huán)境的染色體。這種通過自然選擇與進(jìn)化的機制消除了算法設(shè)計過程中的一個最大障礙，即需要事先描述問題的全部特點，并要說明針對所求問題的不同特點，我們設(shè)計的算

46、法應(yīng)該采用的具體措施。所以，遺傳算法有很高的容錯能力，我們可以利用遺傳算法解決復(fù)雜的非結(jié)構(gòu)化問題。</p><p>　?。?）遺傳算法可以直接用于實際應(yīng)用當(dāng)中，對于給定的問題，可以產(chǎn)生許多解，最終選擇是根據(jù)用戶自己的需求來選取，通用性高，實際應(yīng)用性強，應(yīng)用范圍廣。</p><p>　　2.6 遺傳算法的應(yīng)用</p><p>　　遺傳算法為求解復(fù)雜系統(tǒng)問題提供了一種通

47、用的算法框架，它不取決于問題的具體領(lǐng)域，有很強的魯棒性，因而被廣泛的使用于組合優(yōu)化、機械設(shè)計、人工智能、數(shù)學(xué)建模、軟件工程等領(lǐng)域。</p><p><b>　　（1）函數(shù)優(yōu)化</b></p><p>　　函數(shù)優(yōu)化是遺傳算法經(jīng)典的應(yīng)用領(lǐng)域，也是使用最頻繁的領(lǐng)域。尤其是在數(shù)學(xué)領(lǐng)域，科學(xué)家構(gòu)造出了許許多多復(fù)雜的測試函數(shù)：連續(xù)函數(shù)、離散函數(shù)、凸函數(shù)、凹函數(shù)、單峰函數(shù)、多峰函數(shù)

48、等等。對于這些非線性、求極值、多模型或多目標(biāo)的函數(shù)優(yōu)化問題，用傳統(tǒng)的優(yōu)化方法很難解決，而用遺傳算法可以方便地得到較好的結(jié)果。</p><p><b>　　（2）組合優(yōu)化</b></p><p>　　隨著變量n的不斷增大，問題的規(guī)模增大，組合優(yōu)化問題的求解空間也急劇增大，應(yīng)用傳統(tǒng)的枚舉法等就很難求出最優(yōu)解。對于這一類復(fù)雜的問題，遺傳算法已經(jīng)被證實是十分有效的求解方式。遺

49、傳算法已經(jīng)在求解TSP問題、01背包問題、圖形劃分問題等方面得到了成功的應(yīng)用。</p><p><b>　　(3)生產(chǎn)調(diào)度問題</b></p><p>　　生產(chǎn)調(diào)度問題在很多情況下建立起來的傳統(tǒng)數(shù)學(xué)模難以精確求解，雖然經(jīng)過一些簡化之后可以進(jìn)行求解.也會因簡化得太多而使得求解結(jié)果與實際相差太大。目前在現(xiàn)實生產(chǎn)中主要是靠一些經(jīng)驗來進(jìn)行調(diào)度?，F(xiàn)在遺傳算法已成為解決復(fù)雜調(diào)度問

50、題的有效措施。在單件生產(chǎn)車間調(diào)度、流水線生產(chǎn)間調(diào)度、生產(chǎn)規(guī)劃、任務(wù)分配等方面遺傳算法都得到了有效的應(yīng)用。</p><p><b>　?。?）機器人學(xué)</b></p><p>　　機器人是一類復(fù)雜的難以精確建模的人工系統(tǒng)，而遺傳算法的起源就來自于人工自適應(yīng)系統(tǒng)的研究。所以，機器人學(xué)理所當(dāng)然地成為遺傳算法的一個重要應(yīng)用領(lǐng)域。例如，遺傳算法已經(jīng)在移動機器人路徑規(guī)劃、關(guān)節(jié)機器

51、人運動軌跡規(guī)劃、機器人逆運動學(xué)求解、細(xì)胞機器人的結(jié)構(gòu)優(yōu)化和行為協(xié)調(diào)等方而得到研究和應(yīng)用。</p><p><b>　?。?）數(shù)據(jù)挖掘</b></p><p>　　數(shù)據(jù)挖掘是近幾年出現(xiàn)的數(shù)據(jù)庫技術(shù)，它能夠從大型數(shù)據(jù)庫中提取隱含的、先前未知的、有潛在應(yīng)用價值的知識和規(guī)則。許多數(shù)據(jù)挖掘問題可看成是搜索問題，數(shù)據(jù)庫看作是搜索空間，挖掘算法看作是搜索策略。因此，應(yīng)用遺傳算法在數(shù)

52、據(jù)庫中進(jìn)行搜索，對隨機產(chǎn)生的一組規(guī)則進(jìn)行進(jìn)化.直到數(shù)據(jù)庫能被該組規(guī)則覆蓋，從而挖掘出隱含在數(shù)據(jù)庫中的規(guī)則。Sunil已成功地開發(fā)了一個基于遺傳算法的數(shù)據(jù)挖掘下具。利用該工具對兩個飛機失事的真實數(shù)據(jù)庫進(jìn)行了數(shù)據(jù)挖掘?qū)嶒?，結(jié)果表明遺傳算法是進(jìn)行數(shù)據(jù)挖掘的有效方法之一。</p><p><b>　?。?）人工生命</b></p><p>　　人工生命是用計算機、機械等人工媒

53、體模擬或構(gòu)造出的具有自然生物系統(tǒng)特有行為的人造系統(tǒng)。自組織能力和自學(xué)習(xí)能力是人工生命的兩大主要特征。人工生命與遺傳算法有著密切的關(guān)系?；谶z傳算法的進(jìn)化模型是研究人工生命現(xiàn)象的重要基礎(chǔ)理論。雖然人工生命的研究尚處于啟蒙階段，但遺傳算法已在其進(jìn)化模型、學(xué)習(xí)模型、行為模型、自組織模型等方面顯示出了初步的應(yīng)用能力，并且必將得到更為深入的應(yīng)用和發(fā)展。人工生命與遺傳算法相輔相成，遺傳算法為人工生命的研究提供一個有效的工具，人工生命的研究也必將促進(jìn)

54、遺傳算法的進(jìn)一步發(fā)展。</p><p>　　3 基于遺傳算法求解TSP問題</p><p>　　3.1旅行商問題的描述與建模</p><p>　　旅行商問題，即TSP問題又譯為旅行推銷員問題，屬于NP完全問題，是數(shù)學(xué)領(lǐng)域中著名的問題之一。它可以大致描述為這樣：有一個旅行商人要拜訪n個城市，他必須要經(jīng)過所有的城市，而且每個城市只能拜訪一次，最后要回到原來出發(fā)的城市。要

55、求得的路徑路程為所有可能路徑之中的最小值，即最優(yōu)值問題。</p><p>　　可以用如下公式表達(dá):</p><p><b>　　n-1</b></p><p>　　f(T)= ∑d(ti,ti+1)+d(nt,t1)</p><p><b>　　i=1</b></p><p>

56、;　　本系統(tǒng)是用遺傳算法求解45個城市的旅行商問題，并對其進(jìn)行計算機仿真，做出一個能在計算機上運行的軟件。</p><p><b>　　3.2編碼方式</b></p><p>　　編碼是應(yīng)用遺傳算法時要解決的首要問題，也是設(shè)計遺傳算法時的一個關(guān)鍵步驟。因為編碼方法將會影響到交叉算子、變異算子等遺傳算子的運算方法，很大的程度上決定了遺傳進(jìn)化的效率。迄今為止人們已經(jīng)提出了

57、許多種不同的編碼方法。總的來說，這些編碼方法可以分為三大類：二進(jìn)制編碼法、浮點編碼法、符號編碼法。下面我們從具體實現(xiàn)角度出發(fā)介紹其中的幾種主要編碼方法。</p><p>　　1.二進(jìn)制編碼方法：</p><p>　　它由二進(jìn)制符號0和1所組成的二值符號集。它有以下一些優(yōu)點：</p><p>　　(1）編碼、解碼操作簡單易行</p><p>　

58、　(2)交叉、變異等遺傳操作便于實現(xiàn)</p><p>　　(3)符合最小字符集編碼原則</p><p>　　(4)利用模式定理對算法進(jìn)行理論分析。</p><p>　　二進(jìn)制編碼的缺點是：對于一些連續(xù)函數(shù)的優(yōu)化問題，由于其隨機性使得其局部搜索能力較差，如對于一些高精度的問題（如上題），當(dāng)解迫近于最優(yōu)解后，由于其變異后表現(xiàn)型變化很大，不連續(xù)，所以會遠(yuǎn)離最優(yōu)解，達(dá)不到穩(wěn)

59、定。而格雷碼能有效地防止這類現(xiàn)象。</p><p><b>　　2.浮點編碼法：</b></p><p>　　對于一些多維、高精度要求的連續(xù)函數(shù)優(yōu)化問題，使用二進(jìn)制編碼來表示個體時將會有一些不利之處。</p><p>　　二進(jìn)制編碼存在著連續(xù)函數(shù)離散化時的映射誤差。個體長度較知時，可能達(dá)不到精度要求，而個體編碼長度較長時，雖然能提高精度，但卻使

60、遺傳算法的搜索空間急劇擴大。</p><p>　　所謂浮點法，是指個體的每個基因值用某一范圍內(nèi)的一個浮點數(shù)來表示。在浮點數(shù)編碼方法中，必須保證基因值在給定的區(qū)間限制范圍內(nèi)，遺傳算法中所使用的交叉、變異等</p><p>　　遺傳算子也必須保證其運算結(jié)果所產(chǎn)生的新個體的基因值也在這個區(qū)間限制范圍內(nèi)。</p><p>　　浮點數(shù)編碼方法有下面幾個優(yōu)點：</p>

61、;<p>　　（1)適用于在遺傳算法中表示范圍較大的數(shù)</p><p>　?。?)適用于精度要求較高的遺傳算法</p><p>　?。?)便于較大空間的遺傳搜索</p><p>　?。?)改善了遺傳算法的計算復(fù)雜性，提高了運算交率</p><p>　?。?)便于遺傳算法與經(jīng)典優(yōu)化方法的混合使用</p><p&

62、gt;　?。?)便于設(shè)計針對問題的專門知識的知識型遺傳算子</p><p>　?。?)便于處理復(fù)雜的決策變量約束條件</p><p><b>　　3.符號編碼法：</b></p><p>　　符號編碼法是指個體染色體編碼串中的基因值取自一個無數(shù)值含義、而只有代碼含義的符號集如｛A,B,C…｝。</p><p>　　符號編

63、碼的主要優(yōu)點是：</p><p>　?。?)符合有意義積術(shù)塊編碼原則</p><p>　?。?)便于在遺傳算法中利用所求解問題的專門知識</p><p>　　（3)便于遺傳算法與相關(guān)近似算法之間的混合使用。</p><p>　　但對于使用符號編碼方法的遺傳算法，一般需要認(rèn)真設(shè)計交叉、變異等遺傳運算的操作方法，以滿足問題的各種約束需求，這樣才能

64、提高算法的搜索性能。</p><p>　　使用遺傳算法第一件事情就是確定染色編碼方式，它根據(jù)不同的問題模型使用不同的編碼方式，本系統(tǒng)使用的是Grefenstette等提出的一種新的巡回路線編碼方法，是一種整數(shù)編碼的方式。對于每個城市用一個整數(shù)來編號，例如有45個城市，就用0到45來標(biāo)識每一個城市，然后一個路徑就是一條染色體編碼，染色體長度為45，如：0,1,2,3,4...44就是一個染色體，它表達(dá)的意思就是旅行

65、者從0號城市出發(fā)，依次訪問1,2,...44號城市再回到0號城市；下面具體具體介紹一下這一種編碼方法。</p><p>　　對于給定的旅行商問題，設(shè)其城市列表W，假定對各個城市的訪問順序為T：</p><p>　　T=（T1，T2，T3，…..，Tn）</p><p>　　規(guī)定每訪問完一個城市，就從城市列表W中將該城市除去，則用第i（i=1,2,3……n）個所訪問的

66、城市Ti在所有未訪問城市列表W={T1，T2，T3，…..，Ti-1}中的對應(yīng)位置序號Gi（1≤Gi≤n-i+1）就可表示具體訪問哪個城市，如此這樣直到處理完W中所有的城市。將全部Gi順序排列在一起所得到的一個列表：</p><p>　　G=（G1，G2，G3，……，Gn）</p><p>　　這樣就可以表示一條巡回路線，它就是遺傳算法中的一個個體基因。例如，假設(shè)現(xiàn)在有這樣一個城市序列：&

67、lt;/p><p>　　W=(A,B,C,D,E,F,G,H,I,J)</p><p>　　有如下兩條巡回路線：</p><p>　　T1=(A,D,B,H,F,I,J,G,E,C)</p><p>　　T2=(B,C,A,D,E,J,H,I,F,G)</p><p>　　則按本系統(tǒng)所用的編碼方法，這兩條巡回路線可以編碼為

68、：</p><p>　　G1 =(1,3,1,5,3,4,4,3,2,1)</p><p>　　G2 =(2,2,1,1,1,5,3,3,1,1)</p><p>　　這種編碼方式的優(yōu)點在于任意的染色體都對應(yīng)一條有實際意義的巡回路線，因此可以使用常規(guī)的交叉算子對它進(jìn)行計算，有利于算法的實現(xiàn)。</p><p>　　3.3遺傳算子的設(shè)計（交叉、選

69、擇、變異）</p><p>　　3.3.1 交叉算子</p><p>　　交叉運算，一般指對兩個相互配對的染色體依據(jù)交叉概率 Pc 按某種方式相互交換其部分基因，從而形成兩個新的個體。交叉運算是遺傳算法區(qū)別于其他進(jìn)化算法的重要特征，它在遺傳算法中起關(guān)鍵作用，是產(chǎn)生新個體的主要方法。求解旅行商問題的遺傳算法的交叉算法主要有：部分匹配交叉（PMX）、循環(huán)交叉（CX）、次序交叉（OX）、線性次序

70、交叉（LOX）、邊重組交叉（EX）等。本系統(tǒng)使用的是常規(guī)的單點交叉算子。</p><p>　　由于在確定算法的編碼方式的過程中使用的是Grefenstette等提出的編碼方式，用這種編碼方式表示個體時，個體的基因型和表現(xiàn)型之間是一一對應(yīng)的，它使經(jīng)過運算之后得到的每一個基因型都是一條有實際意義的巡回路線。因此，就可以使用常規(guī)的單點交叉算子。使用單點交叉，即在個體的編碼串上隨機設(shè)置一個交叉點，然后在該點相互交換兩個配

71、對個體的部分染色體。產(chǎn)生下一代個體在使用Grefenstette等提出的編碼方式時，染色體編碼串前面的一些基因發(fā)生變化時，會對后面的基因值產(chǎn)生巨大的影響，產(chǎn)生的新的個體與上一代的性狀變化就會十分明顯，有利于整個算法跳出局部最優(yōu)解。如下是具體代碼：</p><p>　　for(i=0;i<m_CrossNum;i++)</p><p><b>　　{ </b>&

72、lt;/p><p>　　int nPos, temp=0;</p><p>　　int parent1=0; //父代基因1</p><p>　　int parent2=0; //父代基因2</p><p>　　parent1=RandomInt(0,m_nGroupSize-1); </p><p>

73、　　temp=RandomInt(0,m_nGroupSize-1);</p><p>　　if(parent1>temp) parent1=temp;</p><p>　　parent2=RandomInt(0,m_nGroupSize-1);</p><p>　　temp=RandomInt(0,m_nGroupSize-1);</p>&l

74、t;p>　　if(parent2>temp) parent2=temp; </p><p>　　//復(fù)制用于交叉的基因?qū)?lt;/p><p>　　PopNode pop1;</p><p>　　PopNode pop2;</p><p>　　pop1.CopyNode(&oldpop[parent1]);</p>

75、<p>　　pop2.CopyNode(&oldpop[parent2]);</p><p>　　// 基因序列中用于交叉的基因位</p><p>　　nPos=RandomInt(3,MAXCHROM-3); </p><p>　　pop1.CrossTwo(&pop2, nPos); </p><p>　　/

76、/交叉完成,保存結(jié)果</p><p>　　newpop[m_nGroupSize+2*i].CopyNode(&pop1);</p><p>　　newpop[m_nGroupSize+2*i+1].CopyNode(&pop2);</p><p>　　3.3.2 選擇算子</p><p>　　選擇操作是建立在對個體適應(yīng)度進(jìn)行

77、評價的基礎(chǔ)之上的。選擇操作的目的是為了避免基因缺失、提高全局收斂性和計算效率。本課題采用最常用的選擇算子——比例選擇算子（又稱輪盤賭選擇）。其基本思想是：各個個體被選中的概率與其適應(yīng)度大小成正比。適應(yīng)度越高的個體被選中的概率也越大；反之，適應(yīng)度越低的個體被選中的概率也越小。具體操作如下：</p><p>　　計算出群體中每個個體的適應(yīng)度f(i=1，2，…，M)，M為群體大??；</p><p&g

78、t;<b>　　歸一化適應(yīng)度f的值</b></p><p>　　將適應(yīng)度f的值從大到小排列，查找其中最小費用的個體然后將其作為下一代選擇出來。</p><p><b>　　具體代碼如下：</b></p><p>　　for(int gen=0;gen<m_GANum;gen++)</p><p&g

79、t;<b>　　{ </b></p><p>　　// 計算當(dāng)前一代群體中個體的適應(yīng)度數(shù)值F</p><p>　　for(int i=0;i<m_nGroupSize;i++)</p><p>　　TotalF+=1/oldpop[i].CalcCost(m_distance);</p><p><b&g

80、t;　　// 歸一化F值</b></p><p>　　for(i=0;i<m_nGroupSize;i++) </p><p>　　oldpop[i].fit=1/oldpop[i].cost/TotalF*100;</p><p>　　// 將當(dāng)前一代群體中的個體按F值從大到小排序</p><p>　　for(i=0;i&

81、lt;m_nGroupSize-1;i++) </p><p><b>　　{</b></p><p>　　double max=0.0;</p><p>　　int maxpos;</p><p>　　for(int j=i;j<m_nGroupSize;j++) if(oldpop[j].fit>max)

82、</p><p><b>　　{</b></p><p>　　max=oldpop[j].fit; maxpos=j;</p><p><b>　　}</b></p><p>　　if(i!=maxpos) oldpop[i].SwapNode(&oldpop[maxpos]);</p

83、><p><b>　　}</b></p><p>　　m_CurGANum=gen;</p><p>　　// 查找當(dāng)前一代中的最小費用個體</p><p>　　m_MiniCost=oldpop[0].cost;</p><p>　　m_pop.CopyNode(&oldpop[0]);&l

84、t;/p><p>　　m_GAFitness=m_pop.fit;</p><p>　　//AfxMessageBox("顯示數(shù)據(jù)");</p><p>　　UpdateData(false);</p><p>　　UpdateWindow();</p><p>　　if (m_CurGANum ==

85、m_GANum - 1)</p><p><b>　　{</b></p><p><b>　　// 繪制圖形</b></p><p>　　DrawNetwork();</p><p><b>　　}</b></p><p>　　//繼承所有父代基因<

86、;/p><p>　　for(i=0;i<m_nGroupSize;i++) newpop[i].CopyNode(&oldpop[i]);</p><p>　　3.3.3 變異算子</p><p>　　變異運算，是指改變個體編碼串中的某些基因值，從而形成新的個體。變異運算是產(chǎn)生新個體的輔助方法，決定遺傳算法的局部搜索能力，保證了種群的多樣性。交叉運算可以和

87、變異運算相互配合，共同完成對搜索空間的全局搜索和局部搜索。本系統(tǒng)中變異算子采用基本位變異算子?；疚蛔儺愃阕邮侵笇€體編碼串隨機指定的某一位或某幾位基因作變異運算。因為使用由Grefenstette等所提出的編譯方法來表示個體，一個個體經(jīng)過遺傳運算后所得到的任意一個基因型個體與交叉后的情況相同，都能夠?qū)?yīng)于一條具有實際意義的巡回路線。對于二進(jìn)制編碼符號串所表示的個體，若需要進(jìn)行變異操作的某一基因座上的原有基因值為0，則將其變?yōu)?；反之，

88、若原有基因值為1，則將其變?yōu)? ?；疚蛔儺愃阕拥膱?zhí)行過程如下：</p><p>　　（1）對個體的每一個基因座，依變異概率Pm指定其為變異點。</p><p>　?。?）對每一個指定的變異點，對其基因值做取反運算或用其他等位基因值來代替，從而產(chǎn)生出一個新個體。</p><p>　　針對旅行商問題對變異算子的設(shè)計要求，基本位變異即交換變異。變異是單個個體內(nèi)部發(fā)生變化

89、，導(dǎo)致產(chǎn)生新個體，從而產(chǎn)生出一條新的巡回路線。例如：</p><p>　　Tx=（B C A D E J H I F G）</p><p>　?。˙ C A I E J H D F G）=Tx′</p><p><b>　　具體代碼如下：</b></p><p>　　for(i=0;i&

90、lt;m_VariNum;i++)</p><p><b>　　{</b></p><p>　　int nPos1,nPos2,parent=0; //變異父代基因</p><p>　　parent=RandomInt(0,m_nGroupSize-1) （定義變異范圍）</p><p>　　nPos1=Rand

91、omInt(3,MAXCHROM-3); （取其中第三位與倒數(shù)第三位做</p><p>　　nPos2=RandomInt(3,MAXCHROM-3); 為變異結(jié)點）</p><p>　　PopNode pop;</p><p>　　pop.CopyNode(&oldpop[0]);</p><p>　　pop.Varite(nPo

92、s1,nPos2);（執(zhí)行結(jié)點操作）</p><p>　　newpop[m_nGroupSize+m_CrossNum*2+i].CopyNode(&pop);（保存變異結(jié)果）</p><p><b>　　}</b></p><p><b>　　3.4 適應(yīng)度函數(shù)</b></p><p>　

93、　在遺傳算法中，以個體適應(yīng)度的大小來確定該個體被遺傳到下一代群體中的概率。個體的適應(yīng)度越大，該個體被遺傳到下一代的概率也越大；反之，個體的適應(yīng)度越小，該個體被遺傳到下一代的概率也越小。因此適應(yīng)度函數(shù)的選擇至關(guān)重要，直接影響到遺傳算法的收斂速度以及能否找到最優(yōu)解。本系統(tǒng)中以每條路徑長度的倒數(shù)作為適應(yīng)度函數(shù)值，并對其進(jìn)行統(tǒng)一化的操作，即按從大到小進(jìn)行排序，為下一步選擇操作做準(zhǔn)備。為正確計算不同情況下各個個體的遺傳概率，要求所有個體的適應(yīng)度必

94、須為正數(shù)或零，不能是負(fù)數(shù)。具體代碼如下所示：</p><p>　　for(int i=0;i<m_nGroupSize;i++) （nGroupSize是城市之間的距離）</p><p>　　TotalF+=1/oldpop[i].CalcCost(m_distance);（父代結(jié)點的城市距離的倒數(shù)作為它的適應(yīng)度）</p><p>　　3.5 遺傳算法求解TS

95、P問題的具體流程圖</p><p>　　圖3-5 遺傳算法求解旅行商問題的具體流程圖</p><p>　　4 45個城市旅行商問題的仿真軟件的設(shè)計</p><p>　　4.1 系統(tǒng)設(shè)計模塊</p><p>　　本系統(tǒng)在Microsoft Visual C++環(huán)境下完成，根據(jù)需求設(shè)計了三大模塊：算法設(shè)計模塊、演示模塊、幫助模塊。算法設(shè)計模塊完

96、成群體規(guī)模M、交叉概率Pc、變異概率Pm和進(jìn)化代數(shù)T的設(shè)置；具體的參數(shù)已經(jīng)設(shè)置在了演示平臺上，可以根據(jù)需要更改參數(shù)大小，但是盡量在設(shè)定的范圍之內(nèi)，這樣可以保證算法的精確性；幫助模塊則設(shè)置了關(guān)于軟件和制作作者等查看項目。下圖是系統(tǒng)的功能模塊圖。</p><p>　　圖4-1系統(tǒng)功能模塊圖</p><p>　　4.2 系統(tǒng)詳細(xì)設(shè)計</p><p>　　由前文中介紹的個體

97、編碼方法及各種遺傳算子可以構(gòu)成許多種不同的求解旅行商問題的遺傳算法，本系統(tǒng)主要利用這些遺傳算子對含有45座城市的旅行商問題進(jìn)行了試算。</p><p>　　本系統(tǒng)中所使用的遺傳算法是由以下要素所構(gòu)成的：</p><p><b>　　●編碼方法</b></p><p>　　基本遺傳算法使用由Grefenstette所提出的編碼方法，詳細(xì)設(shè)計見第四

98、章編碼方式一節(jié)。</p><p><b>　　●適應(yīng)度函數(shù)</b></p><p>　　系統(tǒng)中以每條路徑長度的倒數(shù)作為適應(yīng)度函數(shù)值。</p><p><b>　　●選擇算子</b></p><p><b>　　采用適應(yīng)度比例法</b></p><p>&

99、lt;b>　　●交叉算子</b></p><p>　　采用常規(guī)單點交叉操作算子。</p><p><b>　　●變異算子</b></p><p>　　使用基本位交換變異操作算子</p><p><b>　　●運行參數(shù)</b></p><p>　　{M，T，P

100、c，Pm}={0~500，0~300，0.2~0.4，0.01~0.08}，式中M為群體大小，T為終止代數(shù)，Pc為交叉概率，Pm為變異概率。本系統(tǒng)給出各個參數(shù)的參考范圍，在此范圍內(nèi)執(zhí)行搜索最佳，超出范圍也可演示，但這會影響搜索效果，可能得不到最優(yōu)解或近似最優(yōu)解。極端情況不可執(zhí)行。這些在上文中已作過詳細(xì)介紹,這里就不再重復(fù)。</p><p>　　4.2.1演示模塊設(shè)計</p><p>　?。?/p>

101、1）主窗口設(shè)計：在VC工具欄insent中插入窗口IDD_CHINA45_DIALOG，再在上面設(shè)置變量，并進(jìn)行初始化。具體變量及其窗口對話框設(shè)置如下表。</p><p>　　表4.2.1為工程添加IDD_CHINA45_DIALOG的菜單選項</p><p>　　表4.2.2通過類查看（ClassView）選項卡，向主對話框添加成員變量</p><p>　　初始化

102、參數(shù)設(shè)置代碼如下：</p><p>　　m_GALen = 45; </p><p>　　m_nGroupSize = 100; </p><p>　　m_GACrossProb = 0.6;</p><p>　　m_GAVariProb = 0.

103、03;</p><p>　　m_GANum = 100;</p><p>　　m_CurGANum = 0;</p><p>　　m_MiniCost = 0.0;</p><p>　　m_CrossNum = 0;</p><p>　　m_VariNum = 0;</p><p>　　m_GA

104、Fitness = 0.0;</p><p>　　變量與對話框進(jìn)行綁定：</p><p>　　DDX_Text(pDX, IDC_EDIT1, m_GALen);</p><p>　　DDX_Text(pDX, IDC_EDIT2, m_nGroupSize);</p><p>　　DDX_Text(pDX, IDC_EDIT3, m_GAC

105、rossProb);</p><p>　　DDX_Text(pDX, IDC_EDIT4, m_GAVariProb);</p><p>　　DDX_Text(pDX, IDC_EDIT5, m_GANum);</p><p>　　DDX_Text(pDX, IDC_EDIT6, m_CurGANum);</p><p>　　DDX_Text

106、(pDX, IDC_EDIT7, m_MiniCost);</p><p>　　DDX_Text(pDX, IDC_EDIT8, m_CrossNum);</p><p>　　DDX_Text(pDX, IDC_EDIT9, m_VariNum);</p><p>　　DDX_Text(pDX, IDC_EDIT10, m_GAFitness);</p>

107、<p>　　打開類向?qū)В–lass Wizard）對話框向主對話框類添加響應(yīng)函數(shù)，用于顯示新生成的群體規(guī)模、交叉變異數(shù)目等。具體代碼如下：</p><p>　　void CChina45Dlg::OnMenuGaset() </p><p><b>　　{</b></p><p>　　// TODO: Add your comma

108、nd handler code here</p><p>　　CGASetDlg dlg;</p><p>　　if(dlg.DoModal()==IDOK)</p><p><b>　　{</b></p><p>　　m_nGroupSize=dlg.m_nGroupSize; （將新的群體規(guī)模賦值給對話框）<

109、/p><p>　　m_GACrossProb=dlg.m_GACrossProb; （將新的交叉概率賦值給對話框）</p><p>　　m_GAVariProb=dlg.m_GAVariProb; （將新的變異概率賦值給對話框）</p><p>　　m_GANum=dlg.m_GANum; （將新的遺傳代數(shù)賦值給對話框）</p>&l

110、t;p>　　UpdateData(false);</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　在主窗口上拖一個按鈕進(jìn)去，按鈕名為OnButtonGa(遺傳算法演示按鈕)并對其添加響應(yīng)函數(shù)聲明,該函數(shù)執(zhí)行最短路徑更新的操作,即執(zhí)行一次算法,顯示一次運算結(jié)果：<

111、;/p><p>　　void CChina45Dlg::OnButtonGa() </p><p><b>　　{</b></p><p>　　PopNode *oldpop;</p><p>　　oldpop=new PopNode[m_nGroupSize];</p><p>　　for(int

112、k=0;k<1;k++)</p><p><b>　　{</b></p><p>　　ExecGA(k, oldpop);</p><p><b>　　}</b></p><p>　　（2）主窗口菜單設(shè)置：在菜單欄中需要做三個選項：文件、設(shè)置和幫助。在文件下面繼續(xù)添加菜單退出，并設(shè)置ID為ID

113、_MENU_EXIT；文件下邊添加菜單遺傳算法設(shè)置，設(shè)置ID為ID_MENU_GASET；幫助下邊添加菜單關(guān)于軟件和關(guān)于作者，設(shè)置ID分別為ID_MENU_SOFT、ID_MENU_WRITE。</p><p>　?。?）遺傳算法參數(shù)設(shè)置窗口的設(shè)計：在菜單遺傳算法設(shè)置下插入一個窗口IDD_DIALOG_SET,具體設(shè)置如下表所示：</p><p>　　表4.2.3 為工程添加IDD_DIA