単純GAの性能評価

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

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