[EP/GP] random opponent

• random opponent

在EP(evolutionary programming)或者GP(genetic programming)裡，我們要過濾出在這個generation下較良好的strategies時，有可能會需要用到Tournament Selection(競爭式選擇)，而在Tournament Selection裡，變動因子除了winner/loser的value assign，比較的先後之外（depends on your program），還有一個關鍵就是競爭者的選擇。

舉個例子來說，假設我們要從10個strategies裡挑出5個較為優秀的作為下一代的parent，我們可能會亂數挑出3個給每一個strategy去做比較，最後再由比較後的得分高低決定誰要留下誰被淘汰。以下是一個tournament selection選擇實例：

• 每一個generation裡有10個strategies。(5個是parent，5個是經由mutation後的child)
• 每一個strategy要亂數挑出其他3個不重複的strategy做比較。
• 經由一輪的比較之後，挑選top 5的strategy做為下一代的parent。
  

當您的程式符合下述情況之後，做進一步的分析可能會發現，有些strategy被挑出來的次數可能是5次、6次，而有些卻只被挑出1次甚至0次（這樣的情形通常是你的亂數程式沒有規劃好），這樣的出現頻率差異，很有可能會破壞"適者生存，不適者淘汰"的理論，這時條件還要加上下面這一項：

• 每一個strategy被選出來比較的次數皆為3。

加上上面的條件之後，理論上tournament selection會更有效率。

筆者為解決這個問題花了一些時間去產生符合上述情況的程式碼。如下：

Download: ranOpp.c


下載版的原始碼裡有完整的註解，這裡就講解主要的副函式- ranOpp().



整個程式裡最關鍵的陣列變數就是connect，他紀錄著每個strategy跟其他strategy的關聯，假設strategy 0已經跟strategy 1比較過，那connect[0][1]就要設成非零數，所以在初始化過程時除了自己本身要設成1之外，其餘皆設成0，這樣就可以避免產生出的對手是自己的狀況。



在程式碼27~33的初始化後，同一個col裡每一個元素（opp[0~9][col]）都有一個唯一的數值，但是都是連續的，我們要透過上面的程式碼將他們的次序打亂，其中的while迴圈就是要避免兩數交換後，同一個row裡的元素數值跟row的值是一樣的，舉個例子來說，strategy 0的opp的數據如下：

opp[0][0]=2

opp[0][1]=2

opp[0][2]=0

可以看到opp[0][2]的值跟row的值是一樣的，所以程式會繼續再亂數挑選出其他strategy的值來做交換。也許你會有疑問，為什麼opp[0][0]跟opp[0][1]的值是一樣的，因為目前還只是初始化過程，我們還沒正式進入數字對調的主程式片段，也許你又會問那為什麼不將上面的檢驗方式直接整合到後面做處理，答案是可以的，只是如果沒有事先先排開，之後要花多一點心力去排除，也許你還是不懂我在說什麼，總之等你遭遇到錯誤時就會懂了。



最外層的迴圈是col為主，因為我們的亂數組是以col為一個單位，而程式碼44~48是在檢查當前的opp[row][col]的值是否符合程式一開始的要求(不重複且不可為自己)，同時在檢查完時不要忘記更新connect裡的數據，這時你又可能會問為什麼這些程式碼不在35~41行裡一起處理？不要忘了我們的程式是以col為主，每跑完一次後的次序會不一樣，所以不能在一開使就決定所有element的狀態。



這部份就是整個程式的核心演算，因為我們並無法確定數值交換要換幾次，所以使用了while迴圈，當目前這個col內的所有element都check過了才跳出迴圈（程式碼69就是在做確認）。

程式碼52行會先檢測當前的element符不符合規則，如果不符合就要進行亂數交換，也許你會覺得使用亂數交換會不會比較慢，尤其當strategy變很大時，難道就沒有一個比較有規則的交換方式嗎？答案是有的，只是如果要規則化就要分批處理，我想我們目前的集合都很小，一般的電腦足以負荷這種極小規模的亂數交換比對。

例外還有一個很值得一提的就是為什麼connect裡的值不是設成1或0，而是遞增遞減，會這麼做的原因是因為我們的while迴圈的檢測只保證一方的值是合法的，但是卻無法保證另一方的值不會重複，例如strategy 5有下面三個對手

NUMM(5) -> 0 1 1

很顯然的strategy 5他有兩個strategy 1對手，這是不合法的，所以當他的第二個1被換掉時你會將connect[5][1]設成0還是connect[5][1]--？我想這樣解釋你應該很清楚為什麼要遞增遞減了。

從頭到尾我都沒有提到說要如何避免strategy出現的頻率不一，但是在過程中我已經處理掉這個問題了，至於我是怎麼做的呢？我想讀者應該都已經發現，如果還是不了解，那就仔細的去觀察初始化的狀況，以及opp陣列的col值所代表的意義。


以下是模擬數據，模擬10個strategy，分別挑出9個strategy對手出來。當然正常情況下不會有這種需求，就算有也不用用上面的麻煩寫法來產生。這個數據只是要驗證我們的程式是正確的。



其實這個程式在邏輯上非常的單純，但有可能是筆者有一陣子沒有去寫GA的程式或者是random的程式要顧慮的條件較多，所以寫起來卡卡的，如果你有更好的方式也歡迎告知。