見出し画像

A Data-Driven System for Combinatorial Optimization Problems

情報処理学会・学会誌「情報処理」

2023年度研究会推薦博士論文速報
［システムソフトウェアとオペレーティング・システム研究会］

齋藤 和広
（（株）KDDI総合研究所 AI部門量子コンピューティングGグループリーダー）

邦訳：組合せ最適化問題を対象としたデータ駆動システム

■キーワード
組合せ最適化／データ仮想化／量子アニーリング

【背景】組合せ最適化は多くの社会課題に存在する重要な問題
【問題】規模の大きい組合せ最適化問題を解くシステムの構築が困難
【貢献】組合せ最適化問題を効率的に解くシステムを提案

　組合せ最適化問題は，膨大な選択肢の中から条件を満たす最適な解を探索する問題である．有名な組合せ最適化問題の例として巡回セールスマン問題があり，「すべての都市を1回訪問する」という条件のもと，「最も短い移動時間」で巡回する順序を求める問題である．ここで解く対象の都市の数が増加すると，順序の選択肢が指数的に増え，組合せ爆発と呼ばれる現象が起きる．この例のように，多くの組合せ最適化問題は規模が拡大すると組合せ爆発により非常に多くのデータと計算時間が必要となる．しかし組合せ最適化問題は，渋滞解消や，物流の配送効率化によるCO2削減，災害時の避難経路など，多くの社会課題に含まれており，これを効率的に解くシステムの実装は非常に重要な課題である．

　組合せ最適化問題を解くためには，その問題を構成するために必要なデータを収集する必要がある．たとえば前述の巡回セールスマン問題では，都市の情報と，その都市間の移動時間を計算するための情報（移動媒体，経路，混雑状況など）が必要となる．これらのデータを収集し，データ分析や機械学習でデータを加工して，最適化処理を実行するデータ駆動型システムを考える．このシステムでは，データ収集時と最適化処理時のそれぞれ課題があった．データ収集では，必要なデータが1つのデータベースに格納されているとは限らず，所望のデータの探索や利用調整などに長時間を要していた．最適化処理については，従来のコンピュータを用いた最適化手法では問題の規模の拡大に伴い性能要件の達成に膨大な計算資源を要していた．

　そこで，これらの課題を解決するために，データ仮想化によるデータ基盤の仮想統合環境と，量子アニーリングによる高性能な最適化環境を備えた組合せ最適化問題のためのデータ駆動システムを提案した．データ仮想化によって複数のデータベースを仮想的に1つのデータベースとして統合し，既存のデータベースに変更を加えずに統一のインタフェースを提供することで，データ収集におけるデータ探索や利用調整などの課題を解決している．さらに，量子効果を利用して組合せ最適化の近似解を求める手法である量子アニーリングによって，従来のコンピュータで困難だった組合せ最適化問題を高速に解くことで，最適化処理における計算資源の課題を解決している．本博士論文では，実装したデータ駆動システムのプロトタイプと，実際の量子アニーリングマシンを利用して，データ仮想化システムとデータベース間の通信がシステムの性能に与える影響を評価し，量子アニーリングと古典的な手法を定量的に比較することで，その有効性を確認した．特に，具体的な組合せ最適化問題として配送計画問題とグルーピング問題において量子アニーリングが有効であることを示し，提案するデータ駆動システムにおいてデータ収集からこれらの最適化問題を解くまでの全体の性能を議論した．

参考文献
1）齋藤和広，渡辺泰之，村松茂樹，小林亜令：適切なクエリ処理エンジンを自動選択するマルチデータベースシステム，情報処理学会論文誌データベース，Vol.8，No.3，pp.24–39 (2015)． http://id.nii.ac.jp/1001/00145401/
2）齋藤和広，米田信之，渡辺泰之，黒川茂莉，村松茂樹，小林亜令：データベース分割を目的としたデータ仮想化によるデータベースの仮想統合，情報処理学会論文誌，Vol.59，No.2，pp.372–383 (2018)． http://id.nii.ac.jp/1001/00185752/
3）齋藤和広，大山重樹，梅木智光，黒川茂莉，小野智弘：配送計画問題における量子アニーリングの評価，情報処理学会論文誌データベース，Vol.14， No.1，pp.8–17 (2021)．http://id.nii.ac.jp/1001/00208971/
4）Saito, K., Kobayashi, A. and Ishikawa, Y. : Evaluating Quantum Annealing for Grouping Optimization with All Members’ Compatibility, in IEEE QCE (2022). https://doi.org/10.1109/QCE53715.2022.00114

（2024年5月26日受付）
（2024年8月15日note公開）

ー ー ー ー ー ー ー ー ー ー ー ー ー ー ー ー ー ー
　取得年月：2024年3月
　学位種別：博士（政策・メディア）
　大学：慶應義塾大学
　正会員
ー ー ー ー ー ー ー ー ー ー ー ー ー ー ー ー ー ー

推薦文［コンピュータサイエンス領域］システムソフトウェアとオペレーティング・システム研究会
複数のデータを統合することでこれまでにない新しい知識を得られます．ところがデータはさまざまな方法で管理されており，その統合は容易ではありません．そこで多様なデータを仮想化することによって一元的に管理できるシステムを提案しました．これに量子アニーリングを組み合わせることで，荷物配送を高速化できました．

研究生活　　本研究は，もともと会社と指導教官の川島英之先生との共同研究として始まりました．ある程度研究が進んだ段階で，社会人博士への進学を勧めていただき，チャレンジする決断をしました．私が取り組んでいた研究課題は，自身の興味領域であるだけでなく，会社としての課題でもあり，会社の理解もあって業務の一環としても研究活動をさせていただきました．しかし会社の方針変更によって途中で研究内容に変更があり，博士論文として仕上げる段階でとても苦労しました．それにもかかわらず，指導教官には熱心に辛抱強く指導いただき，なんとか仕上げることができ，感謝は尽きません．

社会人博士は会社の理解の有無で大変さが大きく変わると思います．博士課程進学と就職で悩んでいる方は，インターンなどを通じて会社の考えを確認した上で，社会人博士を選択肢の1つとして考えていただければと思います．