Jul, 2018

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

PDF
TL;DR本文通过提出多个变量漂移定理，证明了使用一种新的 (1+1)- 型算法以及具有适应性变异强度的做法来解决 OneMax 问题所需的运行时间为 n ln (n) - cn ± o (n)，并在固定预算视角下找到相对于已有算法最优解约高 13%。
evolutionary algorithmsprecise runtime analysiscomplexity theoryonemax function class(1+1)-type algorithm
发现论文，激发创造
  • 自适应变异率的运行时分析

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

    Nov, 2018

  • 基于复杂理论的正确算法选择

    本论文旨在寻找用于黑盒优化的最佳算法，研究表明 Metropolis 算法在求解 DLB 问题时表现最佳，并且比所有其他算法都要快。

    Sep, 2021

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

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

    Apr, 2024

  • 引入精英黑盒模型：精英选择何时会削弱进化算法性能？

    本文提出了一种新的黑盒优化模型 —— 精英黑盒模型，该模型要求算法的所有决策只基于到目前为止采样的固定数量的最佳搜索点，通过实例测试证明，精英黑盒复杂度可以比以前所有黑盒模型的相应复杂度更接近典型进化算法的运行时间，并引入了 $p$-Monte Carlo 黑盒复杂度的概念。

    Aug, 2015

  • 离散黑盒优化启发式的复杂性理论

    研究演化算法的理论，尤其是随机黑盒优化技术理论中占主导地位的一个话题是运行时间分析，它旨在通过限制启发式算法在给定问题上需要的函数评估次数来理解其性能，并通过复杂性理论来研究算法解决问题的极限。该论文从黑盒优化的角度回顾了文献中提出的不同的黑盒复杂性模型，并对这些模型的界限进行了调查，探讨了运行时间分析和黑盒复杂性的相互作用如何启发演化计算中已经研究的问题的新算法解决方案，并讨论了未来工作的若干有趣的开放性问题。

    Jan, 2018

  • 通过更高元操作实现更快的黑盒算法

    本文研究了高级别变异算子在无偏黑箱模型上的应用，特别地，通过研究二进制算子对 leading-ones 和 onemax 的影响，发现 unary 黑箱模型的时间复杂度从 Ω（nlogn）降至 O（nlogn），而 binary 模型的时间复杂度下降到了 O（n）。同时针对 k-ary 操作，本文还发现了时间复杂度能进一步减小至 O（n /log k）.

    Dec, 2010

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

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

    Mar, 2019

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

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

    Feb, 2023

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

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

    Apr, 2017

  • 跳函数上一个重尾 $(1+(λ,λ))$ 遗传算法的运行时分析

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

    Jun, 2020