特許ウォッチ

公開番号2025140504
公報種別公開特許公報(A)
公開日2025-09-29
出願番号2024039942
出願日2024-03-14
発明の名称組合せ最適化方法、組合せ最適化装置、及びプログラム
出願人NTT株式会社,学校法人早稲田大学
代理人個人,個人,個人
主分類G06N 99/00 20190101AFI20250919BHJP(計算;計数)
要約【課題】従来の組合せ最適化装置では、質の高い実行可能解が得られなかった。
【解決手段】上記課題を解決する組合せ最適化装置は、変換部と、イジングマシンと、修復処理部と、改善処理部とを備える。変換部は、制約付き組合せ問題を、目的関数とペナルティ関数とペナルティ係数とからなるイジングモデルに変換する。イジングマシンは、イジングモデルを解いて暫定解を生成する。暫定解が制約を満たさない場合、修復処理部は、制約が満たされるように暫定解を補正して実行可能解を生成する。改善処理部は、制約が満たされるように、または制約を満たしかつ目的関数の値が改善されるように、実行可能解を補正して改善解を生成する。
【選択図】図3
特許請求の範囲【請求項１】
制約付き組合せ問題の最適解を求める方法であって、
変換部が前記制約付き組合せ問題を目的関数とペナルティ関数とペナルティ係数とからなるイジングモデルに変換し、
イジングマシンが、前記イジングモデルを解いて暫定解を生成し、
前記暫定解が前記制約を満たさない場合、修復処理部が、前記制約が満たされるように前記暫定解を補正して実行可能解を生成し、
改善処理部が、前記制約が満たされるように、または前記制約を満たしかつ目的関数の値が改善されるように、前記実行可能解を補正して改善解を生成する
組合せ最適化方法。
続きを表示（約 1,600 文字）【請求項２】
請求項１に記載の組合せ最適化方法であって、
前記目的関数の変数を、前記目的関数への寄与が小さく前記制約への負荷が大きい順に並べた順番を昇順として、
前記修復処理部は、前記暫定解において値が１の変数の中から前記昇順に基づいて選択した変数の値を０に補正して前記実行可能解を求める
ことを特徴とする組合せ最適化方法。
【請求項３】
請求項１に記載の組合せ最適化方法であって、
前記目的関数の変数を、前記目的関数への寄与が大きく前記制約への負荷が小さい順に並べた順番を降順として、
前記改善処理部は、前記実行可能解において値が０の変数の中から前記降順に基づいて選択した変数の値を１に補正して前記改善解を求める
ことを特徴とする組合せ最適化方法。
【請求項４】
請求項１に記載の組合せ最適化方法であって、
前記目的関数の変数を、前記目的関数への寄与が小さく前記制約への負荷が大きい順に並べた順番を昇順、前記目的関数への寄与が大きく前記制約への負荷が小さい順に並べた順番を降順として、
前記改善処理部は、前記実行可能解において値が１の変数の中から前記昇順に基づいて選択した変数の値を０に補正すると共に、前記実行可能解において値が０の変数の中から前記降順に基づいて選択した変数の値を１に補正して前記実行可能解を求める
ことを特徴とする組合せ最適化方法。
【請求項５】
制約付き組合せ問題の最適解を求める装置であって、
前記制約付き組合せ問題を目的関数とペナルティ関数とペナルティ係数とからなるイジングモデルに変換する変換部と、
前記イジングモデルを解いて暫定解を生成するイジングマシンと、
前記暫定解が前記制約を満たさない場合、前記制約が満たされるように前記暫定解を補正して実行可能解を生成する修復処理部と、
改善処理部が、前記制約が満たされるように、または前記制約を満たしかつ目的関数の値が改善されるように、前記実行可能解を補正して改善解を生成する改善処理部と、
を備えた組合せ最適化装置。
【請求項６】
請求項５に記載の組合せ最適化装置であって、
前記目的関数の変数を、前記目的関数への寄与が小さく前記制約への負荷が大きい順に並べた順番を昇順として、
前記修復処理部は、前記暫定解において値が１の変数の中から前記昇順に基づいて選択した変数の値を０に補正して前記実行可能解を求める
ことを特徴とする組合せ最適化装置。
【請求項７】
請求項５に記載の組合せ最適化方法であって、
前記目的関数の変数を、前記目的関数への寄与が大きく前記制約への負荷が小さい順に並べた順番を降順として、
前記改善処理部は、前記実行可能解において値が０の変数の中から前記降順に基づいて選択した変数の値を１に補正して前記改善解を求める
ことを特徴とする組合せ最適化装置。
【請求項８】
請求項５に記載の組合せ最適化方法であって、
前記目的関数の変数を、前記目的関数への寄与が小さく前記制約への負荷が大きい順に並べた順番を昇順、前記目的関数への寄与が大きく前記制約への負荷が小さい順に並べた順番を降順として、
前記改善処理部は、前記実行可能解において値が１の変数の中から前記昇順に基づいて選択した変数の値を０に補正すると共に、前記実行可能解において値が０の変数の中から前記降順に基づいて選択した変数の値を１に補正して前記実行可能解を求める
ことを特徴とする組合せ最適化装置。
【請求項９】
請求項５から８のいずれかに記載の組合せ最適化装置としてコンピュータを機能させるためのプログラム。

発明の詳細な説明【技術分野】
【０００１】
開示技術は、イジングマシンと呼ばれる計算機を用いて組合せ最適化問題を解く技術に関する。特に、制約付き最適化問題において、質の高い実行可能解を得るための技術に関する。
続きを表示（約 2,300 文字）【背景技術】
【０００２】
組合せ最適化は、特定の条件を満たす多数の組合せの中から特定の評価指標（目的関数）についてできるだけ良いもの、すなわち質の高い解を選択する技術である。組合せ最適化は、人員計画、経路探索、創薬といったビジネスでの意思決定から学術的な研究まで広い分野で現れる。
一方、組合せ最適化問題を効率的に（問題サイズに対して多項式時間で）解くことは従来の汎用計算機では難しい。そのため、物理現象などを利用し、最適解の探索を行う計算機ハードウェアを用いて高速に組合せ最適化を実行する技術が重要となっている。
【０００３】
組合せ最適化における発見的解法を実装した（従来の汎用計算機とは異なる種類の）計算機としてイジングマシンがある。イジングマシンは、イジングモデルの基底状態探索を効率的に実行するハードウェアである。イジングモデルとは、+1または-1の二値をとる複数の変数(スピン)に関する2次多項式(ハミルトニアン)により定義される物理モデルである。スピンの値の組み合わせを状態と呼び、状態に対して各スピンの値をハミルトニアンに代入した値をエネルギーと呼ぶ。エネルギーを最小化するような状態を基底状態と呼ぶ。イジングマシンは、入力されたハミルトニアンに対してエネルギーが低い解を出力するアルゴリズムが実装された計算機の総称である。
【０００４】
イジングマシンはその定義から、組合せ最適化に応用される。イジングマシンの実現方法には、量子プロセッサ（量子力学の原理を用いた計算プロセッサ）や縮退光パラメトリック発振器を用いたもの、従来の半導体技術を用いた専用集積回路を用いたものなどがある。
【０００５】
なお、イジングモデルにおけるスピンを、0あるいは1のいずれかの値をとるバイナリ変数で置き換えたモデルをQUBOモデルと呼ぶ。スピン変数をσ
i
∈{+1, -1}、バイナリ変数をq
i
∈{0, 1}として、イジングモデルとQUBOモデルは次の式で相互に変換可能であり、等価である。
TIFF
2025140504000002.tif
20
169
組合せ最適化問題の定式化に、イジングモデルを用いるかQUBOモデルを用いるかは、組合せ問題の性質に応じて、使い分ければよい。
【０００６】
イジングマシンを用いた一般的な組合せ最適化装置を図１に示す。
組合せ最適化装置１０は、QUBO変換部１０１、イジングマシン１０２、逆変換部１０３、評価部１０４、ペナルティ係数更新部１０５を備え、組合せ最適化問題を入力とし、最適解を出力とする。
【０００７】
図２は、組合せ最適化装置１０の作用を説明するフローチャートである。
以下、図１と図２を用いて従来技術を説明する。ここでは、「制約付き組合せ最適化問題」を解く場合について説明する。
ユーザが組合せ最適化問題を入力すると（ステップＳ２０１）、QUBO変換部１０１がQUBOモデルに変換する（ステップＳ２０２）。このとき、元の問題の変数は(場合によっては複数の)バイナリ変数に変換される。
問題が「制約付き組合せ最適化問題」だった場合、QUBOモデルは、目的関数と、ペナルティ関数とペナルティ係数とからなる（詳しくは後述）。
ペナルティ係数更新部１０６は、ペナルティ係数を初期化する（ステップＳ２０３）。
【０００８】
イジングマシン１０２は、QUBOモデルを解いて、暫定解を出力する（ステップＳ２０４）。
逆変換部１０３は、暫定解の変数（QUBOモデルの変数）の値を、元の組合せ最適化問題の変数の値（原始解）に変換する（ステップＳ２０５）。
評価部１０４は、原始解が終了条件を満足するか否か判定する（ステップＳ２０６）。具体的には、原始解が制約を満たすか否か（原始解は実行可能解であるか否か）、実行可能解の出力確率が一定以上を達成したか、イジングマシンの実行回数が一定回数に到達したか、などを判定する。
【０００９】
終了条件を満足していない場合（ステップＳ２０６でＮｏ）、ペナルティ係数更新部１０５は、制約が満たされるように、あるいは実行可能解の出力確率がより高くなるようにペナルティ係数を更新する（ステップＳ２０７）。
イジングマシン１０２は、ペナルティ係数が更新されたQUBOモデルを解く（ステップＳ２０４）。
終了条件を満足していれば（ステップＳ２０６でＹｅｓ）、原始解を、最適化問題の解として出力する。
【００１０】
組合せ最適化問題の入力時におけるイジングモデルへの変換とペナルティ係数について補足する。
イジングモデルの基底状態探索は、二値に値をとる変数上の制約なし最小化問題とみなせる。したがって、組合せ最適化問題を二値変数で表現した際に生じる制約は、実行不能解に対しては正の値を返し、実行可能解に対してはゼロを返す関数（ペナルティ関数と呼ぶ）に変換する。目的関数にペナルティ関数の正の定数（ペナルティ係数と呼ぶ）倍を足したものを新たな目的関数とすることで、制約を除去した問題に変換し、イジングモデル／QUBOモデルに変換する。本明細書の段落［００４１］に具体例を示した。
（【００１１】以降は省略されています）

関連特許