提出新算法动态搜索顶点位置，高效求解交通系统中的最大权重独立集问题。
Dynamic Location Search for Identifying Maximum Weighted Independent Sets in Complex Networks
- 基于评分的自适应顶点扰动与动态区域定位，加速收敛。
- 1000秒内解决360个实例，350次优于其他算法，领先第二名177次。
- 适合需快速求解复杂网络优化的智能交通系统研究者使用。
尽管人工智能（AI）包括生成式AI在智能交通系统（ITS）中能有效生成高质量交通数据和优化方案，但这些技术在大规模复杂场景下通常需要大量训练时间和计算资源。为应对这一挑战，本文提出一种新颖高效的算法DynLS，用于求解最大权重独立集（MWIS）问题，该问题可建模多种ITS应用，如交通信号控制和车辆路径规划。由于MWIS问题是NP-hard，DynLS引入三项关键创新：首先，采用基于评分的自适应顶点扰动（SAVP）技术，加速稀疏图中的收敛；其次，设计区域定位机制（RLM），通过动态调整搜索空间帮助跳出局部最优；最后，提出新型可变邻域下降策略ComLS，结合顶点交换策略与奖励机制，引导搜索向高质量解靠近。实验结果表明，DynLS性能卓越，在360个测试实例上持续输出高质量解，1000秒内完成。相比五种领先算法，其在350个实例中取得最优解，超越第二名算法Cyclic-Fast达177次；同时，其收敛速度与Cyclic-Fast相当，凸显效率与实用性。本研究显著推进了启发式算法在MWIS问题上的进展，为AI优化智能交通系统提供有力支持。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。