巡回セールスマン問題を粘菌の力で解決する新型コンピュータを北大が開発

北海道大学(北大)とAmoeba Energyは12月2日、アメーバ生物である真性粘菌の探索行動から着想を得た新型アナログコンピュータを開発し、代表的な組み合わせ最適化問題「巡回セールスマン問題」を解くことに成功したと共同で発表した。

同成果は、北大 量子集積エレクトロニクス研究センターの葛西誠也教授と、Amoeba Energyとの共同研究チームによるもの。詳細は、英オンライン総合学術誌「Scientific Reports」に掲載された。

巡回セールスマン問題とは、セールスマンが決められた数の都市をそれぞれ一度だけ訪問して出発都市に戻るという巡回経路のうち、移動距離が最短となる(もっとも効率のいい)ルートを導くという問題だ。計算複雑性理論において「NP困難問題」に分類され、多項式時間(実用的時間)内で最適解を導く手法が知られていない複雑な組み合わせ最適化問題として有名である。

なお組み合わせ最適化問題は、巡回セールスマン問題のイメージが強いが、何も数学の研究的な話ばかりではない。物流の配送スケジューリングや職場における勤務シフト作成など、社会のさまざまな課題を解決できる数学である。

社会におけるさまざまな課題を解決するためには、組み合わせ最適化問題の解決が役に立つが、同問題の多くは効率よく最適解を得る解き方が知られておらず、決められた手順に従って動作する従来型のコンピュータがとても苦手とする問題だ。

近年、カナダD-Waveの開発した「量子アニーリングマシン」に代表される、「イジングマシン」と呼ばれる方式の組み合わせ最適化専用コンピュータの研究開発が国内外で活発化している。しかし、実社会の課題をイジングマシンが扱える形式に変換する際に、高い専門知識と複雑な計算が必要だ。また、制約や要求が増大すると条件を満たさないものも解として提示してしまうという弱点を抱えており、こうした問題点の解決が課題となっていた。

真性粘菌は単細胞であるにもかかわらず、不定形の体を環境に適したもっとも良い形に変形できる高度な計算能力を持つことが知られている。そんな粘菌を組み込んだ「粘菌コンピュータ」が、巡回セールスマン問題の良い解を探索できることが示された研究成果も報告されているほどで、エサを効率よく求めていくなど、知性があるのではないかと錯覚するほどである。

そうした背景を受けて共同研究チームは、アメーバが変形するメカニズムをアナログ電子回路中の電子の動きで再現する独自の「アメーバコア」に、制約条件をコンパクトに表現する「抵抗クロスバー」を組み合わせた新方式のコンピュータ「電子アメーバ」を開発した。

• 今回開発された電子アメーバの回路模式図。左側がアメーバコア、右側の格子状の回路が抵抗クロスバー (出所:2者共同プレスリリースPDF)

電子アメーバは、巡回セールスマン問題を定義する都市間距離をクロスバーの交点にある抵抗値で表現し、クロスバーによって定義される電子環境の中でアメーバコアが解を探索するというものだ。都市配置や距離は、抵抗値を変えるだけで簡単に変更することができるようになっている。

今回開発された電子アメーバにより、巡回セールスマン問題のうち、4都市を回る場合の最短経路を探し出すことに成功したという。

• 解かれた巡回セールスマン問題の問題と試作システムの出力波形。“1”となる出力が訪問順を表している。得られた解はA→D→C→B→Aであり、最短経路になっていることがわかる (出所:2者共同プレスリリースPDF)

より大きな都市数の問題に対する探索性能を回路シミュレータを用いて調べると、電子アメーバが探し出せる巡回経路長は、「無作為抽出法」により得られた平均的経路長よりも常に短いことが判明。経路を探すために要する時間も、都市数に比例する程度に抑えられることが確認された。

• 回路シミュレーションによる電子アメーバ性能評価結果。(a)得られた巡回経路長と都市数の関係。縦軸は無作為抽出法によって得られた巡回経路長の平均値で規格化されており、平均経路長よりも常に短い経路が探し出されている。(b)都市数が増えたときに解探索時間がどの程度長くなるかの評価が行われた結果。従来コンピュータ上に実装された、巡回セールスマン問題を解く代表的なアルゴリズム「2-opt法」が電子アメーバが見つけたものと等しい距離の巡回経路を見つけ出す時間が比較された。縦軸は10都市の探索時間からの増分がプロットされている。都市数が増えるほど、電子アメーバの方が有利になることがわかる (出所:2者共同プレスリリースPDF)

巡回セールスマン問題は、理論的には都市数が増えると経路の候補が爆発的に増加していくが、電子アメーバはすべての経路候補を参照しなくても短い経路を見つけ出すことが可能だという。この高い探索能力はアメーバ生物を用いた粘菌コンピュータが持つ特徴と同様であり、電子アメーバは生物が自然淘汰を経て獲得した優れた能力を再現しているといえるとしている。

さらに、巡回セールスマン問題を解く代表的なアルゴリズム「2-opt法」との探索時間に関しての比較が行われ、都市数が多くなるほど電子アメーバが有利になることも確かめられたという。

今回の研究成果は、スーパーコンピュータでも解決困難な組み合わせ最適化問題の解法や、制約や要求が変わり続ける実社会システムの多様な課題にも適応できる新原理コンピュータの実現につながることが期待されるという。Amoeba Energyでは、すでに複数の企業や大学と共同で実用化に向けた研究開発を進めている。

また、電子アメーバとクロスバー構造は、一般的な半導体デバイスで構成されたシンプルかつコンパクトな回路であり、半導体集積回路技術を利用することで小型・低消費電力の専用計算チップを作製できるという。今後、IoTデバイスなどにも組み込み可能な小型で省電力の組み合わせ最適化チップとして、超スマート社会「Society 5.0」におけるさまざまな場面での活躍が期待されるとしている。