特許ウォッチ

公開番号2024092195
公報種別公開特許公報(A)
公開日2024-07-08
出願番号2022207956
出願日2022-12-26
発明の名称温度調整プログラム、データ処理装置及びデータ処理方法
出願人富士通株式会社
代理人弁理士法人扶桑国際特許事務所
主分類G06N 99/00 20190101AFI20240701BHJP(計算;計数)
要約【課題】レプリカ交換法で用いられる最低温度の調整時間を短縮する。
【解決手段】探索部12が、最適化問題を変換したイジングモデルに基づく評価関数の複数のレプリカに対応するレプリカ回路12a1～12anを用いてレプリカ交換法により最適化問題の解の探索処理を行い、処理部13が、探索部12から、探索処理の間に、レプリカ回路12a1～12anのうち最小の温度値が設定されたレプリカ回路による探索処理で得られた評価関数の値の平均値を複数回取得し、複数回取得した平均値のうちの第1平均値と、第1平均値よりも前に取得した第2平均値との比較結果に基づいて、最小の温度値を変更し、変更後の最小の温度値を探索部12に対して設定する。
【選択図】図1
特許請求の範囲【請求項１】
最適化問題を変換したイジングモデルに基づく評価関数の複数のレプリカに対応する複数のレプリカ回路を用いてレプリカ交換法により前記最適化問題の解の探索処理を行う探索部から、前記探索処理の間に、前記複数のレプリカ回路のうち最小の温度値が設定されたレプリカ回路による前記探索処理で得られた前記評価関数の値の平均値を複数回取得し、
複数回取得した前記平均値のうちの第１平均値と、前記第１平均値よりも前に取得した第２平均値との比較結果に基づいて、前記最小の温度値を変更し、
変更後の前記最小の温度値を前記探索部に対して設定する、
処理をコンピュータに実行させる温度調整プログラム。
続きを表示（約 1,400 文字）【請求項２】
前記探索処理の間に所定回数のレプリカ交換が行われるたびに、前記探索部から前記平均値を取得する処理を前記コンピュータに実行させる、請求項１に記載の温度調整プログラム。
【請求項３】
前記最小の温度値の下限値と最大の温度値との間を所定の分割数で分割し、前記分割数に基づく複数段階の大きさをもつ、前記最小の温度値の複数の候補値を算出する、処理を前記コンピュータに実行させる、請求項１に記載の温度調整プログラム。
【請求項４】
前記下限値を、前記最小の温度値の初期値とする場合、
前記第１平均値が前記第２平均値よりも小さいとき、前記最小の温度値を、前記複数の候補値のうち、現在の前記最小の温度値よりも１段階大きい候補値に変更し、
前記第１平均値が前記第２平均値以上であるとき、前記最小の温度値を、前記複数の候補値のうち、現在の前記最小の温度値よりも１段階小さい候補値に変更する、処理を前記コンピュータに実行させる、請求項３に記載の温度調整プログラム。
【請求項５】
最適化問題を変換したイジングモデルに基づく評価関数の複数のレプリカに対応する複数のレプリカ回路を用いてレプリカ交換法により前記最適化問題の解の探索処理を行う探索部と、
前記探索部から、前記探索処理の間に、前記複数のレプリカ回路のうち最小の温度値が設定されたレプリカ回路による前記探索処理で得られた前記評価関数の値の平均値を複数回取得し、複数回取得した前記平均値のうちの第１平均値と、前記第１平均値よりも前に取得した第２平均値との比較結果に基づいて、前記最小の温度値を変更し、変更後の前記最小の温度値を前記探索部に対して設定する処理部と、
を有するデータ処理装置。
【請求項６】
前記探索部は、所定の交換確率に基づいて、前記複数のレプリカ回路の間で前記複数のレプリカの状態を交換し、
前記複数のレプリカ回路のうち、前記最小の温度値が設定された前記レプリカ回路が前記平均値を計算する、
請求項５に記載のデータ処理装置。
【請求項７】
前記探索部は、前記複数のレプリカ回路に設定されている複数の温度値を、所定の交換確率に基づいて交換する温度制御部を有し、
前記温度制御部が、前記最小の温度値が設定された前記レプリカ回路から供給される前記探索処理の間の前記評価関数の値の変化量に基づいて、前記平均値を計算する、
請求項５に記載のデータ処理装置。
【請求項８】
探索部が、最適化問題を変換したイジングモデルに基づく評価関数の複数のレプリカに対応する複数のレプリカ回路を用いてレプリカ交換法により前記最適化問題の解の探索処理を行い、
処理部が、
前記探索部から、前記探索処理の間に、前記複数のレプリカ回路のうち最小の温度値が設定されたレプリカ回路による前記探索処理で得られた前記評価関数の値の平均値を複数回取得し、
複数回取得した前記平均値のうちの第１平均値と、前記第１平均値よりも前に取得した第２平均値との比較結果に基づいて、前記最小の温度値を変更し、
変更後の前記最小の温度値を前記探索部に対して設定する、
データ処理方法。

発明の詳細な説明【技術分野】
【０００１】
本発明は、温度調整プログラム、データ処理装置及びデータ処理方法に関する。
続きを表示（約 1,700 文字）【背景技術】
【０００２】
組合せ最適化問題の解を探索する際に、組合せ最適化問題を、磁性体のスピンの振る舞いを表すイジングモデルに変換する手法がある。イジングモデルは、組合せ最適化問題の解を評価するイジング型の評価関数で表される。イジング型の評価関数は、複数の状態変数と複数の重み値を含む。複数の状態変数の値により、イジングモデルの状態が表される。イジング型の評価関数では、状態変数は、０か１（または－１か＋１）の値を取る２値変数である。状態変数はビットと表記されてもよい。また、イジング型の評価関数の値は、イジングモデルのエネルギーということもできる。
【０００３】
解の探索では、マルコフ連鎖モンテカルロ（ＭＣＭＣ：Markov-Chain Monte Carlo）法が用いられる。以下、ＭＣＭＣ法による解の探索をＭＣＭＣ処理という。ＭＣＭＣ処理では、たとえば、メトロポリス法またはギブス法で規定される状態遷移の受け入れ確率で、状態遷移が受け入れられる。このとき、エネルギーを増加させる状態遷移も確率的に許容される。なお、エネルギーの増加量が大きいほど受け入れ確率は低くなる。
【０００４】
ＭＣＭＣ法の一種として、レプリカ交換法（パラレルテンパリング法などとも呼ばれる）がある。レプリカ交換法では、複数の温度値を用いたＭＣＭＣ処理が、イジングモデルの複数のレプリカにより互いに独立に行われる。そして、ある試行回数ごとに、各ＭＣＭＣ処理で得られるエネルギーが比較され、適切な交換確率で２つの温度値に対する状態が交換される。レプリカ交換法によれば、温度値を徐々に小さくしていく疑似焼き鈍し法と比べて、局所解に拘束される可能性が抑えられ、全解空間を効率よく探索できる。
【０００５】
なお、従来、レプリカ交換法の処理の間に、２つの固定温度値の間の複数の温度値の何れかを調整する手法が提案されている（たとえば、特許文献１参照）。また、従来、交換確率の均一性を高めるために、温度値の間隔を、比熱を利用して調整する手法が提案されている（たとえば、特許文献２参照）。
【先行技術文献】
【特許文献】
【０００６】
特開２０２１－１４０７７９号公報
特開２０２１－４３５０３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
レプリカ交換法を用いて最適化問題を解く際、複数の温度値のうちの最小の温度値（以下最低温度と呼ぶ場合もある）が適切に設定されていない場合、解が求まるまでの時間が非常に長くなることがある。たとえば、最低温度が低すぎると、エネルギー上昇を伴う状態遷移がほとんど起こらず、一度局所解にはまった場合に、その局所解から脱出できない可能性があるためである。
【０００８】
しかし、適切な最低温度を決定するためには、ある最低温度を用いて解の探索処理を行い、その結果に基づいて最低温度を調整する、という手順を繰り返すことになる。このため、最低温度の調整には時間がかかるという問題がある。
【０００９】
１つの側面では、本発明は、レプリカ交換法で用いられる最低温度の調整時間を短縮可能な温度調整プログラム、データ処理装置及びデータ処理方法を提供することを目的とする。
【課題を解決するための手段】
【００１０】
１つの実施態様では、最適化問題を変換したイジングモデルに基づく評価関数の複数のレプリカに対応する複数のレプリカ回路を用いてレプリカ交換法により前記最適化問題の解の探索処理を行う探索部から、前記探索処理の間に、前記複数のレプリカ回路のうち最小の温度値が設定されたレプリカ回路による前記探索処理で得られた前記評価関数の値の平均値を複数回取得し、複数回取得した前記平均値のうちの第１平均値と、前記第１平均値よりも前に取得した第２平均値との比較結果に基づいて、前記最小の温度値を変更し、変更後の前記最小の温度値を前記探索部に対して設定する、処理をコンピュータに実行させる温度調整プログラムが提供される。
（【００１１】以降は省略されています）

関連特許