論文の概要: MARCO: A Memory-Augmented Reinforcement Framework for Combinatorial Optimization

• arxiv url: http://arxiv.org/abs/2408.02207v1
• Date: Mon, 5 Aug 2024 03:15:21 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-06 14:45:49.789469
• Title: MARCO: A Memory-Augmented Reinforcement Framework for Combinatorial Optimization
• Title（参考訳）: MARCO:コンビネーション最適化のためのメモリ拡張強化フレームワーク
• Authors: Andoni I. Garmendia, Quentin Cappart, Josu Ceberio, Alexander Mendiburu,
• Abstract要約: 本稿では,MARCO(Memory-Augmented Reinforcement for Combinatorial Optimization)と呼ばれる多機能フレームワークを紹介する。 MARCOは最適化軌道全体を通して収集されたデータを格納し、各状態におけるコンテキスト関連情報を検索する。 NCOモデルの並列性により、複数の検索スレッドが同時に動作し、すべて同じメモリモジュールを共有することができる。
• 参考スコア（独自算出の注目度）: 44.24494442399324
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Neural Combinatorial Optimization (NCO) is an emerging domain where deep learning techniques are employed to address combinatorial optimization problems as a standalone solver. Despite their potential, existing NCO methods often suffer from inefficient search space exploration, frequently leading to local optima entrapment or redundant exploration of previously visited states. This paper introduces a versatile framework, referred to as Memory-Augmented Reinforcement for Combinatorial Optimization (MARCO), that can be used to enhance both constructive and improvement methods in NCO through an innovative memory module. MARCO stores data collected throughout the optimization trajectory and retrieves contextually relevant information at each state. This way, the search is guided by two competing criteria: making the best decision in terms of the quality of the solution and avoiding revisiting already explored solutions. This approach promotes a more efficient use of the available optimization budget. Moreover, thanks to the parallel nature of NCO models, several search threads can run simultaneously, all sharing the same memory module, enabling an efficient collaborative exploration. Empirical evaluations, carried out on the maximum cut, maximum independent set and travelling salesman problems, reveal that the memory module effectively increases the exploration, enabling the model to discover diverse, higher-quality solutions. MARCO achieves good performance in a low computational cost, establishing a promising new direction in the field of NCO.
• Abstract（参考訳）: Neural Combinatorial Optimization(NCO)は、独立的な解決手段として組合せ最適化問題に対処するためにディープラーニング技術を採用する新興ドメインである。 その可能性にもかかわらず、既存のNCO法は、しばしば非効率な探索空間の探索に悩まされ、しばしば局所的な最適侵入や、以前に訪れた州の冗長な探査につながる。 本稿では, メモリモジュールによるNCOの構成的および改善手法の強化に使用可能な, メモリ拡張型組合せ最適化(MARCO)と呼ばれる多機能フレームワークを提案する。 MARCOは最適化軌道全体を通して収集されたデータを格納し、各状態におけるコンテキスト関連情報を検索する。 このようにして、検索は2つの競合する基準によって導かれる: ソリューションの品質の観点から最良の決定をし、既に探索されたソリューションを再考するのを避ける。 このアプローチは、利用可能な最適化予算をより効率的に活用する。 さらに、NCOモデルの並列性により、複数の検索スレッドが同時に動作し、すべて同じメモリモジュールを共有することにより、効率的な協調探索が可能になる。 最大カット,最大独立セット,トラベリングセールスマン問題に基づく実証評価により,メモリモジュールが探索を効果的に増加させ,多種多様な高品質のソリューションを発見することができることを示した。 MARCOは計算コストが低く、NCO分野において有望な新たな方向性を確立する。

関連論文リスト

• Large Language Models for Combinatorial Optimization of Design Structure Matrix [4.513609458468522]
  エンジニアリングアプリケーションの効率と性能を改善するためには、組合せ最適化(CO)が不可欠である。 実世界の工学的問題に関しては、純粋数学的推論に基づくアルゴリズムは限定的であり、最適化に必要な文脈ニュアンスを捉えることができない。 本研究では,工学的CO問題の解法におけるLarge Language Models (LLMs) の可能性について,その推論能力と文脈的知識を活用して検討する。
  論文  参考訳（メタデータ） (2024-11-19T15:39:51Z)
• LLaMA-Berry: Pairwise Optimization for O1-like Olympiad-Level Mathematical Reasoning [56.273799410256075]
  このフレームワークはMonte Carlo Tree Search (MCTS)と反復的なSelf-Refineを組み合わせて推論パスを最適化する。 このフレームワークは、一般的なベンチマークと高度なベンチマークでテストされており、探索効率と問題解決能力の点で優れた性能を示している。
  論文  参考訳（メタデータ） (2024-10-03T18:12:29Z)
• Memory-Enhanced Neural Solvers for Efficient Adaptation in Combinatorial Optimization [6.713974813995327]
  本稿では、メモリを活用してニューラルネットワークの適応性を向上させるアプローチであるMementOを提案する。 我々は,大規模インスタンス上で全RL自動回帰解法をトレーニングし,MementOが拡張可能で,データ効率がよいことを示す。 全体として、MementOは評価された12のタスクのうち11に最先端のタスクをプッシュすることができる。
  論文  参考訳（メタデータ） (2024-06-24T08:18:19Z)
• Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
  最適化問題に取り組むための新たな戦略は、従来のアルゴリズムに代わるグラフニューラルネットワーク(GNN)の採用である。 GNNや従来のアルゴリズムソルバがCOの領域で人気が高まっているにもかかわらず、それらの統合利用とエンドツーエンドフレームワークにおけるそれらの相関について限定的な研究がなされている。 我々は、GNNを利用してCO問題に補助的なサポートで対処する決定に焦点を当てたフレームワークを導入する。
  論文  参考訳（メタデータ） (2024-06-05T22:52:27Z)
• Moco: A Learnable Meta Optimizer for Combinatorial Optimization [5.359176539960004]
  Mocoは、現在の検索状態から抽出された特徴に基づいて、ソリューション構築手順を更新するグラフニューラルネットワークを学習する。 このメタトレーニング手順は、検索予算などの情報を得た探索手順中に見つかった全体的なベストソリューションをターゲットにしている。 Mocoは完全に学習可能なメタで、特定のローカル検索や分解の問題を一切利用しない。
  論文  参考訳（メタデータ） (2024-02-07T14:41:17Z)
• Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets [86.43523688236077]
  組合せ最適化(CO)問題はしばしばNPハードであり、正確なアルゴリズムには及ばない。 GFlowNetsは、複合非正規化密度を逐次サンプリングする強力な機械として登場した。 本稿では,異なる問題に対してマルコフ決定プロセス(MDP)を設計し,条件付きGFlowNetを学習して解空間からサンプルを作成することを提案する。
  論文  参考訳（メタデータ） (2023-05-26T15:13:09Z)
• RELS-DQN: A Robust and Efficient Local Search Framework for Combinatorial Optimization [11.269582666887324]
  本稿では,DQNフレームワークのRELS-DQNを紹介する。 1つのアプリケーションでトレーニングされたRELS-DQNモデルを使用することで、ローカル検索アルゴリズムと既存のDQNモデルの両方に等しい解値を提供することで、様々なアプリケーションに一般化することができる。
  論文  参考訳（メタデータ） (2023-04-11T18:01:49Z)
• A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs [91.07247251502564]
  本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。 このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
  論文  参考訳（メタデータ） (2021-06-09T09:18:18Z)
• A General Large Neighborhood Search Framework for Solving Integer Linear Programs [46.62993477453986]
  我々は整数プログラムの解法に重点を置いており、我々のアプローチは大規模近傍探索(SLN)パラダイムに根ざしている。 我々のLSSフレームワークは、Gurobiのような最先端の商用解法と比較して、大幅に性能が向上することを示した。
  論文  参考訳（メタデータ） (2020-03-29T23:08:14Z)

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

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