並列GAの理論と評価方法

• a スキーマ理論
• b マルコフチェーン
• c 適応度の評価
• d 多様性の評価

スキーマ理論

並列GAの理論的考察に関する研究はそれほど多くない. 単純GAの理論として最も有名な スキーマ定理 (schema theorem) は, GAの挙動の十分条件を記述しているが, 現実の問 題にはマージンが大き過ぎて適用しづらい. しかし, スキーマ理論を基に, 並列GAと単 純GAを比較することは有効であり, いくつかの理論的解析が行なわれた.

Pettey と Leutze [29] はスキーマ理論を island モデルに拡張し, スキ ーマへの試行の割り当て回数が, 指数増加(減少)関数で制限されていることを証明した. Davidor [5] は ECO GA と呼ばれる fine-grained GA を設計し, スキー マ定理を再構成した. 適応度の高い個体が急速に広がって群を作る現象を理論的に解析 した. クラスタ(群)の形成における境界付近の選択圧力の理論的解析は Spiessens と Manderick [37] に報告されている.

マルコフチェーン

Shonkwiler [34] は並列GAをマルコフチェーンとして表現し, 完全に 孤立した移住なしの island GA と単純GAの最適解への平均到達時間の比較を行なった. 数値計算的には指摘されていた台数倍以上の高速化が得られる現象, すなわち超線形 (superlinear) 高速化が可能であることが理論的に証明された. 詳しくは (6) 並列GAの代表的な研究事例 に後述する.

適応度の評価

単純GAや並列GAを問わずGAの性能を汎用的に評価する基準を作ることは難しい. 一般的 には, 世代数(適応度評価回数)あるいは実際の計算時間を横軸にとり, 最良および平均 の適応度を縦軸にとったグラフによって, アルゴリズムの善し悪しを示している. そこ では, 最終的な適応度の値と共に, いかに速く収束するかも評価の対象となる. 一定世 代後の適応度を比較する方法や, 最適解が分かっているときには最適解に到達するまで の世代数もしばしば使われる. アルゴリズムのロバスト性を評価するために, 試行回数 中の最適解に到達する確率を使う. また, 応用問題においては既存の最適化手法と比較 するために, 収束の限界まで世代を繰り返し, 適応度の絶対値での比較が行なわれるこ ともある.

多様性の評価

これらの評価はいずれも適応度の推移あるいは最終値を評価基準としている. 単純GAで 最大の課題である過剰収束は, 集団の多様性の喪失であるので, 集団の多様性を直接計 測する評価基準が Collins [4] により提案された. ビット多様性 (集団 中の全個体のあるビットが 0 である割合), 遺伝子型多様性(ランダムに n ビット 取りだし, 全集団で何種類あるか), 交配時の2個体の平均類似度(あまり異なると子個 体はほとんどの場合不適解)である. Collins は単純 GA および数種類の cellular GA について世代ごとの多様性を評価し, 単純GAが多様性を急速に失うが cellular GA は 最後まで多様性を維持していることを数値実験で示した.