特許ウォッチ

公開番号2024164601
公報種別公開特許公報(A)
公開日2024-11-27
出願番号2023080206
出願日2023-05-15
発明の名称情報処理システム、情報処理方法及びプログラム
出願人富士通株式会社
代理人弁理士法人扶桑国際特許事務所
主分類G06N 99/00 20190101AFI20241120BHJP(計算;計数)
要約【課題】制約係数の決定にかかる時間を短縮する。
【解決手段】制約条件を含む組合せ最適化問題を、コスト項と制約条件に対応する制約項との和で表されるイジングモデルのエネルギー関数に基づいて計算する情報処理システム10における処理部12が、組合せ最適化問題の問題情報を取得し、問題情報に基づいて、制約条件を満たす解から制約条件を満たさない解への遷移が生じた場合のコスト項の変化量の期待値を計算し、期待値に基づいて制約項の係数を決定し、決定した係数を用いてエネルギー関数の情報を出力する。
【選択図】図1
特許請求の範囲【請求項１】
制約条件を含む組合せ最適化問題を、コスト項と前記制約条件に対応する制約項との和で表されるイジングモデルのエネルギー関数に基づいて計算する情報処理システムであって、
前記組合せ最適化問題の問題情報を取得し、前記問題情報に基づいて、前記制約条件を満たす解から前記制約条件を満たさない解への遷移が生じた場合の前記コスト項の変化量の期待値を計算し、前記期待値に基づいて前記制約項の係数を決定し、決定した前記係数を用いて前記エネルギー関数の情報を出力する処理部と、
出力された前記情報に基づいて、前記イジングモデルの基底状態を探索する探索部と、
を有する情報処理システム。
続きを表示（約 1,300 文字）【請求項２】
前記組合せ最適化問題は二次割当て問題であり、
前記処理部は、前記二次割当て問題の前記問題情報を表す第１の行列と第２の行列とのクロネッカー積によって得られる第３の行列を計算し、前記第３の行列に含まれる要素の第１の平均値に基づいて前記期待値を計算する、請求項１に記載の情報処理システム。
【請求項３】
前記処理部は、前記期待値に調整係数を乗ずることで、前記係数を計算する、請求項１に記載の情報処理システム。
【請求項４】
前記処理部が、前記期待値に前記調整係数を乗じて得られた前記係数を用いて定式化した前記エネルギー関数の前記情報を出力し、
前記探索部が、前記情報に基づいて行った前記基底状態の探索結果を出力し、
前記処理部が、前記調整係数を増加または減少させる、
処理を前記調整係数が上限または下限に達するまで繰返し、
前記処理部は、前記調整係数が上限または前記下限に達した場合、前記探索結果に基づいて、前記調整係数を決定する、
請求項３に記載の情報処理システム。
【請求項５】
前記第３の行列は、前記第１の行列または前記第２の行列のうちの一方の行列に含まれる各要素と、他方の行列との積による複数の小行列を含み、
前記処理部は、前記複数の小行列のそれぞれにおいて、前記複数の小行列のそれぞれに含まれる要素の第２の平均値と前記第１の平均値との差分値を、前記複数の小行列のそれぞれに含まれる前記要素の値に加算または減算することで、前記第１の平均値と前記第２の平均値とを一致させる、
請求項２に記載の情報処理システム。
【請求項６】
制約条件を含む組合せ最適化問題を、コスト項と前記制約条件に対応する制約項との和で表されるイジングモデルのエネルギー関数に基づいて計算する情報処理方法であって、
処理部が、前記組合せ最適化問題の問題情報を取得し、前記問題情報に基づいて、前記制約条件を満たす解から前記制約条件を満たさない解への遷移が生じた場合の前記コスト項の変化量の期待値を計算し、前記期待値に基づいて前記制約項の係数を決定し、決定した前記係数を用いて前記エネルギー関数の情報を出力し、
探索部が、出力された前記情報に基づいて、前記イジングモデルの基底状態を探索する、
情報処理方法。
【請求項７】
制約条件を含む組合せ最適化問題を、コスト項と前記制約条件に対応する制約項との和で表されるイジングモデルのエネルギー関数に基づいて計算する情報処理システムに用いられるコンピュータに、
前記組合せ最適化問題の問題情報を取得し、前記問題情報に基づいて、前記制約条件を満たす解から、前記制約条件を満たさない解への遷移が生じた場合の前記コスト項の変化量の期待値を計算し、
前記期待値に基づいて前記制約項の係数を決定し、
決定した前記係数を用いて前記エネルギー関数の情報を、前記情報に基づいて前記イジングモデルの基底状態を探索する探索部に出力する、
処理を実行させるプログラム。

発明の詳細な説明【技術分野】
【０００１】
本発明は、情報処理システム、情報処理方法及びプログラムに関する。
続きを表示（約 2,000 文字）【背景技術】
【０００２】
ノイマン型コンピュータが不得意とする多変数の組合せ最適化問題を、磁性体のスピンの振る舞いを表すモデルであるイジングモデルに置き換えて計算するイジングマシン（ボルツマンマシンとも呼ばれる）がある。イジングモデルに置き換えられた問題を実用的な時間で解く手法には、たとえば、シミュレーテッドアニーリング（ＳＡ：Simulated Annealing）法やレプリカ交換法などのマルコフ連鎖モンテカルロ（ＭＣＭＣ：Markov Chain Monte Carlo）法がある。組合せ最適化問題は、複数の状態変数を含むエネルギー関数により定式化される。たとえば、情報処理装置は、ＭＣＭＣ法を用いて状態変数の値を変化させることによる状態遷移を繰り返し試行することで、エネルギー関数の値が最小となるイジングモデルの基底状態を探索する。基底状態は組合せ最適化問題の最適解に対応する。
【０００３】
エネルギー関数は、コスト項と制約項との和で表すことができる（たとえば、特許文献１，２参照）。エネルギー関数（Ｅ（ｘ））は、たとえば、以下の式（１）で表せる。
【０００４】
TIFF
2024164601000002.tif
10
147
【０００５】
式（１）において、ｘはｘ＝（ｘ
１
，ｘ
２
，…，ｘ
ｎ
）のバイナリ変数である状態変数によるベクトルである。Ｃ（ｘ）はコスト項であり、最小化したい目的関数である。αＰ（ｘ）は制約項である。組合せ最適化問題が満たすべき制約条件を満たすとき（制約充足時）には、Ｐ（ｘ）＝０となり、制約条件を満たさないとき（制約違反時）には、Ｐ（ｘ）＞０となる。αは、制約係数であり、０より大きい値をもつ。このような制約項をコスト項に加えることで、制約条件を満たさない解（制約違反解）が選ばれにくくなる。
【０００６】
なお、エネルギー関数の符号を変えれば、エネルギー関数の値が最大となるイジングモデルの状態を探索することもできる。
組合せ最適化問題の実用的な問題の例として、二次割当問題（ＱＡＰ：Quadratic Assignment Problem）が挙げられる。ＱＡＰは、ｎ個の割当要素（施設など）をｎ個の割当先（場所など）に割り当てる際に、割当要素間のフロー量（施設間での物資の輸送量などのコスト）と、各割当要素が割り当てられる割当先間の距離との積の総和を最小化するような割当を求める問題である。割当要素間のフロー量と、各割当先間の距離とはそれぞれ行列を用いて表せる。また、ＱＡＰには、全ての割当要素を、互いに異なる割当先に割り当てる、という制約条件が課される。
【０００７】
ところで、上記のような制約係数（式（１）の場合はα）は、小さすぎると制約違反解が発生しやすくなり、逆に大きすぎると制約充足解間のエネルギー障壁が大きくなって解空間の探索に支障をきたす。また、適切な制約係数の値は個々の問題に依存して大きく異なる。従来、イジングマシンによる組合せ最適化問題の解の探索結果に基づいて、制約係数を調整する処理を繰り返すことで、制約係数を最適化していく手法が提案されている。
【先行技術文献】
【特許文献】
【０００８】
国際公開第２０２１－０４４５１６号
特開２００４－１１０８３１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかし、従来の手法で、高品質の解を得るために広範囲での探索ができるような制約係数を得るには多数回の調整が必要となる場合があり、制約係数の決定に時間がかかる。
１つの側面では、本発明は、制約係数の決定にかかる時間を短縮可能な情報処理システム、情報処理方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
１つの実施態様では、制約条件を含む組合せ最適化問題を、コスト項と前記制約条件に対応する制約項との和で表されるイジングモデルのエネルギー関数に基づいて計算する情報処理システムであって、前記組合せ最適化問題の問題情報を取得し、前記問題情報に基づいて、前記制約条件を満たす解から前記制約条件を満たさない解への遷移が生じた場合の前記コスト項の変化量の期待値を計算し、前記期待値に基づいて前記制約項の係数を決定し、決定した前記係数を用いて前記エネルギー関数の情報を出力する処理部と、出力された前記情報に基づいて、前記イジングモデルの基底状態を探索する探索部と、を有する情報処理システムが提供される。
（【００１１】以降は省略されています）

関連特許