なんぞや遺伝的アルゴリズム～人工知能に触れてみよう～: 具体的な流れ

Home

概要

具体的な流れ

実際に使ってみよう

まとめ

「アベノミクス」といえばみなさんご存知でしょう。三本の矢の一つである「成長戦略」実施のため「日本再興戦略」が策定されています。この辺りまでは知っている人も多いのではないでしょうか。

今年2016年の「日本再興戦略2016」では「第4次産業革命」が取り上げられています。第4次産業革命のため、IoT、ビッグデータ、人工知能（AI）、ロボットの活用が重要であるとされています。（参考：日本経済再生本部、「日本再興戦略2016-第4次産業革命に向けて-」）

AIは日本経済の観点からも注目されていると言えるのではないでしょうか。様々な分野において、AIがこれまで以上に活躍することに期待します。

GAは次のステップに大別されます。

1. 初期配列決定

2. 交叉

3. 突然変異

4. 評価

5. 淘汰

6. 終了判定（終了しなければ2に戻る）

上のステップを良い答えが見つかるまで繰り返すことで、目的とする答えを求めます。

このページでは、これらのステップを順に説明していきます。

冒頭で説明した通りGAは、生物の進化のように各種個体同士で、子孫を作ったり、淘汰されたりして最適な解を求めるものです。

そしてここで出てくる個体は次のような数列で表現されます。（初期配列決定）

01000110 or 26382624738 or 141233113 etc....

この初期配列は、解く問題によって変わります。「01000110」のように「0」と「1」で構成されるものもあれば「26382624738」のように「1～9」の数字で表されるものもあります。一般的には「0」か「1」で表されることが多いようです。また数列の長さも問題によってその都度設定されます。

これらの数字の意味はそれぞれの個体の「特徴」を表しており、また桁によって意味が変わってきます。

馬の特徴を例に考えてみましょう。「0」がその特徴がない、「1」がその特徴があるとして、1桁目が足が速い、2桁目が健康状態が良い、3桁目が血統が良い、というように設定したとします。

ある馬が、全部良いなら「111」

ある馬が、全部ダメなら「000」

ある馬が、足も健康状態も良いが血統が良くない場合は「110」

逆に「101」とあったなら、その馬は足と血統は良いが、健康状態がダメというように表されます。

交叉は次の世代の子を作る過程です。2つの個体（親）を色々な方法で組み合わせて、新たな2つの個体（子）を作ります。

例えば次のような感じです

交叉法には色々あります。代表的かつ簡単なものは次の一点交叉法と二点交叉法です。

• 一点交叉法
  遺伝子に一か所ランダムに切れ目を決めて、それ以降を入れ替えて子を作る方法です。
  上図がこの方法で交叉していて、図では、2桁目と3桁目の間に切れ目があり、それ以降が入れ替わっています。
  
  
• 二点交叉法
  切れ目が2つになったのがこの方法。切れ目と切れ目の間が入れ替わります。
  下図では、1桁目と2桁目、3桁目と4桁目に切れ目がありその間が入れ替わっています。

ある与えられた確率で、突然変異を起こさせます。こうすることで、よりよい解に到達する可能性が出てきます。ただあんまり突然変異ばっかり起こるのも良くないので一般的には確率を低くしています。

突然変異の方法としては、

• ランダムに選ばれた遺伝子が、反対の特徴を持つ遺伝子に変わる。（0 ⇒1　or 1⇒0）
• ランダムに選ばれた遺伝子にランダムな値が入る。（5 ⇒1、3 ⇒6など）
• ランダムに選ばれた遺伝子同士が入れ替わる。

などがあります。

例）　※赤い数に突然変異が起きています。

• 1001110 　 ⇒ 1001111
  
  
• 43459137   ⇒ 43452137 
  
  
• 100100110 ⇒ 100110100

GAには適応度という考えがあります。簡単に言えば得点付けで、どの個体がどれだけ優れているかを表す指標です。これにより個体を評価します。

適応度についても初期配列と同様、問題に合わせて自由に設定できます。ただこの設定がテキトーすぎると解もテキトーなものしかできないので注意です。

先程の馬の例で考えてみましょう。例えば「足が速いほど良く、健康もそこそこで血統はどうでも良い」そんな馬が欲しいとします。

この場合、足が速い馬の得点が高くなるように設定すれば良いことになります。

なので、足が速いなら3点、健康が良いなら2点、血統はどうでも良いので0点というように得点を設定します。

こうすれば

• 「足が速い、健康ダメ、血統ダメ」⇒「100」⇒1×3+0×2+0×0＝3点
• 「足が遅い、健康良し、血統良し」⇒「011」⇒0×3+1×2+1×0＝2点
• 「足が速い、健康良し、血統ダメ」⇒「110」⇒1×3+1×2+0×0＝5点

上のように足が速い馬ほど評価が良くなります。

これまでの過程で全体の個体数は「最初の個体数＋交叉で生まれた個体数」になっています。

この淘汰の段階では、最初の個体数と同じ数まで環境に適応しない（＝適応度が低い）個体を淘汰します。

淘汰後に残った個体が次世代の親となり、これまでの過程を今度はこの新しい集団で繰り返す、これが遺伝的アルゴリズムの大まかな流れになります。

この淘汰方法にもいろいろあり、適応度に基づいてルーレットを作りそこから選ぶ「ルーレット選択方式」や適応度が高い方が勝ち残る「トーナメント方式」があります。

ルーレット選択方式 個体数が4でこの中から2個選ぶ場合を考え、適応度に応じて決められたルーレットが右図のようになるとします。 ルーレットを2回だけ回して、そこで選ばれた個体が次世代に残るというのがルーレット選択です。適応度が最も高いAが最も選ばれやすいですが、適応度が低いCやDも選ばれる可能性があります。

トーナメント方式 適応度が「A＞B＞C＞D」の4個の個体から2個を選ぶ場合を考えます。トーナメントはランダムに作成され、右図のようになったとします。 適応度は「A＞B」、「C＞D」なので、このトーナメントではAとCが選ばれる（勝ち残る）ことが分かります。適応度が最も高いAは選ばれ最も低いDは選ばれませんが、トーナメントの組み合わせ次第（右図）では、2番目に適応度が高いBが選ばれないこともあります。

ここで、「適応度が低い個体が選ばれても良いの？」と思う方がいるかもしれません。対応策として、単純に適応度の高い個体を残しておく「エリート保存戦略」が補助的に用いられます。例えば、4個の個体（適応度がA＞B＞C＞D）から2個を選ぶ場合、そのうち1個は最も優秀な（適応度が高い）個体を選びます。ここでは個体Aが選ばれます（エリート保存）。残りの個体（ここでは残り1個）を選ぶとき、後は普通にルーレット選択方式やトーナメント方式を用います。現在最も優秀な個体Aが次世代の親の1つとなるため、適応度が低い個体のみが残るという事態を回避できます。

GAのステップについて説明しました。この後は、交叉～淘汰を繰り返すだけですね！

しかし、「何回繰り返せばいいの？」と思うことでしょう。

何もしないと永遠に繰り返すことになるため、これを満たせば繰り返し（ループ）を終えるという終了条件を設定し、条件を満たしているかループ1回ごとに判定（終了判定）を行います。条件を満たすとループ終了となります。

一般的に、「N回ループした時」、「個体の適応度がxを超えた時」（Nやxの具体的な値は自分で決める）などを終了条件とします。