特許ウォッチ

公開番号2024127272
公報種別公開特許公報(A)
公開日2024-09-20
出願番号2023036306
出願日2023-03-09
発明の名称最適化装置、最適化方法および最適化プログラム
出願人日本電気株式会社
代理人個人,個人
主分類G06N 99/00 20190101AFI20240912BHJP(計算;計数)
要約【課題】組み合わせ最適化問題の近似解を探索できる最適化装置を提供する。
【解決手段】イジングモデル作成手段81は、組み合わせ最適化問題における選択候補と、その選択候補を選択する粒度を規定した解像度により規定される変数を用いて、量子アニーリングによる最適化処理で用いられるイジングモデルを作成する。サンプリング手段82は、作成されたイジングモデルを用いた最適化処理により最適化問題の近似解をサンプリングする。更新手段83は、選択候補および解像度を更新する。そして、イジングモデル作成手段81は、更新された選択候補および解像度により規定される変数を用いてイジングモデルを更新し、サンプリング手段82は、更新されたイジングモデルを用いてサンプリングする。
【選択図】図4
特許請求の範囲【請求項１】
組み合わせ最適化問題における選択候補と、当該選択候補を選択する粒度を規定した解像度により規定される変数を用いて、量子アニーリングによる最適化処理で用いられるイジングモデルを作成するイジングモデル作成手段と、
作成された前記イジングモデルを用いた最適化処理により前記最適化問題の近似解をサンプリングするサンプリング手段と、
前記選択候補および前記解像度を更新する更新手段とを備え、
前記イジングモデル作成手段は、更新された前記選択候補および前記解像度により規定される変数を用いて前記イジングモデルを更新し、
前記サンプリング手段は、更新されたイジングモデルを用いてサンプリングする
ことを特徴とする最適化装置。
続きを表示（約 1,300 文字）【請求項２】
更新手段は、選択候補を一部に絞り込む更新を行うとともに、絞り込まれた選択候補の解像度を詳細にする更新を行う
請求項１記載の最適化装置。
【請求項３】
更新手段は、イジングモデルにより算出されるエネルギー値が小さい上位の選択候補に絞り込む更新を行う
請求項１または請求項２記載の最適化装置。
【請求項４】
更新手段は、制約条件をより優先するようにイジングモデルの重みを更新する
請求項１または請求項２記載の最適化装置。
【請求項５】
更新手段は、前記イジングモデルにおいて、制約条件式を示す項を構成する変数の重みを増加させる更新を行う
請求項１または請求項２記載の最適化装置。
【請求項６】
イジングモデル作成手段は、選択候補の選択有無および当該選択候補の取りうる値の範囲を分割する粒度を規定した解像度に基づいて変数を規定する
請求項１または請求項２記載の最適化装置。
【請求項７】
イジングモデル作成手段は、選択候補の取りうる値の範囲を粒度に応じて等間隔に分割された各範囲の値を取るか否かを示す変数と、当該各範囲の値のうちいずれか１つのみ選択されることを示す制約条件とを含むイジングモデルを作成する
請求項１または請求項２記載の最適化装置。
【請求項８】
イジングモデル作成手段は、組成の割合を決定する組み合わせ最適化問題における選択候補と、当該選択候補が取りうる組成の割合の範囲を粒度に応じて分割した各範囲について割り当てられる変数を用いて、イジングモデルを作成する
請求項１または請求項２記載の最適化装置。
【請求項９】
組み合わせ最適化問題における選択候補と、当該選択候補を選択する粒度を規定した解像度により規定される変数を用いて、量子アニーリングによる最適化処理で用いられるイジングモデルを作成し、
作成された前記イジングモデルを用いた最適化処理により前記最適化問題の近似解をサンプリングし、
前記選択候補および前記解像度を更新し、
更新された前記選択候補および前記解像度により規定される変数を用いて前記イジングモデルを更新し、
更新されたイジングモデルを用いてサンプリングする
ことを特徴とする最適化方法。
【請求項１０】
コンピュータに、
組み合わせ最適化問題における選択候補と、当該選択候補を選択する粒度を規定した解像度により規定される変数を用いて、量子アニーリングによる最適化処理で用いられるイジングモデルを作成するイジングモデル作成処理、
作成された前記イジングモデルを用いた最適化処理により前記最適化問題の近似解をサンプリングするサンプリング処理、および、
前記選択候補および前記解像度を更新する更新処理を実行させ、
前記イジングモデル作成処理で、更新された前記選択候補および前記解像度により規定される変数を用いて前記イジングモデルを更新させ、
前記サンプリング処理で、更新されたイジングモデルを用いてサンプリングさせる
ための最適化プログラム。

発明の詳細な説明【技術分野】
【０００１】
本発明は、組み合わせ最適化問題の解を探索する最適化装置、最適化方法および最適化プログラムに関する。
続きを表示（約 1,300 文字）【背景技術】
【０００２】
ポートフォリオや材料の開発においては、より好ましい結果を得るための組み合わせを試行錯誤することが行われている。例えば、インデックスポートフォリオの場合、ターゲットとするインデックス指標に対し、より少ない銘柄数で、できるだけ同じ値動きになる（追従できる）組み合わせが求められる。また、例えば、ゴム材料開発の場合、ある気象条件での弾性、耐久性を実現するような組成が求められる。
【０００３】
候補になる金融商品や素材が多数であると、その組合せ数は膨大になる。そのため、すべての組合せを試行することは不可能であり、近似的な計算で候補を絞り込むことさえも困難である。組合せの候補数に対して、組合せ数は指数的に増加することから、最適な組合せを求める問題はＮＰ（Non-deterministic Polynomial time ）困難として知られている。
【０００４】
例えば、特許文献１には、ポートフォリオの作成を支援するポートフォリオ作成支援装置が記載されている。特許文献１に記載された装置は、量子コンピュータ、特に量子アニーリング、疑似量子アニーリングの技術を使ってポートフォリオを作成する。
【０００５】
また、特許文献２には、非線形変数を含む混合整数計画問題として定式化された原料配合計画問題を解く方法が記載されている。特許文献２に記載された方法では、組合せ最適化問題を線形緩和やラグランジュ緩和する前処理が行われる。
【先行技術文献】
【特許文献】
【０００６】
特許第７１４１３６５号公報
特許第７０１０２５８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
各銘柄の組成を決定する場合、全銘柄数ＭからＮ個の銘柄を選択するのに、
Ｍ
Ｃ
Ｎ
の組合せ数がある。また、組成の割合は０～１００％の連続値であり、さらに顧客が希望するような銘柄属性（例えば、新興企業、業界、地域性など）を条件とすると、多大な計算量となってしまうため、一般的な方法で最適なポートフォリオ組成を求めることは困難である。
【０００８】
そのため、特許文献１に記載されたような量子コンピュータを利用することも考えられる。しかし、特許文献１に記載された装置では、大規模な組み合わせ最適化問題を扱うことができないため、詳細な組成の量を計算に含めない近似値計算にせざるを得なかった。
【０００９】
また、特許文献２に記載された方法では、制約条件を扱うことが難しく、複数の解を扱えずに、局所解に陥る可能性がある。また、特許文献２に記載された方法では、複数のアルゴリズムを実装するためにシステムが大きくなってしまい、構築コストや保守コストの面でも課題が残る。
【００１０】
一方、厳密な最適解でなくても、最適解に近い解（以下、近似解と記す。）で成果が得られる場合も存在する。このような状況では、組み合わせ最適化問題の最適解に近い解を高速に探索できることが好ましい。
（【００１１】以降は省略されています）

関連特許