Algoritmo hill climbing

Si el cambio produce una mejor solución, otro cambio incremental se le realiza a la nueva solución, repitiendo este proceso hasta que no se puedan encontrar mejoras.

Suele llamarse a esta búsqueda algoritmo voraz local, porque toma un estado vecino "bueno" sin pensar en la próxima acción.

El Algoritmo Hill climbing es interesante para encontrar un óptimo local (una solución que no puede ser mejorada considerando una configuración de la vecindad) pero no garantiza encontrar la mejor solución posible (el óptimo global) de todas las posibles soluciones (el espacio de búsqueda).

La característica de que sólo el óptimo local puede ser garantizado puede ser remediada utilizando reinicios (búsqueda local repetida), o esquemas más complejos basados en iteraciones, como búsqueda local iterada, en memoria, como optimización de búsqueda reactiva y búsqueda tabú, o modificaciones estocásticas, como simulated annealing.

Es usado ampliamente en inteligencia artificial, para alcanzar un estado final desde un nodo de inicio.

Aunque algoritmos más avanzados tales como simulated annealing o búsqueda tabú pueden devolver mejores resultados, en algunas situaciones hill climbing opera sin diferencias.

El hill climbing con frecuencia puede producir un mejor resultado que otros algoritmos cuando la cantidad de tiempo disponible para realizar la búsqueda es limitada, por ejemplo en sistemas en tiempo real.

El algoritmo puede devolver una solución válida aún si es interrumpido en cualquier momento antes de que finalice.

Por ejemplo, el hill climbing puede ser aplicado al problema del viajante.

En el hill climbing simple, el primer nodo cercano es escogido, mientras que en hill climbing de ascenso pronunciado todos los sucesores son comparados y la solución más cercana es elegida.

Ambas formas fallan si no existe un nodo cercano, lo cual sucede si hay máximos locales en el espacio de búsqueda que no son soluciones.

El hill climbing de ascenso pronunciado es similar a la búsqueda en anchura, la cual intenta todas las posibles extensiones del camino actual en vez de sólo una.

Hill climbing estocástico no examina todos los vecinos antes de decidir cómo moverse.

Este realiza, iterativamente, el hill-climbing, cada vez con una condición inicial aleatoria

Hill climbing de reinicio aleatorio es un algoritmo sorprendentemente efectivo en muchos casos.

Las cordilleras son un reto para los algoritmos de hill climbing que optimizan en espacios continuos.

Si los lados de la cordillera(o el corredor) son muy pronunciados, entonces el algoritmo puede verse forzado a realizar pasos muy pequeños mientras zigzaguea hacia una mejor posición.

De esta forma, el método de descenso en la dirección del gradiente o método del gradiente conjugado es generalmente preferido sobre hill climbing cuando la función objetivo es diferenciable.

Los algoritmos de hill climbing, sin embargo, tienen la ventaja de no requerir que la función objetivo sea diferenciable, por lo que pueden ser preferidos cuando la función es compleja.

Otro problema que a veces ocurre con hill climbing es el de la meseta.

Una meseta se encuentra cuando el espacio de búsqueda es plano, o suficientemente plano de manera tal que el valor retornado por la función objetivo es indistinguible de los valores retornados por regiones cercanas debido a la precisión utilizada por la máquina para representar su valor.