Este artículo propone dos algoritmos modificados que mejoran el algoritmo hiperheurístico de aceptación de movimientos existente y demuestran un rendimiento mejorado en varias funciones de referencia. La primera modificación introduce una cadena de Markov simple de dos estados para la selección de operadores de solo mejora y de aceptación de cualquier movimiento, lo que reduce el tiempo de ejecución de la función Jump$_m$ de $\Omega(n^{2m-1})$ a $O(n^{m+1})$. La segunda modificación reemplaza el operador de aceptación de cualquier movimiento con un operador que solo permite el deterioro, lo cual, aunque contraintuitivo, reduce el tiempo de ejecución de la función Jump a $O(n^3 \log n)$ independientemente del tamaño del gap. Demostramos que el algoritmo propuesto garantiza un tiempo de ejecución de $O(n^{k+1} \log n)$ para la clase de referencia SEQOPT$_k$ (la clase de funciones con múltiples óptimos locales consecutivos). La clase SEQOPT$_k$ incluye las funciones Jump$_m$ y Cliff$_d$.
