遺伝的アルゴリズムを入門したかった

この投稿は インタープリズムの面々が、普段の業務に役立つ記事を丹精込めて書き上げる！ Advent Calendar 2016 - Qiitaの8日目 の記事です。

こんにちは、yumeです。

今回は「遺伝的アルゴリズム」で遊んでみます。
「遺伝的アルゴリズムって良く聞くし、面白いっぽいなぁ。でも理論や実装は全然知らないなぁ」というのが動機です。

流れ

まず簡単に遺伝的アルゴリズムについて紹介します。数式が出てきますが、ただ数式で表現しているだけです。難しい数学は始まりません。
次に遊びの題材として選んだ魔方陣について紹介します。なんだかトキメク名前ですが、ファンタジーは関係ありません。
そして実装に入ります。今回はjavaで書きました。
最後に、遊んだ結果をお見せします。

注意

きちんとした教科書を読んだわけではなく、断片的な知識を寄せ集めてできた自分なりの理解の上に成り立っている記事です。
そもそも「遺伝的アルゴリズム」ですらない「そういうアルゴリズム」になっているかも知れません。
どうか、生暖かい目で見ていただければ。

遺伝的アルゴリズム

さて、遺伝的アルゴリズム(Genetic Algorithm、以下GA)って何でしょうね？
GAとは、〇〇である。と言った風にカッコ良く(内包的に、簡潔に、自分の言葉で)答えたいのですが、残念ながら知識不足により今はできません。
なので長くなりますが、こういうのがGAだ、と言う外延的な説明をしようと思います。

染色体、遺伝子、適応度

まず、順序のあるパラメータ $g$ の列 $\langle g_1,g_2, \cdots ,g_n \rangle$ を用意します。
これは染色体と呼ばれ、パラメータ $g_i$ を遺伝子と言います。
複数の染色体を区別する場合に、ラベルを $m$ とした染色体を $C^{(m)}$ で表せば、
$C^{(m)} = \langle g_1^{(m)},g_2^{(m)}, \cdots ,g_n^{(m)} \rangle$
でしょうか。
染色体 $C^{(m)}$ にはある実数 $f^{(m)}$ が対応します。この $f$ を染色体 $C$ の適応度と言います。
一般的に、2つの適応度 $f^{(m)},f^{(k)}$ に対して $f^{(m)} > f^{(k)}$ となる時、染色体 $C^{(m)}$ は $C^{(k)}$ より優れていると言います。

第一世代の集団と交叉

さて、ここからが遺伝的アルゴリズムの流れになります。染色体を幾つか用意しましょう。
$\{ C^{(1)},C^{(2)},\cdots,C^{(N)} \}$
これを第一世代の集団と言います。集団の中から適当に2つを選んでペア $\langle C^{(i)},C^{(j)} \rangle$ を作ります。このペアを親と言います。
親と来れば子ですね。親の持つ遺伝子の集合
$\{ g_1^{(i)}, g_2^{(i)}, \cdots , g_n^{(i)}, g_1^{(j)}, g_2^{(j)},\cdots, g_n^{(j)} \}$
を使って、新しく染色体を作り、集団に加えます。これを
$\langle C^{(i)},C^{(j)} \rangle \mapsto \{ C_1^{(i,j)},C_2^{(i,j)},\cdots,C_{n(i,j)}^{(i,j)} \}$
と表すことにします。以上の、親を選び、親から子を作る操作を交叉と言います。
交叉を適当な回数繰り返した後の集団は
$\{ C^{(1)},C^{(2)},\cdots,C^{(N)} \} \cup \{ C_1^{(i,j)},C_2^{(i,j)},\cdots,C_n^{(i,j)} \mid (i,j)$ はすべての親 $\}$
となります。この集合の大きさを $S$ としましょう。

淘汰と第二世代の集団

次に淘汰をします。名前がなんだか怖いです。
拡大した集団の要素を使って、新たに集団を作ります。
$\{ C^{(a)},C^{(b)},\cdots,C^{(S')} \}$
まず集合の大きさですが、一般的に $N \leq S' \lt S$ です。 $S' = N$ の場合が多いかも知れません。
次に要素の選び方ですが、適応度を基準として選びます。淘汰によって選ばれなかった染色体は、残念ながらこれ以降無視されます。したがって、集団にはより優れた染色体が多く残ります。
淘汰によって作られた新たな集団を第二世代の集団と言います。以降、淘汰される度に数字が大きくなります。

評価と第三世代以降

最後に、第二世代の集団を評価します。
集団に対してある関数(例えば実数値関数) $E$ を用意し、ある基準値 $e$ に対して
$E( \{ C^{(a)},C^{(b)},\cdots,C^{(S')} \} ) \geq e$
ならばGAの終了判定とします。

終了していなければ、再び交叉・淘汰を繰り返します。
繰り返していくうちに、より優れた染色体の多い集団が出来上がるという訳ですね。交叉、淘汰、評価関数を適切に選べば、優れたパラメータを得ることができ、遺伝子、染色体を適切に設定できていれば、問題の解を得ることができます。

突然変異

しかし、このままでは問題があります。
今回説明した交叉も淘汰も、遺伝子の再分配に過ぎません。新たな遺伝子が登場しないため、限られた条件下での最も優れた解(局所的最適解)に収束してしまう恐れがあります。
なので、GAでは突然変異と呼ばれるランダム操作が、上記の流れのどこかで実行されます。

以上がGAの流れになります。
~~やたら数式を書きたくなってしまい~~抽象度・自由度が高くなってしまいましたが、具体的な例をこれから見ていきます。

魔方陣

次は魔方陣を説明します。と言っても、簡単なルールの数学パズルです。

ルール

$N \times N$ の正方格子を用意します。
各マスに $1$ 〜 $N^{2}$ の自然数を重複しない様に入れます。
縦・横・斜め(とり方は $2N + 2$ 通り)の"辺"に並んだ $N$ 個の自然数の合計が、全ての辺について等しくなっていれば、パズルを解いた事になります。

今回はこの魔方陣をGAで解いてみます。

実装

とりあえず、 $3 \times 3$ の場合を考えます。
まずは染色体の定義です。遺伝子に各マスに入る数字をとります。
$C^{(1)} = \langle 3,6,4,9,1,7,8,2,5 \rangle$
今回はランダムで並べます。そして同じものを20個作ります。

public class GA {
    private static final int order = 3;
    private static final int size = order * order;
    private static final int n = 20;
    private static ArrayList<ArrayList<Integer>> squares;

    // 初期化
    private static void initialize() {

        ArrayList<Integer> random = new ArrayList<Integer>(size);
        for (int i = 0; i < size; i++) {
            random.add(i + 1);
        }

        squares = new ArrayList<ArrayList<Integer>>();
        for (int i = 0; i < n; i++) {
            squares.add(new ArrayList<Integer>(size));
            Collections.shuffle(random);
            for (int j = 0; j < size; j++) {
                squares.get(i).add(random.get(j));
            }
        }
    }
}

次は交叉です。
多点交叉や循環交叉等、様々なものがありますが、今回は順序交叉と呼ばれる交叉を採用します。特に理由はありませんが、1つだけ、遺伝子の重複を許さない、という点が重要です。
順序交叉は、ランダムな位置で染色体を切り、前半部はそのまま子へ、後半部はもう一方の親の順序で子へ受け継ぐ交叉です。
具体的な実装を見てもらったほうが早いですね。ちなみに突然変異として、確率で子の遺伝子をシャッフルしています。また、最後の全体の流れとしての実装部でお見せしますが、今回はランダムに親を $10$ 組作ります。漏れなし、重複なしです。

   // 交叉
    private static ArrayList<Integer> crossOver(ArrayList<Integer> p1, ArrayList<Integer> p2) {
        ArrayList<Integer> child = (ArrayList<Integer>) p1.clone();
        ArrayList<Integer> tmp = (ArrayList<Integer>) p2.clone();
        Random rnd = new Random();
        int index = rnd.nextInt(size);
        if (index > order * (order - 1)) {
            Collections.shuffle(child);
        } else {
            for (int i = 0; i < index; i++) {
                tmp.remove(child.get(i));
            }
            child.removeAll(tmp);
            child.addAll(tmp);
        }
        return child;
    }

次は淘汰です。淘汰をするためには適応度を計算できなければならないので、まず適応度の関数を作ります。
$N \times N$ の魔方陣の各列の和は $N (N^{2} + 1 ) / 2$ なので、その差の二乗を足し合わせた物を適応度とします。今回は、適応度の小さいほうが優れた染色体と言えるわけですね。実装はこんな感じです。

   private static final int sum = order * (size + 1) / 2;

    // 初期化
    private static void initialize() {

        // 適応度関数用のリスト作成
        table = new ArrayList<Integer>();
        // 横
        for (int i = 0; i < order * order; i++) {
            table.add(i);
        }
        // 縦
        for (int i = 0; i < order; i++) {
            for (int j = i; j < order * order; j += order) {
                table.add(j);
            }
        }
        // 斜め
        for (int i = 0; i < order * order; i += order + 1) {
            table.add(i);
        }
        for (int i = order - 1; i < order * order - 1; i += order - 1) {
            table.add(i);
        }
    }


    // 適応度
    private static int fitness(ArrayList<Integer> list) {
        int result = 0;
        for (int i = 0; i < table.size(); i += order) {
            int tmp = 0;
            for (int j = i; j < i + order; j++) {
                tmp += list.get(table.get(j));
            }
            result += (sum - tmp) * (sum - tmp);
        }
        return result;
    }

この適応度を基準に淘汰します。上で説明した淘汰はかなり自由度が高いものでしたが、要はどうにかして優れた染色体が残るように集団を小さくすればいいだけ(のはず)です。今回の淘汰方法は、前世代での最も高い適応度(つまり優れていない。ややこしい)までの乱数を用意して、それぞれの染色体の適応度と比較するルーレット方式です。 $S' = N$ として、集団のサイズは $20$ と $40$ を繰り返します。
全体の流れとしての実装は次の通り。最大で $500$ 世代までとしています。

   private static final int limit = 500;

    public static void main(String[] args) {

        initialize();
        boolean end = false;
        int max = 0;
        for (int i = 0; i < squares.size(); i++) {
            int f = fitness(squares.get(i));
            if (max < f) {
                max = f;
            }
        }

        int generation = 1;

        while (generation <= limit && !end) {

            // 交叉用のランダムリスト
            ArrayList<Integer> crossRandom = new ArrayList<Integer>(squares.size());
            for (int i = 0; i < squares.size(); i++) {
                crossRandom.add(i + 1);
            }
            Collections.shuffle(crossRandom);

            // 交叉
            for (int i = 0; i < crossRandom.size(); i += 2) {
                squares.add(crossOver(squares.get(i), squares.get(i + 1)));
                squares.add(crossOver(squares.get(i + 1), squares.get(i)));
            }

            // 淘汰
            System.out.println("---------第" + generation + "世代----------");
            int maxtmp = max;
            max = 0;
            while (squares.size() > n && !end) {
                Collections.shuffle(squares);
                for (Iterator<ArrayList<Integer>> iterator = squares.iterator(); iterator.hasNext();) {
                    Random rnd = new Random();
                    int r = rnd.nextInt(maxtmp);
                    int f = fitness(iterator.next());
                    if (f == 0) {
                        end = true;
                        break;
                    }
                    if (r < f) {
                        iterator.remove();
                    } else if (f > max) {
                        max = f;
                    }
                    if (squares.size() <= n)
                        break;
                }
            }
            if (max == 0) {
                for (int i = 0; i < squares.size(); i++) {
                    int f = fitness(squares.get(i));
                    if (max < f)
                        max = f;
                }
            }
            generation++;
        }
    }

結果

各世代で最も優れた染色体と最も優れていない染色体をお見せします。

---------第1世代----------
6,4,2
1,5,7
9,8,3
54

7,8,6
2,3,5
1,4,9
153

// ランダムなので、まぁこんなもんです。
---------第5世代----------
6,2,5
1,3,9
8,7,4
47

7,5,4
8,1,2
9,6,3
169

---------第10世代----------
5,4,8
9,2,1
3,6,7
33

6,4,9
2,1,3
8,5,7
174

// 少し不安な進化をしています。。
---------第20世代----------
4,6,8
9,5,2
1,3,7
34

4,6,2
7,9,8
1,5,3
174

// 平均値をお見せしていませんが、まだまだ3桁が多いです。
---------第50世代----------
3,4,9
8,6,1
2,5,7
15

7,3,8
5,1,4
9,6,2
134

// 一気に解に近づきました。3桁は1つだけ、半分以上が15と16です。おそらく突然変異の生き残りです。
---------第100世代----------
4,3,9
8,6,1
2,7,5
8

4,5,9
1,6,2
7,3,8
138

// ついに1桁。
---------第200世代----------
4,3,9
8,6,1
2,7,5
8

4,3,9
8,6,1
2,7,5
8

// 全て同じ染色体です。これが局所的最適解になってしまっています。
---------第454世代----------
4,9,2
3,5,7
8,1,6
0

4,9,2
3,8,6
1,7,5
162

// 随分と時間がかかりましたが、無事解にたどり着いた様です。

終わりに

遺伝的アルゴリズム、なんとか実装できました。
ですが、課題は色々です。
まず交叉方法ですが、今回のお題に合っているとは言い難いでしょう。遺伝子の順序がとても重要なので、今回の交叉方法だとより局所的最適解になりやすいのではないでしょうか。
次にに淘汰方法ですが、さすがにちょっと手抜き過ぎたなぁ、と思っています。まぁ、入門(したかった)なので。
そしてそもそもの話ですが、お題が遺伝的アルゴリズムに向いていないと思っています。構想の時点で直感していたのですが、今でもそう感じています。局所的最適解に陥りやすいお題なのではないかと。
ただ、なぜ魔方陣を選んだかと言うと、(最も単純に計算すると) $N^{2}!$ 通りの中から魔方陣を探すのは骨が折れますが、遺伝的アルゴリズムならどうだろう？という好奇心ですね。結果として、まだまだ粗削りですが、回数をこなすことで確実に解に近づくという遺伝的アルゴリズムの威力を感じることが出来ました。生物の遺伝ってすごい。
ちなみに、 $4 \times 4$ だと $10$ 万世代くらいで(時間的にはすぐ)これくらいの結果なら持ってきてくれます。でも $200$ 万世代まで進めても解は出ませんでした。

14,15, 2, 4
 3, 1,16,13
11, 9, 8, 6
 5,10, 7,12
7

うーん、まだまだだなぁ。ではでは。

インタープリズムの面々が、普段の業務に役立つ記事を丹精込めて書き上げる！ Advent Calendar 2016 - Qiitaの9日目の記事

interprism's blog

インタープリズム株式会社の開発者ブログです。