【正文】 portional model） 適應(yīng)度比例方法是目前遺傳算法中最基本最常用的選擇方法，它也叫“賭輪”或蒙特卡羅（ Monte Carlo）選擇。這種對適應(yīng)度的縮放調(diào)整稱作適應(yīng)度定標。在通常情況下，為了把一個最小化問題轉(zhuǎn)化為最大化問題，只需要簡單的把原函數(shù)乘以 1 即可 . 2 適應(yīng)度尺度變換（適應(yīng)度函數(shù)定標） 應(yīng)用遺傳算法時，常常會出現(xiàn)一些不利于優(yōu)化的現(xiàn)象或結(jié)果。 1 目標函數(shù)到適應(yīng)度函數(shù)的映射 在許多問 題中，目標是求費用函數(shù) g x 的最小值。另一方面，如果群體規(guī)模太小，會使遺傳算法的搜索空間分布范圍有限，因此搜索有可能停止在未成熟階段，導致未成熟收斂。所以在實際應(yīng)用中，群體個數(shù)的取值范圍一般在幾十到幾百。 群體設(shè)定 群體的設(shè)定可以采取下面的策略：根據(jù)問題固有知識，設(shè)法把握最優(yōu)解所占空間在整個問題空間的分布范圍，然后，在此分布范圍內(nèi)設(shè)定初始群體。 多參數(shù)映射編碼 多參數(shù)映射編碼的基本思想是把每個參數(shù)先進行二值編碼得到子串，再把這些子串連成一個完整的染色體。此時若采用一維染色體編碼就顯得不方便了。反之，由遺傳算法空間向問題空間的映射稱作譯碼（ Decoding）。 遺傳算法主要通過遺傳操作對群體中具有某種結(jié)構(gòu)形式的個體施加結(jié)構(gòu)重組處理，從而不斷的搜索出群體中個體間的結(jié)構(gòu)相似性。 定義 模式 H 中第一個確定位置和最后一個確定位置之間的距離稱作該模式的定義距離或定義長度，記作 δ H 。顯然，一個模式的“階數(shù)”越高，其樣本數(shù)就越少，因而確定性越高。因此通過分析模式在遺傳操作下的變化，就可以了解什么性質(zhì)被延續(xù)，什么性質(zhì)被丟棄，從而把握遺傳算法的實質(zhì)，這正是模式定理所要揭示的內(nèi)容。在引入模式概念前，我們看到的遺傳算法是：在某一代中， N 個互不相同的串在選擇、交叉、變異等遺傳算子的作用下產(chǎn)生下一代的 N 個新的互不相同的串?，F(xiàn)在增加一個通配符“ *” ，“ *”既可以被當作“ 0”，又可以被當作“ 1”。 隨著人們對遺傳算法研究的不斷深入，可以預見，會有更多的理論和方法被引入到遺傳算法中來。在表達方式上，量子遺傳算法將量子的態(tài)矢量表述引入染色體編碼；在演化機制上，它利用量子門實現(xiàn)染色體演化?；煦邕\動的上述性質(zhì)作為避免陷入局部極小的優(yōu)化搜索機制，恰好可以彌補遺傳算法易陷入局部最優(yōu)、收斂速度慢的缺陷。其次，在模糊遺傳算法中，采用權(quán)變理論中的以變應(yīng)變的思想。其目的是利用模糊優(yōu)化設(shè)計的優(yōu)點，克服一般遺傳算法優(yōu)化設(shè)計存在的不足，從而使得系統(tǒng)的優(yōu)化設(shè)計更靈活、方便，取得好的設(shè)計效果。常用的小生境遺傳算法大多在對群體進行選擇操作前，計算個體之間的海明距離，如小于事先設(shè)定值，則對“適應(yīng)值”低的個體處以罰函數(shù)，降低其適應(yīng)值。 （ 2）免疫遺傳算法 人工免疫算法受生物免疫系統(tǒng)原理的啟發(fā)，針對求解問題特征進行人工疫苗接種，可充分利用問題本身的信息，和遺傳算法結(jié)合時，遺傳算法的全局搜索能力及免疫算法的局部優(yōu)化相配合，可大大提高搜索效率。從統(tǒng)計物理學的觀點看 ，隨著溫度的降低，物質(zhì)的能量將逐漸趨近于一個較低的狀態(tài)，并最終達到某種平衡。其中，尤以遺傳算法與其他算法相結(jié)合方面的研究最為引人關(guān)注。遺傳算法如何提高遺傳算法跳出局部最優(yōu)的能力和如何提高遺傳算法的收斂速度成為近年來遺傳算法的研究熱點。利用該工具對兩個飛機失事的真實數(shù)據(jù)庫進行了數(shù)據(jù)挖掘?qū)嶒?，結(jié)果表明遺傳算法是進行數(shù)據(jù)挖掘的有效方法之一。 [9] （ 10）數(shù)據(jù)挖掘 數(shù)據(jù)挖掘是近幾年出現(xiàn)的數(shù)據(jù)庫技術(shù)，它能夠從大型數(shù)據(jù)庫中提取隱含的、先前未知的、有潛在應(yīng)用價值的知識和規(guī)則。雖然遺 傳編程的理論尚未成熱，應(yīng)用也有一些限制，但它已成功地應(yīng)用于人工智能、機器學習等領(lǐng)域。人下生命與遺傳算法有著密切的關(guān)系。遺傳算法在這些圖像處理中的優(yōu)化計算方面找到了用武之地。例如，遺傳算法已經(jīng)在移動機器人路徑規(guī)劃、關(guān)節(jié)機器人運動軌跡規(guī)劃、機器人逆運動學求解、細胞機器人的結(jié)構(gòu)優(yōu)化和行為協(xié)調(diào)等方而得到研究和應(yīng)用。例如用遺傳算法進行航空控制系統(tǒng)的優(yōu)化、使用遺傳算法設(shè)計空間交會控制器、基于遺傳算法的模糊控制器的優(yōu)化 設(shè)計、基于遺傳算法的參數(shù)辨識、基于遺傳算法的模糊控制規(guī)則的學習、利用遺傳算法進行人工神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)優(yōu)化設(shè)計和“權(quán)值”學習等。因此目前現(xiàn)實生產(chǎn)中也主要靠一些經(jīng)驗進行調(diào)度。 （ 2）組合優(yōu)化 隨著問題規(guī)模的擴大，組合優(yōu)化問題的搜索空間急劇增大，甚者有時無法求到精確最優(yōu)解。 遺傳算法幾個主要應(yīng)用領(lǐng)域 雖然在各種應(yīng)用領(lǐng)域中，算法的具體實施細節(jié)有各自的特點，但遺傳算法提供了一種求解復雜系統(tǒng)優(yōu)化問題的通用框架，它不依賴于問題的具體領(lǐng)域。 （ 4）遺傳算法最優(yōu) 迫近。遺傳算法只需“適應(yīng)值”和串編碼等通用信息，故幾乎可處理任何問題。傳統(tǒng)優(yōu)化算法是從單個初始值迭代求最優(yōu)解的，容易誤入局部最優(yōu)解。也就是說，變異 增加了全局優(yōu)化的特質(zhì) . （ 5）全局最優(yōu)收斂 Convergence to the global optimum 當最優(yōu)個體的適應(yīng)度達到給定的閥值，或者最優(yōu)個體的適應(yīng)度和群體適應(yīng)度不再上升時，則算法的迭代過程收斂、算法結(jié)束。 例如有個體 S＝ 101011。 例如有個體 S1 100101 S2 010111 選擇它們的左邊 3 位進行交叉操作，則有 S1 010101 S2 100111 一般而言，交叉概率 P 取值為 ― 。 （ 3）交叉 對于選中用于繁殖下一代的個體，隨機地選擇兩個個體的相同位置，按交叉概率 P 交叉。 適應(yīng)度較高的個體，繁殖下一代的數(shù)目較多。 [5] （ 2）選擇 根據(jù)適者生存原則選擇下一代的個體。這個初始的群體也就是問題假設(shè)解的集合。一般取 Pc 。 （ 3）遺傳算法自身參數(shù)設(shè)定 遺傳算法自身參數(shù)有 3 個，即群體大小 n、交叉概率 Pc和變異概率 Pm。 法在應(yīng)用中關(guān)鍵的問題 （ 1）串的編碼方式 這本質(zhì)是問題編碼。模式中第 1 個數(shù)字串和最后 一個數(shù)字串間的距離稱為模式的長度，并用δ H 表示。 遺傳算法的基礎(chǔ)理論是摸式定理。根據(jù)這個概率，新個體的染色體隨機的突變，通常就是改變?nèi)旧w的一個字節(jié)（ 0 變到 1，或者 1 變到 0）。交配父母的染色體相互交換，從而產(chǎn)生兩個新 的染色體，第一個個體前半段是父親的染色體，后半段是母親的，第二個個體則正好相反。之后，被選擇的個體進入交配過程。 下一步是產(chǎn)生下一代個體并組成種群。 一開始，算法隨機生成一定數(shù)量的個體，有時候操作者也可以對這個隨機產(chǎn)生過程進行干預，播下已經(jīng)部分優(yōu)化的種子。然后，把這些假設(shè)解置于問題的“環(huán)境”中，并按適者生存的原則，從中選擇出較適應(yīng)環(huán)境的“染色體”進行復制，再通過交叉，變異過程產(chǎn)生更適應(yīng)環(huán)境的新一代“染色體”群。 （ 8）參數(shù)空間 SP 這是“串空間”在物理系統(tǒng)中的映射，它對應(yīng)于遺傳學中的表現(xiàn)型 Phenotype 的集合。 （ 6）基因特征值 Gene Feature 在用“二進制串”表示整數(shù)時，基因的特征值與二進制數(shù)的權(quán)一致；例如在串 S 1011 中，基因位置 3 中的 1，它的基因特征值為 2；基因位置 1 中的 1，它的基因特征值為 8。它們的值稱為等位基因。 [19] 這些概念如下： 1 串 String 它是個體 Individual 的形式，在算法中為二進制串，并且對應(yīng)于遺傳學中的染色體 Chromosome 。每個基因有特殊的位置并控制某種特殊性質(zhì)；所以，每個基因產(chǎn)生的個體對環(huán)境具有某種適應(yīng)性。物種每個個體的基本特征由后代所繼承，但后代又會產(chǎn)生一些異于父代的新變化。在人工智能研究中，現(xiàn)在人們認為“遺傳算法、自適應(yīng)系統(tǒng)、細胞自動機、混沌理論與人工智能一樣，都是對今后十年的計算技術(shù)有重大影響的關(guān)鍵技術(shù)”。 遺傳算法的概念最早是由 Bagley 在 1967 年提出的；而開始遺傳算法的理論和方法的系統(tǒng)性研究的是 1975 年，這一開創(chuàng)性工作是由 Michiganand 所實行。 現(xiàn)在的基因表達式算法應(yīng)該算是遺傳算法的繼承者 遺傳算法概念 遺傳算法和字面意思一樣，原理是關(guān)于遺傳的算法。對于許多問題，包括人工智能和機器學習上的問題都可看作是需要發(fā)現(xiàn)一個計算機程序，即對特定輸入產(chǎn)生特定輸出的程序，形式化為程序歸納，那么遺傳程序設(shè)計提供了實現(xiàn)程序歸納的方法。 作為一種通用的問題求解方法，遺傳算法采用簡單的編碼技術(shù)來表示各種復雜的結(jié)構(gòu)并通過對一組編碼表示進行簡單的遺傳操作和優(yōu)勝劣汰的自然選擇來指導學習和確定搜索的方向。該算法由密執(zhí)安大學教授 Holland 及其學生于 1975 年創(chuàng)建。 1997年， IEEE又創(chuàng)刊了《 Transactions on Evolutionary Computation》。 1992 年， Koza 發(fā)表了他的專著《遺傳程序設(shè)計 :基于自然選擇法則的計算機程序設(shè)計》”。 在歐洲，從 1990 年 開始每隔一年舉辦一次 Parallel Problem Solving from Nature 學術(shù)會議，其中遺傳算法是會議主要內(nèi)容之一。 1985 年，在美國召開了第一屆遺傳算法國際會議（ International Conference on Geic Algorithms ， ICGA），并且成立國際遺傳算法學會（ International Society of Geic Algorithms ， ISGA），以后每兩 年舉行一次。該論文所做的研究工作，可看作是遺傳算法發(fā)展進程中的一個里程碑，這是因為，他把 Holland 的模式理論與他的計算實驗結(jié)合起來。 1975 年Holland 出版了他的著名專著《自然系統(tǒng)和人工系統(tǒng)的自適應(yīng)》（ Adaptation in Natural and Artificial Systems），這是第一本系統(tǒng)論述遺傳算法的專著，因此有人把 1975 年作為遺傳算法的誕生年。遺傳算法的蓬勃發(fā)展正體現(xiàn)了科學發(fā)展的這一特點和趨勢。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。 論文首先介紹了遺傳算法的基本原理、遺傳算法的特點 ,遺傳算法的發(fā)展方向和它的主要應(yīng)用領(lǐng)域；接著針對 TSP 問題論述了遺傳算法在編碼表示和遺傳算子（包括選擇算子，交叉算子，變異算子這三種算子）等方面的應(yīng)用情況，簡單討論幾種編碼方法，并改進了交叉算子。畢業(yè)設(shè)計（論文）遺傳算法畢業(yè)設(shè)計 【摘要】遺傳算法 Geic Algorithm, GA 是近年來迅速發(fā)展起來的一種全新的隨機搜索與優(yōu)化算法 ,其基本思想基于 Darwin 的進化論和 Mendel 的遺傳學。 TSP 旅行商問題是一類典型的 NP 完全問題，遺傳算法是解決 NP 問題的一種較理想的方法。 【關(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 a