特許ウォッチ

公開番号2024167845
公報種別公開特許公報(A)
公開日2024-12-04
出願番号2023084203
出願日2023-05-22
発明の名称プログラム、データ処理装置及びデータ処理方法
出願人富士通株式会社
代理人弁理士法人扶桑国際特許事務所
主分類G06N 99/00 20190101AFI20241127BHJP(計算;計数)
要約【課題】制約条件をもつ組合せ最適化問題の計算量を削減する。
【解決手段】処理部12は、評価関数情報11aに基づいて、複数の制約項のそれぞれに対して、複数の制約項のそれぞれに関する制約を受ける入力量を表す第1補助変数(y_k)の値を特定し、y_kの値に基づいて、y_kを量子化した第2補助変数(z_k)の値を生成し、複数の制約項のうちの、評価関数の複数の状態変数のうちの第1状態変数(x_i)の値の変化に伴いz_kの値が変化する第1制約項について、x_iの値の変化に伴う評価関数の値の第1変化量(ΔH_i)に対する第1制約項の寄与量(g_i ^(k))の、x_iの値の変化に伴う第1差分値(Δg_i ^(k))を算出し、Δg_i ^(k)を用いてΔH_iの算出、またはΔg_i ^(k)を用いて、複数の状態変数のそれぞれの変化に伴う評価関数の値の第2変化量の特定に用いられる局所場の更新を行う。
【選択図】図1
特許請求の範囲【請求項１】
コスト項と複数の制約項を含む組合せ最適化問題の評価関数の評価関数情報を記憶部から取得し、
前記評価関数情報に基づいて、前記複数の制約項のそれぞれに対して、前記複数の制約項のそれぞれに関する制約を受ける入力量を表す第１補助変数の値を特定し、
前記第１補助変数の値に基づいて、前記第１補助変数を量子化した第２補助変数の値を生成し、
前記複数の制約項のうちの、前記評価関数の複数の状態変数のうちの第１状態変数の値の変化に伴い前記第２補助変数の値が変化する第１制約項について、前記第１状態変数の値の変化に伴う前記評価関数の値の第１変化量に対する前記第１制約項の寄与量の、前記第１状態変数の値の変化に伴う第１差分値を算出し、
前記第１差分値を用いて前記第１変化量の算出、または前記第１差分値を用いて、前記複数の状態変数のそれぞれの変化に伴う前記評価関数の値の第２変化量の特定に用いられる局所場の更新を行う、
処理をコンピュータに実行させるプログラム。
続きを表示（約 1,500 文字）【請求項２】
前記第１状態変数の値の変化に伴う前記コスト項の第３変化量と、前記第１差分値から得られる前記第１制約項の第４変化量と、を加算することで、前記第１変化量を算出し、
前記第１変化量と閾値との比較結果に基づいて、前記第１状態変数の値の変化を許容するか否かを判定し、
前記第１状態変数の値の変化を許容すると判定した場合、前記第１状態変数の値を更新する、
処理を前記コンピュータに実行させる請求項１に記載のプログラム。
【請求項３】
前記局所場を保持し、
前記第１状態変数の値の変化が許容された場合、前記複数の状態変数のそれぞれに対する前記局所場に、前記第１差分値を加えることで、前記局所場を更新する、
処理を前記コンピュータに実行させる請求項１に記載のプログラム。
【請求項４】
前記第２補助変数は、前記第１補助変数の値が正であるか負であるか０であるかを示す３値の値である、請求項１に記載のプログラム。
【請求項５】
前記第１状態変数の値の変化に伴う、前記第２補助変数の値の第２差分値を算出し、
前記第２差分値と、前記第１状態変数の値と、前記第１状態変数と前記第１制約項との間の重み値と、に基づいて前記第１差分値を算出する、
処理を前記コンピュータに実行させる請求項１に記載のプログラム。
【請求項６】
コスト項と複数の制約項を含む組合せ最適化問題の評価関数の評価関数情報を記憶する記憶部と、
前記評価関数情報を記憶部から取得し、前記評価関数情報に基づいて、前記複数の制約項のそれぞれに対して、前記複数の制約項のそれぞれに関する制約を受ける入力量を表す第１補助変数の値を特定し、前記第１補助変数の値に基づいて、前記第１補助変数を量子化した第２補助変数の値を生成し、前記複数の制約項のうちの、前記評価関数の複数の状態変数のうちの第１状態変数の値の変化に伴い前記第２補助変数の値が変化する第１制約項について、前記第１状態変数の値の変化に伴う前記評価関数の値の第１変化量に対する前記第１制約項の寄与量の、前記第１状態変数の値の変化に伴う第１差分値を算出し、前記第１差分値を用いて前記第１変化量の算出、または前記第１差分値を用いて、前記複数の状態変数のそれぞれの変化に伴う前記評価関数の値の第２変化量の特定に用いられる局所場の更新を行う処理部と、
を有するデータ処理装置。
【請求項７】
コンピュータが、
コスト項と複数の制約項を含む組合せ最適化問題の評価関数の評価関数情報を記憶部から取得し、
前記評価関数情報に基づいて、前記複数の制約項のそれぞれに対して、前記複数の制約項のそれぞれに関する制約を受ける入力量を表す第１補助変数の値を特定し、
前記第１補助変数の値に基づいて、前記第１補助変数を量子化した第２補助変数の値を生成し、
前記複数の制約項のうちの、前記評価関数の複数の状態変数のうちの第１状態変数の値の変化に伴い前記第２補助変数の値が変化する第１制約項について、前記第１状態変数の値の変化に伴う前記評価関数の値の第１変化量に対する前記第１制約項の寄与量の、前記第１状態変数の値の変化に伴う第１差分値を算出し、
前記第１差分値を用いて前記第１変化量の算出、または前記第１差分値を用いて、前記複数の状態変数のそれぞれの変化に伴う前記評価関数の値の第２変化量の特定に用いられる局所場の更新を行う、
データ処理方法。

発明の詳細な説明【技術分野】
【０００１】
本発明は、プログラム、データ処理装置及びデータ処理方法に関する。
続きを表示（約 830 文字）【背景技術】
【０００２】
組合せ最適化問題には解が満たすべき制約条件をもつものがあり、制約条件を考慮した探索を行う手法が提案されている（たとえば、特許文献１～３参照）。制約条件には、不等式制約、等式制約、絶対値制約などがある。制約条件を反映した評価関数は、以下の式（１）で表せる。
【０００３】
TIFF
2024167845000002.tif
10
142
【０００４】
式（１）の右辺の第１項目はコスト項であり、右辺の２項目は複数の制約項の合計値である。複数の制約項の合計値は、以下の式（２）で表せる。
【０００５】
TIFF
2024167845000003.tif
17
142
【０００６】
式（２）において、Ｐ
ｋ
（ｘ）は識別番号がｋの制約に関する制約項のペナルティ関数である。Ｐ
ｋ
（ｘ）は、非線形な関数で表される。ｍは制約項の総数を表す。また、λ
ｋ
は識別番号がｋの制約についての所定の係数（以下制約係数と呼ぶ）である。以下では、λ
ｋ
Ｐ
ｋ
（ｘ）を制約項という。
【０００７】
制約条件が不等式制約である場合、式（２）のＰ
ｋ
（ｘ）は、以下の式（３）で表すことができる。
【０００８】
TIFF
2024167845000004.tif
17
142
【０００９】
制約条件が等式制約である場合、式（２）のＰ
ｋ
（ｘ）は、以下の式（４）で表すことができる。
【００１０】
TIFF
2024167845000005.tif
13
142
（【００１１】以降は省略されています）

関連特許