Hyper-Heuristics Can Profit From Global Variation Operators

📄 arXiv: 2407.14237v1 📥 PDF

作者: Benjamin Doerr, Johannes F. Lutzeyer

分类: cs.NE, cs.AI, cs.DS

发布日期: 2024-07-19

备注: Continues and significantly extends work presented in the GECCO 2023 conference paper arXiv:2304.10414

💡 一句话要点

全局变异算子提升超启发式算法在多模态优化问题上的性能

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 超启发式算法 全局变异 多模态优化 JUMP函数 进化算法

📋 核心要点

  1. 现有研究表明，移动接受超启发式算法（MAHH）在特定问题（CLIFF）上表现出色，但在其他多模态问题上的性能未知。
  2. 本文提出将MAHH中的局部变异算子替换为全局变异算子，旨在提升其在更广泛的多模态优化问题上的性能。
  3. 实验结果表明，改进后的MAHH在JUMP函数上的性能显著提升，甚至优于简单的精英进化算法。

📝 摘要（中文）

本文研究了移动接受超启发式算法(MAHH)在多模态优化问题上的性能。先前工作表明，MAHH在CLIFF基准测试中能高效地脱离局部最优。然而，本文证明了这种优势仅限于CLIFF问题，在JUMP基准测试中并不成立。对于JUMP函数，MAHH的预期运行时间远慢于简单的精英进化算法(EAs)。令人鼓舞的是，将MAHH中的局部单比特变异算子替换为EA中常用的全局比特位变异算子，可以显著提高其在JUMP函数上的性能，甚至优于简单的精英EA。研究表明，MAHH通过接受次优解，以适度的步长穿过目标值较低的区域，从而获益。这是首次通过数学方法证明这种优化行为。总的来说，该研究表明，结合全局变异和接受次优解这两种应对局部最优的方法，可以带来显著的性能提升。

🔬 方法详解

问题定义：论文旨在研究移动接受超启发式算法(MAHH)在多模态优化问题上的性能，特别是其在不同类型的多模态问题上的泛化能力。现有研究表明MAHH在CLIFF问题上表现出色，但其在其他多模态问题（如JUMP函数）上的性能表现不佳，这限制了MAHH的适用范围。

核心思路：论文的核心思路是将MAHH中的局部单比特变异算子替换为全局比特位变异算子。这种替换的目的是使MAHH能够跳出局部最优，更有效地探索搜索空间，从而提高其在JUMP函数等问题上的性能。全局变异算子允许算法一次改变多个比特位，从而更容易跳过局部最优解的“障碍”。

技术框架：论文的技术框架主要包括以下几个步骤：1) 分析MAHH在JUMP函数上的性能瓶颈；2) 将MAHH中的局部变异算子替换为全局变异算子；3) 对改进后的MAHH在JUMP函数上进行理论分析和实验验证；4) 将改进后的MAHH与简单的精英进化算法(EAs)进行比较，评估其性能提升。

关键创新：论文的关键创新在于将全局变异算子引入到MAHH中，并证明了这种改进可以显著提高MAHH在JUMP函数上的性能。与传统的局部变异算子相比，全局变异算子能够更有效地探索搜索空间，避免陷入局部最优。此外，论文还首次通过数学方法证明了MAHH通过接受次优解来穿过目标值较低的区域的优化行为。

关键设计：论文的关键设计在于全局变异算子的选择和参数设置。全局变异算子通常采用比特位翻转的方式，每个比特位以一定的概率进行翻转。论文中可能需要根据JUMP函数的特性调整全局变异算子的翻转概率，以达到最佳的性能。此外，MAHH中的接受概率参数也可能需要进行调整，以平衡探索和利用之间的关系。

📊 实验亮点

实验结果表明，将MAHH中的局部变异算子替换为全局变异算子后，其在JUMP函数上的运行时间从Ω(n^(2m-1) / (2m-1)!)降低到min{1, O(e*ln(n)/m)^m} * O(n^m)。对于较大的m值，改进后的MAHH在渐近性能上优于简单的精英进化算法。这证明了全局变异算子能够显著提高MAHH在多模态优化问题上的性能。

🎯 应用场景

该研究成果可应用于解决各种具有多模态特性的优化问题，例如机器学习中的超参数优化、组合优化问题、以及工程设计中的参数优化等。通过结合全局变异和接受次优解的策略，可以更有效地搜索到全局最优解，提高优化效率和性能。未来的研究可以进一步探索不同类型的全局变异算子和接受准则，以适应更广泛的优化问题。

📄 摘要（原文）

In recent work, Lissovoi, Oliveto, and Warwicker (Artificial Intelligence (2023)) proved that the Move Acceptance Hyper-Heuristic (MAHH) leaves the local optimum of the multimodal CLIFF benchmark with remarkable efficiency. The $O(n^3)$ runtime of the MAHH, for almost all cliff widths $d\ge 2,$ is significantly better than the $Θ(n^d)$ runtime of simple elitist evolutionary algorithms (EAs) on CLIFF. In this work, we first show that this advantage is specific to the CLIFF problem and does not extend to the JUMP benchmark, the most prominent multi-modal benchmark in the theory of randomized search heuristics. We prove that for any choice of the MAHH selection parameter $p$, the expected runtime of the MAHH on a JUMP function with gap size $m = O(n^{1/2})$ is at least $Ω(n^{2m-1} / (2m-1)!)$. This is significantly slower than the $O(n^m)$ runtime of simple elitist EAs. Encouragingly, we also show that replacing the local one-bit mutation operator in the MAHH with the global bit-wise mutation operator, commonly used in EAs, yields a runtime of $\min{1, O(\frac{e\ln(n)}{m})^m} \, O(n^m)$ on JUMP functions. This is at least as good as the runtime of simple elitist EAs. For larger values of $m$, this result proves an asymptotic performance gain over simple EAs. As our proofs reveal, the MAHH profits from its ability to walk through the valley of lower objective values in moderate-size steps, always accepting inferior solutions. This is the first time that such an optimization behavior is proven via mathematical means. Generally, our result shows that combining two ways of coping with local optima, global mutation and accepting inferior solutions, can lead to considerable performance gains.