この記事は公開されてから1年以上経過しています。情報が古い可能性がありますので、ご注意ください。
こんにちは、ジョン・ヒョンジェです。
皆さんは「適者生存」という用語を聞いたことがありますか？
ある環境において、最も適応できる生物だけが生き残り、適応できない生物は淘汰される
これが適者生存の基本概念です。遺伝的アルゴリズムはこの適者生存という生物進化論をもとにして、生物が環境に適応し進化していく様子を模倣した最適化手法の一つです。今回はこの遺伝的アルゴリズムについてお話ししたいと思います。
遺伝的アルゴリズムとは
遺伝的アルゴリズムは生物進化論の以下のルールを模倣します。
- 環境に一番適応できる、つまり一番優秀な個体が生き残る
- 生き残った個体は繁殖する
- 生き残った個体は親として子孫を生成する。子孫は親の遺伝子を継承して次の世代を生きていく。ここで時々突然変異遺伝子を継承した子孫ができる。
遺伝的アルゴリズムでは進化論での個体を「染色体」と呼びます。染色体は最適化問題で可能な解の候補になります。そして、その染色体は数字やアルファベットで表された「遺伝子」の組み合わせで表現します。
この例では0と1が遺伝子で、この遺伝子の組み合わせが染色体です。遺伝的アルゴリズムの目的は「遺伝子の組み合わせを変化していきながら、最適な組み合わせを見つける」ことです。
遺伝的アルゴリズムは数学的に定義されていない問題や複雑すぎて計算できない問題での最適解を求める時よく使います。決められた方式がありませんので、その原理と流れをはっきり理解して、解決したい問題にどうやって遺伝的アルゴリズムを適用するかを設計するのが最も重要なところです。
遺伝的アルゴリズムの流れ
遺伝的アルゴリズムの流れです。
- 第0世代の染色体をN個生成
- 染色体の遺伝子情報はランダムに設定
- 染色体を評価
- 適応度関数を作成して評価を行う
- 適応度は染色体の優劣を判断する基準
- 一番よく使われる方式は各染色体の適応度を評価して点数を付与する方式
- 染色体を二つ選択し、交叉
- 2段階で評価した染色体の中で二つを選択
- 選択した二つの染色体の遺伝子情報を交叉させて新しい染色体をN個生成
- 選択基準は決められていない（以下で代表的な選択方式をいくつか紹介します）
- 突然変異生成
- 3段階で生成した新しい染色体の中でいくつかの染色体の遺伝子情報を任意に変更
- 親にはなかったいい遺伝子情報を見つけるために必要
- 世代交代
- 既存の世代の染色体を3、4段階で生成した染色体に交代
- 2~5段階を繰り返す
- 新しい世代で2~5段階を繰り返す
- 最大世代数のG回まで繰り返す
- 第G世代で一番適応度が高い染色体が最適解に一番近い解になる
このように染色体は親のいい遺伝子情報を継承して世代を経るたびに段々進化していきます。
遺伝的アルゴリズムの演算方式
遺伝的アルゴリズムでは決められた方式はありませんが、よく使われる代表的な演算方式はあります。それで、いくつか紹介したいと思います。
選択
Roulette wheel selection
Roulette wheel selectionは一番よく使われる選択方式です。仮想のルーレットがあると仮定して染色体に適応度に比例してルーレットの持ち分を配分します。配分が終わったら、ルーレットを回して染色体を選択します。ルーレットを回すのは乱数を生成することで実装します。この方式を使うと、適用度が高ければ高いほど選ばれやすいです。
Ranking selection
| 染色体 | 適応度 | ランキング | 持ち分(%) |
|---|---|---|---|
| A | 90 | 1 | 40 |
| B | 10 | 4 | 10 |
| C | 12 | 3 | 20 |
| D | 15 | 2 | 30 |
Ranking selectionはRoulette wheel selectionと似ていますが、少し違います。Ranking selectionはランクごとにあらかじめルーレットの持ち分を決めておく方式です。適応度によって染色体のランクをつけて、ランクごとに決められた持ち分を付与します。上の票は「1位：40%、2位：30%、3位：20％、4位：10％」に持ち分を決めておいた例です。それで、染色体Aは圧倒的に適応度が高いですが、染色体Dの持ち分と10%しか差がないことがわかります。
Elitist preserving selection
Elitist preserving selectionはその名の通り、一番適応度が高い染色体は次の世代にもそのまま残す方式です。
交叉
1点交叉
特定の交叉ポイントを1点設定して、その前後の遺伝子を入れ替える方式です。
2点交叉
交叉ポイントを2点設定して、二つのポイントに挟まれている部分を入れ替える方式です。
一様交叉
各遺伝子ごとに1/2の確率で入れ替える方式です。
突然変異
突然変異は遺伝子をある確率で任意に変更することです。変異の演算では一般的に「静的変異」、「動的変異」があります。
- 静的変異 : 突然変異の確率を一定に固定する
- 動的変異 : 初期の世代では染色体の品質があまり良くないので変異の確率を高く設定する。後半の世代の染色体は比較的に品質がいいので変異の確率を低く設定する(後半での突然変異はあまり品質向上に役に立たない傾向がある)
変異の確率が高ければ多様な解の生成によって遺伝的アルゴリズムの力動性が高くなりますが、逆に解が収束しにくくなる恐れがあります。そのため、変異の確率を適当に設定する必要があります。
遺伝的アルゴリズムの注意点
遺伝的アルゴリズムを使うとき、注意しなければならない点があります。
まず、問題に対する可能な解が遺伝子の形式で表現できるかを考えなければなりません。遺伝子は一般的に数字やアルファベットで表現しますが、これができない場合や遺伝子の情報が複雑すぎる場合は最適解を求めることができない恐れがあります。
そして、適応度関数により、適応度を計算することができるかを確認する必要があります。適応度関数で染色体をちゃんと評価することができなければ、永遠に染色体が進化できなくなります。
遺伝的アルゴリズムを使うときはこの2点を考えて設計した後、実装する必要があります。
最後に
今まで遺伝的アルゴリズムについて説明をしました。今回紹介した遺伝的アルゴリズムの演算方式意外にも多様な演算方式がありますので、そちらも調べてみてください。
遺伝的アルゴリズムって最初はちょっと理解しにくいかもしれませんが、いったんその流れと原理を理解すれば、とても面白いアルゴリズムだと思います。YouTubeで遺伝的アルゴリズムを検索してみると、興味深いプロジェクトがたくさん出てきますので、ぜひ検索してみてください。
では、以上です。ありがとうございます。
（以下のリンクは私が遺伝的アルゴリズムを理解するのにとても役に立った「ムニムニ」様の動画です）