遺伝的アルゴリズムとは

最近になってまた注目されてる気がする要素技術それが遺伝的アルゴリズムである
BeepCapです。

んまぁ簡単に言えば「真面目にやるのが面倒な問題を適当に最適っぽくする手法」
この場合の適当とはランダムよりはましという程度のお話。

その適当さを求めるために「遺伝」という概念を使う。

ここである例を思い出してもらう。

「無限の数の猿が、無限の時間タイプライターにランダムな文字を打ち込むと、シェイクスピアが書き上げられる」(所詮確率論なので断定するのもどうかと思うが)

数学的には解が収束する問題。
一般的には「答えがある問題」とでも言えば良いか。


遺伝的にアルゴリズムを組みこむとこうなる
「ただし、猿は寿命を持ち、タイプライターでシェイクスピアを書き上げる可能性の高い奴が生き残り、子孫を増やす」

適者生存、タイプライターの前に座れもしない奴は殺される運命にある。
こうすると、今まで無限に近い時間を仮定していたのが、だいぶ枝切りされる可能性を見出せる。





というのが理想


実際の遺伝的アルゴリズムはこのあたりが中々有効にならない。
チューリングの理論を持ち出すまでもなく、何がシェイクスピアに近いのか
コンピュータは完全に判断する事はできない。
という点に尽きるのである。すなわち結局のところこれは解にたどり着く道を枝切りしているのかもしれない。



遺伝的アルゴリズムはおもしろい。

だが、それが真に有効に使えるのはいつの話になるのだろうか
（ただし、曖昧な結果が欲しい場合はこの限りではない。ある程度の曖昧さが必要なゲームの擬似脳などは、思考ルーチンに完璧さを求める必要がないためである。)