cellular GA の多様性評価

Collins [4] は SGA の大域的交配/選択と cellular GA の局所的交配/ 選択の性能をビット値および遺伝子型の多様性, 同種繁殖の割合, 速度とロバスト性の 観点から評価し, 局所的交配/選択の優位性を数値実験により示した.

GAの評価には従来から最適個体の適応度の絶対値や収束性が用いられていたが, Collins の用いた評価基準は GA の計算過程の本質をとらえるものであり, 次の4種類 である.

・ビット値の多様性 D(Diversity of Alleles):

 
それぞれのビットの値の多様性はスキーマの種類を示すので, ビット値の多様性が高け れば過剰収束を防ぐことができる. 各ビット i について, 集団の中で 0 となる割合 から求める. 0 の割合が 50% で最高値 1.0 をとり, 割合が 0% または 100%, つまりそのビットには 0 または 1 のどちらかしか存在しない場合に 最低値 0.0 をとるような関数である.

・遺伝子型の多様性(Diversity of Genotype):

 
集団内の全個体から10ビット(位置はランダム)取りだし, 何種類あるかをカウントする. この評価関数は現在の探索空間の広さを表す.

・交配した2つの個体の類似度 F(Inbreeding Coefficient):

 
非常に異なる個体を交配してもほとんどの場合不適解である. 2つの個体中で異なる値 を持つビット数の, 実際の交配時の値 H とランダムに生成した2つの個体の理論値 の割合 F で計算する. , ただし, p は 0 値の割合である.

・速度とロバスト性(Speed and Robustness):

 
ロバスト性と速度は, 手法全体としての性能の評価である. ロバスト性は, 全実行回中 で最適解に到達した割合(1000世代打切り)である. 速度は, 最適解に到達するまでのコ スト(世代数または計算時間)の全実行回中のメジアンである.

単純GAはルーレットを用いた確率的選択とランク選択の2種類のモデルを用意した. 並 列 GAは個体を1次元配列(1D)または2次元メッシュ(2D)に並べ, 境界はトーラス状に他 辺に接続した. 並列GAの局所的選択は, 離れるほど疎遠になる距離による隔離 ( isolation by distance) と呼ばれるモデルを用いた. ある格子点から R ステップの ランダムウオークで発見された最も適応度の高い個体(これを2回行なう) が, その格子 点の次世代の個体の両親となる. ランダムウォークのスタート地点が含まれるので, そ の格子点の適応度が最高であれば確実に生き残るエリート戦略でもある(図5.10).

図5.10 ランダムウォークを用いた局所選択

問題は64頂点(=64ビット)のマルチレベルグラフで, 集団サイズは 〜 とかなり大規模の問題を扱っている. それぞれの評価基準につ いて, 単純GAと1Dおよび2D cellular GA の性能を次のようにまとめた.

・ビット値の多様性:

確率/ランク選択法は多様性を急速に失うが, 1D/2D局所選択法は最後まで初期の多様性 が維持される.

・遺伝子型の多様性:

すべての手法で数世代の後に急速に多様性を失う. 1D/2D局所選択法は最終的に150種類 (総数:1024種類)前後であるが, 確率選択法は40種類, ランク選択法は15種類まで減少す る.

・同種繁殖の係数:

比較的早い世代では, 確率/ランク選択法は低い値のままであるが, 1D/2D局所選択法は 急速に増加する. 遅い世代では, いずれの手法も高い値を維持する. ただし, 確率選択 法は相対的には低い.

・速度とロバスト性:

純粋な計算時間の観点からみると, ランク選択法が確率選択法より約2倍高速である. 局所選択法では, 5<R<20 が最速であり, 集団サイズが大きくなるほど計算時間が長 くなる. 1Dより2Dの方が速い. しかし, 最も遅い局所選択法でも, 最速の大域的選択法 より約2倍高速である. 一方, ロバスト性の観点から見ると, 局所選択法は100%最適解 に到達したが, 大域的探索法は, 一部で最適解に到達できない.

大域的選択法は2つの最適解の一方に急速に収束するのに対し, 局所選択法はほぼ確実 に2つの最適解の両方を発見した. 局所選択法は deme (ギリシャ時代の行政区) ごとに異なるピークを探索し, しかも deme は小さいので効率が良い.

局所選択法は, ビットや遺伝子型多様性に優れており, 一世代でより多くの遺伝子型を 探索している. 一方, 近親交配係数が高いことは, deme 内では似たような遺伝 子型に収束して効率良く探索していることを意味する. つまり, deme 内の収束 性と, 集団全体の多様性という相反する長所を合わせ持つ.