$(1+(λ,λ))$ 全局 SEMO 算法
本文针对一个由两个多峰目标组成的基准问题,进行 NSGA-II 算法的第一次运行时间分析,结果表明,当种群大小 N 至少是 Pareto 前沿的 4 倍时,NSGA-II 能够在时间复杂度为 O(N n^k)的情况下,使用四种不同的选择父母方式和位操作变异来优化 OneJumpZeroJump 基准测试,其中跳跃大小为 2≤k≤n/ 4。使用快速变异时,最近提出的重尾变异算子使这一保证提高了 k^Ω(k)倍。总体上,本研究表明,NSGA-II 至少可以胜任 OneJumpZeroJump 问题的局部最优解,不输于全局 SEMO 算法。
Apr, 2022
本研究证明使用 NSGA-II 算法,结合两种经典的变异算子和四种不同的父母选择方式,当种群大小为前沿帕累托曲线大小的 4 倍时,可以满足与 SEMO 和 GSEMO 算法在基本的 OneMinMax 和 LeadingOnesTrailingZeros 基准测试中相同的渐近运行时保证,但如果种群大小仅等于前沿帕累托曲线的大小时,NSGA-II 算法无法高效地计算完整的帕累托前沿。
Dec, 2021
本论文研究了 GSEMO 算法在多目标优化中优化群体多样性的方法,阐述了该算法在解决 Pareto - 最优问题中的优势,并得到当问题规模为奇数时,预期时间内收敛到具有最优多样性的种群的证明,分析中涉及了种群的随机漫步等相关理论。
Jul, 2023
通过数学运行分析一个简单的多目标进化算法 (MOEA) 在评估函数噪声存在的情况下对模拟基准的第一次 Pareto 前沿的发现表明,MOEA 的稳健性源于其隐式多样性机制,该机制旨在使其能够计算涵盖整个 Pareto 前沿的人口。
May, 2023
本研究对于遗传算法在随机 3-SAT 问题上的运行时间进行了严格的分析,并针对较弱的适应性 - 距离相似性提出了解决方案。研究结果表明,引入一个上限可以避免种群大小过大而导致的问题,并证明了该算法可以有效地解决组合搜索和优化问题。
Apr, 2017
本文提出了一个自适应版本的 (1,λ) 进化算法,并进行了严格的运行时间分析。结果表明,进化计算中的自适应可以在飞行中找到复杂的最优参数设置。同时,它证明了 Doerr、Gie?en、Witt 和 Yang~(GECCO~2017) 提出的相对复杂的自适应性变异率调整方案可以用我们简单的内生性方案代替。
Nov, 2018
存在一种条件,使得块坐标下降在进化多目标优化中达到渐近效率,我们考虑了这个开放问题并提出了块坐标版本的 GSEMO 算法来与标准 GSEMO 算法的运行时间进行比较,理论和实证结果表明了块坐标下降更快的情况的存在,这一结果可能对此类算法产生更广泛的见解。
Apr, 2024
研究一种遗传算法对于评估函数中噪声的鲁棒性,特别地,较大的后代人口规模通常会带来更强的鲁棒性。实验结果表明,该算法比其他算法更具有鲁棒性。
May, 2023