【正文】 不適應(yīng)者淘汰的自然法則。 [5] （ 2）選擇 根據(jù)適者生存原則選擇下一代的個(gè)體。 通常以隨機(jī)方法產(chǎn)生串或個(gè)體的集合 bi,i＝ 1， 2， ...n。這個(gè)初始的群體也就是問(wèn)題假設(shè)解的集合。一般取 Pm＝ 0． 010． 2。一般取 Pc 。一般 n＝ 30 （ 3）遺傳算法自身參數(shù)設(shè)定 遺傳算法自身參數(shù)有 3 個(gè)，即群體大小 n、交叉概率 Pc和變異概率 Pm。串長(zhǎng)度及編碼形式對(duì)算法收斂影響極大 （ 2）適應(yīng)函數(shù)的確定 適應(yīng)函數(shù) fitness function 也稱(chēng)對(duì)象函數(shù) object function ，這是問(wèn)題求解品質(zhì)的測(cè)量函數(shù)；往往也稱(chēng)為問(wèn)題的“環(huán)境”。 法在應(yīng)用中關(guān)鍵的問(wèn)題 （ 1）串的編碼方式 這本質(zhì)是問(wèn)題編碼。 3 Holland 摸式定理 低階，短長(zhǎng)度的模式在群體遺傳過(guò)程中將會(huì)按指數(shù)規(guī)律增加。模式中第 1 個(gè)數(shù)字串和最后 一個(gè)數(shù)字串間的距離稱(chēng)為模式的長(zhǎng)度，并用δ H 表示。 例如： H 1 x x 0 x x 是一個(gè)模式。 遺傳算法的基礎(chǔ)理論是摸式定理。這樣的過(guò)程不斷的重復(fù)：每個(gè)“個(gè)體”被評(píng)價(jià)，計(jì)算出適應(yīng)度，兩個(gè)個(gè)體交配，然后突變，產(chǎn)生第三代。根據(jù)這個(gè)概率，新個(gè)體的染色體隨機(jī)的突變，通常就是改變?nèi)旧w的一個(gè)字節(jié)（ 0 變到 1，或者 1 變到 0）。再下一步是突變，通過(guò)突變產(chǎn)生新的“子”個(gè)體。交配父母的染色體相互交換，從而產(chǎn)生兩個(gè)新 的染色體，第一個(gè)個(gè)體前半段是父親的染色體，后半段是母親的，第二個(gè)個(gè)體則正好相反。例如，交配概率為 ，則80%的“夫妻”會(huì)生育后代。之后，被選擇的個(gè)體進(jìn)入交配過(guò)程。選擇則是根據(jù)新個(gè)體的適應(yīng)度進(jìn)行的，適應(yīng)度越高，被選擇的機(jī)會(huì)越高，而適應(yīng)度低的，被選擇的機(jī)會(huì)就低。 下一步是產(chǎn)生下一代個(gè)體并組成種群。種群中的“個(gè)體”被按照適應(yīng)度排序，適應(yīng)度高的在前面。 一開(kāi)始，算法隨機(jī)生成一定數(shù)量的個(gè)體，有時(shí)候操作者也可以對(duì)這個(gè)隨機(jī)產(chǎn)生過(guò)程進(jìn)行干預(yù)，播下已經(jīng)部分優(yōu)化的種子。 在遺傳算法里，優(yōu)化問(wèn)題 的解被稱(chēng)為個(gè)體，它表示為一個(gè)參數(shù)列表，叫做染色體或者基因串。然后，把這些假設(shè)解置于問(wèn)題的“環(huán)境”中，并按適者生存的原則，從中選擇出較適應(yīng)環(huán)境的“染色體”進(jìn)行復(fù)制，再通過(guò)交叉，變異過(guò)程產(chǎn)生更適應(yīng)環(huán)境的新一代“染色體”群。 遺傳算法的原理 遺傳算法 GA 把“問(wèn)題的解”表示成“染色體”，在算法中也即是以二進(jìn)制編碼的串。 （ 8）參數(shù)空間 SP 這是“串空間”在物理系統(tǒng)中的映射，它對(duì)應(yīng)于遺傳學(xué)中的表現(xiàn)型 Phenotype 的集合?；虿僮魇窃诮Y(jié)構(gòu)空間中進(jìn)行的。 （ 6）基因特征值 Gene Feature 在用“二進(jìn)制串”表示整數(shù)時(shí)，基因的特征值與二進(jìn)制數(shù)的權(quán)一致；例如在串 S 1011 中，基因位置 3 中的 1，它的基因特征值為 2；基因位置 1 中的 1，它的基因特征值為 8。基因位置由串從左向右計(jì)算，例如在串 S＝ 1101 中， 0 的基因位置 是 3。它們的值稱(chēng)為等位基因。 （ 4）基因 Gene 基因是串中的元素，基因用于表示個(gè)體的特征。 [19] 這些概念如下： 1 串 String 它是個(gè)體 Individual 的形式，在算法中為二進(jìn)制串，并且對(duì)應(yīng)于遺傳學(xué)中的染色體 Chromosome 。經(jīng)過(guò)存優(yōu)去劣的自然淘汰，適應(yīng)性高的基因結(jié)構(gòu)得以保存下來(lái)。每個(gè)基因有特殊的位置并控制某種特殊性質(zhì)；所以，每個(gè)基因產(chǎn)生的個(gè)體對(duì)環(huán)境具有某種適應(yīng)性。 Mendel 遺傳學(xué)說(shuō)最重 要的是基因遺傳原理。物種每個(gè)個(gè)體的基本特征由后代所繼承，但后代又會(huì)產(chǎn)生一些異于父代的新變化。 Darwin 進(jìn)化論最重要的是適者生存原理。在人工智能研究中，現(xiàn)在人們認(rèn)為“遺傳算法、自適應(yīng)系統(tǒng)、細(xì)胞自動(dòng)機(jī)、混沌理論與人工智能一樣，都是對(duì)今后十年的計(jì)算技術(shù)有重大影響的關(guān)鍵技術(shù)”。 遺傳算法簡(jiǎn)稱(chēng) GA Geic Algorithm ，在本質(zhì)上是一種不依賴(lài)具體問(wèn)題的直接搜索方法。 遺傳算法的概念最早是由 Bagley 在 1967 年提出的；而開(kāi)始遺傳算法的理論和方法的系統(tǒng)性研究的是 1975 年，這一開(kāi)創(chuàng)性工作是由 Michiganand 所實(shí)行。 生物的進(jìn)化是一個(gè)奇妙的優(yōu)化過(guò)程， 它通過(guò)選擇淘汰，突然變異，基因遺傳等規(guī)律產(chǎn)生適應(yīng)環(huán)境變化的優(yōu)良物種。 現(xiàn)在的基因表達(dá)式算法應(yīng)該算是遺傳算法的繼承者 遺傳算法概念 遺傳算法和字面意思一樣，原理是關(guān)于遺傳的算法。 近年來(lái)，遺傳程序設(shè)計(jì)運(yùn)用遺傳算法的思想自動(dòng)生成計(jì)算機(jī)程序解決了許多問(wèn)題，如預(yù)測(cè)、分類(lèi)、符號(hào)回歸和圖像處理等，作為一種新技術(shù)，它已經(jīng)與遺傳算法并駕齊驅(qū)。對(duì)于許多問(wèn)題，包括人工智能和機(jī)器學(xué)習(xí)上的問(wèn)題都可看作是需要發(fā)現(xiàn)一個(gè)計(jì)算機(jī)程序，即對(duì)特定輸入產(chǎn)生特定輸出的程序，形式化為程序歸納，那么遺傳程序設(shè)計(jì)提供了實(shí)現(xiàn)程序歸納的方法。 在標(biāo)準(zhǔn)的遺傳算法中，由定長(zhǎng)字符串 問(wèn)題的可行解 組成的群體借助于復(fù)制、交叉、變異等遺傳操作不斷進(jìn)化找到問(wèn)題的最優(yōu)解或次優(yōu)解。 作為一種通用的問(wèn)題求解方法，遺傳算法采用簡(jiǎn)單的編碼技術(shù)來(lái)表示各種復(fù)雜的結(jié)構(gòu)并通過(guò)對(duì)一組編碼表示進(jìn)行簡(jiǎn)單的遺傳操作和優(yōu)勝劣汰的自然選擇來(lái)指導(dǎo)學(xué)習(xí)和確定搜索的方向。自 1985 年以來(lái) .國(guó)際上已召開(kāi)了多次遺傳算法的學(xué)術(shù)會(huì)議和研討會(huì) .國(guó)際遺傳算法學(xué)會(huì)組織召開(kāi)的 ICGA International Conference on Geic Algorithms 會(huì)議和 FOGA Workshop on Foundation of Geic Algorithms 會(huì)議。該算法由密執(zhí)安大學(xué)教授 Holland 及其學(xué)生于 1975 年創(chuàng)建。目前， 關(guān)于遺傳算法研究的熱潮仍在持續(xù)，越來(lái)越多的從事不同領(lǐng)域的研究人員已經(jīng)或正在置身于有關(guān)遺傳算法的研究或應(yīng)用之中。 1997年， IEEE又創(chuàng)刊了《 Transactions on Evolutionary Computation》。有關(guān)遺傳算法的學(xué)術(shù)論文也不斷在《 Artificial Intelligence》、《 Machine Learning》、《 Information science》、《 Parallel Computing》、《 Geic Programming and Evoluable Machines》、《 IEEE Transactions on Neural Networks》、《 IEEE Transactions on Signal Processing》等雜志上發(fā)表。 1992 年， Koza 發(fā)表了他的專(zhuān)著《遺傳程序設(shè)計(jì) :基于自然選擇法則的計(jì)算機(jī)程序設(shè)計(jì)》”。這些國(guó)際會(huì)議論文，集中反映了遺傳算法近些年來(lái)的最新發(fā)展和動(dòng)向。 在歐洲，從 1990 年 開(kāi)始每隔一年舉辦一次 Parallel Problem Solving from Nature 學(xué)術(shù)會(huì)議，其中遺傳算法是會(huì)議主要內(nèi)容之一。該書(shū)總結(jié)了遺傳算法研究的主要成果，對(duì)遺傳算法及其應(yīng)用作了全面而系統(tǒng)的論述。 1985 年，在美國(guó)召開(kāi)了第一屆遺傳算法國(guó)際會(huì)議（ International Conference on Geic Algorithms ， ICGA），并且成立國(guó)際遺傳算法學(xué)會(huì)（ International Society of Geic Algorithms ， ISGA），以后每?jī)?年舉行一次?？梢哉J(rèn)為， De Jong 的研究工作為遺傳算法及其應(yīng)用打下了堅(jiān)實(shí)的基礎(chǔ)，他所得出的許多結(jié)論，迄今仍具有普遍的指導(dǎo)意義。該論文所做的研究工作，可看作是遺傳算法發(fā)展進(jìn)程中的一個(gè)里程碑，這是因?yàn)?，他?Holland 的模式理論與他的計(jì)算實(shí)驗(yàn)結(jié)合起來(lái)。該理論首次確認(rèn)了結(jié)構(gòu)重組遺傳操作對(duì)于獲得并行性的重 要性。 1975 年Holland 出版了他的著名專(zhuān)著《自然系統(tǒng)和人工系統(tǒng)的自適應(yīng)》（ Adaptation in Natural and Artificial Systems），這是第一本系統(tǒng)論述遺傳算法的專(zhuān)著，因此有人把 1975 年作為遺傳算法的誕生年。此后， Holland 指導(dǎo)學(xué)生完成了多篇有關(guān)遺傳算法研 究的論文。遺傳算法的蓬勃發(fā)展正體現(xiàn)了科學(xué)發(fā)展的這一特點(diǎn)和趨勢(shì)。 geic operator。s geics. Extensive use of geic algorithms and development potential make many scholars indepth study of geic algorithms, and published many books about it. TSP problem is the old classic question and about its research have hundreds of years of time. TSP Traveling Salesman Problem is a kind of a typical NPplete problem, geic algorithms to solve NP problems is a more desirable method. Paper first introduces the characteristics, development direction and major applications of basic geic algorithms, and then discussed for the TSP problem of geic algorithms and geic coding that operator including the selection operator, crossover operator, mutation operator of these three operator and other aspects of the application, make a brief discussion about several coding methods, and improved crossover operator. Then use improved geic algorithm to do the experiment, get the oute and analyze the data. Finally, I do a simple suing about TSP. 【 Keywords】 geic algorithm。最后我做了一個(gè) TSP 簡(jiǎn)單應(yīng)用。 論文首先介紹了遺傳算法的基本原理、遺傳算法的特點(diǎn) ,遺傳算法的發(fā)展方向和它的主要應(yīng)用領(lǐng)域；接著針對(duì) TSP 問(wèn)題論述了遺傳算法在編碼表示和遺傳算子（包括選擇算子，交叉算子，變異算子這三種算子）等方面的應(yīng)用情況，簡(jiǎn)單討論幾種編碼方法，并改進(jìn)了交叉算子。 TSP 問(wèn)題是古老的經(jīng)典的問(wèn)題，有關(guān)的研究有幾百年的時(shí)間。畢業(yè)設(shè)計(jì)（論文）遺傳算法畢業(yè)設(shè)計(jì) 【摘要】遺傳算法 Geic Algorithm, GA 是近年來(lái)迅速發(fā)展起來(lái)的一種全新的隨機(jī)搜索與優(yōu)化算法 ,其基本思想基于 Darwin 的進(jìn)化論和 Mendel 的遺傳學(xué)。遺傳算法的廣泛應(yīng)用和發(fā)展?jié)撃苁购芏鄬W(xué)者深入研究遺傳算法，并出版了很多關(guān)于它的書(shū)籍。 TSP 旅行商問(wèn)題是一類(lèi)典型的 NP 完全問(wèn)題，遺傳算法是解決 NP 問(wèn)題的一種較理想的方法。接著對(duì)改進(jìn)的遺傳算法做了實(shí)驗(yàn)，得出結(jié)果并分析了數(shù)據(jù)。 【關(guān)鍵詞】遺傳算法； TSP；遺傳算子 ；編碼 【 Abstract】 Geic Algorithm Geic Algorithm, GA is a new random search and optimization algorithm ， develop rapidly in recent years, the basic idea of the theory is Darwin and Mendel39。 TSP。 coding 目錄 第一章 遺傳算法理論 4 遺傳算法的起源 4 遺傳算法概念 6 遺傳算法的原理 7 法在應(yīng)用中關(guān)鍵的問(wèn)題 9 法基本操作 9 遺傳算法的特點(diǎn) 10 遺傳算法幾個(gè)主要應(yīng)用領(lǐng)域 11 遺傳算法發(fā)展方向 13 第二章．遺傳算法的基本原理和實(shí)現(xiàn)技術(shù) 15 模式定理 15 編碼技術(shù) 16 群體設(shè)定 16 函數(shù) 17 遺傳操作 17 混合遺傳算法 19 第三章 TSP 問(wèn)題描述與實(shí)算 20 旅行商問(wèn)題描述 20 編碼選擇 21 定 21 適應(yīng)函數(shù)度 21 選擇算子的設(shè)計(jì) 21 交叉算子的設(shè)計(jì) 22 子的設(shè)計(jì) 24 對(duì) TSP 遺傳算法的改進(jìn)： 25 TSP 遺傳算法參數(shù)實(shí)驗(yàn) 25 改進(jìn)的交叉算子：產(chǎn)生多個(gè)個(gè)體的部分映射與順序交叉結(jié)合的算子 . 29 TSP 算法實(shí)例 35 附錄（求 51 個(gè)城市最短距離算法） 39 總結(jié) 51 參考文獻(xiàn) 52 致謝 53 第一章 遺傳算法理論 遺傳算法的起源 當(dāng)前科學(xué)技術(shù)正進(jìn)入多學(xué)科互相交叉、互相滲透、互相影響的時(shí)代，生命科學(xué)與工程科學(xué)的交叉、滲透和相互促進(jìn)是其中一個(gè)典型例子，也是近代科學(xué)技術(shù)發(fā)展的一個(gè)顯著特點(diǎn)。 1967 年， Holland 的學(xué)生在博士論文中首次提出“遺傳算法”（