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
