特許ウォッチ

公開番号2024077644
公報種別公開特許公報(A)
公開日2024-06-10
出願番号2022189711
出願日2022-11-29
発明の名称データ処理装置、プログラム及びデータ処理方法
出願人富士通株式会社
代理人弁理士法人扶桑国際特許事務所
主分類G06N 99/00 20190101AFI20240603BHJP(計算;計数)
要約【課題】複数の連続変数を含む評価関数をイジング型の評価関数に変換する際のビット数を削減する。
【解決手段】記憶部11は、組合せ最適化問題を定式化した、複数の連続変数を含む第1評価関数の情報を記憶し、探索部12は、組合せ最適化問題の解を、複数の2値変数を含むイジング型の第2評価関数を用いて探索し、処理部13は、記憶部11から取得した上記の情報に基づいて、複数の連続変数に含まれる連続変数対の相関の大きさを検出し、複数の連続変数のそれぞれに1または複数の2値変数を割り当てる際に、相関が大きいほど、連続変数対に多くの共通の2値変数を割り当て、複数の連続変数のそれぞれと割り当てられた2値変数との対応関係を表す対応情報を生成し、対応情報に基づいて、第1評価関数を第2評価関数に変換し、第2評価関数の係数情報を探索部12に設定する。
【選択図】図1
特許請求の範囲【請求項１】
組合せ最適化問題を定式化した、複数の連続変数を含む第１評価関数の情報を記憶する記憶部と、
前記組合せ最適化問題の解を、複数の２値変数を含むイジング型の第２評価関数を用いて探索する探索部と、
前記情報を前記記憶部から取得し、前記情報に基づいて、前記複数の連続変数に含まれる連続変数対の相関の大きさを検出し、前記複数の連続変数のそれぞれに１または複数の２値変数を割り当てる際に、前記相関が大きいほど、前記連続変数対に多くの共通の２値変数を割り当て、前記複数の連続変数のそれぞれと割り当てられた２値変数との対応関係を表す対応情報を生成し、前記対応情報に基づいて、前記第１評価関数を前記第２評価関数に変換し、前記第２評価関数の係数情報を前記探索部に設定する、処理部と、
を有するデータ処理装置。
続きを表示（約 1,300 文字）【請求項２】
前記情報は、前記複数の連続変数のうち、第１の連続変数と第２の連続変数の間の重み係数を含み、
前記処理部は、前記重み係数を、前記第１の連続変数と前記第２の連続変数による前記連続変数対の前記相関の大きさとして検出する、
請求項１に記載のデータ処理装置。
【請求項３】
前記情報は、前記複数の連続変数のうち、第１の連続変数と第２の連続変数の間の重み係数と、前記第１の連続変数に対する第１のバイアス係数と、前記第２の連続変数に対する第２のバイアス係数と、を含み、
前記処理部は、前記重み係数と前記第１のバイアス係数と前記第２のバイアス係数との和を、前記第１の連続変数と前記第２の連続変数による前記連続変数対の前記相関の大きさとして検出する、
請求項１に記載のデータ処理装置。
【請求項４】
前記処理部は、前記情報に基づいて行われる、所定期間のマルコフ連鎖モンテカルロ法による探索で得られる前記複数の連続変数の値の時間変化を示す時系列情報に基づいて、前記相関の大きさを検出する、
請求項１に記載のデータ処理装置。
【請求項５】
前記処理部は、前記探索部が出力する前記複数の２値変数の値で表される第１の解を取得し、前記第１の解を、前記対応情報に基づいて、前記複数の連続変数の値で表される第２の解に変換する、
請求項１に記載のデータ処理装置。
【請求項６】
組合せ最適化問題を定式化した、複数の連続変数を含む第１評価関数の情報を記憶部から取得し、
前記情報に基づいて、前記複数の連続変数に含まれる連続変数対の相関の大きさを検出し、
前記複数の連続変数のそれぞれに１または複数の２値変数を割り当てる際に、前記相関が大きいほど、前記連続変数対に多くの共通の２値変数を割り当て、前記複数の連続変数のそれぞれと割り当てられた２値変数との対応関係を表す対応情報を生成し、
前記対応情報に基づいて、前記第１評価関数を、複数の２値変数を含むイジング型の第２評価関数に変換し、
前記第２評価関数の係数情報を、前記第２評価関数を用いて前記組合せ最適化問題の解を探索する探索部に設定する、
処理をコンピュータに実行させるプログラム。
【請求項７】
記憶部が、組合せ最適化問題を定式化した、複数の連続変数を含む第１評価関数の情報を記憶し、
探索部が、前記組合せ最適化問題の解を、複数の２値変数を含むイジング型の第２評価関数を用いて探索し、
処理部が、
前記情報を前記記憶部から取得し、
前記情報に基づいて、前記複数の連続変数に含まれる連続変数対の相関の大きさを検出し、
前記複数の連続変数のそれぞれに１または複数の２値変数を割り当てる際に、前記相関が大きいほど、前記連続変数対に多くの共通の２値変数を割り当て、前記複数の連続変数のそれぞれと割り当てられた２値変数との対応関係を表す対応情報を生成し、
前記対応情報に基づいて、前記第１評価関数を前記第２評価関数に変換し、
前記第２評価関数の係数情報を前記探索部に設定する、
データ処理方法。

発明の詳細な説明【技術分野】
【０００１】
本発明は、データ処理装置、プログラム及びデータ処理方法に関する。
続きを表示（約 1,600 文字）【背景技術】
【０００２】
組合せ最適化問題の解を探索する際に、組合せ最適化問題を、磁性体のスピンの振る舞いを表すイジングモデルに変換する手法がある。そして、マルコフ連鎖モンテカルロ法により、イジング型の評価関数の値（イジングモデルのエネルギーに相当する）が極小になるイジングモデルの状態の探索が行われる。評価関数は、複数の状態変数と複数の重み係数を含む。イジング型の評価関数では、状態変数は、０か１（または－１か＋１）の値を取る２値変数である。状態変数はビットと表記されてもよい。評価関数の極小値のうちの最小値になる状態が最適解となる。なお、評価関数の符号を変えれば、評価関数の値が極大になる状態を探索することもできる。
【０００３】
以下、マルコフ連鎖モンテカルロ法を、ＭＣＭＣ（Markov-Chain Monte Carlo）法と略す。また、ＭＣＭＣ法による処理をＭＣＭＣ処理と呼ぶ場合もある。ＭＣＭＣ処理では、たとえば、メトロポリス法またはギブス法で規定される状態遷移の受け入れ確率で、その状態遷移が受け入れられる。ＭＣＭＣ法の一種として、疑似焼き鈍し法やレプリカ交換法がある。
【０００４】
ところで、組合せ最適化問題には、連続変数を含む評価関数を用いて定式化されるものもある。このような組み合わせ最適化問題を、イジングモデルに変換して計算できるようにするために、２進展開などにより、連続変数を２値変数に変換する手法があった（たとえば、特許文献１参照）。
【先行技術文献】
【特許文献】
【０００５】
特開２０２０－６７８１１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
２進展開などにより単純に連続変数を離散化して２値変数に変換する場合、連続変数の数や求める精度などによって、２値変数の数（ビット数）が非常に多くなり、問題の規模が増大してしまうという可能性がある。なお、単純に各連続変数に割り当てるビット数を少なくした場合、イジングモデルを用いた解探索後に得られた複数の２値変数の値を再度連続変数に変換する際に、得られる解の精度が落ちてしまう。
【０００７】
１つの側面では、本発明は、複数の連続変数を含む評価関数をイジング型の評価関数に変換する際のビット数を削減可能なデータ処理装置、プログラム及びデータ処理方法を提供することを目的とする。
【課題を解決するための手段】
【０００８】
１つの実施態様では、組合せ最適化問題を定式化した、複数の連続変数を含む第１評価関数の情報を記憶する記憶部と、前記組合せ最適化問題の解を、複数の２値変数を含むイジング型の第２評価関数を用いて探索する探索部と、前記情報を前記記憶部から取得し、前記情報に基づいて、前記複数の連続変数に含まれる連続変数対の相関の大きさを検出し、前記複数の連続変数のそれぞれに１または複数の２値変数を割り当てる際に、前記相関が大きいほど、前記連続変数対に多くの共通の２値変数を割り当て、前記複数の連続変数のそれぞれと割り当てられた２値変数との対応関係を表す対応情報を生成し、前記対応情報に基づいて、前記第１評価関数を前記第２評価関数に変換し、前記第２評価関数の係数情報を前記探索部に設定する、処理部と、を有するデータ処理装置が提供される。
【０００９】
また、１つの実施態様では、プログラムが提供される。
また、１つの実施態様では、データ処理方法が提供される。
【発明の効果】
【００１０】
１つの側面では、本発明は、複数の連続変数を含む評価関数をイジング型の評価関数に変換する際のビット数を削減できる。
【図面の簡単な説明】
（【００１１】以降は省略されています）

関連特許