遺伝アルゴリズムによる複雑問題への対処法～コンピューターシミュレーション入門～

世の中の問題はますます複雑になり、多くの属性のデータを処理する必要性に迫られています。
すべてを紹介することはできませんが、これらへの対処方法として遺伝アルゴリズムを例に簡単に説明します。
本稿でフォーカスするのは、「複雑システムに対する対処法」です。

複雑システムには、主に以下のようなものがあります。
非線形、不連続、初期値への強依存（カオティック）、動的、非平衡、経路依存的、分散要素と集団の相互依存などです。

これらへの対処法には、主に以下のようなものがあります。
最適制御、安定化、予測、分類、同定などです。
ここでは、ひとつの対処法として、遺伝子アルゴリズム（GA）を取り上げます。

１．遺伝アルゴリズム（GA)とはどのようなものか

遺伝的アルゴリズム（Genetic Algorithms:GA）は、1975年にミシガン大学のJohn Hollandが生物界の進化の仕組みを模倣する（選択－交差－突然変異など）解探索手法として提案したものです。このアルゴリズムでは、解空間をコードレベルで探索することができます。
また、非線形・不連続問題にも適用することができ、問題特有の情報を必要としないことも特徴の一つです。解空間の勾配をするなど、メタ探索の手法であるため、局所解に陥りにくいといわれています。
GAでは、解の探索を実際の遺伝のプロセスを模倣して行うため、原則「偶然の変化」と「たまたま良くできたものを採用」して行ないます。そのため、本提案がなされた当初は、「こんな偶然に頼るデタラメな方法をアルゴリズム（計算手順）と呼べるのか」との厳しい批判にさらされたといわれています。
しかし、1990年代に入るとGAは人工知能の主要分野に躍り出て、世界中で研究が行なわれるようになりました。その背景には、コンピュータの計算速度の飛躍的な向上があります。生物の進化と同様に、GAの進化にも非常に多くの繰返しと試行錯誤が必要だったのです。

２．GAの基本アルゴリズム①　コード化（Coding, Representation）

まず、最適化対象をコード化します。最適化対象のコードは、いわゆるバイナリコードで記述する必要があります。バイナリコード（binary code）とは、コンピュータが読み取れるコンピュータ語に変換したものをいいます。下図がその一例です。

３．GAの基本アルゴリズム②　評価（Evaluation）

次に、複数の探索点を作成します。
これを「メタ戦略」といいます。メタ探索には、以下の特徴があります。

・局所解に陥り難い
・多くの情報を蓄積する（優れた遺伝子コードのパターンとして）

通常、初期値は、乱数により発生させます。初期集団が豊富な遺伝子パターンを持つようにする特殊な方法もあります。探索解を問題依存のモデルにより評価して、適応度を採点していきます。

４．GAの基本アルゴリズム③　淘汰（Selection）

次に、採点された適応度をもとに、親となる探索解を選びます。親となる探索解の選び方にも様々な種類があります。代表的なものを以下に示します。

・ルーレット方式　：適応度に比例して選択確率が高くなる選び方
・トーナメント方式：２つの解を選び、適応度の高い方を選択する選び方
・エリート戦略　　：適応度の高い探索解が自動的に生き残る選び方

また、これらの選択には以下の特徴があります。
乱数を利用することによって、適応度の低い個体にも生き残る可能性が残っています。そのため、遺伝子バラエティの維持（局所解）に陥り難く、曖昧さゆえの環境変化に強い特徴があります。

５．GAの基本アルゴリズム④　交叉（Crossover）

交叉では、２体の親の遺伝子コードを組合わせることで、次の探索解を作成していきます。交叉には、以下のような方法があります。

・１点交叉　　：　１点で２つの遺伝子コードをつなぎ変える
・２点交叉　　：　２点で２つの遺伝子コードをつなぎ変える
・一様交叉　　：　遺伝子座ごとに、一方の遺伝子を引き継ぐ

これらには以下の特徴があります。遺伝子レベルでの探査点を作成するため、解空間の情報が不要です。そのため、汎用性が高いといえます。また、「遺伝子」ではなく、「遺伝子パターン」が受け継がれることも特徴です。

６．GAの基本アルゴリズム⑤　突然変異（Mutation）

突然変異では、低い確率で、遺伝子をランダムに変化させます。これによって、以下の特徴が生まれます。
選択と交叉の繰返しによって、遺伝子パターンの均質化が生じますが、これに対して突然変異によって生まれる「新鮮な」遺伝子を供給することで、新たな領域の探索を継続したり、環境変化への耐性が強くなります。
（突然変異の確率を大きくした場合には、ランダムサーチに近くなります。）

７．GAの基本アルゴリズム⑥　探索の全体像

遺伝アルゴリズム（GA）では、「評価→選択→交叉→突然変異」と、世代交代を繰り返すことで集団の遺伝子が「進化」していきます。
すなわち、同一世代の複数の探索点だけに留まるのではなく、過去の探索における「経験」を「優れた遺伝子コードのパターン」という形で蓄積・利用していきます。優れたメタ解法における情報共有と活用方法だといえます。

８．ＧＡのメリットとデメリット

GAのメリットとデメリットを以下にまとめました。

◆メリット◆
・汎用的
とりあえず、どのような問題にも適用ができる
・単純
理屈が単純なため、誰でも使いやすい
・発見的
思っても見なかった「解」を見つけ出す可能性がある

◆デメリット◆
・探索速度が遅い
評価プロセスに時間がかかるような問題には向かない
・完全な「最適解」ではない
解釈できないパラメータも多く、収束判定も困難

GAを例にあげ、非線形・不連続問題への対処方法について説明してきましたが、要するに、「単純化」するのではなく、「複雑なものを複雑なまま扱う」ということです。
従来のモデル化では、「複雑な問題→単純化→本質の発見→現実解のアイデア抽出」という流れが一般的でした。しかし、問題が複雑であればあるほど、本質の発見や現実解のアイデア抽出というプロセスは困難となります。
しかし、GAのようなアルゴリズムでは、「複雑な問題→現実解の探索→分析→一般化」という流れで、複雑な問題を複雑なまま扱うことができます。そのため、「単純化思考」では不可能であった新たな“発見”も起こりえます。

しかしながら、このような最適解の探索やシミュレーションで陥りがちな幻想ですが、コンピュータを回せば黙っていても解が得られるというようなことはありません。
現実には、試行錯誤を繰り返しながら解にたどり着くことの方が多く、目をつぶっていても解が得られるなどということは断じてありません。

本稿では、GAを例に挙げましたが、現実の問題に対処するためには、このような道具立てを複数用意しておくことが望ましいといえます。
いくら切れ味の鋭い刺身包丁を持っていたとしても、それで薪を切ることはできません。
対処する問題によって包丁（道具）を変えることも大切なことなのです。

【関連記事】