【正文】 ed by four parameters in the basic geic algorithm: the size of population, terminate generation, crosser probability and mutation probability. Adjust the parameters, run and try for better ones. At last, the application of hybrid geic algorithm is briefly presented. It is pointed out that a better crossover or mutation routine can be found out which retains the structure from the parent chromosomes and still ends up with a legal tour in the child chromosomes, which leads to a better solution than ever before. And the prospect for the future of geic algorithm in solving TSP is made. Keywords: TSP geic algorithm geic operators encoding 引 言 現(xiàn)代科學(xué)理論研究與實(shí)踐中存在著大量與優(yōu)化、自適應(yīng)相關(guān)的問(wèn)題，但除了一些簡(jiǎn)單 的情況之外，人們對(duì)于大型復(fù)雜系統(tǒng)的優(yōu)化和自適應(yīng)問(wèn)題仍然無(wú)能為力。遺傳算法正是借鑒生物的自然選擇和遺傳進(jìn)化機(jī)制而開(kāi)發(fā)出的一種全局優(yōu)化自適應(yīng)概率搜索算法。由于其具有思想簡(jiǎn)單、易于實(shí)現(xiàn)、應(yīng)用效果明顯等優(yōu)點(diǎn)而被眾多應(yīng)用領(lǐng) 域所接受，并在自適應(yīng)控制、組合優(yōu)化、模式識(shí)別、機(jī)器學(xué)習(xí)、人工生命、管理策略等領(lǐng)域得到了廣泛應(yīng)用。遺傳算法是一類具有較強(qiáng)魯棒性的優(yōu)化算法，特別是對(duì)于一些大型、復(fù)雜非線性系統(tǒng)，它更表現(xiàn)出了比其他傳統(tǒng)優(yōu)化方法更加獨(dú)特和優(yōu)越的性能。 遺傳算法是新發(fā)展起來(lái)的一門學(xué)科，各種理論、方法尚未成熟，有待于進(jìn)一步地發(fā)展和完善，但它卻為我們解決許多復(fù)雜問(wèn)題提供了希望。我們相信，隨著研究工作的進(jìn)一步深入和發(fā)展，遺傳算法必將在智能計(jì)算領(lǐng)域中起到關(guān)鍵作用。 最早可以追溯到 1759年 Euler提出的騎士旅行問(wèn)題 。目前求解 TSP問(wèn)題的主要方法有啟發(fā)式搜索法、模擬退火算法、遺傳算法、 Hopfield神經(jīng)網(wǎng)絡(luò)算法、二叉樹(shù)描述算法。遺傳算法就其本質(zhì)來(lái)說(shuō) ， 主要是解決復(fù)雜問(wèn)題的一種魯棒性強(qiáng)的啟發(fā)式隨機(jī)搜索算法 。 第一章 基本遺傳算法 遺傳算法的產(chǎn)生及發(fā)展 最早美國(guó) Ｍ ichigan(密執(zhí)安大學(xué) )的 Holland教授提出，起源于 60年代對(duì)自然和人工自適應(yīng)系統(tǒng)的研究。在一系列研究工作的基礎(chǔ)上 80年代 Goldberg進(jìn)行總結(jié)歸納，形成了遺傳算的基本框架。 2 1967年在其博士論文中首次提出了：“遺傳算法”一詞，發(fā)展了復(fù)制、交叉、變異、顯性、倒位等遺傳算子，創(chuàng)立了自適應(yīng)遺傳算法的概念。 4 1989年出版了專著《搜索、優(yōu)化和機(jī)器學(xué)習(xí)中的遺傳算法 (Geic Algorithms in Search， Optimization and Machine Learning)》，系統(tǒng)總結(jié)了遺傳算法的主要研究成果，全面而完整的論述了遺傳算法的基本原理及其應(yīng)用。 6 1992年將遺傳算法應(yīng)用于計(jì)算機(jī)程序的優(yōu)化設(shè)計(jì)及自動(dòng)生成，提出了遺傳編程 (Geic Programming) 的概念，并成功的將其提出的遺傳編程應(yīng)用于人工智能、機(jī)器學(xué)習(xí)符號(hào)處理等方面。 它是一種全局化搜索算法 ， 尤其適用于傳統(tǒng)搜索算法難于解決的復(fù)雜和非線性問(wèn)題 。遺傳算法中包含了如下 5個(gè)基本要素 : (1) 對(duì)參數(shù)進(jìn)行編碼； (2) 設(shè)定初始種群大小； (3) 適應(yīng)度函數(shù)的設(shè)計(jì)； (4) 遺傳操作設(shè)計(jì)； (5) 控制參數(shù)設(shè)定 (包括種群大小、最大進(jìn)化代數(shù)、交叉率、變異率等 )。這樣，由不同的編碼 方法和不同的遺傳算子就構(gòu)成了各種不同的遺傳算法。基于這個(gè)特點(diǎn)， Goldberg總結(jié)出了一種統(tǒng)一的最基本的遺傳算法 —— 基本遺傳算法（ Simple Geic Algorithms，簡(jiǎn)稱 SGA）。 基本遺傳算法描述： 基本遺傳算法只使用選擇算子 ( Selection Operator)、交叉算子(Crossover Operator)、變異算子 (Mutation Operator)這三種算子。 遺傳算法的應(yīng)用步驟： 第一步： 確定決策變量及其各種約束條件，即確定出個(gè)體的表現(xiàn)型 X和問(wèn)題的解空間。 第三步：確定表示可行解的染色體編碼方法，也即確定出個(gè)體的基因型 X及遺傳算法的搜索空間。 第五步：確定個(gè)體適應(yīng)度的量化評(píng)價(jià)方法，即確定出由目標(biāo)函數(shù)值 f(X)到個(gè)體適應(yīng)度 F(X)的轉(zhuǎn)換規(guī)則。 第七步：確定遺傳算法的有關(guān)運(yùn)行參數(shù)，即確定出遺傳算法的 M、 T、 Pc、 Pm等參數(shù)。 編碼是應(yīng)用遺傳算法時(shí)要解決的主要問(wèn)題，也是設(shè)計(jì) 遺傳算法的一個(gè)關(guān)鍵步驟。 針對(duì)一個(gè)具體問(wèn)題，如何設(shè)計(jì)一個(gè)完美的編碼方案一直是遺傳算法的應(yīng)用難點(diǎn)之一，也是遺傳算法的一個(gè)重要研究方向。 De Jong曾提出了兩條操作性較強(qiáng)的實(shí)用編碼原則： 編碼原則一 (有意義積木塊編碼原則 ):應(yīng)使用能易于產(chǎn)生與所求問(wèn)題相關(guān)的且具有低階，短定義長(zhǎng)度的編 碼方案。 迄今為止人們已經(jīng)提出了許多的編碼方法，總的來(lái)說(shuō)，可以分為三類：二進(jìn)制編碼方法，浮點(diǎn)數(shù)編碼方法，符號(hào)編碼方法。它有如下幾個(gè)優(yōu)點(diǎn)： (1)編碼，解碼簡(jiǎn)單易行 。 (3)符合最小字符集編碼原則 。 二進(jìn)制編碼符號(hào)串的長(zhǎng)度與問(wèn)題所要求的精度有關(guān)。 格雷碼編碼 格雷碼，連續(xù)的兩個(gè)整數(shù)所對(duì)應(yīng)的編碼值之間只有一個(gè)碼位不相同。這個(gè)特點(diǎn)是遺傳算法中使用格雷碼進(jìn)行個(gè)體編碼的主要原因。 (2)交叉，變異等遺傳操作易于實(shí)現(xiàn)。 (4)便于用模式定理對(duì)算法進(jìn)行理論分析。格雷碼到二進(jìn)制碼的轉(zhuǎn)換公式： 格雷碼編碼方法是二進(jìn)制編碼方法的一種變形，其編碼精度與相同長(zhǎng)度二進(jìn)制編碼方法的精度相同。 符點(diǎn)數(shù)編碼 符點(diǎn)數(shù)編碼方法 :指?jìng)€(gè)體的每個(gè)基因值用某一范圍內(nèi)的一個(gè)浮點(diǎn)數(shù)來(lái)表示個(gè)體的編碼長(zhǎng)度等于其決策變量的個(gè)數(shù)，個(gè)體變量的長(zhǎng)度等于去決策變量的真實(shí)值，所以也叫真值編碼方法．它有以下幾個(gè)優(yōu)點(diǎn)： (1)適合于在遺傳算法中表示范圍較大的數(shù)。 (3)便于較大空間的遺傳搜索。 (5)便于遺傳算法與經(jīng)典優(yōu)化方法的混合使用。 (7)便于處理復(fù)雜的決策變量約束條件。 (2)便于在遺傳算法中利用所求解問(wèn)題的專門知識(shí)。 但對(duì)于使用符號(hào)編碼方法的遺傳算法，一般需要認(rèn)真設(shè)計(jì)交叉、變異等遺傳運(yùn)算的操作方法，以滿足問(wèn)題的各種約束要求，這樣才能提高算法的搜索性能。 參數(shù)編碼 參數(shù)編碼方法是對(duì)含有多個(gè)變量的個(gè)體進(jìn)行編碼的方法，包含兩種編碼方法： 多參數(shù)級(jí) 聯(lián)編碼方法：將各個(gè)參數(shù)分別以某種編碼方法進(jìn)行編碼，然后再將它們的編碼按一定順序聯(lián)接在一起就組成了表示全部參數(shù)的個(gè)體編碼。 適應(yīng)度函數(shù) 在研究自然界中生物的遺傳和進(jìn)化現(xiàn)象時(shí)，生物學(xué)家使用適應(yīng)度這個(gè)術(shù)語(yǔ)來(lái)度量某個(gè)物種對(duì)其生存環(huán)境的適應(yīng)程度。適應(yīng)度較高的個(gè)體遺傳到下一代的概率就相對(duì)大一些；而適應(yīng)度較低的個(gè)體遺傳到下一代的概率就 相對(duì)較小一些。 根據(jù)個(gè)體的適應(yīng)值，就可決定在此環(huán)境下的生存能力。遺傳算法僅使用所求問(wèn)題的目標(biāo)函數(shù)值就可以得到下一步的有關(guān)搜索信息。 由于個(gè)體適應(yīng)度大小決定該個(gè)體被遺傳到下一代群體中的概率。 (2)由個(gè)體的表現(xiàn)型可計(jì)算出對(duì)應(yīng)個(gè)體的目標(biāo)函數(shù)值。 但是，在僅用適應(yīng)度函數(shù)來(lái)計(jì)算個(gè)體適應(yīng)度時(shí) ,有些遺傳算法收斂很快 ,有些遺傳算法收斂很慢，因此在運(yùn)行到不同的階段時(shí)須對(duì)個(gè)體的適應(yīng)度進(jìn)行適當(dāng)?shù)臄U(kuò)大或縮小。 個(gè)體適應(yīng)度尺度變換的三種方法： 線性尺度變換公式如下： F＇ =aF+b F— 原適應(yīng)度； F＇ — 尺度變換后的新適應(yīng)度； a和 b— 系數(shù)。 指數(shù)尺度變換公式如下： F＇ =exp(β F) 系數(shù)β決定了選擇的強(qiáng)制性。遺傳算法中的選擇操作就是用來(lái)確定如何從父代群體中按某種方法選取哪些個(gè)體遺傳到下一代群體中的一種遺傳運(yùn)算。選擇的主要目的為了避免基因缺失、提高全局收斂性和計(jì)算效率。 最常用的幾種選擇策略有以下幾種： (1) 輪盤賭選擇 (Roulette Wheel Selection) 個(gè)體適應(yīng)度按比例轉(zhuǎn)換為選中概率，將輪盤分成 n個(gè)扇區(qū)進(jìn)行 n次選擇，產(chǎn)生 n個(gè)0～ 1之間的隨機(jī)數(shù)相當(dāng)于轉(zhuǎn)動(dòng) n次輪盤，可以獲得 n次轉(zhuǎn)盤停止時(shí)指針位置，指針停放在某一扇區(qū)，該扇區(qū)代表的個(gè)體被選中。 (2) 最優(yōu)保存策略選擇 (Elitist selection) 在遺傳算法的運(yùn) 行過(guò)程中，通過(guò)對(duì)個(gè)體進(jìn)行交叉、變異等遺傳操作而不斷產(chǎn)生新的個(gè)體，雖然隨著群體的進(jìn)化過(guò)程會(huì)產(chǎn)生出越來(lái)越多的優(yōu)良個(gè)體，但由于遺傳操作的隨機(jī)性，它們也有可能破壞掉當(dāng)前群體中適應(yīng)度最好的個(gè)體。 (3) 排序選擇方法（ Rankbased selection） 主要思想是：對(duì)群體中的所有個(gè)體按其適應(yīng)度大小進(jìn)行排序，基于這個(gè)排序來(lái)分配各個(gè)個(gè)體被選中的概率。由于隨機(jī)操作的原因，這種選擇方法的選擇誤差較大，有時(shí)連適應(yīng)度高的個(gè)體也選不上。 (6) 無(wú)回放隨機(jī)選擇（ Expected value selection） 根據(jù)每個(gè)個(gè)體在下一代群體中的生存期望值來(lái)進(jìn)行隨機(jī)選擇運(yùn)算。 交叉算子 在生物的自然進(jìn)化中，兩個(gè)同源染色體通過(guò)交配而重組，形成新的染色體，從而產(chǎn)生新的個(gè)體或物種。交叉運(yùn)算是指兩個(gè)相互配對(duì)的染色體按某種方式交換其部分基因，從而形成新個(gè)體。 單點(diǎn)交叉算子 最常用的交叉算子是單點(diǎn)交叉算子。 例如：以下 兩個(gè)個(gè)體在第四個(gè)基因座之后進(jìn)行單點(diǎn)交叉運(yùn)算，得到兩個(gè)新個(gè)體： 單點(diǎn)交叉的重要特點(diǎn)是：若鄰接基因座之間的關(guān)系能夠提供較好的個(gè)體性狀和較高的個(gè)體適應(yīng)度的話，則單點(diǎn)交叉操作破壞這種個(gè)體性狀和降低個(gè)體適應(yīng)度的可能性最小。 雙點(diǎn)交叉的具體操作過(guò)程是： (1) 在相互配對(duì)的兩個(gè)個(gè)體編碼中隨機(jī)設(shè)置兩個(gè)交叉點(diǎn)。 例如 ：以下兩個(gè)個(gè)體在第二、四個(gè)基因座之間進(jìn)行交叉運(yùn)算，得到兩個(gè)新個(gè)體： 均勻交叉算子 均勻交叉 (Uniform Crossover)：是指兩個(gè)配對(duì)個(gè)體的每個(gè)基因 座上的基因都以相同的交叉概率進(jìn)行交換，從而形成兩個(gè)新的個(gè)體。然后根據(jù)交叉區(qū)域內(nèi)各個(gè)基因值之間的映射關(guān)系來(lái)修改交叉區(qū)域之外的各個(gè)基因座的基因值。 例如 ： 以下兩個(gè)個(gè)體選取第三 、 六個(gè)基因座之后進(jìn)行交叉運(yùn)算，得到兩個(gè)新個(gè)體： 順序交叉（ Order Crossover）算子 主要思想：先進(jìn)行常規(guī)的雙點(diǎn)交叉，然后進(jìn)行個(gè)體巡回順序的有效順序修改，修改時(shí) 要盡量維持個(gè)點(diǎn)原有的相對(duì)訪問(wèn)順序。在遺傳算法中的變異運(yùn)算，是指將基因座上的基因值用該基因座的等位基因來(lái)替換，從而產(chǎn)生新個(gè)體。它們共同完成對(duì)搜索空間的全局搜索和局部搜索，使遺傳算法能夠以良好的搜索性能完成最優(yōu)化問(wèn)題的尋優(yōu)過(guò)程。 (2) 維持群體多樣性，防止早熟現(xiàn)象。 運(yùn)行參數(shù) 在遺傳算法中需要選擇的運(yùn)行參數(shù)主要有個(gè)體編碼串長(zhǎng)度 l、群體大小 M、交叉概率 pc、變異概率 pm、 、終止代數(shù) T、代溝 G等。使用二進(jìn)制編碼時(shí)，編碼串長(zhǎng)度 l的選取與問(wèn)題所要求的求解精度有關(guān)；使用浮點(diǎn)數(shù)編碼時(shí)，編碼串長(zhǎng)度 l與決策變量的個(gè)數(shù) n相等；使用符號(hào)變量來(lái)表示個(gè)體時(shí)。 (2) 群體大小 M表示群體中所含個(gè)體的數(shù)量。一般的建議范圍是 20～ 100。交叉操作是產(chǎn)生新個(gè)體的主要方法，一般應(yīng)取較大值，但取值過(guò)大的話，它會(huì)破壞群體中的優(yōu)良模式，對(duì)進(jìn)化運(yùn)算反而產(chǎn)生不利影響；取值過(guò)小的話，產(chǎn)生新個(gè)體的速度較慢。 (4) 變異概率 pm。一般取 ～ 。表示遺傳算法運(yùn)行到指定的進(jìn)化代數(shù)之后就停止，并將當(dāng)前群體中的最佳個(gè)體作為所求問(wèn)題的最優(yōu)解輸出。 (6) 代溝 G。 約束條件的處理方法 主要有搜索空間限定法、可行解變換法、罰函數(shù)法。 TSP問(wèn)題的描述很簡(jiǎn)單，簡(jiǎn)言之就是尋找一條最短的遍歷 n個(gè)城市的路徑，或者說(shuō)搜索整數(shù)子集 X = { 1， 2， … ， n} ( X 的元素表示對(duì) n個(gè)城市的編號(hào) ) 的一個(gè)排列л ( X) = { v1， v2， … ， vn},使 T = ∑ d( vi， vi + 1) + d( vi， vn) 取最小值。 產(chǎn)生初始種群的方法通常有兩種。另一種是某些先驗(yàn)知識(shí)可轉(zhuǎn)變?yōu)楸仨殱M足一組要求，然后在滿足這些要求的解中再隨機(jī)地選取樣本。下面給出了 C語(yǔ)言描述的完全隨機(jī)產(chǎn)生新種群的函數(shù)。 /* Seed the randomnumber generator with current time so that * the numbers will be different every time we run. */ srand( (unsigned)time( NULL) )。xPOPSIZE。yPathlength。