遺伝的アルゴリズム（GA）の並列化

は並列分散遺伝的アルゴリズムと呼ばれている。GAも複雑な問題では計算に膨大な時間がかかることが問題点となっている。

日経サイエンス2003年5月号に「発明家に追いついた遺伝的プログラミング（GP:Genetic Programming）」という記事が載っていた。この記事では、電子回路の設計をGA（正確に言えばGP）を用いて行い、人間の発明に匹敵する回路が進化によって生み出される例を挙げている。こういうのは「進化するハードウェア」と呼ばれている。

GAの詳細は省くが通常数万から数十万の個体で構成する集団から始めて数十から数百世代の間に進化させるらしい。ある程度の回路は普通のノートパソコンで1週間ほどで作り出せるが、もっと強力なコンピュータを使わないと手に負えない回路もあるようで、この場合にGAを並列計算するという手法が威力を発揮する。

この記事の著者らは動作周波数が350MHzのPentiumプロセッサを搭載したパソコン1000台つないで、ベオウルフ型クラスタを構築し、7日かけて回路を進化させ有用な回路を作り出したと書いている。GAで最も時間がかかるのは次世代に受け継がれる候補となる固体の適応度評価の部分で1個体を評価するのに約1分かかるためこんなに時間がかかったと説明されていた。1000台で7日もかかるなんてあまり実感がわかないが、相当な計算量が必要らしい。

並列分散遺伝的アルゴリズムの詳細は北野宏明さんの下の本で詳しく説明されている。

遺伝的アルゴリズム〈4〉