【GA】遺伝的アルゴリズム(Genetic algorithm)とは？

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

先ほど述べたように遺伝子を用いて世代交代を繰り返していきます。今から具体的な手順を紹介するのですが、GAにもいろいろ種類があるのでこれは一例となります。

まず初めに①初期個体たちを作ります。その次に②その個体たちを評価（個体がどれだけ優秀かチェック）します。

そうしてその評価に基づいてその個体たちを③選択（評価に基づいてどの個体を交配させるか選ぶ）します。

次に④交叉（選んだ個体たちを交配させて子孫を作る）して、最後に⑤突然変異（ある確率で子孫たちの遺伝子の一部を変更する）を行います。

そうすると、子孫たちができるので、それらにまた評価、選択、交叉、突然変異を行っていくという形です。それを何回か繰り返して、最終的に良かった結果を出すという流れになります。

繰り返し（iteration）の回数は、50～100回くらいです。

これからそれぞれについて詳しく書いていきます。

初期個体の生成（initialization）

個体は大体は0と1で表されていて、初期個体はランダムに0と1を並べて作ることが多いです。

解きたい問題によっては、0と1の数などに条件がある場合があるので、それを守りながらランダムに生成したりします。

それを個体数だけ作ります。個体数は問題にもよりますが、10や20くらいが多いです。あまり個体数が多いと、計算の量が多くなったりうまく世代交代できなかったりします。

評価（evaluation）

ここでは、先ほど作った個体たちの能力を評価していきます。問題に個体の0と1の情報を与えて、計算させます。

この部分がメインの処理になるので、かなり時間がかかると思います。なので、個体の0と1が違っていても共通の計算がある場合まとめて計算すると、計算時間を短縮できると思います。

選択（choice）

先ほどの部分で、個体ごとに評価を出せたと思います。具体的な数値が出てきている場合が多いと思うので、次のようになっていると思います。

問題によっては、評価の値が小さいほうがいい場合もあります。

選択には何個か種類があって、代表的なものは、ルーレット選択・ランキング選択・エリート選択などがあります。時々、エリート選択とルーレット選択の両方が使われている場合もあります。

ルーレット選択（roulette choice）

ルーレット選択は、点数が高い（低い）ものを優先して選択する方法です。

上の例で行くと、個体1が選ばれる確率が100/100+70+130=約33%、個体2が選ばれる確率が70/100+70+130＝約23％、個体３が選ばれる確率が130/100+70+130＝約43％となります。

低いほうが良い場合は、1からそれぞれ上の確率を引きます。その確率で、個体の数だけ個体を選択します。重複する場合もあり、もし個体数が少なすぎると全部同じ遺伝子になったりします。

ランキング選択（ranking choice）

ランキング選択は、点数が高い（低い）順に順序を付けて、1位の個体は2つ生成、2位の個体は1つ生成、3位の個体は生成しないとしてしまう方法です。

ルーレット選択はもし点数に差がありすぎると、その優秀な個体が選ばれる確率が高すぎて選択されるのがその個体だけになってしまうというデメリットがあります。

しかし、ランキング選択は点数に差がありすぎてもある程度いろんな個体が選ばれるのでそこはメリットとなっています。

エリート選択（elite choice）

エリート選択は、必ず1番評価値の良いものを選択するという選択方法です。これを採用すれば、評価値が悪くなることがないので、良く採用されている選択方法です。

よくルーレット選択と併用して使われることが多いです。エリート選択のみ採用する場合は、残りの個体はランダムに選択したりします。

交叉（crossover）

交叉というのは、2つの個体を使ってそれらを親として子孫を作るという作業になります。

この交叉にも1点交叉や2点交叉など種類があります。この交叉には交叉率というパラメーターがあって、その割合に従って交叉を行います。だいたい60％くらいが多いです。

1点交叉（one-point crossover）

1点交叉は遺伝子の並びのうち、1か所場所を決めて、2つの親の間でその前後を入れ替える作業となります。

そうしてできた2つの遺伝子を2体の子孫とします。もし上の選択でエリート選択を採用していたら、エリートの個体は交叉で選ばないようにしましょう。

2点交叉（two-point crossover）

2点交叉は遺伝子の並びのうち、2か所場所を決めて、その2地点に挟まれた場所を2つの親の間で入れ替える方法です。

この方法は、あまり大きく遺伝子が変わらないので、良く採用されている交叉の方法です。

1点交叉・2点交叉ともに、交叉の場所を決めるのはランダムで決めます。

突然変異（mutation）

突然変異は、突然変異率に従って、遺伝子の0と1を反転させる作業です。突然変異率は大体30～50％などです。

あまり大きくしすぎると変異しすぎるので、大きくしすぎないほうが良いです。個体ごとに突然変異させるか上の確率で判定します。

もし変異させるとなったら、ランダムに遺伝子の場所を選び、その場所の0と1をひっくり返します。

交叉の時と同じように、エリート選択した個体は突然変異させないようにしましょう。

何に使える？

遺伝的アルゴリズムは、組み合わせの数が多く手計算では解くことが難しいような問題に応用されています。

たとえば、配送計画問題というどの車がどれだけ荷物を積んで、何か所配送をするのかという問題を解くのに使われたりします。

それぞれの車には何キロまで荷物を積めるという制約がついていたり、配送する地点が多かったりするととても手計算や数学の計算では解けなかったりします。

まとめ

以上となります!簡単にまとめると、遺伝的アルゴリズムは生物の遺伝子をまねて作られた仕組みで、初期個体の生成・評価・選択・交叉・突然変異を繰り返して世代交代をします。

その世代交代をある一定回数行い、最後に残った個体の中から一番良い結果を出すという流れになります。

最新の論文でもよく使われている手法で、知っておくと便利だと思います!ほかにもいろいろ種類があるので、また近々紹介しようと思います。

ぜひsnsフォローお願いします!記事更新の際すぐに見ることができます!