Jul, 2022

基于置换的进化算法的运行时分析

PDF
TL;DR该论文提出了一种将基于经典伪布尔基准问题的算法推广到排列基准问题上的方法，并对旋转置换的基准问题进行了分析，发现排列的循环结构决定了变异的难度，并提出使用更对称的 Scramble 变异操作器和重尾 Scramble 操作器来加速算法运行，并进行了实证分析。
evolutionary algorithmspermutation-based benchmarkscycle structurescramble mutationruntime analysis
发现论文，激发创造
  • 基于置换的进化算法强理论研究

    本研究提出了将经典的伪布尔基准转化为置换集基准的一般方法，分析了置换基础 $(1+1)$EA 在 LeadingOnes 和 Jump 基准的模拟上的运行时间，旨在研究置换问题。

    Apr, 2022

  • 快速遗传算法

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

    Mar, 2017

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

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

    Feb, 2023

  • 排列进化算子的调查与分析

    对组合优化问题的演化操作符与排列进行了调查和分析，使用了开源 Java 库 Chips-n-Salsa 实现并在人工适应度景观上进行了实证分析。

    Nov, 2023

  • 循环突变：通过循环归纳进化排列

    研究演化算法在排列问题和映射问题上的应用，提出了一种新的变异算子 “cycle mutation”，并且利用新的排列距离度量方法进行问题特征分析和应用实验，结果表明 cycle mutation 适用于映射和分配问题，对于旅行商问题有一定局限性，并且相对于常用替代方案对局部最优解的稳健性更好。

    May, 2022

  • 自然进化与人工进化运行时比较的初步步骤

    本文分析了强选择弱突变（SSWM）进化模型运行时间及其与（1 + 1）EA 的异同之处，并研究了如何利用适应度梯度实现 SSWM 在跨越适应度谷时的优势。

    Apr, 2015

  • 遗传算法和其他搜索过程的分层分析

    本论文描述了一种新的基于层级定理的技术，应用于任何非精英进程，并对几个伪布尔函数、排序问题和组合优化中的最优解逼近进行了演示。

    Jul, 2014

  • 置换问题的适应度景观分析：从距离度量到变异算子选择

    本文研究了适应性函数分析在排列优化问题上的理论与实践，着重探讨了距离度量问题及其分类方法，并利用主成分分析法对于度量方法进行分类，揭示出排列优化问题的分类规律及其子类型，利用其进行突变算子的选择和进化算法的优化。

    Aug, 2022

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

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

    Nov, 2018

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

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

    Apr, 2024