論文の概要: Diversity Optimization for Travelling Salesman Problem via Deep Reinforcement Learning
- arxiv url: http://arxiv.org/abs/2501.00884v1
- Date: Wed, 01 Jan 2025 16:08:40 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-01-05 17:16:11.973599
- Title: Diversity Optimization for Travelling Salesman Problem via Deep Reinforcement Learning
- Title（参考訳）: 深層強化学習によるトラベリングセールスマン問題の多様性最適化
- Authors: Qi Li, Zhiguang Cao, Yining Ma, Yaoxin Wu, Yue-Jiao Gong,
- Abstract要約: 既存のトラベリングセールスマン問題(TSP)のニューラルメソッドは主に、単一の最適解を見つけることを目的としている。
本稿では,主にエンコーダ-デコーダ構造ポリシを特徴とする,深層強化学習に基づくニューラルソルバを提案する。
- 参考スコア（独自算出の注目度）: 29.551883712536295
- License:
- Abstract: Existing neural methods for the Travelling Salesman Problem (TSP) mostly aim at finding a single optimal solution. To discover diverse yet high-quality solutions for Multi-Solution TSP (MSTSP), we propose a novel deep reinforcement learning based neural solver, which is primarily featured by an encoder-decoder structured policy. Concretely, on the one hand, a Relativization Filter (RF) is designed to enhance the robustness of the encoder to affine transformations of the instances, so as to potentially improve the quality of the found solutions. On the other hand, a Multi-Attentive Adaptive Active Search (MA3S) is tailored to allow the decoders to strike a balance between the optimality and diversity. Experimental evaluations on benchmark instances demonstrate the superiority of our method over recent neural baselines across different metrics, and its competitive performance against state-of-the-art traditional heuristics with significantly reduced computational time, ranging from $1.3\times$ to $15\times$ faster. Furthermore, we demonstrate that our method can also be applied to the Capacitated Vehicle Routing Problem (CVRP).
- Abstract（参考訳）: 既存のトラベリングセールスマン問題(TSP)のニューラルメソッドは主に、単一の最適解を見つけることを目的としている。
MSTSP(Multi-Solution TSP)のための多種多様な高品質なソリューションを発見するために,エンコーダ-デコーダ構造ポリシを主目的とする,深層強化学習に基づくニューラルソルバを提案する。
具体的には、相対化フィルタ(RF)は、エンコーダの堅牢性を高め、インスタンスの変換をアフィン化し、検出されたソリューションの品質を向上するために設計されている。
一方,MA3S(Multi-Attentive Adaptive Active Search)では,デコーダが最適性と多様性のバランスをとるように調整されている。
ベンチマークインスタンス上での実験的な評価は、異なるメトリクスにわたる最近の神経ベースラインよりも、我々の手法が優れていること、そして、計算時間を大幅に短縮した最先端の従来のヒューリスティックに対する競争性能が、$1.3\times$から$15\times$高速であることを示す。
さらに, CVRP(Capacitated Vehicle Routing Problem)にも適用可能であることを示す。
関連論文リスト
- Multiobjective Vehicle Routing Optimization with Time Windows: A Hybrid Approach Using Deep Reinforcement Learning and NSGA-II [52.083337333478674]
本稿では、時間窓を用いた多目的車両ルーティング問題(MOVRPTW)に対処するために、ウェイト・アウェア・ディープ・強化学習(WADRL)手法を提案する。
WADRLの結果を最適化するために非支配的ソート遺伝的アルゴリズム-II (NSGA-II) 法を用いる。
論文 参考訳（メタデータ） (2024-07-18T02:46:06Z) - Leader Reward for POMO-Based Neural Combinatorial Optimization [8.301694061287565]
本稿では、最適解を生成するモデルの能力を高めるために、Lead Rewardを提案する。
我々は、Lead Rewardがモデルによって生成される最適なソリューションの品質を大幅に改善することを示した。
論文 参考訳（メタデータ） (2024-05-22T19:27:03Z) - Instance-Conditioned Adaptation for Large-scale Generalization of Neural Combinatorial Optimization [15.842155380912002]
本研究は,ニューラル最適化の大規模一般化のための新しいインスタンス・コンディション適応モデル(ICAM)を提案する。
特に,NCOモデルのための強力なインスタンス条件付きルーティング適応モジュールを設計する。
我々は,ラベル付き最適解を使わずに,モデルがクロススケールな特徴を学習することのできる,効率的な3段階強化学習ベーストレーニング手法を開発した。
論文 参考訳（メタデータ） (2024-05-03T08:00:19Z) - BalMCTS: Balancing Objective Function and Search Nodes in MCTS for
Constraint Optimization Problems [7.196057722218442]
制約問題最適化(COP)は、通常ブランチ・アンド・バウンド(B&B)法によって解決される問題において、複雑な課題を提起する。
COPを解くための深度優先探索アルゴリズムに基づく新しいニューラルネットワークアルゴリズムを提案する。
提案手法は,最初の5つの実現可能な解のうち17.63%未満のギャップを有する実現可能な解を同定する。
論文 参考訳（メタデータ） (2023-12-26T03:09:08Z) - Efficient Meta Neural Heuristic for Multi-Objective Combinatorial
Optimization [35.09656455088854]
本稿では,多目的最適化問題を解くために,効率的なメタニューラルベクトル(EMNH)を提案する。
EMNHは、ソリューションの品質と学習効率の点で最先端のニューラルネットワークより優れている。
論文 参考訳（メタデータ） (2023-10-22T08:59:02Z) - Equivariant Deep Weight Space Alignment [54.65847470115314]
本稿では,ウェイトアライメント問題を解決するための学習を目的とした新しいフレームワークを提案する。
まず、重み調整が2つの基本対称性に一致することを証明し、それからこれらの対称性を尊重する深いアーキテクチャを提案する。
論文 参考訳（メタデータ） (2023-10-20T10:12:06Z) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳（メタデータ） (2023-10-08T23:39:38Z) - Backpropagation of Unrolled Solvers with Folded Optimization [55.04219793298687]
ディープネットワークにおけるコンポーネントとしての制約付き最適化モデルの統合は、多くの専門的な学習タスクに有望な進歩をもたらした。
1つの典型的な戦略はアルゴリズムのアンローリングであり、これは反復解法の操作による自動微分に依存している。
本稿では,非ロール最適化の後方通過に関する理論的知見を提供し,効率よく解けるバックプロパゲーション解析モデルを生成するシステムに繋がる。
論文 参考訳（メタデータ） (2023-01-28T01:50:42Z) - 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) - Multi-Agent Deep Reinforcement Learning in Vehicular OCC [14.685237010856953]
我々は車載OCCにおけるスペクトル効率最適化手法を提案する。
我々は最適化問題をマルコフ決定プロセス(MDP)としてモデル化し、オンラインで適用可能なソリューションの利用を可能にする。
提案手法の性能を広範囲なシミュレーションにより検証し,提案手法の様々な変種とランダムな手法との比較を行った。
論文 参考訳（メタデータ） (2022-05-05T14:25:54Z) - Efficient Model-Based Multi-Agent Mean-Field Reinforcement Learning [89.31889875864599]
マルチエージェントシステムにおける学習に有効なモデルベース強化学習アルゴリズムを提案する。
我々の理論的な貢献は、MFCのモデルベース強化学習における最初の一般的な後悔の限界である。
コア最適化問題の実用的なパラメトリゼーションを提供する。
論文 参考訳（メタデータ） (2021-07-08T18:01:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。