遺伝的アルゴリズムとその特徴

並列GAの説明に入る前に, まず Holland 流の単純 GA [15] (SGA: Simple GA)について簡単にまとめる.

単純GAにおける個体(individual)は有限固定長の文字列である. 文字の値として普通は 0/1をとるが, 有限種類のアルファベットを使う場合もある. 個体の集合を集団 (population)と呼び, 個体数は世代を通じて一定である. 文字列には必ずある実数値が 対応し, その個体の適応度(fitness)と呼ぶ. 単純GAの主たる目的は最適化問題であり, 適応度は最適化すべき関数である. 単純GAは以下の手順に従う.

1 初期化:

ランダムな値を持つ個体を N 個生成し, 初期 集団を形成する.

2 複製:

各個体を適応度に比例した確率で複製する. これをルーレット選択と呼ぶ.

3 交配:

設定された交配確率に従って, ランダムにペ アを作り一点で交叉する.

4 突然変異:

設定された確率／方法に従い, 個体の一 部分の値を変更する. 2に戻る.

複製(reproduction), 交配(crossover), 突然変異(mutation)の1サイクルを世代 (generation)と呼ぶ.

単純GAの難点として過剰収束問題(premature convergence problem)がある. 相対的に適応度の高い個体が存在すると, 競争原理が働き過ぎて, まだ十分に探索が行 なわれないにも関わらずその個体によって集団が占拠されてしまう現象である. このた め優秀な形質を一部持っているにも関わらず適応度が低い個体が死滅し, 大域的な探索 が行なわれる前に局所最適値に収束してしまうという問題である. 過剰収束問題は古く から指摘されており, 適応度の計算方法や遺伝オペレータに改良を加えて, 過剰収束を 回避する試みがなされてきた [5] .

De Jong [7] は crowding factor (混雑因子)を導入し, 子個体は 集団の中でより似ている (ハミング距離が近い)個体と置き換わり易いようなメカニズ ムを提案した . Mauldin のuniqness (唯一性)オペレータは, 集団のすべての 個体からハミング距離の意味で一定以上異なっていなければ, 子個体が集団に加われな いことで多様性を維持する方法である. Deb と Goldberg [6] の sharing function も個体間の類似性を評価する関数であり, 類似した個体群で集団が 埋め尽くされるのを防止している.

初期段階では適応度が全体として低いレベルにあるので, 高い適応度を持つ個体が一つ 生成されると, 相対的な評価が非常に高くなり過剰に複製されてしまうことがある. そこで, 適応度の最大値と最小値の差を基準にスケーリングを施し, 適応度の過剰なバラ ツキを防止する方法がある. また, 適応度を値そのものではなく, 集団全体の中での順 位(ranking)によって評価する方法もある[11] .

しかしながら, これらの方法は収束性を改善するものの, 特殊な遺伝オペレータを追 加したり, 多大な計算コストを要したり, 対象とする問題分野に依存していたりするた め, 結局ロバストな解法とは言い難かった.