全2661文字

NECはシミュレーテッドアニーリング(SA)が苦手としていた巡回セールスマン問題での求解を50倍以上高速化する独自アルゴリズムを開発した。加えて、将来の量子コンピューターにつながる技術で独自の量子アニーリング(QA)マシンも開発中だ。NTT、産業技術総合研究所、そしてデンソーまでもが次世代イジングマシンの開発に参戦してきた。

 NECは東芝よりさらに遅れてイジングマシンに参戦してきた。ただ、コロンブスの卵のような、驚きの発想の転換で、いきなりトップランナーになる可能性がありそうだ。

 ここでいうコロンブスの卵とは、独自の発想でイジングマシンの課題を大幅に改善してしまった件である(図16)。

(a)SAは制約条件の領域で無駄の多い探索が多い
(a)SAは制約条件の領域で無駄の多い探索が多い
[画像のクリックで拡大表示]
(b)100都市の巡回セールスマン問題が50倍高速に解けた
(b)100都市の巡回セールスマン問題が50倍高速に解けた
[画像のクリックで拡大表示]
(c)規模拡張には“同時通訳の技”を投入
(c)規模拡張には“同時通訳の技”を投入
[画像のクリックで拡大表示]
図16 独自のSAで巡回セールスマン問題も容易に解ける
NECが開発した独自SAの概要。NECはSAの課題が制約条件の設定と、その条件に反する領域でも探索を進めてしまう点にあると考え、制約条件で禁止されている領域を探索しないようにした独自SAを開発した(a)。すると、一般的にはSAでは制約条件の設定が難しいことでうまく解けないとされる、100都市規模の巡回セールスマン問題も容易に解けることが分かったという(b)。今後は、複数サーバー機間での通信のやり取りを待たずに、推測した値を基にほぼ並列に処理を進め、間違っていたらその部分を再計算する同時通訳の技に似た仕組みで、システムの大規模化を進める計画だという(c)。(出所:NEC)

禁止領域は探索しなければよい

 これを具体的に説明する。イジングマシンは、x≧5といった単純な制約条件で禁止されている領域でも探索してしまう課題を抱えている。特に、巡回セールスマン問題(TSP)のような問題では、目的関数に加える制約条件の定式化が難しく、無駄に探索してしまう領域が大幅に増えてしまう。

 NECはこの課題に対して、目的関数とは独立に、求解時に「ヒント情報」という形で入れた制約条件を考慮し、その制約条件で禁止されている領域の探索をしないようにするSAを開発した。

 言われてみれば確かにという典型的なコロンブスの卵といえる。NECはこのアルゴリズムを100都市のTSPに適用したところ、従来の50倍も高速に解が得られたとする。ベクトルマシンなどハードウエアの強みも含めると、その当時でさらに6倍、合わせて300倍の高速化につながった。ちなみに、現時点ではベクトルマシンの性能が向上し、さらに10倍高速に解けるという。