japan

東芝トップページ > 企業情報 > 研究開発・技術 > 研究開発センター > 研究開発ライブラリ > 世界最速・最大規模の組合せ最適化を可能にする画期的なアルゴリズムの開発について−物流・創薬など社会課題を短時間で解決するサービスプラットフォームの構築に向けて−

情報通信プラットフォーム / 知能化システム

世界最速・最大規模の組合せ最適化を可能にする画期的なアルゴリズムの開発について
−物流・創薬など社会課題を短時間で解決するサービスプラットフォームの構築に向けて−

2019年04月20日
株式会社東芝

当社は、物流における効率的な配送ルートの探索や新薬開発における最も有効な分子構造の決定、収益性の高い金融商品の組合せなど膨大な組合せパターンの中から最良のものを選び出す組合せ最適化技術において、従来方式の約10倍となる世界最高速度、世界最大規模の最適化に成功しました。
本技術「シミュレーテッド分岐アルゴリズム」は、従来の技術では困難であった複雑で大規模な組合せ最適化問題の高精度な近似解(良解)の短時間導出が可能となるだけでなく、既存の計算機を活用した低コストでの大規模化を可能にするものであり、現在の最適化プロセスを一変させる可能性があると考えられます。
シミュレーテッド分岐アルゴリズムを活用することで、社会やビジネスにおける様々な課題を短時間で解決するサービスプラットフォームを構築し、よりよい社会の実現に貢献するとともに、2019年中の事業化を目指します。
なお、本技術の成果は米国オンライン科学雑誌「Science Advances」に掲載されました(追記)

物流・移動経路の最適化による配送効率の向上・渋滞の緩和、創薬のための分子設計、金融ポートフォリオの最適化など、社会やビジネスにおける様々な課題には、膨大な組合せパターンの中から最良のものを選び出す組合せ最適化問題の解決が求められます。この問題の解決には膨大な計算が必要であり、既存の計算機では解くことが困難と考えられているため、量子計算機をはじめとする次世代計算機への期待が高まっています。次世代計算機として、超電導回路、レーザー、半導体デジタル計算機といった様々な方式の組合せ最適化専用計算機が現在活発に研究開発されていますが、扱える問題の大規模化や解を見つけるまでの時間の短縮が課題でした。
例えば、超電導回路を用いた量子計算機では、大規模で複雑な問題を扱うことが現状困難です。一方、半導体デジタル計算機では扱える問題の規模を大規模化しやすくなりますが、そこで用いられている従来アルゴリズムは並列化(注1)しにくく、並列計算による高速化が原理的に困難です。

そこで当社は、並列計算による高速化が可能な全く新しい組合せ最適化アルゴリズム、シミュレーテッド分岐アルゴリズムを開発しました。シミュレーテッド分岐アルゴリズムは高い並列性を持つため、現在普及しているデジタル計算機を用いた並列計算により容易に高速化が可能となります。また、既存の計算機をそのまま利用できるため新たな設備導入が不要となり、低コストでの大規模化も容易です。
例えば、FPGA(注2)を用いると、2000変数・全結合(約200万結合)の問題の良解をわずか0.5ミリ秒で得ることができます。これは同問題の計算において世界最速だったレーザーを用いた量子計算機(注3)に比べて約10倍高速です。また、GPU(注4)を8台つないだGPUクラスタを用いて、10万変数・全結合(約50億結合)の大規模問題に対し、わずか数秒で良解を見つけ出すことができます。これらの結果は、社会やビジネスが抱える大規模な組合せ最適化問題を解くための新たな道を拓くものです。
シミュレーテッド分岐アルゴリズムは、古典力学(注5)における分岐現象(注6)・断熱過程(注7)・エルゴード過程(注8)の3つの現象をうまく利用して、高精度な解を高速に見つけ出します。当社はこの原理を、当社独自の量子計算機(注9)の理論から発見しました。量子力学に導かれてなされた古典力学の本発見は、未知の数学の定理をも示唆する学術的にも新しいものです。

当社グループは、デジタルトランスフォーメーションによってビジネスモデルの革新的な変換を図り、様々な事業分野の顧客企業の経営課題を起点とした新しい課題解決型・成果訴求型ビジネス創出に取り組んでいます。
本技術をキー技術として、物流・金融をはじめ現代社会におけるあらゆる最適化ニーズに応えるサービスプラットフォームを実現するとともに、2019年中の事業化を目指します。

表

シミュレーテッド分岐マシンが2000変数・全結合問題の解を求める際の2000粒子の運動の様子


左図:2000粒子の位置xの時間変化(横軸が時刻、縦軸が位置x)。


右図:2000粒子の位相空間(xy平面)内での動き。(横軸が位置x、縦軸が運動量y)

どちらの図においても、赤はxが正、青はxが負であることを示している

※再生ボタンをクリックすると、YouTubeに掲載している動画が再生されます。
※YouTubeは弊社とは別企業のサービスであり、各サービスの利用規約に則りご利用ください。

(注1)アルゴリズムに含まれる演算のうち同時刻に実行可能な演算を,複数の演算処理部によって同時並行的に処理すること。

(注2)Field-Programmable Gate Arrayの略称。演算処理集積回路の一種で,製造後にユーザーが用途に応じて機能を書き換えることが可能。

(注3)当社調べ。Inagaki et al., Science 354, 603 (2016)。

(注4)Graphics Processing Unit(GPU)の略称。画像処理向け集積回路で,多数の演算処理部を含む。複数のGPUを相互接続したものをGPUクラスタと呼ぶ。

(注5)原子などの微視的な世界を説明する量子力学に対し、それ以前のニュートン以来の力学を古典力学と呼ぶ。

(注6)非線形力学系において、系のパラメータの変化に伴い、安定運動状態が1つから複数に変化する現象。

(注7)力学系において、系のパラメータがゆっくりと変化するとき、エネルギーの低い状態に留まり続ける現象。

(注8)古典力学系において、エネルギー的に許されるあらゆる状態を満遍なく動き回る現象。カオスの一種。

(注9)H. Goto, Scientific Reports 6, 21686 (2016)で発表した、量子断熱定理と量子分岐現象に基づく量子計算機。

(追記)Science Advances 19 Apr. 2019, Vol. 5, no. 4, eaav2372
        「Combinatorial optimization by simulating adiabatic bifurcations in nonlinear Hamiltonian systems」H.Goto et al. 別ウィンドウ


  • 「研究開発センター」のトップへ
  • このページのトップへ