【正文】 我改進了交叉方式，讓上一代兩個個體通過兩種交叉產(chǎn)生 4 個個體， 4 個個體中和了兩種交叉的優(yōu)點，通過一個選擇找出 4 個中最優(yōu)秀的兩個，作為上一代兩個個體的新一帶，新一帶將和眾多的新一代一起競爭最優(yōu)。 temp1 135792468 temp2 456789123 temp1 中 jcross1 到 jcross2 之間的數(shù)據(jù)復(fù)制到 child1 中相應(yīng)位置。 變異我采用的是倒位變異 對 TSP 遺傳算法的改進： TSP 遺傳算法參數(shù)實驗 遺傳算法自身參數(shù)有 3 個，即群體大小 n、交叉概率 Pc 和變異概率 Pm。遺傳算法通過交叉和變異這一對相互配合又相互競爭的操作而使其具備兼顧全局和局部的均衡搜索能力。例： A 9 8 4 | 5 6 7 | 1 3 2 0 B 8 7 1｜ 2 3 0 | 9 5 4 6 根據(jù)匹配區(qū)域的映射關(guān)系，在其區(qū)域外的相應(yīng)位置標記 H，得到： 9 8 4 | 5 6 7 | 1 H H H 8 H 1 | 2 3 0 | 9 H 4 H 然后移動匹配區(qū)至起點位置，且在其后預(yù)留相等于匹配區(qū)域的空間（ H 數(shù)目），再將“其余的碼”按其相對次序排列在預(yù)留區(qū)后面，得到： 5 6 7 H H H 1 9 8 4 2 3 0 H H H 9 4 8 1 最后將“父串” A， B 的匹配區(qū)域交換，并放置到 ,的預(yù)留區(qū)內(nèi)，就得到了兩個子代： 5 6 7 | 2 3 0 | 1 9 8 4 2 3 0 | 5 6 7 | 9 4 8 1 OX 操作保留了部分城市的相對訪問順序，但是它也更多的產(chǎn)生出了父代巡回路線中所沒有的部分新路線，所以這種操作方法的遺傳特性也不好。 總之：選擇的原則是盡可能保留好的個體，淘汰不好的個體。 “個體”被選擇的概率反映了個體的適應(yīng)度在整個群體的個體適應(yīng)度總和中所占的比例。但是，群體過大，其適應(yīng)度評估次數(shù)增加，所以計算量也增加，從而影響算法效率。 對局部搜索過程所得到的局部最優(yōu)解，再通過編碼過程將它們變換為新的個體，以便能夠以一個性能較優(yōu)的新群體為基礎(chǔ)來進行下一代的遺傳進化操作。但是，在遺傳算法的應(yīng)用中也會出現(xiàn)一些不盡人意的問題，這些問題中最主要的是它容易產(chǎn)生早熟現(xiàn)象、局部尋優(yōu)能力較差等。 變異操作的步驟為：在群體中所有個體的“碼串”范圍內(nèi)隨機的確定基因座，然后以事先設(shè)定的變異概率對這些基因座的基因值進行變異。為 了能夠進行線性組合運算，算術(shù)交叉的操作對象一般是由浮點數(shù)編碼所表示的個體。 ② 交叉設(shè)計和編碼設(shè)計是相互聯(lián)系的。一般將這種方法與其它一些選擇操作配合起來使用，才能有良好的效果。選擇的目的是把“優(yōu)化的解”直接遺傳到下一代或者通過配對交叉產(chǎn)生新的個體再遺傳到下一代。因此必須將目標函數(shù)映射為求最大值形式且適應(yīng)度函數(shù)值非負。但是，群體過大，其適應(yīng)度評估次數(shù)增加，所以計算量也增加，從而影響算法效率。作為對策，可以直接把問題的結(jié)構(gòu)表示為染色體來處理，從 而省去編碼和譯碼的操作。 二維染色體編碼 許多應(yīng)用場合里，問題的解呈二維或多維表示。[3] 模式定理是遺傳算法的理論基礎(chǔ)。[2] 比如模式 110*10*的階為 5，而模式 0*****的階為 1。 引入模式概念并不是僅僅為了描述上的方便。遺傳算法與其他算法和理論的結(jié)合已經(jīng)成為改進遺傳算法的一個非常有效的手段?；煦邕\動具有類似隨機變量的雜亂表現(xiàn)，具有隨機性；“混沌”能在一定范圍內(nèi)按其自身特性不重復(fù)地歷經(jīng)所有狀態(tài)，具有遍歷性；初值條件極其微弱的變化會引起混沌系統(tǒng)行為的巨大變化，具有對初始條件的極度敏感性。 （ 4）模糊遺傳算法 模糊遺傳算法，即融合模糊優(yōu)化設(shè)計思 想的遺傳算法，它把模糊優(yōu)化和遺傳算法優(yōu)化結(jié)合起來，構(gòu)成一種混合優(yōu)化的設(shè)計方法。目前，已有許多學(xué)者將退火機制引入到遺傳操作中，使遺傳操作產(chǎn)生優(yōu)良個體的概率增加，并使遺傳算法的尋優(yōu)能力有 了明顯的提高。目前，對遺傳算法的研究主要集中在數(shù)學(xué)基礎(chǔ)、各環(huán)節(jié)的實現(xiàn)方式以及與其他算法的結(jié)合方面。 Sunil 已成功地開發(fā)了一個基于遺傳算法的數(shù)據(jù)挖掘下具。人工生命與遺傳算法相輔相成，遺傳算法為人下生命的研究提供一個有效的下具，人下生命的研究也必將促進遺傳算法的進一步發(fā)展 .[12] （ 8）遺傳編程 1989 年，美國 Standford 大學(xué)的 Koza 教授發(fā)展了遺傳編程的概念，其基本思想是 :采用樹型結(jié)構(gòu)表示計算機程序，運用遺傳算法的思想，通過自動生成計算機程序來解決問題。如何使這些誤差最小是使計算機視覺達到實用化的重要要求。遺傳算法已在其中得到了初步的應(yīng)用，并顯示出良好的效果。對于非線性、多目標的函數(shù)優(yōu)化問題，用其他算法通常較難求解，但使用遺傳算法卻很方便并可以得到較好的結(jié)果。故而，遺傳算法有很高的容錯能力。 這是遺傳算法與傳統(tǒng)優(yōu)化算法的極大區(qū)別。變異概率 Pm 與生物變異極小的情況一致，所以， Pm 的取值較小，一般取 。對于問題求解角度來講，就是選擇出和最優(yōu)解較接近的中間解。問題的最優(yōu)解將通過這些初始假設(shè)解進化而求出。交叉概率 Pc 太小時難以向前搜索，太大則容易破壞“高適應(yīng)值”的結(jié)構(gòu)。當群體的大小為 n 時，每代處理的模式數(shù)目為 0 n3 。周而復(fù)始，直到終止條件滿足為止。每兩個個體通過交配產(chǎn)生兩個新個體，代替原來的“老”個體，而沒交配的個體則保持不變。這里的“高”是相對于初始的種群的“低適應(yīng)度”來說的。并且，在執(zhí)行遺傳算法之前，給出一群“染色體”，也即是假設(shè)解?；蛭恢脤?yīng)于遺傳學(xué)中的地點 Locus 。 由于遺傳算法是由進化論和遺傳學(xué)機理而產(chǎn)生的直接搜索優(yōu)化方法；故而在這個算法中要用到各種進化和遺傳學(xué)的概念。它認為每一物種在發(fā)展中越來越適應(yīng)環(huán)境。遺傳算法是根據(jù)生物進化思想而啟發(fā)得出的一種全局優(yōu)化算法。遺傳程序設(shè)計運用遺傳算法的思想，常采用樹的結(jié)構(gòu)來表示計算機程序，從而解決問題。 遺傳算法 Geic Algorithm, GA 是近三十年來迅速發(fā)展起來的一種全新的隨機搜索與優(yōu)化算法 ,其基本思想是基于 Darwin 的進化論和 Mendel 的遺傳學(xué)說。 1991 年， 編輯出版了《遺傳算法手冊》（ Handbook of Geic Algorithms），其中包括了遺傳算法在工程技術(shù)和社會生活中的 大量應(yīng)用實例。 進入八十年代，遺傳算法迎來了興盛發(fā)展時期，無論是理論研究還是應(yīng)用研究都成了十分熱門的課題。 1971 年， stien 在他的博士論文中首次把遺傳算法用于函數(shù)優(yōu)化。 【關(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。畢業(yè)設(shè)計（論文）遺傳算法畢業(yè)設(shè)計 【摘要】遺傳算法 Geic Algorithm, GA 是近年來迅速發(fā)展起來的一種全新的隨機搜索與優(yōu)化算法 ,其基本思想基于 Darwin 的進化論和 Mendel 的遺傳學(xué)。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。 1975 年Holland 出版了他的著名專著《自然系統(tǒng)和人工系統(tǒng)的自適應(yīng)》（ Adaptation in Natural and Artificial Systems），這是第一本系統(tǒng)論述遺傳算法的專著，因此有人把 1975 年作為遺傳算法的誕生年。 1985 年，在美國召開了第一屆遺傳算法國際會議（ International Conference on Geic Algorithms ， ICGA），并且成立國際遺傳算法學(xué)會（ International Society of Geic Algorithms ， ISGA），以后每兩 年舉行一次。 1992 年， Koza 發(fā)表了他的專著《遺傳程序設(shè)計 :基于自然選擇法則的計算機程序設(shè)計》”。該算法由密執(zhí)安大學(xué)教授 Holland 及其學(xué)生于 1975 年創(chuàng)建。對于許多問題，包括人工智能和機器學(xué)習(xí)上的問題都可看作是需要發(fā)現(xiàn)一個計算機程序，即對特定輸入產(chǎn)生特定輸出的程序，形式化為程序歸納，那么遺傳程序設(shè)計提供了實現(xiàn)程序歸納的方法。 遺傳算法的概念最早是由 Bagley 在 1967 年提出的；而開始遺傳算法的理論和方法的系統(tǒng)性研究的是 1975 年，這一開創(chuàng)性工作是由 Michiganand 所實行。物種每個個體的基本特征由后代所繼承，但后代又會產(chǎn)生一些異于父代的新變化。 [19] 這些概念如下： 1 串 String 它是個體 Individual 的形式，在算法中為二進制串，并且對應(yīng)于遺傳學(xué)中的染色體 Chromosome 。 （ 6）基因特征值 Gene Feature 在用“二進制串”表示整數(shù)時，基因的特征值與二進制數(shù)的權(quán)一致；例如在串 S 1011 中，基因位置 3 中的 1，它的基因特征值為 2；基因位置 1 中的 1，它的基因特征值為 8。然后，把這些假設(shè)解置于問題的“環(huán)境”中，并按適者生存的原則，從中選擇出較適應(yīng)環(huán)境的“染色體”進行復(fù)制，再通過交叉，變異過程產(chǎn)生更適應(yīng)環(huán)境的新一代“染色體”群。 下一步是產(chǎn)生下一代個體并組成種群。交配父母的染色體相互交換，從而產(chǎn)生兩個新 的染色體，第一個個體前半段是父親的染色體，后半段是母親的，第二個個體則正好相反。 遺傳算法的基礎(chǔ)理論是摸式定理。 法在應(yīng)用中關(guān)鍵的問題 （ 1）串的編碼方式 這本質(zhì)是問題編碼。一般取 Pc 。 [5] （ 2）選擇 根據(jù)適者生存原則選擇下一代的個體。 （ 3）交叉 對于選中用于繁殖下一代的個體，隨機地選擇兩個個體的相同位置，按交叉概率 P 交叉。 例如有個體 S＝ 101011。傳統(tǒng)優(yōu)化算法是從單個初始值迭代求最優(yōu)解的，容易誤入局部最優(yōu)解。 （ 4）遺傳算法最優(yōu) 迫近。 （ 2）組合優(yōu)化 隨著問題規(guī)模的擴大，組合優(yōu)化問題的搜索空間急劇增大，甚者有時無法求到精確最優(yōu)解。例如用遺傳算法進行航空控制系統(tǒng)的優(yōu)化、使用遺傳算法設(shè)計空間交會控制器、基于遺傳算法的模糊控制器的優(yōu)化 設(shè)計、基于遺傳算法的參數(shù)辨識、基于遺傳算法的模糊控制規(guī)則的學(xué)習(xí)、利用遺傳算法進行人工神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)優(yōu)化設(shè)計和“權(quán)值”學(xué)習(xí)等。遺傳算法在這些圖像處理中的優(yōu)化計算方面找到了用武之地。雖然遺 傳編程的理論尚未成熱，應(yīng)用也有一些限制，但它已成功地應(yīng)用于人工智能、機器學(xué)習(xí)等領(lǐng)域。利用該工具對兩個飛機失事的真實數(shù)據(jù)庫進行了數(shù)據(jù)挖掘?qū)嶒灒Y(jié)果表明遺傳算法是進行數(shù)據(jù)挖掘的有效方法之一。其中，尤以遺傳算法與其他算法相結(jié)合方面的研究最為引人關(guān)注。 （ 2）免疫遺傳算法 人工免疫算法受生物免疫系統(tǒng)原理的啟發(fā)，針對求解問題特征進行人工疫苗接種，可充分利用問題本身的信息，和遺傳算法結(jié)合時，遺傳算法的全局搜索能力及免疫算法的局部優(yōu)化相配合，可大大提高搜索效率。其目的是利用模糊優(yōu)化設(shè)計的優(yōu)點，克服一般遺傳算法優(yōu)化設(shè)計存