Chapter遺傳算法

1、游戲人工智能遺傳算法（Genetic Algorithm）1遺傳算法定義（1/2）遺傳算法是從代表問題可能潛在的解集的一個(gè)種群（population）開始的，而一個(gè)種群則由經(jīng)過基因（gene）編碼的一定數(shù)目的個(gè)體(individual)組成。每個(gè)個(gè)體實(shí)際上是染色體(chromosome)帶有特征的實(shí)體。染色體作為遺傳物質(zhì)的主要載體，即多個(gè)基因的集合，其內(nèi)部表現(xiàn)（即基因型）是某種基因組合，它決定了個(gè)體的形狀的外部表現(xiàn)，如黑頭發(fā)的特征是由染色體中控制這一特征的某種基因組合決定的。 2遺傳算法定義(2/2)因此，在一開始需要實(shí)現(xiàn)從表現(xiàn)型到基因型的映射即編碼工作。由于仿照基因編碼的工作很復(fù)雜，我們往往

2、進(jìn)行簡化，如二進(jìn)制編碼，初代種群產(chǎn)生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代（generation）演化產(chǎn)生出越來越好的近似解，在每一代，根據(jù)問題域中個(gè)體的適應(yīng)度（fitness）大小選擇（selection）個(gè)體，并借助于自然遺傳學(xué)的遺傳算子（genetic operators）進(jìn)行組合交叉（crossover）和變異（mutation），產(chǎn)生出代表新的解集的種群。這個(gè)過程將導(dǎo)致種群像自然進(jìn)化一樣的后生代種群比前代更加適應(yīng)于環(huán)境，末代種群中的最優(yōu)個(gè)體經(jīng)過解碼（decoding），可以作為問題近似最優(yōu)解。 3遺傳算法共同特征遺傳算法是解決搜索問題的一種通用算法，對于各種通用問題都可以使用。搜索

3、算法的共同特征為： 首先組成一組候選解； 依據(jù)某些適應(yīng)性條件測算這些候選解的適應(yīng)度； 根據(jù)適應(yīng)度保留某些候選解，放棄其他候選解； 對保留的候選解進(jìn)行某些操作，生成新的候選解。4遺傳算法工作過程首先，確定一種編碼方法。將問題的任何一個(gè)潛在可行解能夠編碼表示成為一個(gè)“數(shù)字”染色體。創(chuàng)建一個(gè)由隨機(jī)的染色體（不同的候選解）組成的初始群體，并以強(qiáng)適應(yīng)性為目的培育后代個(gè)體，進(jìn)行進(jìn)化。進(jìn)化過程中要加入少量變異。直到找到解或者無法進(jìn)化。5遺傳算法結(jié)果可能最終收斂到最優(yōu)解可能得到的不是最優(yōu)解也可能得不到解6遺傳算法1）檢查每個(gè)染色體，看它解決問題的性能怎樣，并相應(yīng)的為它分配一個(gè)適應(yīng)性分?jǐn)?shù)。2）從當(dāng)前群體選出2個(gè)

4、成員，選出的概率正比于染色體的適應(yīng)性，適應(yīng)分愈高，被選中的概率愈大。常用方法是賭輪選擇法（roulette wheel selection）3）按照預(yù)先設(shè)定的雜交率（crossover rate），從每個(gè)選中染色體一個(gè)隨機(jī)確定的點(diǎn)上進(jìn)行雜交（crossover）4）按照預(yù)定的變異率（mutation rate），通過對被選染色體的位的循環(huán)，把相應(yīng)的位實(shí)行翻轉(zhuǎn)（flip）5）重復(fù)2，3，4步，直到新的群體被創(chuàng)建出來。7算法說明：把包含5步的一次循環(huán)稱為一個(gè)世代或代（generation）把整個(gè)循環(huán)稱為一個(gè)時(shí)代（epoch）可行解用二進(jìn)制位進(jìn)行編碼。每個(gè)染色體是一組隨機(jī)的二進(jìn)制位。二進(jìn)制位長度在整

5、個(gè)群體中一樣。例如： 100001111通過譯碼就代表當(dāng)前問題的一個(gè)解。初始群體通常情況比較糟。8遺傳算法的核心選擇：根據(jù)各個(gè)個(gè)體的適應(yīng)度，按照一定的規(guī)則或方法，從第t代群體P(t)中選擇出一些優(yōu)良的個(gè)體遺傳到下 一代群體P(t+1)中；交叉：將群體P(t)內(nèi)的各個(gè)個(gè)體隨機(jī)搭配成對，對每一對個(gè)體，以某個(gè)概率(稱為交叉概率）交換它們之間的部分染色體；變異： 對群體P(t)中的每一個(gè)個(gè)體，以某一概率(稱為變異概率)改變某一個(gè)或某一些基因座上的基因值為其他基因值。 9賭輪選擇法染色體被選中的幾率和它們的適應(yīng)性分?jǐn)?shù)成比例，適應(yīng)性分?jǐn)?shù)越高的染色體，被選中的概率也越大。但不保證適應(yīng)性分?jǐn)?shù)最高的染色體成員一

6、定能選入下一代，僅說明它有最大的概率被選中。全體成員的適應(yīng)性分?jǐn)?shù)由一張類似于賭博所用的轉(zhuǎn)輪形狀餅圖來表示10每個(gè)染色體按適應(yīng)性分?jǐn)?shù)分得相應(yīng)的一個(gè)扇區(qū)，適應(yīng)性分?jǐn)?shù)越高，所占區(qū)域面積越大。旋轉(zhuǎn)輪盤，并把一個(gè)小球拋入其中，直到輪盤停止時(shí)，看小球停在哪一部分，就選中它對應(yīng)的那個(gè)染色體。11常用的選擇方法輪盤賭選擇隨機(jī)競爭選擇最佳保留選擇無回放隨機(jī)選擇確定式選擇無回放余數(shù)隨機(jī)選擇均勻選擇最優(yōu)保存策略隨機(jī)聯(lián)賽選擇排擠選擇。12雜交率（1/2）雜交率就是用來確定兩個(gè)染色體進(jìn)行局部位的互換以產(chǎn)生兩個(gè)新的子代的概率。這一數(shù)值經(jīng)常取在0.7左右比較理想。當(dāng)然，具體問題要具體分析。每次從群體中選擇兩個(gè)染色體，同時(shí)生

7、成0和1之間的一個(gè)隨機(jī)數(shù)，然后根據(jù)此數(shù)據(jù)的值來確定兩個(gè)染色體是否需要進(jìn)行雜交。如果數(shù)值低于雜交率（通常0.40.99），就進(jìn)行雜交，否則不雜交。13雜交率（2/2）雜交過程中，沿著染色體的長度隨機(jī)選擇一個(gè)位置，并把此位置之后的所有位進(jìn)行互換。 111100101 111010011 假設(shè)隨機(jī)選擇的位置是12，則雜交后的結(jié)果為： 111100010100 11010011 1 14交叉算法單點(diǎn)交叉兩點(diǎn)交叉多點(diǎn)交叉均勻交叉算術(shù)交叉。交叉算法是產(chǎn)生新個(gè)體的主要算法，它決定了遺傳算法的全局搜索能力。15變異率變異率（突變率）：就是在一個(gè)染色體中將位實(shí)行翻轉(zhuǎn)的幾率。 翻轉(zhuǎn)：0變1，1變0這個(gè)值通常都是很

8、低的。比如0.001通常在0.00010.1 雜交之后，要從頭到尾檢查子代染色體的各個(gè)位，并按所規(guī)定的幾率對其中某些位實(shí)行翻轉(zhuǎn)（突變）。16變異前：0000010000變異后：1000010000變異點(diǎn)17變異的算法適合于二進(jìn)制編碼和浮點(diǎn)數(shù)編碼個(gè)體的幾種變異算子基本位變異均勻變異邊界變異非均勻變異高斯近似變異變異本身是一種隨機(jī)算法，只是產(chǎn)生新個(gè)體的輔助算法，它決定了遺傳算法的局部搜索能力。18遺傳算法的特點(diǎn)（1/3）(1)遺傳算法從問題解的串集開始嫂索，而不是從單個(gè)解開始。這是遺傳算法與傳統(tǒng)優(yōu)化算法的極大區(qū)別。傳統(tǒng)優(yōu)化算法是從單個(gè)初始值迭代求最優(yōu)解的；容易誤入局部最優(yōu)解。遺傳算法從串集開始搜索

9、，覆蓋面大，利于全局擇優(yōu)。 (2)許多傳統(tǒng)搜索算法都是單點(diǎn)搜索算法，容易陷入局部的最優(yōu)解。遺傳算法同時(shí)處理群體中的多個(gè)個(gè)體，即對搜索空間中的多個(gè)解進(jìn)行評(píng)估，減少了陷入局部最優(yōu)解的風(fēng)險(xiǎn)，同時(shí)算法本身易于實(shí)現(xiàn)并行化。 19遺傳算法的特點(diǎn)（2/3）(3)遺傳算法基本上不用搜索空間的知識(shí)或其它輔助信息，而僅用適應(yīng)度函數(shù)值來評(píng)估個(gè)體，在此基礎(chǔ)上進(jìn)行遺傳操作。適應(yīng)度函數(shù)不僅不受連續(xù)可微的約束，而且其定義域可以任意設(shè)定。這一特點(diǎn)使得遺傳算法的應(yīng)用范圍大大擴(kuò)展。 (4)遺傳算法不是采用確定性規(guī)則，而是采用概率的變遷規(guī)則來指導(dǎo)他的搜索方向。 20遺傳算法的特點(diǎn)（3/3）(5)具有自組織、自適應(yīng)和自學(xué)習(xí)性。遺傳算

10、法利用進(jìn)化過程獲得的信息自行組織搜索時(shí)，硬度大的個(gè)體具有較高的生存概率，并獲得更適應(yīng)環(huán)境的基因結(jié)構(gòu)。 21遺傳算法的應(yīng)用（1/3）函數(shù)優(yōu)化。 函數(shù)優(yōu)化是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域，也是遺傳算法進(jìn)行性能評(píng)價(jià)的常用算例，許多人構(gòu)造出了各種各樣復(fù)雜形式的測試函數(shù)：連續(xù)函數(shù)和離散函數(shù)、凸函數(shù)和凹函數(shù)、低維函數(shù)和高維函數(shù)、單峰函數(shù)和多峰函數(shù)等。對于一些非線性、多模型、多目標(biāo)的函數(shù)優(yōu)化問題，用其它優(yōu)化方法較難求解，而遺傳算法可以方便的得到較好的結(jié)果。 22遺傳算法的應(yīng)用（2/3）組合優(yōu)化 隨著問題規(guī)模的增大，組合優(yōu)化問題的搜索空間也急劇增大，有時(shí)在目前的計(jì)算上用枚舉法很難求出最優(yōu)解。對這類復(fù)雜的問題，人們已經(jīng)

11、意識(shí)到應(yīng)把主要精力放在尋求滿意解上，而遺傳算法是尋求這種滿意解的最佳工具之一。實(shí)踐證明，遺傳算法對于組合優(yōu)化中的NP問題非常有效。例如遺傳算法已經(jīng)在求解旅行商問題、 背包問題、裝箱問題、圖形劃分問題等方面得到成功的應(yīng)用。23遺傳算法的應(yīng)用（3/3）此外，GA也在生產(chǎn)調(diào)度問題、自動(dòng)控制、機(jī)器人學(xué)、圖象處理、人工生命、遺傳編碼和機(jī)器學(xué)習(xí)等方面獲得了廣泛的運(yùn)用。 24遺傳算法應(yīng)用幫助Bob回家25問題：這是一個(gè)尋找路徑問題。尋找路徑問題是游戲人工智能的一塊“神圣基石”，使用非常廣泛。問題：一個(gè)迷宮，左邊有一個(gè)入口，右邊有一個(gè)出口，并有一些障礙物散布在其中。假設(shè)有一個(gè)虛擬的人Bob，要他從入口到出口。

12、幫助他尋找路徑，并且避免與所有障礙物相碰撞。26迷宮圖27迷宮的計(jì)算機(jī)表示： 用二維數(shù)組來存儲(chǔ)迷宮。用0表示開放的空間，用1表示墻壁或障礙物，5為入口，8為出口。28迷宮的二維數(shù)組29為染色體編碼（1/2）Bob行動(dòng)分為四個(gè)方向：東，南，西，北。編碼后的染色體代表這四個(gè)方向信息的一個(gè)字符串。二進(jìn)制代碼是進(jìn)制譯碼代表的方向000向東011向西102向南113向北30為染色體編碼（2/2）一個(gè)二進(jìn)制字符串 1111110010101 代表的基因就是： 11,11,10,01,10,11,10,11,10,01,01,01 譯碼為十進(jìn)制： 3,3,2,1,2,3,2,3,2,1,1,1 代表的方向就

13、是： 北,北,西,南,西,北,西,北,西,南,南,南31說明初始，Bob置于迷宮的入口，然后依據(jù)染色體譯出的方向一步步走。如果某個(gè)方向碰壁或遇到障礙物，忽略該指令繼續(xù)執(zhí)行下一條指令。直到用完所有方向或Bob到達(dá)出口為止。適應(yīng)性度量：一個(gè)染色體的適應(yīng)性要看它能讓Bob走到離出口的遠(yuǎn)近程度。讓好的來產(chǎn)生后代，期待它們的子孫中能有比這一次走的離出口更近一點(diǎn)。32適應(yīng)性分?jǐn)?shù)的計(jì)算：Bob距離出口的距離。DiffX=abs（posX-EndX）DiffY=abs（posY-EndY）Diff=DiffX+DiffY+1FitnessScores=1/Diff如果Bob到達(dá)出口，DiffX+DiffY=033參數(shù)說明雜交率選為0.7（0.40.99）變異率選為0.001（0.00010.1）染色體長度為70：表示Bob最大可能移動(dòng)數(shù)目為35步。群體規(guī)模：140（10200之間選定）賭輪選擇法：在整個(gè)適應(yīng)性分?jǐn)?shù)范圍內(nèi)隨機(jī)選取一個(gè)實(shí)數(shù)，通過循環(huán)以考察各個(gè)染色體，把它們適應(yīng)性分?jǐn)?shù)累加起來，直到累加和大于選取的實(shí)數(shù)值，選擇該基因組。34函數(shù)優(yōu)化示例求下列一元函數(shù)的最大值：x-1,2 ，求解結(jié)果精確到6位小數(shù)。35SGA對于本例的編碼 由于區(qū)間長度為3，求解結(jié)果精確到6位小數(shù)，因此可將自變