2ちゃんねるというアジア逆さメガネ、車のハンドル、ピンボールのフリッパー

2016年06月27日

できるだけわかりやすく説明してみるという実験:遺伝的アルゴリズム

プログラムに登場するオブジェクトは、一般的にその性質や状態を表すパラメータを複数持っている。
たとえば、ある生物を表すオブジェクトがあった場合、その形を表すパラメータ(脚の本数、脚の長さ、目の位置など)や身体能力を表すデータ(足の速さ、他の種と戦う時の攻撃力など)、繁殖能力(一度に生まれる子供の数、受精から出産までにかかる時間など)といったように、ある生物の個体は複数のパラメータでその性質が表される。

遺伝的アルゴリズム(GA: Genetic Algorythm)は、このようなオブジェクトのパラメータを「交配」させることにより、最適なパラメータの組み合わせを見つけるための技術である。

従来の線形的な計算では、そのパラメータが無数なるにつれて、その組み合わせ数が爆発し、ある一定時間内には最適解にたどり着くことが非常に困難になる。

遺伝的アルゴリズムは、そのオブジェクトがもつパラメータを一本の遺伝子情報に見立て、それを交配することで新たな個体を発生する。このとき、ダーウィンの進化論に基づき、「より優性な個体どうしを掛けあわせてできる子供は優性である」ということから、交配と選別(=淘汰)を繰り返す。

たとえば先程の生物オブジェクトを一本の遺伝子情報にするというのは下図のようになる。 

ga1
 これと同じデータ構造(=遺伝子情報)を持ったもうひとつのオブジェクトを並べ、任意のある一点を「交差点」として決め、その点で両者の遺伝子情報を入れ替える。

ga2
 上の図の左側は親の世代で、それを交配してできたのが右側である。
この交差点を色々とかえることで微妙に性質が異なる子供をいくつか作ることができる。
そのなかからより優性(=最適解に近いもの)を2つ選び、それらを親としてさらに次の世代をいくつか作る、、、ということを繰り返すうちにどんどん最適解に近づいていく、という考え方が遺伝的アルゴリズムである。

この技術は、たとえば株式の分散投資をする際の最適なポートフォリオを見つける、といったような、無数の組み合わせがあるものの最適解を見つける、というところに応用される。
また、人工生命の分野においては欠かせないものである。これについてはそのうち。 


OLランキングで1位になりたい!賛同していただける方は下記をクリック!
2ちゃんねるというアジア逆さメガネ、車のハンドル、ピンボールのフリッパー