特許ウォッチ

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

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

関連特許