論文の概要: Large Neighborhood Search based on Neural Construction Heuristics
- arxiv url: http://arxiv.org/abs/2205.00772v1
- Date: Mon, 2 May 2022 09:38:19 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-03 20:56:27.484988
- Title: Large Neighborhood Search based on Neural Construction Heuristics
- Title(参考訳): ニューラルコンストラクションヒューリスティックスに基づく大規模近傍探索
- Authors: Jonas K. Falkner, Daniela Thyssens, Lars Schmidt-Thieme
- Abstract要約: 時間窓を用いた車両経路問題の解法として,ニューラルネットワークを応用した学習構築法を提案する。
本手法では, グラフニューラルネットワークを用いて問題を符号化し, 解を自己回帰的に復号する。
- 参考スコア(独自算出の注目度): 5.210197476419621
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: We propose a Large Neighborhood Search (LNS) approach utilizing a learned
construction heuristic based on neural networks as repair operator to solve the
vehicle routing problem with time windows (VRPTW). Our method uses graph neural
networks to encode the problem and auto-regressively decodes a solution and is
trained with reinforcement learning on the construction task without requiring
any labels for supervision. The neural repair operator is combined with a local
search routine, heuristic destruction operators and a selection procedure
applied to a small population to arrive at a sophisticated solution approach.
The key idea is to use the learned model to re-construct the partially
destructed solution and to introduce randomness via the destruction heuristics
(or the stochastic policy itself) to effectively explore a large neighborhood.
- Abstract(参考訳): 本稿では,ニューラルネットワークに基づく学習構築ヒューリスティックを補修オペレータとして活用し,時間窓(vrptw)による車両経路問題を解くための大規模地区探索(lns)手法を提案する。
本手法では,グラフニューラルネットワークを用いて問題を符号化し,自己回帰的に解を復号し,監視のためのラベルを必要とせず,構築作業の強化学習によって学習する。
神経修復演算子は、局所探索ルーチン、ヒューリスティック破壊演算子、および少数の集団に適用される選択手順と組み合わせて、洗練されたソリューションアプローチに到達する。
鍵となるアイデアは、部分的に分解された解を再構成するために学習されたモデルを使い、大きな近所を効果的に探索するために破壊的ヒューリスティックス(あるいは確率的政策自体)を介してランダム性を導入することである。
関連論文リスト
- Deep Reinforcement Learning for Picker Routing Problem in Warehousing [0.6562256987706128]
本稿では、強化学習を用いて学習したピッカーツアーをモデル化するための注意に基づくニューラルネットワークを提案する。
提案手法の重要な利点は,経路の複雑さを低減できるオプションを提供することである。
論文 参考訳(メタデータ) (2024-02-05T21:25:45Z) - Too Big, so Fail? -- Enabling Neural Construction Methods to Solve
Large-Scale Routing Problems [10.832715681422842]
最先端のニューラルコンストラクション手法でさえ、単純なイテレーションによって性能が向上していることを示す。
本稿では, 解の局所的な部分を完全に破壊し, 改良された変種を再現する。
論文 参考訳(メタデータ) (2023-09-29T09:36:37Z) - The Clock and the Pizza: Two Stories in Mechanistic Explanation of
Neural Networks [59.26515696183751]
ニューラルネットワークにおけるアルゴリズム発見は、時としてより複雑であることを示す。
単純な学習問題でさえ、驚くほど多様なソリューションを許容できることが示されています。
論文 参考訳(メタデータ) (2023-06-30T17:59:13Z) - Graph Neural Networks for Decentralized Multi-Agent Perimeter Defense [111.9039128130633]
我々は,防御者の地域認識とコミュニケーショングラフから行動へのマッピングを学習する模倣学習フレームワークを開発した。
学習ネットワークの性能を実証するために、異なるチームサイズと構成のシナリオで周辺防衛ゲームを実行します。
論文 参考訳(メタデータ) (2023-01-23T19:35:59Z) - 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) - Deep Policy Dynamic Programming for Vehicle Routing Problems [89.96386273895985]
本稿では,学習ニューラルの強みと動的プログラミングアルゴリズムの強みを組み合わせた深層ポリシー動的プログラミング(d pdp)を提案する。
D PDPは、例の解からエッジを予測するために訓練されたディープニューラルネットワークから派生したポリシーを使用して、DP状態空間を優先し、制限する。
本研究では,旅行セールスマン問題 (TSP) と車両ルーティング問題 (VRP) の枠組みを評価し,ニューラルネットワークが(制限された)DPアルゴリズムの性能を向上させることを示す。
論文 参考訳(メタデータ) (2021-02-23T15:33:57Z) - Local Critic Training for Model-Parallel Learning of Deep Neural
Networks [94.69202357137452]
そこで我々は,局所的批判訓練と呼ばれる新しいモデル並列学習手法を提案する。
提案手法は,畳み込みニューラルネットワーク(CNN)とリカレントニューラルネットワーク(RNN)の両方において,階層群の更新プロセスの分離に成功したことを示す。
また,提案手法によりトレーニングされたネットワークを構造最適化に利用できることを示す。
論文 参考訳(メタデータ) (2021-02-03T09:30:45Z) - Automated Search for Resource-Efficient Branched Multi-Task Networks [81.48051635183916]
我々は,多タスクニューラルネットワークにおける分岐構造を自動的に定義する,微分可能なニューラルネットワーク探索に根ざした原理的アプローチを提案する。
本手法は,限られた資源予算内で高い性能の分岐構造を見いだすことができる。
論文 参考訳(メタデータ) (2020-08-24T09:49:19Z) - Reinforcement Learning for Combinatorial Optimization: A Survey [12.323976053967066]
最適化問題を解決する多くの伝統的なアルゴリズムは、解決を逐次構築する手工芸品を使用する。
強化学習(Reinforcement Learning, RL)は、エージェントを監督的または自己監督的な方法で訓練することにより、これらの検索を自動化する優れた代替手段を提案する。
論文 参考訳(メタデータ) (2020-03-07T16:19:45Z) - Learn to Design the Heuristics for Vehicle Routing Problem [5.37343672465706]
本稿では,車両問題 (VRP) の解法を反復的に改善する局所探索の学習手法を提案する。
ローカルサーチは、候補解をデストラクトするデストラクト演算子と、デストラクトされたものを新しいものに再構築する後続のリカバリ演算子とから構成される。
提案されたニューラルネットワークは、アクター批判フレームワークによってトレーニングされたもので、Graph Attention Networkの修正版としてエンコーダで構成されている。
論文 参考訳(メタデータ) (2020-02-20T02:39:02Z) - Multi-Vehicle Routing Problems with Soft Time Windows: A Multi-Agent
Reinforcement Learning Approach [9.717648122961483]
ソフトタイムウインドウ(MVRPSTW)を用いたマルチ車両ルーティング問題は、都市ロジスティクスシステムにおいて不可欠である。
従来の手法は計算効率と解の質のジレンマを引き起こす。
そこで本研究では,ルーティング問題の解決に要する時間的オフライントレーニングのメリットを即時評価する,Multi-Agent Attention Modelと呼ばれる新しい強化学習アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-02-13T14:26:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。