読者です 読者をやめる 読者になる 読者になる

牌語備忘録 -pygo

あくまでもメモです。なるべくオフィシャルの情報を参照してください。

牌語備忘録 -pygo

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

Python

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

人工知能の一つである「遺伝的アルゴリズム
(以後、Genetic Algorithm=GAと呼ぶ)

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

プログラムの仕様はこちら
問題は問1〜10まですべて3択(問題はこちら

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 set_lst + add_box
    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]
    print genetic_algorithm(answer)

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

実行結果

採点 [AIの解答]
(正解は[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点にならない場合も...(´・ω・`)(修正済み)