北海道大学の葛西誠也教授らの研究グループは、Amoeba Energy株式会社と共同で、アメーバ生物である粘菌の行動に学んだ新型アナログコンピュータを開発し、代表的な組合せ最適化問題「巡回セールスマン問題」を解くことに成功した。
巡回セールスマン問題とは、セールスマンが指定都市を各一度ずつ訪問し出発都市に戻る巡回経路のうち最短距離の経路を導く問題。「組合せ最適化問題」と呼ばれるこの数学的問題は、物流配送計画や勤務スケジュール作成など社会の様々な課題に関連する。しかし、従来型デジタルコンピュータでは解決が難しく、近年は量子コンピュータなどによる提案が相次いでいる。ただ、マシンが扱える形式に問題を変換することが難しいという課題があった。
アメーバ生物である単細胞の真性粘菌は、不定形の体を環境に最適な形に変形できる高度な計算能力を持つ。先行研究で、アメーバ生物を組込んだ「粘菌コンピュータ」が巡回セールスマン問題に利用可能と分かっていた。そこで研究グループは、アメーバが変形するメカニズムをアナログ回路中の電子の動きで再現し、都市配置や距離などの制約条件をコンパクトに表現できる仕組みの新方式コンピュータ「電子アメーバ」を開発。これにより、巡回セールスマン問題の解を迅速に探し出すことに成功した。この問題を解く代表的なアルゴリズム（2-opt法）と比較すると、都市数が多くなるほど電子アメーバが解探索で有利になった。
生物が獲得した探索能力を電子回路で再現した電子アメーバは、制約や要求が変わり続ける実社会の難しい課題の解決に貢献できる。さらに、IoTデバイスなどに組込み可能な小型で低消費電力の新原理コンピュータの実現も期待される。
論文情報：
投稿 難問の巡回セールスマン問題、粘菌に学んだ新型コンピュータで北海道大学が解決 は 大学ジャーナルオンライン に最初に表示されました。
