IV. 遺伝的アルゴリズム

基本的記述

進化に関するダーウィンの理論によって起こされました。 遺伝的アルゴリズムによって解かれる問題の解は進化します。

アルゴリズムは、個体群と呼ばれる解(染色体によって表現される)の集団で始まります。 １つの個体群から解が抜き取られ、新しい個体群を形成するために使われます。 これは、新しい個体群は古いものよりも良いという期待に動機付けられます。 新しく形成された解(子孫)に選ばれる解は、彼ら(解)の適合度によって選ばれます。 より適合しているものは、より再生されるチャンスがあります。

これがある状態（例えば個体群の数、最も良い解が改善される）が満足されるまで続けられます。

サンプル
探索空間の章からすでにご存知のように、問題解決の方法は、しばしば関数の極値を探すことによって表わされます。 ここにちょうど問題が示されています。 いくつかの関数が与えられて、ＧＡは関数の最小値を探そうとします。
Start ボタンを押すと、下のアプレットで遺伝的アルゴリズムを実行できます。グラフは探索空間を表し、縦線は解を表しています。赤い線が最良の解、緑の線がその他の解です。Start はアルゴリズムを開始し、Step は 1 ステップだけ実行し、Stop は停止、Reset は個体群を初期状態に戻します。





基本的な遺伝的アルゴリズムの概要

  1. [スタート] n 個の染色体からなるランダムな個体群を生成する
  2. [適合度] 個体群内のすべての染色体xの適合度f(x) を評価する
  3. [新しい個体群] 新しい個体群が完成するまで、次のステップを繰り返すことにより新しい個体群を創り出す
    1. [選択] 適合度により個体群の中から両親となる２つの染色体を選び出す(良い適合度になるにつれ、選ばれるチャンスは広がります)
    2. [交叉] 交叉確率に従って、新しい子孫（子供）を作り出す親を交叉させます。 もし交叉が行われない場合には、親がそっくりコピーされます。
    3. [突然変異] 突然変異確率に従って、新しい子孫のすべての位置（染色体上の位置）にたいして、突然変異を行います
    4. [受け入れ] 新しい子孫を新しい個体群に入れる
  4. [置き換え] アルゴリズムの次の実行のために、新しく生成された個体群を使います
  5. [テスト] 最終条件が満たされたら、終了し、現在の個体群の最良の解を返します。
  6. [ループ] 2へ戻る

見てわかるように、基本的なＧＡの概要は非常に一般的です。 様々な問題について違った実装が可能です。

はじめの疑問は、どんなタイプのエンコードを選んで、染色体を作ればいいかということです。 これは、交叉、突然変異という、GAの２つの基本的なオペレータにも関係してきます。 交叉と突然変異については次の章で紹介します。

次の疑問は、どのように交叉のための親を選択するかということです。 これはいろいろな方法で行うことができますが、主な考え方は他のに比べて良い両親を選ぶということです（他のより良い両親は、良い子孫を残すという希望がこめられています）。 また、あなたは新しい子孫だけで新しい個体群を作ると、現在の個体群のもっともよい染色体が失われてしまうと思うかもしれません。 これは本当です、エリート主義と呼ばれるものがしばしば使われます。 これは、少なくとも１つの最も良い解は、なんの変更もなしに新しい個体群にコピーされます。 ですから、見つかったもっともよい解は実行の最後まで生き残ります。

いくつかの関係した疑問は、後で議論します

ひょっとしたら、あなたは何故遺伝的アルゴリズムが機能するのか不思議におもうかもしれません。 それは、部分的にはスキーマ理論(Holland)によって説明することができます、 しかしながらこの定理は、最近非難にさらされています。 もしもっと知りたいのであれば、他の資料を見てください。