黃鼠狼程式

概觀

I don't know who it was first pointed out that, given enough time, a monkey bashing away at random on a typewriter could produce all the works of Shakespeare. The operative phrase is, of course, given enough time. Let us limit the task facing our monkey somewhat. Suppose that he has to produce, not the complete works of Shakespeare but just the short sentence 'Methinks it is like a weasel', and we shall make it relatively easy by giving him a typewriter with a restricted keyboard, one with just the 26 (capital) letters, and a space bar. How long will he take to write this one little sentence?

We again use our computer monkey, but with a crucial difference in its program. It again begins by choosing a random sequence of 28 letters, just as before ... it duplicates it repeatedly, but with a certain chance of random error – 'mutation' – in the copying. The computer examines the mutant nonsense phrases, the 'progeny' of the original phrase, and chooses the one which, however slightly, most resembles the target phrase, METHINKS IT IS LIKE A WEASEL.

演算法範例

1. 從一條具有28個字母的隨機字串開始
2. 複製100個相同的字串，然後每個字母有5%的機率會換成另一個隨機的字母
3. 將每個字串與目標 "METHINKS IT IS LIKE A WEASEL"作比較，給每個字串進行評分(正確的字母出現在正確的位置上此字串得一分)。
4. 如果任何字串達到28分，也就是滿足條件時，程式停止
5. 否則，取用分數最高的字串，然後回到步驟2

參考資料

1. ^ 對有28個字母的字串，每個字母分別有27種可能性(A-Z和空白)，要產生正確的特定字串其機率是1/27^28；這個數字大約是1/10^40。宇宙的年紀大約是140億年，也就是4.415 x 10^17秒，假設一個程式從宇宙創生開始運作，每秒產生一千萬個字串，那麼到現在也只不過嘗試了4.415 x 10^24個字串，正確的機率僅為4.415 x 10^-16
2. ^ http://creation.com/weasel-words-creation-magazine-critique-of-dawkins