特許ウォッチ

公開番号2025069535
公報種別公開特許公報(A)
公開日2025-05-01
出願番号2023179311
出願日2023-10-18
発明の名称プログラム、データ処理装置及びデータ処理方法
出願人富士通株式会社
代理人弁理士法人扶桑国際特許事務所
主分類G06N 99/00 20190101AFI20250423BHJP(計算;計数)
要約【課題】多くの組合せ最適化問題の解探索に有用な、汎用性の高いパラメータの値を得る。
【解決手段】処理部12は、複数の組合せ最適化問題に対する第1解探索の結果を用いて、複数の組合せ最適化問題のそれぞれの第1難易度を決定する。また、処理部12は、複数の組合せ最適化問題のそれぞれ、または複数の組合せ最適化問題の一部の組合せ最適化問題に対し、問題規模、制約条件の種類、または制約条件の数を用いて第2難易度を決定する。そして、処理部12は、複数の組合せ最適化問題から、第1難易度と第2難易度に基づいて得られる第3難易度の高い順に、複数の評価対象問題を選択し、複数の評価対象問題に対して、解探索のパラメータの候補値を用いた第2解探索の結果に基づいて候補値の評価値を算出する処理を、候補値を変更して複数回行い、評価値に基づいて、パラメータの値を決定する。
【選択図】図1
特許請求の範囲【請求項１】
複数の組合せ最適化問題に対する第１解探索の結果を用いて、前記複数の組合せ最適化問題のそれぞれの第１難易度を決定し、
前記複数の組合せ最適化問題のそれぞれ、または前記複数の組合せ最適化問題の一部の組合せ最適化問題に対し、問題規模、制約条件の種類、または前記制約条件の数を用いて第２難易度を決定し、
前記複数の組合せ最適化問題から、前記第１難易度と前記第２難易度に基づいて得られる第３難易度の高い順に、複数の評価対象問題を選択し、
前記複数の評価対象問題に対して、解探索のパラメータの候補値を用いた第２解探索の結果に基づいて前記候補値の評価値を算出する処理を、前記候補値を変更して複数回行い、前記評価値に基づいて、前記パラメータの値を決定する、
処理をコンピュータに実行させるプログラム。
続きを表示（約 1,700 文字）【請求項２】
前記複数の組合せ最適化問題は、前記第１難易度に基づいて、前記一部の組合せ最適化問題に絞り込まれ、
前記一部の組合せ最適化問題に対して、前記第２難易度が決定される、
請求項１に記載のプログラム。
【請求項３】
前記一部の組合せ最適化問題は、前記複数の組合せ最適化問題のうち、前記第１難易度が最も高い組合せ最適化問題から難易度順に数えて、前記複数の評価対象問題の問題数に対応する組合せ最適化問題の前後の所定数の組合せ最適化問題であり、
前記所定数の組合せ最適化問題の前記第３難易度として、前記第２難易度が用いられる、
請求項１に記載のプログラム。
【請求項４】
前記第１難易度は、前記第１解探索において、前記第１解探索の開始時刻から、前記複数の組合せ最適化問題のそれぞれの評価関数の値が最後に更新された最終更新時刻までの時間を用いて決定され、
前記一部の組合せ最適化問題は、前記複数の組合せ最適化問題のうち、前記最終更新時刻が、前記第１解探索の終了時刻から所定の時間内である、前記複数の評価対象問題の問題数よりも多い複数の第１組合せ最適化問題であり、
前記複数の第１組合せ最適化問題の前記第３難易度として、前記第２難易度が用いられる、
請求項１に記載のプログラム。
【請求項５】
前記一部の組合せ最適化問題は、前記複数の組合せ最適化問題のうち、前記第１難易度が最も高い組合せ最適化問題から難易度順に、前記複数の評価対象問題の問題数に所定の値を乗じた数分、選択された複数の第２組合せ最適化問題であり、
前記複数の第２組合せ最適化問題の前記第３難易度として、前記第２難易度が用いられる、
請求項１に記載のプログラム。
【請求項６】
前記第１難易度は、前記第１解探索における、前記複数の組合せ最適化問題のそれぞれの評価関数の値の更新履歴に基づいて決定される、請求項１に記載のプログラム。
【請求項７】
前記評価値に基づいて決定された前記パラメータの値と、前記複数の組合せ最適化問題の問題情報とをイジングマシンに設定し、前記イジングマシンに前記複数の組合せ最適化問題に対する第３解探索を行わせる、処理を前記コンピュータに実行させる、請求項１に記載のプログラム。
【請求項８】
複数の組合せ最適化問題に対する第１解探索の結果を記憶する記憶部と、
前記第１解探索の結果を用いて、前記複数の組合せ最適化問題のそれぞれの第１難易度を決定し、前記複数の組合せ最適化問題のそれぞれ、または前記複数の組合せ最適化問題の一部の組合せ最適化問題に対し、問題規模、制約条件の種類、または前記制約条件の数を用いて第２難易度を決定し、前記複数の組合せ最適化問題から、前記第１難易度と前記第２難易度に基づいて得られる第３難易度の高い順に、複数の評価対象問題を選択し、前記複数の評価対象問題に対して、解探索のパラメータの候補値を用いた第２解探索の結果に基づいて前記候補値の評価値を算出する処理を、前記候補値を変更して複数回行い、前記評価値に基づいて、前記パラメータの値を決定する処理部と、
を有するデータ処理装置。
【請求項９】
コンピュータが、
複数の組合せ最適化問題に対する第１解探索の結果を用いて、前記複数の組合せ最適化問題のそれぞれの第１難易度を決定し、
前記複数の組合せ最適化問題のそれぞれ、または前記複数の組合せ最適化問題の一部の組合せ最適化問題に対し、問題規模、制約条件の種類、または前記制約条件の数を用いて第２難易度を決定し、
前記複数の組合せ最適化問題から、前記第１難易度と前記第２難易度に基づいて得られる第３難易度の高い順に、複数の評価対象問題を選択し、
前記複数の評価対象問題に対して、解探索のパラメータの候補値を用いた第２解探索の結果に基づいて前記候補値の評価値を算出する処理を、前記候補値を変更して複数回行い、前記評価値に基づいて、前記パラメータの値を決定する、
データ処理方法。

発明の詳細な説明【技術分野】
【０００１】
本発明は、プログラム、データ処理装置及びデータ処理方法に関する。
続きを表示（約 1,700 文字）【背景技術】
【０００２】
組合せ最適化問題の解を探索する際に、組合せ最適化問題を、磁性体のスピンの振る舞いを表すイジングモデルに変換する手法がある。イジングモデルは、組合せ最適化問題の解を評価するイジング型の評価関数で表される。イジング型の評価関数は、複数の状態変数と複数の重み値を含む。複数の状態変数の値により、イジングモデルの状態が表される。イジング型の評価関数では、状態変数は、０か１（または－１か＋１）の値を取る２値変数である。状態変数はビットと表記されてもよい。また、イジング型の評価関数はエネルギー関数、評価関数の値はイジングモデルのエネルギーということもできる。
【０００３】
このようなイジング型の評価関数を用いて解探索を行う装置は、イジングマシンと呼ばれる。イジングマシンは、評価関数に含まれる状態変数の値の組合せのうち、たとえば、評価関数の値を最小化する組合せを探索する。この場合、評価関数の値を最小化する状態変数の値の組合せは、基底状態または最適解に相当する。
【０００４】
実用的な時間で組合せ最適化問題の近似解を得る求解手法には、たとえば、シミュレーテッドアニーリング（ＳＡ：Simulated Annealing）法、レプリカ交換法がある。他にも、遺伝的アルゴリズム（ＧＡ：Genetic Algorithm）、シミュレーテッド量子アニーリング（ＳＱＡ：Simulated Quantum Annealing）法、タブーサーチ法などがある。これらの各求解手法では解探索の実行に所定のパラメータが用いられる。たとえば、ＳＡ法では、最高温度、最低温度などの温度パラメータが用いられる。
【０００５】
パラメータの値は、イジングマシンの求解性能に影響する。ＳＡ法やレプリカ交換法などで用いられるパラメータの値を決定するために、本番の解探索前に適切なパラメータの値を探索することがある（たとえば、特許文献１参照）。
【先行技術文献】
【特許文献】
【０００６】
特開２０２３－７９０１５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
多くの組合せ最適化問題の解探索に有用な汎用性の高いパラメータの値を、各組合せ最適化問題に対する解探索の結果に基づいて探索する場合、探索時間が長くなってしまう。探索時間を短縮するために、複数の組合せ最適化問題の中からパラメータの値の探索に用いる問題をランダムに選択することが考えられるが、十分な汎用性を有さないパラメータの値が得られてしまう可能性がある。
【０００８】
１つの側面では、本発明は、多くの組合せ最適化問題の解探索に有用な、汎用性の高いパラメータの値を得ることを目的とする。
【課題を解決するための手段】
【０００９】
１つの実施態様では、複数の組合せ最適化問題に対する第１解探索の結果を用いて、前記複数の組合せ最適化問題のそれぞれの第１難易度を決定し、前記複数の組合せ最適化問題のそれぞれ、または前記複数の組合せ最適化問題の一部の組合せ最適化問題に対し、問題規模、制約条件の種類、または前記制約条件の数を用いて第２難易度を決定し、前記複数の組合せ最適化問題から、前記第１難易度と前記第２難易度に基づいて得られる第３難易度の高い順に、複数の評価対象問題を選択し、前記複数の評価対象問題に対して、解探索のパラメータの候補値を用いた第２解探索の結果に基づいて前記候補値の評価値を算出する処理を、前記候補値を変更して複数回行い、前記評価値に基づいて、前記パラメータの値を決定する、処理をコンピュータに実行させるプログラムが提供される。
【００１０】
また、１つの実施態様では、データ処理装置が提供される。
また、１つの実施態様では、データ処理方法が提供される。
【発明の効果】
（【００１１】以降は省略されています）

関連特許