Búsquedas Locales

- porque este planteamiento resulte demasiado artificial y lejano al problema porque no haya operadores de transición, o porque no sea natural asociar una función de coste a dichos estados,
- o porque no hay posibilidad de hallar una solución óptima debido a que el tamaño del espacio de búsqueda es demasiado grande, y en este caso nos conformamos con una solución que podamos considerar suficientemente buena.
- Si es relativamente asequible encontrar una solución inicial, aunque no sea demasiado buena, podemos cambiar nuestra tarea de buscar un camino entre estados a encontrar una mejora sucesiva en el espacio de soluciones.
- Si no es posible encontrar una solución inicial (aunque no sea suficientemente buena) podemos ver si, partiendo de una solución no válida, podemos ir construyendo una solución que sí lo sea.
- Una solución inicial, que en este caso será una solución completa, no un trozo inicial del camino y que, aunque la llamemos así, no tiene porqué ser una solución en su sentido estricto.
- Operadores de cambio de la solución, que en este caso manipularán soluciones completas y que no tendrán un coste asociado.
- Una función de calidad, que debe medir lo buena que es una solución y permitirá dirigir la búsqueda. A diferencia de las funciones heurísticas anteriores, en este caso esta función no indica cuánto falta para encontrar la solución que buscamos, sino que proporciona una forma de comparar la calidad entre soluciones para indicarnos cuál es la dirección que debemos tomar para encontrar soluciones mejores.
Subiendo la colina

- Ascenso de colinas simple: consiste en elegir siempre el primer operador que suponga una mejora respecto al nodo actual, de manera que no exploramos todas las posibilidades accesibles, ahorrándonos el explorar cierto número de descendientes. Presenta la ventaja de ser más rápido que explorar todas las opciones, pero la desventaja de que hay más probabilidad de no alcanzar las soluciones mejores. En cierta forma, sería el equivalente al algoritmo voraz para este tipo de casos pero con información limitada (ya que no explora todos los posibles sucesores).

- Ascenso de colinas por máxima pendiente (steepest ascent hill climbing): expande todos los posibles descendientes de un nodo y elige el que suponga la máxima mejora respecto al nodo actual. Este algoritmo supone que la mejor solución la encontraremos a través del sucesor que mayor diferencia tenga respecto a la solución actual, siguiendo una política avariciosa. La utilización de memoria para mantener la búsqueda es nula, ya que solo tenemos en cuenta el nodo mejor. Se pueden hacer versiones que guarden caminos alternativos que permitan una vuelta atrás en el caso de que consideremos que la solución a la que hemos llegado no es suficientemente buena, pero en este caso han de imponerse ciertas restricciones de memoria para no tener un coste en espacio demasiado elevado.
Algoritmo: Ascenso de colinas por máxima pendiente Actual ← Estado_inicial seguir? ← verdad mientras seguir? hacer Hijos ← generar_sucesores(Actual) Hijos ← ordenar_y_eliminar_peores(Hijos, Actual) si no vacio?(Hijos) entonces Actual ← Escoger_mejor(Hijos) si no seguir? ← falso fin fin

- Búsqueda por ascenso con reinicio aleatorio (random restarting hill climbing): para subsanar este problema se puede intentar la ejecución del algoritmo cierto número de veces desde distintos puntos escogidos aleatoriamente y quedarse solo con la mejor exploración. Por simple que parezca, muchas veces esta estrategia es más efectiva que otros métodos más complejos, y resulta muy barata de implementar. La única dificultad que podemos encontrar radica en la capacidad para poder generar los distintos puntos iniciales de búsqueda, ya que en ocasiones el problema no permite hallar soluciones iniciales con facilidad.

- Búsqueda en haces (beam search): Un problema con el que se encuentran este tipo de algoritmos son las zonas del espacio de búsqueda en las que la función heurística no es informativa, como por ejemplo las denominadas mesetas y las funciones en escalón, en las que los valores de los nodos vecinos al actual tienen valores iguales, y por lo tanto una elección local no nos permite decidir el camino a seguir. Para evitar estos problemas se debe extender la búsqueda más allá de los vecinos inmediatos para obtener información suficiente para encaminar la búsqueda, pero supone un coste adicional en cada iteración, prohibitivo cuando el factor de ramificación es excesivamente grande. Una alternativa es permitir que el algoritmo guarde parte de los nodos visitados para proseguir la búsqueda por ellos en caso de que el algoritmo se quede atascado en un óptimo local. El algoritmo más utilizado de este tipo es el denominado búsqueda en haces (beam search).
En este algoritmo se van guardando un número N de las mejores soluciones, expandiendo siempre la mejor de ellas. De esta manera no se sigue un solo camino sino N caminos eventualmente distintos. Las variantes que se pueden plantear están en cómo se escogen esas N soluciones que se mantienen. Si siempre se sustituyen las peores soluciones de las N por los mejores sucesores del nodo actual, caemos en el peligro de que todas acaben estando en el mismo camino, reduciendo la capacidad de volver hacia atrás, así que el poder mantener la variedad de las soluciones guardadas es importante. Está claro que cuantas más soluciones se guarden, más posibilidad habrá de encontrar una buena solución, pero se tiene un coste adicional tanto en memoria como en tiempo, ya que habrá que decidir con qué sucesores quedarse y qué soluciones guardadas se sacrifican.
Algoritmo: Búsqueda en Haces Actual ← Estado_inicial Soluciones_actuales.añadir(Estado_inicial) seguir? ← verdadero mientras seguir? hacer Hijos ← generar_sucesores(Actual) soluciones_actuales.actualizar_mejores(Hijos) si soluciones_actuales.algun_cambio?() entonces Actual ← soluciones_actuales.escoger_mejor() si no seguir? ← falso fin fin