論文-遺傳算法的基本步驟

1、遺傳算法遺傳算法（Genetic Algorithm）是基于進化論的原理發(fā)展起來的一種廣為應(yīng)用，高效的隨機搜索與優(yōu)化的方法。它從一組隨機產(chǎn)生的初始解稱為“種群”，開始搜索過程。種群中的每個個體是問題的一個解，成為“染色體”是一串符號。這些染色體在每一代中用“適應(yīng)度”來測量染色體的好壞, 通過選擇、交叉、變異運算形成下一代。選擇的原則是適應(yīng)度越高,被選中的概率越大。適應(yīng)度越低，被淘汰的概率越大。每一代都保持種群大小是常數(shù)。經(jīng)過若干代之后，算法收斂于最好的染色體，它很可能是問題的最優(yōu)解或次優(yōu)解。這一系列過程正好體現(xiàn)了生物界優(yōu)勝劣汰的自然規(guī)律。比如有編號為1到10的特征，現(xiàn)在要選取其中的5個，基于遺

2、傳算法的特征選擇可以如下這樣直觀的理解： 下續(xù)（表格） 下續(xù)初始群體第一次迭代第二次迭代特征組合判別值特征組合判別值特征組合判別值1,2,3,4,981,2,3,4,981,3,5,7,9132,3,6,8,971,3,5,7,8101,2,3,7,8106,7,8,9,1041,2,3,7,9121,3,5,7,8101,3,5,7,8101,3,4,5,891,2,3,7,912即設(shè)有4個不同的初始特征組合，分別計算判別值，然后取最大的2個組合（1,2,3,4,9和1,3,5,7,8）進行雜交，即互換部分相異的特征（4和7），得到新的兩個特征組合（1,2,3,7,9和1,3,4,5,8）,

3、然后再計算這兩個新的組合的判別值，和原來的放在一起，再從中選擇2個具有最大判別值的組合進行雜交。如此循環(huán)下去，在某一代的時候就得到了一個最好的特征組合（比如第2代的1,3,5,7,9的特征組合）。當(dāng)然，在實際中每代的個體和雜交的數(shù)量是比較大的。遺傳算法的具體的步驟如下：1.編碼：把所需要選擇的特征進行編號，每一個特征就是一個基因，一個解就是一串基因的組合。為了減少組合數(shù)量，在圖像中進行分塊（比如5*5大小的塊），然后再把每一塊看成一個基因進行組合優(yōu)化的計算。每個解的基因數(shù)量是要通過實驗確定的。2.初始群體（population）的生成：隨機產(chǎn)生個初始串結(jié)構(gòu)數(shù)據(jù)，每個串結(jié)構(gòu)數(shù)據(jù)稱為一個個體。個個

4、體，構(gòu)成了一個群體。GA以這個串結(jié)構(gòu)數(shù)據(jù)作為初始點開始迭代。這個參數(shù)需要根據(jù)問題的規(guī)模而確定。3.交換(crossover)：交換（也叫雜交）操作是遺傳算法中最主要的遺傳操作。由交換概率()挑選的每兩個父代通過將相異的部分基因進行交換（如果交換全部相異的就變成了對方而沒什么意義），從而產(chǎn)生新的個體?？梢缘玫叫乱淮鷤€體，新個體組合了其父輩個體的特性。交換體現(xiàn)了信息交換的思想。4.適應(yīng)度值(fitness)評估檢測：計算交換產(chǎn)生的新個體的適應(yīng)度。適應(yīng)度用來度量種群中個體優(yōu)劣（符合條件的程度）的指標(biāo)值，這里的適應(yīng)度就是特征組合的判據(jù)的值。這個判據(jù)的選取是GA的關(guān)鍵所在。5.選擇（selection）

5、：選擇的目的是為了從交換后的群體中選出優(yōu)良的個體，使它們有機會作為父代為下一代繁殖子孫。遺傳算法通過選擇過程體現(xiàn)這一思想，進行選擇的原則是適應(yīng)性強的個體為下一代貢獻的概率大，選擇實現(xiàn)了達爾文的適者生存原則。本文直接選取交換后的群體中具有最大適應(yīng)度的前個個體作為下一代進行繁殖。這一步驟的存在使得當(dāng)前群體是所有搜索過的解之中是最優(yōu)的前個的集合。6.變異（mutation）：變異首先在群體中隨機選擇一定數(shù)量個體，對于選中的個體以一定的概率（成為變異概率）隨機地改變串結(jié)構(gòu)數(shù)據(jù)中某個基因的值。同生物界一樣，GA中變異發(fā)生的概率很低，通常取值在0.0010.01之間。變異為新個體的產(chǎn)生提供了機會。7.中止

6、。規(guī)則有三種情況：給定一個最大的遺傳代數(shù)MAXGEN(人為事先確定)，算法迭代在達MAXGEN時停止。給定問題一個下界的計算方法，當(dāng)進化中達到要求的偏差時，算法終止。當(dāng)監(jiān)控得到的算法再進化已無法改進解的性能，即解的適應(yīng)度無法再提高，此時停止計算。遺傳算法有如下特點：遺傳算法的處理對象不是參數(shù)本身，而是對參數(shù)集進行了編碼的個體。此操作使得遺傳算法可直接對結(jié)構(gòu)對象進行操作。傳統(tǒng)搜索算法都是單點搜索算法，容易陷入局部的最優(yōu)解。遺傳算法同時處理群體中的多個個體，即對搜索空間中的多個解進行評估，減少了陷入局部最優(yōu)解的風(fēng)險，同時算法本身易于實現(xiàn)并行化。求解時使用特定問題的信息極少，容易形成通用算法程序。由于遺傳算法使用適應(yīng)值這一信息進行搜索，并不需要問題導(dǎo)數(shù)，空間連通、凸性等與問題直接相關(guān)的信息。遺傳算法只需適應(yīng)值和串編碼等通用信息，解的定義域可任意混合，故幾乎可處理任何問題。選擇、交叉和變異都是隨機操作，而不是確定的精確規(guī)則。這說明遺傳算法是采用隨機方法進行最優(yōu)解搜索，選擇體