１．遺伝的アルゴリズムとは

---

遺伝的アルゴリズムとは、ある問題に対する最適な解を求めるための手法といえるでしょう。この手法はもともと、生物の世界にある遺伝の法則をまねて作られたもので、複数の解を、遺伝的に変化させながら、より良い解を求めていくものです。

ＧＡでは解を遺伝子という形で表現します。これは解の持つ特徴を一定のルールに従って記述したもので、このルールを決めて遺伝子を決定することをコーディングといいます。つまり、問題をどう表現をするかということになります。

図１．１　コーディング

例えば、y=ax+bという式で問題が表されるとき、係数a,bを調節することでxに対してyの値が最適になるようにしたいとき、表現型というのはa,bの値がそうです。遺伝子型というのは、コーディングの仕方によって異なりますが、a,bの値を4bitずつで二進化してつなげた8bitのビット列とするとこれが遺伝子型となります。（遺伝子型を２進数にしないで実数値で表すＧＡもあります。）

つまり、a=5,b=12というのは表現型、01011100というのは遺伝子型となります。

（0101は5の２進数表現、1100は12の２進数表現）

コーディングに誤りがあったり、あまり問題に適していなかったりすると良好な結果は得られません。また、コーディングの仕方によってはいわゆるＧＡの操作（交叉や突然変異）を行ったときにその効果が均等に現れない可能性もあります。

図１．２　ＧＡの流れ

上の図は基本的なＧＡの例です。ただし、これは１例であり必ずしもこの通りである必要はありません。左図はフローチャートの形式になっていますので、上から順に説明したいと思います。

まず、初期集団を用意します。初期集団というのは解の集団であり、ＧＡではこれを個体群と呼びます。初期集団となる個体群はこういうデータといった決まりは無く、ランダムに作り出したものであったり、何らかのデータが用意されていればそこから用意したりしてもかまいません。

ただ、一つ言えることは初期集団には多様性があったほうがいいということです。つまり、遺伝的操作によって最適解を求めるわけですから、なるべくいろいろはパターンを用意すれば、それだけ調べられる可能性も広いというわけです。

図１．３　初期集団

求めたい答えが解空間のどこにあるのかが解らないのなら、(b)の状態から始めるよりは(a)の状態から始めたほうが、初めからよりいろんな場合を調べられていいですよね。

次に評価を行います。現在の個体群の中に条件を満たす解が含まれているなど、一定の条件を満たしたとき、ＧＡは終了します。終了条件を、解とＧＡの世代（計算回数）の条件を用意すると、解の判定用の条件が厳しすぎたときにＧＡが終わらなくなるのを防ぐことができます。

選択では、個体群の全ての個体（解）について適合度を求めて、この適合度に基づき次の世代に残す個体を決定します。適合度というのは、解の評価の高さのようなものです。問題によって求め方は変わりますが、良い解ほど高い適合度が得られるように評価関数を設定します。また、選択の方法についてもさまざまな手法があります。問題によって適したものを選ぶとよいでしょう。一般に解を表現型に直すと評価しやすいと思います。

交叉と突然変異はＧＡオペレータと呼ばれ、ＧＡを特徴づけるものです。ともに、遺伝の法則をヒントに作られたもので交叉では複数の親（一般には二つ）から遺伝子を受け継ぐ新しい個体（子）を作ります。突然変異では、低い確率で起き、遺伝子の一部が変化します。

図１．４　交叉と突然変異

ここで、交叉の目的は両方の親から、別々の良い形質を受け継ぐより良い遺伝子を作り出すことであり、突然変異の目的は遺伝子が局所的な最適解に落ち着いてしまうことを防ぎ、より広い範囲で最適な解を探すことにあります。

交叉と突然変異を繰り返すだけでは、遺伝子をいろいろ変化させるだけですが、選択により適合度の低い個体は順次淘汰される仕組みになっているため、結果的には良い方向に変化をした個体が生き残っていきます。まさしく、自然界における生き物の進化と同じことが起きているわけです。

単純ＧＡ（ＳＧＡ：Simple GA）

ＳＧＡはもっとも基本的な構成のＧＡとして提案されました。ＧＡには様々なタイプが提案されていますが、これらはＳＧＡを拡張したものと言えるでしょう。ＳＧＡはアルゴリズム自体のパラメータとして、終了までの世代数Ｔ集団の個体数Ｍ、交叉の起こる確率Pc、突然変異の起こる確率Pm、の４つを持っています。これらのパラメータはよく（Ｔ,Ｍ,Pc,Pm）という形で表されます。それでは以下に具体的な構成を紹介します。

コーディング

ＳＧＡでは0,1の２値で遺伝子型を表します。

例えば３つのパラメータ(13,5,10)を持つ個体を遺伝子型で表すなら、

110101011010

となります。

( 1101=13 , 0101=5 , 1010=10 ) というわけです。

初期集団

ＳＧＡの初期集団は、乱数によりＭ個生成します。

評価

評価はのちに選択を行うときに利用するため、正の値で計算します。

選択

各個体について求めた評価（適応度）をg(i)とし、全個体の評価の総和をGとして、各個体の選択される確率g(i)/Gを求めます。そして、前の個体群からこの確率を用いて個体をＭ個選び、新しい個体群とします。（ルーレット選択）

交叉

すべての個体をペアにして、それぞれのペアについてPc（交叉確率）に基づいて、交叉を行うか決定します。交叉が起こるペアでは交差点をランダムに選び、その後ろを入れ換えます。（一点交叉）
図１．４参照

突然変異

各遺伝子座について、Pm（突然変異確率）に基づいて突然変異を行います。（ビットの反転）
図１．４参照

以上、評価から突然変異までを一世代と考えＴ回繰り返します。

各パラメータ（Ｔ,Ｍ,Pc,Pm）については、問題によって最適な値は異なります。

Ｔは回の収束の遅い問題では大きく設定しなければなりませんが、早くに収束する問題ではＴが大きいと無駄な計算を繰り返すことになってしまいます。

Ｍは解の多様性に関るので、大きめの値にするとより多くのパターンの解について調べることができますが、Ｍが大きいと個体数も多いわけですからそれだけ一世代における計算量も増えてしまいます。

Pcは収束の速さに関ってきます。交叉を行うことでＧＡは探索を行っているわけですが、交叉が起こりやすいと優秀な個体が消えてしまう可能性もあり、場合によっては収束結果があまり良くないかも知れません。（0.5〜1.0が一般的）

Pmは個体群の多様性を保つ働きを調節できます。この値が大きいと、より多様な個体が現れます。しかし、大きすぎると優秀な個体を破壊することになりかねませんし、また収束にかかる世代も長くなってきます。（0.1以下が一般的）