特許ウォッチ

公開番号2025027344
公報種別公開特許公報(A)
公開日2025-02-27
出願番号2023132079
出願日2023-08-14
発明の名称プログラム、データ処理方法およびデータ処理装置
出願人富士通株式会社
代理人弁理士法人扶桑国際特許事務所
主分類G06N 99/00 20190101AFI20250219BHJP(計算;計数)
要約【課題】求解性能を向上すること。
【解決手段】処理部12は、複数の状態変数を含む評価関数に基づく解探索において、複数の状態変数のうちの何れかの状態変数の値が更新されると、当該更新の前の複数の状態変数の値から、複数の状態変数のうちの第1の状態変数の値が更新される場合の評価関数の値の変化量に関する第1の指標値を算出する。処理部12は、第1の状態変数の値が更新された後における第1の状態変数の値の更新を抑制する期間の長さを、第1の指標値に基づいて決定する。
【選択図】図1
特許請求の範囲【請求項１】
複数の状態変数を含む評価関数に基づく解探索において、前記複数の状態変数のうちの何れかの状態変数の値が更新されると、当該更新の前の前記複数の状態変数の値から、前記複数の状態変数のうちの第１の状態変数の値が更新される場合の前記評価関数の値の変化量に関する第１の指標値を算出し、
前記第１の状態変数の値が更新された後における前記第１の状態変数の値の更新を抑制する期間の長さを、前記第１の指標値に基づいて決定する、
処理をコンピュータに実行させるプログラム。
続きを表示（約 1,800 文字）【請求項２】
前記第１の指標値の算出では、今回の更新の前の前記複数の状態変数の値から前記第１の状態変数の値を更新する場合の前記変化量の絶対値を、今回の更新の前の前記複数の状態変数の値から何れかの前記状態変数の値を更新する場合の前記変化量の絶対値の最大値で割ることで、前記第１の指標値を算出する、
請求項１記載のプログラム。
【請求項３】
前記期間の長さの決定では、
前記第１の指標値が第１の閾値より小さい場合に、前記期間の長さを増加させ、
前記第１の指標値が、前記第１の閾値より大きい第２の閾値より大きい場合に、前記期間の長さを減少させ、
前記第１の指標値が前記第１の閾値以上かつ前記第２の閾値以下の場合に、前記期間の長さを変更しない、
請求項１記載のプログラム。
【請求項４】
前記第１の状態変数は、前記解探索において値が今回更新された前記状態変数である、
請求項１記載のプログラム。
【請求項５】
前記解探索における前記状態変数の値の更新が所定回数行われるたびに、前記複数の状態変数の各々を前記第１の状態変数として、前記第１の指標値の算出および前記期間の長さの決定を、前記第１の状態変数ごとに行う、
請求項１記載のプログラム。
【請求項６】
前記第１の指標値とともに、前記第１の状態変数の値の更新頻度に関する第２の指標値を算出し、
前記期間の長さの決定では、前記第１の指標値と前記第２の指標値とに基づいて前記期間の長さを決定する、
請求項１記載のプログラム。
【請求項７】
前記第１の状態変数は、前記解探索において値が今回更新された前記状態変数であり、
前記第２の指標値の算出では、前記第１の状態変数に対して設定済の前記期間の長さを、前記第１の状態変数の値が前回更新されてから今回更新されるまでの第１の時間間隔で割ることで、前記第２の指標値を算出する、
請求項６記載のプログラム。
【請求項８】
前記第１の状態変数は、前記解探索において値が今回更新された前記状態変数であり、
前記第２の指標値の算出では、
前記第１の状態変数に対応する前記期間の長さの決定の処理を行ってから、前記第１の状態変数の値を所定回数更新したか否かを判定し、
前記所定回数更新した場合、前記第１の状態変数に対して設定済の前記期間の長さに前記所定回数を乗じた値を、前記第１の状態変数の値が前記所定回数前に更新されてから今回更新されるまでの第２の時間間隔で割ることで、前記第２の指標値を算出する、
請求項６記載のプログラム。
【請求項９】
前記解探索における何れかの前記状態変数の値の更新が所定回数行われるたびに、前記複数の状態変数の各々を前記第１の状態変数として選択し、
前記第１の指標値の算出では、前記第１の指標値を前記第１の状態変数ごとに算出し、
前記第２の指標値の算出では、前記第１の状態変数に対応する前記期間の長さの決定を前回行ってから、前記第１の状態変数の値が更新された回数を、前記所定回数で割ることで、前記第２の指標値を前記第１の状態変数ごとに算出し、
前記期間の長さの決定では、前記第１の指標値と前記第２の指標値とに基づいて前記期間の長さを前記第１の状態変数ごとに決定する、
請求項６記載のプログラム。
【請求項１０】
前記期間の長さの決定では、
前記第１の指標値が第１の閾値より小さく、かつ、前記第２の指標値が第３の閾値より大きい場合に、前記期間の長さを増加させ、
前記第１の指標値が前記第１の閾値より大きい第２の閾値より大きく、かつ、前記第２の指標値が前記第３の閾値より小さい第４の閾値より小さい場合に、前記期間の長さを減少させ、
前記第１の指標値が前記第１の閾値以上かつ前記第２の閾値以下である場合、および、前記第２の指標値が前記第４の閾値以上かつ前記第３の閾値以下である場合の少なくとも一方の場合に、前記期間の長さを変更しない、
請求項６記載のプログラム。
（【請求項１１】以降は省略されています）
発明の詳細な説明【技術分野】
【０００１】
本発明はプログラム、データ処理方法およびデータ処理装置に関する。
続きを表示（約 1,300 文字）【背景技術】
【０００２】
組合せ最適化問題の求解に情報処理装置が用いられることがある。組合せ最適化問題は、例えば磁性体のスピンの振る舞いを表すモデルであるイジングモデルのエネルギーを表す評価関数により定式化される。
【０００３】
情報処理装置は、例えば評価関数に含まれる状態変数の値の組合せのうち、評価関数の値を最小化する組合せを探索する。この場合、評価関数の値を最小化する状態変数の値の組合せは、基底状態または最適解に相当する。実用的な時間で組合せ最適化問題の近似解を得る手法には、シミュレーテッドアニーリング（ＳＡ：Simulated Annealing）法やタブーサーチ（Tabu Search）法などがある。
【０００４】
例えば、電圧制御機器の電圧基準値やインピーダンスなどの最適整定値の候補の探索に、タブーサーチを用いる方法の提案がある。提案の方法では、過去の探索過程で求められた解や探索の移動パターンをタブーリストに記憶しておき、タブーリストに含まれない解の中から最良のものが選択される。提案の方法では、タブーリスト内の情報量が所定値を超えた場合、最も古い情報が除去される。
【０００５】
また、ＳＡ法やタブーサーチ法などを用いて、大規模な問題を複数のノードにより分散して解く情報処理システムの提案がある。
また、運搬経路問題（ＶＲＰ：Vehicle Routing Problem）の求解にタブーサーチ法を用いるシステムの提案がある。
【０００６】
更に、実現可能な空間のみを探索する特別なタブーサーチによって、目的関数に対する求解を行うシステムの提案がある。
【先行技術文献】
【特許文献】
【０００７】
特開２００３－２０９９２６号公報
特開２０２２－１６４１６２号公報
米国特許出願公開第２０１０／００８８１４６号明細書
米国特許出願公開第２０１４／０３４４３２２号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００８】
上記のように評価関数に基づく解探索では、ある状態変数の値を更新した後に当該状態変数の値の更新を一定の期間、抑制するように制御することがある。この場合、当該期間の長さが不適切であると、求解性能の向上を十分に図れないという問題がある。
【０００９】
１つの側面では、本発明は、求解性能の向上を目的とする。
【課題を解決するための手段】
【００１０】
１つの態様では、プログラムが提供される。このプログラムは、コンピュータに次の処理を実行させる。コンピュータは、複数の状態変数を含む評価関数に基づく解探索において、複数の状態変数のうちの何れかの状態変数の値が更新されると、当該更新の前の複数の状態変数の値から、複数の状態変数のうちの第１の状態変数の値が更新される場合の評価関数の値の変化量に関する第１の指標値を算出する。コンピュータは、第１の状態変数の値が更新された後における第１の状態変数の値の更新を抑制する期間の長さを、第１の指標値に基づいて決定する。
（【００１１】以降は省略されています）

関連特許