ALGORITMOS DE BÚSQUEDA LOCAL Y PROBLEMAS DE OPTIMIZACIÓN

INTRODUCCIÓN

En capítulos anteriores hemos estudiado diferentes algoritmos de búsquedas, los cuales han sido diseñados para explorar de manera sistemática los espacios de búsqueda, manteniendo en memoria uno o más caminos registrando los puntos que hayan sido explorados con anterioridad. Estos tipos de búsquedas son usados cuando importa el camino al objetivo.

Sin embargo en ocasiones se presentan problemas en los que saber el camino hacia el objetivo es irrelevante, lo único importante es la configuración o estado final. Esta clase de problemas incluyen muchas aplicaciones importantes como diseño de circuitos integrados, disposición del suelo de una fábrica, programación del trabajo en tiendas, programación automática, optimización de redes de telecomunicaciones.

MARCO TEÓRICO

ALGORITMOS DE BÚSQUEDA LOCAL

Funcionan con un solo estado actual, además tienen dos ventajas claves: Usan muy poca memoria (por lo general una cantidad constante); y pueden encontrar a menudo soluciones razonables en espacios de estados grandes o infinitos (continuos) para los cuales son inadecuados los algoritmos sistemáticos.

Además de encontrar los objetivos, los algoritmos de búsqueda local son útiles para resolver problemas de optimización puros, en los cuales el objetivo es encontrar el mejor estado según una función objetivo.

BÚSQUEDA DE ASCENSIÓN DE COLINAS

La ascensión de colinas es un bucle que se mueve continuamente en dirección al valor creciente, es decir, hacia arriba. El bucle termina cuando se alcanza un pico, es decir, ningún nodo vecino tiene un valor más alto. La ascensión de colinas no mira delante más allá de los vecinos inmediatos del estado actual.

A veces a la ascensión de colinas se le llama búsqueda local voraz porque toma un estado vecino bueno sin pensar hacia dónde ir después. Sin embargo tiene algunas desventajas, y es que tiene 3 principales motivos por los cuales la búsqueda se atasca o finaliza, sin haber encontrado la solución.

El éxito de la ascensión de colinas depende muchísimo de la forma del paisaje del espacio de estados: si hay pocos máximos locales y mesetas, la ascensión de colinas con reinicio aleatorio encontrará una solución buena muy rápidamente.

BÚSQUEDA DE TEMPLE SIMULADO

En el algoritmo anterior nunca se hace movimientos hacia abajo, por lo que se estanca al encontrar un máximo local, por tanto se ha desarrollado una especie de algoritmo combinado que en un principio comienza por buscar un punto alto y luego se reduce gradualmente la intensidad.

El temple simulado es bastante similar a la ascensión de colinas. Sin embargo, escoge un movimiento aleatorio. Si este movimiento mejora la situación, es siempre aceptado. Por otra parte, el algoritmo acepta el movimiento con una probabilidad menor que uno.

BÚSQUEDA POR HAZ LOCAL

Esta búsqueda hace una exageración en cuanto a no usar mucha memoria ya que solo guarda un nodo en memoria. El algoritmo guarda la pista de k estados (no sólo uno). Comienza con estados generados aleatoriamente. En cada paso, se generan todos los sucesores de los k estados. Si alguno es un objetivo, paramos el algoritmo. Por otra parte, se seleccionan los k mejores sucesores de la lista completa y repetimos.

CONCLUSION

Estos tipos de algoritmos tratan de encontrar una de las mejores opciones al problema presentado, sea maximizando o minimizando ganancias o costes respectivamente.

Ademas, algunos de estos algortimos utilizan estados generados aleatoriamente conm la finalidad de observar el comportamiento que tendra.

BIBLIOGRAFÍA

Pérez, A. s.f. Búsqueda local. Formato PDF. Disponible en: http://delta.cs.cinvestav.mx/~adiaz/anadis/LocalSearch.pdf

Ruiz, J. 2015. Búsqueda local y algoritmos genéticos. Formato PDF. Disponible en: http://www.cs.us.es/cursos/iati/temas/tema-05.pdf

Russell, S y Norvig, P. 2008. Inteligencia Artificial Un Enfoque Moderno. 2 ed. España. Pearson Education. p 1242