特許ウォッチ

公開番号2024044506
公報種別公開特許公報(A)
公開日2024-04-02
出願番号2022150067
出願日2022-09-21
発明の名称演算プログラム、演算方法、および情報処理装置
出願人富士通株式会社
代理人個人
主分類G06N 3/126 20230101AFI20240326BHJP(計算;計数)
要約【課題】計算コストを削減することができる演算プログラム、演算方法、および情報処理装置を提供する。
【解決手段】演算プログラムは、コンピュータに、配列探索を含む組合せ最適化処理の対象であって順序情報を有する個体を対象として、進化的アルゴリズムを用いて世代が進むことに応じて評価値が更新されるように前記順序情報を探索する順序探索処理と、前記順序探索処理によって探索された前記個体が有する前記順序情報を用いて配列を生成し、生成された前記配列をQUBO形式に変換して組合せを探索する組合せ探索処理と、を実行させる。
【選択図】図5

特許請求の範囲【請求項１】
コンピュータに、
配列探索を含む組合せ最適化処理の対象であって順序情報を有する個体を対象として、進化的アルゴリズムを用いて世代が進むことに応じて評価値が更新されるように前記順序情報を探索する順序探索処理と、
前記順序探索処理によって探索された前記個体が有する前記順序情報を用いて配列を生成し、生成された前記配列をＱＵＢＯ形式に変換して組合せを探索する組合せ探索処理と、
を実行させることを特徴とする演算プログラム。
続きを表示（約 1,200 文字）【請求項２】
前記順序情報は、前記個体に含まれる複数の要素の配列の順序を示す情報であり、前記組合せは、前記複数の要素の配列に関する組合せであることを特徴とする請求項１に記載の演算プログラム。
【請求項３】
前記評価値は、前記進化的アルゴリズムによって得られる個体が有する順序情報を用いて配列を生成し、生成された前記配列をＱＵＢＯ形式に変換し、組合せ最適化を実行することで得られた結果を評価することで得られる値であることを特徴とする請求項１または請求項２に記載の演算プログラム。
【請求項４】
前記コンピュータに、
前記進化的アルゴリズムによって得られる個体の前記評価値をキャッシュに格納しておき、次世代以降に得られる個体が有する配列が前記キャッシュに格納された前記個体の配列と同じときは、前記キャッシュに格納された前記評価値を読み出し、個体の評価に用いる処理を実行させることを特徴とする請求項３に記載の演算プログラム。
【請求項５】
前記進化的アルゴリズムとして、遺伝的アルゴリズムを用いることを特徴とする請求項１または請求項２に記載の演算プログラム。
【請求項６】
前記個体は、複数の化合物基が順次配置される格子の集合である格子空間に、前記複数の化合物基のいずれかが前記格子空間のいずれかの格子に配置されたことを表す個体であることを特徴とする請求項１または請求項２に記載の演算プログラム。
【請求項７】
配列探索を含む組合せ最適化処理の対象であって順序情報を有する個体を対象として、進化的アルゴリズムを用いて世代が進むことに応じて評価値が更新されるように前記順序情報を探索し、
探索された前記個体が有する前記順序情報を用いて配列を生成し、生成された前記配列をＱＵＢＯ形式に変換して組合せを探索する、
処理をコンピュータが実行することを特徴とする演算方法。
【請求項８】
前記順序情報は、前記個体に含まれる複数の要素の配列の順序を示す情報であり、前記組合せは、前記複数の要素の配列に関する組合せであることを特徴とする請求項７に記載の演算方法。
【請求項９】
配列探索を含む組合せ最適化処理の対象であって順序情報を有する個体を対象として、進化的アルゴリズムを用いて世代が進むことに応じて評価値が更新されるように前記順序情報を探索する順序探索処理部と、
前記順序探索処理部によって探索された前記個体が有する前記順序情報を用いて配列を生成し、生成された前記配列をＱＵＢＯ形式に変換して組合せを探索する組合せ探索処理部と、を備えることを特徴とする情報処理装置。
【請求項１０】
前記順序情報は、前記個体に含まれる複数の要素の配列の順序を示す情報であり、前記組合せは、前記複数の要素の配列に関する組合せであることを特徴とする請求項９に記載の情報処理装置。

発明の詳細な説明【技術分野】
【０００１】
本件は、演算プログラム、演算方法、および情報処理装置に関する。
続きを表示（約 1,800 文字）【背景技術】
【０００２】
配列探索を含む組合せ最適化を行なう技術が開示されている（例えば、特許文献１～４参照）。
【先行技術文献】
【特許文献】
【０００３】
特開２０２２－９０２４９号公報
特開２０２０－１９４２７３号公報
特開２０２１－１０３４１７号公報
特開２０１４－４４５６５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
配列探索を含む組合せ問題をＱＵＢＯ形式で表現して最適化することが求められている。しかしながら、配列探索を含む組合せ問題をＱＵＢＯ形式で表現して最適化を実行すると、計算コストが大きくなってしまう。
【０００５】
１つの側面では、本件は、計算コストを削減することができる演算プログラム、演算方法、および情報処理装置を提供することを目的とする。
【課題を解決するための手段】
【０００６】
１つの態様では、演算プログラムは、コンピュータに、配列探索を含む組合せ最適化処理の対象であって順序情報を有する個体を対象として、進化的アルゴリズムを用いて世代が進むことに応じて評価値が更新されるように前記順序情報を探索する順序探索処理と、前記順序探索処理によって探索された前記個体が有する前記順序情報を用いて配列を生成し、生成された前記配列をＱＵＢＯ形式に変換して組合せを探索する組合せ探索処理と、を実行させる。
【発明の効果】
【０００７】
計算コストを削減することができる。
【図面の簡単な説明】
【０００８】
ＱＵＢＯ形式での解の探索を例示する図である。
（ａ）は情報処理装置の全体構成を例示するブロック図であり、（ｂ）は情報処理装置のハードウェア構成を例示するブロック図である。
情報処理装置の動作の一例を表すフローチャートである。
サブフローを例示する図である。
情報処理装置の処理を視覚的に理解しやすいように整理した概要図である。
（ａ）および（ｂ）はキャッシュの利用の概要を説明するための図である。
（ａ）および（ｂ）は分子の配列および安定構造を探索する問題を例示する図である。
（ａ）～（ｅ）は各格子位置における粒子の有無をビットで表現した図である。
９（ａ）～（ｄ）は制約条件と目的関数がどうあるべきかを例示するDiamond encoding法である。
ＱＵＢＯ形式の定式化を例示する図である。
ＱＵＢＯ形式の定式化を例示する図である。
ＱＵＢＯ形式の定式化を例示する図である。
結合相互作用および非結合相互作用について示す図である。
（ａ）は配列全探索とＬＰＰを実行した場合の結果を示しており、（ｂ）は実施例に係る処理を実行した場合の結果を示している。
【発明を実施するための形態】
【０００９】
配列探索を含む組み合わせ最適化問題をＱＵＢＯ形式で表現し、ＱＵＢＯ形式で表現された最適化問題をデジタルアニーラなどのイジングマシンで効果的に最適化することが求められている。配列とは、複数の要素（値）の集合を格納および管理するために用いられるデータ構造である。
【００１０】
ここで、ＱＵＢＯ形式とは、Quadratic Unconstrained Binary Optimizationのことであり、二次制約が無く二値最適化が可能な形式のことである。ＱＵＢＯ形式は、例えば、下記式のように表現することができる。なお、ｘ
ｉ
＝０または１で（ｉ＝１，…，Ｎ）である。Ｗ
ｉｊ
は、ｘ
ｉ
とｘ
ｊ
の結合係数である。ｂ
ｉ
は、ｘ
ｉ
のバイアス係数である。右辺の第１項は、二次の項であって、相互作用を表している。右辺の第２項は、一次の項であって、バイアス作用を表している。右辺の第３項は、定数項である。ＱＵＢＯ形式では、下記式に従って、図１で例示するように、エネルギーを表すＥ（ｘ）を最小化するためのｘが探索される。
TIFF
2024044506000002.tif
24
170
（【００１１】以降は省略されています）

関連特許