Jul, 2023

使用 GSEMO 在 OneMinMax 上进行多样性优化的严格运行时分析

PDF
TL;DR本论文研究了 GSEMO 算法在多目标优化中优化群体多样性的方法，阐述了该算法在解决 Pareto - 最优问题中的优势，并得到当问题规模为奇数时，预期时间内收敛到具有最优多样性的种群的证明，分析中涉及了种群的随机漫步等相关理论。
evolutionary diversity optimizationmulti-objective optimizationpareto-optimalgsemo algorithmrandom walk
发现论文，激发创造
  • 多目标问题（前导 1，尾随 0）的进化多样性优化的运行时分析

    本研究分析了进化多目标优化算法在多样性优化问题中的应用，并证明了一种算法能够在预期的迭代次数下计算出所有 Pareto 最优解。同时，还分析了该算法找到具有最佳多样性的种群所需的迭代次数，并通过实证研究验证了理论预测的准确性。

    Apr, 2024

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

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

    May, 2023

  • 多样性基于的父辈选择策略的设计与分析 —— 加速多目标进化优化

    本研究提出了一种基于多样性的度量方法来改进遗传算法中的亲本选择，研究发现其在解决多目标优化中表现良好，并探讨出现停滞的原因和对策。

    May, 2018

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

    本研究证明使用 NSGA-II 算法，结合两种经典的变异算子和四种不同的父母选择方式，当种群大小为前沿帕累托曲线大小的 4 倍时，可以满足与 SEMO 和 GSEMO 算法在基本的 OneMinMax 和 LeadingOnesTrailingZeros 基准测试中相同的渐近运行时保证，但如果种群大小仅等于前沿帕累托曲线的大小时，NSGA-II 算法无法高效地计算完整的帕累托前沿。

    Dec, 2021

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

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

    Oct, 2022

  • 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

  • 利用 MOEA/D 求解多目标最小权重基问题的严格运行时分析

    研究了多目标最小重量基问题的性质，并给出了 MOEA/D 算法的运行时间分析，表明在理论和实践方面都比已有的算法更优，可望在预期的多项式时间内找到所有的极值点。

    Jun, 2023

  • 多目标质量多样性优化

    本研究提出了一种新的多目标优化方法，将 MAP-Elites 算法中的多样性与多目标优化相结合，通过使用 Pareto Front 填充每个单元格，能够在描述符空间中提取多样性解，并在探索不同目标之间的折衷方案时提供全局性能优异的解决方案。

    Feb, 2022

  • 一个块坐标下降的多目标优化算法：理论和实证分析

    存在一种条件，使得块坐标下降在进化多目标优化中达到渐近效率，我们考虑了这个开放问题并提出了块坐标版本的 GSEMO 算法来与标准 GSEMO 算法的运行时间进行比较，理论和实证结果表明了块坐标下降更快的情况的存在，这一结果可能对此类算法产生更广泛的见解。

    Apr, 2024

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

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

    Sep, 2022