初めに

まずは遺伝的アルゴリズムの基本概念から説明します。

全体の流れ

  1. 染色体をランダムに生成します
  2. 染色体の適応度と選択される確率を計算します
  3. 交差を行う。N-M個染色体を生成します
  4. 上で生成したN-M個染色体を変異させます
  5. 複製操作により、M個適応度のいい染色体を次の世代にコピーします
  6. 2~5の操作を繰り返します

遺伝子と染色体

数学問題を考えよう

x+2y+3z<0

こういう不等式が複数の解をもつ場合が多いです。一つの解が一つの染色体となります。その染色体の中のx,y,zは遺伝子と呼ばれます。

適応度関数

自然淘汰や増殖のため、染色体ごとに評価するものが適応度関数と呼ばれます。世代交代のたびに、新たな染色体が生成し、評価されます。点数の高い染色体だけ残します。

交差

前の世代の染色体の中から二つ選び、ある位置から分割し、分割されたものを組み合わせすると、新しい染色体になります。

例えば

親1: 2 3 4 5 6 7 -> 2 3 + 4 5 6 7

親2: 1 5 9 3 5 2 -> 1 5 + 9 3 5 2

子: 2 3 9 3 5 2

染色体選択はランダムではなく、ルーレットで親染色体を選びます。

世代交代という過程が進化と呼び、進化するたびに、染色体の適応度を計算し、以下の式で 選択される確率を計算します。適応度が高いほど、選択される確率が高いです。これがいい染色体が残られる理由です。

染色体aが選択される確率 =染色体aの適応度/同世代すべて染色体の適応度の和

突然変異

交差だけでは、染色体の組み合わせで、局所最適解にたどり着けますけど、全域最適解を見つけるため、新たな染色体の遺伝子を書き換えて、探索範囲を広くすします。こうすると、全域最適解の探索に有利になります。

複製

進化たびに、前の世代のいい染色体をそのまま次の世代にコピーする必要があります。

進化ごとにN個染色体が必要だとすると、交差で生成する染色体がN-M個。残りのM個が前の世代の適応度の高いものをそのまま複製してきます。

python 実装については以下のリンクに参照できる 。http://darden.hatenablog.com/entry/2017/03/29/213948

終わりに

GAは組み合わせ最適化問題にふさわしいものであり、ほかのアルゴリズムとの組み合わせで、精度上げることができます。でもすべての最適化問題がGAを使えるわけではありません。

次回はGAの欠点について、改良版GAを紹介します。

(著:Hu

関連記事