#遺傳算法其在TSP問題應用(共26頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)專心-專注-專業(yè)精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)本 科 畢 業(yè) 設 計畢業(yè)設計題目：遺傳算法及其在TSP問題的應用學生姓名： 學 號：系 別： 專業(yè)班級： 指導教師姓名及職稱： 起止時間： 摘要遺傳算法(Genetic Algorithm, GA是近年來迅速發(fā)展起來的一種全新的隨機搜索與優(yōu)化算法,旅行商問題是一個典型的NP完全問題，而遺傳算法是解決這類問題的一個比較理想的算法,它的基本思想來源于Darwin的進化論和Mendel的遺傳學。本文首先對遺傳算法和旅行商問題進行了簡單的介紹，并用數(shù)學的方式描述了TSP問題。

2、然后詳細地闡述了遺傳算法在編碼表示和遺傳算子 is a new random search and optimization algorithm，develops rapidly in recent years,TSP (Traveling Salesman Problem is a typical NP - complete problem and genetic algorithm (GA is one of the best methods for solving NP - complete problem, the basic idea of the theory is Darwin

3、and Mendels genetics. Firstly，the articleintroduces the Genetic Algorithm and Traveling Salesman Problem briefly and mathematically. Then describes the detail of the genetic algorithm，such as coded representation，genetic operators(including selection operator, crossover operator, mutation operator a

4、nd the other applications. Finally，we modify the parameters of the initial population，genetic algebra，crossover rate，mutation rate to verify the influence onthe result and solvingefficiencyof the algorithm.Keywordsgenetic algorithm TSP codingRoulette algorithmElitist strategyOrder crossover目錄 TOC o

5、1-3 h z u 第一章引言21.1 研究背景31.2 國內(nèi)外發(fā)展現(xiàn)況31.3 主要研究內(nèi)容51.4 本文結(jié)構5第二章遺傳算法與TSP問題介紹62.1 遺傳算法介紹62.1.1 遺傳算法的特點72.1.2 基本遺傳算法的應用步驟72.1.3 基本遺傳算法的流程圖82.1.4 遺傳算法應用中的關鍵問題92.2 TSP問題介紹12第三章遺傳算法在TSP上的應用與實現(xiàn)133.1 遺傳算法解決TSP問題的具體實現(xiàn)133.1.1 本文用遺傳算法解決TSP問題的流程圖133.1.2 編碼143.1.3 適應度函數(shù)143.1.4 初始化種群143.1.5 選擇操作153.1.6 交叉操作163.1.7 變

6、異操作163.2 不同參數(shù)下的計算結(jié)果對比173.2.1 初始種群10和100的對比183.2.2 不同交叉率和變異率的對比193.2.3 不同參數(shù)下結(jié)果對比結(jié)論213.2.4 程序運算過程截圖213.3 東莞10個景點坐標和運行結(jié)果24第四章結(jié)論26參考文獻27附錄相關源代碼28致謝35第一章 引言在過去,人們往往只能處理一些簡單的問題，對于大型復雜系統(tǒng)的優(yōu)化和自適應問題，仍然無能為力。但是在這方面，自然界中的生物表現(xiàn)出了其優(yōu)異的能力，它們能夠通過優(yōu)勝劣汰、適者生存的自然進化法則進行生存和繁衍，并能漸漸地進化出對其生存環(huán)境適應性越來越高的優(yōu)良物種。遺傳算法就是模擬自然界中生物進化的一種高效的

7、算法，其基本思想就是模擬自然界進化機制和生物進化論而形成的一種機制求解最優(yōu)值問題的自組織、自適應的智能算法。遺傳算法1(Genetic Algorithm, GA是近年來迅速發(fā)展起來的一種全新的隨機搜索與優(yōu)化算法，盡管各種理論、方法都尚未成熟，有待于進一步地完善和發(fā)展，但我們從它的身上看到了解決多種復雜問題的希望。雖然在遺傳算法的研究和應用過程中出現(xiàn)過各種不同的算法設計，同時也會遇到過許多不同的難題，但是就目前而言，遺傳算法的應用過程已經(jīng)展現(xiàn)出了其突出的性能和巨大的發(fā)展前景。近年來，遺傳程序設計運用遺傳算法的思想自動生成計算機程序解決了許多問題，如預測、分類、符號回歸和圖像處理等，作為一種新技

8、術，它已經(jīng)與遺傳算法并駕齊驅(qū)。我相信，隨著研究工作進一步深入地發(fā)展，遺傳算法將會在智能計算領域中起到非常重要的作用。旅行商問題(Traveling Salesman Problem, TSP,是一個著名的組合優(yōu)化問題2,該類問題具有非常廣泛的運用背景。如物流的調(diào)度問題、數(shù)控機床上的最優(yōu)鉆孔路線的選取、電路板的焊接都屬于旅行商問題。因此旅行商問題受到了各方面的關注，有效解決TSP問題在計算理論和實際應用上都有很高的價值。目前解決TSP的主要方法有遺傳算法、模擬退火算法、啟發(fā)式搜索法、Hopfield神經(jīng)網(wǎng)絡算3、二叉樹描述算法。本文主要介紹了應用遺傳算法來解決TSP問題。1.1 研究背景如今的科

9、學技術正步入多學科互相影響、相互交叉、互相滲透的時代，生命科學與項目科學的交叉、滲透和互相促進是其中一個典型的例子，也是近代科學技術發(fā)展的一個里程碑。遺傳算法也因此誕生。TSP問題，也稱為旅行商問題，就是為人們所廣泛研究的典型的組合優(yōu)化為題。而且因為TSP問題的典型性，使得它已經(jīng)成為各種啟發(fā)式的搜索、優(yōu)化算法(如遺傳算法、模擬退火法、神經(jīng)網(wǎng)絡優(yōu)化法、蟻群優(yōu)化算法、列表尋優(yōu)法等4的間接比較標準。其中，遺傳算法有不俗的表現(xiàn)5 。1.2 國內(nèi)外發(fā)展現(xiàn)況遺傳算法最早由美國Michigan(密執(zhí)安大學的Holland 6 7教授提出，起源于60年代對自然和人工自適應系統(tǒng)的研究。70年代DeJong基于遺

10、傳算法的思想在計算機上進行了大量純數(shù)值函數(shù)優(yōu)化計算實驗。80年代Goldberg8在一系列研究工作的基礎上進行總結(jié)歸納，形成了遺傳算的基本框架。步入八十年代，遺傳算法迎來了興盛的發(fā)展時期，無論在理論研究還是應用研究方面都成為了十分熱門的課題。1985年，在美國召開了第一屆遺傳算法國際會議International Conference on Genetic Algorithms ，ICGA），并且成立國際遺傳算法學International Society of Genetic Algorithms ，ISGA），往后每兩年舉行一次。1989年，Holland的學生D.E.Goldberg出版

11、了專著搜索、優(yōu)化和機器學習中的遺傳算法方法，成功地解決了許多問題。1990年，歐洲開始每隔一年舉辦一次Parallel Problem Solving from Nature 學術會議，遺傳算法都是會議的主要內(nèi)容之一。此外，以遺傳算法的理論基礎為中心的學術會議還有Foundations of Genetic Algorithms，該會也是從1990年開始隔年召開一次。這些國際學術會議，集中反映了近些年來遺傳算法的最新發(fā)展動向。1991年，L.Davis編輯出版了遺傳算法手冊Handbook of Genetic lgorithms），書中囊括了遺傳算法在項目技術和社會生活中的大量應用實例。 1

12、992年，Koza發(fā)表了他的專著遺傳程序設計:基于自然選擇法則的計算機程序設計。1993年，MIT出版社創(chuàng)刊了新雜志Evolutionary Computation。1997年，IEEE又創(chuàng)刊了Transactions on Evolutionary Computation。Advanced Computational Intelligence雜志也即將發(fā)刊，由模糊集合創(chuàng)始人L.A.Zadeh教授為名譽主編。1994年，Koza接著出版了遺傳程序設計，第二冊:可重用程序的自動發(fā)現(xiàn)，使得遺傳程序設計更加深化研究，程序設計自動化展現(xiàn)了新局面。有關遺傳算法的學術論文也不斷在Artificial In

13、telligence、Genetic Programming and Evoluable Machines、Information science、Machine Learning、Parallel Computing、IEEE Transactions on Neural Networks、IEEE Transactions on Signal Processing等雜志上發(fā)表。目前，關于遺傳算法的研究熱潮仍在持續(xù)，越來越多從事各種不同領域的研究人員已經(jīng)或正在置身于有關遺傳算法的研究或應用之中。1.3 主要研究內(nèi)容本文通過對遺傳算法的研究，并且利用Visual C+集成開發(fā)環(huán)境將其編程實現(xiàn)來

14、解決TSP問題。在運用遺傳算法成功解決TSP問題基礎上，再通過改變不同的初始種群數(shù)目、遺傳代數(shù)、交叉率、變異率來比較算法的質(zhì)量與效率。從而觀察、驗證這類參數(shù)對算法質(zhì)量和效率的影響程度。1.4 本文結(jié)構第一章：引言首先對本文的研究背景、遺傳算法在國內(nèi)外目前的發(fā)展狀況進行了簡單的描述,然后再對本文研究的大致內(nèi)容進行了說明。第二章：遺傳算法與TSP問題的介紹,首先對遺傳算法的基本術語概念、個體的編碼方式、初始化種群、適應度函數(shù)、選擇算子、交叉算子、變異算子、運行參數(shù)和全局最優(yōu)收斂進行介紹，然后也對TSP問題的數(shù)學模型進行了闡述。第三章：遺傳算法在TSP上的應用與實現(xiàn),通過選取網(wǎng)上已有最優(yōu)解的10個城

15、市的TSP問題為例，運用遺傳算法求解該TSP問題。然后通過選取不同的參數(shù)進行測試，對比結(jié)果，從而驗證遺傳算法的各參數(shù)對算法效率和質(zhì)量的影響程度。并對東莞10個景點的實例TSP問題進行解決。第四章：結(jié)論,對第三章的結(jié)果對比進行了總結(jié)與歸納。總結(jié)了種群大小、遺傳代數(shù)、交叉率、變異率等參數(shù)對算法效率和質(zhì)量的影響程度及改善方式。第二章 遺傳算法與TSP問題介紹2.1 遺傳算法介紹遺傳算法是一種借鑒生物界自然選擇和自然遺傳機制的隨機化搜索算法，由美國Holland 教授提出，其基本思想是基于Darwin的進化論和Mendel的遺傳學說，其最初的目的是研究自然系統(tǒng)的自適應行為。作為一種通用的問題求解方法，

16、遺傳算法采用了簡單的編碼技術來表示各種復雜的結(jié)構，并通過對一組編碼進行優(yōu)勝劣汰的自然選擇原則的遺傳操作來指導學習和確定搜索的方向。與自然界相似，遺傳算法對求解問題的本身一無所知，它需要對算法產(chǎn)生的每個染色體進行評價，并基于適應度值來選擇染色體，使適應性好的染色體有更多的繁衍機會。在遺傳算法中，通過隨機方式產(chǎn)生若干個所求問題的數(shù)字編碼即染色體），形成初始種群；根據(jù)所要解決的問題設定一個適應度函數(shù)，然后給每一個個體一個適應度的評價，淘汰適應度低的個體，選擇適應度高的個體進行遺傳操作，經(jīng)過遺傳操作后形成新一代的種群，對新一代的種群再進行下一輪的進化，直到產(chǎn)生近似的最優(yōu)解。這就是遺傳算法的基本原理。為

17、了更好理解遺傳算法，下面介紹一下遺傳算法中的一些基本概念9：的形式，在算法中為二進制串，并且對應于遺傳學中的染色體(Chromosome。2）群體：個體的集合稱為群體，“串”是群體的元素。群體大小：在群體中個體的數(shù)目被稱為群體的大小。3）基因：基因是串中的元素，基因用于表現(xiàn)個體的特征。列入一個串1,2,3，其中1，2，3這3個元素都是基因。4）基因位置：一個基因在串中的位置被稱為基因位置。基因位置從左到右計算。的集合。的集合。7）適應度：表示某個個體對環(huán)境的適應程度。2.1.1遺傳算法的特點1）遺傳算法從問題解的部分集合開始搜索。傳統(tǒng)的優(yōu)化算法是從單個解開始搜索。這是遺傳算法和傳統(tǒng)優(yōu)化算法的幾

18、大區(qū)別之一。傳統(tǒng)優(yōu)化算法從單個個體開始迭代，容易陷入局部最優(yōu)。遺傳算法從“串集”開始搜索，覆蓋的面積大，利于全局最優(yōu)。2）遺傳算法對優(yōu)化問題沒有太多的要求，只需知道目標函數(shù)的信息即可，易于形成通用的算法。算子、交叉(crossover算子和變異(mutation算子10，發(fā)揮著重要的遺傳作用。以下來詳細說明：(1 個體的編碼方式：編碼：信息從一種形式或格式轉(zhuǎn)換為另一種形式的過程。編碼是應用遺傳算法時要解決的主要問題，也是遺傳算法程序設計的一個關鍵步驟。編碼方法除了會決定個體染色體的排列形式之外，還會決定個體從搜索空間的基因型變成解決空間的表現(xiàn)型的編碼方法，編碼方法也會影響到交叉算子、變異算子的

19、運算方法。通常編碼方法有二進制編碼、參數(shù)編碼、格雷碼編碼、浮點數(shù)編碼等。在TSP問題中常用：訪問路徑順序進行編碼。二進制編碼：二進制編碼是一種常用的編碼方式，它使用由二進制符號0和1組成的二值符號集0,1，它所構成的個體是一個二進制編碼符號串。二進制編碼符號串長度與問題所要求的精度有關。因為二進制不便于反映所求問題的結(jié)構特征和一些連續(xù)函數(shù)的優(yōu)化問題，也因為遺傳算法的隨機特性使得其局部搜索能力較差，因此本文不采用此編碼方法。參數(shù)編碼：參數(shù)編碼方法是對含有多個變量的個體進行編碼的方法，包含兩種編碼方法，多參數(shù)級聯(lián)編碼方法和多參數(shù)交叉編碼方法。格雷碼編碼：格雷碼是二進制編碼的變形，其精度也與二進制編

20、碼相同，但是任意兩個相鄰整數(shù)的格雷碼的海明距為1，即編碼串之間也只有一位差異。這徉就相當于增強了遺傳算法的局部搜素能力，便于對連續(xù)函數(shù)進行局部空間搜索。浮點數(shù)編碼：個體的每個基因值用某一范圍內(nèi)的一個浮點數(shù)來表示，個體的編碼長度等于其決策變量的個數(shù)，個體變量的長度等于其決策變量的真實值，所以也叫真實值編碼方法。以訪問路徑順序進行編碼是解決TSP問題的一種常用的編碼方式。在第三章中會重點介紹。(2 初始化種群：選擇一個群體，就是選擇一個個體的集合。這個初始群體就是問題假設解的集合。在遺傳算法求解TSP問題中通常以隨機方式產(chǎn)生串或者個體的集合11。初始種群個數(shù)越多，得到最優(yōu)解的希望越大，但個數(shù)過多會

21、導致每進行一輪的機器計算時間變長，降低算法效率。(3 適應度函數(shù)：度量物種適應度的函數(shù)就被稱為適應度函數(shù)。在研究自然界中生物的遺傳和進化現(xiàn)象時，生物學家常常使用適應度這個術語來衡量某個物種對環(huán)境的適應率。適應度較高的物種將會得到更多的繁殖的機會，而適應度低的物種則被淘汰。在遺傳算法中，根據(jù)個體的適應值來決定其在此環(huán)境下的生存能力。個體適應度大小決定該個體被遺傳到下一代群體中的概率。所以個體適應度的評價在遺傳算法中也是一個重要的步驟。其一般過程為：a.對個體編碼的串進行解碼處理后，可以得到個體的表現(xiàn)型。b.由個體的表現(xiàn)型計算出對應個體的目標函數(shù)值。c.根據(jù)最優(yōu)化問題的類型，由目標函數(shù)值按一定的轉(zhuǎn)

22、換規(guī)則求出個體的適應度。(4 選擇算子：選擇算子是遺傳算法中的又一個關鍵步驟。遺傳算法通過它對群體中的個體進行優(yōu)勝劣汰操作。適應度值高的個體被選中的幾率高，適應度低的個體被選中的概率低。選擇操作就是用于確定如何從父代群體中按某種方式選取一些較優(yōu)的個體進行雜交、變異操作。選擇操作建立在對個體適應度值評價的基礎上。選擇的目的是為了避免基因缺失、提高計算效率和收斂率。幾種常用的選擇算子的操作方法有：輪盤賭選擇、精英保留策略、確定式采樣選擇、無放回隨機選擇、排序選擇等。(5 交叉算子：在生物的自然進化中，兩個同源染色體通過交叉而重新組合，形成新的染色體，從而產(chǎn)生新的個體或物種。遺傳算法模仿這個過程，使

23、用交叉算子來產(chǎn)生新的個體。交叉運算在選擇運算之后，兩個相互配對的染色體按某種方式交換其部分基因，從而產(chǎn)生新的問題解。交叉運算是遺傳算法區(qū)別于其他算法的重要特征，充當著重要的作用，是產(chǎn)生新個體的主要方式。常用的交叉算子有：單點交叉算子、雙點交叉算子、均勻交叉算子、順序交叉算子OX）、部分映射交叉算子 變異算子：在生物的遺傳和自然進化中，細胞的分裂復制環(huán)節(jié)有可能會因為某些偶然因素的影響而發(fā)生一些復制差錯，就會導致生物的某些基因發(fā)生變異，從而產(chǎn)生新的個體。在遺傳算法中，變異操作也是如此。交叉操作是產(chǎn)生新個體的主要方式，它決定了算法的全局搜索能力。而變異操作則起著輔助作用，它提高了算法的局部搜索能力，

24、避免算法陷入局部最優(yōu)。兩種算子的理想結(jié)合，才能大大提高了整個算法可行性。使計算結(jié)果更加接近全局最優(yōu)解。變異算子的2個重要作用：a.改善遺傳算法的局部搜索能力。b.維持群體多樣性，防止早熟現(xiàn)象。(7運行參數(shù):在遺傳算法中需要選擇的參數(shù)主要有個體的編碼長度、群體大小、交叉率、變異率和遺傳代數(shù)。個體編碼長度：根據(jù)具體問題進行設定。群體大?。罕硎救后w中所含的個體數(shù)量。當群體較小時，遺傳算法的運算速度較快，但是降低了群體的多樣性，從而導致了遺傳算法的早熟現(xiàn)象；而當群體較大時，又會增大機器的開銷、降低了算法的效率。交叉率：交叉是產(chǎn)生新個體的主要方式，一般應取較大值，但取值過大會破壞群體中的優(yōu)秀個體，對進化

25、反而產(chǎn)生不利影響；取值過小的話，會導致收斂速度過慢。所以一般應取0.4到0.9。變異率：取值較大雖然能幫助種群產(chǎn)生較多的新個體，但同時也可能破壞了很多較好的個體，使得遺傳算法的性能靠近隨機搜索算法的性能；取值過小的話，變異操作產(chǎn)生新個體的能力和抑制早熟的能力就會變差。一般應取值0.01到0.1。(8 全局最優(yōu)收斂當設定的遺傳代數(shù)循環(huán)結(jié)束，運算得出的最優(yōu)個體就是全局最優(yōu)解，則說明算法全局最優(yōu)收斂。但如果得到的解并不是全局最優(yōu)解，同時運算得到的解，已經(jīng)過早的不發(fā)生變化，說明算法陷入了局部最優(yōu)解。另外當循環(huán)結(jié)束時，最優(yōu)解還在緩慢的變優(yōu)，則需提高遺傳代數(shù)來得出全局最優(yōu)解。2.2 TSP問題介紹TSP問

26、題，也稱旅行商問題。已知n個城市之間的相互距離，現(xiàn)有一個推銷員必須遍訪這n個城市，并且每個城市只能訪問一次，最后又必須返回出發(fā)城市。如何安排他的訪問順序，可使其旅行的總長度最短12。用圖論的術語來說，假設有一個圖g=(v,e,其中v是頂點集，e是邊集，設d=是由頂點i和頂點j之間距離所組成的距離矩陣，旅行商問題就是要求出一條通過所有頂點且每個頂點只通過一次的具有最短距離的回路。這個問題可分為對稱旅行商問題(=任意和非對稱旅行商問題(任意i,j=。城市的一個訪問順序為,其中v(i=1,2,3,n，且記，則旅行商問題的數(shù)學模型為：min =d(t(i,t(i+1 i=0,9） 。第三章 遺傳算法在

27、TSP上的應用與實現(xiàn)本文通過遺傳算法來解決10個城市的旅行商問題。即一個商人需要經(jīng)過10個城市去交易，每個城市必須且只能經(jīng)過一次。最后回到初始點，求出最短路徑。 首先，本文運用Visual C+集成開發(fā)環(huán)境將遺傳算法編程實現(xiàn)，并解決TSP問題。然后通過改變各個參數(shù)的值來觀察計算結(jié)果，接著對運算結(jié)果的進行對比分析，從而驗證各個參數(shù)對遺傳算法的影響。3.1 遺傳算法解決TSP問題的具體實現(xiàn)3.1.1 本文用遺傳算法解決TSP問題的流程圖以訪問路徑順序進行編碼采用隨機方式初始化種群外部輸入初始化種群個數(shù)、遺傳代數(shù)、交叉率、變異率以每次訪問總距離的倒數(shù)作為評估函數(shù)，對每個個體進行評估，初始化代數(shù)p=0

28、P=遺傳代數(shù)成立不成立輸出結(jié)果P=p=1選擇操作結(jié)束交叉操作變異操作圖3.1 遺傳算法運用在tsp上的流程圖3.1.2 編碼編碼是遺傳算法程序設計的第一個重點。上文已經(jīng)闡述過編碼的各種主要方法。如：二進制表示、浮點編碼、格雷碼、參數(shù)編碼等。而在TSP問題中，路徑表示可能是最直接自然的表示方式。它直接采用城市在整個路徑中的相對位置來表示。遺傳算法中的每個個體，就是一次訪問順序。如有10個城市：0,1，2,3,4,5,6,7,8,9。商人的一次訪問順序為6,2,1,0,5,8,3,9,4,7,6）。就用6,2,1,0,5,8,3,9,4,7）作為種群中的一個個體的編碼。表示商人從城市6出發(fā)路徑為6

29、,2,1,0,5,8,3,9,4,7最后回到城市6，這種編碼方式顯然是非常自然的。其主要的缺點在于普通的單點、雙點交叉操作后往往會引起路徑的非法訪問,即在整個訪問過程中有些城市不止訪問了1次。為了消除這一缺點，本文采用了順序交叉方法代替了傳統(tǒng)的單點、雙點交叉。3.1.3適應度函數(shù)為了能體現(xiàn)出種群中個體的適應能力，遺傳算法中引入了對種群中每個個體適應度進行度量的函數(shù)，即適應度函數(shù)，通過它決定個體的優(yōu)劣來體現(xiàn)出自然進化中優(yōu)勝劣汰的原則。對于優(yōu)化問題，適應度函數(shù)就是目標函數(shù)。TSP問題的目標就是求出最短訪問路徑。本文采用路徑距離之和的倒數(shù)作為適應函數(shù)，并用數(shù)組存放eval100每個個體的總路程，而e

30、val1100每個個體總路程的倒數(shù)，則作為適應度函數(shù)：fori=0；i；3.1.4初始化種群初始化種群：采用隨機的方式獲得初始化種群。它適合于對問題解無任何先驗知識的情況。代碼見附錄。3.1.5選擇操作選擇操作也稱作復制操作。根據(jù)個體適應度函數(shù)所決定的優(yōu)劣程度來決定個體是遺傳還是被淘汰。在求解TSP問題中，常用的選擇機制有輪盤賭選擇、最佳個體保存選擇、排序模型選擇機制、期望值模型機制等。在遺傳算法中，算法“早熟”即局部收斂，是一個需要關注的問題。為了保證算法的全局收斂性，避免進入局部收斂，就要維持種群個體的多樣性，避免有效個體的丟失。Rudolhp C13提出采用精英保留策略，保存群體中最好的

31、個體不丟失，以保證算法的收斂性。Konstantin Boukreev14采用聯(lián)賽選擇方法和最優(yōu)個體保存方法相結(jié)合的方法。而本文采用輪盤賭算法和最優(yōu)保存策略的結(jié)合。(1 輪盤賭算法：將個體的適應度值按比例換算為被選中的概率，使得適應度值高的個體的被選中的概率也高。令for(i=0。igailvi=eval1i/total。首先將輪盤分成100個扇區(qū)進行100次選擇，產(chǎn)生100個0到1之間的隨機數(shù)。這相當于輪盤轉(zhuǎn)動100次，就可獲得n次轉(zhuǎn)盤停止時的指針位置，指針停放在某一個扇區(qū)，就表示選中了該扇區(qū)的個體。所以概率越大面積越大，被選中的幾率越大。代碼見附錄。(2 最優(yōu)保存策略：在生物遺傳的過程中，

32、通過對個體進行交叉、變異等遺傳操作不斷產(chǎn)生新一代的種群個體，雖然能夠隨著不斷進化會產(chǎn)生越來越多的優(yōu)秀個體，但是因為遺傳操作的隨機性，也可能會破壞掉種群中當代最優(yōu)秀的個體。所以我們希望適應度最好的個體能夠盡可能的保存到下一代的群體中。為了實現(xiàn)這一目標，本文采用最優(yōu)保存策略輔助輪盤算法來進行選擇操作。最優(yōu)保存的具體過程：首先找出當代個體中的最優(yōu)個體和最差個體。如果當代個體中的最優(yōu)個體比總最優(yōu)個體，由Davis等人提出。順序交叉算法首先隨機地在上一代群體中選擇兩個雜交點，再交換雜交段，其他位置根據(jù)保持上代群體的相對順序來確定。例如：A110=0,1,2,3,4,5,6,7,8,9 A210=9,8,

33、7,6,5,4,3,2,1,0隨機雜交點為3和5。首先交換雜交段。B110=#,#,#|6,5,4|#,#,#,#B210=#,#,#|3,4,5|#,#,#,#從B1的第二個雜交點開始6-7-8-9-0-1-2-3-4-5，去除雜交段中的6,5,4。變成7-8-9-0-1-2-3。一次順序從第二個雜交點開始填入得:B110=1,2,3,6,5,4,7,8,9,0同理得:B210=8,7,6,3,4,5,2,1,0,9代碼見附錄。3.1.7變異操作在遺傳算法中，強調(diào)的是雜交功能，變異操作并不是最主要的。變異操作是用于改善遺傳算法的局部搜索能力、維持群體的多樣性和防止早熟現(xiàn)象。針對TSP問題，陳

34、國良等介紹了四種主要的變異技術：1）點位變異，變異僅以某一很小的概率對串的某些位值變異；2）逆轉(zhuǎn)變異，在串中隨機選擇兩點，再將這兩點內(nèi)的內(nèi)容按反序插入到原來的位置中。插入變異，從串中隨機選擇1個碼，將此碼插入隨機選擇的插入點之后。本文采用對換變異操作。代碼見附錄。此外，對于變異操作還有一些變體形式，如Sushil Jouis提出的貪心對換變異、謝勝利17等提出倒位變異算子。3.2 不同參數(shù)下的計算結(jié)果對比本文采用網(wǎng)絡上已有的城市距離矩陣來驗證所寫程序的正確性:int length1010= 0,23, 93, 18, 40, 34, 13, 75, 50, 35, 23, 0, 75, 4,

35、72, 74, 36, 57, 36, 22, 93, 75, 0, 64, 21, 73, 51, 25, 74, 89, 18, 4, 64, 0, 55, 52, 8, 10, 67, 1, 40, 72, 21, 55, 0, 43, 64, 6, 99, 74, 34, 74, 73, 52, 43, 0, 43, 66, 52, 39, 13, 36, 51, 8, 64, 43, 0, 16, 57, 94, 75, 57, 25, 10, 6, 66, 16 , 0, 23, 11, 50, 36, 74, 67, 99, 52, 57 ,23, 0, 42, 35, 22,

36、89, 1, 74, 39, 94 ,11 ,42, 0,。 其最優(yōu)距離已被求解為：226.3.2.1 初始種群10和100的對比在理論上，遺傳算法中初始種群的個數(shù)決定了種群個體的多樣性。初始種群過小容易導致程序陷入局部最優(yōu)，而無法得到近似的最優(yōu)解。增加種群個數(shù)雖然可以避免陷入局部最優(yōu)，但是種群過大會減慢程序的運算速度，降低算法效率。下面是初始種群10和100的結(jié)果對比。下表為交叉率Pc=0.9，變異率 Pm=0.01,初始種群分別為10,100，遺傳代數(shù)分別為100,200的實驗結(jié)果對比：表3.2 不同初始種群的算法結(jié)果對比表次數(shù)遺傳代數(shù)100200初始種群大小最優(yōu)解代數(shù)最優(yōu)解最優(yōu)解代數(shù)最優(yōu)

37、解1104024610023810011232131226210602381932261002422950226310712457423310094226302264102722910224010091226124226510552479423310054226161226610142339523310035229572267104322910022910080235782328109025219322610030232752269104024712922910030228782321010502491712281001822877226初始種群為10，遺傳代數(shù)為100的平均最優(yōu)解為:241.

38、5初始種群為10，遺傳代數(shù)為200的平均最優(yōu)解為:231.4初始種群為100，遺傳代數(shù)為100的平均最優(yōu)解為:229.1初始種群為100，遺傳代數(shù)為200的平均最優(yōu)解為:227.2以上結(jié)果非常顯然地表示出了當初始種群個數(shù)增加后，獲得的平均解更接近全局最優(yōu)解。但增加初始種群同時會增加的算法的循環(huán)次數(shù)，從而降低了算法的運算效率。而選取初始種群為10，遺傳代數(shù)為100的個體，除去獲得全局最優(yōu)解的個體，然后計算獲得最優(yōu)解的代數(shù)的平均值：49，數(shù)據(jù)表現(xiàn)出算法在沒有獲得全局最優(yōu)解的前提下過早的確定問題解。原因：初始種群個數(shù)過少，導致陷入局部最優(yōu)解。3.2.2不同交叉率和變異率的對比1）下面是初始種群為10

39、的模塊。設定相同的交叉率、不同的變異率來觀察兩組計算的對比結(jié)果：表3.2 相同交叉率、不同變異率的算法結(jié)果對比表條件Pc=0.9 Pm=0.001Pc=0.9 Pm=0.1遺傳代數(shù)300500300500次數(shù)最優(yōu)解代數(shù)最優(yōu)解最優(yōu)解代數(shù)最優(yōu)解最優(yōu)解代數(shù)最優(yōu)解最優(yōu)解代數(shù)最優(yōu)解11172337922919724436522821442288723224124029023331632402562282782353172334982331982281522322122495270228450232196240350232666238372282182323012297832338223820023824

40、22338147241311229181232313241910822976232258248295232103024663229233232276232狀態(tài)Pc=0.9 Pm=0.001 遺傳代數(shù)300 的平均最優(yōu)解代數(shù)為：119.6遺傳代數(shù)500 的平均最優(yōu)解代數(shù)：163.6狀態(tài)Pc=0.9 Pm=0.1遺傳代數(shù) 300 的平均最優(yōu)解代數(shù)為：215.4遺傳代數(shù) 500 的平均最優(yōu)解代數(shù)為：296.1從上述結(jié)果可觀察到：在眾多計算結(jié)果未得到全局最優(yōu)解的計算中，狀態(tài)比起狀態(tài)來，過早收斂，從而降低了其抑制早熟的能力。 初始種群的大小決定了種群的多樣性。種群個體過少會導致算法過早收斂，從而陷入局部

41、最優(yōu)解，難以得到全局最優(yōu)解。但是種群過大則會導致遺傳操作要進行的循環(huán)過多，大大加大了機器開銷，降低算法效率。一般10個城市選取種群大小為50-200為宜。2）變異率取值過小，就會導致算法容易陷入局部收斂。從而降低了其抑制早熟的能力。但也不能過大，否則會破壞群體中的優(yōu)秀個體，降低算法效率，甚至有可能找不到最優(yōu)解。在本算法中變異率取0.01到0.1為宜。3）交叉概率過小會導致產(chǎn)生新個體的速度變慢，而導致收斂速度降低。但也不能過大，過大可能會破壞種群中的優(yōu)秀個體。本算法中交叉率取0.7到0.9為宜。3.2.4程序運算過程截圖初始種群為10，遺傳代數(shù)為200，交叉率為0.9、變異率為0.01的運行圖：圖3.2 初始種群為10的算法運行圖初始種群為