特許ウォッチ

公開番号2025019421
公報種別公開特許公報(A)
公開日2025-02-07
出願番号2023123028
出願日2023-07-28
発明の名称データ処理装置、データ処理プログラム及びデータ処理方法
出願人富士通株式会社
代理人弁理士法人扶桑国際特許事務所
主分類G06N 99/00 20190101AFI20250131BHJP(計算;計数)
要約【課題】制約条件をもつ組合せ最適化問題の解探索を行う複数ビット遷移処理の実装を実現する。
【解決手段】遷移候補決定回路13は、第1時点における第1局所場の値を用いて算出した、複数の状態変数のそれぞれの値の変化に伴う評価関数の値の変化量に基づいて、複数の状態変数のうち値を変化させる候補を1つずつ決定する。更新回路14は、候補が決定されるたびに候補の値と、第1局所場の値及び、制約違反量の特定に用いられる第2局所場の値を更新し、第2時点において、第2局所場の第1、第2時点の値を用いて、第1局所場の値をさらに更新する。判定回路16は、候補の値を変化させたときの変化量の累積値に基づいて、2以上の第1の数の候補の値の変化を受け入れるか否かを判定し、変化を受け入れないと判定された場合、制御回路17は、複数の状態変数の値、第1及び第2局所場の値をそれぞれ、第1時点における値に戻す。
【選択図】図3
特許請求の範囲【請求項１】
制約条件をもつ組合せ最適化問題の評価関数に含まれる複数の状態変数の第１時点の値と、前記複数の状態変数のそれぞれの値の変化に伴う前記評価関数の値の変化量の特定に用いられる第１局所場の前記第１時点の値と、前記制約条件が満たされないときに前記評価関数の値に加算される制約違反量の特定に用いられる第２局所場の前記第１時点の値と、を記憶するメモリと、
前記第１時点における前記第１局所場の値を用いて前記変化量を算出するとともに、前記変化量に基づいて、前記複数の状態変数のうち値を変化させる候補を１つずつ決定する遷移候補決定回路と、
前記候補が決定されるたびに前記候補の値と、前記第１局所場及び前記第２局所場の値を更新し、第２時点において、前記第２局所場の前記第１時点の値及び前記第２時点の値を用いて、前記第１局所場の値をさらに更新する更新回路と、
前記候補の値を変化させたときの前記変化量の累積値を算出する累積値算出回路と、
前記累積値に基づいて、２以上の第１の数の前記候補の値の変化を受け入れるか否かを判定する判定回路と、
前記判定回路が前記第１の数の前記候補の値の変化を受け入れないと判定した場合、前記複数の状態変数の値、前記第１局所場の値、及び前記第２局所場の値をそれぞれ、前記第１時点における値に戻す制御回路と、
を有するデータ処理装置。
続きを表示（約 1,900 文字）【請求項２】
前記制御回路は、前記遷移候補決定回路に、前記変化量に基づいて前記複数の状態変数のそれぞれの値の変化を許容するか否かを判定する第１処理をさせるか、前記候補を１つずつ決定する第２処理をさせるかを切り替え、
前記第１時点は、前記第２処理が開始する時点である、
請求項１に記載のデータ処理装置。
【請求項３】
前記第２時点は、前記候補が複数回決定された時点である、請求項１に記載のデータ処理装置。
【請求項４】
前記メモリは、前記複数の状態変数の値と前記第１局所場及び前記第２局所場の値を、複数のレプリカの数分記憶し、
前記制御回路は、前記遷移候補決定回路と、前記更新回路と、前記累積値算出回路と、前記判定回路に、前記複数のレプリカに対するパイプライン処理を行わせる、
請求項１に記載のデータ処理装置。
【請求項５】
前記遷移候補決定回路は、複数のモジュールを含み、前記複数のモジュールは、前記複数の状態変数のうち互いに異なる状態変数群の範囲内で、前記候補を１つずつ前記第１の数、決定し、
前記更新回路は、前記複数のモジュールのそれぞれに対応する、前記状態変数群の値、前記第１局所場及び前記第２局所場の値を、前記複数のモジュールのそれぞれが決定した前記候補にしたがって更新し、
前記累積値算出回路は、前記複数のモジュールのそれぞれに対して前記累積値を算出するとともに、前記複数のモジュールのそれぞれに対して算出した前記累積値のうちの１つを選択し、
前記判定回路は、選択された前記累積値に基づいて、選択された前記累積値に対応した前記第１の数の前記候補の値の変化を受け入れるか否かを判定する、
請求項１に記載のデータ処理装置。
【請求項６】
制約条件をもつ組合せ最適化問題の評価関数に含まれる複数の状態変数の第１時点の値と、前記複数の状態変数のそれぞれの値の変化に伴う前記評価関数の値の変化量の特定に用いられる第１局所場の前記第１時点の値と、前記制約条件が満たされないときに前記評価関数の値に加算される制約違反量の特定に用いられる第２局所場の前記第１時点の値と、をメモリに記憶し、
前記第１時点における前記第１局所場の値を用いて前記変化量を算出するとともに、前記変化量に基づいて、前記複数の状態変数のうち値を変化させる候補を１つずつ決定し、
前記候補が決定されるたびに前記候補の値と、前記第１局所場及び前記第２局所場の値を更新し、第２時点において、前記第２局所場の前記第１時点の値及び前記第２時点の値を用いて、前記第１局所場の値をさらに更新し、
前記候補の値を変化させたときの前記変化量の累積値を算出し、
前記累積値に基づいて、２以上の第１の数の前記候補の値の変化を受け入れるか否かを判定し、
前記第１の数の前記候補の値の変化を受け入れないと判定した場合、前記複数の状態変数の値、前記第１局所場の値、及び前記第２局所場の値をそれぞれ、前記第１時点における値に戻す、
処理をコンピュータに実行させるデータ処理プログラム。
【請求項７】
メモリが、制約条件をもつ組合せ最適化問題の評価関数に含まれる複数の状態変数の第１時点の値と、前記複数の状態変数のそれぞれの値の変化に伴う前記評価関数の値の変化量の特定に用いられる第１局所場の前記第１時点の値と、前記制約条件が満たされないときに前記評価関数の値に加算される制約違反量の特定に用いられる第２局所場の前記第１時点の値と、を記憶し、
遷移候補決定回路が、前記第１時点における前記第１局所場の値を用いて前記変化量を算出するとともに、前記変化量に基づいて、前記複数の状態変数のうち値を変化させる候補を１つずつ決定し、
更新回路が、前記候補が決定されるたびに前記候補の値と、前記第１局所場及び前記第２局所場の値を更新し、第２時点において、前記第２局所場の前記第１時点の値及び前記第２時点の値を用いて、前記第１局所場の値をさらに更新し、
累積値算出回路が、前記候補の値を変化させたときの前記変化量の累積値を算出し、
判定回路が、前記累積値に基づいて、２以上の第１の数の前記候補の値の変化を受け入れるか否かを判定し、
制御回路が、前記判定回路が前記第１の数の前記候補の値の変化を受け入れないと判定した場合、前記複数の状態変数の値、前記第１局所場の値、及び前記第２局所場の値をそれぞれ、前記第１時点における値に戻す、
データ処理方法。

発明の詳細な説明【技術分野】
【０００１】
本発明は、データ処理装置、データ処理プログラム及びデータ処理方法に関する。
続きを表示（約 1,900 文字）【背景技術】
【０００２】
組合せ最適化問題の解を探索する際に、組合せ最適化問題を、磁性体のスピンの振る舞いを表すイジングモデルに変換する手法がある。そして、マルコフ連鎖モンテカルロ法により、イジング型の評価関数の値、つまりイジングモデルのエネルギーに相当する値が極小になるイジングモデルの状態の探索が行われる。評価関数の極小値のうちの最小値になる状態が最適解となる。イジング型の評価関数に含まれる状態変数は、０または１の値を取るバイナリ変数である。状態変数はビットと表記されてもよい。なお、評価関数の符号を変えれば、評価関数の値が極大になる状態を探索することもできる。
【０００３】
以下、マルコフ連鎖モンテカルロ法を、ＭＣＭＣ（Markov-Chain Monte Carlo）法と略す。また、ＭＣＭＣ法による処理をＭＣＭＣ処理と呼ぶ場合もある。ＭＣＭＣ処理では、たとえば、メトロポリス法またはギブス法で規定される状態遷移の受け入れ確率で、その状態遷移が受け入れられる。ＭＣＭＣ法の一種として、疑似焼き鈍し法やレプリカ交換法がある。
【０００４】
従来、ＭＣＭＣ処理の１試行あたりに状態変数の変化（以下、遷移という）を許容するビット数を１とする処理（以下単一ビット遷移処理という）がある。しかし、単一ビット遷移処理では、解が局所解に嵌まった場合に、その局所解から脱出することが難しくなり、探索速度が低下する場合がある。
【０００５】
そのため、複数ビットの遷移が生じる場合の評価関数の値の変化量の計算結果に基づいて、当該複数ビットの遷移の可否を判定し、遷移が許容された場合には複数ビットの遷移を生じさせる処理が提案されている（たとえば、特許文献１－４参照）。以下このような処理を複数ビット遷移処理という。複数ビット遷移処理によれば、解の局所解からの脱出が促進され、探索範囲を広げることができる。
【０００６】
ところで、組合せ最適化問題には、解が満たすべき制約条件をもつものがある。たとえば、離散最適化問題の１つであるナップザック問題では、ナップザックに詰め込める荷物の総容量は、ナップザックの容量以下であるという制約条件をもつ。
【先行技術文献】
【特許文献】
【０００７】
特開２０２０－０２１２０９号公報
特開２０２０－０６４５３６号公報
特開２０２１－１５７３６１号公報
特開２０２１－１６５９６５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
従来の複数ビット遷移処理では、複数ビットの遷移が生じる場合の評価関数の値の変化量を計算するための構成やデータを伝搬する構成などが複雑となるため、実装が容易ではなかった。
【０００９】
１つの側面では、本発明は、制約条件をもつ組合せ最適化問題の解探索を行う複数ビット遷移処理の実装が実現可能なデータ処理装置、データ処理プログラム及びデータ処理方法を提供することを目的とする。
【課題を解決するための手段】
【００１０】
１つの実施態様では、制約条件をもつ組合せ最適化問題の評価関数に含まれる複数の状態変数の第１時点の値と、前記複数の状態変数のそれぞれの値の変化に伴う前記評価関数の値の変化量の特定に用いられる第１局所場の前記第１時点の値と、前記制約条件が満たされないときに前記評価関数の値に加算される制約違反量の特定に用いられる第２局所場の前記第１時点の値と、を記憶するメモリと、前記第１時点における前記第１局所場の値を用いて前記変化量を算出するとともに、前記変化量に基づいて、前記複数の状態変数のうち値を変化させる候補を１つずつ決定する遷移候補決定回路と、前記候補が決定されるたびに前記候補の値と、前記第１局所場及び前記第２局所場の値を更新し、第２時点において、前記第２局所場の前記第１時点の値及び前記第２時点の値を用いて、前記第１局所場の値をさらに更新する更新回路と、前記候補の値を変化させたときの前記変化量の累積値を算出する累積値算出回路と、前記累積値に基づいて、２以上の第１の数の前記候補の値の変化を受け入れるか否かを判定する判定回路と、前記判定回路が前記第１の数の前記候補の値の変化を受け入れないと判定した場合、前記複数の状態変数の値、前記第１局所場の値、及び前記第２局所場の値をそれぞれ、前記第１時点における値に戻す制御回路と、を有するデータ処理装置が提供される。
（【００１１】以降は省略されています）

関連特許