論文の概要: Dynamic Location Search for Identifying Maximum Weighted Independent Sets in Complex Networks

• arxiv url: http://arxiv.org/abs/2505.04674v1
• Date: Wed, 07 May 2025 10:35:53 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-09 21:43:49.626984
• Title: Dynamic Location Search for Identifying Maximum Weighted Independent Sets in Complex Networks
• Title（参考訳）: 複雑ネットワークにおける最大重み付き独立集合の動的位置探索
• Authors: Enqiang Zhu, Chenkai Hao, Chanjuan Liu, Yongsheng Rao,
• Abstract要約: 本稿では,最大重み付き独立集合(MWIS)問題を解くための,新しい,効率的なアルゴリズムを提案する。 MWIS問題のNPハード性を考えると,提案アルゴリズムであるDynLSには3つの重要なイノベーションが組み込まれている。 我々の実験結果はDynLSの優れた性能を示し、1000秒以内の高品質なソリューションを一貫して提供した。
• 参考スコア（独自算出の注目度）: 0.47248250311484113
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: While Artificial intelligence (AI), including Generative AI, are effective at generating high-quality traffic data and optimization solutions in intelligent transportation systems (ITSs), these techniques often demand significant training time and computational resources, especially in large-scale and complex scenarios. To address this, we introduce a novel and efficient algorithm for solving the maximum weighted independent set (MWIS) problem, which can be used to model many ITSs applications, such as traffic signal control and vehicle routing. Given the NP-hard nature of the MWIS problem, our proposed algorithm, DynLS, incorporates three key innovations to solve it effectively. First, it uses a scores-based adaptive vertex perturbation (SAVP) technique to accelerate convergence, particularly in sparse graphs. Second, it includes a region location mechanism (RLM) to help escape local optima by dynamically adjusting the search space. Finally, it employs a novel variable neighborhood descent strategy, ComLS, which combines vertex exchange strategies with a reward mechanism to guide the search toward high-quality solutions. Our experimental results demonstrate DynLS's superior performance, consistently delivering high-quality solutions within 1000 seconds. DynLS outperformed five leading algorithms across 360 test instances, achieving the best solution for 350 instances and surpassing the second-best algorithm, Cyclic-Fast, by 177 instances. Moreover, DynLS matched Cyclic-Fast's convergence speed, highlighting its efficiency and practicality. This research represents a significant advancement in heuristic algorithms for the MWIS problem, offering a promising approach to aid AI techniques in optimizing intelligent transportation systems.
• Abstract（参考訳）: Generative AIを含む人工知能(AI)は、インテリジェントトランスポートシステム(ITS)で高品質なトラフィックデータと最適化ソリューションを生成するのに効果的であるが、これらの技術は、特に大規模で複雑なシナリオにおいて、大きなトレーニング時間と計算資源を必要とすることが多い。 そこで本研究では,交通信号制御や車両のルーティングなど,多数のITS応用をモデル化するための,MWIS問題の解法を提案する。 MWIS問題のNPハード性を考えると,提案アルゴリズムであるDynLSには3つの重要なイノベーションが組み込まれている。 まず、スコアベースの適応頂点摂動(SAVP)技術を用いて収束を加速する。 第二に、探索空間を動的に調整することで局所最適から逃れるのに役立つ領域位置機構(RLM)を含んでいる。 最後に,バーテックス交換戦略と報奨機構を組み合わせて高品質なソリューションへの探索を誘導する,新しい可変近傍降下戦略であるComLSを採用している。 我々の実験結果はDynLSの優れた性能を示し、1000秒以内の高品質なソリューションを一貫して提供した。 DynLSは360のテストインスタンスで5つの主要なアルゴリズムを上回り、350のインスタンスで最高のソリューションを達成し、第2のベストアルゴリズムであるCyclic-Fastを177のインスタンスで上回った。 さらにDynLSはCyclic-Fastの収束速度と一致し、その効率性と実用性を強調した。 この研究は、MWIS問題に対するヒューリスティックアルゴリズムの大幅な進歩を示し、インテリジェントトランスポートシステムの最適化においてAI技術を支援するための有望なアプローチを提供する。

関連論文リスト

• Accelerating Vehicle Routing via AI-Initialized Genetic Algorithms [55.78505925402658]
  車両ルーティング問題(VRP)は、トラベリングセールスパーソン問題の延長であり、進化的最適化における基本的なNPハードチャレンジである。 遺伝的アルゴリズムによってさらに最適化された初期解を迅速に生成するために、強化学習エージェント(事前インスタンスで訓練された)を使用した新しい最適化フレームワークを導入する。 例えば、EARLIは1秒以内に500カ所の車両ルーティングを処理し、同じソリューション品質の現在のソルバよりも10倍高速で、リアルタイムやインタラクティブなルーティングのようなアプリケーションを可能にする。
  論文  参考訳（メタデータ） (2025-04-08T15:21:01Z)
• DNN Partitioning, Task Offloading, and Resource Allocation in Dynamic Vehicular Networks: A Lyapunov-Guided Diffusion-Based Reinforcement Learning Approach [49.56404236394601]
  本稿では,Vehicular Edge Computingにおける共同DNNパーティショニング,タスクオフロード,リソース割り当ての問題を定式化する。 我々の目標は、時間とともにシステムの安定性を保証しながら、DNNベースのタスク完了時間を最小化することである。 拡散モデルの革新的利用を取り入れたマルチエージェント拡散に基づく深層強化学習(MAD2RL)アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-06-11T06:31:03Z)
• Multi-Objective Optimization Using Adaptive Distributed Reinforcement Learning [8.471466670802815]
  本稿では,多目的・マルチエージェント強化学習(MARL)アルゴリズムを提案する。 我々はエッジクラウドコンピューティングを用いたITS環境でアルゴリズムをテストする。 また,本アルゴリズムは,モジュール化および非同期オンライントレーニング手法により,様々な実用上の問題にも対処する。
  論文  参考訳（メタデータ） (2024-03-13T18:05:16Z)
• Spatial-temporal-demand clustering for solving large-scale vehicle routing problems with time windows [0.0]
  本稿では,クラスタリングを用いて顧客をグループ化するDRI(Decompose-route-improve)フレームワークを提案する。 その類似度基準は、顧客の空間的、時間的、需要データを含む。 本研究では,解答サブプロブレム間でプルーンド局所探索(LS)を適用し,全体の解法を改善する。
  論文  参考訳（メタデータ） (2024-01-20T06:06:01Z)
• Qubit efficient quantum algorithms for the vehicle routing problem on NISQ processors [48.68474702382697]
  時間窓付き車両ルーティング問題(VRPTW)は、ロジスティクス業界で直面する一般的な最適化問題である。 そこで本研究では,以前に導入した量子ビット符号化方式を用いて,バイナリ変数の数を削減した。
  論文  参考訳（メタデータ） (2023-06-14T13:44:35Z)
• High-Speed Resource Allocation Algorithm Using a Coherent Ising Machine for NOMA Systems [3.6406488220483326]
  NOMA手法の有効性を十分に活用する上で重要な課題は、リソース割り当ての最適化である。 NOMAシステムにおけるチャネル割り当てのためのコヒーレントIsing Machine(CIM)に基づく最適化手法を提案する。 提案手法は, 高速化と最適解の両面において優れていることを示す。
  論文  参考訳（メタデータ） (2022-12-03T09:22:54Z)
• ARES: An Efficient Algorithm with Recurrent Evaluation and Sampling-Driven Inference for Maximum Independent Set [48.57120672468062]
  本稿では、2つの革新的な手法を取り入れたMIS問題に対する効率的なアルゴリズムを提案する。 提案アルゴリズムは、解の質、計算効率、安定性の点で最先端のアルゴリズムより優れている。
  論文  参考訳（メタデータ） (2022-08-16T14:39:38Z)
• Reconfigurable Intelligent Surface Assisted Mobile Edge Computing with Heterogeneous Learning Tasks [53.1636151439562]
  モバイルエッジコンピューティング(MEC)は、AIアプリケーションに自然なプラットフォームを提供します。 再構成可能なインテリジェントサーフェス(RIS)の助けを借りて、MECで機械学習タスクを実行するインフラストラクチャを提示します。 具体的には,モバイルユーザの送信パワー,基地局のビームフォーミングベクトル,risの位相シフト行列を共同で最適化することにより,参加ユーザの学習誤差を最小化する。
  論文  参考訳（メタデータ） (2020-12-25T07:08:50Z)
• Distributed Multi-agent Meta Learning for Trajectory Design in Wireless Drone Networks [151.27147513363502]
  本稿では,動的無線ネットワーク環境で動作するエネルギー制約型ドローン群に対する軌道設計の問題点について検討する。 値ベース強化学習(VDRL)ソリューションとメタトレイン機構を提案する。
  論文  参考訳（メタデータ） (2020-12-06T01:30:12Z)

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

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