遊戲人工智慧 讀書筆記 （六） AI演算法簡介——演化演算法

來自專欄第九藝術魅影

作者： fled

本文內容包含以下章節：

Chapter 2 AI Methods

Chapter 2.4 Evolutionary Computation

Chapter 2.8 Hybrid Algorithm: Neuroevolution

本書英文版： Artificial Intelligence and Games - A Springer Textbook4

從前面一篇文章可以看到，樹搜索演算法是從初始狀態開始，基於合法的動作來生成一顆樹，樹的葉子節點是終止狀態，然後通過搜索，來找到一條最佳的從初始狀態到終止狀態的路徑。而優化演算法(optimization algorithm)則是基於任務來構造一個目標函數(Objective function），然後在整個解法空間中，來尋找一個可以最大化目標函數的效用（Utility)的策略(Strategy)。

一. Local Search: 爬山演算法和模擬退火

Local Search 是其中最簡單的一種優化演算法，顧名思義，假設一個solution是N維向量，那麼當前給定一個solution （N維空間上的一個點）, 我們就在 附近的區間內尋找一個更好的解法 ,然後再從 出發尋找下一個解法。Local Search在每一代都只保留一個解法，每次都從該解法出發去找尋下一個解法。這個方式其實有點像爬山的過程，因此又叫hill climber演算法。但是如下圖所示，這個演算法很可能會終止在一個local maximum裡面。

為了解決Local Maximum的問題，人們參考突變(mutation)的思想設計了隨機爬山演算法(Randomized Hill Climber), 從當前的狀態 開始，不再是基於梯度的方式，而是隨機的改變 的某些維度來得到一個新的狀態 ，看是否能到達一個更好的狀態，這樣，上圖中的狀態就有機會向左邊轉變，然後跑到global maximum去。這個演算法還是要求突變後的狀態要比原理的狀態好，因此也不能保證一定能找到最優解。

另外一種方法是模擬退火演算法（Simulated Annealing）， 和爬山演算法相比，它的搜索過程引入了隨機因素。這個退火也是來自於對材料退火的原理。

模擬退火來自冶金學的專有名詞退火。退火是將材料加熱後再經特定速率冷卻，目的是增大晶粒的體積，並且減少晶格中的缺陷。材料中的原子原來會停留在使內能有局部最小值的位置，加熱使能量變大，原子會離開原來位置，而隨機在其他位置中移動。退火冷卻時速度較慢，使得原子有較多可能可以找到內能比原先更低的位置。

https://zh.wikipedia.org/wiki/%E6%A8%A1%E6%8B%9F%E9%80%80%E7%81%AB

我們如果把一個解法(solution)看作空間中的一個原子，那麼「加熱」的過程相當於隨機的改變當前的解法，然後得到一個新的解法。這個時候我們就基於Metropolis準則來判斷是否接受新解法：1. 如果新的解法比原來的解法好，我們會接受該解法；2. 如果新的解法比原來的解法差，我們還是有一定的概率來接受新的解法。這個概率是由兩個參數決定的: 1. 兩個解法的Fitting Function的差值（「能量差」） 和 2. 當前的「溫度」（也即是演算法的迭代次數）。 因此如果兩個解法的差距不大，接受新解法的概率越大；在演算法迭代開始的時候，接受新解法的概率也更大一些。參考熱力學定律，在溫度為 時，出現能量差為 的降溫的概率為 , 這個也是我們是否接受新解法的概率。整個模擬退火的偽代碼如下：

def simulated_anneling(): s = s0 #initial solution T = T0 #initial temperature while T > Tmin and E(s) > Emax: s_n = random_new_state(s) #get a new state based on s if E(s_n) > E(s): #get the "energy"(fitness score) of solution s = s_n else: dE = abs(E(s_n) - E(s)) if random(0,1) < exp(dE/T): #accept new solution s = s_n T = r * T # reduce the temperature, 0<r<1

模擬退火演算法與初始值無關，演算法求得的解與初始解狀態S（是演算法迭代的起點）無關；模擬退火演算法具有漸近收斂性，已在理論上被證明是一種以概率1收斂於全局最優解的全局優化演算法；模擬退火演算法具有並行性。

https://zh.wikipedia.org/wiki/%E6%A8%A1%E6%8B%9F%E9%80%80%E7%81%AB

二. 遺傳演算法(Genetic Algorithm)

而如果我們初始化的時候，不是只初始化一個種子，而是同時保留多個不同的solutions,同時更新。每次優化的時候，也不是只保留一個新的解法，而是丟掉比較差的演算法，但保留多個不同的解法，我們就得到了演化演算法的基本思路。

遺傳演算法（Genetic Algorithm，簡稱GA）是一種最基本的演化演算法(Evolutionary Algorithm)，它是模擬達爾文生物進化理論的一種優化模型，是全局的隨機優化演算法（Randomized Global Optimization Algorithms)。遺傳演算法中從一個或多個初始策略開始（稱為初代）, 每一代成為一個種群, 種群中每個個體都是解空間上的一個可行解，通過模擬生物的進化過程，隨機的改變部分策略（突變）或者隨機的合併多個策略（雜交）來得的新的策略（下一代），從而在解空間內搜索最優解。遺傳演算法一般是通過Utility Function(或者在演化演算法中通常叫Fitness Function)來保留當前更好的策略，而去除一些較差的策略（天擇），有些演算法還會隨機的消滅掉部分的策略，而不管它是不是當前比較好的策略（來模擬自然界中的災變，比如毀滅恐龍的小行星 和 打個響指的滅霸）。

在有些時候，我們的解法是有一定的限制(constraint)的，因此隨機的crossover和mutation可能都會產生很多的不合法的解法。但是如果我們給演化的過程增加限制，去除很多的不合法解法的話，很可能我們的演化演算法沒法找到一個很好的solution，因為初期大部分的演化solution都被殺死了。因此人們提出了feasible-infeasible 2-population(FI-2pop)演算法來緩解這個問題。在演化的過程中，演算法維護兩個隊列，一個隊列里只包含可用的解法（feasible),另一個隊列則沒有限制(infeasible)，只要infeasible的隊列中產生了可用解法(feasible solution)，這個解法就會放入feasible的隊列中。通過這樣的方式，FI-2pop找到不同的feasible solution的概率增大了。

三. 進化策略(Evolution Strategy)

在傳統的遺傳演算法中，一般是使用二進位編碼（DNA）來編碼種群中的個體的，這樣最大的好處是做crossover 和 Mutation特別方便，mutation 就是某個位置上的0變成1 或者 1變成0， crossover就可以簡單的定義為異或，或者隨機選取父輩對應位置的編碼就可以了。

但是在很多場景中，個體的特性不是固定的，而是服從某種分布的。比如人的能力，就不是一個固定值，而是會在一定的範圍內波動。通過我們假設這個分布是高斯分布，這樣我們就可以用均值和方差來表示這個分布了，因此和GA相比，進化策略(ES)的演算法表示是兩組實數值的編碼(DNA)，一組代表該維的均值，另一組代表方差。這樣在進化的時候(crossover 和 mutation)也和GA稍有不同，crossover相當於合併兩個高斯分布，通常可以考慮合併高斯分布的均值；mutation則可以改變高斯分布的方差。這個改變的幅度也可以用一個權重來控制。基於不同的合併策略，我們可以得到不同的ES的變種。

四. 多目標演化演算法

另一方面，演化演算法很可能是多目標的(multiobjective)，演化演算法要找到一個帕累托最優（Pareto Optimality)的solution,這個解法要滿足「不可能再改善某些目標的境況，而不使任何其他的目標受損」。通常來說這個解法不是唯一的。在遊戲AI的設計中，我們經常會碰到這樣的問題，比如在設計策略遊戲的過程中，我們希望設計各方的兵種是各有特色的，同時各方的實力又比較平衡的，這方面的比較好的例子有《星際爭霸》。

通常這樣的多目標的優化問題很難用數學的方法來進行優化，但是演化演算法在這上面比較有優勢。 因為演化演算法每代都隨機的全局搜索，可以產生多個候選的解，構成近似問題的Pareto最優解集；同時在種群中，不同的個體可以滿足不同類型的目標函數和約束。常用的多目標演化演算法有GA, 蟻群演算法等，這裡就不詳細的闡述了。

五. 神經進化演算法（Neuroevolution）

前面幾篇文章分別討論了不同類型的AI演算法。但是在實際應用中，我們經常會把不同的AI技術混在一起使用，以期獲得更好的效果。例如，我們可以用演化演算法(GA)來學習行為樹的參數，我們也可以像Deepmind那樣用神經網路來對MCTS做更有效的剪枝(Pruning)。我們通常稱這樣的演算法為混合演算法(Hybrid algorithm)。這裡把神經網路和演化演算法結合的混合演算法就叫做：Neuroevolution。

神經演化演算法（Neuroevolution）主要是用演化學習的思想來調整神經網路的結構和權重。通常我們是用梯度下降的方法來更新神經網路的結構，但是如果我們不能很好的用監督學習的方法來訓練神經網路的時候（例如訓練的神經網路的loss function沒法微分(differentiable)，或者我們沒有一個很好的標註的訓練樣本），這個時候我們就要考慮演化學習的框架了。這個在遊戲AI中經常能夠遇到，比如我們很難定義一個行為是不是好的（如王者榮耀中，一個英雄在某個場景中使用某個技能是好的還是壞的）。而在演化學習的框架下，我們只需要考慮一個對Solution（某個訓練好的神經網路）的度量（fitness function)。其中基於NEAT演算法(NeuroEvolution of Augmenting Topologies 增強拓撲的神經網路進化), 人們開發了可以玩馬里奧的AI，具體的代碼實現可以看下面的鏈接。