初めに

今回は遺伝的アルゴリズム(GA)での組み合わせアルゴリズムの応用例を紹介いたします。k-meansは非階層的クラスタリングアルゴリズムの一つで、局所探索には優れています。一方GAは大域探索に使われています。この二つのアルゴリズムを結合することで、大域探索ができることと局所探索が早いことを両方併せ持つアルゴリズムをGKAと呼びます。まず二つのベースアルゴリズムを説明します。

対象読者

少しクラスタリングと遺伝的アルゴリズムの前提知識が必要です。

k-means

一番使われている非階層的クラスタリング手法の一つです。
基本の流れは

1. k個のクラスタを決める
2. ランダムにデータ集から重心をk個抽出する
   例えば: 2次元、k=3の場合、初期重心は[[1,0],[1,1],[1,0]]
3. データを各重心とのユークリッド距離を計算し、一番短い重心に割り当てる
4. 各クラスタ内のデータの平均値が新たな重心になる
5. 3と4を重心が変化しなくなるまで、繰り返す

GA

前の記事で紹介したように

1. 初期集団生成
2. 適応度計算
3. 選択
4. 交差
5. 変異

を終了条件を満たすまで繰り返します。

わからない方は以下のリンクに参考してください

GKA

k-meansは初期値による結果に影響されやすい、つまり局所最小値に陥りやすいアルゴリズムです。これに対する解決手法がいろんな手があります。例えばよく使われているk-means++初期化手法です。GKAもその解決手法の一つです。

アルゴリズムが単純にGAとk-meansの結合です。大まかな流れは

1. 初期集団作成
   データ集からランダムにk個データを重心として抽出します。これを一つの染色体(1次元リスト)に格納します。これを初期集団のサイズ(個体数)回まで繰り返したものが初期集団になります。
   例えば: 上のk-meansの例を用いると、染色体が[1,0,1,1,1,0]になります。
2. k-means
   局所探索の収束速度を早くするため、k-meansの局所探索を利用します。各個体に対し、k-meansで一回重心を更新します。
3. 適応度計算
   各クラスタ内のデータとクラスタとのユークリッド距離の和の反比例
   M(C_1,C_2,...,C_k)= {\sum_{i=1}^k} \sum_ {x_j \in C_i} ||x_j-z_j||
   したがって適応度は
   1/M
   となります。
4. 選択
5. 交差
6. 突然変異
7. 2-6を終了条件を満たすまで繰り返します。

まとめ

GKAが大域探索においてはk-meansより良い精度を得られますが、速度上では個体ごとに各操作を行うので、k-meansより劣っています。