用马尔可夫选择与仅接受恶化操作，大幅加速超启发式算法跳出局部最优。
Speeding Up Hyper-Heuristics With Markov-Chain Operator Selection and the Only-Worsening Acceptance Operator
- 用二状态马尔可夫链替代随机选择移动接受策略。
- 在跳跃函数上运行时间从Ω(n²ᵐ⁻¹)降至O(nᵐ⁺¹)，在悬崖函数上达O(n³ log n)。
- 反直觉地仅接受恶化操作反而更高效，适合优化复杂多峰问题。
最近研究显示，移动-接受型超启发式算法能以惊人效率跳出局部最优（Lissovoi等，人工智能，2023）。本文提出两项改进：(i) 采用简单的两状态马尔可夫链来决定在仅改进与任意移动接受算子间的选择，使跳跃函数（Jumpₘ）的运行时间从Ω(n²ᵐ⁻¹)降至O(nᵐ⁺¹)；(ii) 将所有移动接受算子替换为仅接受恶化状态的操作，该反直觉设计此前未被使用。理论证明表明，该仅恶化接受算子显著提升跳出局部最优的能力，例如在跳跃函数上运行时间为O(n³ log n)，与间隙大小无关。总体上，我们证明了该马尔可夫移动接受超启发式在新基准类SEQOPTₖ上的运行时间为O(nᵏ⁺¹ log n)，该类包含具有k个连续局部最优的大量函数，且包含广泛研究的跳变函数（Jumpₘ）和悬崖函数（Cliff_d）当k=2时的情形。
原文摘要 · Abstract (English)
The move-acceptance hyper-heuristic was recently shown to be able to leave local optima with astonishing efficiency (Lissovoi et al., Artificial Intelligence (2023)). In this work, we propose two modifications to this algorithm that demonstrate impressive performances on a large class of benchmarks including the classic Cliff$_d$ and Jump$_m$ function classes. (i) Instead of randomly choosing between the only-improving and any-move acceptance operator, we take this choice via a simple two-state Markov chain. This modification alone reduces the runtime on Jump$_m$ functions with gap parameter $m$ from $Ω(n^{2m-1})$ to $O(n^{m+1})$. (ii) We then replace the all-moves acceptance operator with the operator that only accepts worsenings. Such a, counter-intuitive, operator has not been used before in the literature. However, our proofs show that our only-worsening operator can greatly help in leaving local optima, reducing, e.g., the runtime on Jump functions to $O(n^3 \log n)$ independent of the gap size. In general, we prove a remarkably good runtime of $O(n^{k+1} \log n)$ for our Markov move-acceptance hyper-heuristic on all members of a new benchmark class SEQOPT$_k$, which contains a large number of functions having $k$ successive local optima, and which contains the commonly studied Jump$_m$ and Cliff$_d$ functions for $k=2$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。