权重受限最短路径问题增强方法:约束路径搜索与双目标搜索相遇
本文提出了在多目标最短路径问题中使用平衡二叉搜索树来维护非支配前沿集,以更高效地找到帕累托最优解的方法。实验表明,该方法在三、四、五个目标的问题中比现有技术快一个数量级。
Feb, 2022
该论文提出了一种使用分层规划展开的基于成本约束的随机最短路径问题(HC-SSP)的框架,通过分支和剪枝算法来迭代地分配成本预算,从而在真实时间和风险敏感的应用中找到一个可行解。
May, 2022
本文介绍了一个基于约束的随机规划问题,其中利用整数线性规划方法确保了确定性决策,同时为安全性关键的应用提供了约束违规概率的上界。同时还介绍了确定性策略和随机策略的随机舍入过程,并探讨了如何在考虑不同时间步的约束情况下进行 CC-SSP 的推广。
Feb, 2023
在加权有向图中解决最短路径问题时,考虑边权重计算时间以及与权重不确定性的关系可以提高性能。通过建立在加权有向图的通用框架上,引入了找到最紧适应最短路径(TASP)的问题,该路径在最优成本的上界上最紧缩,实现了对有界不确定性的最短路径问题的泛化,其中可以用计算成本代替边权重的不确定性。我们提出了一个完整的算法来解决 TASP,并对解决方案的质量进行了保证。实证评估支持这种方法的有效性。
Aug, 2023
利用规划和运筹学的新框架,解决了随机最短路径问题中冗余计算的问题,提出了一种有效的约束生成技术,应用到了新算法 CG-iLAO*,实验证明 CG-iLAO * 相较于 LRTDP 和 iLAO * 在解决问题时速度提高了 8 倍和 3 倍,并忽略了 iLAO * 的多达 57% 的动作。
Jan, 2024
本文研究了多智能体路径规划中的 Conflict-Based Search 算法,证明了权重 cost-to-go 和冲突启发式算法可以被用于低级规划器,旨在提高算法效率和解决冲突问题。此外,该文章进一步表明算法性能与高低级之间的权衡有关,对现有算法进行了优化。
May, 2022
本文提供了一种面向带权有向图的广义框架,可以计算(估算)多次边权重,并以不同准确性和运行时开销进行优化,从而提出了一个最短路径问题的广义形式。我们介绍了该问题的一个完整的任何时刻的解法算法,并在实验中证明了其有效性。
Aug, 2022
该论文探讨了针对约束优化问题,采用深度优先搜索算法以在前 n 个解中寻找最优或近似最优解,并提出了一种基于 MCTS 的新型启发式神经网络算法,结合编码约束优化问题和利用图神经网络聚合变量和约束信息的方法,实验结果表明该方法能够快速找到初始的 5 个可行解中与最优解间隔小于 17.63% 的解,并在应用于约束满足问题时,与最先进方法相比,搜索节点数减少不到 5%。
Dec, 2023
本文探讨了在 Search-Based Software Engineering (SBSE) 中,当清晰的利益相关者偏好给定时,是否应该优先使用加权搜索,结果表明,即使在存在明确偏好的情况下,权重也可能对搜索进程有害。具体来说,作者进行了大规模的实证研究,结果在通常搜索预算的情况下表明,帕累托搜索在绝大多数情况下,甚至达到 77%的情况下比其加权对应物有显着优势。
Feb, 2022
本研究使用 MaxSAT 问题中的 SPB 约束和子句权重技术,提出了一种新的局部搜索算法 SPB-MaxSAT,为 MaxSAT 局部搜索求解器的子句权重方法提供了新的视角和优秀的性能。
Jan, 2024