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

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

2、然后詳細(xì)地闡述了遺傳算法在編碼表示和遺傳算子 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 國(guó)內(nèi)外發(fā)展現(xiàn)況31.3 主要研究?jī)?nèi)容51.4 本文結(jié)構(gòu)5第二章遺傳算法與TSP問題介紹62.1 遺傳算法介紹62.1.1 遺傳算法的特點(diǎn)72.1.2 基本遺傳算法的應(yīng)用步驟72.1.3 基本遺傳算法的流程圖82.1.4 遺傳算法應(yīng)用中的關(guān)鍵問題92.2 TSP問題介紹12第三章遺傳算法在TSP上的應(yīng)用與實(shí)現(xiàn)133.1 遺傳算法解決TSP問題的具體實(shí)現(xiàn)133.1.1 本文用遺傳算法解決TSP問題的流程圖133.1.2 編碼143.1.3 適應(yīng)度函數(shù)143.1.4 初始化種群143.1.5 選擇操作153.1.6 交叉操作163.1.7 變

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

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

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

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

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

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

12、992年，Koza發(fā)表了他的專著遺傳程序設(shè)計(jì):基于自然選擇法則的計(jì)算機(jī)程序設(shè)計(jì)。1993年，MIT出版社創(chuàng)刊了新雜志Evolutionary Computation。1997年，IEEE又創(chuàng)刊了Transactions on Evolutionary Computation。Advanced Computational Intelligence雜志也即將發(fā)刊，由模糊集合創(chuàng)始人L.A.Zadeh教授為名譽(yù)主編。1994年，Koza接著出版了遺傳程序設(shè)計(jì)，第二冊(cè):可重用程序的自動(dòng)發(fā)現(xiàn)，使得遺傳程序設(shè)計(jì)更加深化研究，程序設(shè)計(jì)自動(dòng)化展現(xiàn)了新局面。有關(guān)遺傳算法的學(xué)術(shù)論文也不斷在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ā)表。目前，關(guān)于遺傳算法的研究熱潮仍在持續(xù)，越來越多從事各種不同領(lǐng)域的研究人員已經(jīng)或正在置身于有關(guān)遺傳算法的研究或應(yīng)用之中。1.3 主要研究?jī)?nèi)容本文通過對(duì)遺傳算法的研究，并且利用Visual C+集成開發(fā)環(huán)境將其編程實(shí)現(xiàn)來

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

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

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

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

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

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

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

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

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

23、用交叉算子來產(chǎn)生新的個(gè)體。交叉運(yùn)算在選擇運(yùn)算之后，兩個(gè)相互配對(duì)的染色體按某種方式交換其部分基因，從而產(chǎn)生新的問題解。交叉運(yùn)算是遺傳算法區(qū)別于其他算法的重要特征，充當(dāng)著重要的作用，是產(chǎn)生新個(gè)體的主要方式。常用的交叉算子有：?jiǎn)吸c(diǎn)交叉算子、雙點(diǎn)交叉算子、均勻交叉算子、順序交叉算子OX）、部分映射交叉算子 變異算子：在生物的遺傳和自然進(jìn)化中，細(xì)胞的分裂復(fù)制環(huán)節(jié)有可能會(huì)因?yàn)槟承┡既灰蛩氐挠绊懚l(fā)生一些復(fù)制差錯(cuò)，就會(huì)導(dǎo)致生物的某些基因發(fā)生變異，從而產(chǎn)生新的個(gè)體。在遺傳算法中，變異操作也是如此。交叉操作是產(chǎn)生新個(gè)體的主要方式，它決定了算法的全局搜索能力。而變異操作則起著輔助作用，它提高了算法的局部搜索能力，

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

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

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

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

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

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

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

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

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

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

34、國(guó)良等介紹了四種主要的變異技術(shù)：1）點(diǎn)位變異，變異僅以某一很小的概率對(duì)串的某些位值變異；2）逆轉(zhuǎn)變異，在串中隨機(jī)選擇兩點(diǎn)，再將這兩點(diǎn)內(nèi)的內(nèi)容按反序插入到原來的位置中。插入變異，從串中隨機(jī)選擇1個(gè)碼，將此碼插入隨機(jī)選擇的插入點(diǎn)之后。本文采用對(duì)換變異操作。代碼見附錄。此外，對(duì)于變異操作還有一些變體形式，如Sushil Jouis提出的貪心對(duì)換變異、謝勝利17等提出倒位變異算子。3.2 不同參數(shù)下的計(jì)算結(jié)果對(duì)比本文采用網(wǎng)絡(luò)上已有的城市距離矩陣來驗(yàn)證所寫程序的正確性: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的對(duì)比在理論上，遺傳算法中初始種群的個(gè)數(shù)決定了種群個(gè)體的多樣性。初始種群過小容易導(dǎo)致程序陷入局部最優(yōu)，而無法得到近似的最優(yōu)解。增加種群個(gè)數(shù)雖然可以避免陷入局部最優(yōu)，但是種群過大會(huì)減慢程序的運(yùn)算速度，降低算法效率。下面是初始種群10和100的結(jié)果對(duì)比。下表為交叉率Pc=0.9，變異率 Pm=0.01,初始種群分別為10,100，遺傳代數(shù)分別為100,200的實(shí)驗(yàn)結(jié)果對(duì)比：表3.2 不同初始種群的算法結(jié)果對(duì)比表次數(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é)果非常顯然地表示出了當(dāng)初始種群個(gè)數(shù)增加后，獲得的平均解更接近全局最優(yōu)解。但增加初始種群同時(shí)會(huì)增加的算法的循環(huán)次數(shù)，從而降低了算法的運(yùn)算效率。而選取初始種群為10，遺傳代數(shù)為100的個(gè)體，除去獲得全局最優(yōu)解的個(gè)體，然后計(jì)算獲得最優(yōu)解的代數(shù)的平均值：49，數(shù)據(jù)表現(xiàn)出算法在沒有獲得全局最優(yōu)解的前提下過早的確定問題解。原因：初始種群個(gè)數(shù)過少，導(dǎo)致陷入局部最優(yōu)解。3.2.2不同交叉率和變異率的對(duì)比1）下面是初始種群為10

39、的模塊。設(shè)定相同的交叉率、不同的變異率來觀察兩組計(jì)算的對(duì)比結(jié)果：表3.2 相同交叉率、不同變異率的算法結(jié)果對(duì)比表?xiàng)l件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é)果可觀察到：在眾多計(jì)算結(jié)果未得到全局最優(yōu)解的計(jì)算中，狀態(tài)比起狀態(tài)來，過早收斂，從而降低了其抑制早熟的能力。 初始種群的大小決定了種群的多樣性。種群個(gè)體過少會(huì)導(dǎo)致算法過早收斂，從而陷入局部

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