特許ウォッチ

公開番号2025014165
公報種別公開特許公報(A)
公開日2025-01-30
出願番号2023116455
出願日2023-07-18
発明の名称プログラム、データ処理装置及びデータ処理方法
出願人富士通株式会社
代理人弁理士法人扶桑国際特許事務所
主分類G06N 99/00 20190101AFI20250123BHJP(計算;計数)
要約【課題】ユーザが解きたい問題に適した最適化システムにより解探索を可能とする。
【解決手段】記憶部11は、組合せ最適化問題の目的関数と近傍状態の定義に依存しない処理を表すベース情報11bを記憶し、処理部12は、目的関数を定義する関数定義情報と、近傍状態を定義する近傍定義情報と、を含むユーザ定義情報11aの入力を受け付け、ベース情報11bと、ユーザ定義情報11aに基づいて、組合せ最適化問題の解を局所探索により探索する最適化システム15を生成し、目的関数に含まれる係数の値の入力を受け付け、最適化システム15を実行することで、関数定義情報と、近傍定義情報と、係数の値に基づいて、目的関数に含まれる複数の状態変数の値により表される状態が、近傍状態に遷移したときの目的関数の値の変化量に基づいて、第1近傍状態を選択し、複数の状態変数の値を、第1近傍状態の値に更新する。
【選択図】図1
特許請求の範囲【請求項１】
組合せ最適化問題の目的関数を定義する関数定義情報と、前記組合せ最適化問題の解を局所探索により探索するときの１または複数の近傍状態を定義する近傍定義情報と、を含むユーザ定義情報の入力を受け付け、
前記目的関数と前記１または複数の近傍状態の定義に依存しない処理を表し、メモリに記憶されたベース情報と、前記ユーザ定義情報に基づいて、前記組合せ最適化問題の解を前記局所探索により探索する最適化システムを生成し、
前記目的関数に含まれる係数の値の入力を受け付け、
前記最適化システムを実行することで、前記関数定義情報と、前記近傍定義情報と、前記係数の値に基づいて、前記目的関数に含まれる複数の状態変数の値により表される状態が、前記１または複数の近傍状態に遷移したときの、前記目的関数の値の変化量を算出し、前記変化量に基づいて、前記１または複数の近傍状態のうちの第１近傍状態を選択し、前記複数の状態変数の値を、前記第１近傍状態の値に更新する、
処理をコンピュータに実行させるプログラム。
続きを表示（約 1,400 文字）【請求項２】
前記最適化システムは、前記ベース情報に基づいて処理を行うベース部分と、前記ユーザ定義情報に基づいて処理を行うユーザ定義部分とを含む、請求項１に記載のプログラム。
【請求項３】
前記ユーザ定義情報は、前記局所探索の初期解を生成する処理の処理定義を示す第１処理定義情報を含み、
前記ユーザ定義部分は、前記第１処理定義情報に基づいて、入力される識別情報に応じた前記初期解を生成し、出力する初期解生成部を有する、
請求項２に記載のプログラム。
【請求項４】
前記最適化システムは、前記変化量の算出と、前記第１近傍状態の選択と、前記複数の状態変数の値の前記第１近傍状態の値への更新と、を繰り返すことで、前記局所探索を行い、前記局所探索により得られた解を、解プールに格納し、
前記ユーザ定義情報は、複数の解から、前記局所探索を再度開始するときの開始解を生成する処理の処理定義を示す第２処理定義情報を含み、
前記ユーザ定義部分は、前記第２処理定義情報に基づいて、前記解プールに格納されている前記複数の解から前記開始解を生成し、出力する開始解生成部を有する、
請求項２に記載のプログラム。
【請求項５】
組合せ最適化問題の目的関数と前記組合せ最適化問題の解を局所探索により探索するときの１または複数の近傍状態の定義に依存しない処理を表すベース情報を記憶する記憶部と、
前記目的関数を定義する関数定義情報と、前記１または複数の近傍状態を定義する近傍定義情報と、を含むユーザ定義情報の入力を受け付け、前記ベース情報と、前記ユーザ定義情報に基づいて、前記組合せ最適化問題の解を前記局所探索により探索する最適化システムを生成し、前記目的関数に含まれる係数の値の入力を受け付け、前記最適化システムを実行することで、前記関数定義情報と、前記近傍定義情報と、前記係数の値に基づいて、前記目的関数に含まれる複数の状態変数の値により表される状態が、前記１または複数の近傍状態に遷移したときの、前記目的関数の値の変化量を算出し、前記変化量に基づいて、前記１または複数の近傍状態のうちの第１近傍状態を選択し、前記複数の状態変数の値を、前記第１近傍状態の値に更新する処理部と、
を有するデータ処理装置。
【請求項６】
コンピュータが、
組合せ最適化問題の目的関数を定義する関数定義情報と、前記組合せ最適化問題の解を局所探索により探索するときの１または複数の近傍状態を定義する近傍定義情報と、を含むユーザ定義情報の入力を受け付け、
前記目的関数と前記１または複数の近傍状態の定義に依存しない処理を表し、メモリに記憶されたベース情報と、前記ユーザ定義情報に基づいて、前記組合せ最適化問題の解を前記局所探索により探索する最適化システムを生成し、
前記目的関数に含まれる係数の値の入力を受け付け、
前記最適化システムを実行することで、前記関数定義情報と、前記近傍定義情報と、前記係数の値に基づいて、前記目的関数に含まれる複数の状態変数の値により表される状態が、前記１または複数の近傍状態に遷移したときの、前記目的関数の値の変化量を算出し、前記変化量に基づいて、前記１または複数の近傍状態のうちの第１近傍状態を選択し、前記複数の状態変数の値を、前記第１近傍状態の値に更新する、
データ処理方法。

発明の詳細な説明【技術分野】
【０００１】
本発明は、プログラム、データ処理装置及びデータ処理方法に関する。
続きを表示（約 1,600 文字）【背景技術】
【０００２】
実社会における様々な問題（以下実問題と略す）は、組合せ最適化問題として表せる場合がある。組合せ最適化問題を解く場合、使用する最適化システムによって定められた形式に、問題が変換される。この変換は、定式化といわれる。たとえば、イジングマシンを用いる最適化システムの場合、組合せ最適化問題は、ＱＵＢＯ（Quadratic Unconstrained Binary Optimization）形式の目的関数に定式化されることがある。ユーザは、最適化システムに解探索を実行させ、得られた解探索結果を実問題に反映させ、適切な解が得られているか否かを確認する。
【０００３】
従来、計算対象の組合せ最適化問題に応じて、目的関数に含まれる係数がユーザによって指定されることがあった（たとえば、特許文献１－４参照）。
【先行技術文献】
【特許文献】
【０００４】
特開２０２１－１３１６１１号公報
特開２０１６－１０３２８２号公報
米国特許出願公開第２０１８／０３６５５８６号明細書
米国特許出願公開第２０１９／０１０２３５３号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００５】
従来の技術では、目的関数は、最適化システムにおいて定められた範囲内でしか定義することができない。たとえば、２次の目的関数を対象とするイジングマシンを用いる最適化システムでは、３次や４次の項をもつ目的関数を直接扱うことができない。また、ユーザが解きたい問題に特化した解法を、最適化システムに追加することができない。
【０００６】
このような場合、ユーザが自身でオリジナルの最適化システムを０から構築することがあるが、構築には非常に工数がかかる。したがって、ユーザが解きたい問題に適した最適化システムにより解を探索することは難しい。
【０００７】
１つの側面では、本発明は、ユーザが解きたい問題に適した最適化システムにより解探索可能なプログラム、データ処理装置及びデータ処理方法を提供することを目的とする。
【課題を解決するための手段】
【０００８】
１つの実施態様では、組合せ最適化問題の目的関数を定義する関数定義情報と、前記組合せ最適化問題の解を局所探索により探索するときの１または複数の近傍状態を定義する近傍定義情報と、を含むユーザ定義情報の入力を受け付け、前記目的関数と前記１または複数の近傍状態の定義に依存しない処理を表し、メモリに記憶されたベース情報と、前記ユーザ定義情報に基づいて、前記組合せ最適化問題の解を前記局所探索により探索する最適化システムを生成し、前記目的関数に含まれる係数の値の入力を受け付け、前記最適化システムを実行することで、前記関数定義情報と、前記近傍定義情報と、前記係数の値に基づいて、前記目的関数に含まれる複数の状態変数の値により表される状態が、前記１または複数の近傍状態に遷移したときの、前記目的関数の値の変化量を算出し、前記変化量に基づいて、前記１または複数の近傍状態のうちの第１近傍状態を選択し、前記複数の状態変数の値を、前記第１近傍状態の値に更新する、処理をコンピュータに実行させるプログラムが提供される。
【０００９】
また、１つの実施態様では、データ処理装置が提供される。
また、１つの実施態様では、データ処理方法が提供される。
【発明の効果】
【００１０】
１つの側面では、本発明は、ユーザが解きたい問題に適した最適化システムにより解探索が可能となる。
【図面の簡単な説明】
（【００１１】以降は省略されています）

関連特許