Algoritmo de Hill Climbing

El algoritmo de ascenso de colina (hill climbing) es un método de búsqueda local para problemas de optimización. Parte de una solución cualquiera y, de forma iterativa, se desplaza al vecino que más mejora la función objetivo; repite ese salto hasta que ningún vecino supera al estado actual, punto en el que se detiene.

Es un algoritmo voraz (greedy): en cada paso elige la mejor mejora inmediata sin planificar más allá. Y consume muy poca memoria, porque solo necesita recordar el estado actual y evaluar sus vecinos, sin guardar el camino recorrido ni una frontera de nodos. Russell y Norvig, en «Artificial Intelligence: A Modern Approach», lo presentan como el ejemplo canónico de búsqueda local.

Cómo funciona y por qué es eficiente

Imagina una función que asigna a cada solución una «altura», es decir, su calidad. El ascenso de colina se comporta como un excursionista que solo sabe mirar a sus pies: examina las soluciones vecinas, se mueve a la que más sube y vuelve a mirar. Cuando todos los vecinos están más abajo, entiende que ha llegado a una cima y para.

La versión clásica, el ascenso por la máxima pendiente (steepest-ascent), evalúa todos los vecinos y elige el mejor. Su atractivo es la simplicidad y el coste: no mantiene listas de nodos abiertos ni reconstruye rutas, así que escala bien a espacios enormes donde una búsqueda exhaustiva sería inviable. Por eso aparece en tareas como la colocación de componentes, el ajuste de parámetros o la planificación de rutas, donde basta con una solución suficientemente buena y rápida.

El problema: óptimos locales, mesetas y crestas

Su virtud es también su talón de Aquiles. Como nunca acepta un paso a peor, el algoritmo se queda atrapado en óptimos locales: cimas menores desde las que cualquier movimiento baja, aunque exista una montaña más alta al otro lado del valle. La analogía es escalar en la niebla subiendo siempre: puedes coronar un altozano y creer que es el techo del mundo.

Dos terrenos más lo frenan. Las mesetas (plateaus) son zonas planas donde todos los vecinos valen lo mismo y el algoritmo no sabe hacia dónde ir. Las crestas (ridges) son filos estrechos que ascienden en diagonal: como el método solo prueba movimientos alineados con los ejes, avanza a pequeños zigzags o se detiene, incapaz de seguir el filo.

Variantes: reinicio aleatorio, estocástico y el temple simulado

Para esquivar estas trampas existen variantes. El ascenso estocástico elige al azar entre los movimientos que mejoran, en lugar del mejor siempre; la versión primero-el-mejor (first-choice) genera vecinos al azar hasta dar con uno que mejore, útil cuando hay demasiados. Pero la técnica más eficaz por su sencillez es el reinicio aleatorio (random-restart): lanzar muchas búsquedas desde puntos de partida distintos y quedarse con la mejor cima encontrada.

Cuando ni así basta, se recurre al temple simulado (simulated annealing), que sí acepta a veces movimientos a peor —con una probabilidad que decrece con el tiempo— para escapar de los óptimos locales antes de asentarse. El ascenso de colina sigue siendo, pese a sus límites, la puerta de entrada para entender la búsqueda local y una herramienta práctica siempre que baste con una buena solución en poco tiempo.