Mar, 2024

广义针问题上随机局部搜索的运行时间

PDF
TL;DRC. Doerr and Krejca's research explores the influence of needle radius on the runtime of the randomized local search heuristic for generalized Needle functions, providing upper and lower bounds as well as an exact description and asymptotic estimates of the expected runtime.
发现论文，激发创造
  • 跳函数上一个重尾 $(1+(λ,λ))$ 遗传算法的运行时分析

    基于幂律分布的遗传算法可以非常快速且实例独立地优化跳函数，并且比先前使用固定参数的算法更接近于最优解。

    Jun, 2020

  • 从理解 NSGA-II 的种群动力学到首个已证明的下界

    通过第一次对 NSGA-II 人口动态的数学理解，我们证明了适当的人口规模的 NSGA-II 需要 O（Nnlogn）函数评估来查找 OneMinMax 问题的 Pareto 前沿，并且需要 O（Nn^k）个评估来解决带跳跃大小为 k 的 OneJumpZeroJump 问题，这些界限与以前显示的上界相一致，并且表明即使在并行运行时间（迭代次数）方面，NSGA-II 在较大的种群大小上也不会获益。

    Sep, 2022

  • Lp 范数多核学习的本地 Rademacher 复杂度

    本文针对不同特征映射的多核学习，推导出其本地 Rademacher 复杂度的上限，提供了比全局方法更紧致的超限风险边界，并在 1<=p<= 无穷的所有情况下进行了分析。作者还通过推导获得了 O (n^-alpha/(1+alpha)) 的快速收敛速度，其中 alpha 是个体内核的最小特征值衰减率。

    Mar, 2011

  • 核岭回归和核 $k$- 均值聚类的严格核查询复杂度

    在本研究中，我们提出了 Kernel Ridge Regression (KRR) 和 Kernel K-means 聚类 (KKMC) 中所需的核函数评估数量的严格下限，并且通过有效的统计维度，我们的 KRR 结果解决了一个关于采样复杂度的开放性问题。此外，对于输入数据为高斯混合模型的情况，我们提供了一种超越了上述下限的 KKMC 算法。

    May, 2019

  • 局部 Rademacher 复杂度

    本文提出了基于数据依赖性复杂度概念的学习算法误差的新界限，利用局部和经验版本的 Rademacher 平均值对估计进行优化，适用于具有小样本误差函数子集的情况，并应用于凸函数类和核函数类的分类和预测问题。

    Aug, 2005

  • 傅里叶分析与运行时分析相遇：高原上的精确运行时间

    本文提出一种基于离散傅里叶分析的新方法，用于分析演化算法在高原上花费的时间，从而在 LeadingOnes 问题上演示了预计运行时间的紧凑证明，并确定了在不同突变率下的最佳突变率。

    Feb, 2023

  • cGA 在跳跃函数上的严格运行时分析 —— 无额外成本的 EDA 也能跨越适应度山谷

    该研究针对超过一定规模的高维跳跃函数，证明了一种新型的基于紧凑遗传算法（compact genetic algorithm，cGA）的最优解搜索算法具有较快的运行速度，且此算法可在无额外耗费的情况下穿越低适应度的中等大小的山谷。同时提供了平行运行的简单的通用方法，使基于分布式的进化算法能够近似最优化。

    Mar, 2019

  • 随机可满足 3-CNF 公式上 $(1+(λ,λ))$ 遗传算法的运行时分析

    本研究对于遗传算法在随机 3-SAT 问题上的运行时间进行了严格的分析，并针对较弱的适应性 - 距离相似性提出了解决方案。研究结果表明，引入一个上限可以避免种群大小过大而导致的问题，并证明了该算法可以有效地解决组合搜索和优化问题。

    Apr, 2017

  • 钉子张量模型的景观

    本研究考虑估计具有高秩的张量，提出了似然度最大化估计的方法并分析了优化算法的失败原因。

    Nov, 2017

  • 自适应变异率的运行时分析

    本文提出了一个自适应版本的 (1,λ) 进化算法，并进行了严格的运行时间分析。结果表明，进化计算中的自适应可以在飞行中找到复杂的最优参数设置。同时，它证明了 Doerr、Gie?en、Witt 和 Yang~(GECCO~2017) 提出的相对复杂的自适应性变异率调整方案可以用我们简单的内生性方案代替。

    Nov, 2018