特許ウォッチ

公開番号2024084000
公報種別公開特許公報(A)
公開日2024-06-24
出願番号2022198142
出願日2022-12-12
発明の名称情報処理装置、情報処理方法およびプログラム
出願人株式会社東芝
代理人弁理士法人酒井国際特許事務所
主分類G06N 99/00 20190101AFI20240617BHJP(計算;計数)
要約【課題】組合せ最適化問題で求解された制約違反解を用いて情報処理機能の性能または効率を向上させる。
【解決手段】実施形態に係る情報処理システムは、データに対して処理を実行する。情報処理装置は、予め定められた制約条件の下でデータに基づく組合せ最適化問題を生成し、生成された組合せ最適化問題を、制約条件を満たさないことを許容して求解し、求解して得られた組合せ最適化問題の解を算出し、解が制約条件を満たさない場合、制約違反部分に基づく制約違反制御信号を生成し、制約違反制御信号に基づき、データに対して予め定められた第1処理を実行し、第1処理が実行されたデータを出力する。
【選択図】図8
特許請求の範囲【請求項１】
データに対して処理を実行する情報処理装置であって、
予め定められた制約条件の下で前記データに基づく組合せ最適化問題を生成し、
生成された前記組合せ最適化問題を、前記制約条件を満たさないことを許容して求解し、求解して得られた前記組合せ最適化問題の解を算出し、
前記解が前記制約条件を満たさない場合、制約違反制御信号を生成し、
前記制約違反制御信号に基づき、前記データに対して予め定められた第１処理を実行し、
前記第１処理が実行された前記データを出力する
情報処理装置。
続きを表示（約 1,800 文字）【請求項２】
前記組合せ最適化問題の生成において、コスト関数とペナルティ関数とを加算するトータルコスト関数を最小化する前記組合せ最適化問題を生成し、
前記コスト関数は、前記データに対応する複数の決定変数を引数として含み、前記複数の決定変数の１次以上の関数であり、
前記ペナルティ関数は、前記複数の決定変数の少なくとも一部を含み、前記解が前記制約条件を満足するときに最小値となる関数である
請求項１に記載の情報処理装置。
【請求項３】
前記制約違反制御信号の生成において、
求解された前記組合せ最適化問題の前記解が、前記制約条件を満たすか否かを判断し、
前記解が、前記制約条件を満たさない場合、前記制約違反制御信号を出力する
請求項２に記載の情報処理装置。
【請求項４】
前記制約条件は、それぞれが等式または不等式である１個または複数の制約式により表され、
前記制約違反制御信号の生成において、
前記解が、前記１個または複数の制約式を満たすか否かを判断し、
前記解が、前記１個または複数の制約式を満たさない場合、前記制約違反制御信号を出力する
請求項２に記載の情報処理装置。
【請求項５】
前記制約条件は、それぞれが等式または不等式である１個または複数の制約式により表され、
前記制約違反制御信号の生成において、前記解が前記１個または複数の制約式を満たさず、且つ、前記１個または複数の制約式のうち、式を満たさない制約式の数が予め設定された値以下の場合、前記制約違反制御信号を出力する
請求項２に記載の情報処理装置。
【請求項６】
前記解を前記ペナルティ関数に代入して得られる値が、前記最小値よりも大きく、予め設定された値以下の場合、前記制約違反制御信号を出力する
請求項２に記載の情報処理装置。
【請求項７】
さらに、
前記解が前記制約条件を満たしている場合、
前記データに対して前記解に基づき予め定められた第２処理を実行し、
前記第２処理が実行された前記データを出力する
請求項２に記載の情報処理装置。
【請求項８】
前記解が前記制約条件を満たさない場合、
前記解のうちの前記制約条件を満たさない制約違反部分、および、前記解のうち前記制約条件を満たす制約満足部分を特定し、
前記制約違反部分に基づく前記制約違反制御信号、および、前記制約満足部分に基づく制約満足制御信号を出力し、
前記制約満足制御信号に基づき、前記データに対して前記第２処理を実行し、
前記制約違反制御信号に基づき、前記データにおける前記制約違反部分に対応するデータに対して前記第１処理を実行する
請求項７に記載の情報処理装置。
【請求項９】
前記制約違反部分および前記制約満足部分の特定において、
取得した前記解に基づき、前記複数の決定変数のうちの前記制約条件を満たさない要因となる決定変数を特定し、前記制約条件を満たさない要因となる決定変数の値を変化させることにより、前記制約満足部分を特定し、
前記制約条件を満たさない要因となる決定変数の値を抽出して前記制約違反部分を特定する
請求項８に記載の情報処理装置。
【請求項１０】
前記組合せ最適化問題の生成において、第１組合せ最適化問題および第２組合せ最適化問題を生成し、
前記第１組合せ最適化問題は、前記第２組合せ最適化問題よりも、前記コスト関数に対する前記ペナルティ関数の比率が大きく
前記解の求解において、前記第１組合せ最適化問題および前記第２組合せ最適化問題のそれぞれについて、前記解を求解し、
前記制約違反部分および前記制約満足部分の特定において、
前記第１組合せ最適化問題の前記解を、前記制約満足部分として特定し、
前記第１組合せ最適化問題の前記解と、前記第２組合せ最適化問題の前記解との差に基づき、前記制約違反部分を特定する
請求項８に記載の情報処理装置。
（【請求項１１】以降は省略されています）
発明の詳細な説明【技術分野】
【０００１】
本発明は、情報処理装置、情報処理方法およびプログラムに関する。
続きを表示（約 2,600 文字）【背景技術】
【０００２】
制御、金融、通信、物流、化学などの様々な応用分野における系の最適化は、多くの場合、組合せ最適化問題へ数学的に帰着される。組合せ最適化問題を解くことによって、認識、判断および計画等の様々な情報処理機能を実現およびこのような機能の効率化をする情報処理システムが提案されている。
【０００３】
組合せ最適化問題とは、最適化の対象となる系の状態を表す複数の決定変数（例えば離散変数）を引数とするコスト関数を定義し、定義したコスト関数を最小化する複数の決定変数の値の組合せを求解する問題である。複数の決定変数により表される系の状態は、解と呼ばれる。組合せ最適化問題は、決定変数の数が増えるほど、解として取り得る状態の数が指数関数的に増大する。解として取り得る状態の数が増大することを、組み合わせ爆発と呼ぶ。全ての解の候補から最適な一つの解を選ぶという組み合わせ最適化は計算困難な問題として知られている。大規模な組み合わせ最適化を短時間に実行することは、いまだチャレンジングな課題である。
【０００４】
制約付き組合せ最適化問題は、解に一定の制約条件を課し、制約条件の下でコスト関数を最小化する解を求解する問題である。制約条件を満たす解は、制約満足解と呼ばれる。制約条件を満たす解は、実行可能解と呼ばれる場合もある。制約条件を満たさない解は、制約違反解と呼ばれる。制約条件を満たさない解は、実行不可能解と呼ばれる場合もある。
【０００５】
従来の制約付き組合せ最適化問題を解く情報処理システムは、制約違反解を解として出力しなかったり、制約違反解を求解しても破棄をしたりする。しかし、制約違反解であっても、情報処理機能の性能または効率を向上させるために有効な解が含まれる可能性がある。
【０００６】
従来、制約違反解のうちの情報処理機能の性能または効率を向上させるために有効な解を効率良く出力する技術、または、制約違反解を用いて情報処理機能の性能または効率を向上させる技術は知られていない。従って、従来の技術では、制約違反解に情報処理機能の性能または効率を向上させるために有効な解が含まれていても、情報処理機能の性能または効率を向上させることができなかった。
【先行技術文献】
【特許文献】
【０００７】
特開２０１９－１４５０１０号公報
特開２０１９－１５９５６６号公報
特開２０２１－０４３６６７号公報
特開２０２１－０４３５８９号公報
特開２０２１－０６０８６４号公報
【非特許文献】
【０００８】
A Bewley, et at.， “Simple online and realtime tracking”， IEEE ICIP（2016）， pp. 3464-3468， 2016
Hayato Goto， Kosuke Tatsumura and Alexander R. Dixon， “Combinatorial optimization by simulating adiabatic bifurcations in nonlinear Hamiltonian systems，” Science Advances 5， eaav2372， 2019
Hayato Goto， Kotaro Endo， Masaru Suzuki， Yoshisato Sakai， Taro Kanao， Yohei Hamakawa， Ryo Hidaka， Masaya Yamasaki and Kosuke Tatsumura， “High-performance combinatorial optimization based on classical mechanics”， Science Advances 7， eabe7953， 2021
Joseph Redmon， Santosh Divvala， Ross Girshick and Ali Farhadi， “You Only Look Once: Unified， Real-Time Object Detection”， Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition （CVPR）， 2016， pp. 779-788
Wei Liu， et al.， “SSD: Single Shot MultiBox Detector”， Springer International Publishing AG 2016， ECCV 2016，Part I， LNCS vol 9905， pp. 21-37， 2016
【発明の概要】
【発明が解決しようとする課題】
【０００９】
本発明が解決しようとする課題は、組合せ最適化問題で求解された制約違反解を用いて情報処理機能の性能または効率を向上させることにある。
【課題を解決するための手段】
【００１０】
実施形態に係る情報処理システムは、データに対して処理を実行する。前記情報処理装置は、予め定められた制約条件の下で前記データに基づく組合せ最適化問題を生成し、生成された前記組合せ最適化問題を、前記制約条件を満たさないことを許容して求解し、求解して得られた前記組合せ最適化問題の解を算出し、前記解が前記制約条件を満たさない場合、制約違反部分に基づく制約違反制御信号を生成し、前記制約違反制御信号に基づき、前記データに対して予め定められた第１処理を実行し、前記第１処理が実行された前記データを出力する。
【図面の簡単な説明】
（【００１１】以降は省略されています）

関連特許