遺伝的アルゴリズム

投稿者: | 2012年5月22日

1.はじめに

遺伝的アルゴリズムを自己流に解釈すると、こんな感じです。

  • 「ある問題に対する最適な解の組み合わせを模索してくれるシステム」

例えば、プレイヤーが「剣で切りつけてきた」とします。この場合のCPUの反撃パターンとして、以下の要素があります。

  1. 距離はどのくらいを保つのか?
  2. どのようなアクションを返すのか?
  3. 今の状態は?

1については、例えば以下のような解があります。

  • 近距離
  • 中距離
  • 長距離

2については、例えば以下のような解があります。

  • 剣で反撃
  • 弓で攻撃
  • 魔法を使う
  • 様子を伺う(何もしない)
  • 逃走する

3については、例えば以下のような状態があるとします。

  • 健康
  • 少し怪我
  • ピンチ

このような「解の組み合わせ」を、if~else if~…で判断するのは大変です。また、プレイヤーの行動パターンには「魔法で攻撃」「弓で攻撃」など、様々な種類があるため、if~else if~…で対応するのは、気が遠くなりそうです。さらに、武器も「短剣」や「ロングソード」があり、、、となると、組み合わせは膨大な量となります。

そこで、この組み合わせをランダムに決めて、プレイヤーにぶつけた結果、より良い結果が得られた組み合わせを、次回の思考ルーチンにする、というのが、遺伝的アルゴリズムとなります。

2.仕組み

遺伝的アルゴリズムの、大まかな流れは以下のようになります。

「第一次世代」とは、ランダムで解の「組み合わせ」を生成することです。

次に「第一次世代」がプレイヤーに与えた影響を評価します。

これが「適正評価」です。

先ほどの例で言えば、

  • その行動がプレイヤーに与えた損害(プラス要素)
  • その行動によって自身がこうむった損害(マイナス要素)

を算出します。

この値は「ダメージ量」などの具体的な数値になります。もし、プレイヤーを倒せた場合には高い評価を与え、やられた場合には最低の評価となります。そして、その評価を元に次の世代に残す種を「選択」します。例えば、最も高い評価であった「組み合わせ」と次に評価の高い「組み合わせ」を残すとします。

最後に「進化」です。先ほど残した2つの「組み合わせ」を掛け合わせます。イメージとしてはこんな感じです。

この処理を交叉(こうさ)といいます。図では2つの「組み合わせ」を交互に掛け合わせていますが、そのルールは全く自由です。(組み合わせ順はランダムであるのが一番楽かもしれません)

こうして組み合わせのパターンをいくつか作り、それをプレイヤーにぶつけて、評価して、、、という処理を繰り返すことにより、最強の思考ルーチンを作成することができるわけです。

3.突然変異

実は、このままでは最初のランダムな組み合わせを最適な組み合わせに再構築しているだけなので、ある時点で進化が止まってしまいます。そこで、低確率で「突然変異」を発生させます。具体的には、第一次世代で起こしたランダムな組み合わせを、再び部分的に発生させます。

下から3番目に、不確定な要素の「G」を発生させています。これが「突然変異」です。これにより「突然変異」が高い評価を受ければ進化をする、という仕組みが出来上がります。