Please enable JavaScript.
Coggle requires JavaScript to display documents.
Capítulo 4. Búsqueda Informada y exploración (Algoritmos de búsqueda local…
Capítulo 4. Búsqueda Informada y exploración
Estrategias de búsqueda informada
Búsqueda primero el
mejor
Se selecciona un nodo para la expansión
basada en una función de evaluación, f (n).
Se selecciona para la expansión el nodo con la evaluación más baja, porque la evaluación mide la distancia al objetivo
Un componente clave de estos algoritmos es una base heurística
Búsqueda voraz primero el mejor
Intenta expandir el nodo más cercano al objetivo
Evalúa los nodos utilizando sólo la función heurística: f (n) = h (n)
Búsqueda A*
Evalúa los nodos combinando g (n), costo para llegar al nodo y h (n), el costo de ir al nodo de destino: f (n) = g (n) + h (n)
G (n) nos da el costo de la ruta desde el nodo de inicio hasta el nodo n
h (n) el costo estimado de la ruta más barata desde n hasta el objetivo
f (n) el costo estimado más bajo de la solución a través de n
Búsqueda heurística con memoria acotada
La diferencia principal entre A * PI y el estándar iterativo de profundidad es que el corte utilizado es el costo (g + h) en lugar de la profundidad
La forma más sencilla de reducir los requisitos de memoria para A * es adaptar la idea de profundización iterativa al contexto de búsqueda heurística.
Da como resultado
El algoritmo A
de profundidad iterativa = A *
PQ
Funciones Heurísticas
Precisión heurística en el rendimiento
Una forma de caracterizar la calidad de una heurística es el factor de ramificación b * eficaz
Si el número total de nodos generados por A* para un problema particular es N,
y la profundidad de la solución es d.
Entonces
b* es el factor de ramificación que un árbol
uniforme de profundidad d debería tener para contener N + 1 nodos
Funciones heurísticas admisibles
La heurística es admisible porque la solución óptima en el problema original es también una solución en el problema relajado.
La heurística admisible debe ser al menos tan costosa como la solución óptima en el problema relajado
Una función heurística h(n), estima el costo de una solución que comienza desde el estado en el nodo n.
Algoritmo de aprendizaje inductivo
Se puede utilizar para construir una función h(n) que pueda predecir los costos solución para otros estados que surjan durante la búsqueda.
Algoritmos de búsqueda local y problemas de optimización
Algoritmo de búsqueda
Funcionan con un solo estado actual(más que múltiples caminos) y generalmente se mueve sólo a los vecinos del estado.
Son útiles para resolver problemas de optimización
Ventajas
Usan muy poca memoria
Pueden encontrar a menudo soluciones razonables en espacios de estados grandes o infinitos.
Problemas de optimización
Su objetivo es encontrar el mejor estado según una función objetivo.
Paisaje del espacio de estados
Tiene
Posición
Definido por el estado
Elevación
Definido por el valor de la función de coste heurística o función objetivo.
Si la elevación corresponde al costo, entonces el objetivo es encontrar el valle más bajo
(mínimo global)
Si la elevación corresponde a una función objetivo, entonces hay que encontrar un pico más alto
(máximo global)
Búsqueda de ascensión de colinas
Algoritmo de búsqueda de ascensión de colinas
Un bucle que continuamente se mueve en dirección del valor creciente es decir cuesta arriba.
Termina cuando alcanza un pico en donde ningún vecino tiene un valor más alto.
Se atasca por:
Máximo local
Es un pico que es más alto que cada uno de sus estados vecinos, pero más abajo que el máximo global.
Crestas
Causan una secuencia de máximos locales que hace muy díficil la navegación para los algoritmos avaros.
Meseta
Es un área del paisaje del espacio de estados donde la función de evaluación es plana.
Máximo local plano
Una terraza
Variaciones de la ascensión de colinas
Ascensión de colinas estocástica
Ascensión de colinas de primera
Ascensión de colinas de reinicio aleatorio
Búsqueda de temple simulado
Combinar la ascensión de colinas con un camino aleatorio de algún modo que produzca tanto eficacia como completitud
Búsqueda por haz local
Guarda la pista de k estados (no sólo uno)
Comienza con estados generados aletaoriamente
En cada paso, se generan todos los sucesores de los k estados.
Si alguno es un objetivo se detiene el algoritmo
Se seleccionan los k mejores sucesores de la lista completa y se repite.
Algoritmos genéticos
Es una variante de la búsqueda de haz estocástica en la que los estados sucesores se generan combinando dos estados padres, más que modificar un solo estado.
Comienzan con un conjunto de k estados generados aleatoriamente llamados
población
Cada estado o individuo está representado como una cadena sobre un alfabeto finito.
Función idoneidad
Debería devolver valores más altos para estados mejores.
Búsqueda local en espacios continuos
Los espacios continuos dimensionalmente altos son lugares grandes en los que es fácil perderse.
Un modo de evitar problemas continuos es discretizar la vecindad de cada estado y luego se puede aplicar cualquiera de los algoritmos de búsqueda local.
Agentes de búsqueda online y ambientes desconocidos
Funciona intercalando el cálculo y la acción, primero toma una acción, observa el entorno y calcula la siguiente acción.
Es una idea mejor para dominios estocásticos.
Es una idea necesaria para un problema de exploración, donde los estados y las acciones son desconocidos por el agente.
Problemas de búsqueda en linea
Puede resolverse solamente por un agente que ejecute acciones, más que por un proceso puramente computacional.
Agentes de búsqueda en línea
Después de cada acción, un agente online recibe una percepción al decirle que estado ha alcanzado, de esta información puede aumentar su mapa del entorno.
Búsqueda local en línea
Los agentes aprenden un "mapa" del entorno simplemente registrando cada una de sus experiencias
Los agentes de búsqueda locales adquieren estimaciones más precisas del valor de cada estado utilizando las reglas de actualización locales, como en AA * TR.