广义针问题上随机局部搜索的运行时间
内容提要
本文研究了基于幂律分布的遗传算法在优化跳函数方面的应用，分析了NSGA-II算法在适当人口规模下的效率，特别是在解决OneMinMax和OneJumpZeroJump问题时的评估复杂度。此外，探讨了多核学习的Rademacher复杂度、KRR和KKMC的核函数评估下限，以及基于数据复杂度的新学习算法的误差界限，提出了高维跳跃函数的优化算法和自适应进化算法的运行时间分析。
延伸解读
NSGA-II 在双目标问题上的评估复杂度
文章指出，适当种群规模的 NSGA-II 在 OneMinMax 问题上需要 O(Nn log n) 次函数评估，在 OneJumpZeroJump 问题上需要 O(Nn^k) 次评估。这些界限与已知上界一致，并表明即使考虑并行运行时间，NSGA-II 在较大种群规模下也不会获益。这为理解该算法在双目标优化中的效率提供了理论依据。
多核学习的泛化风险与收敛速度
针对不同特征映射的多核学习，文章推导了局部 Rademacher 复杂度的上界，给出了比全局方法更紧致的超限风险边界，并覆盖 1≤p≤∞ 的所有情况。同时获得了 O(n^{-α/(1+α)}) 的快速收敛速度，其中 α 是个体内核的最小特征值衰减率。这为多核学习的理论保证提供了更精细的工具。
核方法中核函数评估的严格下限
文章提出了 Kernel Ridge Regression (KRR) 和 Kernel K-means 聚类 (KKMC) 中所需核函数评估数量的严格下限。通过有效的统计维度，KRR 的结果解决了一个关于采样复杂度的开放性问题。对于输入数据为高斯混合模型的情况，文章还提供了一种超越上述下限的 KKMC 算法，展示了在特定分布下降低计算成本的可能性。
高维跳跃函数与自适应进化算法的进展
文章提出了一种基于紧凑遗传算法 (cGA) 的高维跳跃函数优化算法，该算法能快速搜索最优解，并可在无额外耗费的情况下穿越低适应度的中等大小山谷。同时，自适应版本的 (1,λ) 进化算法通过严格的运行时间分析表明，其能在飞行中找到复杂的最优参数设置，甚至可替代先前提出的复杂自适应变异率调整方案。
Q&A
基于幂律分布的遗传算法有什么优势？
该算法能够快速且实例独立地优化跳函数，接近最优解。
NSGA-II算法在解决OneMinMax问题时的效率如何？
在适当人口规模下，NSGA-II算法需要O(Nnlogn)的函数评估来查找Pareto前沿。
多核学习的Rademacher复杂度有什么特点？
它提供了比全局方法更紧致的超限风险边界，并推导出快速收敛速度。
新学习算法的误差界限适用于哪些情况？
该误差界限适用于小样本误差函数子集，并应用于分类和预测问题。
高维跳跃函数的优化算法有什么创新？
提出了一种基于紧凑遗传算法的新型优化算法，具有较快的运行速度。
自适应版本的(1,λ)进化算法的有效性如何？
该算法能够在飞行中找到复杂的最优参数设置，且运行时间分析表明其有效性。
