アメーバベースのコンピューティングシステムによって得られる巡回セールスマン問題の解決策。 実験で得られた4、5、6、7、8都市のセールスマンツアーの例。各ツアーは右図の対応するチャンネルに赤く塗られています。 左のパネルは、初期状態の透過光画像を示しています（
東京の慶應義塾大学の日本人研究者グループは、アメーバが巡回セールスマン問題として知られている驚くほど複雑な数学的問題の近似解を生成できることを実証しました。
セールスマンのタスクは、最も有名な組み合わせ最適化タスクの1つです。これは、これらの都市を少なくとも1回通過してから元の都市に戻る最も収益性の高いルートを見つけることです。
ただし、問題の最適化ステートメントは、その特殊なケースのほとんどと同様に、NPハード問題のクラスに属します。 「決定問題」のバージョン（つまり、ルートが指定されたkの値を超えて存在しないかどうかが問われる問題）のバージョンは、NP完全問題のクラスに属します。
適切なソリューションを計算することの難しさは、より多くの都市がタスクに追加されるにつれて指数関数的に増加します。 たとえば、4つの都市には3つのソリューションがあり、6つの都市には360のソリューションがあります。将来、指数関数的な成長が続きます。
計算が非常に複雑であるにもかかわらず、数万都市の場合を完全に解決できるヒューリスティックで正確なアルゴリズムが多数あり、数百万都市の問題でさえ0.05％以内で近似できます 。 示されたリンクには、National Geographical Societyの拠点から地球の1,904,711都市のインスタンスを解決する試みが含まれています。
1,904,711都市の国立地理学会の拠点
現時点では、地球の都市の最小距離の記録は7 515 772 107 kmであり、ヒューリスティックLKHアルゴリズムを使用して2018年3月13日に設定されました。
コンピューターサイエンスにおける古典的なセールスマンの問題は、最適化アルゴリズムのベンチマークとして使用されます。
アメーバは単細胞生物であり、組み合わせ最適化の複雑さについてはまったく考えていません。 彼らは中枢神経系に遠隔的に似ているものすらありません。そのため、そのような複雑な問題を解決するのに適していない候補になります。 しかし、日本の研究者は、特定のタイプのアメーバを使用して、8都市の巡回セールスマン問題の最適に近いソリューションを計算できることを発見しました。
科学記事によると、以前に他のいくつかの実験で生物学的コンピューターとして使用されていたPhysarum polycephalumと呼ばれるアメーバが実験に参加しました。 この生物は、より効率的な食物の入手方法を求めて体のさまざまな領域を拡大でき、光を嫌うため、生物学的コンピューティングで特に有用であると考えられています。
栄養のこの自然なメカニズムをコンピューターに変えるために、日本の研究者たちは、アメーバを動物が体を伸ばすことができる方向に64チャンネルの特別なプレートに置いた。 アメーバは、栄養プレートの可能な限り大きな領域をカバーするために、常に体を拡張しようとしています。 それにもかかわらず、プレートの各チャンネルを照らすことができます。これにより、アメーバは光に対する嫌悪感からこのチャンネルから抜け出します。
巡回セールスマンの問題をシミュレートするために、プレート上の64チャンネルのそれぞれに、都市の順序を示す1から8までの数字に加えて、AとHの間の都市コードが割り当てられました（都市の順序は、セールスマンが訪問した順序に対応します）。
アメーバをプログラムするために、研究者はニューラルネットワークを使用しました。これには、アメーバの現在の位置と特定のチャネルを照らすための都市間の距離に関するデータが含まれていました。 ニューラルネットワークは、都市（チャネル）間の距離が大きいほど照らす可能性が高くなりました。
アルゴリズムとアメーバが相互作用すると、後者は巡回セールスマン問題の近似解を表す形式を取ります。 最も興味深いのは、ソリューションの数が指数関数的に増加するにもかかわらず、これらのほぼ最適なソリューションを取得するのにアメーバが要する時間が増加することです。 近い将来、研究者は何万ものチャネルでチップを製造し、アメーバが何百もの都市で巡回セールスマンの問題を解決できるようにします。
科学論文は、2018年12月19日にジャーナルRoyal Society Open Science （doi：10.1098 / rsos.180396）に掲載されました。