チェスをするアリが古い問題に新たな解決策を見つける

チェス盤からナイト 1 体以外の駒をすべて取り除きます。次に、ナイトを盤の 64 マスすべてに 1 回ずつ触れながら動かします (ナイトは L 字型に移動し、一方向に 2 マス、次に 90 度の角度で左か右か上か下に 1 マス移動します)。このいわゆる「ナイトのツアー」を 1 人で達成するのは非常に困難ですが、数学者の計算によると、これを実現する方法は驚くほどたくさんあります。開始した場所に戻れば、いわゆる「クローズド ツアー」を完了することになります。これには 26 兆通り以上の方法があります。開始点に戻らずにすべての場所に触れるだけの場合は、オープン ツアーと呼ばれます。これを行う方法の数は非常に多いため、科学者はまだ計算していません。

数世紀にわたって数学者を魅了してきた騎士の巡礼問題に対する新しい解法を求めて、ノッティンガム大学のコンピューター科学者グラハム・ケンドール氏とその同僚は、シミュレーションされたアリに着目した。彼らは、アリのコロニーと食料源の間の経路を探すアリの行動に基づいた群知能技術であるアリコロニー最適化アルゴリズムを使用した。ケンドール氏が The Conversation で説明しているように、その仕組みは次の通りである。

コンピュータ プログラムを使用して、アリの集団をシミュレートします。これらのアリには、問題の解決策を見つけるというタスクが割り当てられます。各アリはタスクを実行するときに、フェロモン トレイル (アリ同士のコミュニケーションに使う臭い物質) を敷きます。シミュレートされたアルゴリズムでは、最も成功したアリ (問題をよりうまく解決するアリ) は、パフォーマンスの低いアリよりも多くのフェロモンを敷きます。

このプログラムは数十万回繰り返され、ツアーを完了する道にさらに多くの「フェロモン」を配置します。ただし、機能する道を強化することと、新しい道を見つけることを重視することの間でバランスを取る必要があります。

ケンドール氏と彼の同僚は、このプログラムを使用して、騎士の旅に対する約 50 万通りの新しい解答を見つけました。何世紀にもわたって人々の興味をそそってきた疑問に対して、(シミュレーションされた) アリが新しい答えを見つけられるとは、誰が想像したでしょうか。

会話