新規性探索アルゴリズムとは

「新規性探索（Novelty Search）」アルゴリズムとは、LehmanとStanleyが2008年に提案したアルゴリズムで、Open-ended evolution（OEE）を目指したALIFE研究のひとつです（論文はこちら）。

Novelty Search Users Page

このアルゴリズムは、目的を持たせなくても、「新しい行動をする」ことを追求する、という概念を実装したアルゴリズムです。目的に近づいているかどうかに関係なく、新しい行動をひたすら追求するだけで、単純な行動から複雑な行動へと進化していき、結果的に目的を達成されることが示されました。また、新規性探索アルゴリズムを使うと、目的に向かって探索する目的型探索では、局所解に陥ってしまい辿り着けない課題を、解けることがあることがシステマティックに示された瞬間でもありました。

たとえば、次の左の動画は、目的をもたせてロボットを進化させた場合の結果です。歩くことはできていますが、遠くに歩けるような安定した歩行は獲得できていないため、途中で転んでしまいます。一方、右の動画は、新規性探索アルゴリズムを使って、ひたすら新しい行動をするように進化させた場合の結果です。新しい行動をするように進化させたロボットの方が、結果的に遠くまで歩けるように進化しています。

新規性探索アルゴリズムは、その後、Map-Elites、Minimum Criterion Coevolution、POETアルゴリズムなど、「品質多様性（Quality Diversity）アルゴリズム」と呼ばれる発散的なアルゴリズムへと発展するきっかけとなりました。

新規性探索アルゴリズムや品質多様性アルゴリズムのように、OEEの研究は、自然の進化が多様な生物が無目的に変化してきたような、終わりなき、開かれた進化を実現するアルゴリズムの開発を目指しています。