基于复杂理论的正确算法选择
本文通过提出多个变量漂移定理,证明了使用一种新的 (1+1)- 型算法以及具有适应性变异强度的做法来解决 OneMax 问题所需的运行时间为 n ln (n) - cn ± o (n),并在固定预算视角下找到相对于已有算法最优解约高 13%。
Jul, 2018
我们引入了一个名为欺骗性领先块(DLB)的新基准问题,通过它来严格研究单变量边际分布算法(UMDA)在存在遗传上下文和欺骗的情况下的运行时间。我们展示了简单的进化算法(EA)优于 UMDA,除非选择压力 $\mu/\lambda$ 极高,其中 $\mu$ 和 $\lambda$ 分别为父代和子代种群大小,并说明 UMDA 在父代种群大小为 $\mu=Ω(\log n)$ 的情况下,预期将具有 $e^{Ω(\mu)}$ 的 DLB 问题运行时间,假设选择压力 $\frac {\mu}{\lambda} \geq \frac {14}{1000}$,而非精英 $(\mu,\lambda)~\text {EA}$ 的预期运行时间为 $\mathcal {O}(n\lambda\log \lambda+n^3)$ 且 $\mu/\lambda\leq 1/e$。这些结果说明了单变量 EDA 在面对现实世界问题中的欺骗和遗传上下文的固有限制。相比之下,实证证据揭示了双变量 MIMIC 算法在 DLB 问题上的效率。我们的结果表明,当优化问题具有一定程度的遗传上下文和欺骗性时,应考虑具有更复杂概率模型的 EDA。
Jul, 2019
本文提出了一种新的黑盒优化模型 —— 精英黑盒模型,该模型要求算法的所有决策只基于到目前为止采样的固定数量的最佳搜索点,通过实例测试证明,精英黑盒复杂度可以比以前所有黑盒模型的相应复杂度更接近典型进化算法的运行时间,并引入了 $p$-Monte Carlo 黑盒复杂度的概念。
Aug, 2015
本研究中,我们提出了一种新的局部贝叶斯优化算法 MinUCB,通过在 GIBO 中将梯度下降步骤替换为最小化 UCB 的策略来改进了梯度下降方法,证明了在应用高斯过程作为替代物时,后者可以比直接梯度下降更好。此外,我们还通过前瞻策略改进了 MinUCB 的取样函数,得到了更高效的算法 LA-MinUCB,并在不同的合成和现实函数中应用我们的算法,结果表明了我们方法的有效性。我们的算法还从上界的角度改进了贝叶斯优化中的局部搜索策略,并为未来算法设计提供了新的方向。
May, 2024
研究演化算法的理论,尤其是随机黑盒优化技术理论中占主导地位的一个话题是运行时间分析,它旨在通过限制启发式算法在给定问题上需要的函数评估次数来理解其性能,并通过复杂性理论来研究算法解决问题的极限。该论文从黑盒优化的角度回顾了文献中提出的不同的黑盒复杂性模型,并对这些模型的界限进行了调查,探讨了运行时间分析和黑盒复杂性的相互作用如何启发演化计算中已经研究的问题的新算法解决方案,并讨论了未来工作的若干有趣的开放性问题。
Jan, 2018
本文提出了一种名为 TuRBO 的算法来解决高维问题的全局优化,该算法利用一系列局部模型,通过隐式赌博方法对这些模型之间的样本进行原则性的全局分配,并在强化学习、机器人学和自然科学领域的问题上显著优于其他现有方法。
Oct, 2019
本文探讨了应用特定硬件、量子和量子灵感求解器对组合优化问题 QUBO 变形进行优化是否比应用经典进化算法在其自然表示中求解同一问题更快,并证实了 Fujitsu Digital Annealer 在旅行商、二次分配和多维背包问题实例上比遗传算法表现更优。
May, 2022
该研究论文研究了如何通过黑盒优化算法设计新的生物序列,提出了一种名为 P3BO 的人口基础的黑盒优化算法,并结合进化优化算法在线调整超参数,实验证明 P3BO 可以提供更高质量、多样化的序列,是将机器学习应用于实际序列设计的重要步骤。
Jun, 2020
通过使用多线性多项式和指数权重更新,我们提出了一种基于模拟退火的计算有效模型学习算法,以优化布尔双立方体上的黑盒函数优化问题,并获得了比文献中现有算法快几个数量级的计算时间和具有竞争性的性能。
Jun, 2020
基于数学运行时间分析,该研究表明在具有先前的比特噪声的情况下,(1+λ) 和 (1,λ) 进化算法都可以容忍恒定的噪声概率而不增加 OneMax 基准测试的渐近运行时间。
Apr, 2024