[EP/GP] Evolution with Internal Observer

• Evolution with Internal Observer

Download: Evolution_TicTacToe_Internal_Observer.zip


多數情況下，在目前的演化程式設計上我們仍然多使用supervised的架構，因為unsupervised模式所造成的時間成本很高，以及訓練後的準確性不優於supervisered，所以多數人仍採用其他透過具有專業知識的方式來做machine learning（reinforcement learning, temporal difference learning）。這裡我沿用[ANN] FeedForward MultiLayer Perceptron的程式來介紹內部觀察者，internal observer的角色在這次的主題範例裡扮演著競爭的標竿，每一代所產生的neural network如果無法在與internal observer競爭之後取得前50％的名次就會被淘汰，這樣的設計方式廣泛使用在一些較複雜且難以以數學模組精準算出誤差的問題，遊戲就是其中之一（當然這裡的tic tac toe並不屬於複雜問題。），比起完全無監督的演化網路來說，有內部觀察者的演化會比較有效率，我的observer可分為三級，是經過我簡單設計出來的AI:

• Level I :ADR (Attack, Defence, Random Move)
• Level II :ADCR (Attack, Defence, Center Move, Random Move)
• Level III :SADCR(Super Attack, Defence, , Center Move, Random Move)

基本上就是基於tic tac toe的規則先做攻擊，再做防守，最後亂數選擇一個位置，其餘的就是選擇中心點，選擇高動線位置，或者是一些例外處理，這裡的等級一跟等級二只差了中心點的選擇而已，而等級三則是做比較多的例外處理。

模擬參數如下：

population size: 100 (50 parent+ 50 offspring)


generation: 1000

Number of games for each neural network: 10

selection: tournament selection with expert observer


• 結果



由圖表數據可以觀察到，使用AI_level3來做observer不到50代就已經有大部分的神經網路可以贏過AI_level3，但是反觀AI_level2跟AI_level1卻發現結果沒有AI_level3來的好，難道是用什麼等級去做訓練才能得到那個等級的能力嗎？

• Average Survival Time



網路在每一代裡的平均存活次數，可以發現年代越高，存活越久，同時也表示著網路已經邁入0成長的狀態。

• Standard Deviation for Number of Win Games



很多情況下Standard Deviation的圖會對應到第一張圖（通常是在網路比較穩定的狀態時），一般來講我都會使用Survival Times跟standard deviation這兩張圖來觀察網路的收斂狀況。

回到先前的問題，使用比較強的AI來做observer不一定比較好？是的，更準確的說應該是observer必須具有更多的隨機性，越強的observer他有更多特殊策略，但卻有可能忽略掉一些基本的策略，以及隨機的多樣性，反而會讓網路趨向只能解決特定的輸入參數，而無法去處理其他更多的輸入變化，進而導致一個網路可以贏過強的策略，卻輸給一個弱的策略。所以最簡易的解決辦法就是在trainer裡加一些隨機程序，我隨便加了一些隨機情況重跑模擬後如下：

• Neural Network v.s. AI



由上圖跟第一張圖做比較可以發現雖然在跟AI_level 3的比較能力有下降一些，AI_level 2則是沒有多大的改變，但是AI_level 1的能力比較卻有明顯的上升，其碼有一半的網路是有能力贏過level 1的。比起原先的數據平均只有10個網路能贏來說，可以說是進步很多。更仔細的觀察 AI_level 1的數據，在40代左右，網路能力瞬間提升到平均有25個網路可以贏過level 1，但是到了1000代，有上升的趨勢，這個能力的提昇是仰賴競爭選擇的方式，所以選擇的壓力控制也是影響著演化的好壞。


一般在做演化計算上我們會特別去注意training set的廣度與深度，才能產生出較好的fitness function。最佳化除了選擇的方式可以改良之外，其他還有網路架構的設計，資料計算的轉換等等都是可以提昇網路能力的方向。同樣的，如果將這樣的觀念套用在沒有專家知識干涉的natural evolution裡，要如何製造好的競爭選擇標竿來產生出較佳解，那就是另一個研究議題了。