※この記事は以下の記事を読んでいることを想定しています．
分布推定アルゴリズムを学ぶ (1) ～概要～
分布推定アルゴリズムを学ぶ (2) ～PBIL～

Compact Genetic Algorithm(CGA)とは

遺伝的アルゴリズム(Genetic Algorithm; GA)を分布推定アルゴリズムというフレームワーク上で実現した離散最適化手法．
GAと比較してメモリの消費量が少なくて済むというメリットがある．

概要

遺伝的アルゴリズムは，選択・交叉・突然変異という3つの操作を繰り返し，集団内の個体を進化させることで最適化を実現する手法である．

ここでは，それぞれの操作をEDAという枠組みで実現するための議論を行う．
また，PBILとの違いについても説明し，最後にCGAのアルゴリズムをまとめる．

選択

選択は，集団内で評価値の良い個体を次世代に残すための操作である．
しかし，個体の各次元に対して常に良い結果を生み出すと言うわけではない．
なぜなら，個体が高次元の場合には一回の選択だけで各次元の良し悪しを決定できないからである．

以下に例を示す．
ここではOne-Max問題を例に，$\boldsymbol{a}=(1,0,1,1),\boldsymbol{b}=(0,1,0,1)$という２つの個体に対しての選択を考える．
この２つの個体から次世代に残す個体を選ぶとすれば，おそらく$\boldsymbol{a}$が残るであろう．
これは，$\boldsymbol{a}$の評価値は3であり，$\boldsymbol{b}$の評価値は2であるという結果から導かれる．
しかし，次世代に$\boldsymbol{a}$のみが残ってしまうと，2次元目が誤ったままになってしまうということが分かる．
すなわち，この選択では2次元目に対しては誤った選択をしているということである．
GAではこのような事態を避けるため，集団という形で多様性を確保し，各次元に対する選択の誤りへの冗長性を確保している．

上記例の選択方式は，トーナメントサイズが2のトーナメント選択と等価である．
ここでは，より具体的なイメージを持つために，集団サイズ$\lambda$の集団$P$からトーナメント選択を用いて新たな集団$P'$を生成することを考える(EDAの文脈で言えば，集団$P^t$から集団$S^t$を生成する過程．分布推定アルゴリズムを学ぶ (1) ～概要～のEDAの流れ部分を参照)．

まず，集団$P$から2個の個体(ここでは上記の$\boldsymbol{a},\boldsymbol{b}$)をサンプルしたとする．
すると，評価値の良い$\boldsymbol{a}$が選ばれ，集団$P'$に追加される．
集団$P'$に個体$\boldsymbol{a}$が追加されたことによって，集団$P$と比較して集団$P'$内の1,3次元目の1の出現割合は$1/\lambda$だけ増加し，2次元目の1の出現割合は$1/\lambda$だけ減少する．4次元目については$\boldsymbol{a}$と$\boldsymbol{b}$で同じ値のため，集団$P$と集団$P'$で出現割合は変わらない．
GAにおけるトーナメント選択は，上記の流れを集団$P$と集団$P'$の集団サイズが同じになるまで繰り返す．

上記の例より，EDAにおいてGAのトーナメント選択と等価の振る舞いを実現するには，確率モデルからサンプリングされた2つの個体をトーナメント選択で選び，各次元で値が異なる部分に対して1の出現確率を$1/\lambda$だけ増加もしくは減少させればいいということが分かる．

交叉

GAにおける交叉の役割は，2つの個体を継ぎ接ぎしてより良い個体を作ることである．
集団に対して一般的な交叉の操作を繰り返し適用すると，最終的に集団内の各次元が無相関になることが知られている．
その場合，集団を確率ベクトルに置き換えた方がよりコンパクトに表現することができる．
そのため，CGAでは確率モデル$M^t$部分に確率ベクトルを用い，これによってGAにおける交叉の役割を実現する．

突然変異

CGAでは突然変異に関しては特に考慮していないようである．
PBILのような突然変異に関するGAとのアナロジーを考慮した実装方法もありそうだが．．．

PBILとの違い

PBILとの違いは以下の2点である．

集団サイズを指定したGAを完全にシミュレート出来ている
メモリの消費量がより少ない

CGAの確率モデルの更新則には定数$1/\lambda$のみが用いられる．
そのため，一般のGAであれば集団を保持するために$\lambda$ビットのメモリが必要になるのに対し，CGAの場合には集団内の1の出現割合$(0,1/\lambda,2/\lambda,...,\lambda/\lambda)$を保存できればいいので$log_2(\lambda+1)$ビットで十分になる．
PBILでは，学習率を用いた更新則の関係上，確率ベクトルの取りうる値の範囲は有限ではなく，CGAと比較して多くのメモリを必要とする．

一般に問題の規模が大きくなれば巨大な集団サイズを指定する必要があり，そういった場合にはメモリ消費量が$\lambda$から$log_2\lambda$まで削減できることは非常に有用である．
(正直，メモリがふんだんに使えるこのご時世にこのメリットは有ってないようなものだと思う．1990年代に提案された手法にそんなことを言うのは野暮だが）

アルゴリズム

以上の議論をふまえて，以下にCGAのアルゴリズムを示す．

ここで$\lambda$は集団サイズ，$D$は次元，$f$は目的関数である．
1～3行目では確率ベクトルを初期化している．$p_i$は$i$番目の変数が1になる確率である．5行目で確率ベクトル$\boldsymbol{p}$に基づいて2個の個体を生成する．6～10行目では評価値に応じて勝者$w$と敗者$l$を決める．
11～19行目では，勝者と敗者の各変数を比較して値が違う場合には勝者の値に応じて確率ベクトルを更新する．

実装

プログラム全体はgithubに置いてある．

環境

windows10
Python 3.7.3
anaconda Command line client (version 1.7.2)
conda 4.7.10
numpy 1.16.2

githubの方にSingularityの環境ファイルを置いてあるので，それをビルドしても動く(動作確認済み 2019/12/19時点)．

コード

import numpy as np

from optimizer.eda_base import EDABase


class CGA(EDABase):
    def __init__(self, categories, lam=32, theta_init=None):
        super(CGA, self).__init__(categories, lam=2, theta_init=theta_init)
        self.all_lam = lam

    def update(self, c_one, fxc, range_restriction=False):
        assert c_one.shape[0] == 2
        self.eval_count += c_one.shape[0]
        # sort by fitness
        idx = np.argsort(fxc)
        # store best individual and evaluation value
        if self.best_eval > fxc[idx[0]]:
            self.best_eval = fxc[idx[0]]
            self.best_indiv = c_one[idx[0]]
        # get winner and loser, and transform one-hot vector to index
        win = np.argmax(c_one[idx[0]], axis=1)
        lose = np.argmax(c_one[idx[-1]], axis=1)
        # get index for updating parameter that is difference between winner and loser
        diff_idx = win != lose
        # update parameter
        self.theta[diff_idx, win[diff_idx]] += 1 / self.all_lam
        self.theta[diff_idx, lose[diff_idx]] -= 1 / self.all_lam
        # if range_restriction is True, clipping
        for i in range(self.d):
            ci = self.C[i]
            theta_min = 1.0 / (self.valid_d * (ci - 1)) if range_restriction and ci > 1 else 0.0
            self.theta[i, :ci] = np.maximum(self.theta[i, :ci], theta_min)
            theta_sum = self.theta[i, :ci].sum()
            tmp = theta_sum - theta_min * ci
            self.theta[i, :ci] -= (theta_sum - 1.0) * (self.theta[i, :ci] - theta_min) / tmp
            self.theta[i, :ci] /= self.theta[i, :ci].sum()

実験：CGAの性能評価

実験設定

目的関数はOne-Max問題を用いる．
One-Max問題の次元は$D=100$とする．

CGAの集団サイズは$\lambda =\{10, 20, 30, 40, 50, 60, 70, 80, 90, 100\}$でそれぞれ最適化を行う．

以下のいずれかを満たした場合，最適化を終了する．

大域的最適解をサンプルできたとき(成功)
確率分布が収束したとき(失敗)
上限世代数(2000世代)に達したとき(失敗)

以上の設定で，乱数のシードを変更して10試行行う．

比較手法

CGAはGAをEDA上でシミュレートした手法なので，GAとの性能比較を行う．

GAに関するユーザーパラメータは以下の通りである．
・選択方式：トーナメントサイズ2のトーナメント選択
・交叉：集団全ての個体に対して一様交叉(例えば，集団サイズが100の場合は，50回の交叉によって100個の新たな個体が生成される)
・突然変異：使用しない

観察指標

以下の指標を記録する．

成功試行数(大域的最適解を見つけられた回数)
平均評価回数($\pm$標準偏差)
最適化終了時の最良評価値の平均($\pm$標準偏差)

ここで平均評価回数は，成功試行時のみのものとする．
評価回数は以下で計算する．

評価回数 = 集団サイズ \times 世代数

結果

One-Max問題($D=100$)をGAとCGAでそれぞれ最適化したときの結果を以下に示す．

手法	集団サイズ	成功試行数	平均評価回数($\pm$標準偏差)	平均最良評価値($\pm$標準偏差)
GA	10	0/10	-	71.90$\pm$2.70
CGA	10	0/10	-	85.30$\pm$2.24
GA	20	0/10	-	85.30$\pm$3.58
CGA	20	0/10	-	97.20$\pm$0.98
GA	30	0/10	-	91.80$\pm$2.36
CGA	30	3/10	734.00$\pm$46.68	99.00$\pm$0.89
GA	40	0/10	-	95.60$\pm$1.36
CGA	40	8/10	931.00$\pm$33.12	99.80$\pm$0.40
GA	50	2/10	1325.00$\pm$125.00	97.70$\pm$1.55
CGA	50	9/10	1132.44$\pm$68.63	99.90$\pm$0.30
GA	60	4/10	1860.00$\pm$103.92	98.50$\pm$1.36
CGA	60	10/10	1343.00$\pm$57.64	100.00$\pm$0.0
GA	70	4/10	1925.00$\pm$160.39	99.20$\pm$0.75
CGA	70	10/10	1500.80$\pm$84.32	100.00$\pm$0.0
GA	80	7/10	2182.86$\pm$164.03	99.70$\pm$0.46
CGA	80	10/10	1771.00$\pm$82.43	100.00$\pm$0.0
GA	90	9/10	2430.00$\pm$134.16	99.90$\pm$0.30
CGA	90	10/10	1928.60$\pm$91.72	100.00$\pm$0.0
GA	100	9/10	2633.33$\pm$176.38	99.90$\pm$0.30
CGA	100	10/10	2087.60$\pm$71.53	100.00$\pm$0.0

考察

表より，GAとCGAで比較するとCGAの方が成功試行数，平均評価回数のいずれの点でも優れている．
参考文献1でも，CGAとGAをOne-Max問題で比較しており，今回の結果と同様の傾向が出現している．

これは，各手法で個体の生成方法が異なることが理由と考えられる．
例えばGAでOne−Max問題を解く時，集団内の全個体の特定の次元が0になっていると，選択・交叉のみでは絶対にその部分は1にはならず，最適解を得ることが出来ない(普通は突然変異がこの問題を解消する役割を果たすが，今回は使用していない)．
一方でCGAでは，1になる確率を表す確率ベクトルから個体を毎世代サンプリングするため，確率ベクトルが0に収束していない限りは1になる可能性がある．
このように，GAの交叉では２つの個体の組み合わせから得られるパターンの個体しか生成出来ないのに対し，CGAでは確率ベクトルからのサンプリングのために探索空間全体から個体をサンプリングできる(確率ベクトルが0または1に収束していない限り)．
これは探索に対しての効率性が大きく変わる部分であり，それが表の結果に反映されていると考えられる．

まとめ

CGAはGAをEDA上でシミュレートした手法
アルゴリズムが非常にシンプルかつ簡単な問題にはしっかりと効果を発揮
各世代でサンプルする個体数が2個で十分という性質は問題設定によっては有利に働くかも

参考文献

The Compact Genetic Algorithm