特許ウォッチ

公開番号2024175889
公報種別公開特許公報(A)
公開日2024-12-19
出願番号2023093971
出願日2023-06-07
発明の名称計算装置、計算方法、プログラムおよび回路情報
出願人株式会社東芝,東芝デジタルソリューションズ株式会社
代理人弁理士法人酒井国際特許事務所
主分類G06Q 10/04 20230101AFI20241212BHJP(計算;計数)
要約【課題】多目的最小化問題における近似パレート解集合を少ない計算量で精度良く算出する。
【解決手段】計算装置は、予測部と、選択部と、更新部と、繰返制御部と、出力部とを備える。予測部は、複数のウェイトパターンのそれぞれについて、対応するウェイトパターンを用いてパレート超体積の増加量を予測する予測処理を実行する。選択部は、増加量が最大となる最大ウェイトパターンを選択する選択処理を実行する。更新部は、複数の目的関数と最大ウェイトパターンにより表される複数のウェイト係数との線形加重和である合成目的関数を最小化する問題における複数の解をソルバ装置から取得して候補解集合に加えることにより、候補解集合を更新する更新処理を実行する。繰返制御部は、予測処理と、選択処理と、更新処理とを繰り返す繰返制御をする。出力部は、候補解集合のうちの非劣解を含む集合を近似パレート解集合として出力する。
【選択図】図6
特許請求の範囲【請求項１】
複数の目的関数を最小化する多目的最小化問題におけるパレート解に近似した近似パレート解を含む近似パレート解集合を算出する計算装置であって、
前記複数の目的関数を取得する関数取得部と、
前記複数の目的関数に一対一で対応する複数のウェイト係数を表す複数のウェイトパターンのそれぞれについて、対応するウェイトパターンを用いて、前記近似パレート解の候補である候補解を含む候補解集合を更新する場合における、劣解領域の超体積であるパレート超体積の増加量を予測する予測処理を実行する予測部と、
前記複数のウェイトパターンのうちの前記増加量が最大となるウェイトパターンを、最大ウェイトパターンとして選択する選択処理を実行する選択部と、
前記複数の目的関数と前記最大ウェイトパターンにより表される前記複数のウェイト係数との線形加重和である合成目的関数を最小化する問題における複数の解をソルバ装置から取得し、取得した前記複数の解のうちの少なくとも一部の解を前記候補解として前記候補解集合に加えることにより、前記候補解集合を更新する更新処理を実行する更新部と、
前記予測処理と、前記選択処理と、前記更新処理とを繰り返す繰返制御をする繰返制御部と、
前記繰返制御が終了した後、前記候補解集合に含まれる前記候補解のうちの非劣解を選択し、選択した前記非劣解を含む集合を前記近似パレート解集合として出力する出力部と、
を備える計算装置。
続きを表示（約 1,900 文字）【請求項２】
前記劣解領域は、前記複数の目的関数の全てを満たす実行可能解の領域のうちの、前記候補解集合に含まれる前記候補解が前記非劣解として選択されない領域である
請求項１に記載の計算装置。
【請求項３】
前記更新部は、取得した前記複数の解のうちの前記合成目的関数の値が予め定められた基準値以下または前記合成目的関数の値が小さい方から所定個の解を前記候補解として前記候補解集合に加える
請求項１に記載の計算装置。
【請求項４】
前記合成目的関数は、それぞれに前記複数のウェイト係数のうちの対応するウェイト係数が乗算された前記複数の目的関数を加算した関数である
請求項１に記載の計算装置。
【請求項５】
前記予測部は、それぞれに前記対応するウェイトパターンにより表される前記複数のウェイト係数が乗算された前記複数の目的関数を加算した関数を最小化する解を、前記候補解として前記候補解集合に加える場合における、前記パレート超体積の前記増加量を予測する
請求項１に記載の計算装置。
【請求項６】
前記関数取得部は、さらに、制約条件を取得し、
前記更新部は、前記複数の解のうちの、前記制約条件を満たす解を、前記候補解として前記候補解集合に加える
請求項１に記載の計算装置。
【請求項７】
前記多目的最小化問題におけるパレート解集合の凸閉包に近似した集合に含まれる複数の凸閉包解を取得する凸閉包取得部と、
前記複数の目的関数のそれぞれについて、前記複数の凸閉包解のそれぞれを対応する目的関数に代入して得られる各値のうちの最大値を取得する最大値取得部と、
前記複数の目的関数のそれぞれについて、前記複数の凸閉包解のそれぞれを対応する目的関数に代入して得られる各値のうちの最小値を取得する最小値取得部と、
前記複数の目的関数のそれぞれを前記最小値が得られる解を代入した場合に０となり、前記最大値が得られる解を代入した場合に１となるように係数を乗じるとともに平行移動し、さらに１より大きい予め設定された第１乗数でべき乗することにより、前記複数の目的関数のそれぞれを修正する関数修正部と、
をさらに備え、
前記繰返制御部は、修正した前記複数の目的関数を用いて、前記予測処理と、前記選択処理と、前記更新処理とを繰り返す前記繰返制御をする
請求項１に記載の計算装置。
【請求項８】
前記繰返制御部は、前記繰返制御に先立って、前記複数の凸閉包解を、前記候補解集合に含める
請求項７に記載の計算装置。
【請求項９】
前記関数取得部は、さらに、制約条件を取得し、
前記更新部は、前記複数の解のうちの、前記制約条件を満たす解を前記候補解として前記候補解集合に加える
請求項７に記載の計算装置。
【請求項１０】
複数の目的関数を最小化する多目的最小化問題におけるパレート解に近似した近似パレート解を含む近似パレート解集合を、情報処理装置により算出する計算方法であって、
前記情報処理装置が、前記複数の目的関数を取得し、
前記情報処理装置が、前記複数の目的関数に一対一で対応する複数のウェイト係数を表す複数のウェイトパターンのそれぞれについて、対応するウェイトパターンを用いて、前記近似パレート解の候補である候補解を含む候補解集合を更新する場合における、劣解領域の超体積であるパレート超体積の増加量を予測する予測処理を実行し、
前記情報処理装置が、前記複数のウェイトパターンのうちの前記増加量が最大となるウェイトパターンを、最大ウェイトパターンとして選択する選択処理を実行し、
前記情報処理装置が、前記複数の目的関数と前記最大ウェイトパターンにより表される前記複数のウェイト係数との線形加重和である合成目的関数を最小化する問題における複数の解をソルバ装置から取得し、取得した前記複数の解のうちの少なくとも一部の解を前記候補解として前記候補解集合に加えることにより、前記候補解集合を更新する更新処理を実行し、
前記予測処理と、前記選択処理と、前記更新処理とを繰り返す繰返制御をする繰返制御部と、
前記情報処理装置が、前記繰返制御が終了した後、前記候補解集合に含まれる前記候補解のうちの非劣解を選択し、選択した前記非劣解を含む集合を前記近似パレート解集合として出力する
計算方法。
（【請求項１１】以降は省略されています）
発明の詳細な説明【技術分野】
【０００１】
本発明の実施形態は、計算装置、計算方法、プログラムおよび回路情報に関する。
続きを表示（約 2,900 文字）【背景技術】
【０００２】
実社会における最適化問題の多くは、単一の評価値によって最適解が定まるのではなく、複数の評価値を考慮して最適解が定まる。このような複数の評価値を用いる最適化問題を、多目的最適化問題と呼ぶ。多目的最適化問題では、理想解をパレート解と呼ぶ。多目的最適化問題は、評価値のバランスが異なる複数のパレート解が存在する。実社会における最適化問題の多くは、このような複数のパレート解に基づき、複数の評価値のトレードオフを考慮して最適解が定められる。
【０００３】
多目的最適化問題を解いて複数のパレート解を算出する方法として、制約法、線形加重和法および多目的最適化法が知られている。
【０００４】
制約法は、複数の評価値のうちの１個の評価値を目的関数により表し、他の評価値を制約条件として表す。そして、制約法は、制約条件による制約の下で、目的関数を最適化する解を、最適化ソルバを用いて解く。しかし、制約法は、制約条件を合理的に決定することが難しい。また、制約法は、目的関数を最適化する解を制約条件を変更して複数回解かなければ、バランスが異なる複数のパレート解を得ることができない。
【０００５】
線形加重和法は、複数の評価値のそれぞれを個別の目的関数により表す。そして、線形加重和法は、複数の目的関数と複数のウェイト係数との線形加重和を算出して合成目的関数を生成する。しかし、線形加重和法は、複数のウェイト係数を合理的に決定することが難しい。また、線形加重和法は、複数のウェイト係数を変更して合成目的関数を最適化する解を複数回解かなければ、バランスが異なる複数のパレート解を得ることができない。また、線形加重和法は、実行可能解を含む集合が非凸の場合、凹み部分のパレート解を得ることができない。
【０００６】
多目的最適化法は、多目的最適化ソルバにより多目的最適化問題を解く。しかし、多目的最適化ソルバは、アルゴリズムが複雑であり、計算量も膨大となってしまう。
【先行技術文献】
【特許文献】
【０００７】
特開２０２２－１１８５５５号公報
特開２０２１－０４３６６７号公報
特開２０２１－０４３５８９号公報
【非特許文献】
【０００８】
Yoshihiko Ozaki, Yuki Tanigaki, Shuhei Watanabe and Masaki Onishi, “Multiobjective Tree-structured Parzen Estimator for Computationally Expensive Optimization Problems”, Association for Computing Machinery, The Genetic and Evolutionary Computation Conference, 2020 June, pp. 533-541
Preferred Networks, Optuna（登録商標）, [2023年5月12日検索], インターネット<URL, https://optuna.org/>, <URL, https://optuna.readthedocs.io/en/stable/reference/samplers/generated/optuna.samplers.MOTPESampler.html>
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
【発明の概要】
【発明が解決しようとする課題】
【０００９】
本発明が解決しようとする課題は、多目的最小化問題における複数の近似パレート解を、少ない計算量で精度良く算出することができる計算装置、計算方法、プログラムおよび回路情報を提供することにある。
【課題を解決するための手段】
【００１０】
実施形態に係る計算装置は、複数の目的関数を最小化する多目的最小化問題におけるパレート解に近似する近似パレート解を含む近似パレート解集合を算出する。前記計算装置は、関数取得部と、予測部と、選択部と、更新部と、繰返制御部と、出力部と、を備える。前記関数取得部は、前記複数の目的関数を取得する。前記予測部は、前記複数の目的関数に一対一で対応する複数のウェイト係数を表す複数のウェイトパターンのそれぞれについて、対応するウェイトパターンを用いて、前記近似パレート解の候補である候補解を含む候補解集合を更新する場合における、劣解領域の超体積であるパレート超体積の増加量を予測する予測処理を実行する。前記選択部は、前記複数のウェイトパターンのうちの前記増加量が最大となるウェイトパターンを、最大ウェイトパターンとして選択する選択処理を実行する。前記更新部は、前記複数の目的関数と前記最大ウェイトパターンにより表される前記複数のウェイト係数との線形加重和である合成目的関数を最小化する問題における複数の解をソルバ装置から取得し、取得した前記複数の解のうちの少なくとも一部の解を前記候補解として前記候補解集合に加えることにより、前記候補解集合を更新する更新処理を実行する。前記繰返制御部は、前記予測処理と、前記選択処理と、前記更新処理とを繰り返す繰返制御をする。前記出力部は、前記繰返制御が終了した後、前記候補解集合に含まれる前記候補解のうちの非劣解を選択し、選択した前記非劣解を含む集合を前記近似パレート解集合として出力する。
【図面の簡単な説明】
（【００１１】以降は省略されています）

関連特許