【正文】 許多的編碼方法，總的來說，可以分為三類：二進制編碼方法，浮點數(shù)編碼方法，符號編碼方法。 12 格雷碼編碼 格雷碼，連續(xù)的兩個整數(shù)所對應(yīng)的編碼值之間只有一個碼位不相同。格雷碼到二進制碼的轉(zhuǎn)換公式： 格雷碼編碼方法是二進制編碼方法的一種變形，其編碼精度與相同長度二進制編碼方法的精度相同。 (7)便于處理復雜的決策變量約束條件。 適應(yīng)度函數(shù) 在研究自然界中生物的遺傳和進化現(xiàn)象時，生物學家使用適應(yīng)度這個術(shù)語來度量某個物種對其生存環(huán)境的適應(yīng)程度。 由于個體適應(yīng)度大小決定該個體被遺傳到下一代群體中的概率。 指數(shù)尺度變換公式如下： F＇ =exp(β F) 系數(shù)β決定了選擇的強制性。 (2) 最優(yōu)保存策略選擇 (Elitist selection) 在遺傳算法的運行過程中，通過對個體進行交叉、變異等遺傳操作而不斷產(chǎn)生新的個體，雖然隨著群體的進化過程會產(chǎn)生出越來越多的 優(yōu)良個體，但由于遺傳操作的隨機性，它們 15 也有可能破壞掉當前群體中適應(yīng)度最好的個體。 交叉算子 在生物的自然進化中，兩個同源染色體通過交配而重組，形成新的染色 體，從而產(chǎn)生新的個體或物種。 雙點交叉的具體操作過程是： (1) 在相互配對的兩個個體編碼中隨機設(shè)置兩個交叉點。在遺傳算法中的變異運算，是指將基因座上的基因值用該基 因座的等位基因來替換，從而產(chǎn)生新個體。使用二進制編碼時，編碼串長度 l的選取與問題所要求的求解精度有關(guān)；使用浮點數(shù)編碼時，編碼串長度 l與決策變量的個數(shù) n相等；使用符號變量來表示個體時。 (4) 變異概率 pm。 約束條件的處理方法 主要有搜索空間限定法、可行解變換法、罰函數(shù)法。下面給出了 C語言描述的完全隨機產(chǎn)生新種群的函數(shù)。 else code[x][y]=rand()%(Pathlengthy)+1。yPathlength。 順序表示是指所有城市依次排列構(gòu)成一個順序表(order list)， 對于 一條旅程 ， 可以依旅行經(jīng)過順序處理每個城市 ， 每個城市在順序表中的順序就是一個遺傳因子的表示 ， 每處理完一個城市 ， 從順序表中去掉該城市。iMaxPathlength。 b[j]=1。 謝勝利等提出濃度控制策略 ， 當某種個體的濃度超過給定的濃度閥值時減少該種個體的數(shù)量 ， 使之控制在給定的濃度閥值之內(nèi) ， 并隨機產(chǎn)生新的個體以補足種群的規(guī)模 ， 他們通過實驗證明該策略很好的解決了遺傳算法中群體的多樣性問題 。 (3)用迄今為止最好的個體替換掉當前群體中最差的個體。x++) rate(x)。iPathlength。 } } } } } rightvalue(int n) { int i,j。j++) length=l[population[i].Path[j]1][population[i].Path[j+1]1]+length。 int temp_value。 population[j].value=population[i].value 。 population[j].Path[x]=population[i].Path[x] 。i++) path_code(i)。 for(i。 (2)對交叉區(qū)域中的每個基因座Ｐ（Ｐ＝Ｉ＋１， I＋２ … ，Ｊ） ,體Ｔ Ｘ 中去求出 tＱ Ｘ =tＰＹ 的基因座Ｑ，在個體ＴＹ 中求出 tＲＹ ＝ tＰy的基因座Ｒ，然后相互交換基因值 tＱＸ 和 tＰＹ ， tＲＹ 和 tＰy所得的結(jié)果即為ＴＸ１ ，ＴＹ１ 。 while(abs(p2p1)2) { /*srand( (unsigned)time( NULL ) )。jPathlength。jPathlength。 i=rand()%(POPSIZE)。 } (2) 逆轉(zhuǎn)變異 ， 在編碼串中 ， 隨機選擇兩點 ， 再將這兩點內(nèi)的子串按反序插入到原來的位置中。 p2=rand()%Pathlength。i=p1+1。 p2=rand()%(Pathlength1)+1。 } (4) 插入變異 ， 從串中隨機選擇 1個碼 ， 將此碼插入隨機選擇的插入點之后 。 } if(p1p2) { temp=p1。 } 此外 ， 對于變異操作還有一些變體形式 ， 如 Sushil Jouis[19]提出的貪心對換變異(greedyswap mutation)， 其基本思想是從一個染色體中隨機的選擇兩個城市 (即兩個碼值 )， 然后交換它們 ， 得到新的染色體 ， 以旅程長度為依據(jù)比較交換后的染色體與原來的染色體的大小 ， 保留旅程長度值小的染色體 。 將這種算法應(yīng)用于 TSP問題取得了滿意的結(jié)果 ， 把局部優(yōu)化的高效性與遺傳算法的魯棒性很好的結(jié)合起了 。針對上述 10點的測試數(shù)據(jù)，在 Pc=,PM=,100個種群，運行最大代數(shù)為 200的條件下，利用 數(shù)據(jù)，用方法 112進 行測試，出現(xiàn)最好解的代數(shù)、權(quán)值如下 表 43 112方法。 TSP的混和遺傳算法 隨著遺傳算法的發(fā)展 ,遺傳算法廣泛的與其它算法相結(jié)合 ， 產(chǎn)生許多混合遺傳算法(Hybrid geic algorithm)。i) population[x].Path[i]=population[x].Path[i1]。 p2=rand()%(Pathlength2)+2。 population[x].Path[p1]=population[x].Path[p2]。 x=rand()%(POPSIZE)。i++) { insert[ip11]=population[x].Path[i]。 p2=rand()%(Pathlength2)+2。iPOPSIZE。 針對 TSP問題 ， 陳國良等 [4]介紹了四種主要的變異技術(shù)： (1) 點位變異 ， 變異僅以一定的概率 (通常很小 )，對串的某些位做值的變異。i=p2。i=p2。*/ p1=rand()%Pathlength。整個交叉分兩步進行：首先對個體編碼串進行常規(guī)的雙點 交叉操作，然后根據(jù)交叉區(qū)域內(nèi)各個基因值之間的映射關(guān)系來修改交叉區(qū)域之外的各個基因座的基因值。 printf(\n)。 for(i=0。xPathlength。iPOPSIZE。 } mode() { int i,j。 for(j=0。 b[j]=1。i++) b[i]=0。 for(x=0。 最優(yōu)保存策略進化模型的具體操作過程 ： (1)找出當前群體中適應(yīng)度最高的個體和適應(yīng)度最低的個體。 Rudolhp C[4]提出采用精英選擇策略即保持群體中最好的個體不丟失 ， 以保證算法的收斂性 。jPathlength+1。 int i,j,k。 在求解 TSP問題時 ， 采用基于二進制的遺傳算法 ， 基于二進制的遺傳算法不利于交叉和變異操作 。x++) { printf(%3d ,x+1)。yPathlength。另一種是某些先驗知識可轉(zhuǎn)變?yōu)楸仨殱M足一組要求，然后在滿足這些要求的解中再隨機地選取樣本。 (6) 代溝 G。交叉操作是產(chǎn)生新個體的主要方法，一般應(yīng)取較大值，但取值過大的話，它會破壞群體中的優(yōu)良模式，對進化運算反而產(chǎn)生不利影響；取值過小的話，產(chǎn)生新個體的速度較慢。 運行參數(shù) 在遺傳算法中需要選擇的運行參數(shù)主要有個體編碼串長度 l、群體大小 M、交叉概率 pc、變異概率 pm、 、終止代數(shù) T、代溝 G等。 例如 ： 以下兩個個體選取第三 、 六個基因座之后進行交叉運算，得到兩個新個體： 17 順序交叉（ Order Crossover）算子 主要思想：先進行常規(guī)的雙點交叉，然后進行個體巡回順序的有效順序修改，修改時 要盡量維持個點原有的相對訪問順序。 例如：以下兩個個體在第四個基因座之后進行單點交叉運算，得到兩個新個體： 16 單點交叉的重要特點是：若鄰接基因座之 間的關(guān)系能夠提供較好的個體性狀和較高的個體適應(yīng)度的話，則單點交叉操作破壞這種個體性狀和降低個體適應(yīng)度的可能性最小。 (6) 無回放隨機選擇（ Expected value selection） 根據(jù)每個個體在下一代群體中的生存期望值來進行隨機選擇運算。 最常用的 幾種選擇策略有以下幾種： (1) 輪盤賭選擇 (Roulette Wheel Selection) 個體適應(yīng)度按比例轉(zhuǎn)換為選中概率，將輪盤分成 n個扇區(qū)進行 n次選擇，產(chǎn)生 n個 0～ 1之間的隨機數(shù)相當于轉(zhuǎn)動 n次輪盤，可以獲得 n次轉(zhuǎn)盤停止時指針位置，指針停放在某一扇區(qū)，該扇區(qū)代表的個體被選中。 個體適應(yīng)度尺度變換的三種方法： 線性尺度變換公式如下： 14 F＇ =aF+b F— 原適應(yīng)度； F＇ — 尺度變換后的新適應(yīng)度； a和 b— 系數(shù)。遺傳算法僅使用所求問題的目標函數(shù)值就可以得到下一步的有關(guān)搜索信息。 參數(shù)編碼 參數(shù)編碼方法是對含有多個變量的個體進行編碼的方法，包含兩種編碼方法： 多參數(shù)級聯(lián)編碼方法：將各個參數(shù)分別以某種編碼方法進行編碼，然后再將它們的編碼按一定順序聯(lián)接在一起就組成了表示全部 參數(shù)的個體編碼。 (5)便于遺傳算法與經(jīng)典優(yōu)化方法的混合使用。 (4)便于用模式定理對算法進行理論分析。 二進制編碼符號串的長度與問題所要求的精度有關(guān)。 De Jong曾提出了兩條操作性較強的實用編碼原則： 編碼原則一 (有意義積木塊編碼原則 ):應(yīng)使用能易于產(chǎn)生與所求問題相關(guān)的且具有低階，短定義長度的編碼方案。 第五步：確定個體適應(yīng)度的量化評價方法，即確定出由目標函數(shù)值 f(X)到個體適應(yīng)度F(X)的轉(zhuǎn)換規(guī)則?；谶@個特點， Goldberg總結(jié)出了一種統(tǒng)一的最基本的遺傳算法 —— 基本遺傳算法（ Simple Geic Algorithms，簡稱 SGA）。 6 1992年將遺傳算法應(yīng)用于計算機程序的優(yōu)化設(shè)計及自動生成，提出了遺傳編程 (Geic Programming) 的概念，并成功的將其提出的遺傳編程應(yīng)用于人工智能、機器學習符號處理等方面。 7 第一章 基 本遺傳算法 遺傳算法的產(chǎn)生及發(fā)展 最早美國 Ｍ ichigan(密執(zhí)安大學 )的 Holland教授提出，起源于 60年代對自然和人工自適應(yīng)系統(tǒng)的研究。我們相信，隨著研究工作的進一步深入和發(fā)展，遺傳算法必將在智能計算領(lǐng)域中起到關(guān)鍵作用。遺傳算法正是借鑒生物的自然選擇和遺傳進化機制而開發(fā)出的一種全局優(yōu)化自適應(yīng)概率搜索算法。 作者簽 名： 日期： 年 月 日 學位論文版權(quán)使用授權(quán)書 本學位論文作者完全了解學校有關(guān)保留、使用學位論文的規(guī)定，同意學校保留并向國家有關(guān)部門或機構(gòu)送交論文的復印件和電子版，允許論文被查閱和借閱。 1 摘要 I Abstract II 引 言 1 第一章 基本遺傳算法 2 遺傳算法的產(chǎn)生及發(fā)展 ......................................................... 3 基本原理 ..................................................................... 3 遺傳算法的特點 ............................................................... 3 基本遺傳算法描述 ............................................................. 5 遺傳算法構(gòu)造流程 ............................................................. 6 第二章 遺傳算法的實現(xiàn)技術(shù) 6 編碼方法 .................................................................... 7 二進制編碼 ............................................................. 7 格雷碼編碼 ............................................................. 7 符點數(shù)編碼 ............................................................. 8 參數(shù)編碼 ............................................................... 8 適應(yīng)度函數(shù) .....................................................