「組合せ最適化問題」に必要なQUBO行列を超高速に作成
続いて発表したのは中川修氏。応募プログラムは「量子アニーリングを用いた避難経路最適化のためのリアルタイムQUBO行列作成プログラム」。解決したい社会課題として中川氏がテーマにしたのは群衆事故。群衆事故とは、統制ないし誘導されていない人の流れによって発生する事故のことを指す。
人が密集する空間で避難口に人が殺到して群衆事故が発生しないよう、いかにして人びとを迅速に避難誘導させるか。「これは言うほど簡単なことではない」と中川氏。というのも全体状況を俯瞰して超高速に組合せ最適化問題を解く必要があるからだ。量子アニーリングを使えば簡単に解けるのではと思うかもしれないが、量子アニーリング計算に必要なQUBO行列作成は従来型のコンピュータで作るしかなく、これが遅いと意味がない。そこでSX-Aurora TSUBASAのベクトルエンジンを利用することで、QUBO行列の作成を高速化・リアルタイム化するプログラムの実現に取り組むことになったという。
組合せ最適化の基本アイデアは、各人に対する避難経路の候補を数パターン生成し、各人の重なりの最も少ない経路を最適経路とする。
計算式は次の図の通り。
中川氏は10x10の通路マップ上に50人が、ある偏りをもってランダムに存在するという状態を想定して、量子アニーリングで全体最適化を実施した。発生していた渋滞は緩和できたが、QUBO作成に0.008秒かかったという。この結果からベクトルエンジンを使う必要がないと思われるかもしれないが、大規模ショッピングモールや百貨店の避難経路最適化を考えると、複数階のフロアにまたがった通路に数百～数千人の客が集まる状況が起こりえる。例えば5000人だとQUBO行列の計算時間は約9秒。「そんな時間は待てませんよね」と中川氏。そこで活用するのがSX-Aurora TSUBASAのベクトルエンジンである。
リアルタイムQUBO行列作成プログラムの処理の流れは次の図の通り。
候補経路作成とQUBO行列作成のソースコードにベクトル化の工夫を施した上で、「ベクトルエンジンを利用しない場合（gccのみ）」「ベクトルエンジンを利用しない場合（gcc＋OpenMP利用）」「ベクトルエンジンを利用する場合（ncc＋OpenMP利用）の3つのパターンで処理時間を計測した。OpenMPを利用することで約7.8倍、ベクトルエンジンを利用することでさらに約14.2倍の高速化、トータルで約111倍の高速化を実現。約0.08秒で計算が完了したという。
「今回の技術は災害時の避難誘導だけではなく、交通渋滞の回避やドローンなどの次世代交通インフラの制御にも適用できると考えられます」と中川氏は加える。
災害対策や高度交通システム、エアモビリティなどは、大量のセンシングデータを収集してリアルタイムに計算結果を返す必要がある領域。これらは、普通のPCに組み込んで使えるSX-Aurora TSUBASAが生かせる領域だ。
続いて行われた質疑応答では、NEC速水氏の「SX-Aurora TSUBASAを操作した感想やベクトル化の工夫について教えてほしい」という質問に対し、中川氏は「FOR LOOPの中にif文を書くと遅くなるので、if文に相当するものをLOOPの外に出すような処理を多用しています。乱数発生のところもLOOPに入れると時間がかかるので、NECが提供している数値計算のライブラリを使用し、乱数を外に出すという工夫をしました」と回答。
また田尾氏の「組合せ最適化問題で未解決な問題はいろいろあったと思いますが、今回のプログラムを選んだ理由について教えてください」という質問には、「例えば製造スケジューリングやシフト表、物流の配送ルートなども組合せ最適化問題ですが、それらは数理最適ソフトウェアが出ており、それで解けてしまいます。今回のプログラムを選んだのは、量子アニーリングの得意分野である2次計画問題であり、社会課題解決につながると考えたからです」と回答した。
