特許ウォッチ

公開番号2025007989
公報種別公開特許公報(A)
公開日2025-01-20
出願番号2023109786
出願日2023-07-04
発明の名称プログラム、データ処理方法およびデータ処理装置
出願人富士通株式会社
代理人弁理士法人扶桑国際特許事務所
主分類G06N 99/00 20190101AFI20250109BHJP(計算;計数)
要約【課題】求解を効率化する。
【解決手段】記憶部11は、複数のアイテムを領域R1に配置する問題を示す情報を記憶する。処理部12は、複数のアイテムそれぞれに対し、当該アイテムを領域R1に配置する位置に応じた複数の状態を、当該情報に基づいて生成する。処理部12は、複数のアイテムに含まれる2つのアイテムのペアを複数特定する。処理部12は、特定された複数のペアにおける2つのアイテムの状態の組合せに応じた評価値を示す評価関数を計算する。処理部12は、複数のアイテムの状態の組合せに対して、評価関数により示される、複数のペアの各々の評価値の和を示すコスト項を含む、イジング型の目的関数を生成する。処理部12は、目的関数に基づいて解の探索を行う探索部13を用いて問題に対応する解を取得する。
【選択図】図1
特許請求の範囲【請求項１】
コンピュータに、
複数のアイテムを所定の領域に配置する問題を示す情報を取得し、
前記複数のアイテムそれぞれに対し、当該アイテムを前記領域に配置する位置に応じた複数の状態を、前記情報に基づいて生成し、
前記複数のアイテムに含まれる２つのアイテムのペアを複数特定し、特定された複数の前記ペアにおける前記２つのアイテムの状態の組合せに応じた評価値を示す評価関数を計算し、
前記複数のアイテムの状態の組合せに対して、前記評価関数により示される、複数の前記ペアの各々の前記評価値の和を示すコスト項を含む、イジング型の目的関数を生成し、
前記目的関数に基づいて解の探索を行う探索部を用いて前記問題に対応する前記解を取得する、
処理を実行させるプログラム。
続きを表示（約 1,400 文字）【請求項２】
前記複数の状態の生成では、前記複数のアイテムの各々を配置する座標および回転の有無により前記状態を表すデータを生成する、
処理を前記コンピュータに実行させる請求項１記載のプログラム。
【請求項３】
前記評価関数の計算では、前記２つのアイテムの重なりの大きさを示す第１評価関数、および、前記２つのアイテムにより形成される閉鎖領域の大きさを示す第２評価関数の少なくとも一方を計算する、
処理を前記コンピュータに実行させる請求項１記載のプログラム。
【請求項４】
前記評価関数の計算では、複数の評価関数を計算し、
前記目的関数の生成では、前記複数の評価関数に対応する複数のコスト項の線形結合を含む前記目的関数を生成する、
処理を前記コンピュータに実行させる請求項１記載のプログラム。
【請求項５】
前記目的関数は、１つのアイテムが同時に取り得る状態が１つであることを表す制約項を含む、
請求項１記載のプログラム。
【請求項６】
前記情報は、前記複数のアイテムおよび前記領域のそれぞれを示すビットマップを含む、
請求項１記載のプログラム。
【請求項７】
前記問題の元になる他の問題における前記複数のアイテムの形状および前記領域の形状をビットマップ化することで、前記情報を生成し、
前記問題に対応する前記解を取得すると、前記解に基づいて前記他の問題の初期解を生成し、前記初期解を用いて前記他の問題の求解を行う、
処理を前記コンピュータに実行させる請求項６記載のプログラム。
【請求項８】
コンピュータが、
複数のアイテムを所定の領域に配置する問題を示す情報を取得し、
前記複数のアイテムそれぞれに対し、当該アイテムを前記領域に配置する位置に応じた複数の状態を、前記情報に基づいて生成し、
前記複数のアイテムに含まれる２つのアイテムのペアを複数特定し、特定された複数の前記ペアにおける前記２つのアイテムの状態の組合せに応じた評価値を示す評価関数を計算し、
前記複数のアイテムの状態の組合せに対して、前記評価関数により示される、複数の前記ペアの各々の前記評価値の和を示すコスト項を含む、イジング型の目的関数を生成し、
前記目的関数に基づいて解の探索を行う探索部を用いて前記問題に対応する前記解を取得する、
データ処理方法。
【請求項９】
複数のアイテムを所定の領域に配置する問題を示す情報を記憶する記憶部と、
前記複数のアイテムそれぞれに対し、当該アイテムを前記領域に配置する位置に応じた複数の状態を、前記記憶部に記憶された前記情報に基づいて生成し、前記複数のアイテムに含まれる２つのアイテムのペアを複数特定し、特定された複数の前記ペアにおける前記２つのアイテムの状態の組合せに応じた評価値を示す評価関数を計算し、前記複数のアイテムの状態の組合せに対して、前記評価関数により示される、複数の前記ペアの各々の前記評価値の和を示すコスト項を含む、イジング型の目的関数を生成し、前記目的関数に基づいて解の探索を行う探索部を用いて前記問題に対応する前記解を取得する処理部と、
を有するデータ処理装置。

発明の詳細な説明【技術分野】
【０００１】
本発明はプログラム、データ処理方法およびデータ処理装置に関する。
続きを表示（約 1,600 文字）【背景技術】
【０００２】
組合せ最適化問題を計算する装置として、イジング型の目的関数に基づいて解を探索するイジングマシンがある。目的関数は、ＱＵＢＯ（Quadratic Unconstrained Binary Optimization）形式で表される。目的関数は、エネルギー関数と言われることもある。イジングマシンによる求解では、例えば、シミュレーテッドアニーリング（ＳＡ：Simulated Annealing）や量子アニーリング（ＱＡ：Quantum Annealing）などが用いられる。イジングマシンは、ＱＵＢＯソルバの一種である。
【０００３】
例えば、多目的最適化問題をＳＡやＱＡなどのアニーリングにより解く最適化装置の提案がある。提案の最適化装置は、アニーリングの最適解に至る複数の途中解に基づいて、多点探索法による解探索を実行することで、少なくとも１つの目的関数に対して満足できる値を有する解が複数の目的関数に対して満遍なく得られるようにする。
【０００４】
なお、勾配降下法などの最適化アルゴリズムにより解決済の問題とその解を用いた機械学習により、当該最適化アルゴリズムで用いる最適な初期化値を得るための初期化規則を学習するシステムの提案がある。
【０００５】
また、量子クエンチアルゴリズムと呼ばれる手法により組合せ最適化問題の解を得るシステムの提案がある。更に、最適解を得るための演算を簡略化した簡易演算により、最適解ではないが最適解に近似する複数の近似解を求め、近似解を含む解群を初期個体群とした遺伝的アルゴリズムにより最適解を探索する最適解探索装置の提案がある。
【先行技術文献】
【特許文献】
【０００６】
特開２０２２－１１８５５５号公報
米国特許出願公開第２０２２／０１６４６４４号明細書
米国特許出願公開第２０２０／０２０２２４９号明細書
特開２０２２－７９３７６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
組合せ最適化問題として、複数のアイテムを所定の領域に配置する問題がある。このような問題の一例としてパッキング問題やスケジューリング問題などがある。しかし、当該問題におけるアイテムの形状や、配置可能な位置などの制約条件をＱＵＢＯで正確に表現するのが難しく、イジングマシンを用いた求解を効率的に行えないことがある。
【０００８】
１つの側面では、本発明は、求解を効率化することを目的とする。
【課題を解決するための手段】
【０００９】
１つの態様では、プログラムが提供される。このプログラムは、次の処理をコンピュータに実行させる。コンピュータは、複数のアイテムを所定の領域に配置する問題を示す情報を取得する。コンピュータは、複数のアイテムそれぞれに対し、当該アイテムを領域に配置する位置に応じた複数の状態を、当該情報に基づいて生成する。コンピュータは、複数のアイテムに含まれる２つのアイテムのペアを複数特定し、特定された複数のペアにおける２つのアイテムの状態の組合せに応じた評価値を示す評価関数を計算する。コンピュータは、複数のアイテムの状態の組合せに対して、評価関数により示される、複数のペアの各々の評価値の和を示すコスト項を含む、イジング型の目的関数を生成する。コンピュータは、目的関数に基づいて解の探索を行う探索部を用いて問題に対応する解を取得する。
【００１０】
また、１つの態様では、コンピュータによって実行されるデータ処理方法が提供される。また、１つの態様では、記憶部と処理部とを有するデータ処理装置が提供される。
【発明の効果】
（【００１１】以降は省略されています）

関連特許