論文の概要: Knowledge-Guided Memetic Algorithm for Capacitated Arc Routing Problems with Time-Dependent Service Costs

• arxiv url: http://arxiv.org/abs/2507.21740v1
• Date: Tue, 29 Jul 2025 12:17:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-30 17:08:56.164285
• Title: Knowledge-Guided Memetic Algorithm for Capacitated Arc Routing Problems with Time-Dependent Service Costs
• Title（参考訳）: 時間依存サービスコストを考慮した有極アークルーティング問題に対する知識誘導メメティックアルゴリズム
• Authors: Qingya Li, Shengcai Liu, Wenjie Chen, Juan Zou, Ke Tang, Xin Yao,
• Abstract要約: 本稿では,ゴールデンセクション探索と負相関探索を用いた知識誘導メメティックアルゴリズムを提案する。 最先端の手法よりも高い探索効率を実現する。
• 参考スコア（独自算出の注目度）: 18.734871315760717
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The capacitated arc routing problem with time-dependent service costs (CARPTDSC) is a challenging combinatorial optimization problem that arises from winter gritting applications. CARPTDSC has two main challenges about time consumption. First, it is an NP-hard problem. Second, the time-dependent service costs of tasks require frequent evaluations during the search process, significantly increasing computational effort. These challenges make it difficult for existing algorithms to perform efficient searches, often resulting in limited efficiency. To address these issues, this paper proposes a knowledge-guided memetic algorithm with golden section search and negatively correlated search (KGMA-GN), where two knowledge-guided strategies are introduced to improve search efficiency. First, a knowledge-guided initialization strategy (KGIS) is proposed to generate high-quality initial solutions to speed up convergence. Second, a knowledge-guided small-step-size local search strategy (KGSLSS) is proposed to filter out invalid moves, thereby reducing unnecessary evaluations and saving the computation time. Experimental results on five benchmark test sets, including both small- and larger-scale instances, demonstrate that KGMA-GN achieves higher search efficiency than the state-of-the-art methods. Moreover, the ablation study further confirms that the knowledge-guided local search operators in KGSLSS can significantly reduce runtime compared to traditional operators, especially for the knowledge-guided swap operator, which achieves more than a tenfold improvement in speed.
• Abstract（参考訳）: CARPTDSC (Cacacitated arc routing problem with time-dependent service cost) は、冬研削の応用から生じる組合せ最適化問題である。 CARPTDSCには、時間消費に関する2つの大きな課題がある。 第一に、NPハード問題である。 第2に、タスクの時間依存サービスコストは、探索プロセス中に頻繁な評価を必要とし、計算労力を大幅に増加させる。 これらの課題により、既存のアルゴリズムが効率的な検索を行うのが難しくなり、しばしば効率が制限される。 そこで本研究では,ゴールデンセクション探索と負相関探索(KGMA-GN)を併用した知識誘導メメカティックアルゴリズムを提案する。 まず,知識誘導型初期化戦略(KGIS)を提案する。 次に,知識誘導型小型局所探索戦略 (KGSLSS) を提案し, 不正な動作を除去し, 不要な評価を低減し, 計算時間を短縮する。 小型および大規模のインスタンスを含む5つのベンチマークテストセットの実験結果は、KGMA-GNが最先端の手法よりも高い探索効率を達成することを示した。 さらに,KGSLSSにおける知識誘導型局所探索演算子は,知識誘導型スワップ演算子において,従来の演算子に比べて実行時間を大幅に削減できることを確認した。

関連論文リスト

• Demystifying and Enhancing the Efficiency of Large Language Model Based Search Agents [9.862334188345791]
  大規模言語モデル(LLM)に基づく検索エージェントは,複雑なタスクを解く際,顕著な能力を示した。 LLMベースの検索エージェントのための高効率推論フレームワークであるSearchAgent-Xを紹介する。 SearchAgent-Xは、vLLMやHNSWベースの検索のような最先端システムよりも一貫して優れている。
  論文  参考訳（メタデータ） (2025-05-17T16:07:01Z)
• Resource Constrained Pathfinding with Enhanced Bidirectional A* Search [10.100786663811666]
  本研究では,大規模ネットワークにおける高速かつ効率的なRCSP探索を実現するために,効率的なプルーニング戦略を用いた制約付き検索フレームワークを提案する。 その結果, 拡張されたフレームワークは, 最先端技術と比較して, 探索時間を大幅に短縮し, 最大2桁の高速化を達成できることが示唆された。
  論文  参考訳（メタデータ） (2024-12-18T14:29:40Z)
• Decision Transformer for Enhancing Neural Local Search on the Job Shop Scheduling Problem [10.316443594063173]
  ジョブショップスケジューリング問題(JSSP)とその解法アルゴリズムは、何十年もの間、アカデミックと産業の両方に永続的な関心を集めてきた。 近年、機械学習(ML)は、JSSPのための既存のソリューションと新しいソリューションの構築において、より短い時間でより良いソリューションを見つけることを目的として、ますます重要な役割を担っている。 我々は、JSSP上の大規模局所探索を効率よく効果的に制御できる、Neural Local Search(NLS)と呼ばれる最先端の深層強化学習(DRL)エージェントの上に構築する。
  論文  参考訳（メタデータ） (2024-09-04T13:33:38Z)
• Quantum Algorithm Exploration using Application-Oriented Performance Benchmarks [0.0]
  Application-Oriented BenchmarksのQED-Cスイートは、量子コンピュータの性能特性を測定する機能を提供する。 我々は,このベンチマーク手法がより複雑なアプリケーションに適用される可能性を広げる上での課題について検討する。
  論文  参考訳（メタデータ） (2024-02-14T06:55:50Z)
• Roulette-Wheel Selection-Based PSO Algorithm for Solving the Vehicle Routing Problem with Time Windows [58.891409372784516]
  本稿では,Roulette Wheel Method (RWPSO) を用いた新しいPSO手法を提案する。 RWPSOのSolomon VRPTWベンチマークデータセットを用いた実験は、RWPSOが文学の他の最先端アルゴリズムと競合していることを示している。
  論文  参考訳（メタデータ） (2023-06-04T09:18:02Z)
• ARES: An Efficient Algorithm with Recurrent Evaluation and Sampling-Driven Inference for Maximum Independent Set [48.57120672468062]
  本稿では、2つの革新的な手法を取り入れたMIS問題に対する効率的なアルゴリズムを提案する。 提案アルゴリズムは、解の質、計算効率、安定性の点で最先端のアルゴリズムより優れている。
  論文  参考訳（メタデータ） (2022-08-16T14:39:38Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• CATCH: Context-based Meta Reinforcement Learning for Transferrable Architecture Search [102.67142711824748]
  CATCHは、転送可能なarChitecture searcHのための、Context-bAsed meTa強化学習アルゴリズムである。 メタラーニングとRLの組み合わせにより、CATCHは検索空間に依存しないまま、新しいタスクに効率的に適応できる。 また、ImageNet、COCO、Cityscapesの競合ネットワークとしてクロスドメインアーキテクチャサーチを扱うこともできる。
  論文  参考訳（メタデータ） (2020-07-18T09:35:53Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。 既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。 我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
  論文  参考訳（メタデータ） (2020-05-09T02:48:23Z)
• Improving a State-of-the-Art Heuristic for the Minimum Latency Problem with Data Mining [69.00394670035747]
  ハイブリッドメタヒューリスティックスは、オペレーション研究のトレンドとなっている。 成功例は、Greedy Randomized Adaptive Search Procedures (GRASP)とデータマイニング技術を組み合わせたものだ。
  論文  参考訳（メタデータ） (2019-08-28T13:12:30Z)

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

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