Shogo's Blog

Oct 4, 2012 - 8 minute read - 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ですん☆)

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);
    }
}

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

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

ランダムで式を作る

くいなちゃん: で、くいなちゃんは めんどくさがり屋なので、いちいち式を作るのが嫌です。 なので、ランダムで式を作る関数を追加しましょう。 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　　たしかにちゃんと計算されてそう。

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());
    }
}

遺伝させる

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

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

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

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

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

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

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

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

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

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

くいなちゃん: はい、以上をプログラムで書いたのが、これです。 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乗)　がフィボナッチ数列に最も近い式だ、ということになりました。 なるほど、確かにちょっと近そう…？

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());
    }
}

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

くいなちゃん: はい、いよいよ交叉と突然変異を追加するわけですが、 その前に、便利関数として、木のノード数を数える関数や、自分自身のコピー木を作る関数や、任意の番号のノードを取得できる関数などを、数式木のクラスに書き加えました。 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 の確率で起こることが、ソースをよく読んでたら解りますね。(ﾁﾗｯ

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(魚拓) この出力は、どの程度 フィボナッチ数列に近い遺伝子が見つかったかを示すものです(大きいほうが近い)。 なるほど、確かに、だんだん進化してますね。

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(魚拓) なんかすごく近い関数が発見されました！！ 右側にフィボナッチ数列を載せていますが、確かに比較すると 近いことが判ると思います。 (ただ、確かに近いけれど、なんか違う…)

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文なども含めて遺伝させると、ちょー複雑なプログラムも 自動で誕生させることができます。　試してみてください☆