コラム / 遺伝的アルゴリズム / 第2章

HOME 研究室概要 コラム 周辺探索 メンバー 掲示板 リンク

第2章 遺伝的アルゴリズムの処理手順

 遺伝的アルゴリズムの考え方については、前の章で説明しました。しかし、いくら遺伝的アルゴリズムが生物の進化の仕組みを模擬化したものだと説明しても、みなさんには、なかなかピンとこないと思います。

 そこで、本章では、実際の遺伝的アルゴリズムの処理手順について説明し、さまざまな方法についてお教えしたいと思います。

 このページの目次

2.1節 遺伝的アルゴリズムの処理手順
2.2節 初期集団の生成
2.3節 評価値の評価
2.4節 選択
2.5節 交叉
2.6節 突然変異

 2.1節 遺伝的アルゴリズムの処理手順

 遺伝的アルゴリズムの実際の処理手順は、次のようになっています。

  1. 初期集団の生成
  2. 終了条件が満たされるまでループ
    (a) 適応度の評価
    (b) 選択
    (c) 交叉
    (d) 突然変異

 また、その遺伝的アルゴリズムのフローチャートは、図.3のようになります。

遺伝的アルゴリズムのフローチャート

図.3: 遺伝的アルゴリズムのフローチャート


 2.2節 初期集団の生成

 まず、初期集団の生成を行います。一般には、決められた個体数の染色体をランダムに生成します。染色体は遺伝情報を伝える実体として存在しています。実際の生物では、これは塩基で構成されていますが、遺伝的アルゴリズムでは、データ領域や配列が考えられます。

 2.3節 適応度の評価

 次に各々個体に対して適応度の評価を行います。適応度は、どれだけその個体が優れているかを示したもので、値が大きいほど良いとします。一般に、予め定めておいた評価関数と呼ばれる関数を用いて、各個体ごとに求められます。解こうとする問題ごとに方法は違ってきますが、基本はよりよい個体が高い適応度の評価をされるということです。

 2.4節 選択

 各々の個体に適応度が決定されたら、それを基に選択交配を行います。基本的には、適応度の高い個体がより多くの子孫を残すような機構になっています。現在までに、いくつかの方法が提案されていますが、ここでは、その中で代表的な方法を紹介します。

選択

図.4: 選択

『適応度比例戦略』

 適応度に比例して、親として選択される確率をさだてめ、その確率にしたがって、ランダムに選びます。

  個体数を n 、ある個体 i の適応度を f i とします。すると、ある個体 i が、各々の選択で選ばれる確率 p i は、次式のようになります。

適応度比例戦略の式

『エリート保存戦略』

 最も適応度の高い固体をそのまま次世代に複製する方法です。この方法を採用すると、その時点で最も良い解が選択、突然変異で壊されない利点があります。普通は、他の戦略と組み合わせて用います。

『トーナメント戦略』

 ランダムに複数の個体を選び、最も適応度の高いものを親として残します。トーナメントを行う個体の数は、2が一般的ですが、より大きく設定する場合もあります。

 2.5節 交叉

 選択交配を行う個体対が決定されたら、染色体の交叉を行います。交叉とは、基本的には選択によって選出された個体に対して、ある交叉位置で双方の染色体の一部ずつを採ってきて、子孫の染色体を作ります。ただし、ある遺伝子座には、同じ遺伝子座から、どちらかの親の遺伝子を複製します。

『1点交叉』

 最も単純な方法は、交叉点を1箇所選んで、その前と後で、遺伝子を入れ替える方法です。これを1点交叉と言います。

1点交叉

図.5: 1点交叉

『多点交叉』

 1点交叉は、交叉点が1箇所でしたが、これを複数点にしたのが多点交叉です。

『一様交叉』

 あらかじめ用意したマスク(一般には、ランダムなビット列)を用い、マスクパターンが 0 の位置では、子Aには親Aの遺伝子を、 1 の位置では、親Bの遺伝子をコピーします。子Bに関しては、これの逆を行います。一様交叉は多点交叉の一種と考えることができます。

一様交叉

図.6: 一様交叉

 2.6節 突然変異

 最後に、突然変異を加えます。これは、ある確率で染色体の一部の値を変える操作です。もともと交叉だけでは、個体の親に依存するような限られた範囲の子しか生成することができません。突然変異は、染色体上のある遺伝子を一定の突然変異率で、他の対立遺伝子に置き換えることにより、交叉だけでは生成できない子を生成して個体群の多様性を維持する働きをします。

突然変異

図.7: 突然変異

 これらの操作を終了すると、新しい世代の個体集団が作られたことになります。そして、この新たな集団に対して、終了条件を満たすまで、また適応度の評価、選択交配、突然変異を行います。

 以上が遺伝的アルゴリズムの一連の流れです。みなさんもこれで、遺伝的アルゴリズムの動きが良くわかったと思います。次章では、この遺伝的アルゴリズムを用いると、一体どのような効果があるかについて説明していきたいと思います。

ページの上へ 前の章へ 上のページへ 次の章へ


企画・製作 村上・泉田研究室 HP製作委員会(2001)
ご意見・お問い合わせは、こちら までどうぞ。