用Generic Algorithm實作N-Queen後的初步心得

這系列Evolutional Computation的文章是去年修課時寫的，今天收到別人寄信說看到我去年寫的筆記，對他有些幫助，滿高興的。事實上我已忘了把筆記轉到web上這回事，與其讓這些資料繼續躺在web角落，不如放到普及度較高的Blog吧。

---

( 寫於2005/10/08 )

Evolutionary Computation,
這是門詭異的學門, 耳熟能詳的Generic Algorithm是EC的一種

據ypchen所言, 這個領域的人不知道為什麼, 不愛寫書, 不愛寫paper,
看來神祕的力量都是不留記錄

EC發展20多年, 仍然沒有基本定理, 沒有公式, 沒有證明,
沒有人知道它為什麼對, 只能說些似是而非, 看起來好像有道理的話,
雖然有些中心思想[*1], 但不怎麼數學, 比較像物理化學,
發現一個現象, 再想辦法掰公式, 想辦法解釋它,
如果風行已久, 又沒人推翻它, 就大概是對的吧

簡單的描述一下用EC解N-Queen的一種作法 (以8-Queen為例)
1. 隨機產生100個盤面, 放到Set S裡
ex: 1 2 3 4 5 6 7 8, 4 1 2 5 3 8 7 6, …
這裡的數字表示各個row的queen要放在第幾個column上

2. 挑一個看起來最正確的, 隨機選兩個位置做swap
ex: 4 1 2 5 3 8 7 6 ==(swap 1,8)==> 4 8 2 5 3 1 7 6,
將新盤面加到 S 裡

3. 從 S 裡刪掉看起來最不正確的

4. 重覆step 2, 3到你高興為止
ex: 找到一組解了, 或是執行個100次

結果呢?
要找大量不同的解很困難, 但只要找到一個解到是出乎意料的快

ex: N = 100時, 4 secs, 在第171代找出一組解 (即試了100+171 = 271種可能)
N = 200時, 28 secs, 在第522代找出一組解 (試了621種可能) [*2]

很顯然的, 一般解法 (Backtracking的經典例題),
不可能在可接受的時間內(比方一天)找到一組解

從以上的作法裡, 看得出來”Why it works?”嗎?
只能說冥冥之中自有天意啊

PS

*1
EC的學者認為, 在一堆隨機的候選答案裡, 存在和最終解的關聯性,
只是我們不知道怎麼找出搜尋的規則,
EC的作法, 就是想辦法讓這莫名的規則發生,
使候選答案一步步成長為最終解

拿DP來比喻可能會有所領會,
也就是問題的最佳解取決於子問題的最佳解,
DP有明確的數學規則, EC則否

*2
N = 200時的解, 看看就好

125 142 24 196 45 105 179 140 107 20 49 92 148 165 48 197 78 8 155 80
132 7 153 93 31 72 161 190 103 53 116 40 188 75 111 119 187 69 18 130
77 55 36 106 19 83 65 141 100 89 101 129 34 162 192 28 46 10 169 173
114 32 4 143 95 61 189 193 200 133 96 166 60 22 131 172 152 112 57
146 113 102 90 87 71 15 109 183 170 52 118 174 21 186 137 167 11 67
25 157 33 35 120 2 117 98 44 50 26 104 184 68 177 73 164 9 47 147 64
97 168 1 62 121 38 178 182 13 63 154 145 160 86 199 5 138 29 74 158 3
37 126 191 91 56 181 156 94 115 110 195 39 6 23 27 16 58 81 134 128
76 150 124 180 84 42 171 151 127 41 136 163 144 99 175 17 85 122 194
185 135 70 14 66 59 54 12 82 139 30 43 149 79 176 51 159 88 108 123
198