特許ウォッチ

公開番号2025104790
公報種別公開特許公報(A)
公開日2025-07-10
出願番号2023222858
出願日2023-12-28
発明の名称機械学習プログラム、判定プログラム、機械学習方法、判定方法、機械学習装置、および判定装置
出願人富士通株式会社
代理人個人
主分類G06N 99/00 20190101AFI20250703BHJP(計算;計数)
要約【課題】組み合わせ最適化問題において複数の解を求解することができる機械学習プログラム、判定プログラム、機械学習方法、判定方法、機械学習装置、および判定装置を提供する。
【解決手段】コンピュータに、離散最適化問題に連続緩和を取り入れて探索を行う探索処理におけるコスト関数として、最適化対象の離散変数を連続行列に緩和した行列の各要素が離散最適化問題となるコスト関数を用いた機械学習により、機械学習モデルを訓練する処理を実行させる。
【選択図】図3

特許請求の範囲【請求項１】
コンピュータに、
離散最適化問題に連続緩和を取り入れて探索を行う探索処理におけるコスト関数として、最適化対象の離散変数を連続行列に緩和した行列の各要素が離散最適化問題となるコスト関数を用いた機械学習により、機械学習モデルを訓練する処理を実行させることを特徴とする機械学習プログラム。
続きを表示（約 1,000 文字）【請求項２】
前記コスト関数は、前記探索処理における制約を表すペナルティ項を含んでおり、
前記機械学習モデルを訓練する際に、前記ペナルティ項のペナルティ係数を学習することを特徴とする請求項１に記載の機械学習プログラム。
【請求項３】
前記離散最適化問題は、ＱＵＢＯ形式で表されることを特徴とする請求項１に記載の機械学習プログラム。
【請求項４】
前記機械学習モデルを訓練する際に、最適化対象の変数の連続および離散の程度に応じた損失項を用い、前記探索処理の進行に応じて前記損失項を変化させることを特徴とする請求項１に記載の機械学習プログラム。
【請求項５】
前記コンピュータに、前記探索処理が進行するにつれて、前記損失項を、前記変数が連続的であるほど損失が小さくなるものから、前記変数が連続的であるほど損失が大きくなるものに変化させる処理を実行させることを特徴とする請求項４に記載の機械学習プログラム。
【請求項６】
コンピュータに、
請求項１から請求項５のいずれか一項に記載の機械学習プログラムの実行によって訓練された機械学習モデルに最適化問題を埋め込むことによって解を出力する、処理を実行させることを特徴とする判定プログラム。
【請求項７】
コンピュータが、
離散最適化問題に連続緩和を取り入れて探索を行う探索処理におけるコスト関数として、最適化対象の離散変数を連続行列に緩和した行列の各要素が離散最適化問題となるコスト関数を用いた機械学習により、機械学習モデルを訓練する処理を実行することを特徴とする機械学習方法。
【請求項８】
コンピュータが、
請求項７に記載の機械学習プログラムの実行によって訓練された機械学習モデルに最適化問題を埋め込むことによって解を出力する、処理を実行することを特徴とする判定方法。
【請求項９】
離散最適化問題に連続緩和を取り入れて探索を行う探索処理におけるコスト関数として、最適化対象の離散変数を連続行列に緩和した行列の各要素が離散最適化問題となるコスト関数を用いた機械学習により、機械学習モデルを訓練する処理を実行する実行部を備えることを特徴とする機械学習装置。
【請求項１０】
請求項９に記載の機械学習装置によって訓練された機械学習モデルに最適化問題を埋め込むことによって解を出力する出力部を備えることを特徴とする判定装置。

発明の詳細な説明【技術分野】
【０００１】
本件は、機械学習プログラム、判定プログラム、機械学習方法、判定方法、機械学習装置、および判定装置に関する。
続きを表示（約 1,400 文字）【背景技術】
【０００２】
複雑な組み合わせを最適化する技術が開示されている（例えば、非特許文献１，２参照）。
【先行技術文献】
【非特許文献】
【０００３】
Schuetz, M. J., Brubaker, J. K., and Katzgraber, H. G. (2022a). Combinatorial optimization with physics-inspired graph neural networks. Nature Machine Intelligence, 4(4):367-377.
Schuetz, M. J., Brubaker, J. K., Zhu, Z., and Katzgraber, H. G. (2022b). Graph coloring with physics-inspired graph neural networks. Physical Review Research, 4(4):043131.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
組み合わせ最適化において、機械学習モデルを用いた連続緩和求解法によって最適解を探索することが考えられている。しかしながら、複数の解を求解することは困難である。
【０００５】
１つの側面では、本発明は、組み合わせ最適化問題において複数の解を求解することができる機械学習プログラム、判定プログラム、機械学習方法、判定方法、機械学習装置、および判定装置を提供することを目的とする。
【課題を解決するための手段】
【０００６】
１つの態様では、機械学習プログラムは、コンピュータに、離散最適化問題に連続緩和を取り入れて探索を行う探索処理におけるコスト関数として、最適化対象の離散変数を連続行列に緩和した行列の各要素が離散最適化問題となるコスト関数を用いた機械学習により、機械学習モデルを訓練する処理を実行させる。
【０００７】
他の態様では、判定プログラムは、コンピュータに、上記の機械学習プログラムの実行によって訓練された機械学習モデルに最適化問題を埋め込むことによって解を出力する、処理を実行させる。
【発明の効果】
【０００８】
組み合わせ最適化問題において複数の解を求解することができる。
【図面の簡単な説明】
【０００９】
グラフ埋め込みベクトルへの変換を例示する図である。
検証結果を例示する図である。
（ａ）は実施例１に係る情報処理装置の全体構成を表す機能ブロック図であり、（ｂ）は制約調節部の詳細を表すブロック図である。
情報処理装置のハードウェア構成図である。
機械学習時における情報処理装置の動作の一例を表すフローチャートである。
機械学習の結果を利用して最適化する場合における情報処理装置の動作の一例を表すフローチャートである。
【発明を実施するための形態】
【００１０】
製造業界や流通業界をはじめ、様々な業界の現場には最適化問題が存在している。特に、組み合わせを最適化する組み合わせ最適化問題は、最適化の分野で最も重要な分野の１つである。組み合わせ最適化問題は、輸送、物流、通信、金融など、様々な分野で応用されている。
（【００１１】以降は省略されています）

関連特許