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

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

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個(gè)不同的初始特征組合，分別計(jì)算判別值，然后取最大的2個(gè)組合（1,2,3,4,9和1,3,5,7,8）進(jìn)行雜交，即互換部分相異的特征（4和7），得到新的兩個(gè)特征組合（1,2,3,7,9和1,3,4,5,8）,

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

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

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

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