TOP
|
特許
|
意匠
|
商標
特許ウォッチ
Twitter
他の特許を見る
10個以上の画像は省略されています。
公開番号
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
特許請求の範囲
【請求項1】
二次元的なワンホット条件を制約条件として含む組合せ最適化問題をQUBOモデル化して得られるQUBO行列から、組合せ最適化問題の種類に応じて、0でない成分を含む正方行列であるブロックを抽出する問題分割手段と、
抽出された前記ブロックの各成分行列が示す問題であるサブ問題を、もとの組合せ最適化問題に応じて決定される方法により最適化を行うサブ問題最適化手段と、
得られたサブ問題の最適化結果を結合した新たな組合せ最適化問題であるスーパー問題に定式化する問題結合手段と、
前記スーパー問題の最適化処理を行うスーパー問題最適化手段とを備え、
前記問題結合手段は、前記サブ問題で最適化したそれぞれの地域の順序のうち、順序が連続する2都市を当該地域ごとに選択し、地域ごとに選択された2都市を訪問する巡回セールスマン問題を新たな組合せ最適化問題として定式化し、
前記スーパー問題最適化手段は、最適化された前記組合せ最適化問題の最適化結果に、地域ごとに最適化された最適化結果を挿入する
ことを特徴とする最適化装置。
続きを表示(約 3,100 文字)
【請求項2】
問題分割手段は、クラスタリングを行う基準とするブロックを特定し、特定されたブロックの二次元配列で表わされた変数のインデックスに関して縦方向および横方向に対してクラスタリングの可否を試行し、
スーパー問題最適化手段は、二次元配列で表わされた変数のインデックスに関して縦方向または横方向のうちのいずれか一方のクラスタリングの試行の結果に応じて、他方のクラスタリングのインデックスの値を1ずつ変更しながら最適化処理を繰り返す
請求項1記載の最適化装置。
【請求項3】
二次元的なワンホット条件を制約条件として含む組合せ最適化問題をQUBOモデル化して得られるQUBO行列から、組合せ最適化問題の種類に応じて、0でない成分を含む正方行列であるブロックを抽出する問題分割手段と、
抽出された前記ブロックの各成分行列が示す問題であるサブ問題を、もとの組合せ最適化問題に応じて決定される方法により最適化を行うサブ問題最適化手段と、
得られたサブ問題の最適化結果を結合した新たな組合せ最適化問題であるスーパー問題に定式化する問題結合手段と、
前記スーパー問題の最適化処理を行うスーパー問題最適化手段とを備え、
前記問題分割手段は、製品の順番の制約に関し、QUBO行列から前記サブ問題の製品間の制約に関するブロックを抽出し、
前記サブ問題最適化手段は、抽出されたブロックの目的関数のQUBO行列に、二次元的なワンホット条件を加えた前記サブ問題を最適化し、
前記問題結合手段は、前記サブ問題の最適解として導出された順において、最初の製品と最後の製品とを使用して、前記サブ問題同士の順番を決定する問題として定式化し、
前記スーパー問題最適化手段は、生成された前記サブ問題同士の順番を決定するスーパー問題を最適化する
ことを特徴とする最適化装置。
【請求項4】
問題分割手段は、抽出したブロックの先頭行の成分の値が昇順になるようにインデックスをソートしたブロックを生成し、隣接する成分の比または差が予め定めた閾値を超える場合、当該隣接する左側の成分までの行を含む正方行列を分割して新たなブロックを生成する
請求項3記載の最適化装置。
【請求項5】
問題分割手段は、変数のインデックスの集合であるクラスタのQUBO行列の成分の和の平均をクラスタ間の距離と定義し、当該距離の近いクラスタ同士を結合して、予め定めた条件を満たすまでクラスタを結合する処理を繰り返すことによりブロックを分割する
請求項3記載の最適化装置。
【請求項6】
二次元的なワンホット条件を制約条件として含む組合せ最適化問題をQUBOモデル化して得られるQUBO行列から、組合せ最適化問題の種類に応じて、0でない成分を含む正方行列であるブロックを抽出し、
抽出された前記ブロックの各成分行列が示す問題であるサブ問題を、もとの組合せ最適化問題に応じて決定される方法により最適化を行い、
得られたサブ問題の最適化結果を結合した新たな組合せ最適化問題であるスーパー問題に定式化し、
前記スーパー問題の最適化処理を行い、
前記スーパー問題の定式化において、前記サブ問題で最適化したそれぞれの地域の順序のうち、順序が連続する2都市を当該地域ごとに選択し、地域ごとに選択された2都市を訪問する巡回セールスマン問題を新たな組合せ最適化問題として定式化し、
前記スーパー問題の最適化処理において、最適化された前記組合せ最適化問題の最適化結果に、地域ごとに最適化された最適化結果を挿入する
ことを特徴とする最適化方法。
【請求項7】
二次元的なワンホット条件を制約条件として含む組合せ最適化問題をQUBOモデル化して得られるQUBO行列から、組合せ最適化問題の種類に応じて、0でない成分を含む正方行列であるブロックを抽出し、
抽出された前記ブロックの各成分行列が示す問題であるサブ問題を、もとの組合せ最適化問題に応じて決定される方法により最適化を行い、
得られたサブ問題の最適化結果を結合した新たな組合せ最適化問題であるスーパー問題に定式化し、
前記スーパー問題の最適化処理を行い、
前記スーパー問題の定式化において、製品の順番の制約に関し、QUBO行列から前記サブ問題の製品間の制約に関するブロックを抽出し、
抽出されたブロックの目的関数のQUBO行列に、二次元的なワンホット条件を加えた前記サブ問題を最適化し、
前記サブ問題の最適解として導出された順において、最初の製品と最後の製品とを使用して、前記サブ問題同士の順番を決定する問題として定式化し、
生成された前記サブ問題同士の順番を決定するスーパー問題を最適化する
ことを特徴とする最適化方法。
【請求項8】
コンピュータに、
二次元的なワンホット条件を制約条件として含む組合せ最適化問題をQUBOモデル化して得られるQUBO行列から、組合せ最適化問題の種類に応じて、0でない成分を含む正方行列であるブロックを抽出する問題分割処理、
抽出された前記ブロックの各成分行列が示す問題であるサブ問題を、もとの組合せ最適化問題に応じて決定される方法により最適化を行うサブ問題最適化処理、
得られたサブ問題の最適化結果を結合した新たな組合せ最適化問題であるスーパー問題に定式化する問題結合処理、および、
前記スーパー問題の最適化処理を行うスーパー問題最適化処理を実行させ、
前記問題結合処理で、前記サブ問題で最適化したそれぞれの地域の順序のうち、順序が連続する2都市を当該地域ごとに選択させ、地域ごとに選択された2都市を訪問する巡回セールスマン問題を新たな組合せ最適化問題として定式化させ、
前記スーパー問題最適化処理で、最適化された前記組合せ最適化問題の最適化結果に、地域ごとに最適化された最適化結果を挿入させる
ための最適化プログラム。
【請求項9】
コンピュータに、
二次元的なワンホット条件を制約条件として含む組合せ最適化問題をQUBOモデル化して得られるQUBO行列から、組合せ最適化問題の種類に応じて、0でない成分を含む正方行列であるブロックを抽出する問題分割処理、
抽出された前記ブロックの各成分行列が示す問題であるサブ問題を、もとの組合せ最適化問題に応じて決定される方法により最適化を行うサブ問題最適化処理、
得られたサブ問題の最適化結果を結合した新たな組合せ最適化問題であるスーパー問題に定式化する問題結合処理、および、
前記スーパー問題の最適化処理を行うスーパー問題最適化処理を実行させ、
前記問題分割処理で、製品の順番の制約に関し、QUBO行列から前記サブ問題の製品間の制約に関するブロックを抽出させ、
前記サブ問題最適化処理で、抽出されたブロックの目的関数のQUBO行列に、二次元的なワンホット条件を加えた前記サブ問題を最適化させ、
前記問題結合処理で、前記サブ問題の最適解として導出された順において、最初の製品と最後の製品とを使用して、前記サブ問題同士の順番を決定する問題として定式化させ、
前記スーパー問題最適化処理で、生成された前記サブ問題同士の順番を決定するスーパー問題を最適化させる
ための最適化プログラム。
発明の詳細な説明
【技術分野】
【0001】
本発明は、組合せ最適化問題に応じた最適化を行う最適化装置、最適化方法および最適化プログラムに関する。
続きを表示(約 1,600 文字)
【背景技術】
【0002】
組合せ最適化問題は、組合せに関する選択肢の中から、ある指標に基づいて最も良い組合せを探そうとする問題であり、様々な制約の下で所定の指標を最適化する変数の値の組合せを導出する問題である。組合せ最適化問題は、日常の様々な場面に適用される問題であるが、その問題の特性上、規模が大きくなると計算量が爆発することも知られている。
【0003】
このような問題を解決するため、近年、最適化問題をシミュレーテッドアニーリング(Simulated Annealing 。以下、SAと記すこともある。)や量子アニーリングにより解く方法が各種提案されている。例えば、特許文献1には、生産性が最大になる生産計画を作成する生産計画方法が記載されている。特許文献1に記載された方法では、製品の生産計画作成問題に関する目的関数及び制約条件をQUBO(Quadratic Unconstrained Binary Optimization:制約なし二次バイナリ最適化)モデルもしくはイジングモデルに定式化し、アニーリングマシンを用いて最適解を取得する。
【0004】
なお、非特許文献1には、イジングマシンを用いた制約付きスロット配置問題の解決方法が記載されている。
【先行技術文献】
【特許文献】
【0005】
特開2020-140615号公報
【非特許文献】
【0006】
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
【発明の概要】
【発明が解決しようとする課題】
【0007】
イジングモデルは、結晶を構成する原子のスピンの向きを計算する簡易的なモデルであり、組合せ最適化問題の定式化の一つである。また、QUBOモデルも、組合せ最適化問題の定式化の一つであり、QUBOモデルの係数を表わす行列は、QUBO行列と呼ばれる。QUBOモデルとイジングモデルは一対一に変形できるため、QUBOモデル化された組合せ最適化問題は、アニーリングマシンで解くことが可能である。
【0008】
そして、QUBOモデル化された組合せ最適化問題をそのままアニーリングマシンで解くことも原理的には可能である。しかし、組合せ最適化問題の単純なQUBOモデルを用いた場合、最適解に近い解が得にくい場合も存在し、また、多くの時間を要してしまう可能性もある。
【0009】
特許文献1に記載された方法では、生産ラインにおける生産計画を時空間ネットワークモデルで定式化した組合せ最適化問題をQUBOモデルもしくはイジングモデルに変換して最適解を導出する。しかし、このように定式化された組合せ最適化問題を変換したQUBOモデルを解く場合にも、上記のような可能性が存在することから、より適切に最適化する方法は不明である。そのため、QUBOモデル化された最適化問題に応じて、より適切な最適化処理を実施できることが好ましい。
【0010】
そこで、本発明は、QUBOモデル化された最適化問題に応じて適切な最適化処理を実施できる最適化装置、最適化方法および最適化プログラムを提供することを目的とする。
【課題を解決するための手段】
(【0011】以降は省略されています)
この特許をJ-PlatPatで参照する
関連特許
日本電気株式会社
原子発振器
1か月前
日本電気株式会社
デルタシグマ変調装置
1か月前
日本電気株式会社
デバイスとその製造方法
22日前
日本電気株式会社
ボロメータ及び製造方法
8日前
日本電気株式会社
監視装置および監視方法
9日前
日本電気株式会社
通信装置および通信システム
2日前
日本電気株式会社
超伝導共振回路及び測定方法
1か月前
日本電気株式会社
通信システム及び通信制御方法
12日前
日本電気株式会社
画像処理システム、画像処理方法
1か月前
日本電気株式会社
情報処理装置、方法及びプログラム
8日前
日本電気株式会社
処理装置、処理システム及び処理方法
1か月前
日本電気株式会社
端末装置、通知方法、及びプログラム
2日前
日本電気株式会社
表示装置、表示方法、及びプログラム
2日前
日本電気株式会社
受光器、通信装置、および通信システム
2日前
日本電気株式会社
回転台、制御システム、および制御方法
1か月前
日本電気株式会社
バックドア検査装置、方法及びプログラム
3日前
日本電気株式会社
異常予兆判定装置および異常予兆判定方法
1か月前
日本電気株式会社
監視装置、監視方法および監視プログラム
1か月前
日本電気株式会社
通信装置、通信システム、および通信方法
2日前
日本電気株式会社
情報処理装置、情報処理方法、プログラム
2日前
日本電気株式会社
情報処理装置、情報処理方法、プログラム
29日前
日本電気株式会社
通話支援装置、通話支援方法及びプログラム
22日前
日本電気株式会社
提案装置、提案方法、および提案プログラム
22日前
日本電気株式会社
信号模擬装置、信号模擬方法及びプログラム
1か月前
日本電気株式会社
情報処理装置、情報処理方法、及びプログラム
26日前
日本電気株式会社
情報処理装置、情報処理方法、及びプログラム
1か月前
日本電気株式会社
デジタル署名システムと方法並びにプログラム
8日前
日本電気株式会社
雑音抑圧装置、雑音抑圧方法、及びプログラム
8日前
日本電気株式会社
情報処理装置、情報処理方法、及びプログラム
29日前
日本電気株式会社
情報表示装置、情報表示方法、及びプログラム
8日前
日本電気株式会社
販促提案装置、販促提案方法、及びプログラム
1か月前
日本電気株式会社
情報処理装置、情報処理方法、及びプログラム
29日前
日本電気株式会社
情報表示装置、情報表示方法、及びプログラム
1か月前
日本電気株式会社
情報処理装置、情報処理方法、及びプログラム
1日前
日本電気株式会社
需要予測装置、需要予測方法、及びプログラム
8日前
日本電気株式会社
需要予測装置、需要予測方法、及びプログラム
8日前
続きを見る
他の特許を見る