特許ウォッチ

公開番号2024099215
公報種別公開特許公報(A)
公開日2024-07-25
出願番号2023002994
出願日2023-01-12
発明の名称最適化システム、最適化方法及びプログラム
出願人国立大学法人東北大学
代理人個人,個人,個人,個人,個人
主分類G06N 99/00 20190101AFI20240718BHJP(計算;計数)
要約【課題】アニーリングによる最適化の実行による最適化の精度を高める技術を提供すること。
【解決手段】第1変数を独立変数とする関数で表現される最適化対象であって拘束条件を有する最適化対象、の最適化を行う最適化システムであって、アニーリングによる最適化を実行するアニーラーと、前記アニーラーを制御する制御部と、を備え、前記最適化は、前記第1変数にくわえて更に第2変数を独立変数とする関数であり第1変数についてより一層低次元である、という条件を満たす関数によって分配関数が表現された系であって前記最適化対象を表現する系、の最適化であり、前記最適化は、第1変数に基づいて第2変数を推定する数理モデルを前記制御部が実行する推定処理と、アニーリングによって最適化を行う処理とを含み、前記数理モデルは、前記最適化の結果に応じて更新される、最適化システム。
【選択図】図1
特許請求の範囲【請求項１】
第１変数ｘを独立変数とする関数で表現される最適化対象であって拘束条件を有する最適化対象、の最適化を行う最適化システムであって、
アニーリングによる最適化を実行するアニーラーと、
前記アニーラーを制御する管理制御部と、
を備え、
前記最適化は、前記第１変数ｘにくわえて更に第２変数ｚを独立変数とする関数であり、前記拘束条件を示す項が、前記第２変数ｚを用いない場合よりも前記第１変数ｘについて低次元である、という条件を満たす関数である低次元分配関数、によって分配関数が表現された系であって前記最適化対象を表現する系、の最適化であり、
前記最適化は、前記第１変数ｘに基づいて前記第２変数ｚを推定する数理モデルを前記管理制御部が実行する推定処理と、前記第２変数ｚの値が前記推定処理で推定された値に固定された状態における前記最適化対象の最適化を前記アニーラーがアニーリングによって行うアニーリング処理と、前記拘束条件が満たされている度合が所定の度合よりも高いか否かを前記アニーリング処理の結果を用いて前記管理制御部が判定する判定処理と、を含み、
前記度合が前記所定の度合以下である場合に、前記管理制御部は、前記拘束条件が満たされている度合をより一層高めるように前記数理モデルを更新する、
最適化システム。
続きを表示（約 800 文字）【請求項２】
前記低次元分配関数における前記拘束条件を示す項は、前記第１変数ｘについて１次元である、
請求項１に記載の最適化システム。
【請求項３】
前記アニーリングは、量子アニーリングである、
請求項１に記載の最適化システム。
【請求項４】
第１変数ｘを独立変数とする関数で表現される最適化対象であって拘束条件を有する最適化対象、の最適化を行う最適化システムであって、アニーリングを実行するアニーラーと、前記アニーラーを制御する管理制御部と、を備え、前記最適化は、前記第１変数ｘにくわえて更に第２変数ｚを独立変数とする関数であり、前記拘束条件を示す項が、前記第２変数ｚを用いない場合よりも前記第１変数ｘについて低次元である、という条件を満たす関数である低次元分配関数、によって分配関数が表現された系であって前記最適化対象を表現する系、の最適化である最適化システム、が実行する最適化方法であって、
前記管理制御部が、前記第１変数ｘに基づいて前記第２変数ｚを推定する数理モデルを実行する推定ステップと、
前記アニーラーが、前記第２変数ｚの値が前記推定ステップで推定された値に固定された状態における前記最適化対象の最適化をアニーリングによって行うアニーリングステップと、
前記管理制御部が、前記拘束条件が満たされている度合が所定の度合よりも高いか否かを前記アニーリングステップの結果を用いて判定する判定ステップと、
を有し、
前記管理制御部は、前記度合が前記所定の度合以下である場合に、前記拘束条件が満たされている度合をより一層高めるように前記数理モデルを更新する、
最適化方法。
【請求項５】
請求項１～３のいずれか一項に記載の最適化システムとしてコンピュータを機能させるためのプログラム。

発明の詳細な説明【技術分野】
【０００１】
本発明は、最適化システム、最適化方法及びプログラムに関する。
続きを表示（約 2,200 文字）【背景技術】
【０００２】
近年、最適化を高速に行えることから、量子アニーリング等のアニーリングによる最適化（以下「アニーリング最適化」という。）の実行による最適化への注目が高まっている。アニーリング最適化は、具体的には、量子アニーラー（非特許文献１参照）等によって実行される。
【先行技術文献】
【非特許文献】
【０００３】
Masayuki Ohzeki, Akira Miki, Masamichi J. Miyama, Masayoshi Terabe, “Control of automated guided vehicles without collision by quantum annealer and digital devices”, Front. Comput. Sci., 19 (2019)
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、独立変数について２次以上の高次の項を含む関数で最適化対象が表現される場合、アニーリング最適化の実行による最適化の精度は良く無い場合があった。理由は、ビットを表現する実体間の相互作用の影響である。なお、ビットを表現する実体は、量子アニーラーであれば例えばスピンである。
【０００５】
上記事情に鑑み、本発明は、アニーリングによる最適化の実行による最適化の精度を高める技術を提供することを目的としている。
【課題を解決するための手段】
【０００６】
本発明の一態様は、第１変数ｘを独立変数とする関数で表現される最適化対象であって拘束条件を有する最適化対象、の最適化を行う最適化システムであって、アニーリングによる最適化を実行するアニーラーと、前記アニーラーを制御する管理制御部と、を備え、前記最適化は、前記第１変数ｘにくわえて更に第２変数ｚを独立変数とする関数であり、前記拘束条件を示す項が、前記第２変数ｚを用いない場合よりも前記第１変数ｘについて低次元である、という条件を満たす関数である低次元分配関数、によって分配関数が表現された系であって前記最適化対象を表現する系、の最適化であり、前記最適化は、前記第１変数ｘに基づいて前記第２変数ｚを推定する数理モデルを前記管理制御部が実行する推定処理と、前記第２変数ｚの値が前記推定処理で推定された値に固定された状態における前記最適化対象の最適化を前記アニーラーがアニーリングによって行うアニーリング処理と、前記拘束条件が満たされている度合が所定の度合よりも高いか否かを前記アニーリング処理の結果を用いて前記管理制御部が判定する判定処理と、を含み、前記度合が前記所定の度合以下である場合に、前記管理制御部は、前記拘束条件が満たされている度合をより一層高めるように前記数理モデルを更新する、最適化システムである。
【０００７】
本発明の一態様は、第１変数ｘを独立変数とする関数で表現される最適化対象であって拘束条件を有する最適化対象、の最適化を行う最適化システムであって、アニーリングを実行するアニーラーと、前記アニーラーを制御する管理制御部と、を備え、前記最適化は、前記第１変数ｘにくわえて更に第２変数ｚを独立変数とする関数であり、前記拘束条件を示す項が、前記第２変数ｚを用いない場合よりも前記第１変数ｘについて低次元である、という条件を満たす関数である低次元分配関数、によって分配関数が表現された系であって前記最適化対象を表現する系、の最適化である最適化システム、が実行する最適化方法であって、前記管理制御部が、前記第１変数ｘに基づいて前記第２変数ｚを推定する数理モデルを実行する推定ステップと、前記アニーラーが、前記第２変数ｚの値が前記推定ステップで推定された値に固定された状態における前記最適化対象の最適化をアニーリングによって行うアニーリングステップと、前記管理制御部が、前記拘束条件が満たされている度合が所定の度合よりも高いか否かを前記アニーリングステップの結果を用いて判定する判定ステップと、を有し、前記管理制御部は、前記度合が前記所定の度合以下である場合に、前記拘束条件が満たされている度合をより一層高めるように前記数理モデルを更新する、最適化方法。である。
【０００８】
本発明の一態様は、上記の最適化システムとしてコンピュータを機能させるためのプログラムである。
【発明の効果】
【０００９】
本発明により、アニーリングによる最適化の実行による最適化の精度を高める技術を提供することが可能となる。
【図面の簡単な説明】
【００１０】
実施形態の最適化システムの概要を説明する説明図。
実施形態における最適化システムで実行される最適化の処理の流れの一例を示すフローチャート。
実施形態における管理装置のハードウェア構成の一例を示す図である。
実施形態におけるアニーラーのハードウェア構成の一例を示す図。
実施形態におけるアニール部の構成の一例を示す図。
【発明を実施するための形態】
（【００１１】以降は省略されています）

関連特許