論文の概要: Neural Improvement Heuristics for Graph Combinatorial Optimization Problems

• arxiv url: http://arxiv.org/abs/2206.00383v3
• Date: Sat, 7 Oct 2023 12:33:05 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-13 17:03:14.024601
• Title: Neural Improvement Heuristics for Graph Combinatorial Optimization Problems
• Title（参考訳）: グラフ組合せ最適化問題に対するニューラル改善ヒューリスティックス
• Authors: Andoni I. Garmendia, Josu Ceberio, Alexander Mendiburu
• Abstract要約: 本稿では,ノード,エッジ,あるいはその両方に情報をエンコードするグラフベースの問題を扱う新しいニューラル改善(NI)モデルを提案する。 提案モデルは,各地区の操作の選択を誘導する丘登頂に基づくアルゴリズムの基本的な構成要素として機能する。
• 参考スコア（独自算出の注目度）: 49.85111302670361
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Recent advances in graph neural network architectures and increased computation power have revolutionized the field of combinatorial optimization (CO). Among the proposed models for CO problems, Neural Improvement (NI) models have been particularly successful. However, existing NI approaches are limited in their applicability to problems where crucial information is encoded in the edges, as they only consider node features and node-wise positional encodings. To overcome this limitation, we introduce a novel NI model capable of handling graph-based problems where information is encoded in the nodes, edges, or both. The presented model serves as a fundamental component for hill-climbing-based algorithms that guide the selection of neighborhood operations for each iteration. Conducted experiments demonstrate that the proposed model can recommend neighborhood operations that outperform conventional versions for the Preference Ranking Problem with a performance in the 99th percentile. We also extend the proposal to two well-known problems: the Traveling Salesman Problem and the Graph Partitioning Problem, recommending operations in the 98th and 97th percentile, respectively.
• Abstract（参考訳）: グラフニューラルネットワークアーキテクチャの最近の進歩と計算能力の向上は、組合せ最適化(CO)の分野に革命をもたらした。 提案したCO問題モデルのうち、ニューラル改善(NI)モデルは特に成功した。 しかし、既存のNIアプローチは、ノードの特徴とノード単位の位置エンコーディングのみを考慮するため、エッジに重要な情報がエンコードされる問題に適用可能である。 この制限を克服するために,ノード,エッジ,あるいはその両方に情報をエンコードするグラフベースの問題を扱う新しいNIモデルを導入する。 提案モデルは,各繰り返しの近傍操作の選択を誘導するヒルクライミングに基づくアルゴリズムの基本的な構成要素として機能する。 実験により,提案モデルでは,99パーセントの精度で従来の優先順位付け問題よりも高い性能を示す近傍操作を推奨できることを示した。 また,この提案を,トラベルセールスマン問題とグラフ分割問題という2つのよく知られた問題にも拡張し,それぞれ98パーセンタイルと97パーセンタイルの操作を推奨した。

関連論文リスト

• Enhancing GNNs Performance on Combinatorial Optimization by Recurrent Feature Update [0.09986418756990156]
  本稿では,組合せ最適化(CO)問題を効率よく解くために,GNNのパワーを活用して,QRF-GNNと呼ぶ新しいアルゴリズムを提案する。 QUBO緩和による損失関数の最小化による教師なし学習に依存している。 実験の結果、QRF-GNNは既存の学習ベースアプローチを大幅に上回り、最先端の手法に匹敵することがわかった。
  論文  参考訳（メタデータ） (2024-07-23T13:34:35Z)
• Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
  最適化問題に取り組むための新たな戦略は、従来のアルゴリズムに代わるグラフニューラルネットワーク(GNN)の採用である。 GNNや従来のアルゴリズムソルバがCOの領域で人気が高まっているにもかかわらず、それらの統合利用とエンドツーエンドフレームワークにおけるそれらの相関について限定的な研究がなされている。 我々は、GNNを利用してCO問題に補助的なサポートで対処する決定に焦点を当てたフレームワークを導入する。
  論文  参考訳（メタデータ） (2024-06-05T22:52:27Z)
• A Graph Neural Network-Based QUBO-Formulated Hamiltonian-Inspired Loss Function for Combinatorial Optimization using Reinforcement Learning [1.325953054381901]
  グラフニューラルネットワーク(GNN)を用いた新しいモンティカルロ木探索手法を提案する。 PI-GNNに関連する行動パターンを特定し,その性能向上のための戦略を考案する。 また、RL法とQUBO法で定式化されたハミルトニアンとの橋渡しにも着目する。
  論文  参考訳（メタデータ） (2023-11-27T19:33:14Z)
• Learning to Optimize Permutation Flow Shop Scheduling via Graph-based Imitation Learning [70.65666982566655]
  置換フローショップスケジューリング(PFSS)は製造業で広く使われている。 我々は,より安定かつ正確に収束を加速する専門家主導の模倣学習を通じてモデルを訓練することを提案する。 我々のモデルのネットワークパラメータはわずか37%に減少し、エキスパートソリューションに対する我々のモデルの解のギャップは平均6.8%から1.3%に減少する。
  論文  参考訳（メタデータ） (2022-10-31T09:46:26Z)
• Improved Algorithms for Neural Active Learning [74.89097665112621]
  非パラメトリックストリーミング設定のためのニューラルネットワーク(NN)ベースの能動学習アルゴリズムの理論的および経験的性能を改善する。 本研究では,SOTA(State-of-the-art (State-the-art)) 関連研究で使用されるものよりも,アクティブラーニングに適する人口減少を最小化することにより,2つの後悔の指標を導入する。
  論文  参考訳（メタデータ） (2022-10-02T05:03:38Z)
• Comprehensive Graph Gradual Pruning for Sparse Training in Graph Neural Networks [52.566735716983956]
  本稿では,CGPと呼ばれるグラフの段階的プルーニングフレームワークを動的にGNNに提案する。 LTHに基づく手法とは異なり、提案手法では再学習を必要とせず、計算コストを大幅に削減する。 提案手法は,既存の手法の精度を一致させたり,あるいは超えたりしながら,トレーニングと推論の効率を大幅に向上させる。
  論文  参考訳（メタデータ） (2022-07-18T14:23:31Z)
• Graph Neural Network based scheduling : Improved throughput under a generalized interference model [3.911413922612859]
  本稿では,アドホックネットワークのためのグラフ畳み込みニューラルネットワーク(GCN)に基づくスケジューリングアルゴリズムを提案する。 この研究で注目すべき特徴は、ニューラルネットワークをトレーニングするためにラベル付きデータセット(NP-hard to compute)を必要としないことである。
  論文  参考訳（メタデータ） (2021-10-31T10:36:11Z)
• Persistent Neurons [4.061135251278187]
  本稿では,学習課題を最適化するトラジェクトリベースの戦略を提案する。 永続ニューロンは、決定論的誤差項によって個々の更新が破損する勾配情報バイアスを持つ方法とみなすことができる。 完全かつ部分的なパーシステンスモデルの評価を行い、NN構造における性能向上に有効であることを示す。
  論文  参考訳（メタデータ） (2020-07-02T22:36:49Z)
• Towards an Efficient and General Framework of Robust Training for Graph Neural Networks [96.93500886136532]
  グラフニューラルネットワーク(GNN)は、いくつかの基本的な推論タスクに大きく進歩している。 GNNの目覚ましい性能にもかかわらず、グラフ構造上の摂動を慎重に作り、誤った予測を下すことが観察されている。 我々は,強靭なGNNを得るために,欲求探索アルゴリズムとゼロ階法を利用する汎用フレームワークを提案する。
  論文  参考訳（メタデータ） (2020-02-25T15:17:58Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。