Cet article propose deux algorithmes modifiés qui améliorent l'algorithme hyperheuristique d'acceptation de mouvement existant et démontrent des performances accrues sur diverses fonctions de référence. La première modification introduit une chaîne de Markov simple à deux états pour la sélection des opérateurs d'acceptation d'amélioration seule et d'acceptation de tout mouvement, réduisant le temps d'exécution de la fonction Jump$_m$ de $\Omega(n^{2m-1})$ à $O(n^{m+1})$. La seconde modification remplace l'opérateur d'acceptation de tout mouvement par un opérateur n'autorisant que la détérioration, ce qui, bien que contre-intuitif, réduit le temps d'exécution de la fonction Jump à $O(n^3 \log n)$ quelle que soit la taille de l'écart. Nous prouvons que l'algorithme proposé garantit un temps d'exécution de $O(n^{k+1} \log n)$ pour la classe de référence SEQOPT$_k$ (la classe des fonctions à multiples optima locaux consécutifs). La classe SEQOPT$_k$ inclut les fonctions Jump$_m$ et Cliff$_d$.
