複雑な組合せ最適化問題を解決する、高度なAIベースの技術のスケールアップ(Advanced AI-Based Techniques Scale-up Solving Complex Combinatorial Optimization Problems)

ad

2024-06-10 カリフォルニア大学サンディエゴ校(UCSD)

カリフォルニア大学サンディエゴ校の研究者らが、複雑な計算問題を従来の方法よりも速く、スケーラブルに解決できるAIフレームワーク「HypOp」を開発しました。このフレームワークは、教師なし学習とハイパーグラフニューラルネットワークを使用し、組合せ最適化問題を大幅に効率よく解決します。HypOpは、新しい分散アルゴリズムを用いて複数の計算ユニットが並列に問題を解決するため、広範な現実世界の問題に適用可能です。また、転移学習により、ある問題の解決方法を他の関連する問題に応用できます。この技術は、医薬品開発やチップ設計、物流などでの応用が期待されています。

<関連情報>

ハイパーグラフ・ニューラルネットワークを活用した分散制約組み合わせ最適化 Distributed constrained combinatorial optimization leveraging hypergraph neural networks

Nasimeh Heydaribeni,Xinrui Zhan,Ruisi Zhang,Tina Eliassi-Rad & Farinaz Koushanfar
Nature Machine Intelligence  Published:30 May 2024
DOI:https://doi.org/10.1038/s42256-024-00833-7

  • 複雑な組合せ最適化問題を解決する、高度なAIベースの技術のスケールアップ(Advanced AI-Based Techniques Scale-up Solving Complex Combinatorial Optimization Problems)

Abstract

Scalable addressing of high-dimensional constrained combinatorial optimization problems is a challenge that arises in several science and engineering disciplines. Recent work introduced novel applications of graph neural networks for solving quadratic-cost combinatorial optimization problems. However, effective utilization of models such as graph neural networks to address general problems with higher-order constraints is an unresolved challenge. This paper presents a framework, HypOp, that advances the state of the art for solving combinatorial optimization problems in several aspects: (1) it generalizes the prior results to higher-order constrained problems with arbitrary cost functions by leveraging hypergraph neural networks; (2) it enables scalability to larger problems by introducing a new distributed and parallel training architecture; (3) it demonstrates generalizability across different problem formulations by transferring knowledge within the same hypergraph; (4) it substantially boosts the solution accuracy compared with the prior art by suggesting a fine-tuning step using simulated annealing; and (5) it shows remarkable progress on numerous benchmark examples, including hypergraph MaxCut, satisfiability and resource allocation problems, with notable run-time improvements using a combination of fine-tuning and distributed training techniques. We showcase the application of HypOp in scientific discovery by solving a hypergraph MaxCut problem on a National Drug Code drug-substance hypergraph. Through extensive experimentation on various optimization problems, HypOp demonstrates superiority over existing unsupervised-learning-based solvers and generic optimization methods.

1602ソフトウェア工学
ad
ad
Follow
ad
タイトルとURLをコピーしました