【正文】 ................................................... 8 遺傳算法用于 TSP 問題 ............................................. 9 編碼表示 .................................................... 9 初始化群體和適應(yīng)度函數(shù)及其終止條件的設(shè)定 .................... 9 選擇算子 ................................................... 10 交叉算子 ................................................... 10 變異算子 ................................................... 11 TSP 問題的總結(jié) ............................................. 11 第四章 應(yīng)用舉例 ........................................................ 12 4． 1 問題陳述 ........................................................ 12 4． 2 詳細(xì)解答過程 .................................................... 12 問題分析 ................................................... 12 實(shí)驗(yàn)原理與數(shù)學(xué)模型 ......................................... 13 MATLAB 求解結(jié)果 ............................................. 15 貴州大學(xué) 第 2 頁 4． 3 求解結(jié)果驗(yàn)證與反思 .............................................. 16 第五章 附錄 ............................................................ 17 5． 1 Matlab 程序代碼 ................................................. 17 參考文獻(xiàn) ................................................................ 22 貴州大學(xué) 第 3 頁 【摘要】 ： 遺傳算法（ Geic Algorithm,GA）是近年來迅速發(fā)展起來的一種全新的隨機(jī)搜索與優(yōu)化算法， 是一種借鑒生物界自然選擇和進(jìn)化機(jī)制發(fā)展起來的高度并行、隨機(jī)、自適應(yīng)搜索算法。近年來世界范圍形成的進(jìn)化計(jì)算熱潮，計(jì)算智能已作為人工智能研究的一個(gè)重要方向，以及后來的人工生命研究興起，使遺傳算法受到廣泛的關(guān)注。遺傳算法的廣泛使用和發(fā)展?jié)撃苁沟煤芏鄬W(xué)者深入研究遺傳算法，并出版了很多關(guān)于它的書籍。 TSP 旅行商問題是一類典型的 NP 完全問題， 遺傳算法是解決 NP問題的一種較理想 的方法。 【關(guān)鍵詞】遺傳算法； TSP； 遺傳算子；編碼 【 Abstract】 Geic Algorithm (based Algorithm, GA) is developed rapidly in recent years a new kind of random search and optimization Algorithm, is a kind of reference for biological mechanism of natural selection and evolution of highly parallel, randomized, adaptive search Algorithm. Its research history is shorter, the early is an attempt to explain plex adaptive process of creatures in nature system, simulation of the evolution mechanism to construct the model of artificial system. Range of evolutionary putation in the world in recent years, putational intelligence has as an important direction of artificial intelligence research, and later the artificial life research, geic algorithm has been widely attention. Its basic idea is based on Darwin39。s geics. The widespread use of geic algorithm and the development potential has led many scholars indepth study geic algorithm, and has published many books about it. The TSP problem is a classic problem of ancient, studies of hundreds of years. TSP traveling salesman problem is a typical NP plete problem, geic algorithm is an ideal method to solve the problem of NP. This paper firstly introduces the basic principle of geic algorithm, geic algorithm, the characteristics of the development direction of geic algorithm and the main application field。TSP。coding 貴州大學(xué) 第 4 頁 第一章 緒 論 遺傳算法 (Geic Algorithm， GA)是近年來迅速發(fā)展起來的一種全新的隨機(jī)搜索與優(yōu)化算法。它起源于達(dá)爾文的進(jìn)化論，是模擬達(dá)爾文的遺傳選擇和自然淘汰的生物進(jìn)化過程的計(jì) 算模型。自1985 年以來，國際上已召開了多次遺傳算法的學(xué)術(shù)會(huì)議和研討會(huì)，國際遺傳算法學(xué)會(huì)組織 召 開 的 ICGA(International Conference on Geic Algorithms)會(huì)議和FOGA(Workshop on Foundation ofGeic Algorithms)會(huì)議，為研究和應(yīng)用遺傳算法提供了國際交流的機(jī)會(huì)。它尤其適用于處理傳 統(tǒng)搜索方法難于解決的復(fù)雜和非線性問題，可廣泛應(yīng)用于組合優(yōu)化、機(jī)器學(xué)習(xí)、自適應(yīng)控制、規(guī)劃設(shè)計(jì)和人工生命等領(lǐng)域。進(jìn)入 80年代，遺傳算法迎來了興盛發(fā)展時(shí)期，無論是理論研究還是應(yīng)用研究都成了十分熱門的話題近年來，遺傳算法已被成功地應(yīng)用于經(jīng)濟(jì)答理、交通運(yùn)輸、工業(yè)設(shè)計(jì)等不同領(lǐng)域．解決了許多問題。 貴州大學(xué) 第 5 頁 第二章 遺傳算法介紹 遺傳算法介紹 遺傳算法（ geic algorithms， GA）是一種模擬自然選擇和遺傳機(jī)制的尋優(yōu)方法， 它是建立在達(dá)爾文的生物進(jìn)化論和孟德爾的遺傳學(xué)說基礎(chǔ)上的算法。遺傳算法就是模仿了生物的遺傳、進(jìn)化原理，并引用了隨機(jī)統(tǒng)計(jì)原理而形成的。受此啟發(fā)， Holland 教授認(rèn)識(shí)到自然遺傳可以轉(zhuǎn)化為人工遺傳算法。 1975 年， Holland 出版了《自然與人工系統(tǒng)中的適應(yīng)性行為》。 20 世紀(jì) 80 年代初， Holland 教授實(shí)現(xiàn)了第一個(gè)基于遺傳算法的機(jī)器學(xué)習(xí)系統(tǒng) 分類器系統(tǒng) (Classifier System 簡稱 CS)，開創(chuàng)了基于遺傳算法的機(jī)器學(xué)習(xí)的新概念。隨著遺傳算法的不斷發(fā)展， 關(guān)于遺傳算法的國際學(xué)術(shù)活動(dòng)越來越多， 遺傳算法已成為一個(gè)多學(xué)科、多領(lǐng)域的重要研究方向。 初始化： 隨機(jī)產(chǎn)生一個(gè)規(guī)模為 P的初始種群 , 其中每個(gè)個(gè)體為一定長度的碼鏈 , 該群體代表優(yōu)化問題的一些可能解的集合。一般來說適應(yīng)度越高 , 解的素質(zhì)越好。 再生 (選擇 ): 根據(jù)每個(gè)個(gè)體的相對(duì)適應(yīng)度 , 計(jì)算每個(gè)個(gè)體的再生次數(shù) , 并進(jìn)行再生操作 , 產(chǎn)生新的個(gè)體加人下一代群體中 , 一般再生的概率與其適應(yīng)度成正比。 變異： 從種群中隨機(jī)地選擇一個(gè)染色體 , 按一定的變異概率 P進(jìn)行基因變異 ,GA 的搜索能力主要是由選擇與交叉賦于的 , 變異算子則保證了算法能搜索到問題空間的每一點(diǎn) , 從而使算法具有全局最優(yōu)性 , 它進(jìn)一步增強(qiáng)了 GA的能力 . 貴州大學(xué) 第 7 頁 重復(fù)： 若發(fā)現(xiàn)最優(yōu)解 , 則算法停止 , 否則轉(zhuǎn) 3 ,對(duì)產(chǎn)生的新一代群體進(jìn)行重新評(píng)價(jià)、選擇、交叉、變異操作 , 如此循環(huán)往復(fù) , 使群體中最優(yōu)個(gè)體的適應(yīng)度和平均適應(yīng)度不斷提高。最早可以追溯到 1759 年