# 『マッチ箱の脳』人工知能ジェネテックアルゴリズムをPythonでやってみた

マッチ箱の脳 WEB ver『‚Ù‚Ú“úŠ§ƒCƒgƒCV•· - ‚ª‚ñ‚Î‚êXì‚­‚ñ‚Ìˆâ“`Žq‚­‚ñ』のマッチ箱で作るGAをPythonでやってみた。

（以後、Genetic Algorithm＝GAと呼ぶ）

‚Ù‚Ú“úŠ§ƒCƒgƒCV•· - ‚ª‚ñ‚Î‚êXì‚­‚ñ‚Ìˆâ“`Žq‚­‚ñ

プログラムの仕様はこちら

##### Python

[訂正] 若干修正
[訂正] 重複したリスト削除
[訂正] frozenset()をset()に
[訂正] #!/usr/local/bin/pythonを#!/usr/bin/env python

```#!/usr/bin/env python
# *-# -*- coding: utf-8 -*-
# Genetic Algorithm
# ga2_1.py

import random

def matchbox(num = 10, kind = 1, to_kind = 3):
return [random.randint(kind, to_kind) for n in range(num)]

def amount_of_box(amount = 10):
return [matchbox() for count in range(amount)]

def del_duplication(box_seq):
set_tu = set(map(tuple,box_seq))
set_lst = map(list, set_tu)
n = len(set_lst)
if n < 10:
add_box = [matchbox() for i in range(10 - n)]
return box_seq

def rating(ans, box_seq):
point_lst = []
for box in box_seq:
point = 0
for a, b in zip(ans, box):
if a == b:
point += 10
point_lst.append([point, box])
return sorted(point_lst, reverse = True)

def parent(rate_seq, choice = 2):
return [rate_seq[0][1], rate_seq[1][1]]

def mutation(kids_seq):
p = random.randint(0, len(kids_seq))
if p < 10:
change = lambda x:x + 1 if x < 3 else x - 2
kids_seq[p] = change(kids_seq[p])
return kids_seq

def recombination(parent_seq):
crossing = random.randint(0, 10)
kid_a = parent_seq[1][:crossing] + parent_seq[0][crossing:]
kid_b = parent_seq[0][:crossing] + parent_seq[1][crossing:]
return [mutation(kid_a), mutation(kid_b)]

def genetic_algorithm(ans, count = 200):
log = []
all_box = amount_of_box()
for i in range(count):
dd_box = del_duplication(all_box)
rate_seq = rating(ans, dd_box)[:]
log.append("Generation: %d" % (i + 1))
log.append("\n".join(["%d %s" % (n,l) for n,l in rate_seq]))
all_box = [l for n,l in rate_seq]
parent_seq = parent(rate_seq)
top = all_box[:2]
tail = all_box[2:-2]
all_box = recombination(parent_seq) + tail + top
if rate_seq[0][0] == 100:
break
else:
log.append("break: over %d Generation!" % count)
return "\n".join(log)

if __name__ == "__main__":
answer = [3, 1, 2, 2, 2, 3, 1, 3, 2, 1]
```

100点取るか、200世代を超える場合は終了。（count = 200）

##### 実行結果

（正解は[3, 1, 2, 2, 2, 3, 1, 3, 2, 1]）

```>>> Generation: 1
70 [3, 3, 3, 2, 2, 3, 1, 1, 2, 1]
40 [3, 2, 3, 3, 2, 1, 1, 2, 2, 2]
40 [2, 1, 1, 3, 1, 3, 3, 2, 2, 1]
30 [3, 3, 2, 1, 3, 1, 3, 1, 3, 1]
30 [2, 3, 1, 1, 1, 3, 2, 1, 2, 1]
30 [2, 2, 2, 2, 1, 1, 1, 1, 3, 3]
30 [1, 3, 1, 3, 2, 1, 1, 3, 1, 2]
30 [1, 1, 1, 2, 3, 2, 3, 2, 2, 3]
20 [1, 2, 1, 1, 1, 3, 2, 1, 3, 1]
10 [3, 2, 1, 1, 1, 2, 3, 1, 3, 3]
Generation: 2
70 [3, 3, 3, 2, 2, 3, 1, 1, 2, 1]
60 [3, 3, 3, 2, 2, 1, 1, 3, 2, 2]
50 [3, 2, 3, 3, 2, 3, 1, 1, 3, 1]
40 [3, 2, 3, 3, 2, 1, 1, 2, 2, 2]
40 [2, 1, 1, 3, 1, 3, 3, 2, 2, 1]
30 [3, 3, 2, 1, 3, 1, 3, 1, 3, 1]
30 [2, 3, 1, 1, 1, 3, 2, 1, 2, 1]
30 [2, 2, 2, 2, 1, 1, 1, 1, 3, 3]
30 [1, 3, 1, 3, 2, 1, 1, 3, 1, 2]
30 [1, 1, 1, 2, 3, 2, 3, 2, 2, 3]
Generation: 3
80 [3, 1, 3, 2, 2, 1, 1, 3, 2, 1]
70 [3, 3, 3, 2, 2, 3, 1, 1, 2, 1]
60 [3, 3, 3, 2, 2, 1, 1, 3, 2, 2]
60 [3, 3, 1, 2, 2, 3, 1, 1, 2, 2]
50 [3, 2, 3, 3, 2, 3, 1, 1, 3, 1]
40 [3, 2, 3, 3, 2, 1, 1, 2, 2, 2]
40 [2, 1, 1, 3, 1, 3, 3, 2, 2, 1]
30 [3, 3, 2, 1, 3, 1, 3, 1, 3, 1]
30 [2, 3, 1, 1, 1, 3, 2, 1, 2, 1]
30 [2, 2, 2, 2, 1, 1, 1, 1, 3, 3]
Generation: 4
80 [3, 1, 3, 2, 2, 1, 1, 3, 2, 1]
70 [3, 3, 3, 2, 2, 3, 1, 1, 2, 1]
70 [3, 2, 3, 2, 2, 1, 1, 3, 2, 1]
60 [3, 3, 3, 2, 2, 3, 1, 1, 2, 2]
60 [3, 3, 3, 2, 2, 1, 1, 3, 2, 2]
60 [3, 3, 1, 2, 2, 3, 1, 1, 2, 2]
50 [3, 2, 3, 3, 2, 3, 1, 1, 3, 1]
40 [3, 2, 3, 3, 2, 1, 1, 2, 2, 2]
40 [2, 1, 1, 3, 1, 3, 3, 2, 2, 1]
30 [3, 3, 2, 1, 3, 1, 3, 1, 3, 1]
Generation: 5
80 [3, 3, 1, 2, 2, 3, 1, 3, 2, 1]
80 [3, 1, 3, 2, 2, 1, 1, 3, 2, 1]
70 [3, 3, 3, 2, 2, 3, 1, 1, 2, 1]
70 [3, 2, 3, 2, 2, 1, 1, 3, 2, 1]
70 [3, 1, 3, 2, 2, 2, 1, 1, 2, 1]
60 [3, 3, 3, 2, 2, 3, 1, 1, 2, 2]
60 [3, 3, 3, 2, 2, 1, 1, 3, 2, 2]
60 [3, 3, 1, 2, 2, 3, 1, 1, 2, 2]
50 [3, 2, 3, 3, 2, 3, 1, 1, 3, 1]
40 [3, 2, 3, 3, 2, 1, 1, 2, 2, 2]
Generation: 6
80 [3, 3, 1, 2, 2, 3, 1, 3, 2, 1]
80 [3, 1, 3, 2, 2, 1, 1, 3, 2, 1]
70 [3, 3, 3, 2, 2, 3, 1, 1, 2, 1]
70 [3, 3, 1, 2, 2, 3, 2, 3, 2, 1]
70 [3, 2, 3, 2, 2, 1, 1, 3, 2, 1]
70 [3, 2, 3, 2, 2, 1, 1, 3, 2, 1]
70 [3, 1, 3, 2, 2, 2, 1, 1, 2, 1]
60 [3, 3, 3, 2, 2, 3, 1, 1, 2, 2]
60 [3, 3, 3, 2, 2, 1, 1, 3, 2, 2]
60 [3, 3, 1, 2, 2, 3, 1, 1, 2, 2]
Generation: 7
80 [3, 3, 1, 2, 2, 3, 1, 3, 2, 1]
80 [3, 1, 3, 2, 2, 1, 1, 3, 2, 1]
80 [3, 1, 3, 2, 2, 1, 1, 3, 2, 1]
70 [3, 3, 3, 2, 2, 3, 1, 1, 2, 1]
70 [3, 3, 1, 2, 2, 3, 2, 3, 2, 1]
70 [3, 3, 1, 2, 2, 1, 1, 3, 2, 1]
70 [3, 2, 3, 2, 2, 1, 1, 3, 2, 1]
70 [3, 2, 3, 2, 2, 1, 1, 3, 2, 1]
70 [3, 1, 3, 2, 2, 2, 1, 1, 2, 1]
60 [3, 3, 3, 2, 2, 3, 1, 1, 2, 2]
Generation: 8
80 [3, 3, 1, 2, 2, 3, 1, 3, 2, 1]
80 [3, 3, 1, 2, 2, 3, 1, 3, 2, 1]
80 [3, 1, 3, 2, 2, 1, 1, 3, 2, 1]
80 [3, 1, 3, 2, 2, 1, 1, 3, 2, 1]
70 [3, 3, 3, 2, 2, 3, 1, 1, 2, 1]
70 [3, 3, 1, 2, 2, 3, 2, 3, 2, 1]
70 [3, 3, 1, 2, 2, 1, 1, 3, 2, 1]
70 [3, 2, 3, 2, 2, 1, 1, 3, 2, 1]
70 [3, 2, 3, 2, 2, 1, 1, 3, 2, 1]
70 [3, 1, 3, 2, 2, 1, 1, 3, 3, 1]
Generation: 9
80 [3, 3, 1, 2, 2, 3, 1, 3, 2, 1]
80 [3, 3, 1, 2, 2, 3, 1, 3, 2, 1]
80 [3, 3, 1, 2, 2, 3, 1, 3, 2, 1]
80 [3, 1, 3, 2, 2, 1, 1, 3, 2, 1]
80 [3, 1, 3, 2, 2, 1, 1, 3, 2, 1]
70 [3, 3, 3, 2, 2, 3, 1, 1, 2, 1]
70 [3, 3, 1, 3, 2, 3, 1, 3, 2, 1]
70 [3, 3, 1, 2, 2, 3, 2, 3, 2, 1]
70 [3, 3, 1, 2, 2, 1, 1, 3, 2, 1]
70 [3, 2, 3, 2, 2, 1, 1, 3, 2, 1]
Generation: 10
90 [3, 1, 1, 2, 2, 3, 1, 3, 2, 1]
80 [3, 3, 1, 2, 2, 3, 1, 3, 2, 1]
80 [3, 3, 1, 2, 2, 3, 1, 3, 2, 1]
80 [3, 3, 1, 2, 2, 3, 1, 3, 2, 1]
80 [3, 1, 3, 2, 2, 1, 1, 3, 2, 1]
80 [3, 1, 3, 2, 2, 1, 1, 3, 2, 1]
70 [3, 3, 3, 2, 2, 3, 1, 1, 2, 1]
70 [3, 3, 1, 3, 2, 3, 1, 3, 2, 1]
70 [3, 3, 1, 2, 2, 3, 2, 3, 2, 1]
70 [3, 3, 1, 2, 2, 3, 1, 3, 2, 2]
Generation: 11
90 [3, 1, 1, 2, 2, 3, 1, 3, 2, 1]
80 [3, 3, 1, 2, 2, 3, 1, 3, 2, 1]
80 [3, 3, 1, 2, 2, 3, 1, 3, 2, 1]
80 [3, 3, 1, 2, 2, 3, 1, 3, 2, 1]
80 [3, 1, 3, 2, 2, 1, 1, 3, 2, 1]
80 [3, 1, 3, 2, 2, 1, 1, 3, 2, 1]
80 [3, 1, 1, 2, 3, 3, 1, 3, 2, 1]
70 [3, 3, 3, 2, 2, 3, 1, 1, 2, 1]
70 [3, 3, 1, 3, 2, 3, 1, 3, 2, 1]
70 [3, 3, 1, 2, 2, 3, 1, 3, 3, 1]
Generation: 12
100 [3, 1, 2, 2, 2, 3, 1, 3, 2, 1]
90 [3, 1, 1, 2, 2, 3, 1, 3, 2, 1]
80 [3, 3, 1, 2, 2, 3, 1, 3, 2, 1]
80 [3, 3, 1, 2, 2, 3, 1, 3, 2, 1]
80 [3, 3, 1, 2, 2, 3, 1, 3, 2, 1]
80 [3, 1, 3, 2, 2, 1, 1, 3, 2, 1]
80 [3, 1, 3, 2, 2, 1, 1, 3, 2, 1]
80 [3, 1, 1, 2, 3, 3, 1, 3, 2, 1]
70 [3, 3, 3, 2, 2, 3, 1, 1, 2, 1]
70 [3, 3, 1, 2, 2, 1, 1, 3, 2, 1]```

12世代目で100点でた。なかなか賢い(・∀・)
※追記／何回か実行したら200世代までいっても100点にならない場合も...(´･ω･`)（修正済み）