社内勉強会用に遺伝的プログラミングでFizzBuzzを(作るプログラムを)つくってみました。

勉強会には間に合わなかったのでこちらで公開します。

遺伝的プログラミングの解説と例はこちらの本に載っています。

Amazon.co.jp： 集合知プログラミング: Toby Segaran, 當山 仁健, 鴨澤 眞夫: 本

今回作ったスクリプトは上記の本に載っていたものをFizzBuzz用に修正したものです。Pythonで書いてあります。元々のスクリプトの機能は整数の加算、減算、乗算、if、>を組み合わせて目的にあった挙動をするプログラムを組み立てるというものでした。

今回修正した点は

• 文字列を扱えるよう変数の型の概念を導入した。
• 結果の出力を画像化した。

の２点です。

ソースコードはこちらから。実行にはPython2.6以降とpyDotが必要です。

genetic_fizzbuzz.py

以下、修正した主な部分の解説です。

class fWrapper:
    def __init__(self,function,child_count,name,params,type):
        self.function = function
        self.child_count = child_count
        self.name = name
        self.params = params
        self.type = type

paramsとtypeを指定して、パラメタ、戻り値の型を指定できるように修正。

def make_random_tree(pc,max_depth=4,fpr=0.5,ppr=0.6,type='object'):
    if random() < fpr and max_depth > 0:
        f = choice(flist[type])
        children = [make_random_tree(pc,max_depth-1,fpr,ppr,type=t) for t in f.params]
        return node(f,children)
    elif random() < ppr and type == 'int':
        return paramNode(randint(0,pc-1))
    elif type == 'object':
        return constNode(choice(['','fizz','buzz','fizzbuzz',randint(0,100)]));
    elif type == 'string':
        return constNode(choice(['','fizz','buzz','fizzbuzz']))
    else:
        return constNode(randint(0,100))

こちらもchildrenを作成するときに戻り値の型を指定するように修正。

mutateとcrossoverも同様の修正をしています。

定数ノードではfizz,buzz,fizzbuzzの文字を発生させる様に修正してます。

本当は文字列もランダムで発生させたかったのですが、進化にかかる時間が増えるので少し手抜きしました。

def write_jpeg(tree):
    stack = [tree]
    g = pydot.Dot()
    root = True
    while len(stack) > 0:
        node = stack.pop()
        parent_node = pydot.Node(node.name+"_"+str(id(node)))
        parent_node.set_label(node.name)
        if root:
            g.add_node(parent_node)
            root = False
        if hasattr(node,"children"):
            for child in node.children:
                stack.append(child)
                child_node = pydot.Node(child.name+"_"+str(id(child)))
                child_node.set_label(child.name)
                g.add_node(child_node)
                g.add_edge(pydot.Edge(parent_node,child_node))
    g.write_jpeg('tree.jpg',prog='dot')

新しく追加したメソッド。

ツリーを受け取って、jpeg画像を出力します。

画像の出力にはgraphvizを使っています。

一世代の個体群の数=100、最大世代交代数=5000で実行した結果が以下の画像です。

図中のif,mod,div,fizz,buzzは関数、p0はパラメータ（fizzbuzzが取る1~100の整数）、それ以外は、定数を表しています。たとえば一番左下のdivから61,11に矢印が伸びている部分はdiv(61,11)=61/11=5を表しています。

図のプログラムを、結果が定数になるような冗長な計算をはぶいてPythonで書くと以下の様になります。

if p0 % 5 > 1:
    if p0 % 3 > 1:
        return ""
    else:
        return "fizz"
else:
    return "buzz"

３、５の公倍数のときの出力ができてないのが残念ですが、おおむねfizzbuzzの動作をしています。個体群数や世代数、突然変異の発生率などを色々変えて試してみましたが、いまのところこれが最善の結果でした。

というわけで、完全な結果が得られなくて残念でしたが、変数型を導入できたので、いろいろ応用ができそうです。また何か作ったらここで公開したいと思います。