特許ウォッチ

公開番号2025023395
公報種別公開特許公報(A)
公開日2025-02-17
出願番号2023127482
出願日2023-08-04
発明の名称データ処理装置、プログラム及びデータ処理方法
出願人富士通株式会社,ザガバニングカウンシルオブザユニバーシティオブトロント,THE GOVERNING COUNCIL OF THE UNIVERSITY OF TORONTO
代理人弁理士法人扶桑国際特許事務所
主分類G06N 99/00 20190101AFI20250207BHJP(計算;計数)
要約【課題】割当問題を計算するときのメモリの使用容量を削減する。
【解決手段】記憶部11は、フロー行列と距離行列の行列演算を用いて表される評価関数をもつ割当問題の、フロー行列と距離行列の一方を記憶し、処理部12は、複数の割当先に割り当てられる複数の要素のうち、第1要素と第2要素を選択し、記憶部11から、第1要素と第2要素に対応する、フロー行列と距離行列の一方の第1行列要素を読み出し、第1要素と第2要素に基づいて、フロー行列と距離行列のうちの他方であるパターン化した行列の第2行列要素を生成し、第1行列要素と第2行列要素を用いて第1要素または第2要素の割当先が変更する割当変更が生じた場合の評価関数の値の変化量を計算し、変化量に基づいて、割当変更を許容するか否かを判定し、割当変更を許容すると判定した場合、割当状態を更新する。
【選択図】図4
特許請求の範囲【請求項１】
フロー行列と距離行列の行列演算を用いて表される評価関数をもつ割当問題の、前記フロー行列と前記距離行列の一方を記憶する記憶部と、
複数の割当先に割り当てられる複数の要素のうち、第１要素と第２要素を選択し、前記記憶部から、前記第１要素と前記第２要素に対応する、前記フロー行列と前記距離行列の一方の第１行列要素を読み出し、前記第１要素と前記第２要素に基づいて、前記フロー行列と前記距離行列のうちの他方であるパターン化した行列の第２行列要素を生成し、前記第１行列要素と前記第２行列要素を用いて前記第１要素または前記第２要素の割当先が変更する割当変更が生じた場合の前記評価関数の値の変化量を計算し、前記変化量に基づいて、前記割当変更を許容するか否かを判定し、前記割当変更を許容すると判定した場合、割当状態を更新する処理部と、
を有するデータ処理装置。
続きを表示（約 1,400 文字）【請求項２】
前記第２行列要素は、前記第１要素と前記第２要素の割当先を入れ替えることによる前記割当変更が生じた場合の、前記変化量の計算に用いられる行列要素である、請求項１に記載のデータ処理装置。
【請求項３】
前記第２行列要素は、前記第１要素の第１割当先に前記第２要素を割り当てることによる前記割当変更が生じた場合の、前記変化量の計算に用いられる行列要素である、請求項１に記載のデータ処理装置。
【請求項４】
前記記憶部は、前記フロー行列と前記距離行列の一方を記憶する第１メモリと、前記距離行列の対角要素を記憶する第２メモリと、を含み、
前記処理部は、前記第１行列要素と、前記第２行列要素と、前記第２メモリから読み出された第３行列要素とに基づいて、前記変化量を計算する、
請求項１に記載のデータ処理装置。
【請求項５】
前記割当問題がＱＭＫＰの場合、前記距離行列は、対角要素の１つ以外が１であり、他の行列要素は０となるようにパターン化され、
前記処理部は、前記第１要素の第１割当先と、前記第２要素の第２割当先とに基づいて、前記距離行列の前記第２行列要素である、１または０を生成する、
請求項１に記載のデータ処理装置。
【請求項６】
フロー行列と距離行列の行列演算を用いて表される評価関数をもつ割当問題の、前記フロー行列と前記距離行列の一方をメモリに記憶し、
複数の割当先に割り当てられる複数の要素のうち、第１要素と第２要素を選択し、
前記メモリから、前記第１要素と前記第２要素に対応する、前記フロー行列と前記距離行列の一方の第１行列要素を読み出し、
前記第１要素と前記第２要素に基づいて、前記フロー行列と前記距離行列のうちの他方であるパターン化した行列の第２行列要素を生成し、
前記第１行列要素と前記第２行列要素を用いて前記第１要素または前記第２要素の割当先が変更する割当変更が生じた場合の前記評価関数の値の変化量を計算し、
前記変化量に基づいて、前記割当変更を許容するか否かを判定し、
前記割当変更を許容すると判定した場合、割当状態を更新する、
処理をコンピュータに実行させるプログラム。
【請求項７】
記憶部が、フロー行列と距離行列の行列演算を用いて表される評価関数をもつ割当問題の、前記フロー行列と前記距離行列の一方を記憶し、
処理部が、
複数の割当先に割り当てられる複数の要素のうち、第１要素と第２要素を選択し、
前記記憶部から、前記第１要素と前記第２要素に対応する、前記フロー行列と前記距離行列の一方の第１行列要素を読み出し、
前記第１要素と前記第２要素に基づいて、前記フロー行列と前記距離行列のうちの他方であるパターン化した行列の第２行列要素を生成し、
前記第１行列要素と前記第２行列要素を用いて前記第１要素または前記第２要素の割当先が変更する割当変更が生じた場合の前記評価関数の値の変化量を計算し、
前記変化量に基づいて、前記割当変更を許容するか否かを判定し、
前記割当変更を許容すると判定した場合、割当状態を更新する、
データ処理方法。

発明の詳細な説明【技術分野】
【０００１】
本発明は、データ処理装置、プログラム及びデータ処理方法に関する。
続きを表示（約 1,500 文字）【背景技術】
【０００２】
組合せ最適化問題の１つである割当問題の例として、２次割当問題（ＱＡＰ：Quadratic Assignment Problem）がある。２次割当問題は、ｎ個の要素（施設など）をｎ個の割当先に割り当てる際に、要素間のフロー量（施設間での物資の輸送量などのコスト）と、各要素が割り当てられる割当先間の距離との積の総和を最小化するような割当を求める問題である。すなわち、２次割当問題は、以下の式（１）で表される評価関数の値を最小化するような割当を探索する問題である。評価関数は割当状態に応じたコストを表し、コスト関数などとも呼ばれる。
【０００３】
TIFF
2025023395000002.tif
19
145
【０００４】
式（１）において、ｆ
ｉ，ｊ
は、識別番号＝ｉ，ｊの要素間のフロー量、ｄ
φ（ｉ），φ（ｊ）
は、識別番号＝ｉ，ｊの要素が割り当てられている割当先間の距離を示す。ｂ
ｉ，φ（ｉ）
は、バイアス係数である。バイアス係数ｂ
ｉ，φ（ｉ）
は、識別番号＝ｉの要素を識別番号＝φ（ｉ）の割当先に割り当てるための一定のコストを表している。
【０００５】
ところで、ノイマン型コンピュータが不得意とする大規模な離散最適化問題を計算する装置として、イジング型の評価関数（エネルギー関数などとも呼ばれる）を用いたイジング装置（ボルツマンマシンとも呼ばれる）がある。
【０００６】
イジング装置は、組合せ最適化問題を磁性体のスピンの振る舞いを表すイジングモデルに変換する。そして、イジング装置は、疑似焼き鈍し法やレプリカ交換法（パラレルテンパリング法などとも呼ばれる）などのマルコフ連鎖モンテカルロ法により、イジング型の評価関数の値（エネルギーに相当する）が最小となるイジングモデルの状態の探索を行う。イジングモデルの状態は、複数の状態変数の値の組合せにより表現できる。各状態変数の値として、０または１を用いることができる。
【０００７】
このようなボルツマンマシンを用いて２次割当問題を計算する技術が提案されている。
２次割当問題のイジング型の評価関数は、以下の式で表せる。
【０００８】
TIFF
2025023395000003.tif
14
145
【０００９】
式（２）において、ｘは状態変数をベクトル化したものであり、ｎ個の要素のｎ個の割当先への割当状態を表す。ｘ
Ｔ
は、（ｘ
１，１
，…，ｘ
１，ｎ
，ｘ
２，１
，…，ｘ
２，ｎ
，……，ｘ
ｎ，１
，…，ｘ
ｎ，ｎ
）と表せる。ｘ
ｉ，ｊ
＝１は、識別番号＝ｉの要素が、識別番号＝ｊの割当先に割り当てられていることを示し、ｘ
ｉ，ｊ
＝０は、識別番号＝ｉの要素が、識別番号＝ｊの割当先に割り当てられていないことを示す。
【００１０】
Ｗは、重み値の行列であり、要素間のフロー量の行列であるフロー行列と割当先間の距離の行列の行列演算で表される。重み行列Ｗは、フロー行列の各フロー量をｆ
ｉ，ｊ
と距離行列Ｄを用いて、以下の式（３）で表せる。
（【００１１】以降は省略されています）

関連特許