論文の概要: Instance-Conditioned Adaptation for Large-scale Generalization of Neural Combinatorial Optimization
- arxiv url: http://arxiv.org/abs/2405.01906v1
- Date: Fri, 3 May 2024 08:00:19 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-06 13:35:25.934605
- Title: Instance-Conditioned Adaptation for Large-scale Generalization of Neural Combinatorial Optimization
- Title（参考訳）: ニューラルコンビネーション最適化の大規模一般化のためのインスタンス記述型適応
- Authors: Changliang Zhou, Xi Lin, Zhenkun Wang, Xialiang Tong, Mingxuan Yuan, Qingfu Zhang,
- Abstract要約: 本研究は,ニューラル最適化の大規模一般化のための新しいインスタンス・コンディション適応モデル(ICAM)を提案する。
特に,NCOモデルのための強力なインスタンス条件付きルーティング適応モジュールを設計する。
我々は,ラベル付き最適解を使わずに,モデルがクロススケールな特徴を学習することのできる,効率的な3段階強化学習ベーストレーニング手法を開発した。
- 参考スコア（独自算出の注目度）: 15.842155380912002
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The neural combinatorial optimization (NCO) approach has shown great potential for solving routing problems without the requirement of expert knowledge. However, existing constructive NCO methods cannot directly solve large-scale instances, which significantly limits their application prospects. To address these crucial shortcomings, this work proposes a novel Instance-Conditioned Adaptation Model (ICAM) for better large-scale generalization of neural combinatorial optimization. In particular, we design a powerful yet lightweight instance-conditioned adaptation module for the NCO model to generate better solutions for instances across different scales. In addition, we develop an efficient three-stage reinforcement learning-based training scheme that enables the model to learn cross-scale features without any labeled optimal solution. Experimental results show that our proposed method is capable of obtaining excellent results with a very fast inference time in solving Traveling Salesman Problems (TSPs) and Capacitated Vehicle Routing Problems (CVRPs) across different scales. To the best of our knowledge, our model achieves state-of-the-art performance among all RL-based constructive methods for TSP and CVRP with up to 1,000 nodes.
- Abstract（参考訳）: NCO(Neural combinatorial Optimization)アプローチは、専門家の知識を必要とせずにルーティング問題を解決する大きな可能性を示している。
しかし、既存の構成的NCO手法では、大規模インスタンスを直接解決できないため、アプリケーションの見通しは著しく制限される。
これらの重要な欠点に対処するため、ニューラルコンビナトリ最適化の大規模一般化のための新しいICAM(Instance-Conditioned Adaptation Model)を提案する。
特に、異なるスケールのインスタンスに対してより良いソリューションを生成するために、NCOモデルのための強力で軽量なインスタンス条件適応モジュールを設計する。
さらに,ラベル付き最適解を使わずに,モデルがクロススケールな特徴を学習できる3段階強化学習に基づく効率的なトレーニング手法を開発した。
実験の結果,提案手法はトラベリングセールスマン問題 (TSP) とキャパシタントカールーティング問題 (CVRP) を異なるスケールで解く際に,非常に高速な推論時間で優れた結果が得られることがわかった。
我々の知る限り、我々のモデルは、最大1000ノードのTSPとCVRPのためのすべてのRLベースの構築手法の中で、最先端のパフォーマンスを達成する。
関連論文リスト
- 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) - Self-Improved Learning for Scalable Neural Combinatorial Optimization [15.842155380912002]
本研究は、ニューラルネットワーク最適化のスケーラビリティを向上させるための新しい自己改善学習(SIL)手法を提案する。
我々は,ラベル付きデータを使わずに大規模問題インスタンス上での直接モデルトレーニングを可能にする,効率的な自己改善機構を開発した。
さらに,計算モデルに対する線形注意複雑化機構を設計し,オーバヘッドの少ない大規模問題インスタンスを効率的に処理する。
論文 参考訳（メタデータ） (2024-03-28T16:46:53Z) - An Efficient Learning-based Solver Comparable to Metaheuristics for the
Capacitated Arc Routing Problem [67.92544792239086]
我々は,高度メタヒューリスティックスとのギャップを著しく狭めるため,NNベースの解法を導入する。
まず,方向対応型注意モデル(DaAM)を提案する。
第2に、教師付き事前学習を伴い、堅牢な初期方針を確立するための教師付き強化学習スキームを設計する。
論文 参考訳（メタデータ） (2024-03-11T02:17:42Z) - Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale
Generalization [15.189182646851865]
本稿では、この重要な問題に対処する強力な一般化能力を持つ新しい軽量重復号器(LEHD)モデルを提案する。
提案するLEHDモデルに対して,データ効率のトレーニング手法とフレキシブルな解法機構を開発する。
提案したLEHDモデルは,建設的NCOの最先端性能を大幅に向上させることができることを確認した。
論文 参考訳（メタデータ） (2023-10-12T02:18:50Z) - 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) - On the Generalization of Neural Combinatorial Optimization Heuristics [0.7049738935364298]
提案手法は,2つの最先端モデルの一般化を著しく改善することを示す。
我々は、個別の学習課題として、与えられたインスタンス分布上でのCO問題の解法を定式化する。
新しいタスクに適応する能力の最適化を目的として,様々なタスクのモデル学習のためのメタラーニング手法について検討する。
論文 参考訳（メタデータ） (2022-06-01T22:39:35Z) - Sample-Efficient, Exploration-Based Policy Optimisation for Routing
Problems [2.6782615615913348]
本稿では,エントロピーに基づく新しい強化学習手法を提案する。
さらに、我々は、期待したリターンを最大化する、政治以外の強化学習手法を設計する。
我々のモデルは様々な経路問題に一般化可能であることを示す。
論文 参考訳（メタデータ） (2022-05-31T09:51:48Z) - Neural Combinatorial Optimization: a New Player in the Field [69.23334811890919]
本稿では,ニューラルネットワークに基づくアルゴリズムの古典的最適化フレームワークへの導入に関する批判的分析を行う。
性能, 転送可能性, 計算コスト, 大規模インスタンスなど, これらのアルゴリズムの基本的側面を分析するために, 総合的研究を行った。
論文 参考訳（メタデータ） (2022-05-03T07:54:56Z) - Efficient Model-Based Multi-Agent Mean-Field Reinforcement Learning [89.31889875864599]
マルチエージェントシステムにおける学習に有効なモデルベース強化学習アルゴリズムを提案する。
我々の理論的な貢献は、MFCのモデルベース強化学習における最初の一般的な後悔の限界である。
コア最適化問題の実用的なパラメトリゼーションを提供する。
論文 参考訳（メタデータ） (2021-07-08T18:01:02Z) - Automatically Learning Compact Quality-aware Surrogates for Optimization
Problems [55.94450542785096]
未知パラメータで最適化問題を解くには、未知パラメータの値を予測し、これらの値を用いて問題を解くための予測モデルを学ぶ必要がある。
最近の研究によると、複雑なトレーニングモデルパイプラインのレイヤーとして最適化の問題を含めると、観測されていない意思決定の繰り返しを予測することになる。
我々は,大規模最適化問題の低次元サロゲートモデルを学習することにより,解の質を向上させることができることを示す。
論文 参考訳（メタデータ） (2020-06-18T19:11:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。