遺伝的アルゴリズムとは？わかりやすく解説！

今回は、AIの分野でよく使われる「遺伝的アルゴリズム」について解説していきたいと思います。

遺伝的アルゴリズムとは、簡単に言えば「優秀な遺伝子を残していくぞー！！」っていう学習方法です。

比較的簡単に実装ができるという点も魅力の一つです。

私も、遺伝的アルゴリズムにはお世話になっております。

それでは解説していきます！

遺伝的アルゴリズム(Genetic Algorithm)とは？

遺伝的アルゴリズムとは、生物の進化の仕組みを模した、近似解を探索するアルゴリズムです。

英語では「Genetic Algorithm」と書きその頭文字をとってよく「GA」と略されます。

生物の進化は、環境に適応する個体が生き残り、環境に適応できない個体が死んでいくということを繰り返しでできています。

例えば、寒い地域では寒さに耐えられる遺伝子を持った個体が生き残り、そうでない個体は絶滅していきます。

だから結果的に、寒い地域には、寒さに耐えられるようなモフモフの毛をもった動物たちがいるのです。

遺伝的アルゴリズムは、この環境や問題に対する適応度をもとに、優秀な個体を次世代へと受け継ぎ、優秀でない個体を排除するという大まかな考え方のもとに成り立ちます。

最終世代を迎えたときに、一番適応度の高い個体の遺伝子情報がその問題の解となります。

では、具体的に遺伝的アルゴリズムがどのような流れで実現しているか見ていきましょう。

遺伝的アルゴリズムにおいての遺伝子って結局なに？

遺伝的アルゴリズムには「遺伝子」が必要不可欠です。

しかし、この遺伝子が結局プログラム上で何を意味するのかを知っておかなければなりません。

遺伝的アルゴリズムにおいての遺伝子とは、パラメータや解だと思ってください。

例えば、テトリスのAIであれば、盤面を評価するためのパラメータです。

• 凸凹をどのくらい重視するのか？
• 平均的な高さをどのくらい重視するのか？

といったような評価の重みを遺伝子として表すのです。

ほかにも最短経路問題であれば、通る場所の順番を遺伝子として表すこともできます。

本当は文字じゃないですが、[北海道,東京,大阪,福岡,沖縄]といったように。

このように、何を遺伝子として持たせるのかは、遺伝的アルゴリズムを適用する問題によって異なります。

実数解を遺伝子として持つのか、または、0か1のどちらかを遺伝子として持つのか、はたまた、（X, Y）といったような座標を遺伝子として持つのか。

いろんな場合が考えられます。

遺伝的アルゴリズムの流れ

遺伝的アルゴリズムの流れを簡単に見ていきましょう。

①複数の個体をランダムに生成する

まずは、一世代目の個体をランダムに生成してあげる必要があります。

なので、各遺伝子（各パラメータ）はテキトーです。

②それぞれの個体の適応度を計算する

次は、その世代の全個体の適応度を計算します。

例えば、ゲームの強化学習AIであれば、実際にその遺伝子情報に基づいてゲームをプレイして、どのくらい報酬を獲得できたかが適応度になります。

ほかにも、最短経路問題であれば、その遺伝子に対応する経路の距離がそのまま適応度になります。

あえて評価のイメージを書くとすれば、以下のような感じです。

個体0	個体1	個体2	個体3	個体4	個体5	個体6	個体7	個体8	個体9
10点	5点	8点	21点	4点	3点	9点	8点	12点	25点

③次世代の生成「選択」「交叉」「突然変異」

この工程が遺伝的アルゴリズムにおいて一番重要なポイントだといっても過言ではありません。

この工程では、次世代の生成を行います。

その方法として、まず「選択」「交叉」のいずれかの操作を次世代の個体数に達するまで繰り返し行うということをします。

生成は以下の動画（1:50～）がわかりやすいです。

下に詳しい解説を書きますが、ここでは、

• 選択：どれか一つの個体を選んで遺伝子をそのままコピー
• 交叉：どれか二つの個体を選んで遺伝子をいろいろ入れ替える

このようにとらえてください。

どちらかの方法により、次世代の個体が生成されていき、これを現世代と同じ個体数になるまで繰り返します。

1個体を生成するのに「選択」と「交叉」のどちらの方法が選ばれるかは、確率によって決める方法もあれば、あらかじめ決めておいた個体数を選択で生成してそれ以降はすべて交叉で生成するといった方法もとることができます。

また、選択においての1個体の選び方、交叉においての2個体の選び方も多種多様です。

そして次世代の個体生成が終わると「突然変異」の段階に入ります。

• 突然変異：どれか一つの個体を選んで遺伝子の一部を変化させる

これは、ある一定の確率で生成した次世代の個体の遺伝子が変化することを意味します。

突然変異確率は0.1%～1%程度の非常に小さい値でないと、うまく機能しないとも言われています。

これらの段階を踏んで、次世代の個体が生成され次の世代交代へと進んでいきます。

④世代交代

次世代の生成が終われば、悲しいですが現世代はもう必要ありません。

つまり今回の例では、1世代目から2世代目を生成したので、1世代目が役目を終えることとなります。

そして、新しく生成された2世代目が「現世代」と呼ばれ、あとは①からの繰り返しを行うことになります。

つまり、2世代目の適応度が計算され、それによって3世代目が生まれるといったように、この繰り返しをG世代目まで行うこととなります。

一般に遺伝的アルゴリズムに使われる個体数をN（体）、解を決定する最終世代のことをG（世代）と呼びます。

⑤最終世代のもっとも適応度の高い個体が解となる

②～④の繰り返しが終わり、最終世代の適応度の評価が終われば、その中の一番適応度の高い個体が、この遺伝的アルゴリズムの解となります。

遺伝的操作「選択」「交叉」「突然変異」とは？

遺伝的アルゴリズムにおいて、とても重要な「次世代の生成」。

次世代の生成は、現世代の個体を用いて行います。

それぞれ方式について深いところまでは触れませんが、ざっと書いてみます。

選択（selection）とは？

選択とは、「コピー」です。

「ならそう書けよっ！」という話なのですが、遺伝的アルゴリズムでは選択という風に呼ばれるのです。

もっと言えば、選択とは、生物の「自然淘汰」をモデル化したものです。

自然淘汰とは、簡単に言ってしまえば「強いものが生き残る」ということです。

弱いものは数を減らし、強いものが生き残る。

この考えが遺伝的アルゴリズムには導入されています。

遺伝的アルゴリズムでいえば、「適応度が高い個体」「優秀な個体」の遺伝子が高確率で受け継がれるといえるでしょう。

仕組みはいろいろありますが意外と簡単です。

ルーレット方式

ルーレット方式は、適応度の分だけ当たりやすいくじ引きのような方法です。

適応度が高い個体は、それだけ選択される可能性が高くなります。

ランキング方式

ランキング方式は、適応度が高い順にランキングをつけて、1位には30%、2位には20%、3位には15%、4位には10%といったように、選択される確率をあらかじめて決めておく方式です。

適応度の差があまりない場合でも、ランクによって確率に大きな差が生じることがあります。

逆に、奇跡的に適応度がとても高い個体が生まれたとしても、選択確率に上限があるために選択されない場合もあります。

トーナメント方式

トーナメント方式は、複数の個体を選択し、その中で適応度の一番高い個体が選択されるという方式です。

例えば、10体の個体の中から4体をまず選び、その中から適応度が一番高い個体を選ぶというようなもの。

エリート選択方式

エリート選択方式は、「もう優秀な個体はとっとこうよ」って方式です。

ほかの選択方式では、一番優秀な個体は比較的高確率で選択対象とされるのですが、そうならないことも大いにあります。

そんな中エリート選択方式は「一番優秀な個体は絶対次世代にコピーします」宣言をしているようなものなので、その心配はありません。

しかし、優秀な個体は絶対次世代に受け継がれるというのがそもそも遺伝的アルゴリズムとしてうまく働くのかは吟味する必要があります。（局所解に陥ることへの懸念など）

交叉（crossover）とは？

交叉とは、生物の「交配」をモデル化したもので、組み換えとも呼ばれます。

生物は交配によって子孫を残す際に、子孫は親の遺伝子を受け継ぎます。

親Aと親Bがいた場合、親Aからはパラメータ0~4を受け継ぎ、親Bからはパラメータ5~10を受け継ぐといったことが可能になります。

交叉にもいくつか種類があります。

一点交叉

一点交叉は、遺伝子番号をランダムに1つ選び、そこから後ろの遺伝子を丸ごと入れ替える手法です。

切る場所は一つ。

なので、とても単純で分かりやすいのですが、あまり効率が良くないといわれています。

二点交叉

二点交叉は、遺伝子番号をランダムで2つ選び、その間の遺伝子を2個体間でそのまま入れ替える手法です。

1~100の遺伝子情報があったとして、その中から適当に2つの遺伝子番号を選択します。

それが、51と60だった場合、51~60までの10個の遺伝子をそっくりそのまま交換するみたいなことです。

細かいところは置いといて、選んだ2点に挟まれた遺伝子を交換するみたいなイメージです。

一様交叉

一様交叉は、一つ一つの遺伝子がある決まった確率（1/2の確率など）で交換されるかされないかが決まる手法です。

上の交叉方法は、連続したパラメータをごっそり入れ替える手法ともとらえられますが、

一様交叉は、一つ一つが独立して交換されるかされないかが決まるという点で違いがあります。

ほかにも、多点交叉や順列問題の交叉など多種多様な交叉方式があります。

突然変異（mutation）とは？

突然変異は、遺伝的アルゴリズムにおいて重要な役目を担います。

単語の意味からも容易に想像ができますが、突然変異とは、

「ある一定の確率で遺伝子が変化すること」を指します。

例えば、突然変異確率0.5%の場合、200回に1回のペースで遺伝子が変化します。

代表的な突然変異の方式は、

• 前の状態に関係なくまったく別の遺伝子に置き換わる「置換」
• 前の状態から少し変化が起こる「摂動」

があります。（ほかにもいろいろ）

この突然変異があることによって、遺伝的アルゴリズムが「局所解に陥ること」を防いでいます。

全体最適解と局所最適解 - Qiita

ここでは、その代表的な突然変異の方式である「置換」と「摂動」を紹介します。

置換（substitution）

置換は、ランダムに選ばれた遺伝子をそっくりそのままほかの値に入れ替える方式です。

選ばれた遺伝子情報が0であろうと1であろうと100であろうとお構いなしに、全く別の値へ変更されます。

遺伝子情報がバイナリ（0 or 1）によって表現されるときに、その値が反転するといった用途で使われます。

摂動（perturbation）

摂動は、ランダムに選ばれた遺伝子にちょっと値を足したり引いたりする方式です。

例えば、100 →101だとか100 → 96だとかそうゆうことです。

置換と違い、前の遺伝子情報が影響するため、いきなり1から100といったようにぶっ飛んだ変更がされないという特徴を持ちます。

遺伝的アルゴリズムのわかりやすい解説動画

最後に、遺伝的アルゴリズムを用いて学習している参考動画をご紹介します。

遺伝的アルゴリズムを使った四足歩行の学習動画

遺伝的アルゴリズムを使って四足歩行を学習させている動画です。

あらかじめ4つの姿勢（それぞれ関節の角度を遺伝子として表現）を決めて置き、それらを繰り返すことで歩行を実現しようという試みです。

4つの姿勢があり、それぞれ8個の関節があるので、遺伝子一つは4×8=32個の遺伝子情報が必要ということになります。

世代が進むにつれ、すこしずつちゃんと歩けるようになっていきます。

遺伝的アルゴリズムで多関節の三脚が歩き方を学習する

こちらは、タコみたいな多関節の生物（？）に歩き方を学習させる動画です。

遺伝アルゴリズムを用いた最短経路問題

こちらは、上の二つの動画と少し違いますね。

すべての点を通って帰ってくることを条件に、より距離が短い経路を求める問題です。

https://www.youtube.com/watch?v=B3MeTjmX7UM

【ITエンジニア志望の学生限定】筆者が利用した就活エージェントを紹介！

「ITエンジニア志望だけど、就活って何から始めたらよいかわからない。」
「エンジニアになるには、どんなスキルがどのくらい求められるんだろう。」

このような悩みを抱えていないでしょうか？

実際私も「何から始めたらよいかわからない」状態のときがありました。

そんな方は、まず騙されたと思って「レバテックルーキー」というITエンジニア専門の就活エージェントに登録してみてください。

まだまだ魅力がありますが、それを書くと長くなってしまうので、気になる方は以下の記事をご覧ください。

そんな「レバテックルーキー」ですが、サービスを受けるには2つの条件をクリアしている必要があります。

• 大学生・大学院生・専門学生・高専生・短大生である【文系・理系・情報系は問わない】
• ITエンジニア志望・もしくは興味がある

この条件に当てはまる方は、ぜひとも早めに登録することをおすすめします。（就活は早めにはじめると超有利になります。）

＼ カウンセリング~内定まで"全て無料"！ ／

レバテックルーキーの公式サイト

【優良企業に就職したい大学生へ】実務レベルのスキルを身に着けよう。

「ITエンジニアとして就職したいけど、プログラミングスキルがないのが不安。」
「大学でプログラミングの授業を受けたけど、全然自信がない。」

こんな悩みを持った大学生におすすめなのが「レバテックカレッジ」です。

「レバテックカレッジ」は大学生・大学院生専用のプログラミングスクールで、 Web開発の企業に求められる ECサイトやSNSの構築などのWebアプリ開発のスキルを学ぶことができます。

また、スキルを学ぶだけでなく就活のサポートもガッツリ受けられるので、プログラミングスキル習得から就活・内定まで一気通貫でサポートしてもらいたいという大学生の方にピッタリのサービスとなっています。

レバテックカレッジの公式サイト

最後にこの記事を読んでくださった方におすすめの記事を張って終わりとします。

以上「遺伝的アルゴリズムとは？わかりやすく解説！」でした！