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

Nov, 2018

Runtime Analysis for Self-adaptive Mutation Rates

Benjamin Doerr, Carsten Witt, Jing Yang

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

Abstract

We propose and analyze a self-adaptive version of the $(1,\lambda)$ evolutionary algorithm in which the current mutation rate is part of the individual and thus also subject to mutation. A rigorous runtime analysis

self-adaptive algorithm mutation rate evolutionary computation parameter settings runtime analysis

发现论文，激发创造

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

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

Apr, 2017

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

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

Apr, 2024

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

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

Jul, 2018

基于交叉算法的快速变异

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

Apr, 2020

快速遗传算法

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

Mar, 2017

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

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

Apr, 2017

自适应进化算法在多峰优化上的应用

该研究提出了一种名为停滞检测的机制，可用作现有进化算法的模块，通过在多模式优化和自适应机制的探索中对其进行实验以及在限制方面研究其模块的潜在影响，验证了该模块的性能。

Apr, 2020

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

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

Feb, 2023

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

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

Jun, 2020

在噪声存在的情况下多目标进化算法的运行分析

通过数学运行分析一个简单的多目标进化算法 (MOEA) 在评估函数噪声存在的情况下对模拟基准的第一次 Pareto 前沿的发现表明，MOEA 的稳健性源于其隐式多样性机制，该机制旨在使其能够计算涵盖整个 Pareto 前沿的人口。

May, 2023