第五章遺傳算法

第5章遺傳算法計算智能與人工智能（Bezdek，1992）

——計算智能取決于制造者提供的數(shù)據(jù)，而不依賴于知識；人工智能則應(yīng)用知識精品。計算智能是一種智力方式的低層認(rèn)知，含有知識的智能是一種中層或高層認(rèn)知系統(tǒng)。人工智能系統(tǒng)：計算智能系統(tǒng)+知識（精品）5.1進(jìn)化計算進(jìn)化計算的研究起源于20世紀(jì)50年代。（如何模仿生物，進(jìn)而將他們運用于復(fù)雜的優(yōu)化問題，成為一個研究熱點）1965年，Holland首次提出了人工遺傳操作的重要性，并把這些應(yīng)用于自然系統(tǒng)和人工系統(tǒng)中。大約在同一時期：

Rechenberg和Schwefel提出了進(jìn)化策略。

Fogel提出了進(jìn)化規(guī)劃。1967年，Bagley在他的論文中首次提出了遺傳算法這一術(shù)語，并討論了遺傳算法在自動博弈中的應(yīng)用。1970年，Cavicchio把遺傳算法應(yīng)用于模式識別中。第一個把遺傳算法應(yīng)用于函數(shù)優(yōu)化的是Hollstien。

1975年是遺傳算法研究的歷史上十分重要的一年。Holland出版了他的著名專著《自然系統(tǒng)和人工系統(tǒng)的適應(yīng)性》該書系統(tǒng)地闡述了遺傳算法的基本理論和方法，并提出了對遺傳算法的理論研究和發(fā)展極為重要的模式理論（schematatheory），該理論首次確認(rèn)了結(jié)構(gòu)重組遺傳操作對于獲得隱并行性的重要性。同年，DeJong完成了他的重要論文《遺傳自適應(yīng)系統(tǒng)的行為分析》。他在該論文中所做的研究工作可看作是遺傳算法發(fā)展過程中的一個里程碑，這是因為他把Holland的模式理論與他的計算使用結(jié)合起來。

1989Goldberg對遺傳算法從理論上，方法上和應(yīng)用上作了系統(tǒng)的總結(jié)。1990年，Koza提出了遺傳程序設(shè)計（GeneticProgramming）的概念。（用于搜索解決特定問題的最適計算機(jī)程序）進(jìn)化計算的三大主流板塊Holland提出的遺傳算法(GeneticAlgorithm)。Rechenberg和Schwefel提出的進(jìn)化策略(EvolutionaryStrategies)。Fogel提出的進(jìn)化規(guī)劃(Evolutionaryprogramming)，又稱為進(jìn)化程序設(shè)計。遺傳算法思想來源于生物進(jìn)化過程,它是基于進(jìn)化過程中的信息遺傳機(jī)制和優(yōu)勝劣汰的自然選擇原則的搜索算法(以字符串表示狀態(tài)空間)。遺傳算法用概率搜索過程在該狀態(tài)空間中搜索，產(chǎn)生新的樣本。5.2遺傳算法遺傳算法的特點特點：通用魯棒次優(yōu)解、滿意解遺傳算法能解決的問題：優(yōu)化NP完全NP難高度復(fù)雜的非線性問題遺傳算法基本機(jī)理遺傳算法先將搜索結(jié)構(gòu)編碼為字符串形式,每個字符串結(jié)構(gòu)被稱為個體。然后對一組字符串結(jié)構(gòu)(被稱為一個群體)進(jìn)行循環(huán)操作。每次循環(huán)被稱作一代,包括一個保存字符串中較優(yōu)結(jié)構(gòu)的過程和一個有結(jié)構(gòu)的、隨機(jī)的字符串間的信息交換過程。類似于自然進(jìn)化，遺傳算法通過作用于染色體上的基因?qū)ふ液玫娜旧w來求解問題。在遺傳算法中，位字符串扮演染色體的作用，單個位扮演了基因的作用，隨機(jī)產(chǎn)生一個體字符串的初始群體，每個個體給予一個數(shù)值評價，稱為適應(yīng)度，取消低適應(yīng)度的個體，選擇高適應(yīng)度的個體參加操作。常用的遺傳算子有復(fù)制、雜交、變異和反轉(zhuǎn)。遺傳算法與傳統(tǒng)優(yōu)化算法的主要不同遺傳算法不是直接作用在參變量集上,而是利用參變量集的某種編碼;遺傳算法不是從單個點,而是在群體中從一個點開始搜索;遺傳算法利用適應(yīng)值信息,無需導(dǎo)數(shù)或其它輔助信息;遺傳算法利用概率轉(zhuǎn)移規(guī)則,而非確定性規(guī)則。遺傳算法的準(zhǔn)備工作確定表示方案;確定適應(yīng)值的度量;確定控制該算法的參數(shù)和變量;確定怎樣指定結(jié)果及程序運行結(jié)束的標(biāo)準(zhǔn)?；具z傳算法基本遺傳算法(SimpleGeneticAlgorithm:SGA)又稱為簡單遺傳算法，只使用選擇算子、交叉算子和變異算子這三種基本的遺傳算子。其遺傳操作簡單、容易理解，是其它遺傳算法的雛形和基礎(chǔ)。基本遺傳算法的構(gòu)成要素（四）1、染色體編碼方法：首先必須對問題的解空間進(jìn)行編碼，使之能用遺傳算法進(jìn)行操作。較常用的是二進(jìn)制編碼方法，現(xiàn)在使用非二進(jìn)制編碼的也逐漸增多。

編碼：將問題結(jié)構(gòu)變換為位串形式編碼表示的過程

解碼：將位串形式編碼表示變換為原問題結(jié)構(gòu)的過程2、適應(yīng)度函數(shù)（fitnessfunction，又稱為適應(yīng)值／適值函數(shù)）用來評價一個染色體的好壞。3、遺傳算子選擇算子(selection)：又稱為復(fù)制算子。按照某種策略從父代中挑選個體進(jìn)入下一代，如使用比例選擇、輪盤式選擇。交叉算子(crossover)：又稱為雜交算子。將從群體中選擇的兩個個體，按照某種策略使兩個個體相互交換部分染色體，從而形成兩個新的個體。如使用單點一致交叉。變異算子(mutation)：按照一定的概率（一般較?。?，改變?nèi)旧w中某些基因的值。4、運行參數(shù)N：群體大小，即群體中包含的個體的數(shù)量T：遺傳算法終止的進(jìn)化代數(shù)。Pc：交叉概率，一般取為0.4～0.99。Pm：變異概率，一般取為0.0001～0.1。輪盤式選擇首先計算每個個體i被選中的概率然后根據(jù)概率的大小將將圓盤分為n個扇形，每個扇形的大小為2πpi。選擇時轉(zhuǎn)動輪盤，參考點r落到扇形i則選擇個體i。......p1p2pir單點一致交叉首先以概率pc從種群中隨機(jī)地選擇兩個個體p1、p2。在{1,2,...,l}內(nèi)隨機(jī)選擇一個數(shù)i,作為交叉的位置，稱為交叉點。然后將兩個個體交叉點后面的部分交換。例如：

0110101100011001100111000110011100101100雜交操作舉例[Crossover][Parents][Offspring]111001000000101111000101011010110101100110111324111001111000101000000101001010110111010110111100110101變異操作簡單的變異操作過程如下:每個位置的字符變量都有一個變異概率,各位置互相獨立。通過隨機(jī)過程選擇發(fā)生變異的位置：產(chǎn)生一個新結(jié)構(gòu),其中是從對應(yīng)位置的字符變量的值域中隨機(jī)選擇的一個取值?？梢酝瑯拥玫健Ｒ恢伦儺愐愿怕蕄m對種群中所有個體的每一位進(jìn)行變異。對于個體pi的第j位，在[0,1]的范圍內(nèi)隨機(jī)地生成一個數(shù)r,如果r<pm,則對第j位取反，否則保持第j位不變。反轉(zhuǎn)操作簡單反轉(zhuǎn)操作的步驟如下:從當(dāng)前群體中隨機(jī)選擇一個結(jié)構(gòu)a=s1s2…sl從中隨機(jī)選擇兩個數(shù)i和j,并定義

i=min{i',j'},j=max{i',j'};顛倒a中位置i、j之間的部分,產(chǎn)生新結(jié)構(gòu)基本遺傳算法隨機(jī)產(chǎn)生一個由固定長度字符串組成的初始群體;對于字符串群體，迭代地執(zhí)行下述步驟，直到選種標(biāo)準(zhǔn)被滿足為止：計算群體中的每個個體字符串的適應(yīng)值;應(yīng)用下述三種操作(至少前兩種)來產(chǎn)生新的群體:復(fù)制:把現(xiàn)有的個體字符串復(fù)制到新的群體中。雜交:通過遺傳重組隨機(jī)選擇兩個現(xiàn)有的子字符串,產(chǎn)生新的字符串。變異:將現(xiàn)有字符串中某一位的字符隨機(jī)變異。把在后代中出現(xiàn)的最高適應(yīng)值的個體字符串指定為遺傳算法運行的結(jié)果。這一結(jié)果可以是問題的解(或近似解)。基本遺傳算法流程圖GEN=0概率地選擇遺傳操作隨機(jī)創(chuàng)建初始群體計算群體中每個個體的適應(yīng)值i:=0顯示結(jié)果結(jié)束GEN:=GEN+1是是否（轉(zhuǎn)下頁）i=N?GEN=T？1否概率地選擇遺傳操作根據(jù)適應(yīng)值選擇一個個體完成交叉i:=i+1i:=i+1復(fù)制個體p(r)選擇（接上頁）基于適應(yīng)值選擇兩個個體把新的兩個孩子加到群體中p(c)交叉變異p(m)把新的孩子加入到群體中完成變異根據(jù)適應(yīng)值選擇一個個體把變異后個體加入到群體中1遺傳算法舉例問題：求Maxf(x)=x2,x[0,31]（1）編碼：x00000--11111

此時取均長為5，每個染色體{0,1}5（2）初始群體生成：群體大小視情況而定，此處設(shè)置為4，隨機(jī)產(chǎn)生四個個體：編碼：01101，11000，01000，10011

解碼：1324819

適應(yīng)度：16957664361（3）適應(yīng)度評價：fitness(x)=x2（4）選擇：選擇概率Pi=fi/ff=1170

個體：01101110000100010011

適應(yīng)度：16957664361選擇概率：0.140.490.060.31選擇結(jié)果：01101110001100010011（5）交叉操作：發(fā)生交叉的概率較大哪兩個個體配對交叉是隨機(jī)的交叉點位置的選取是隨機(jī)的(單點交叉)0110101100110001101111000110011001110000(6)變異：發(fā)生變異的概率很小

(7)新群體的產(chǎn)生:保留上一代最優(yōu)個體，一般為10%左右，至少1個用新個體取代舊個體，隨機(jī)取代或擇優(yōu)取代。

11000，11011，11001，10011

01101，11000，01000，10011(初始種群)（8）重復(fù)上述操作：說明：GA的終止條件一般人為設(shè)置；

GA只能求次優(yōu)解或滿意解。分析：按第二代新群體進(jìn)行遺傳操作，若無變異，永遠(yuǎn)也找不到最優(yōu)解——擇優(yōu)取代有問題。遺傳算法的工作步驟：（1）編碼：將待解空間的解數(shù)據(jù)表示成基因型串結(jié)構(gòu)數(shù)據(jù)（2）初始群體的生成：按照設(shè)定的編碼方案，隨機(jī)產(chǎn)生N個初始串結(jié)構(gòu)數(shù)據(jù)，構(gòu)成一個種群作為初始點開始迭代。（3）適應(yīng)性評估檢測：適應(yīng)度函數(shù)對每個種子進(jìn)行分值評定，表明種子的優(yōu)劣性。（4）選擇：從當(dāng)前群體中選出優(yōu)良的種子作為父代繁殖下一代。常用輪盤賭實現(xiàn)。（5）雜交：按照設(shè)定的雜交率可以得到新一代個體，新個體組合了其父輩個體的特性。（6）變異：對于選中的個體按照變異率改變串結(jié)構(gòu)數(shù)據(jù)中某個串的值。利用遺傳算法求解迷宮

編碼采用一系列的二進(jìn)制位代表可行解的染色體。每個染色體都是一組隨機(jī)的二進(jìn)制位。二進(jìn)制位的長度在整個群體中都是一樣的。以下為一個長為20的染色體的編碼：

01010010100101001111

這可能是一個很差的解，也可能是一個十分完美的解，重要的是每一個單個的染色體都代表了一個可行解。

賭輪選擇法：從種子群體中選擇一些成員的方法，種子被選中的概率和它們的適應(yīng)性分值(適應(yīng)度)成正比，適應(yīng)性分值越高，種子被選中的概率越大。這表明適應(yīng)性強的個體被選中的概率大，同時實現(xiàn)了“適者生存”原則。對n個個體進(jìn)行編號計算從1開始到n結(jié)束的累計概率產(chǎn)生0-1之間的隨機(jī)數(shù)，判斷在累計概率中的位置確定被隨機(jī)選中的個體

雜交率：用來確定兩個種子進(jìn)行局部的互換以產(chǎn)生兩個新的子代的概率。經(jīng)驗表明這一數(shù)值通常取為0.6–1之間是理想的。每一次從群體中選擇兩個種子，再隨機(jī)產(chǎn)生一個0—1之間的數(shù)值，該數(shù)值與雜交率比較來確定是否雜交，如果數(shù)值低于雜交率，就進(jìn)行雜交，然后在種子的長度上隨機(jī)地選擇一個位置，并把在此位置之后的所有位進(jìn)行互換。例如，設(shè)給定的兩個種子串碼為：

10001001110010010 01010001001000011隨機(jī)選擇第10位，互換第10位之后的所有位，兩個種子變?yōu)椋?/p>

10001001101000011 01010001010010010

變異率：就是在一個種子中將位實行翻轉(zhuǎn)的幾率。同生物界一樣，GA中變異發(fā)生的概率很低，通常取值在0.001~0.01之間。變異為新個體的產(chǎn)生提供了機(jī)會。按照設(shè)定的變異率在一個種子中將位實行翻轉(zhuǎn)，即0變1，1變0。

問題描述：創(chuàng)建一個迷宮，它的右邊有一入口，左邊有一出口，并有一些障礙物散布在其中。在出發(fā)點放置一個虛擬的人Bob，然后要為他解決如何尋找路徑的問題，使他能夠找到出口，并避免與所有障礙物相碰撞。

迷宮的表示：通過一個二維整數(shù)數(shù)組，用0來表示開放的空間，1代表墻壁或障礙物。{1，1，1，1，1，1，1，1，1，1，1，1，1，1，11，0，1，0，0，0，0，0，1，1，1，0，0，0，15，0，0，0，0，0，0，0，1，1，1，0，0，0，11，0，0，0，1，1，1，0，0，0，0，0，1，0，11，1，0，0，1，1，1，0，0，0，0，0，1，0，11，0，0，0，0，1，0，0，0，0，1，1，1，0，11，0，1，1，0，0，1，0，0，0，0，0，0，0，81，0，1，1，0，0，0，1，0，0，0，0，0，0，11，1，1，1，1，1，1，1，1，1，1，1，1，1，1}

為染色體編碼：每個染色體必須把Bob的每一個行動編入代碼中。Bob的行動僅限為4個方向，向東，向南，向西，向北，故編碼后的染色體應(yīng)該就是代表這4個方向信息的一個字符串。具體如下：二進(jìn)制代碼十進(jìn)制譯碼代表的方向000向北011向南102向東113向西

對于一個隨機(jī)的二進(jìn)制字符串，就能根據(jù)上表譯出John行動時所遵循的一系列方向。如：

111110011011101110010101

它代表的基因就是：

11，11，10，01，10，11，10，11，10，01，01，01

轉(zhuǎn)為十進(jìn)制就是：

3，3，2，1，2，3，2，3，2，1，1，1

即John將要行走的方向是： 西，西，東，南，東，西，東，西，東，南，南，南#defineCROSSOVER_RATE0.7

雜交率#defineMUTATION_RATE

0.001

變異率#defineCHROMO_LENGTH

70

每個染色體的長度#definePOP_SIZE

140

種群里的種子數(shù)

確定群體大小的一條有用規(guī)則是將基因組的數(shù)目取為染色體長度的２倍1.UpdateFitnessScores（）;

intDiffX=abs(posX-m_iEndX);

intDiffY=abs(posY-m_iEndY);

Score=1/(1+DiffX+DiffY)Epoch（）方法2.創(chuàng)建一個新的群體3.用輪盤賭法選擇2個父輩（parents）4.雜交操作

5.變異操作

Epoch函數(shù)將無止境地重復(fù)，直到一個染色體可以作為解，或到用戶要求停止時為止Bob有時會被粘住在一個局部地區(qū)不確定地逗來逗去，如同一個喝醉了酒的人在試著尋找他的回家的路。這主要由于群體太快地收斂到一個特殊類型的染色體。這樣，由于群體中的成員變得如此相似，c