Apr, 2017

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

PDF
TL;DR本研究对于遗传算法在随机 3-SAT 问题上的运行时间进行了严格的分析，并针对较弱的适应性 - 距离相似性提出了解决方案。研究结果表明，引入一个上限可以避免种群大小过大而导致的问题，并证明了该算法可以有效地解决组合搜索和优化问题。
发现论文，激发创造
  • 跳函数上一个重尾 $(1+(λ,λ))$ 遗传算法的运行时分析

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

    Jun, 2020

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

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

    Nov, 2018

  • 较大的后代种群有助于 $(1 + (λ, λ))$ 遗传算法克服噪声

    研究一种遗传算法对于评估函数中噪声的鲁棒性，特别地，较大的后代人口规模通常会带来更强的鲁棒性。实验结果表明，该算法比其他算法更具有鲁棒性。

    May, 2023

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

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

    Apr, 2024

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

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

    Mar, 2019

  • $(1+(λ,λ))$ 全局 SEMO 算法

    本研究设计了一种遗传算法以及动态参数设置，针对多目标优化问题达到更快的运行时，并在算法证明过程中对其在运行时方面进行了验证。

    Oct, 2022

  • 自适应变异率 (1+$λ$) 进化算法

    介绍了一种自适应算法来动态调节种群进化算法的变异率；研究表明这种机制可以更快地优化 OneMax 测试函数，提高了优化效果。

    Apr, 2017

  • 基于交叉算法的快速变异

    本文研究了基于基因重组和变异的遗传算法的运行时间。研究表明，使用重尾变异率可以达到线性运行时间，并且具有与自适应版本相当的运行时间。

    Apr, 2020

  • 非支配排序遗传算法 III（NSGA-III）的数学运行时分析

    本文提供了 NSGA-III 的第一次数学运行时间分析，证明该算法对于 3 目标问题能够计算完整的 Pareto 前沿，远远优于 NSGA-II。

    Nov, 2022

  • 快速遗传算法

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

    Mar, 2017