特許ウォッチ

公開番号2025022329
公報種別公開特許公報(A)
公開日2025-02-14
出願番号2023126778
出願日2023-08-03
発明の名称最適化装置、最適化方法および最適化プログラム
出願人日本電気株式会社
代理人個人,個人
主分類G06N 10/60 20220101AFI20250206BHJP(計算;計数)
要約【課題】アニーリングを用いた最適化において段階的な最適解を得ることができる最適化装置を提供する。
【解決手段】最適化装置80は、アニーリング手段81を備えている。アニーリング手段81は、n回目の求解において、n-1回目までの求解で得られた最適解を示すスピンの組との距離が所定の範囲内のスピンの組を、探索範囲から除外するように求解を実行する。
【選択図】図14
特許請求の範囲【請求項１】
組み合わせ最適化問題をアニーリングにより解く最適化装置であって、
アニーリングによる求解を複数回実行するアニーリング手段を備え、
前記アニーリング手段は、ｎ回目の求解において、ｎ－１回目までの求解で得られた最適解を示すスピンの組との距離が所定の範囲内のスピンの組を、探索範囲から除外するように求解を実行する
ことを特徴とする最適化装置。
続きを表示（約 2,100 文字）【請求項２】
複数回の求解により得られた最適解を、当該最適解が得られた順に出力する出力手段を備えた
請求項１記載の最適化装置。
【請求項３】
アニーリング手段は、過去のｎ－１回目までの求解において既に得られた最適解を示すスピンの組との距離が所定の範囲内の解が選ばれた場合にペナルティが与えられる制約式を追加したハミルトニアンを用いて、ｎ回目の求解を実行する
請求項１または請求項２記載の最適化装置。
【請求項４】
組み合わせ最適化問題をアニーリングにより解く最適化装置であって、
アニーリングによる求解を複数回実行するアニーリング手段と、
スピンの組を説明変数とし、当該スピンの組をブラックボックス最適化問題を表わすブラックボックス関数に適用して得られる値を目的変数とする学習データを用いた機械学習により、スピンの多項式で表わされた目的関数モデルを学習する学習手段とを備え、
前記アニーリング手段は、前記目的関数モデルを含むハミルトニアンを用いて前記アニーリングによる求解を実行し、前記目的関数モデルの学習と前記アニーリングによる求解とを繰り返し行う最適化計算を複数回行い、
前記アニーリング手段は、ｎ回目の前記最適化計算において、ｎ－１回目までの前記最適化計算で得られた最良解を示すスピンの組との距離が所定の範囲内のスピンの組を、探索範囲から除外するように前記アニーリングによる求解を実行する
ことを特徴とする最適化装置。
【請求項５】
学習手段は、アニーリングによる求解で得られた解を前記ブラックボックス関数に適用して新たな学習データを作成し、生成された学習データを用いた機械学習により目的関数モデルを学習する
請求項４記載の最適化装置。
【請求項６】
アニーリング手段は、ｎ回目の最適化計算において、ｎ－１回目までの最適化計算で得られた最良解を示すスピンの組との距離が所定の範囲内の解が選ばれた場合にペナルティが与えられる制約式を追加したハミルトニアンを用いて、求解を実行する
請求項４または請求項５記載の最適化装置。
【請求項７】
組み合わせ最適化問題をアニーリングにより解く最適化方法であって、
アニーリングによる求解を複数回実行し、
前記アニーリングの際、ｎ回目の求解において、ｎ－１回目までの求解で得られた最適解を示すスピンの組との距離が所定の範囲内のスピンの組を、探索範囲から除外するように求解を実行する
ことを特徴とする最適化方法。
【請求項８】
組み合わせ最適化問題をアニーリングにより解く最適化方法であって、
スピンの組を説明変数とし、当該スピンの組をブラックボックス最適化問題を表わすブラックボックス関数に適用して得られる値を目的変数とする学習データを用いた機械学習により、スピンの多項式で表わされた目的関数モデルを学習し、
前記目的関数モデルを含む目的関数を用いてアニーリングによる求解を実行し、
前記目的機関数モデルの学習と前記アニーリングによる求解とを繰り返し行う最適化計算を複数回行い、
ｎ回目の前記最適化計算において、ｎ－１回目までの前記最適化計算で得られた最良解を示すスピンの組との距離が所定の範囲内のスピンの組を、探索範囲から除外するように前記アニーリングによる求解を実行する
ことを特徴とする最適化方法。
【請求項９】
組み合わせ最適化問題をアニーリングにより解くコンピュータに適用される最適化プログラムであって、
前記コンピュータに、
アニーリングによる求解を複数回実行するアニーリング処理を実行させ、
前記アニーリング処理で、ｎ回目の求解において、ｎ－１回目までの求解で得られた最適解を示すスピンの組との距離が所定の範囲内のスピンの組を、探索範囲から除外するように求解を実行させる
ための最適化プログラム。
【請求項１０】
組み合わせ最適化問題をアニーリングにより解くコンピュータに適用される最適化プログラムであって、
前記コンピュータに、
アニーリングによる求解を複数回実行するアニーリング処理、および、
スピンの組を説明変数とし、当該スピンの組をブラックボックス最適化問題を表わすブラックボックス関数に適用して得られる値を目的変数とする学習データを用いた機械学習により、スピンの多項式で表わされた目的関数モデルを学習する学習処理を実行させ、
前記アニーリング処理で、前記目的関数モデルを含む目的関数を用いて前記アニーリングによる求解を実行させ、前記目的関数モデルの学習と前記アニーリングによる求解とを繰り返し行う最適化計算を複数回行わせ、
前記アニーリング処理で、ｎ回目の前記最適化計算において、ｎ－１回目までの前記最適化計算で得られた最良解を示すスピンの組との距離が所定の範囲内のスピンの組を、探索範囲から除外するように前記アニーリングによる求解を実行させる
ための最適化プログラム。

発明の詳細な説明【技術分野】
【０００１】
本開示は、組み合わせ最適化問題をアニーリングにより解く最適化装置、最適化方法および最適化プログラムに関する。
続きを表示（約 2,500 文字）【背景技術】
【０００２】
組み合わせ最適化問題における目的関数の最適値を、量子アニーリングを用いて求めることが一般に行われている。例えば、特許文献１には、回帰モデルを構築する情報処理装置が記載されている。特許文献１に記載された情報処理装置では、最適解演算部が、量子アニーリングを用いて回帰モデルから最適解を求める。
【０００３】
なお、非特許文献１には、放射冷却材料の所望の放射強度を与える素材の配置を決定する方法として、ブラックボックス最適化問題に量子アニーリングを用いる方法が記載されている。
【先行技術文献】
【特許文献】
【０００４】
特開２０２２－００３４８４号公報
【非特許文献】
【０００５】
Koki Kitai, et. al., "Designing metamaterials with quantum annealing and factorization machines", PHYSICAL REVIEW RESEARCH 2, 013319 (2020)
【発明の概要】
【発明が解決しようとする課題】
【０００６】
一方、用途によっては、目的関数の最適値が得られる最適解だけでなく、次善の最適解、さらに次善の最適解のように、段階的に最適解が要求される場合がある。しかし、そのような段階的な最適解を得ることは一般には困難である。
【０００７】
そこで、本開示では、アニーリングを用いた最適化において段階的な最適解を得ることができる最適化装置、最適化方法および最適化プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
本開示による最適化装置は、組み合わせ最適化問題をアニーリングにより解く最適化装置であって、アニーリングによる求解を複数回実行するアニーリング手段を備え、アニーリング手段が、ｎ回目の求解において、ｎ－１回目までの求解で得られた最適解を示すスピンの組との距離が所定の範囲内のスピンの組を、探索範囲から除外するように求解を実行することを特徴とする。また、本開示による他の最適化装置は、組み合わせ最適化問題をアニーリングにより解く最適化装置であって、アニーリングによる求解を複数回実行するアニーリング手段と、スピンの組を説明変数とし、そのスピンの組をブラックボックス最適化問題を表わすブラックボックス関数に適用して得られる値を目的変数とする学習データを用いた機械学習により、スピンの多項式で表わされた目的関数モデルを学習する学習手段とを備え、アニーリング手段が、目的関数モデルを含むハミルトニアンを用いてアニーリングによる求解を実行し、目的関数モデルの学習とアニーリングによる求解とを繰り返し行う最適化計算を複数回行い、アニーリング手段が、ｎ回目の最適化計算において、ｎ－１回目までの最適化計算で得られた最良解を示すスピンの組との距離が所定の範囲内のスピンの組を、探索範囲から除外するようにアニーリングによる求解を実行することを特徴とする。
【０００９】
本開示による最適化方法は、組み合わせ最適化問題をアニーリングにより解く最適化方法であって、アニーリングによる求解を複数回実行し、アニーリングの際、ｎ回目の求解において、ｎ－１回目までの求解で得られた最適解を示すスピンの組との距離が所定の範囲内のスピンの組を、探索範囲から除外するように求解を実行することを特徴とする。また、本開示による他の最適化方法は、組み合わせ最適化問題をアニーリングにより解く最適化方法であって、スピンの組を説明変数とし、そのスピンの組をブラックボックス最適化問題を表わすブラックボックス関数に適用して得られる値を目的変数とする学習データを用いた機械学習により、スピンの多項式で表わされた目的関数モデルを学習し、目的関数モデルを含む目的関数を用いてアニーリングによる求解を実行し、目的機関数モデルの学習とアニーリングによる求解とを繰り返し行う最適化計算を複数回行い、ｎ回目の最適化計算において、ｎ－１回目までの最適化計算で得られた最良解を示すスピンの組との距離が所定の範囲内のスピンの組を、探索範囲から除外するようにアニーリングによる求解を実行することを特徴とする。
【００１０】
本開示による最適化プログラムは、組み合わせ最適化問題をアニーリングにより解くコンピュータに適用される最適化プログラムであって、コンピュータに、アニーリングによる求解を複数回実行するアニーリング処理を実行させ、アニーリング処理で、ｎ回目の求解において、ｎ－１回目までの求解で得られた最適解を示すスピンの組との距離が所定の範囲内のスピンの組を、探索範囲から除外するように求解を実行させることを特徴とする。また、本開示による他の最適化プログラムは、組み合わせ最適化問題をアニーリングにより解くコンピュータに適用される最適化プログラムであって、コンピュータに、アニーリングによる求解を複数回実行するアニーリング処理、および、スピンの組を説明変数とし、そのスピンの組をブラックボックス最適化問題を表わすブラックボックス関数に適用して得られる値を目的変数とする学習データを用いた機械学習により、スピンの多項式で表わされた目的関数モデルを学習する学習処理を実行させ、アニーリング処理で、目的関数モデルを含む目的関数を用いてアニーリングによる求解を実行させ、目的関数モデルの学習とアニーリングによる求解とを繰り返し行う最適化計算を複数回行わせ、アニーリング処理で、ｎ回目の最適化計算において、ｎ－１回目までの最適化計算で得られた最良解を示すスピンの組との距離が所定の範囲内のスピンの組を、探索範囲から除外するようにアニーリングによる求解を実行させることを特徴とする。
【発明の効果】
（【００１１】以降は省略されています）

関連特許