TIM Labs

2013年4月アーカイブ

遺伝的アルゴリズムは、生命の遺伝そっくりの方法で問題解決を図る。
個体(染色体)を進化をさせて目的の個体を得る。
このちき、正常系の遺伝と、異常系の遺伝を用意する。
正常系の遺伝では、2つの個体から、両方の性質を普通に混ぜ合わせた個体をつsくる。
でも、正常系の遺伝だけでは、凡人と秀才しかいないつまらない世界になり、進化は止まってしまう。
進化が停滞してしまうのを打破するために、突然変異という仕掛けが必要である。
親の染色体の一部をランダムに変更する。すると、ほとんどの場合は酷い状態になってしまい、捨てられる。
しかし、まれに非常に優秀な個体ができる。
そして、この優秀な個体は、正常な遺伝によって子孫に広がっていく。
正常系と異常系のバランスが非常に重要である。
正常系だけで解けるような問題に遺伝的アルゴリズムをわざわざ使うのは無駄だろう。
どうやったら解けるかどうか分からない、手がつけられないような問題に適用すると良い結果が得られることがある。
突然変異の作り方は、扱っている問題によってどう実装するのが良いかは異なる。本とかには基本的なやり方は書かれているが、問題の特徴を考えて、突然変異の起こし方をそれぞれの場合に応じて調整しないと、うまく進化は進まない。
この調整は、なかなか難しいが、一番面白いところでもある。
生命の遺伝においても、高等生物が誕生したのは、突然変異が奇跡的にうまくいったからであろう。
突然変異は重要で、進歩のきっかけをもたらすのは奇人・変人であることが、遺伝的アルゴリズムをやることで実感できる。平均的人間ばかりでは社会は停滞する訳だ。
遺伝的アルゴリズムでは、対象を染色体という形でモデル化する。
染色体というと、生物の染色体のイメージがあるので、数個の値しか取らない数値が延々と並んだ配列とかリストを考えるのではないかと思う。
多くの場合そうなのだが、遺伝的アルゴリズムでの染色体はヒモ状のものである必要はないし、個々の遺伝子も、0/1あるいは、AGCTの様に数個の値に限定する必要もない。
単純な数値である必要もなく、座標値、形状データなど、実は何でも良い。
重要なのは、コンピュータで扱えること、2つの染色体から子供を普通に作る方法と、突然変異した子供を作る方法が用意できればOKである。
言葉による説明だけでは分かり難いだろうから、実例を紹介しよう。

一般的には、ナップサック問題とか巡回セールスマン問題で遺伝的アルゴリズムを体験するようだ。
でも、それだけでは、あまり面白味がないだろう。
と思っていたら、車のデザインに利用した例があった。

BoxCar 2D


適当にデザインして走らして、交叉や突然変異で次世代車を作り、また走らせて、そして選択してというのを続けていると、次第に理想的な形の車になって行きます。
この例では、実際に走行シミュレーションさせて評価するので、良い車になるまでにかなりの時間がかかります。プログラムを走らせたまま一晩放置しておけば、かなり良い状態になっていることでしょう。

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

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

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

書影

WEB+DB PRESS plus シリーズ の最新刊「開発ツール徹底攻略」に Vim の記事を寄稿しました。

「オペレーターやテキストオブジェクト等の有用な標準機能の活用術」「キーバインドを始めとした各種設定方法や便利な設定例」「プラグインの導入や活用方法」「プラグイン作成のいろは」といった内容を駆け足で解説しています。内容としては2009年8月に発売された WEB+DB PRESS Vol.52 の特集記事とほぼ同じですが、2013年に合わせてほんのり差し替えているところもあります。是非買ってください。

このアーカイブについて

このページには、2013年4月に書かれたブログ記事が新しい順に公開されています。

前のアーカイブは2013年3月です。

次のアーカイブは2013年5月です。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。