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

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

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

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

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

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

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

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

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

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

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

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

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