How the Move Acceptance Hyper-Heuristic Copes With Local Optima: Drastic Differences Between Jumps and Cliffs
Benjamin Doerr, Arthur Dremaux, Johannes F. Lutzeyer, A. Stumpf · Proceedings of the Genetic and Evolutionary Computation Conference · 2023
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. With its O (n3) runtime, for almost all cliff widths d, the MAHH massively outperforms the Θ(nd) runtime of simple elitist evolutionary algorithms (EAs). For the most prominent multimodal benchmark, the jump functions, the given runtime estimates of O(n2mm-Θ(m)) and Ω(2Ω(m)), for gap size m ≥ 2, are far apart and the real performance of MAHH is still an open question.