Download Búsqueda primero el mejor - Centro de Inteligencia Artificial

Universidad
de Oviedo
Centro de
Inteligencia Artificial
SISTEMAS INTELIGENTES
T3: Búsqueda Heurística
{jdiez, juanjo} @ aic.uniovi.es
Sistemas Inteligentes - T3: Búsqueda Heurísitica
Centro de
Inteligencia Artificial
Universidad
de Oviedo
Índice
•  Conceptos generales de búsqueda
informada o heurística
•  Sistemas de búsqueda heurística
°  Búsquedas sistemáticas:
» Voraz primero el mejor
» Algoritmo A*
» Memoria acotada
°  Búsqueda local:
» Escalada (hill-climbing)
» Temple simulado (simulated annealing)
» Haz local (beam search)
» Algoritmos genéticos (T4)
Sistemas Inteligentes - T3: Búsqueda Heurísitica
Universidad
de Oviedo
Centro de
Inteligencia Artificial
Búsqueda informada o heurística
•  La búsqueda no informada es tremendamente
ineficiente en la mayoría de los casos
•  El propósito de la búsqueda informada es utilizar
conocimiento específico del problema para alcanzar el
objetivo de manera más eficiente
•  La idea es ser capaces de medir la “calidad” de un
estado
•  Eso nos permitirá dirigir la búsqueda por los estados
mejores que estarán “más cerca” del objetivo y no
seguir estrategias en anchura o profundidad que no
tienen en cuenta la calidad de los estados
•  Las estrategias de búsqueda informada son mucho
más eficientes que las no informadas
Sistemas Inteligentes - T3: Búsqueda Heurísitica
Universidad
de Oviedo
Centro de
Inteligencia Artificial
Función de evaluación (I)
•  Función de evaluación f(n), dado un nodo n
estima la distancia desde ese nodo n a un nodo
objetivo
•  Un nodo tendrá más calidad cuanto menor sea la
distancia al objetivo
•  Las búsquedas informadas expanden primero los
nodos que están más cerca del objetivo, aquellos en
los que la función f(n) asigna un menor valor
•  Hay distintas formas de definir la función de
evaluación. Básicamente, se pueden tener en cuenta
dos distancias:
distancia desde el nodo inicial a n
°  La distancia desde n hasta un nodo objetivo
°  La
Sistemas Inteligentes - T3: Búsqueda Heurísitica
Universidad
de Oviedo
Centro de
Inteligencia Artificial
Búsqueda primero el mejor
•  Se expandirán primero los estados con menor
valor de f(n)
•  Es un caso particular de los algoritmos
generales de búsqueda en árboles o grafos
•  El nombre primero el mejor es inexacto, si
realmente supiéramos cuál es el mejor, la
búsqueda sería directa
•  En realidad escogemos el estado que “parece
el mejor”
•  La función de evaluación es un estimador
Sistemas Inteligentes - T3: Búsqueda Heurísitica
Centro de
Inteligencia Artificial
Universidad
de Oviedo
Función de evaluación (II)
•  Puede tener dos componentes:
Coste del camino g(n): coste del mejor camino
conocido para ir desde el nodo inicial al nodo n
Función heurística h(n): estimación del camino de
menor coste desde el nodo n a un objetivo
»  Si n es un objetivo necesariamente h(n)=0
•  Jugando con g(n) y h(n) podemos definir
distintas funciones de evaluación f(n):
»  f(n) = g(n)
(Coste uniforme, búsq. no infor.)
»  f(n) = h(n)
(Voraz primero el mejor)
»  f(n) = g(n)+h(n) (A*)
Sistemas Inteligentes - T3: Búsqueda Heurísitica
Centro de
Inteligencia Artificial
Universidad
de Oviedo
Búsqueda voraz primero el mejor (I)
•  Se trata de expandir el nodo más cercano al
objetivo
f(n)=h(n)
•  No tiene en cuenta el coste de llegar hasta n
•  Se pretende llegar rápidamente a la solución,
sin importar tanto el coste
•  La bondad que tenga la función heurística h
determinará la rapidez con que llegamos a un
estado objetivo
Sistemas Inteligentes - T3: Búsqueda Heurísitica
Centro de
Inteligencia Artificial
Universidad
de Oviedo
Búsqueda voraz primero el mejor (II)
hDLR(n)
= distancia en
línea recta
desde n a
Bucarest
Sistemas Inteligentes - T3: Búsqueda Heurísitica
Universidad
de Oviedo
Centro de
Inteligencia Artificial
Búsqueda voraz primero el mejor (III)
Sistemas Inteligentes - T3: Búsqueda Heurísitica
Universidad
de Oviedo
Centro de
Inteligencia Artificial
Búsqueda voraz primero el mejor (IV)
En este caso encuentra una
solución de forma directa, pero no
es óptima
Su “avaricia” le lleva a descartar
la ruta por Rimnicu Vilcea y
Pitesti, que es 32 Km. más corta
Sistemas Inteligentes - T3: Búsqueda Heurísitica
Centro de
Inteligencia Artificial
Universidad
de Oviedo
Búsqueda voraz primero el mejor (V)
•  La minimización de h(n) puede llevarnos a
ventajas falsas
°  Puede
hacernos expandir nodos innecesarios
°  Si
no se tiene cuidado con los estados repetidos,
podemos llegar a callejones sin salida
•  Se parece a la búsqueda primero en
profundidad y tiene las mismas desventajas:
°  No
es óptima y es incompleta
°  La complejidad es O(bm)
•  La complejidad se reduce en función de la
calidad de la heurística utilizada
Sistemas Inteligentes - T3: Búsqueda Heurísitica
Centro de
Inteligencia Artificial
Universidad
de Oviedo
Búsqueda A* (I)
•  Estrategia más conocida de búsqueda primero el
mejor
•  Trata de minimizar el coste estimado total de la
solución. La función de evaluación es:
f(n) = g(n) + h(n)
•  En este caso f(n) representa el coste estimado menor
de una solución que pase por n
•  Esta estrategia es muy buena, incluso óptima si la
función heurística cumple ciertas condiciones:
°  Admisibilidad: no sobreestimar el coste hasta el
objetivo
°  Consistencia o Monotonía: desigualdades
triangulares entre nodos sucesores
Sistemas Inteligentes - T3: Búsqueda Heurísitica
Centro de
Inteligencia Artificial
Universidad
de Oviedo
Búsqueda A* (II)
Sistemas Inteligentes - T3: Búsqueda Heurísitica
Centro de
Inteligencia Artificial
Universidad
de Oviedo
Búsqueda A* (III)
Sistemas Inteligentes - T3: Búsqueda Heurísitica
Centro de
Inteligencia Artificial
Universidad
de Oviedo
Búsqueda A* (IV)
Sistemas Inteligentes - T3: Búsqueda Heurísitica
Centro de
Inteligencia Artificial
Universidad
de Oviedo
Admisibilidad (I)
h(n) es admisible si no sobrestima el coste
de alcanzar el objetivo, es decir,
h(n) <= h*(n)
(coste óptimo desde n)
Dado que g(n) es el coste exacto para
alcanzar n, f(n) no sobrestima el coste
verdadero de una solución a través de n
f(n) <= f*(n) (coste óptimo de una solución por n)
Ejemplo: hDLR es admisible
Sistemas Inteligentes - T3: Búsqueda Heurísitica
Centro de
Inteligencia Artificial
Universidad
de Oviedo
Admisibilidad (II)
A*, usando el algoritmo de búsqueda en
árboles, es óptimo si h(n) es admisible
Demostración: Supongamos que en la frontera
tenemos un nodo objetivo no óptimo n2 y que el
coste a una solución óptima es C*:
f(n2)=g(n2)+h(n2)=g(n2)>C*
Si consideramos que en la frontera tiene que haber
un nodo n1 que esté sobre un camino solución
óptimo
f(n1)=g(n1)+h(n1)<=C* ya que h es admisible
Luego n2 no será expandido y A* es óptimo
Sistemas Inteligentes - T3: Búsqueda Heurísitica
Centro de
Inteligencia Artificial
Universidad
de Oviedo
Consistencia o Monotonía (I)
h(n) es consistente si para cada nodo n y para
cada sucesor n’ de n generado por cualquier acción
a debe cumplirse que
h(n) <= c(n,a,n’) + h(n’)
Se puede demostrar que si h es consistente
también es admisible
Esto es una forma de desigualdad
triangular, el triángulo está
formado por n, n’ y el objetivo
más cercano a n
Ejemplo: hDLR es consistente
n
c(n,a,n’)
h(n)
n’
h(n’)
objetivo
Sistemas Inteligentes - T3: Búsqueda Heurísitica
Universidad
de Oviedo
Centro de
Inteligencia Artificial
Consistencia o Monotonía (II)
A*, usando el algoritmo de búsqueda en grafos, es
óptimo si h(n) es consistente
Si h(n) es consistente entonces los valores de f(n) a
lo largo de cualquier camino no disminuyen
Demostración: Supongamos n’ sucesor de n entonces g
(n’) = g(n)+c(n,a,n’). Siguiendo la definición:
f(n’)=g(n’)+h(n’)= g(n)+c(n,a,n’)+h(n’)>= g(n)+h(n)= f(n)
Los nodos expandidos por A* tienen valores crecientes de f
(n). Luego el primer nodo objetivo seleccionado para
expandir debe ser la solución óptima, ya que los nodos
posteriores serán al menos tan costosos
Sistemas Inteligentes - T3: Búsqueda Heurísitica
Centro de
Inteligencia Artificial
Universidad
de Oviedo
Búsqueda A* (V)
•  Conclusiones
°  A*
expande todos los nodos con f(n)<C*
°  A* podría expandir nodos con f(n)=C* antes de seleccionar
un nodo objetivo
°  A* no expande ningún nodo con f(n)>C* (poda)
•  A* es óptimamente eficiente, ningún otro algoritmo
óptimo garantiza expandir menos nodos que A*
(excepto por los desempates en f(n)=C*). Los
algoritmos que no expandan todos los nodos f(n)<C*
corren el riesgo de no encontrar la solución óptima
•  La búsqueda A* es completa, óptima y óptimamente
eficiente entre todos los algoritmos
Sistemas Inteligentes - T3: Búsqueda Heurísitica
Centro de
Inteligencia Artificial
Universidad
de Oviedo
Búsqueda A* (VI)
•  Pero A* no es la solución a todos los males
•  En la mayoría de problemas los nodos que cumplen
que f(n)<C* definen un espacio de búsqueda todavía
exponencial
•  El número de nodos expandidos suele ser exponencial
para la mayoría de problemas, lo que supone un
problema de tiempo y espacio
•  Pueden utilizarse variantes que encuentran soluciones
subóptimas o heurísticas más exactas pero no
admisibles
•  BRPM y los algoritmos con memoria acotada (A*M y
A*MS) son evoluciones de A* que utilizan cantidades
limitadas de memoria
Sistemas Inteligentes - T3: Búsqueda Heurísitica
Universidad
de Oviedo
Centro de
Inteligencia Artificial
Búsqueda recursiva primero el mejor (I)
•  Es similar a la búsqueda primero en profundidad
recursiva
•  En lugar de seguir indefinidamente hacia abajo el
camino actual, se mantiene el mejor camino
alternativo disponible de uno de los antepasados del
nodo actual
•  Si el nodo actual excede el límite, la recursividad
vuelve atrás al camino alternativo
•  Cuando vuelve hacia atrás sustituye el valor de f de
cada nodo a lo largo del camino con el mejor valor de f
de uno de sus hijos
•  De esta forma el algoritmo recuerda la calidad de la
mejor hoja del subárbol olvidado y así puede decidir
más tarde si merece expandir de nuevo ese subárbol
Sistemas Inteligentes - T3: Búsqueda Heurísitica
Universidad
de Oviedo
Centro de
Inteligencia Artificial
Búsqueda recursiva primero el mejor (II)
Sistemas Inteligentes - T3: Búsqueda Heurísitica
Universidad
de Oviedo
Centro de
Inteligencia Artificial
Búsqueda recursiva primero el mejor (III)
Sistemas Inteligentes - T3: Búsqueda Heurísitica
Universidad
de Oviedo
Centro de
Inteligencia Artificial
Búsqueda recursiva primero el mejor (IV)
•  Es un algoritmo óptimo si h es admisible
•  La complejidad espacial es O(bd)
•  Su complejidad temporal es difícil de
caracterizar ya que depende de la exactitud de
la función heurística y de cómo cambia el
camino al ir expandiendo nodos
•  El algoritmo sufre al usar muy poca memoria,
aunque tenga más memoria disponible. Eso le
obliga a volver a expandir caminos ya visitados
•  Una solución mejor pasa por usar más
memoria y tener que re-expandir menos nodos
Sistemas Inteligentes - T3: Búsqueda Heurísitica
Universidad
de Oviedo
Centro de
Inteligencia Artificial
Búsqueda A*MS (memoria simplificada) (I)
•  La idea es ocupar toda la memoria disponible
•  Expande nodos de la misma forma que A*
hasta que la memoria se llena. En ese punto,
no se puede añadir ningún nuevo nodo
•  Lo que se hace es eliminar el peor nodo hoja y,
como en BRPM, A*MS devuelve hacia atrás el
valor del nodo olvidado. De esta forma el
antepasado sabe la calidad del mejor camino
en ese subárbol
•  Si todos los descendiente de un nodo n son
olvidados, no sabremos por qué camino ir
desde n, pero sí cuanto cuesta
Sistemas Inteligentes - T3: Búsqueda Heurísitica
Universidad
de Oviedo
Centro de
Inteligencia Artificial
Búsqueda A*MS (memoria simplificada) (II)
•  Es completo si hay alguna solución alcanzable, es decir,
si d es menor que el tamaño de la memoria
•  Es óptimo si alguna solución óptima es alcanzable; de
otra manera devuelve la mejor solución alcanzable
•  Pasa por ser el mejor algoritmo para encontrar
soluciones óptimas cuando:
°  el espacio de estados es un grafo
°  con costes no uniformes
°  la generación de nodos es costosa en comparación
con la gestión de las listas abierta y cerrada
•  Las restricciones de memoria pueden hacer un problema
intratable en cuanto a tiempo de cálculo
•  La compensación entre tiempo y memoria es siempre
ineludible, la única salida es sacrificar la exigencia de
encontrar soluciones óptimas
Sistemas Inteligentes - T3: Búsqueda Heurísitica
Centro de
Inteligencia Artificial
Universidad
de Oviedo
Funciones heurísticas
•  Es fundamental definir buenas funciones heurísticas para
mejorar las búsquedas con A*
•  Un heurístico h está mejor informado que h’ sii los dos
son admisibles y parta todo n no objetivo: h(n)>h’(n)
•  Ejemplo: n-puzzle
h1=número de piezas mal colocadas
°  h2=suma de las distancias de las piezas a sus posiciones objetivo
° 
h1=8
h2=3+1+2+2+2+3+
3+2 =18
Ambas son admisibles
¿Cuál es mejor?
Estado inicial
Estado objetivo
Sistemas Inteligentes - T3: Búsqueda Heurísitica
Centro de
Inteligencia Artificial
Universidad
de Oviedo
Formas de definir funciones heurísticas
•  Relajando el problema
° 
Original: una ficha puede moverse de A a B si son adyacentes
(horizontal o verticalmente) y B es vacía
» un ficha puede moverse de A a B si son adyacentes (h2)
» un ficha puede moverse de A a B si B es vacío
» un ficha puede moverse de A a B en cualquier caso (h1)
•  Combinando heurísticas
° 
si disponemos de un conjunto de heurísticas admisibles h1,
…,hm y ninguna domina al resto:
h(n)=max{h1,…,hm } h domina a todas las demás
•  Calculando el coste de un subproblema
•  Mediante programas:
ABSOLVER genera heurísticas a partir de la definición formal
del problema, relanjándolo
°  Programas que aprenden a partir de la experiencia
° 
Sistemas Inteligentes - T3: Búsqueda Heurísitica
Universidad
de Oviedo
Centro de
Inteligencia Artificial
Técnicas de búsqueda local (I)
•  Los algoritmos de búsqueda local se usan cuando el
camino hasta el objetivo es irrelevante y
solamente interesa el estado objetivo
•  Muchos de ellos funcionan con un solo estado, el
actual, y se mueven a los vecinos de ese estado
•  Se utilizan para resolver problemas de optimización
puros, en los que no existe un estado objetivo, sino
que se trata de encontrar el mejor estado según una
función objetivo
•  Ventajas:
°  Este
tipo de algoritmos usan menos memoria ya que no
necesitan mantener los caminos hasta la solución
°  A menudo encuentran soluciones razonables en espacios de
estados muy grandes en los que los algoritmos sistemáticos
son inadecuados
Sistemas Inteligentes - T3: Búsqueda Heurísitica
Centro de
Inteligencia Artificial
Universidad
de Oviedo
Técnicas de búsqueda local (II)
Función objetivo
Máximo global
Terraza
Máximo local
Meseta
Estado actual
Sistemas Inteligentes - T3: Búsqueda Heurísitica
Espacio de
estados
Universidad
de Oviedo
Centro de
Inteligencia Artificial
Técnicas de búsqueda local (III)
z = 3*(1-x)2 *
exp(-(x2) - (y+1)2) –
10*(x/5 - x3 - y5) *
exp(-x2-y2) 1/3*exp(-(x+1)2 – y2)
Sistemas Inteligentes - T3: Búsqueda Heurísitica
Centro de
Inteligencia Artificial
Universidad
de Oviedo
Búsqueda por escalada (hill-climbing) (I)
•  Es un algoritmo voraz, que no mantiene un árbol de
búsqueda, sino sólo la representación del estado
actual y el valor de su función objetivo
•  No se mira más allá de los vecinos inmediatos del
estado actual
•  Escoge el vecino que tiene un mejor valor de la
función objetivo
•  Finaliza cuando alcanza un “extremo” (máximo o
mínimo, depende del planteamiento)
•  Obviamente no garantizan encontrar la solución
óptima, la búsqueda se puede quedar atascada:
en un máximo o mínimo local
°  en una meseta, en una terraza
°  en una cresta
° 
•  Pero es capaz de encontrar soluciones rápidamente
Sistemas Inteligentes - T3: Búsqueda Heurísitica
Centro de
Inteligencia Artificial
Universidad
de Oviedo
Búsqueda por escalada (hill-climbing) (II)
•  8-reinas con búsqueda por escalada:
°  Cada
estado tiene las 8 reinas en el tablero
°  La función sucesor devuelve todos los estados posibles
moviendo una reina a otra posición de la misma columna
°  La función objetivo es el numero de pares de reinas que se
atacan, directa o indirectamente
h=17
h=1
Sistemas Inteligentes - T3: Búsqueda Heurísitica
Centro de
Inteligencia Artificial
Universidad
de Oviedo
Variantes de hill-climbing
•  Escalada estocástica
°  escoge
aleatoriamente entre todos los sucesores con mejor
valoración que el estado actual
•  Escalada de primera opción
°  generan
aleatoriamente sucesores, escogiendo el primero
con mejor valoración que el estado actual
•  Escalada con reinicio aleatorio
°  se
repite varias veces la búsqueda, partiendo cada vez de
un estado inicial distinto, generado aleatoriamente
°  “si no te sale a la primera, inténtalo otra vez”
°  si la probabilidad de éxito de una búsqueda individual es p,
entonces el número esperado de reinicios es 1/p
Sistemas Inteligentes - T3: Búsqueda Heurísitica
Universidad
de Oviedo
Centro de
Inteligencia Artificial
Búsqueda por temple simulado
•  Temple: proceso para endurecer metales, calentándolos a un
temperatura alta y luego dejándolos enfriar gradualmente
•  La idea es movernos de los extremos locales mediante sacudidas
(simulan la temperatura) que irán decreciendo en intensidad
•  Trata de combinar hill-climbing con búsqueda aleatoria
•  Se selecciona aleatoriamente un sucesor del estado actual y se
pasa a él de forma condicional:
° 
° 
Si su valoración es mejor, se pasa a ese nuevo estado
Si la valoración del sucesor no es mejor, pasamos con probabilidad eΔE/T
-  ΔE es el gradiente de la valoración
-  T es una metáfora de la temperatura en un proceso de templado metalúrgico
•  Si T disminuye bastante despacio, el algoritmo encontrará un óptimo
global con probabilidad cerca de uno
•  Utilizada en problemas de distribución VLSI y de optimización a gran
escala
Sistemas Inteligentes - T3: Búsqueda Heurísitica
Centro de
Inteligencia Artificial
Universidad
de Oviedo
Búsqueda por haz local (beam search)
•  Se guarda la pista de k estados
Comienza con estados generados aleatoriamente. Si alguno es
objetivo, se detiene la búsqueda
En cada paso se generan todos los sucesores de los k estados.
°  Si alguno es objetivo, se detiene la búsqueda
°  Si no, se seleccionan los k mejores sucesores de la lista
completa y se repite el proceso
•  Es diferente a lanzar en paralelo k escaladas con
reinicio aleatorio:
En la búsqueda por haz local la información útil se pasa entre
los k hilos de búsqueda, si uno genera mejores sucesores, los k
hilos de búsqueda seguirán por ese camino
•  Puede carecer de diversidad en los k estados
Sistemas Inteligentes - T3: Búsqueda Heurísitica
Universidad
de Oviedo
Centro de
Inteligencia Artificial
Búsqueda por haz estocástica
•  La búsqueda por haz local puede concentrarse
rápidamente en pequeñas regiones del espacio
de estados (explotación)
•  A veces es necesario explorar otras zonas
aparentemente peores
•  Trata de combinar la explotación de las zonas
mejores con la exploración de las zonas
aparentemente peores
°  En
vez de elegir los k mejores sucesores, se eligen k
sucesores con una probabilidad que es función
creciente de su valoración
°  los mejores tiene mayor probabilidad de ser elegidos,
aunque no siempre lo serán
°  Guarda relación con la selección natural
Sistemas Inteligentes - T3: Búsqueda Heurísitica
Universidad
de Oviedo
Centro de
Inteligencia Artificial
Búsqueda en espacios continuos (I)
•  La función sucesor devuelve infinitos estados
•  Ejemplo: colocar tres aeropuertos en Rumania
minimizando su distancia a las ciudades
°  estados:
están definidos por las coordenadas de los 3
aeropuertos: (x1,y1) (x2,y2) (x3,y3)
°  función objetivo: f(x1,y1,x2,y2,x3,y3)=distancia de todas las
ciudades a su aeropuerto más cercano
•  Muchos métodos usan el gradiente que nos da
la magnitud y la dirección de la inclinación más
pronunciada:
⎛ ∂f ∂f ∂f ∂f ∂f ∂f ⎞
⎟⎟
∇f = ⎜⎜
,
,
,
,
,
⎝ ∂x1 ∂x2 ∂x3 ∂x4 ∂x5 ∂x6 ⎠
Sistemas Inteligentes - T3: Búsqueda Heurísitica
Centro de
Inteligencia Artificial
Universidad
de Oviedo
Búsqueda en espacios continuos (II)
•  Normalmente, no podemos encontrar un
extremo resolviendo de forma directa ∇f = 0
•  Pero podemos calcular el gradiente localmente
•  y hacer un hill-climbing actualizando el estado
actual
x ← x + α∇f (x)
donde α es una pequeña cte
•  La determinación de α es fundamental: si es
pequeña necesitaremos muchos pasos para
alcanzar un extremo, y si es grande podremos
pasarnos del extremo
Sistemas Inteligentes - T3: Búsqueda Heurísitica