算法运行时间预测:方法与评估
介绍了一种算法设计范例 —— 基于学习预测器的算法,将在线学习技术应用于预测器学习、调整鲁棒性 - 一致性折中并绑定样本复杂度,在构建优美的预测器的同时,在二分图匹配、滑雪租赁、页面迁移和作业调度等多场景中优化了多个现有结果,且提供了第一批基于学习理论的担保。
Feb, 2022
开发了一种利用机器学习稀疏回归技术猜测候选闭合形式函数并使用 SMT 求解器和计算机代数系统来验证是否是递归关系的解的新型通用方法,相比传统方法在给定时间内能够找到一类不能被现有分析系统或当前计算机代数系统解决的递归式的闭合解。
Aug, 2023
本文针对设计算法组合的问题,提出了并行考虑调度问题和机器学习问题的技术,并在布尔可满足性、01 整数规划和人工智能规划等领域取得了显著的实验性能提升,具有较强的理论保证。
Jun, 2012
本论文研究了使用随机局部搜索解决基于满足性问题的 SAT 问题的流行范式,以及通过学习逻辑蕴含来改善求解器性能,并提出了一种生成逻辑等价问题形式的方法,进一步深入研究学习逻辑蕴含如何影响 SLS 运行时间的问题。
Oct, 2022
本研究提出了一种可以估算算法性能预测模型泛化能力的方法,并通过在基准测试套件之间训练预测模型来测试该方法的可行性,结果表明,特征空间中的泛化模式确实反映在性能空间中。
May, 2023
布尔可满足性 (SAT) 是一个基础的 NP-complete 问题,具有许多应用,包括自动计划和调度。为了解决大规模的情况,SAT 求解器必须依赖启发式算法,如在 DPLL 和 CDCL 求解器中选择一个分支变量。我们建议使用机器学习模型来改进这些启发式算法,通过减少步数来降低运行时间,但是由于有用的模型相对较大和较慢,这通常会阻碍运行时间。我们建议首先使用训练好的机器学习模型进行几个初始步骤,然后将控制权交给经典启发式算法,这简化了 SAT 求解的冷启动,并可以减少步数和总运行时间,但需要单独决定何时将控制权交给求解器。此外,我们介绍了一种改进的 Graph-Q-SAT,专门针对从其他领域转换而来的 SAT 问题,例如开放式车间调度问题。我们通过随机和工业 SAT 问题验证了我们方法的可行性。
Jul, 2023
本文通过分析顺序版本算法的运行时行为,提出了一种评估给定算法并行性能的框架,并将此方法应用于研究两种 SAT 局部搜索求解器的并行性能,结果表明模型能够准确预测性能并展示了不同情况下局部搜索求解器的运行时分布。
Jan, 2024
本文使用统计和在线学习理论的概念来分析特定应用领域下的算法选择问题,并将算法选择建模为统计学习问题,同时研究了在线算法选择问题的可能性和不可能性结果。
Nov, 2015
本研究提出了一种应用于计算机视觉的结构化预测方法,在训练过程中综合加入了结构和特征计算的权衡,在测试时具有任意性,以达到提高最佳分类性能的目的。
Dec, 2013
用于计算程序资源使用情况的自动静态成本分析方法,基于回归关系解决递归方程求解问题,结合机器学习回归技术、SMT 求解器和计算代数系统,提出了一种新的、通用的方法来解决任意受限递归关系方程,证明在 CiaoPP 系统中能够胜过现有最先进成本分析工具和递归求解器,并解决不能被它们解决的递归方程。
May, 2024