２．探索法としてのＧＡ

ここではＧＡをさまざまな探索法と比較してみたいと思います。

まず、もっとも簡単な探索法として、全探索が考えられます。解の全ての可能性について調べてみるというものです。これは、はっきりいって探索法といえるようなものではありませんね。例えば、地図の中の最も標高の高い地点を探すときに、地図の左上の角から右へ順番に移っていき、右端まで来たら次の列を左から順に調べて行き、最後まで調べ終わって一番標高の高かった地点が答えというわけです。

もう少し探索法らしいものでは、ランダムサーチが考えられます。ランダムサーチでは解のすべての可能性の空間を考え、その中から無作為に選び出した解が条件に適合するか判定するというものです。この方法では探索のアルゴリズムなどないに等しく、くじを引くのと同じです。地図上の標高を調べる例で言うと、ルーレットを回して出てきた数値の座標を調べるといった手法です。したがって、一定回調べて一番標高の高かった地点を答えとします。

次に簡単な探索法として山登り法（最急勾配法）が考えられます。この手法は現在の状態から、もっとも評価のよくなる方向へ変化させるというものです。地図上の標高を調べる例で言うと、初期地点から隣り合うすべての地点の中で最も標高の高い地点への移動を繰り返すという手法です。この場合はより標高の高い地点に移動できなくなった地点が答えとなります山頂を目指して山登りをする感じですね。

上にあげた探索法は、単純な手法としては代表的なものですが、それぞれ欠点があります。全探索では必ず標高の最も高い地点は見つかりますが、調べるべき地点が多い場合には計算時間が非常に長くなってします。ランダムサーチではくじを引くようなものですから、１０万地点ある地図を調べるときにランダムで１万地点を調べるとすると運が悪ければ、標高の高い地点が全く見つからない可能性があります。山登り法では初期地点によっては、一つの山頂にはたどりついたものの、別なところにもっと高い山があったといった事になりかねません。これを局所安定とか局所最適と言います。

それではＧＡの探索について考えてみます。ＧＡ探索は、初期集団から選択と交叉の組み合わせにより並列的に山登り探索をし、なおかつ突然変異によりときどきランダムな変化を起こしています。いわゆる焼きなまし法（シミュレーテッドアニーリング）のようなことを並列的に行っているわけです。

つまり、ＧＡはランダムサーチと山登り法の両方の特性をあわせ持っていると言えるでしょう。複数の解について並列的に調べていくため、山登り法のような局所安定には陥りにくくなっています。さらに、それでも局所安定解に近づいてしまったとしても、突然変異によりそこから抜けだすことができます。

ＧＡの難点は個体数、世代数、交叉や突然変異の確率などのパラメータやコーディングの一般的手法が確立されていないというところにあるでしょう。それから、必ず最適解を求めなくてはならないという場合にも使えません。しかし、ある程度の基準以上の解をなるべく少ない計算量で求めたいというような場合（一般的にはこのような問題が多いと思います）には、なかなかいい手法ではないでしょうか。