Mar, 2019

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

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

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

    Jun, 2020

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

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

    Sep, 2022

  • 快速遗传算法

    本文讨论了基于位串表示的遗传算法的变异率的选择问题，建议采用来自幂律分布的随机变异率，可以获得快速的优化结果并被称为快速遗传算法。

    Mar, 2017

  • NSGA-II 对一个多模态问题的首次运行时分析

    本文针对一个由两个多峰目标组成的基准问题，进行 NSGA-II 算法的第一次运行时间分析，结果表明，当种群大小 N 至少是 Pareto 前沿的 4 倍时，NSGA-II 能够在时间复杂度为 O（N n^k）的情况下，使用四种不同的选择父母方式和位操作变异来优化 OneJumpZeroJump 基准测试，其中跳跃大小为 2≤k≤n/ 4。使用快速变异时，最近提出的重尾变异算子使这一保证提高了 k^Ω（k）倍。总体上，本研究表明，NSGA-II 至少可以胜任 OneJumpZeroJump 问题的局部最优解，不输于全局 SEMO 算法。

    Apr, 2022

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

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

    Apr, 2017

  • NSGA-II 的运行时分析：从交叉算子中可证明的加速

    本文通过数学分析证实采用交叉操作时，NSGA-II 可以更快地优化 OneJumpZeroJump benchmark，并证明了这种交叉操作对单目标优化也有帮助，实验结果与证明相符。

    Aug, 2022

  • 逗号选择是否有助于克服局部最优解

    研究了非精英主义的进化算法在最基本的基准函数中的性能，证明了非精英主义算法在运行时间上不具备优势。这是对多模问题上非精英算法的第一个紧密性结果。

    Apr, 2020

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

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

    Nov, 2018

  • 精确黑盒分析下的最优参数选择

    本文通过提出多个变量漂移定理，证明了使用一种新的 (1+1)- 型算法以及具有适应性变异强度的做法来解决 OneMax 问题所需的运行时间为 n ln (n) - cn ± o (n)，并在固定预算视角下找到相对于已有算法最优解约高 13%。

    Jul, 2018

  • 适度数量的种群可证明具有强健的抗噪性

    基于数学运行时间分析，该研究表明在具有先前的比特噪声的情况下，(1+λ) 和 (1,λ) 进化算法都可以容忍恒定的噪声概率而不增加 OneMax 基准测试的渐近运行时间。

    Apr, 2024