進化か創造か — 生命の起源に関わる論争において、進化生物学者のリチャード・ドーキンスは「イタチプログラム（Weasel program）」を提唱し、遺伝子の途方もなく複雑で精緻な配列が「設計者なき設計」で生み出されることを説明しました。イタチプログラムは「突然変異と選択による進化（蓄積淘汰）」と「単純なランダムな変化（一段階淘汰）」とで、正しい配列に到達する難易度がどれだけ異なるかを調べるものです。アルゴリズムは以下の通りです。
1.ランダムな28文字の文字列を用意する。
2.一定数(100など)のコピーを作る、ただし、各文字のコピー時に一定確率(5%など)でランダムな文字に変異する。
3.ターゲットの文字列"METHINKS IT IS LIKE A WEASEL"とできた各コピーを比べ、合致した文字数に応じたスコアを算出し、最も高いスコアの文字列で更新し、2に戻る。
4.ターゲットと合致すればそこで終了する。
"Methinks it is like a weasel."はハムレットの一節で、雲の形を巡って会話が交わされているシーンだそうです。現代語では"To me it looks like a weasel." 雲はたまたまその形を作っただけです。子孫を残すこともなく、ランダムにイタチを形作ります。つまり一段階淘汰の例というわけです。
↑BBCが1987年に放送した、ドーキンスがイタチプログラムを紹介している場面。
↑実験の途中経過。上がターゲット文字列、真ん中がイタチアルゴリズム、下がただのランダム。
ドーキンスが最初にBASICで書いて実験した頃は、実験が終わるまで30分かかっていましたが、今は一瞬で終わります。
このイタチプログラムをPythonで書いてみました。
import random
TARGET_STRING = "METHINKS IT IS LIKE A WEASEL"
CHAR_LIST = ["A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","V","W","X","Y","Z"," "]
CHILD_PER_GENERATION = 100
MUTATION_CHANCE = 0.05
length = len(TARGET_STRING)
def make_child(parent):
child = ""
for char in parent:
if random.random() < MUTATION_CHANCE:
child += random.choice(CHAR_LIST)
#突然変異
else:
child += char
#そのまま遺伝
return child
def check_string(character):
score = 0
for i in range(length):
if character[i] == TARGET_STRING[i]:
score += 1
return score
#マッチした文字数＝スコア を返す
def main():
generation = 0
best_score = 0
best_child = ""
first_char = ""
for _ in range(length):
first_char += random.choice(CHAR_LIST)
#ここまで初期化と最初の文字列の生成
while True:
for _ in range(CHILD_PER_GENERATION):
if best_child == "":
best_child = first_char
#最初はランダムな文字列で開始
new_child = make_child(best_child)
new_score = check_string(new_child)
if new_score > best_score:
best_score = new_score
best_child = new_child
#世代の最良の文字列で更新する
print(str(generation) + " " + best_child + " --score:" + str(best_score))
if best_score == length:
break
#合致すれば終了
generation += 1
main()
実行結果のサンプルです。
% python weasel.py
0 VCTHJWRBDCZJXGVZQO CVFKA YFL --score:3
1 VCTHJWRBCCZ XGVZQH VFWA YFL --score:6
2 VETHJWCBCCZ XGVLQH VFWA YFL --score:8
3 METHJWCB CT XSVLLHX VFWAAYOL --score:13
4 METHJWCB CT XSVLLHX VFWAAYOL --score:13
5 METHJWCB CT XSVLLHX VFWAAYEL --score:14
6 METHJWCB CT XSVLLHX VFWAAYEL --score:14
7 METHJWEB CT XSVLLVE AFWAAYEL --score:16
8 METHJWEB CT XSVLLVE AFWAAYEL --score:16
9 METHIWEB CT XSVLKVE AFWAAYEL --score:17
10 METHIWEB CT ISVLKVE AFWAAVEL --score:18
11 METHIWKB CT ISVLKVE A WAAVEL --score:20
12 METHIWKB CT ISVLKVE A WAAVEL --score:20
13 METHIWKB IT ISVLKVE A WAAVEL --score:21
14 METHINKB IT ISVLKVE A WAAVEL --score:22
15 METHINKB IT ISVLKVE A WEAVEL --score:23
16 METHINKB IT ISVLKVE A WEAVEL --score:23
17 METHINKB IT ISVLKVE A WEAVEL --score:23
18 METHINKB IT ISVLKVE A WEAVEL --score:23
19 METHINKB IT ISVLKVE A WEASEL --score:24
20 METHINKB IT IS LKVE A WEASEL --score:25
21 METHINKB IT IS LKVE A WEASEL --score:25
22 METHINKB IT IS LKVE A WEASEL --score:25
23 METHINKB IT IS LKVE A WEASEL --score:25
24 METHINKB IT IS LKVE A WEASEL --score:25
25 METHINKB IT IS LKVE A WEASEL --score:25
26 METHINKB IT IS LKVE A WEASEL --score:25
27 METHINKB IT IS LKVE A WEASEL --score:25
28 METHINKB IT IS LKVE A WEASEL --score:25
29 METHINKB IT IS LKVE A WEASEL --score:25
30 METHINKB IT IS LKVE A WEASEL --score:25
31 METHINKB IT IS LIVE A WEASEL --score:26
32 METHINKB IT IS LIVE A WEASEL --score:26
33 METHINKB IT IS LIVE A WEASEL --score:26
34 METHINKB IT IS LIVE A WEASEL --score:26
35 METHINKS IT IS LIVE A WEASEL --score:27
36 METHINKS IT IS LIVE A WEASEL --score:27
37 METHINKS IT IS LIKE A WEASEL --score:28
確かに比較的短期で正解へ収束しています。これを完全にランダムな変異で実現するのは無謀です。$\frac{1}{28^{28}} $ を引き当てなければならないので。
ドーキンスによるこの実験は、いわば遺伝的アルゴリズムの先駆けです。
参考：
Weasel program
https://en.wikipedia.org/wiki/Weasel_program
Randomness and Evolution
https://youtu.be/qkSkXbqcCgU
リチャード・ドーキンス著,中嶋・遠藤・疋田訳,『盲目の時計職人』（早川書房,2004）