Jan, 2018

离散黑盒优化启发式的复杂性理论

PDF
TL;DR研究演化算法的理论，尤其是随机黑盒优化技术理论中占主导地位的一个话题是运行时间分析，它旨在通过限制启发式算法在给定问题上需要的函数评估次数来理解其性能，并通过复杂性理论来研究算法解决问题的极限。该论文从黑盒优化的角度回顾了文献中提出的不同的黑盒复杂性模型，并对这些模型的界限进行了调查，探讨了运行时间分析和黑盒复杂性的相互作用如何启发演化计算中已经研究的问题的新算法解决方案，并讨论了未来工作的若干有趣的开放性问题。
发现论文，激发创造
  • 引入精英黑盒模型：精英选择何时会削弱进化算法性能？

    本文提出了一种新的黑盒优化模型 —— 精英黑盒模型，该模型要求算法的所有决策只基于到目前为止采样的固定数量的最佳搜索点，通过实例测试证明，精英黑盒复杂度可以比以前所有黑盒模型的相应复杂度更接近典型进化算法的运行时间，并引入了 $p$-Monte Carlo 黑盒复杂度的概念。

    Aug, 2015

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

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

    Jul, 2018

  • 被限制的重要性：处理微分进化等问题中的不可行解

    通过理论分析和实验验证，论文提出必须在启发式优化算法中明确规定如何处理超出范围解的策略，这个问题对于 Differential Evolution 等算法的表现，扰动性和种群多样性有显著的影响，尤其是在高维问题中。建议该领域正式采纳这一算法部件的概念，并在算法描述中规定，以保证结果可复制和更深入地了解其整体影响，以此自动化算法设计。

    Mar, 2022

  • 基于复杂理论的正确算法选择

    本论文旨在寻找用于黑盒优化的最佳算法，研究表明 Metropolis 算法在求解 DLB 问题时表现最佳，并且比所有其他算法都要快。

    Sep, 2021

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

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

    Jul, 2014

  • 进化优化和贝叶斯优化中的模型不确定性：一项比较分析

    这篇论文介绍了黑盒优化问题以及贝叶斯优化和替代辅助进化算法两种优化技术的使用方法和差异，还介绍了一种新的基于模型辅助的策略，通过利用未评估的解产生后代，并结合进化算法的群体搜索能力来提高模型辅助优化的效果。实验结果表明，该方法在准确性和效率方面优于主流的贝叶斯优化算法。

    Mar, 2024

  • 通用黑盒优化

    本文介绍了 Shiwa 算法，它可用于离散和连续、有噪音和无噪音、单项和并行、黑盒优化。通过在 YABBOB 和几个变体上进行实验比较，并在几个实际测试平台上验证了该算法。

    Apr, 2020

  • 协同进化和赌博学习算法的浓度尾部限制分析

    本文研究了随机算法（如演化算法和贝叶斯算法）的运行时间以及寻找问题解决方案之前所需的迭代次数，并提供了一个新的漂移定理，给出了在正、弱、零甚至负漂移情况下的精确指数尾界，用于证明 AI 算法的运行时间高度集中在最优解上，同时指出了 RLS-PD 算法在一些情况下存在遗忘性和高度集中的问题，需要进一步改进。

    May, 2024

  • 组合黑盒优化与专家建议

    通过使用多线性多项式和指数权重更新，我们提出了一种基于模拟退火的计算有效模型学习算法，以优化布尔双立方体上的黑盒函数优化问题，并获得了比文献中现有算法快几个数量级的计算时间和具有竞争性的性能。

    Jun, 2020

  • 面向生物序列设计的基于种群的黑盒优化

    该研究论文研究了如何通过黑盒优化算法设计新的生物序列，提出了一种名为 P3BO 的人口基础的黑盒优化算法，并结合进化优化算法在线调整超参数，实验证明 P3BO 可以提供更高质量、多样化的序列，是将机器学习应用于实际序列设计的重要步骤。

    Jun, 2020