( 寫於2005/12/20 )
想了一種新方法, 測試結果還不錯
將sigma encode到chromosome裡, i.e., chromosome含有Gk, Gs, sigma
select a parent p,
if p.Gk == G
do adaptation (=> revise p.sigma)
p.Gk = p.Gs = 0
fi
p.Gk++
offspring = mutation(p)
if offpsring.fitness BetterThan p.fitness
p.Gs++
fi
如果parent在replacement時被幹掉了也沒差,
一直都留下來的話自然會做到adaptation
( 即parent夠優秀, 才有必要對它調適sigma )
看起來很直接的想法,
但在想出來之前, 一點也不直接, 得跳出幾個迷思才行
( 寫於2005/12/06 )
前言: 這篇是針對了解ES的人寫的
原本的(1+1)-ES如下
Gs: succesful mutation (offspring is better than parent)
G : sample generations
p = Gs / G
a = (0,1) (recommendation a = 0.8)
sigma = {
sigma / a, if p > 0.2
sigma * a, if p < 0.2
sigma , if p = 0.2
}
經測試結果, 1/5 rule非常有威力, 大大加速了收斂和找到好結果
但在(u+k)-ES時要怎麼套呢? (k > 1)
count all mutations, if it’s successful, Gs++
p = Gs / (G*k)
count all successful replacement,
Gs = number of offsprings which is replaced into populations
p = Gs / (G*u)
測試結果, way1比way2好 (還滿合理的),
但都比N step-sized的self-adaptive差
今天終於想到一個解法
for each generation, count successful mutation, say n,
Gs++ if n/k >= 0.5
p = Gs / G
結果比way1好很多, 而且比N step-sized self-adaptive好
每一generation的mutation成功與否, 應該是各自判斷, 而非累計,
way1有個盲點, 假設sample 5 generation,
結果1st generation幾乎都成功, 但2~5 generation幾乎都失敗,
但加起來的機率仍 > 0.2怎麼辦? 這個反應已和1st generation的情況差很遠了
所以我認為way3最合理, 而且1/5 rule應該比N step-sized好 (一般來說)
個人認為fitness愈能合理且即時反應在meta-parameters上,
self-adaptive才會有效果, 但要怎麼個合理法, 怎樣才夠即時, 是另一大問題
相較於以前不認同不知所云的解，現在我不會排斥用EC解。漸漸覺得傳統嚴僅的AI無法做出超越人腦的產物，雖然人腦運作方式還沒完全破解，但我想類神經網路或演化計算的做法，較接近人腦運作的原理吧。
( 寫於 2005/12/09 )
昨天ypchen說, 如果將design和optimization做比較,
他覺得EC是做design的還較有道理
所謂的物競天擇, 適者生存, 真的有選出最佳種嗎?
還是只是設定了一個門檻, 低於此限的物種就無法延續下去,
所以EC無法拿來做optimization, 只能去掉比較不好的
如果針對這兩者來比較的話,
EC較像用來選design的, 不是做optimization,
我們可以從EC的結果看出一些隱藏的想法
我認同這個觀點, 拿蟑螂來看就可以明白,
蟑螂稱不上很突出的物種, 它之所以能一直存活,
是因為它仍能適應環境的限制
原本我以為EC就是做optimization的,
聽了ypchen這番話後想想, 覺得很有道理,
這個想法更明確地釐清一些現象
我覺得我對EC的態度, 比較像是從中激發一些靈感, 而非用它來解決問題,
以我的個性來說, 即使用EC解決我的問題,
我也不想用一個不知所芸的東西當解決方案,
所以我會把EC當做達到最後目標的過程裡的一個嘗試吧
這系列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
最近讀了《資訊架構學》，覺得即使是Wiki，也可以構思如何將頁面以更豐富的方式呈現，比方加上最近更新的頁面。
原本 Site.AllRecentChanges 就有顯示所有更新過的頁面，但不方便自訂格式，像是去掉一些不想統計的頁面（例如*.RecentChange），所以自己來弄一個。做法相當簡單，只要用shell script找出wiki.d/下的更新時間即可，再將shell執行結果讀進自訂變數，由wiki page內文裡讀出變數的結果即可。由於做法太簡單了，我就沒找Cookbook裡有沒有類似工具，自己直接黑手做掉了。
最上面加入shell script取得更新列表：
function GetRecentUpdatedList() { $result = `ls -tl wiki.d | perl -ne 'print if ! /\.RecentChanges|\.AllRecentChanges|PmWiki\.|Site\.ActionLog|^total /' \ | perl -ane 'print " \$F[-4]-\$F[-3] \$F[-2] [[\$F[-1]]]\n";' | head -30`; return $result; } ... $result = GetRecentUpdatedList(); $FmtPV['$RecentUpdatedList'] = "'" . $result . "'"; #capture contents of $result
比方在Main.HomePage裡加上：
!! Recent Updated List {$RecentUpdatedList}
這個做法的關鍵是使用自訂變數，參照PmWiki官網說明：OtherVariables，有使用自訂變數的範例。
圖文並茂的入門書，編排方式都是左頁文字右頁圖，大部份內容看右頁圖就好，讀起來很快。從基本的供給和需求講起，到市場運作機制，貨幣制定和運作機制，最後是說明國際貿易和貨幣流動（升貶值）的關係，將基本名詞解釋得很清楚。除了貨幣升貶和景氣之間的變化沒完全看懂外，整本書看下來，偶而細想一下即可吸收，真的是不錯的入門書。
如同《圖解OOO》系列的副標語所言：「一冊通曉，不可不知的基礎人文知識」，理工人了解一些社會人文的內容，有個基本認知，應該很有幫助。況且在一個領域待久了，腦袋只會愈來愈硬，試著看看不同領域怎麼思考，滿有趣的。
《圖解經濟學》真是易讀易懂的好書，弄懂不少觀念。經濟流通的根本是供給和需求，物品的價值由供需雙方共同認定，基本觀念大家都懂：
以此發展的基本原則有「物以稀為貴」、「以價制量」、「以量制價（規模經濟）」，皆不離供需的運作。
當物價有廣為人知的標準時，就是俗稱的行情，比方一般600c.c.的飲用水賣20元左右。當物價的供需標準不夠流通時，就回歸原始的做法，喊到買賣雙方都認可的價格，比方買古董或接case。
貨幣也是物品的一種，運作的法則也是如此。
銀行和物品專賣店的本質一樣，只是銀行買賣的物品是貨幣。所以銀行內有很多貨幣時，借貸率低；貨幣少時，借貸率高。於是中央銀行（大盤商）要把關貨幣流通率，貨幣量對社會的影響如下：
中央銀行要調整各家銀行的貨幣備存量（比方必須保留20%的貨幣），限制銀行能借出的貨幣額度。
另外政府缺錢時可以徵稅、發行公債、讓中央銀行發行貨幣（就是印鈔票啦），前兩者的運作模式和後果容易理解，但以前我搞不懂印鈔票的運作模式。如果可以印鈔票，為什麼不印？如果可以印鈔票，那錢不就無中生有，不合常理。
其實印鈔票並不是無中生有，錢也是物品，印鈔票增加鈔票量，造成鈔票貶值，也就是通貨膨脹，假設中央銀行印了現有鈔票一樣的量，也就是讓總量變兩倍，那每張鈔票的價值可能會跌為一半，一碗25元的陽春麵可能變成50元。換個角度來看，印鈔票就是讓全民買單，政府從全民口袋裡的鈔票抽走部份價值，再從自己口袋拿出來用。這樣來看，政府三種補錢的做法，只有舉行公債才不會傷到全民，徵稅是有差別比例傷害，印鈔是無差別全砍，但砍得方式比較無形，暫時看不出影響。
終於解開小時候的疑惑了。
