遺伝的アルゴリズムの紹介
2001年の勉強会で発表した遺伝的アルゴリズムの紹介資料です。HDDをあさってたら見つけたので一応記録。ほんのさわりです。最近の研究ではどこまで進展したんでしょうね？遺伝的アルゴリズムって複雑系と人工生命の文脈で捕らえるのが面白いのに、研究だとただの探索アルゴリズムになっちゃうのが悲しかった。
はじめに
遺伝的アルゴリズム（Genetic Algorithm:GA）とは、生物進化（自然選択、突然変異）から着想を得た汎用的な探索手法です。探索というのは、たくさんの解の候補がある中から、最も良い解を探すことです。つまり、GAとは解の候補から最もよいものを探すのが目的と考えられます。
歴史的背景
GAは、1975年、Hollandによって初めて導入されました。当時は、「なぜ進化のような何十億年もかかるプロセスの真似をするのか？」という反応が多かったらしいです。しかし、その後のGoldbergの研究や、一連の会議（International Conference on Genetic Algorithms:ICGA）により、GAに対する関心が高まってきました。
GAはどのような分野で用いられるのか？
現在、最適解はわからないが、解の評価は可能であるという問題（NP完全問題）が多数存在します。そのような、解法が確立されていない、最適解の求め方が非常に非効率で実用にならないという問題に大して、GAは非常に適した手法です。
初期には、GAを用いた巡回セールスマン問題、8クイーン問題など有名な問題が研究対象とされていました。GAの応用としては、ガスパイプライン制御、ジョブショップ・スケジューリング、鉄道会社の配送計画、戦闘機の保守計画、ジェットエンジンの設計などの様々な最適化問題が主流です。バイオインフォマティクスの分野では、遺伝子の情報解析、たんぱく質の構造決定などがあります。また、GAの創発性を利用して人工生命に応用されたり、ニューラルネット、ファジー理論との組合せも考えられています。
概要
GAは先ほど述べたように自然選択から着想を得たものです。自然選択とは、「生物の進化は環境に適応した生物が生き残ることによって起きた」という仮説で、ダーウィンによって提唱されました。下では、これを実際の生物にあてはめた場合と、GAの場合を比較しています。
実世界の場合
環境の中には、たくさんの個体（生物）がすんでいます。この個体たちは、環境に適しているものもいれば、適してないものもいます。環境に適応できなかった個体は自然淘汰されます。つまり、死んでいきます。環境に適応できた個体は生き残り、つがいとなって子を産みます（交叉）。この子は親の環境に適した遺伝子を受け継ぐため、より環境に適していると考えられます。子の中には、突然変異を起こすものもいます。突然変異が悪いものかもしれませんが、より環境に適するような変異を起こすものも現れます。このようにして、次の世代となる個体ができます。この個体たちにも同様なことがおきます。このようにして世代を重ねていくうちに、どんどん環境に適した生物が現れ、進化する（環境に適応する）ことになります。
GAの場合
環境の中には、たくさんの個体（解の候補）がすんでいます。この個体たちは、環境に適しているものもいれば、適してないものもいます。環境に適応できなかった個体は自然淘汰されます。つまり、死んでいきます。環境に適応できた個体は生き残り、つがいとなって子を産みます（交叉）。この子は親の環境に適した遺伝子を受け継ぐため、より環境に適していると考えられます。子の中には、突然変異を起こすものもいます。突然変異が悪いものかもしれませんが、より環境に適するような変異を起こすものも現れます。このようにして、次の世代となる個体ができます。この個体たちにも同様なことがおきます。このようにして世代を重ねていくうちに、どんどん環境に適した生物が現れ、進化する（環境に適応する）ことになります。
（補足）GAでの環境は人間が決めます。環境に適した解というのは、対象となっている問題において比較的良い解のことです。ここで、解が子を産んだり、突然変異を起こしたりできるのかという疑問があると思います。実際の解の形ではそんなことはできません。下のように解の形を変化させるのです。
左の図のように、実際の解の形（表現型）をGAを適用できる形（遺伝子型）へ変換します。こうして変換された解の形では、子を産む（交叉）ことや、突然変異を起こすこともできます。これを何世代にも渡って繰り返し、十分進化したところで、これを元の表現型に戻して最良の解を得ます。
基礎概念
北野[4]を元にして、GAの基礎概念についてまとめておきます。
用語
GAで用いられる用語は生物学に現れる用語が多いです。しかし、それをモデル化してコンピュータ上で表すため、意味が少し違うものもあります。注意してください。
- 個体（individual）
- 現実の解に対応するもの。各個体は染色体という遺伝子の塊をもっています。個体は完全に染色体によって特徴づけられます。つまり、良い染色体を持っていれば良い個体で、悪い染色体を持っていれば悪い個体です。
- 集団（population）
- 個体の集まりです。
- 遺伝子（gene）
- 遺伝情報を表す構成要素です。実際の生物はATCGという記号が使われますが、GAでは、ビット列や文字などで表されます。
- 染色体（chromosome）
- 遺伝子が並んだものです。通常、一次元配列として表されます。
- 適応度（fitness）
- 各個体が環境にどの程度適応しているかを示す指標です。適応度が悪い個体は次の世代で淘汰されます。染色体から実数値への一対一の関数として表されることが多いです。
遺伝的操作
実際の解の形（表現型）を遺伝子型に変換させると、下のようなGAの操作を適用することができます。
- 選択（selection）
- 適応度に基づいて次の交叉に参加させる個体を選ぶ操作です。すなわち、環境に適応しているものを選び取り、適応していないものは淘汰します。先ほどは、自然選択と言っていました。
- 交叉（crossover）
- 2つの親の染色体を組み替えて子の染色体を作る操作です。子は親の染色体の一部を受け継ぎます。先ほどは、子を産むと言っていました。
- 突然変異（mutation）
- 遺伝子を一定の確率で変化させます。
GAの手順
GAはアルゴリズムなので、手順を下のようなフローチャートで表すことができます。
まず、初期集団を生成します。初期集団は、一般的にランダムな染色体を持つ個体で構成されます。ランダムなので、その集団の中には良い解も悪い解もごちゃまぜに入っています。次に、各個体がどの程度環境に適しているのか（すなわち、各解がどれだけ良いか）を評価します。この評価は適応度関数というものを使います。適応度関数は、染色体を入力すると、適応度が出力されます。このようにして、全ての個体の適応度を計算するわけです。次に、適応度が高い個体を2つ選択して親とします。次に、交叉して子を作ります。次に、確率的に突然変異を起こし、子の染色体を変化させます。こうして、出来た子を次の世代として、再び評価します。この手順を繰り返し行ない、何世代か経った後、終了させます。
GAの簡単な例
表のように初期集団として4つの個体がいる状態を考えます。各個体はビット列で表された染色体を持っていて、各個体の適応度は染色体を10進数で表したものとします。ここでの目標は、適応度が最大となる解（個体）を見つけることです。すぐに、11111と分かりますが、GAで求めてみます。
第1世代（初期集団）
| - | 染色体 | 適応度 |
|---|---|---|
| 個体1 | 01100 | 12 |
| 個体2 | 10110 | 22 |
| 個体3 | 00011 | 3 |
| 個体4 | 10001 | 17 |
| 平均 | - | 13.5 |
適応度を見ると、個体2は最も環境に適応できる良い解なので、選択される確率は大きいです。逆に個体3は適応度が低く悪い解なので、選択される確率は小さいです。まず、選択ですが、ここでは、個体1と個体2をペア、個体2と個体4をペアとして選択します（このとき同じ個体が何度選ばれても構いません。確率的に選びます）。案の定、個体3は選択されません、つまり淘汰されます。次に交叉です。図のように個体1と個体2、個体2と個体4の染色体を交叉させて、子の染色体を構成します。ここでの交叉は染色体のある点で区切って入れ替えるだけの方法で、単純交叉と言われます。
次に突然変異です。ここでは、子4の染色体の一部を変えてみます。
このようにして出来た4つの子が第2世代となります。
第2世代
| - | 染色体 | 適応度 |
|---|---|---|
| 個体1 | 01110 | 14 |
| 個体2 | 10100 | 20 |
| 個体3 | 10101 | 21 |
| 個体4 | 11010 | 26 |
| 平均 | - | 20.3 |
この平均適応度を見ると、第1世代の13.5から20.3に増えていることが分かります。つまり、第2世代は第1世代より進化して適応度が高くなったわけです。再び、同じことをこの第2世代について行ないます。まず、選択ですが、ここでは、なるべく適応度が高い、個体3と個体4をペア、個体2と個体4をペアとして選択します。次に交叉です。図のように個体3と個体4、個体2と個体4の染色体を交叉させて、子の染色体を構成します。
今回は突然変異は起こさないことにします。このようにして出来た4つの子が第3世代となります。
第3世代
| - | 染色体 | 適応度 |
|---|---|---|
| 個体1 | 10010 | 18 |
| 個体2 | 11101 | 29 |
| 個体3 | 10010 | 18 |
| 個体4 | 11100 | 28 |
| 平均 | - | 23.3 |
この平均適応度を見ると、第2世代の20.3から23.3に増えていることが分かります。つまり、第3世代は第2世代より進化して適応度が高くなったわけです。このように、選択、交叉、突然変異という操作を繰り返し行なっていくと、適応度はどんどん高くなり、最高の適応度を持つ個体はそのうち出現すると考えられます。その個体を取り出すことによって、「最高の適応度を持つ解を見つける」という目標を達成することが出来ます。
まとめ
今回の例で適応度が徐々に増えていったのは偶然ではなく、各世代において適応度の高い個体を選択してきたことによります。その適応度の高い個体を交叉させることによって、集団中に適応度の高い個体が増えていったのです。
この例ではビット列に特別な意味（表現型）を持たせずに、GAの操作の部分だけ述べました。つまり、概要のところの図の右側の部分だけです。この記号に特別な意味を持たせることにより、様々な問題に応用できます。次の例では、記号に特別な意味を持たせる例について述べようと思います。
巡回セールスマン問題への応用
巡回セールスマン問題とは
巡回セールスマン問題（Traveling Salesman Problem:TSP）とは、N個の都市を1回ずつ通って巡回する最小経路を見つける問題です。都市数が増えると探索経路が爆発的に大きくなってしまう NP完全問題の代表例です。左の例を見ると、都市は、a,b,c,d,eと5つあります。都市と都市は道でつながれていて、コスト（距離）が設定されています。ここで、全ての都市を巡回し、かつその経路のコストが最小になるような経路を見つけるのです。左の例では、 a->e->d->b->cが最短経路です。ここでは、TSPにどのようにGAを適用するかを概観します。山村、小野、小林[6] を参考にしました。
解の染色体の表現
まず、解の候補がどうなるか考えてみます。明らかに解の候補は、都市の並び（順列）です。つまり、
a->b->c->d->e、a->b->c->e->d、b->c->a->e->d、 ...
など、全ての通り道のパターンを用意し、その中から、最小経路を持つパターンを探すのです。そこで、都市名を遺伝子とし、固定された出発点の都市から巡回順に都市名をリストアップした文字列を染色体とします。これはパス表現と呼ばれます。この都市の経路順という問題の解を、染色体として表現するというのは、概要のところの図の左側の表現型から右側の遺伝子型に変換したところです。例えば、上であげた経路の表現型は、
（a,b,c,d,e） （a,b,c,e,d） （b,c,a,e,d）
のような遺伝子型になります。適応度は染色体の順で経路をまわったときの距離の和です。この例では、距離は小さければ小さいほどよいので、適応度が低いほど良いことになります。適応度が大きいほど良いとしたいなら、逆数を使えばよいです。
交叉法
次に、染色体の交叉法について考えてみます。まず、先ほど使った単純交叉を使ってみます。下図のように交叉させ、子の染色体を作ります。
この子の染色体を見ると、TSPの解の条件を満たしていないことがわかります。すなわち、全ての都市を1度ずつ訪問するという条件を満たしていないのです（例えば、子Aはb,cを2回訪問していて、d,eを訪問していない）。このような個体は致死遺伝子を持つといい、淘汰されます。この単純交叉では、ほとんど致死遺伝子を持つ子が出来てしまいます。そこで、次に致死遺伝子を持たない子を作る交叉の仕方を考えて見ます。
順序表現による交叉法
ここでは、順序表現というものを使います。染色体のパス表現をこの順序表現にすると交叉しても致死遺伝子を持つ子が発生しなくなります。順序表現とは、次に巡回する都市が残りの都市の中で何番目にあるかの番号を遺伝子とし、固定された出発点の都市から順にこれを並べた文字列を染色体とする方法です。
例として、親Bがパス表現から順序表現へどのように変換するかを見てみます。最初の都市aはアルファベット順の都市リスト（a,b,c,d,e）の 1番目なので順序表現の最初の要素は1です。2番目の都市dはaを除く都市リスト（b,c,d,e）の3番目なので、2番目の要素は3です。3番目の都市 eはa,dを除く都市リスト（b,c,d）の3番目なので、3番目の要素は3です。以下同様です。このように順序表現にした染色体で交叉させて、子の染色体を作ります。子の染色体は上の逆変換をすることでパス表現になります。
TPSでのGAの流れ
これでようやく準備が整ったので、GAでどのように最適解を見つけるのか説明します。流れ図は下ようになります。
まず、ランダムなパス表現を持つ個体を多数用意します。この中には、良いパスも悪いパスもごちゃまぜに入っています。次に、このパス表現を評価して、適応度を求めます。先ほど述べたように適応度は染色体のパスの順で経路を通ったときの総距離数です。次に、この個体の中から、適応度の比較的良い個体を確率的に選択し、順序表現に直して交叉させます。これを何世代にも渡って繰り返し行い、解を進化させます。こうして、もう十分経ったと思ったら、その集団の中で最も適応度の良いものを取り出し、それをパス表現に戻します。そのパス表現は都市の訪問順を表しているので、それをTSPの解とします。
おわりに
GAは適用範囲の広い汎用探索アルゴリズムです。他にも、スケジューリング問題、経路最適化、ロボット制御、プログラム自動生成、VLSIのレイアウト設計、遺伝子情報解析、蛋白質の構造決定などにも適用されています。GAの問題点としては、
- 数学的解析が進んでいない。
- 染色体への符号化をどのように行うかの方針が明確ではない。
などがあります。特に、数学的解析があまり成されていないことは、情報科学として扱うには致命的かもしれません。たまたまある問題に適応してみたらうまくいった、ということが多く、なぜそのようにしたらうまくいくのかはわかっていないことが多いそうです。今後、GAが生き残っていくためには、数学的解析を進めることが重要だと思います。
参考文献
- J. H. Holland, "Adaptation in Natural and Artificial Systems", Univ. of Michigan Press, 1975.
- D. E. Goldberg, "Genetic Algorithms in Search, Optimization, and Machine Learning", Addison-Wesley, 1989.
- 北野宏明, "遺伝的アルゴリズム", 産業図書, 1993.
- 北野宏明, "遺伝的アルゴリズム", 人工知能学会誌, Vol.7, No.1, 1992.
- 波多野寿昭, "遺伝的アルゴリズム", 人工知能学会誌, Vol.8, No.3, 1993.
- 山村雅幸, 小野貴久, 小林重信, "形質の遺伝を重視した遺伝的アルゴリズムに基づく巡回セールスマン問題の解法", 人工知能学会誌, Vol.7, No.6, 1992.
