特許ウォッチ

公開番号2025036675
公報種別公開特許公報(A)
公開日2025-03-14
出願番号2024231484,2023564832
出願日2024-12-27,2022-11-07
発明の名称最適化装置、最適化方法および最適化プログラム
出願人日本電気株式会社
代理人個人,個人
主分類G06N 99/00 20190101AFI20250306BHJP(計算;計数)
要約【課題】QUBOモデル化された最適化問題に応じて適切な最適化処理を実施できる最適化装置を提供する。
【解決手段】最適化装置90は、判別手段91と、最適化手段92とを備えている。判別手段91は、二次元的なワンホット条件を制約条件として含む組合せ最適化問題をQUBOモデル化して得られるQUBO行列から、その組合せ最適化問題の種類を判別する。最適化手段92は、判別された組合せ最適化問題の種類に応じた最適化処理を行う。
【選択図】図41
特許請求の範囲【請求項１】
二次元的なワンホット条件を制約条件として含む組合せ最適化問題をＱＵＢＯモデル化して得られるＱＵＢＯ行列から、組合せ最適化問題の種類に応じて、０でない成分を含む正方行列であるブロックを抽出する問題分割手段と、
抽出された前記ブロックの各成分行列が示す問題であるサブ問題を、もとの組合せ最適化問題に応じて決定される方法により最適化を行うサブ問題最適化手段と、
得られたサブ問題の最適化結果を結合した新たな組合せ最適化問題であるスーパー問題に定式化する問題結合手段と、
前記スーパー問題の最適化処理を行うスーパー問題最適化手段とを備え、
前記問題結合手段は、前記サブ問題で最適化したそれぞれの地域の順序のうち、順序が連続する２都市を当該地域ごとに選択し、地域ごとに選択された２都市を訪問する巡回セールスマン問題を新たな組合せ最適化問題として定式化し、
前記スーパー問題最適化手段は、最適化された前記組合せ最適化問題の最適化結果に、地域ごとに最適化された最適化結果を挿入する
ことを特徴とする最適化装置。
続きを表示（約 3,100 文字）【請求項２】
問題分割手段は、クラスタリングを行う基準とするブロックを特定し、特定されたブロックの二次元配列で表わされた変数のインデックスに関して縦方向および横方向に対してクラスタリングの可否を試行し、
スーパー問題最適化手段は、二次元配列で表わされた変数のインデックスに関して縦方向または横方向のうちのいずれか一方のクラスタリングの試行の結果に応じて、他方のクラスタリングのインデックスの値を１ずつ変更しながら最適化処理を繰り返す
請求項１記載の最適化装置。
【請求項３】
二次元的なワンホット条件を制約条件として含む組合せ最適化問題をＱＵＢＯモデル化して得られるＱＵＢＯ行列から、組合せ最適化問題の種類に応じて、０でない成分を含む正方行列であるブロックを抽出する問題分割手段と、
抽出された前記ブロックの各成分行列が示す問題であるサブ問題を、もとの組合せ最適化問題に応じて決定される方法により最適化を行うサブ問題最適化手段と、
得られたサブ問題の最適化結果を結合した新たな組合せ最適化問題であるスーパー問題に定式化する問題結合手段と、
前記スーパー問題の最適化処理を行うスーパー問題最適化手段とを備え、
前記問題分割手段は、製品の順番の制約に関し、ＱＵＢＯ行列から前記サブ問題の製品間の制約に関するブロックを抽出し、
前記サブ問題最適化手段は、抽出されたブロックの目的関数のＱＵＢＯ行列に、二次元的なワンホット条件を加えた前記サブ問題を最適化し、
前記問題結合手段は、前記サブ問題の最適解として導出された順において、最初の製品と最後の製品とを使用して、前記サブ問題同士の順番を決定する問題として定式化し、
前記スーパー問題最適化手段は、生成された前記サブ問題同士の順番を決定するスーパー問題を最適化する
ことを特徴とする最適化装置。
【請求項４】
問題分割手段は、抽出したブロックの先頭行の成分の値が昇順になるようにインデックスをソートしたブロックを生成し、隣接する成分の比または差が予め定めた閾値を超える場合、当該隣接する左側の成分までの行を含む正方行列を分割して新たなブロックを生成する
請求項３記載の最適化装置。
【請求項５】
問題分割手段は、変数のインデックスの集合であるクラスタのＱＵＢＯ行列の成分の和の平均をクラスタ間の距離と定義し、当該距離の近いクラスタ同士を結合して、予め定めた条件を満たすまでクラスタを結合する処理を繰り返すことによりブロックを分割する
請求項３記載の最適化装置。
【請求項６】
二次元的なワンホット条件を制約条件として含む組合せ最適化問題をＱＵＢＯモデル化して得られるＱＵＢＯ行列から、組合せ最適化問題の種類に応じて、０でない成分を含む正方行列であるブロックを抽出し、
抽出された前記ブロックの各成分行列が示す問題であるサブ問題を、もとの組合せ最適化問題に応じて決定される方法により最適化を行い、
得られたサブ問題の最適化結果を結合した新たな組合せ最適化問題であるスーパー問題に定式化し、
前記スーパー問題の最適化処理を行い、
前記スーパー問題の定式化において、前記サブ問題で最適化したそれぞれの地域の順序のうち、順序が連続する２都市を当該地域ごとに選択し、地域ごとに選択された２都市を訪問する巡回セールスマン問題を新たな組合せ最適化問題として定式化し、
前記スーパー問題の最適化処理において、最適化された前記組合せ最適化問題の最適化結果に、地域ごとに最適化された最適化結果を挿入する
ことを特徴とする最適化方法。
【請求項７】
二次元的なワンホット条件を制約条件として含む組合せ最適化問題をＱＵＢＯモデル化して得られるＱＵＢＯ行列から、組合せ最適化問題の種類に応じて、０でない成分を含む正方行列であるブロックを抽出し、
抽出された前記ブロックの各成分行列が示す問題であるサブ問題を、もとの組合せ最適化問題に応じて決定される方法により最適化を行い、
得られたサブ問題の最適化結果を結合した新たな組合せ最適化問題であるスーパー問題に定式化し、
前記スーパー問題の最適化処理を行い、
前記スーパー問題の定式化において、製品の順番の制約に関し、ＱＵＢＯ行列から前記サブ問題の製品間の制約に関するブロックを抽出し、
抽出されたブロックの目的関数のＱＵＢＯ行列に、二次元的なワンホット条件を加えた前記サブ問題を最適化し、
前記サブ問題の最適解として導出された順において、最初の製品と最後の製品とを使用して、前記サブ問題同士の順番を決定する問題として定式化し、
生成された前記サブ問題同士の順番を決定するスーパー問題を最適化する
ことを特徴とする最適化方法。
【請求項８】
コンピュータに、
二次元的なワンホット条件を制約条件として含む組合せ最適化問題をＱＵＢＯモデル化して得られるＱＵＢＯ行列から、組合せ最適化問題の種類に応じて、０でない成分を含む正方行列であるブロックを抽出する問題分割処理、
抽出された前記ブロックの各成分行列が示す問題であるサブ問題を、もとの組合せ最適化問題に応じて決定される方法により最適化を行うサブ問題最適化処理、
得られたサブ問題の最適化結果を結合した新たな組合せ最適化問題であるスーパー問題に定式化する問題結合処理、および、
前記スーパー問題の最適化処理を行うスーパー問題最適化処理を実行させ、
前記問題結合処理で、前記サブ問題で最適化したそれぞれの地域の順序のうち、順序が連続する２都市を当該地域ごとに選択させ、地域ごとに選択された２都市を訪問する巡回セールスマン問題を新たな組合せ最適化問題として定式化させ、
前記スーパー問題最適化処理で、最適化された前記組合せ最適化問題の最適化結果に、地域ごとに最適化された最適化結果を挿入させる
ための最適化プログラム。
【請求項９】
コンピュータに、
二次元的なワンホット条件を制約条件として含む組合せ最適化問題をＱＵＢＯモデル化して得られるＱＵＢＯ行列から、組合せ最適化問題の種類に応じて、０でない成分を含む正方行列であるブロックを抽出する問題分割処理、
抽出された前記ブロックの各成分行列が示す問題であるサブ問題を、もとの組合せ最適化問題に応じて決定される方法により最適化を行うサブ問題最適化処理、
得られたサブ問題の最適化結果を結合した新たな組合せ最適化問題であるスーパー問題に定式化する問題結合処理、および、
前記スーパー問題の最適化処理を行うスーパー問題最適化処理を実行させ、
前記問題分割処理で、製品の順番の制約に関し、ＱＵＢＯ行列から前記サブ問題の製品間の制約に関するブロックを抽出させ、
前記サブ問題最適化処理で、抽出されたブロックの目的関数のＱＵＢＯ行列に、二次元的なワンホット条件を加えた前記サブ問題を最適化させ、
前記問題結合処理で、前記サブ問題の最適解として導出された順において、最初の製品と最後の製品とを使用して、前記サブ問題同士の順番を決定する問題として定式化させ、
前記スーパー問題最適化処理で、生成された前記サブ問題同士の順番を決定するスーパー問題を最適化させる
ための最適化プログラム。

発明の詳細な説明【技術分野】
【０００１】
本発明は、組合せ最適化問題に応じた最適化を行う最適化装置、最適化方法および最適化プログラムに関する。
続きを表示（約 1,600 文字）【背景技術】
【０００２】
組合せ最適化問題は、組合せに関する選択肢の中から、ある指標に基づいて最も良い組合せを探そうとする問題であり、様々な制約の下で所定の指標を最適化する変数の値の組合せを導出する問題である。組合せ最適化問題は、日常の様々な場面に適用される問題であるが、その問題の特性上、規模が大きくなると計算量が爆発することも知られている。
【０００３】
このような問題を解決するため、近年、最適化問題をシミュレーテッドアニーリング（Simulated Annealing 。以下、ＳＡと記すこともある。）や量子アニーリングにより解く方法が各種提案されている。例えば、特許文献１には、生産性が最大になる生産計画を作成する生産計画方法が記載されている。特許文献１に記載された方法では、製品の生産計画作成問題に関する目的関数及び制約条件をＱＵＢＯ（Quadratic Unconstrained Binary Optimization：制約なし二次バイナリ最適化）モデルもしくはイジングモデルに定式化し、アニーリングマシンを用いて最適解を取得する。
【０００４】
なお、非特許文献１には、イジングマシンを用いた制約付きスロット配置問題の解決方法が記載されている。
【先行技術文献】
【特許文献】
【０００５】
特開２０２０－１４０６１５号公報
【非特許文献】
【０００６】
Sho KANAMARU, Kazushi KAWAMURA, Shu TANAKA, Yoshinori TOMITA, Nozomu TOGAWA, "Solving Constrained Slot Placement Problems Using an Ising Machine and Its Evaluations", IEICE Transactions on Information and Systems, Volume E104.D, Issue 2, Pages 226-236, 2021
【発明の概要】
【発明が解決しようとする課題】
【０００７】
イジングモデルは、結晶を構成する原子のスピンの向きを計算する簡易的なモデルであり、組合せ最適化問題の定式化の一つである。また、ＱＵＢＯモデルも、組合せ最適化問題の定式化の一つであり、ＱＵＢＯモデルの係数を表わす行列は、ＱＵＢＯ行列と呼ばれる。ＱＵＢＯモデルとイジングモデルは一対一に変形できるため、ＱＵＢＯモデル化された組合せ最適化問題は、アニーリングマシンで解くことが可能である。
【０００８】
そして、ＱＵＢＯモデル化された組合せ最適化問題をそのままアニーリングマシンで解くことも原理的には可能である。しかし、組合せ最適化問題の単純なＱＵＢＯモデルを用いた場合、最適解に近い解が得にくい場合も存在し、また、多くの時間を要してしまう可能性もある。
【０００９】
特許文献１に記載された方法では、生産ラインにおける生産計画を時空間ネットワークモデルで定式化した組合せ最適化問題をＱＵＢＯモデルもしくはイジングモデルに変換して最適解を導出する。しかし、このように定式化された組合せ最適化問題を変換したＱＵＢＯモデルを解く場合にも、上記のような可能性が存在することから、より適切に最適化する方法は不明である。そのため、ＱＵＢＯモデル化された最適化問題に応じて、より適切な最適化処理を実施できることが好ましい。
【００１０】
そこで、本発明は、ＱＵＢＯモデル化された最適化問題に応じて適切な最適化処理を実施できる最適化装置、最適化方法および最適化プログラムを提供することを目的とする。
【課題を解決するための手段】
（【００１１】以降は省略されています）

関連特許