不一樣的演化演算法

編譯／台大農藝系 林采萱

演化算法

深度學習和神經網路的蓬勃發展，很容易令人以為現今的電腦科學已達到巔峰，無以為繼。畢竟，在人臉識別、西洋棋、圍棋和各類街機遊戲中，神經網絡的表現已逐步超越人類。而深度學習強大的表徵能力、靠著巨量資訊處理在電腦視覺與語音辨識領域取得突破性發展，並在各類遊戲中屢屢擊敗人類玩家，更是讓研究者們趨之若鶩的原因。

神經網路的結構是效仿人類中樞神經系統的訊息處理機制，但難道沒有比這個更具潛力的演算法嗎？在數百萬年的生物演化過程中，經過一系列適者生存的天擇，包含人類大腦在內的精密器官在世代更迭中形成，可見演化不同凡響的潛力。正因如此，電腦科學家一直試圖掌控這種能力，並在30年前第一次將演化演算法投入工廠生產線的優化，短短數載，即已取得卓越的成就，近年更有與深度學習一較高下的趨勢。

演化算法的運作原理與神經網路大相逕庭，以一種看似違反直覺的方式來寫程式碼。傳統的程式碼是在先有特定目標後，依據邏輯原理編寫；而演化演算法所編寫的程式碼，則完全由數十萬個有意義的程式碼片段─簡單如ADD，僅代表數學運算（x + y）/ 2；複雜如VECFROMDOUBLE，表示「如果x是純量，則回傳1-元素的向量x」─隨機排列組合而成，並一次產生數個版本。

由於這些程式碼在一開始都是隨機產生的，因此無法達到預設目標與要求。不過，偶然之間，仍會發現一些程式碼片段表現優於其他程式碼，此一片段便會在下一代被保存並大量複製。而每代間也非完全相同的複製品，必須從中加入一些變化。可以是抽換程式碼中特定片段─類似「點突變」─或將兩筆不同的程式碼各切一半並相互交換─類似有性生殖中發生的「重組」。

2013年，Dennis Wilson和法國Toulouse大學的研究團隊，使用街機學習環境（Arcade Learning Environment，ALE）資料庫中包括Pong、Breakout和Space invader等61款Atari 遊戲，測試演算法的學習能力。這些盛行於1980到1990年代的街機遊戲，其遊戲規則簡單，但要突破關卡仍有難度，常作為AI訓練及測試的框架，並有助於研究人員定量比對不同機器學習方法在遊戲智能領域的表現，也成功證明透過演化演算法，如果開發環境適宜，隨著時間演進，程式碼的表現會變得越來越理想，甚至優於人類所設計的，在在顯示了演化演算法的開發潛力。

笛卡爾遺傳編程

演化演算法其實有很多分支，包含演化策略、演化編程、遺傳算法、遺傳編程等，而Wilson的研究之所以極具特殊性，不僅證明演化演算法也能有優秀表現，更是首次在強化學習的模式下，以笛卡爾遺傳編程（Cartesian Genetic Programming，CGP）開發出成功的遊戲AI。在強化學習（reinforcement learning）的架構下，透過獎勵或懲罰，程序可因應環境而做出改變，獲得最大利益。而笛卡爾遺傳編程是演化演算法中遺傳編程（genetic programming）的一種形式，1997年才由Julian F. Miller等人開發出來。

CGP使用圖形表示法來編碼電腦程序，且採用二維節點網格，其中程序表現為線性的，常以笛卡爾座標表示非迴圈圖，在此演算法中基因型即是表現型。CGP可藉由調整三種參數：行數、列數、levels-back，來控制算法結構及節點間的連接關係。

此外，CGP有三種基因，分別是：函式基因（Function genes）、連結基因（Connection genes）、輸出基因（Output genes）。通常由一組歷經演化後的函式基因定義功能性節點，並透過節點的連結基因連接到程序輸入端與其它功能性節點，程序輸出基因則來自於任何內部節點或是經過演化後輸出座標得來的程序輸入。

CGP玩遊戲的方式與人類十分接近，都是先看到螢幕顯示的畫面才進行反應，所以演算法必須要能分析出遊戲背景與玩家的位置，再來決定該如何移動，才能獲得更多的積分。遊戲指令也與人類相同：上、下、左、右和四個對角線方向等八個按鈕，再加上執行攻擊與否的按鈕，總共18種控制指令，但並非所有遊戲都會全部使用到。

CGP在訓練過程中，也常利用遊戲設定漏洞，自行發展出一些全新且複雜的遊戲策略或特殊的破關技巧。例如「Boxing」拳擊遊戲中，CGP不斷使用撞擊逼迫對方緩慢移動至拳擊場邊緣的圍繩處，藉此贏得比賽；在「Kung Fu Master」遊戲中，CGP發現最有效的得分攻擊方式是蹲伏拳─不僅可以躲過一半的子彈，還能藉機攻擊周遭的任何東西─所以在每個回合中盡可能地維持蹲伏拳，減低死亡率同時增加得分數，確保最大效益。

CGP的程序規模雖小，但相較於其他演算法來說，所需的訓練時間較短。除了能更快產出具體成果，也一解許多理論數學與統計學家對一般機器學習方法的詬病─決策無理論依據。由於人類常常無法釐清AI的內部決策機制，這很可能在實際應用時衍生出法律問題。CGP的架構精簡，可以清楚解析算法的執行與決策，在邏輯推演上更佔優勢。

編譯來源

Emerging Technology from the arXiv, ” Evolutionary algorithm outperforms deep-learning machines at video games“, MIT Technology Review, 2018.

參考資料

1. D.G. Wilson, S. Cussat-Blanc, H. Luga, J. F. Miller, ” Evolving simple programs for playing Atari games“, arXiv preprint, 2018.
2. J.F. Miller, “ Cartesian genetic programming“, Cartesiangp, 2018.

(本文由教育部補助｢AI報報─AI科普推廣計畫」執行團隊編譯)