論文の概要: Hybridising Reinforcement Learning and Heuristics for Hierarchical Directed Arc Routing Problems

• arxiv url: http://arxiv.org/abs/2501.00852v1
• Date: Wed, 01 Jan 2025 14:29:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-05 17:13:03.995889
• Title: Hybridising Reinforcement Learning and Heuristics for Hierarchical Directed Arc Routing Problems
• Title（参考訳）: 階層指向アークルーティング問題に対する強化学習とヒューリスティックス
• Authors: Van Quang Nguyen, Quoc Chuong Nguyen, Thu Huong Dang, Truong-Son Hy,
• Abstract要約: HDCARPは容量アークルーティング問題(CARP)の拡張である 本稿では,HDCARPの計算課題を効果的に解決する手法を提案する。 我々はこのハイブリッドアルゴリズムをHRDA(Hybrid Reinforcement Learning and Heuristic Algorithm for Directed Arc Routing)と呼ぶ。
• 参考スコア（独自算出の注目度）: 4.2873412319680035
• License:
• Abstract: The Hierarchical Directed Capacitated Arc Routing Problem (HDCARP) is an extension of the Capacitated Arc Routing Problem (CARP), where the arcs of a graph are divided into classes based on their priority. The traversal of these classes is determined by either precedence constraints or a hierarchical objective, resulting in two distinct HDCARP variants. To the best of our knowledge, only one matheuristic has been proposed for these variants, but it performs relatively slowly, particularly for large-scale instances (Ha et al., 2024). In this paper, we propose a fast heuristic to efficiently address the computational challenges of HDCARP. Furthermore, we incorporate Reinforcement Learning (RL) into our heuristic to effectively guide the selection of local search operators, resulting in a hybrid algorithm. We name this hybrid algorithm as the Hybrid Reinforcement Learning and Heuristic Algorithm for Directed Arc Routing (HRDA). The hybrid algorithm adapts to changes in the problem dynamically, using real-time feedback to improve routing strategies and solution's quality by integrating heuristic methods. Extensive computational experiments on artificial instances demonstrate that this hybrid approach significantly improves the speed of the heuristic without deteriorating the solution quality. Our source code is publicly available at: https://github.com/HySonLab/ArcRoute
• Abstract（参考訳）: Hierarchical Directed Capacitated Arc Routing Problem (HDCARP) は Capacitated Arc Routing Problem (CARP) の拡張であり、グラフの弧はその優先度に基づいてクラスに分けられる。 これらのクラスのトラバースは、優先順位制約または階層的目的によって決定され、2つの異なるHDCARP変異をもたらす。 我々の知る限りでは、これらの変種に対しては1つの数理学しか提案されていないが、特に大規模インスタンス(Ha et al , 2024)では比較的遅い。 本稿では,HDCARPの計算問題を効率的に解くための高速ヒューリスティックを提案する。 さらに,Reinforcement Learning (RL) をヒューリスティックに組み込んで局所探索演算子の選択を効果的に導くことで,ハイブリッドアルゴリズムを実現する。 我々はこのハイブリッドアルゴリズムをHRDA(Hybrid Reinforcement Learning and Heuristic Algorithm for Directed Arc Routing)と呼ぶ。 ハイブリッドアルゴリズムは、リアルタイムフィードバックを用いて、ヒューリスティックな手法を統合することにより、ルーティング戦略とソリューションの品質を改善する。 人工インスタンスに関する大規模な計算実験により、このハイブリッドアプローチは解の質を劣化させることなくヒューリスティックの速度を大幅に改善することを示した。 私たちのソースコードは、https://github.com/HySonLab/ArcRouteで公開されています。

関連論文リスト

• Faster Optimal Coalition Structure Generation via Offline Coalition Selection and Graph-Based Search [61.08720171136229]
  本稿では,3つの革新的手法のハイブリッド化に基づく問題に対する新しいアルゴリズムSMARTを提案する。 これらの2つの手法は動的プログラミングに基づいており、評価のために選択された連立関係とアルゴリズムの性能の強力な関係を示す。 我々の手法は、問題にアプローチする新しい方法と、その分野に新しいレベルの精度をもたらす。
  論文  参考訳（メタデータ） (2024-07-22T23:24:03Z)
• An Efficient Learning-based Solver Comparable to Metaheuristics for the Capacitated Arc Routing Problem [67.92544792239086]
  我々は,高度メタヒューリスティックスとのギャップを著しく狭めるため,NNベースの解法を導入する。 まず,方向対応型注意モデル(DaAM)を提案する。 第2に、教師付き事前学習を伴い、堅牢な初期方針を確立するための教師付き強化学習スキームを設計する。
  論文  参考訳（メタデータ） (2024-03-11T02:17:42Z)
• Enhancing Column Generation by Reinforcement Learning-Based Hyper-Heuristic for Vehicle Routing and Scheduling Problems [9.203492057735074]
  カラム生成(CG)は変数を動的に生成することで大規模問題を解決する重要な手法である。 CGの性能を高めるために,RLHHと呼ばれる強化学習に基づく超ヒューリスティックフレームワークを提案する。
  論文  参考訳（メタデータ） (2023-10-15T00:05:50Z)
• Bringing regularized optimal transport to lightspeed: a splitting method adapted for GPUs [9.297785393486976]
  正規化された最適輸送のための効率的なアルゴリズムを提案する。 従来の手法とは対照的に、ダグラス・ラフフォード分割法を用いて、幅広い正規化器を扱える効率的な解法を開発した。
  論文  参考訳（メタデータ） (2023-05-29T12:04:55Z)
• Stochastic Unrolled Federated Learning [85.6993263983062]
  本稿では,UnRolled Federated Learning (SURF)を導入する。 提案手法は,この拡張における2つの課題,すなわち,非学習者へのデータセット全体の供給の必要性と,フェデレート学習の分散的性質に対処する。
  論文  参考訳（メタデータ） (2023-05-24T17:26:22Z)
• Solving the vehicle routing problem with deep reinforcement learning [0.0]
  本稿では,NP-Hard 問題のクラスに属する有名な問題である Vehicle Routing Problem (VRP) に対する RL の適用について述べる。 第2フェーズでは、アクターと批評家の背後にあるニューラルアーキテクチャが確立され、畳み込みニューラルネットワークに基づいたニューラルアーキテクチャを採用することが選択された。 広範囲なインスタンスで行った実験では、アルゴリズムが優れた一般化能力を持ち、短時間で良い解に達することが示されている。
  論文  参考訳（メタデータ） (2022-07-30T12:34:26Z)
• Reinforcement Learning for Branch-and-Bound Optimisation using Retrospective Trajectories [72.15369769265398]
  機械学習は分岐のための有望なパラダイムとして登場した。 分岐のための単純かつ効果的なRLアプローチであるレトロ分岐を提案する。 我々は現在最先端のRL分岐アルゴリズムを3～5倍に上回り、500の制約と1000の変数を持つMILP上での最高のILメソッドの性能の20%以内である。
  論文  参考訳（メタデータ） (2022-05-28T06:08:07Z)
• DAAS: Differentiable Architecture and Augmentation Policy Search [107.53318939844422]
  この研究は、ニューラルネットワークとデータ拡張のカップリングの可能性を検討し、それらを共同で検索する効果的なアルゴリズムを提案する。 CIFAR-10では97.91%、ImageNetデータセットでは76.6%の精度で97.91%の精度を達成し、検索アルゴリズムの優れた性能を示している。
  論文  参考訳（メタデータ） (2021-09-30T17:15:17Z)
• Adaptive Approach For Sparse Representations Using The Locally Competitive Algorithm For Audio [5.6394515393964575]
  本稿ではガンマチャープのパラメータを最適化するための適応的アプローチを提案する。 提案手法はLCAのニューラルネットワークを利用してガンマチャープのフィルタバンクを自動的に適応する。 以上の結果から, このアプローチによるLCAの性能向上は, スパーシリティ, 再建品質, 収束時間の観点から示される。
  論文  参考訳（メタデータ） (2021-09-29T20:26:16Z)
• Phase Retrieval using Expectation Consistent Signal Recovery Algorithm based on Hypernetwork [73.94896986868146]
  位相検索は現代の計算イメージングシステムにおいて重要な要素である。 近年のディープラーニングの進歩は、堅牢で高速なPRの新たな可能性を開いた。 我々は、既存の制限を克服するために、深層展開のための新しいフレームワークを開発する。
  論文  参考訳（メタデータ） (2021-01-12T08:36:23Z)

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

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