※現在、ブログ記事を移行中のため一部表示が崩れる場合がございます。
順次修正対応にあたっておりますので何卒ご了承いただけますよう、お願い致します。

遺伝的アルゴリズム


2013年 04月 07日

「遺伝的アルゴリズム」というのをご存知だろうか。
生命の遺伝のメカニズムそっくりの方法で問題を解決しようという方法である。
アルゴリズムと言いながら、実はアルゴリズムがないというのが特徴のアルゴリズムである。
生命は、延々と遺伝が行われ進化して、人とか非常に高度で複雑なことができる生命が生まれてきた。
染色体が交差や突然変異によって次の世代ができ、環境適応性の良い個体が生き延びることで進化したと考えられる。
これを、そのまま様々な問題に応用しようというのである。

解説書はあまり多くはないが、実はとんでもなく単純である。
なのに、なぜか難しいと思い込まれているところが残念である。
ネットにも情報がいろいろあるし、遺伝的アルゴリズムを研究している大学の研究室も簡単に見つかるだろう。
遺伝的アルゴリズムは一種のフレームワークというか、もっと大雑把に捉えるべきだろう。
コンピュータで実現する場合、対象を何とか染色体にモデル化する。
そして、染色体の交差と突然変異に対する操作を決める。ここで乱数を使う。
世代毎に、多数の染色体から次世代に生き延びさせる染色体の選択方式を決める。
選択のために、各染色体を評価しなければならないので、環境適応度関数をでっちあげる。
あと、最初に、かなりデタラメでよいから、適当な個数の染色体をでっちあげる。
これだけ作って、スタートさせると、うまくいくと、そのうち、何十世代か何百世代後に、欲しかった染色体ができたりする。

成功するかどうかは、神のみぞ知るようなアルゴリズムなので、これをアルゴリズムと言って良いものか、少なからず疑問である。
でも、どうすれば解決できるか分からない、あるいは非常に面倒な問題を、単純な方法で解決できたりする。
今、この方法を使って、簡単に組合せ爆発が起きる分野に対して、実際に生産に使う実験をやっていて、かなり良い結果が出つつあるので、紹介していこうと思う。