Shogo's Blog

Oct 4, 2012 - 10 minute read - Comments - 6さいカンファレンス

6さいカンファレンス 第3回「アルゴリズムを自力で生み出すプログラムを作ろう!」まとめ

2012/09/06にくいなちゃんさん主催で開催された6さいカンファレンスのまとめ。 第3回は「アルゴリズムを自力で生み出すプログラムを作ろう!」です。

勝手にまとめてしまったので、何か問題があれば@shogo82148まで。

WELCOME TO HEAVEN!!

くいなちゃん: ところでみなさん、次の( ) に入る数を当ててください

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ( )

くいなちゃん: はい、正解です! これは、フィボナッチ数列と呼ばれ、 前の2つの値の和が、次の値になっているという数列です

くいなちゃん: これを、f(0) = 0, f(1) = 1, f(2) = 1, f(3) = 2, f(4) = 3, f(5) = 5, … と書いていくことにしましょう。 f(10) = 55 ですね!

くいなちゃん: もっと汎用的に考えて、f(x) の x を与えると、フィボナッチ数が返ってくることを考えましょう。 x = 10 のとき、f(x) が 55 になる、といった感じです

くいなちゃん: ではみなさん、この f(x) を、プログラムで書くことはできますでしょうか。 言語は何でも構いません。

くいなちゃん: やり方は、いくつかあります。 x = 100 と与えられれば、0, 1, 1, 2, 3, 5, … と 約100回繰り返して、x = 100 の値を求めるというものです。

くいなちゃん: しかし、これはちょっと効率が悪いですね… x = 100000 なら、100000回計算しなくてはなりません。 理想的には、x = 100000 でも、一発で計算結果が返ってくるアルゴリズムが望ましいです。 難しい言葉で言えば、O(1) ですね。

くいなちゃん: そんなの無理! って思うかもしれませんが、実は可能です。 Wikipedia で調べると、 f(x) = 1 / √5 ( ((1+√5)/2)^x - ((1-√5)/2)^x)  と出てきます。

くいなちゃん: イミフですね! あなたがどう頭を使っても、なかなかこのアルゴリズムに到達することはできないでしょう…。

くいなちゃん: というわけで、今回は、 あなたが頭を使うことなしに、アルゴリズムを自動で作り出すプログラムを作ろう! ということをしたいと思います。

くいなちゃん: どうやって? と思うかもしれませんので、これからその仕組みを簡単に説明しましょう。

遺伝的プログラミング

くいなちゃん: まず、あなたは人間です(たぶん)。 人間は、優れた頭脳や肉体を持っていますが、これは神によって創られたものではありません(たぶん)。 生物学的な「遺伝」によって、生まれました。

くいなちゃん: というわけなので、これをプログラムで同じ感じにやれば、 超複雑なプログラムが、遺伝によって生まれうるのではないか! というわけなのです

くいなちゃん: これを、「遺伝的プログラミング」 と呼びます。 (遺伝的アルゴリズムとはちょっと違う)

くいなちゃん: というわけなので、折角なので このフィボナッチ数を求めるプログラム(アルゴリズム) を、遺伝によって発見させてみることにしましょー☆

くいなちゃん: 次のプログラムと図をご覧ください。 http://kuina.tes.so/6saiconf_3/img0.png(魚拓) ここでは、四則演算と累乗が、木構造として定義されています。 (今回は、Javaですん☆)

``` java Tree.java http://kuina.tes.so/6saiconf_3/img0.png public class Tree { public String value; public Tree[] children;

public String dump() {
    String result = value;
    for (int i = 0; i < children.length; i++)
        result += " " + children[i].dump();
    return result;
}

public double calc(double x) {
    switch (value.charAt(0)) {
    case '+': return children[0].calc(x) + children[1].calc(x);
    case '-': return children[0].calc(x) - children[1].calc(x);
    case '*': return children[0].calc(x) * children[1].calc(x);
    case '/': return children[0].calc(x) / children[1].calc(x);
    case '^': return Math.pow(children[0].calc(x), children[1].calc(x));
    case 'x': return x;
    }
    return Double.parseDouble(value);
}

}


くいなちゃん: [前回](/blog/2012/10/02/6saiconf-2/)も言いましたが、くいなちゃんは ポーランド記法が好きなので、
みなさんもポーランド記法に慣れてくださいね。
例えば、ここで x\*(2-3) という式は、ポーランド記法で \* x - 2 3 となり、右のような木構造になります。

くいなちゃん: プログラム中の dump() は、式を単に出力する関数で、calc() は、式の計算結果を返す関数になっています。
再帰使ってるけど、大丈夫かな?


## ランダムで式を作る

くいなちゃん: で、くいなちゃんは めんどくさがり屋なので、いちいち式を作るのが嫌です。
なので、ランダムで式を作る関数を追加しましょう。
<http://kuina.tes.so/6saiconf_3/img1.png>([魚拓](/files/6saiconf/3/img1.png))

``` java Tree.java http://kuina.tes.so/6saiconf_3/img1.png
public class Tree {
    public String value;
    public Tree[] children;

    public String dump() {
        String result = value;
        for (int i = 0; i < children.length; i++)
            result += " " + children[i].dump();
        return result;
    }

    public double calc(double x) {
        switch (value.charAt(0)) {
        case '+': return children[0].calc(x) + children[1].calc(x);
        case '-': return children[0].calc(x) - children[1].calc(x);
        case '*': return children[0].calc(x) * children[1].calc(x);
        case '/': return children[0].calc(x) / children[1].calc(x);
        case '^': return Math.pow(children[0].calc(x), children[1].calc(x));
        case 'x': return x;
        }
        return Double.parseDouble(value);
    }

    static public Tree make(java.util.Random rand, int len) {
        Tree result = new Tree();
        switch(len >= 5 ? 6 : rand.nextInt(7)) {
        case 0: result.value = "+"; result.children = new Tree[2]; break;
        case 1: result.value = "-"; result.children = new Tree[2]; break;
        case 2: result.value = "*"; result.children = new Tree[2]; break;
        case 3: result.value = "/"; result.children = new Tree[2]; break;
        case 4: result.value = "^"; result.children = new Tree[2]; break;
        case 5: result.value = "x"; result.children = new Tree[0]; break;
        default: result.value = ((Integer)(rand.nextInt(10) + 1)).toString(); result.children = new Tree[0];
        }
        for (int i = 0; i < result.children.length; i++)
            result.children[i] = make(rand, len + 1);
        return result;
    }
}

くいなちゃん: バツしてるところは、さっき書いた部分なので気にしなくてokです

くいなちゃん: これで、+ - * / \^ x 0 1 2 3 4 5 6 7 8 9 の文字がランダムに生成されるようになりました。 make() ですね。

くいなちゃん: はい、では、試しにランダムで式を作って、計算させてみましょう☆ http://kuina.tes.so/6saiconf_3/img2.png(魚拓) 画面の下のほうに実行結果が出ています。 - 4 / 2 - 10 2 = 3.75  たしかにちゃんと計算されてそう。

``` java Example.java http://kuina.tes.so/6saiconf_3/img2.png public class Example { public static void main(String[] args) { Tree tree = Tree.make(new java.util.Random(), 0); System.out.println(tree.dump()); System.out.println(“= ” + ((Double)tree.calc(1.0)).toString()); } }


<input type="button" id="Example1" value="計算">
<pre><code id="Example1Result"></code></pre>
<script>
document.getElementById('Example1').addEventListener('click', function() {
    var tree = Tree.make(0);
    document.getElementById('Example1Result').innerText = tree.dump() + '\n= ' + tree.calc(1.0);
}, false);
</script>


## 遺伝させる

くいなちゃん: こんな感じで、式が木構造で表現できるようになりました!
あとは、これを遺伝させて、フィボナッチ数を求めるアルゴリズム(例の複雑な式)が求まれば、成功ですん☆

くいなちゃん: では、遺伝とは、具体的に何をさせるのか、説明いたしましょう。

くいなちゃん: まず、ランダムで作った式 1つ1つを、「遺伝子」と呼ぶことにしましょう。
遺伝子は あらかじめ 100個くらい用意します。

くいなちゃん: 次に、これらの遺伝子の「子供」を作り、次の世代の遺伝子とすることにします。
次の世代も、親の世代と同じ 100個になるように調整します。

くいなちゃん: あとは、これを延々と繰り返していくわけですが、ここで、子孫を残す親を、「優れた遺伝子」から選ばれるような仕組みにします。
つまり、フィボナッチ数に近いような式になっている遺伝子は、親になる可能性が高くなるということです。

くいなちゃん: これにより、世代を重ねていくごとに、より良い遺伝子(式) になっていくことが期待できるのですー☆

くいなちゃん: 遺伝的プログラミングが、遺伝的アルゴリズムと異なるのは、後者が n個のデータを遺伝させるのに対し、前者は ツリー(式やプログラム)を遺伝させるということです。

くいなちゃん: はい、親を2人選んだら、子供が生まれるわけですが、具体的には「交叉」と「突然変異」というシステムで実現します。
<http://kuina.tes.so/6saiconf_3/imga.png>([魚拓](/files/6saiconf/3/imga.png))
この図で、左側が交叉、右側が突然変異を説明しています

くいなちゃん: 交叉は、両親の遺伝子の一部ずつを取ってきて、子に遺伝させるということです。
しかし、ごく微小確率(ここでは5%としている) で、突然変異が起こり、デタラメな式に書き換わってしまうのです。

くいなちゃん: まあこれは、人間においても、遺伝子のコピーミスなどで、ガン細胞が発生したりする過程と同じですん☆

くいなちゃん: はい、以上をプログラムで書いたのが、これです。
Javaのせいで気分が悪くなったら、無理に読まなくて結構ですん
<http://kuina.tes.so/6saiconf_3/img3.png>([魚拓](/files/6saiconf/3/img3.png))

``` java GP.java http://kuina.tes.so/6saiconf_3/img3.png
public class GP {
    private java.util.Random rand;
    private Tree[] genes;
    private double[] values;
    private Tree bestgene;
    private double bestvalue;

    public GP(int genesnum) {
        rand = new java.util.Random();
        genes = new Tree[genesnum];
        for (int i = 0; i < genes.length; i++)
            genes[i] = Tree.make(rand, 0);
        values = new double[genesnum];
        bestgene = null;
        bestvalue = 0.0;
        refreshValues();
    }

    public Tree refreshValues() {
        for (int i = 0; i < genes.length; i++) {
            // x    = 0 1 2 3 4 5 6  7  8  9 10
            // f(x) = 0 1 1 2 3 5 8 13 21 34 55
            double[] fx = {0.0, 1.0, 1.0, 2.0, 3.0, 5.0, 8.0, 13.0, 21.0, 34.0, 55.0};
            values[i] = 0.0;
            for (int j = 0; j < fx.length; j++) {
                double v;
                if (genes[i].countLeaves() >= 50)
                    v = 100000000.0;
                else {
                    v = genes[i].calc((double)j) - fx[j];
                    v *= v;
                }
                if (Double.isNaN(v))
                    v = 100000000.0;
                values[i] += v;
            }
            values[i] = 1.0 / values[i];
            if (bestvalue < values[i]) {
                bestvalue = values[i];
                bestgene = genes[i];
            }
        }
        return bestgene;
    }
}

くいなちゃん: とはいえ、まだこのプログラムでは、交叉と突然変異を書いていません。 ランダムで遺伝子を100個用意して、その中で フィボナッチ数に最も近そうな遺伝子が見つかるところまでです

くいなちゃん: とりあえず、折角ここまで書いたのでテストしてみましょう。 http://kuina.tes.so/6saiconf_3/img4.png(魚拓) まだ 1世代目なので、そんなに優れた遺伝子はありません。 実行例では、\^ x x つまり x^x (xのx乗) がフィボナッチ数列に最も近い式だ、ということになりました。 なるほど、確かにちょっと近そう…?

``` java Example.java http://kuina.tes.so/6saiconf_3/img4.png public class Example { public static void main(String[] args) { GP gp = new GP(100); Tree tree = gp.refreshValues(); System.out.println(tree.dump()); for (int i = 0; i < 11; i++) System.out.println(“f(” + i + “)” + “= ” + ((Double)tree.calc((double)i)).toString()); } }


<input type="button" id="Example2" value="計算">
<pre><code id="Example2Result"></code></pre>
<script>
document.getElementById('Example2').addEventListener('click', function() {
    var gp = new GP(100);
    var tree = gp.refreshValues();
    var result = '';
    var i;
    result += tree.dump() + '\n';
    for(i = 0; i < 11; i++) {
        result += 'f(' + i + ') = ' + tree.calc(i) + '\n';
    }
    document.getElementById('Example2Result').innerText = result;
}, false);
</script>

くいなちゃん: (そうでもない)

くいなちゃん: はい、いよいよ交叉と突然変異を追加するわけですが、
その前に、便利関数として、木のノード数を数える関数や、自分自身のコピー木を作る関数や、任意の番号のノードを取得できる関数などを、数式木のクラスに書き加えました。
<http://kuina.tes.so/6saiconf_3/img5.png>([魚拓](/files/6saiconf/3/img5.png))
図をじっと見てたら、何してるかくらいは判るはず

``` java Tree.java http://kuina.tes.so/6saiconf_3/img5.png
public class Tree {
    public String value;
    public Tree[] children;

    public String dump() {
        String result = value;
        for (int i = 0; i < children.length; i++)
            result += " " + children[i].dump();
        return result;
    }

    public double calc(double x) {
        switch (value.charAt(0)) {
        case '+': return children[0].calc(x) + children[1].calc(x);
        case '-': return children[0].calc(x) - children[1].calc(x);
        case '*': return children[0].calc(x) * children[1].calc(x);
        case '/': return children[0].calc(x) / children[1].calc(x);
        case '^': return Math.pow(children[0].calc(x), children[1].calc(x));
        case 'x': return x;
        }
        return Double.parseDouble(value);
    }

    static public Tree make(java.util.Random rand, int len) {
        Tree result = new Tree();
        switch(len >= 5 ? 6 : rand.nextInt(7)) {
        case 0: result.value = "+"; result.children = new Tree[2]; break;
        case 1: result.value = "-"; result.children = new Tree[2]; break;
        case 2: result.value = "*"; result.children = new Tree[2]; break;
        case 3: result.value = "/"; result.children = new Tree[2]; break;
        case 4: result.value = "^"; result.children = new Tree[2]; break;
        case 5: result.value = "x"; result.children = new Tree[0]; break;
        default: result.value = ((Integer)(rand.nextInt(10) + 1)).toString(); result.children = new Tree[0];
        }
        for (int i = 0; i < result.children.length; i++)
            result.children[i] = make(rand, len + 1);
        return result;
    }

    public int countLeaves() {
        int result = 1;
        for (int i = 0; i < children.length; i++)
            result += children[i].countLeaves();
        return result;
    }

    public Tree copy(int[] leaf, Tree other) {
        leaf[0]--;
        if (leaf[0] == -1)
            return other.copy(leaf, null);
        Tree result = new Tree();
        result.value = value;
        result.children = new Tree[children.length];
        for (int i = 0; i < children.length; i++)
            result.children[i] = children[i].copy(leaf, other);
        return result;
    }

    public Tree select(int[] leaf) {
        leaf[0]--;
        if (leaf[0] == -1)
            return this;
        for (int i = 0; i < children.length; i++) {
            Tree result = children[i].select(leaf);
            if ( result != null)
                return result;
        }
        return null;
    }
}

くいなちゃん: 判れ。

くいなちゃん: で、がんばって、交叉と突然変異を実装しました。 http://kuina.tes.so/6saiconf_3/img6.png(魚拓) getGoodGene は、より優れた遺伝子が高確率で選択させるようにした関数で、これで親になる遺伝子を選びます。 inherit は、交叉・突然変異を一まとめにして、「次の世代を作る遺伝処理」をする関数になっています。 突然変異は、0.05 の確率で起こることが、ソースをよく読んでたら解りますね。(チラッ

``` java GP.java http://kuina.tes.so/6saiconf_3/img6.png public class GP { private java.util.Random rand; private Tree[] genes; private double[] values; private Tree bestgene; private double bestvalue;

public GP(int genesnum) {
    rand = new java.util.Random();
    genes = new Tree[genesnum];
    for (int i = 0; i < genes.length; i++)
        genes[i] = Tree.make(rand, 0);
    values = new double[genesnum];
    bestgene = null;
    bestvalue = 0.0;
    refreshValues();
}

public Tree refreshValues() {
    for (int i = 0; i < genes.length; i++) {
        // x    = 0 1 2 3 4 5 6  7  8  9 10
        // f(x) = 0 1 1 2 3 5 8 13 21 34 55
        double[] fx = {0.0, 1.0, 1.0, 2.0, 3.0, 5.0, 8.0, 13.0, 21.0, 34.0, 55.0};
        values[i] = 0.0;
        for (int j = 0; j < fx.length; j++) {
            double v;
            if (genes[i].countLeaves() >= 50)
                v = 100000000.0;
            else {
                v = genes[i].calc((double)j) - fx[j];
                v *= v;
            }
            if (Double.isNaN(v))
                v = 100000000.0;
            values[i] += v;
        }
        values[i] = 1.0 / values[i];
        if (bestvalue < values[i]) {
            bestvalue = values[i];
            bestgene = genes[i];
        }
    }
    return bestgene;
}

public Tree getGoodGene() {
    double totalvalue = 0.0;
    for (int i = 0; i < genes.length; i++)
        totalvalue += values[i];
    double r = rand.nextDouble() * totalvalue;
    int select = 0;
    while (r >= values[select]) {
        r -= values[select];
        select++;
    }
    return genes[select];
}

public double inherit() {
    Tree[] newgenes = new Tree[genes.length];
    for (int i = 0; i < genes.length; i++) {
        Tree a = getGoodGene(), b;
        if (rand.nextDouble() < 0.05)
            b = Tree.make(rand, 0);
        else
            b = getGoodGene();
        if (a == b)
            newgenes[i] = a;
        else {
            int[] leafa = new int[] { rand.nextInt(a.countLeaves()) };
            int[] leafb = new int[] { rand.nextInt(b.countLeaves()) };
            newgenes[i] = a.copy(leafa, b.select(leafb));
        }
    }
    genes = newgenes;
    refreshValues();
    return bestvalue;
}

}


くいなちゃん: なるほど、わからん

くいなちゃん: はい、それでは、本当に 遺伝を繰り返すと、良い遺伝子が得られるのか、テストしてみましょう。
<http://kuina.tes.so/6saiconf_3/img7.png>([魚拓](/files/6saiconf/3/img7.png))
この出力は、どの程度 フィボナッチ数列に近い遺伝子が見つかったかを示すものです(大きいほうが近い)。
なるほど、確かに、だんだん進化してますね。

``` java Example.java http://kuina.tes.so/6saiconf_3/img7.png
public class Example {
    public static void main(String[] args) {
        GP gp = new GP(100);
        for (int i = 0; i < 50; i++)
            System.out.println(gp.inherit());
    }
}

くいなちゃん: では、せっかくなので、100000回くらい遺伝させてみましょう!!

くいなちゃん: 100000回というと、孫の孫の孫の孫の… と膨大な数の子孫を経た世代ということです。 恐ろしい。

くいなちゃん: その結果… http://kuina.tes.so/6saiconf_3/img8.png(魚拓) なんかすごく近い関数が発見されました!! 右側にフィボナッチ数列を載せていますが、確かに比較すると 近いことが判ると思います。 (ただ、確かに近いけれど、なんか違う…)

java Example.java http://kuina.tes.so/6saiconf_3/img8.png public class Example { public static void main(String[] args) { GP gp = new GP(100); for (int i = 0; i < 100001; i++) { double value = gp.inherit(); if (i % 10000 == 0) System.out.println(value); } Tree bestgene = gp.refreshValues(); System.out.println(bestgene.dump()); for (int i = 0; i < 11; i++) System.out.println("f(" + i + ")" + "= " + ((Double)bestgene.calc((double)i)).toString()); } }

くいなちゃん: その式とは、 + x + / x 4 / * …  と続く、大変意味不明な式です。 なんですか、この式は…?

くいなちゃん: 期待していた、最初のほうで言った式とは、なんか違いますよね… 気のせいかな?

くいなちゃん: とは言っても、ポーランド記法に慣れていない 皆さんは、ぱっと見ても解らないと思います。 なので、普通の式に整理して書き直してみました☆

くいなちゃん: 今回、このプログラムが発見した フィボナッチ数列の式とは… http://kuina.tes.so/6saiconf_3/img9.png(魚拓) これです!!

くいなちゃん: 一番下のやつ

くいなちゃん: 参考までに、正しいフィボナッチ数列の式を一番上に掲げておきました。

くいなちゃん: なんと、√とか使わない式で、フィボナッチ数列を再現したのです…!

くいなちゃん: はい、分数です

くいなちゃん: そこにある式全部で、一つの式です。 つまり、6次式ですね!

くいなちゃん: 6次式より、高次だった

くいなちゃん: はい、まとめですん☆ 遺伝的プログラムを用いると、こんな感じで、近いアルゴリズムを 自動で発見させることができます。 今回は、簡単な計算式のみを遺伝させましたが、for文や if文なども含めて遺伝させると、ちょー複雑なプログラムも 自動で誕生させることができます。 試してみてください☆