Algoritmos de Búsqueda Local y Problemas de Optimización

1.1.       INTRODUCCIÓN

En anteriores publicaciones hable sobre las búsquedas informadas y diversas estrategias que se utilizan para este tipo de búsquedas generando una secuencia de posibles estados de manera sistemática, en las búsquedas locales lo importantes es alcanzar al estado objetivo más que como se hizo para poder llegar, si bien es conocido las búsquedas informadas son efectivas al momento de encontrar un resultado, aunque este no sea el más óptimo.

En vista de que existen problemas en los que se deben satisfacer ciertas restricciones para llegar al mejor de todos los objetivos, surgen algunos algoritmos de búsqueda local y problemas de optimización en los cuales el camino hacia la solución del problema es irrelevante y lo que importa es simplemente la solución.

En esta publicación les hablare de aquellos algoritmos de búsqueda local y de cómo funcionan.

1.2.       OBJETIVO 

Conocer la importancia de los algoritmos de búsqueda local y problemas de optimización para comprender su funcionamiento y uso en la solución de problemas de agentes.

MARCO TEÓRICO

Como ya he mencionado estos algoritmos de búsqueda local no se preocupan por los caminos que se puedan tomar para llegar a un estado óptimo, si no que se enfocan en su gran parte en el estado actual y se mueve de un estado vecino hacia otro, este tipo de algoritmos tienen algunas ventajas que los vuelven importantes en comparación con otros algoritmos como son:

·         Son ahorrativos: No usan mucha memoria ya que no almacenan la secuencia de estados.

·         Razonables: Ofrecen soluciones posibles a un problema cuando el espacio de estados es infinito.  

·         Óptimos: Capaces de encontrar el mejor estado en base a su función objetivo. 

2.1.       Búsqueda Por Ascensión En Colina

Este algoritmo es una de las estrategias de las búsquedas locales, el cual no mantiene un árbol de búsqueda si no que solo la representación del estado actual y el valor de la función objetivo, se basa en iteraciones que intentan dar solución a un problema localizando la mejor solución a través de la modificación de un elemento incremental. El nombre de este algoritmo se debe gracias a que realiza una búsqueda hacia arriba y termina cuando alcanza el lugar más alto de ahí surge la similitud con una colina.

Imagen 1: Representación del Algoritmo Ascensión de Colinas

Pese a que es un algoritmo simple y muy conocido en inteligencia artificial por ser bueno para encontrar un óptimo local no garantiza encontrar la solución óptima debido a que pueden existir muchos posibles estados en donde la búsqueda se puede atascar debido a un estado máximo o mínimo local, una meseta y una cresta.

Este algoritmo posee tres variantes diferentes y estas son:

Imagen 2: Variaciones del Algoritmo Ascensión en Colina

2.1.       Búsqueda De Temple Simulado

Este algoritmo surge como alternativa para el algoritmo de ascensión de colinas ya que este no es muy complejo debido a que solo verifica los caminos cuesta arriba y no pasa por estados bajos donde el costo es más alto y se estanca en máximos locales.

El temple simulado es una combinación de la ascensión de colinas y la aleatoriedad que establezca completitud, esta clase de algoritmos no escoge el mejor movimiento si no que más bien lo hace de manera aleatoria y si esta mejora la situación actual entonces es aceptado.

Imagen 3: Algoritmo Temple Simulado

2.1.       Búsqueda Por Haz Local

A diferencia de las otras búsquedas en las cuales los estados expandidos y sus nodos no son guardados en la memoria, la búsqueda por haz local guarda la pista de K estados, y se generan estados sucesores aleatorios para cada uno de ellos, por lo que se seleccionan los mejores sucesores y en caso de ser el objetivo el algoritmo se detiene, en caso de no ser el objetivo se selección los K mejores estados de una lista completa y se repite el proceso.

La gran diferencia con el algoritmo de reinicios aleatorios es que la búsqueda por haz local no es independiente, poniendo un ejemplo tenemos un estado generado aleatoriamente puede generar a su vez muchos otros estados considerados buenos, y otro estado puede generar el mismo número de estados, pero malos y solo uno bueno, esto puede indicar claramente que el estado a elegir sería el primero en la lista.

Imagen 4: Algoritmo Haz Local

2.1.       Algoritmos Genéticos

Estos algoritmos son una variante de los algoritmos de Haz local, estos son métodos adaptativos que pueden ser utilizados para implementar búsquedas y problemas de optimización, se basan en los procesos genéticos de los organismos biológicos, codificando una posible solución a un problema en un "cromosoma" compuesto por una cadena de bits o caracteres. Estos algoritmos se enfocan en la combinación de dos estados padres para formar un nuevo estado sucesor o hijo.

Imagen 5: Algoritmo Genético

CONCLUSIONES

Los algoritmos de búsqueda local y problemas de optimización son una medida de solución arbitraria a un problema, es decir que se trata de maximizar o minimizar un resultado, esto en base a la búsqueda del mejor resultado posible dentro de un espacio de resultados, a travez de un conjunto de restricciones determinados por el tipo de búsqueda local que se realice.

Es clase de algoritmos son muy eficaces en problemas complejos, aplicados al mundo real, como producción y ciertas actividades que requieren precisión y mejora de resultados. Dentro de estos algoritmos, están los mas complejos, que son los algoritmos genéticos, los cuales son muy conocidos pero tienen una utilización compleja.

BIBLIOGRAFIAS

Russell, S., Norvig, P. 2008. Inteligencia Artificial Un Enfoque Moderno. Segunda Edición. Pearson Education. España