組合わせ最適化問題は私たちの生活の身の回りで最もよく行われているといっても過言ではない。しかし、その裏には大変な計算量を処理する作業が必要となる。 利用されているものとして、例えば金融ポートフォリオ、物流経路、製造工程から人員のシフト決め等が挙げられる。

 

　今回 CEATEC2023 の河原研究室の発表において、この最適化問題を高速求解する大変ユニークなデバイスが紹介された。

 

そもそも組み合わせ最適化問題とは？

 

　組合わせ最適化問題は、先述の通り私たちの身近に数多く存在する。まずは簡潔にこの問 題について解説する。

最も簡潔にいうと、組合わせ最適化問題とは、膨大な選択肢の中から最適な選択肢を選ぶ作業となる。代表的な問題として、巡回セールスマン問題が挙げられる。

巡回セールスマン問題とは「セールスマンがいくつかの都市を 1 度ずつすべて訪問して出発点に戻ってくるときに、移動距離が最小になる経路」を求める問題だ。

都市数を n とすると、可能な経路の総数は n!/2n 通り存在する。

一見単純に思える。しかし n が大きくなると、この組み合わせの総数は爆発的に増加し、すべてを調べることは事実上不可能になる。

どの位絶望的かというと、ｎ（都市数）が 30 となると、スーパーコンピュータ「京」をもってしても 10250 億年かかる計算となる。

 

組合せ最適化問題の解決法

 

　近年、「アニーリングマシン」と呼ばれる組合せ最適化マシンの提案が相次いでいる。

それは、強磁性体の性質をモデル化した「イジングモデル」採用している。

イジングモデルとは強磁性体の原子の温度変化に伴う振る舞いをモデル化したものだ。

これを最適解探索プロセスとして利用する 本ブースで紹介されていたものは、まさに「イジングモデル」利用したものであった。

 

　余談だが、「イジングモデル」の代わりに、アメーバの振る舞いを最適解探索プロセスとみなすモデルも存在する。

アメーバは栄養吸収量を最大化しながら、忌避刺激である光の被照射リスクを最小化できる形状へと変形する振る舞いをする。

これを最適化探索プロセスと考え、最適化問題の試行回数を減らすのに利用する。

これらの最適化探索モデルを非常に簡潔にいえば、総当たりで全ての可能性を試すのではなく、既に自然界に存在するモデルに当てはめて、試行する回数を減らす手法ということだ。

 

本展示で紹介されていたデバイスのすごさ

 

　

出典:IoT社会のサステナブルな発展のために。東京理科大学 河原研究室

 

　本ブースで展示が行われていたのは、 「イジングモデル」を利用したマシンボードである。

一般的に、最適化問題は大規模なサ ーバーなどで実行される。 よって私たちの手元のデバイスで 実行されるというのは性能的な問題からあり得ないことであった。

しかし本展示は、その常識に風穴を開けるものであった。

本デモで展示されていたデバイスは、全結合型イジングマシンであった。

このサイズにまで小型化され、CMOS での検証に成功した実物は本展示物が初となる。

分り易くいえば、全結合型の「イジングモデル」を採用した演算装置ということになる。

 

　全結合型とは、「イジングモデル」を実行する複数のイジングマシンを集積し並列動作させる方式である。

どの位の数のイジングマシンを並列動作させるのかということを自由に設計することができるため、大きさと性能の設計自由度が高い。

よって求められるシチュエーションに合わせた開発が可能ということだ。

 

オフラインで最適化問題を解くと一体どのような利点があるのだろうか？

 

　まずは何といってもその場で、人員配置等の組合わせ最適化問題を解くことが出来るということに尽きるだろう。

その場で解けば、遅延が発生することもなく、データの伝送中における不意のエラーも発生することもない。

さらに、オフラインで行うのでセキュリティ面での不確実性が一切存在しない。

現在、多くの身の回りにある最適化問題はデータセンター等の大規模な施設で実行されている。

しかしその施設を開発・管理を行うのには莫大なコストがかかる。

この方式を採用したデバイスが普及することによって、小規模な組織や個人が最適化問題を処理し、私たちは大きな利便性を享受できるようになると河原教授は言った。

 

　まだ実験レベルのものであるのは明らかではあるが、採用されている技術は既存のものであり、実装した場合の信頼性は高いと容易に推測される。身近にありがら、極めて複雑な問題を解決できる本技術への期待度は高いと考えられる。

 

 

（IRUNIVERSE　Imahoko）

 

 

関連記事