論文の概要: Scaling Combinatorial Optimization Neural Improvement Heuristics with Online Search and Adaptation
- arxiv url: http://arxiv.org/abs/2412.10163v1
- Date: Fri, 13 Dec 2024 14:25:27 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-16 15:03:50.842109
- Title: Scaling Combinatorial Optimization Neural Improvement Heuristics with Online Search and Adaptation
- Title(参考訳): オンライン検索と適応による組合せ最適化ニューラル改善ヒューリスティックスのスケーリング
- Authors: Federico Julian Camerota Verdù, Lorenzo Castelli, Luca Bortolussi,
- Abstract要約: リミテッドロールアウトビームサーチ(Limited Rollout Beam Search, LRBS)を導入する。
LRBSは, 分散性能と大規模問題インスタンスへの一般化の両方を著しく向上させることを示す。
また、事前訓練された改善ポリシーのオフラインおよびオンライン適応に検索戦略を採用し、検索性能を向上させる。
- 参考スコア(独自算出の注目度): 0.40964539027092917
- License:
- Abstract: We introduce Limited Rollout Beam Search (LRBS), a beam search strategy for deep reinforcement learning (DRL) based combinatorial optimization improvement heuristics. Utilizing pre-trained models on the Euclidean Traveling Salesperson Problem, LRBS significantly enhances both in-distribution performance and generalization to larger problem instances, achieving optimality gaps that outperform existing improvement heuristics and narrowing the gap with state-of-the-art constructive methods. We also extend our analysis to two pickup and delivery TSP variants to validate our results. Finally, we employ our search strategy for offline and online adaptation of the pre-trained improvement policy, leading to improved search performance and surpassing recent adaptive methods for constructive heuristics.
- Abstract(参考訳): リミテッドロールアウトビームサーチ(Limited Rollout Beam Search, LRBS)を導入する。
ユークリッド旅行セールスパーソン問題(英語版)における事前学習モデルを利用することで、LRBSは分配性能とより大きな問題インスタンスへの一般化の両方を著しく向上させ、既存の改善ヒューリスティックスを上回る最適性ギャップを達成し、最先端の建設手法とのギャップを狭める。
また、分析結果を2種類のTSP変種に拡張し、その結果を検証した。
最後に、事前訓練された改善政策のオフラインおよびオンライン適応に検索戦略を採用し、検索性能の向上と最近の建設的ヒューリスティックスへの適応手法を超越した。
関連論文リスト
- Improving Existing Optimization Algorithms with LLMs [0.9668407688201361]
本稿では,Large Language Models (LLM) が既存の最適化アルゴリズムをどのように拡張するかを検討する。
事前学習した知識を用いて、革新的なバリエーションと実装戦略を提案する能力を示す。
以上の結果から, GPT-4oによる代替案はCMSAのエキスパート設計よりも優れていた。
論文 参考訳(メタデータ) (2025-02-12T10:58:57Z) - Discovering Preference Optimization Algorithms with and for Large Language Models [50.843710797024805]
オフライン優先最適化は、LLM(Large Language Model)出力の品質を向上・制御するための重要な手法である。
我々は、人間の介入なしに、新しい最先端の選好最適化アルゴリズムを自動で発見する客観的発見を行う。
実験は、ロジスティックと指数的損失を適応的にブレンドする新しいアルゴリズムであるDiscoPOPの最先端性能を示す。
論文 参考訳(メタデータ) (2024-06-12T16:58:41Z) - Learning Reward and Policy Jointly from Demonstration and Preference Improves Alignment [58.049113055986375]
我々は、報酬モデルとポリシーをトレーニングするために、AIHF(Alignment with Integrated Human Feedback)と呼ばれる単一ステージアプローチを開発する。
提案した手法は、一般的なアライメントアルゴリズムに容易に還元し、活用できる、効率的なアルゴリズムの集合を認めている。
本研究では,LLMにおけるアライメント問題と,MuJoCoにおけるロボット制御問題を含む広範な実験により,提案手法の有効性を実証する。
論文 参考訳(メタデータ) (2024-06-11T01:20:53Z) - Primitive Agentic First-Order Optimization [0.0]
本研究では,一階強化学習として,原始状態表現とエージェント環境相互作用を組み合わせた概念実証研究を提案する。
その結果,RLに基づく最適化では,基本的RL法と簡潔な部分的状態表現を組み合わせることで,複雑性の管理を最適化できることがわかった。
論文 参考訳(メタデータ) (2024-06-07T11:13:38Z) - Unleashing the Potential of Large Language Models as Prompt Optimizers: Analogical Analysis with Gradient-based Model Optimizers [108.72225067368592]
本稿では,大規模言語モデル(LLM)に基づくプロンプトの設計について検討する。
モデルパラメータ学習における2つの重要な要素を同定する。
グラディエントにインスパイアされた Prompt ベースの GPO を開発した。
論文 参考訳(メタデータ) (2024-02-27T15:05:32Z) - Acceleration in Policy Optimization [50.323182853069184]
我々は、楽観的かつ適応的な更新を通じて、政策改善のステップにフォレストを組み込むことにより、強化学習(RL)における政策最適化手法を加速するための統一パラダイムに向けて研究する。
我々は、楽観主義を、政策の将来行動の予測モデルとして定義し、適応性は、過度な予測や変化に対する遅延反応からエラーを軽減するために、即時かつ予測的な修正措置をとるものである。
我々は,メタグラディエント学習による適応型楽観的ポリシー勾配アルゴリズムを設計し,実証的なタスクにおいて,加速度に関連するいくつかの設計選択を実証的に強調する。
論文 参考訳(メタデータ) (2023-06-18T15:50:57Z) - Provable Reward-Agnostic Preference-Based Reinforcement Learning [61.39541986848391]
PbRL(Preference-based Reinforcement Learning)は、RLエージェントが、軌道上のペアワイドな嗜好に基づくフィードバックを用いてタスクを最適化することを学ぶパラダイムである。
本稿では,隠れた報酬関数の正確な学習を可能にする探索軌道を求める理論的報酬非依存PbRLフレームワークを提案する。
論文 参考訳(メタデータ) (2023-05-29T15:00:09Z) - Online Control of Adaptive Large Neighborhood Search using Deep Reinforcement Learning [4.374837991804085]
DR-ALNSと呼ばれる深層強化学習に基づくアプローチを導入し、演算子を選択し、パラメータを調整し、検索全体を通して受け入れ基準を制御する。
提案手法は,IJCAIコンペティションで提示されたオリエンテーリングウェイトと時間窓の問題に対して評価する。
その結果,本手法はバニラALNSよりも優れており,ALNSはベイジアン最適化と2つの最先端DRLアプローチに適合していることがわかった。
論文 参考訳(メタデータ) (2022-11-01T21:33:46Z) - Accelerated Federated Learning with Decoupled Adaptive Optimization [53.230515878096426]
フェデレートドラーニング(FL)フレームワークは、クライアント上のトレーニングデータのプライバシを維持しながら、共有モデルを協調的に学習することを可能にする。
近年,SGDM,Adam,AdaGradなどの集中型適応最適化手法をフェデレートした設定に一般化するためのイテレーションが多数実施されている。
本研究は、常微分方程式(ODE)のダイナミクスの観点から、FLの新しい適応最適化手法を開発することを目的としている。
論文 参考訳(メタデータ) (2022-07-14T22:46:43Z) - Deep Reinforcement Learning for Exact Combinatorial Optimization:
Learning to Branch [13.024115985194932]
本稿では、強化学習(RL)パラダイムを用いた最適化において、データラベリングと推論の問題を解決するための新しいアプローチを提案する。
我々は模倣学習を用いてRLエージェントをブートストラップし、PPO(Proximal Policy)を使用してグローバルな最適なアクションを探索する。
論文 参考訳(メタデータ) (2022-06-14T16:35:58Z) - Sample-Efficient, Exploration-Based Policy Optimisation for Routing
Problems [2.6782615615913348]
本稿では,エントロピーに基づく新しい強化学習手法を提案する。
さらに、我々は、期待したリターンを最大化する、政治以外の強化学習手法を設計する。
我々のモデルは様々な経路問題に一般化可能であることを示す。
論文 参考訳(メタデータ) (2022-05-31T09:51:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。