特許ウォッチ

公開番号2025168797
公報種別公開特許公報(A)
公開日2025-11-12
出願番号2024073559
出願日2024-04-30
発明の名称プログラム及びデータ処理装置
出願人富士通株式会社
代理人弁理士法人扶桑国際特許事務所
主分類G06N 99/00 20190101AFI20251105BHJP(計算;計数)
要約【課題】組合せ最適化問題の局所解からの脱出を促進する。
【解決手段】処理部12aは、局所探索により組合せ最適化問題の解を、複数の状態変数による第1探索範囲で探索する。処理部12aは、第1探索範囲の探索において、複数の状態変数の値の組合せで表される現在状態が局所解に陥ったか否かを判定し、現在状態が局所解に陥ったと判定した場合、記憶部11に記憶された複数の解候補に基づいて、第1解候補を決定する。処理部12aは、複数の状態変数のうち、現在状態と第1解候補との間で相互に同じ値をもつ第1状態変数の値を固定した状態で、複数の状態変数のうち、現在状態と第1解候補との間で相互に異なる値をもつ第2状態変数による第2探索範囲で、局所探索を実行する。
【選択図】図1
特許請求の範囲【請求項１】
局所探索により組合せ最適化問題の解を、複数の状態変数による第１探索範囲で探索し、
前記第１探索範囲の探索において、前記複数の状態変数の値の組合せで表される現在状態が局所解に陥ったか否かを判定し、
前記現在状態が前記局所解に陥ったと判定した場合、記憶部に記憶された複数の解候補に基づいて、第１解候補を決定し、
前記複数の状態変数のうち、前記現在状態と前記第１解候補との間で相互に同じ値をもつ第１状態変数の値を固定した状態で、前記複数の状態変数のうち、前記現在状態と前記第１解候補との間で相互に異なる値をもつ第２状態変数による第２探索範囲で、前記局所探索を実行する、
処理をコンピュータに実行させるプログラム。
続きを表示（約 1,400 文字）【請求項２】
前記複数の解候補のそれぞれは、前記第１探索範囲の探索中に得られる前記組合せ最適化問題の評価関数の値のうち、最小値が更新されたときの、前記複数の状態変数の値の組合せで表される、請求項１に記載のプログラム。
【請求項３】
前記局所探索は、互いに異なる複数の計算条件で行われ、
前記複数の解候補は、前記複数の計算条件で行われる前記局所探索のそれぞれで得られた解候補を含む、
請求項２に記載のプログラム。
【請求項４】
前記第１解候補は、前記複数の解候補のうち、前記現在状態との間のハミング距離が閾値に最も近い解候補である、請求項１に記載のプログラム。
【請求項５】
前記第１解候補は、前記複数の解候補からランダムに選択される２つの解候補を用いて、パス再結合法により決定される、請求項１に記載のプログラム。
【請求項６】
前記第１探索範囲の探索中に得られる前記組合せ最適化問題の評価関数の値のうちの最小値が、所定期間更新されなかったときに、前記現在状態が前記局所解に陥ったと判定する、処理を前記コンピュータに実行させる請求項１に記載のプログラム。
【請求項７】
前記第２探索範囲の探索中に、前記現在状態が前記局所解から脱出したか否かを判定し、
前記現在状態が前記局所解から脱出したと判定したときに、前記第１状態変数の値の固定を解除し、前記第１探索範囲で、前記局所探索を実行する、
処理を前記コンピュータに実行させる請求項１に記載のプログラム。
【請求項８】
前記第２探索範囲の探索中に、所定期間内に前記現在状態が前記局所解から脱出しなかったと判定されたときに、前記複数の解候補に基づいて、前記第１解候補とは異なる第２解候補を決定し、
前記複数の状態変数のうち、前記現在状態と前記第２解候補との間で、相互に同じ値をもつ第３状態変数の値を固定し、
前記複数の状態変数のうち、前記現在状態と前記第２解候補との間で、相互に異なる値をもつ第４状態変数による第３探索範囲で、前記局所探索を実行する、
処理を前記コンピュータに実行させる請求項７に記載のプログラム。
【請求項９】
組合せ最適化問題の解を、第１評価関数を用いた局所探索により探索し、
前記第１評価関数を用いた探索において、前記第１評価関数に含まれる複数の状態変数の値の組合せで表される現在状態が局所解に陥ったか否かを判定し、
前記現在状態が前記局所解に陥ったと判定した場合、記憶部に記憶された複数の解候補に基づいて、第１解候補を決定し、
前記第１評価関数を、前記第１解候補と前記現在状態との間のハミング距離に比例する大きさをもつ第１制約項を前記第１評価関数に加えた第２評価関数に変更し、
前記第２評価関数を用いて、前記局所探索を実行する、
処理をコンピュータに実行させるプログラム。
【請求項１０】
前記複数の解候補のそれぞれは、前記第１評価関数を用いた探索中に得られる前記第１評価関数の値のうち、最小値が更新されたときの、前記複数の状態変数の値の組合せで表される、請求項９に記載のプログラム。
（【請求項１１】以降は省略されています）
発明の詳細な説明【技術分野】
【０００１】
本発明は、プログラム及びデータ処理装置に関する。
続きを表示（約 1,800 文字）【背景技術】
【０００２】
組合せ最適化問題の解を探索する際に、組合せ最適化問題を、磁性体のスピンの振る舞いを表すイジングモデルに変換する手法がある。イジングモデルは、組合せ最適化問題の解を評価するイジング型の評価関数で表される。イジング型の評価関数は、複数の状態変数と複数の重み値を含む。複数の状態変数の値の組合せにより、イジングモデルの状態が表される。イジング型の評価関数では、状態変数は、０か１（または－１か＋１）の値を取る２値変数である。状態変数はビットと表記されてもよい。また、イジング型の評価関数はエネルギー関数、評価関数の値はイジングモデルのエネルギーということもできる。
【０００３】
このようなイジング型の評価関数を用いて解探索を行う装置は、イジングマシンと呼ばれる。イジングマシンは、評価関数に含まれる状態変数の値の組合せのうち、たとえば、評価関数の値を最小化する組合せを探索する。この場合、評価関数の値を最小化する状態変数の値の組合せは、基底状態または最適解に相当する。
【０００４】
実用的な時間で組合せ最適化問題の近似解を得る求解手法には、局所探索がある（たとえば、特許文献１～４参照）。局所探索を行う方法の例として、たとえば、ＭＣＭＣ（Markov Chain Monte Carlo）法の一種である疑似焼き鈍し法やレプリカ交換法（交換モンテカルロ法などとも呼ばれる）などがある。
【０００５】
また、最適化問題には、評価関数に含まれる状態変数群のうち値が１となる状態変数の数を１つのみとする制約（１－ｈｏｔ制約）をもつものがある。従来、１－ｈｏｔ制約を満たす状態に絞って局所探索を行うことで、計算時間を短縮する最適化装置が提案されている（たとえば、特許文献５参照）。
【先行技術文献】
【特許文献】
【０００６】
特開２００３－２２３３２２号公報
特開２０１８－１０９９５０号公報
米国特許出願公開第２０１９／０２５１２２７号明細書
米国特許出願公開第２０１６／０２０３４１９号明細書
特開２０２０－０６４５３６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
局所探索では、評価関数に含まれる状態変数の値の組合せで表される状態が、局所解に陥って脱出できなくなる場合がある。この場合、求解時間が長くなる可能性がある。
１つの側面では、組合せ最適化問題の局所解からの脱出を促進することを目的とする。
【課題を解決するための手段】
【０００８】
１つの実施態様では、局所探索により組合せ最適化問題の解を、複数の状態変数による第１探索範囲で探索し、前記第１探索範囲の探索において、前記複数の状態変数の値の組合せで表される現在状態が局所解に陥ったか否かを判定し、前記現在状態が前記局所解に陥ったと判定した場合、記憶部に記憶された複数の解候補に基づいて、第１解候補を決定し、前記複数の状態変数のうち、前記現在状態と前記第１解候補との間で相互に同じ値をもつ第１状態変数の値を固定した状態で、前記複数の状態変数のうち、前記現在状態と前記第１解候補との間で相互に異なる値をもつ第２状態変数による第２探索範囲で、前記局所探索を実行する、処理をコンピュータに実行させるプログラムが提供される。
【０００９】
また、１つの実施態様では、組合せ最適化問題の解を、第１評価関数を用いた局所探索により探索し、前記第１評価関数を用いた探索において、前記第１評価関数に含まれる複数の状態変数の値の組合せで表される現在状態が局所解に陥ったか否かを判定し、前記現在状態が前記局所解に陥ったと判定した場合、記憶部に記憶された複数の解候補に基づいて、第１解候補を決定し、前記第１評価関数を、前記第１解候補と前記現在状態との間のハミング距離に比例する大きさをもつ第１制約項を前記第１評価関数に加えた第２評価関数に変更し、前記第２評価関数を用いて、前記局所探索を実行する、処理をコンピュータに実行させるプログラムが提供される。
【００１０】
また、１つの実施態様では、データ処理装置が提供される。
【発明の効果】
（【００１１】以降は省略されています）

関連特許