Inteligencia Computacional

Si bien los métodos estudiados de búsqueda ciega nos permiten encontrar una solución, son terriblemente ineficientes. El conocimiento acerca del dominio del problema nos permite evaluar a determinadas direcciones de búsqueda como más prometedoras. Este conocimiento es denominado conocimiento heurístico y permite, al incorporarlo en las etapas de selección y refinamiento, lograr búsquedas más eficientes.

El método Depth First informado (profundidad primero informado), se trata de expandir por el nodo que parece más prometedor para alcanzar el objetivo.

Para realizarlo, se utiliza una función que permita evaluar cuan prometedor es un nodo, a esta función se la denomina funciónheurística.

• h(n)  es una función heurística, estima el menor costo desde el nodo n  hasta la meta.

Volviendo a nuestro ejemplo de ir de A hacia E (donde la letras representan ciudades y los arcos rutas) una función heurística práctica sería la distancia aérea entre las ciudades. Es plausible que si la distancia área es menor entonces el nodo esté más cerca de la meta y por lo tanto conviene expandirlo.

La calidad de la función h(n) determinará el grado de disminución de la complejidad temporal y de memoria con respecto a la búsqueda profundidad primero. Este tipo de estrategia no es completa ni óptima, aunque si la heurística es buena uno puede esperar que el camino hallado sea lo suficientemente aceptable. Se implementa en nuestro algoritmo en la función Obtener_Nodo para que devuelva el nodo de menor heurística (o puede también insertarse en forma ordenada en la lista ABIERTA).

Poda del Arbol de Búsqueda

Así como se introduce la heurística en la etapa de selección para elegir el camino más prometedor, es posible reducir el árbol de búsqueda en la etapa de refinamiento, a esto lo llamamos podar el árbol de búsqueda.

 La poda puede ser clasificada en tres tipos:

• Irrevocable: se eliminan todos los nodos salvo uno.
• Tentativa: no se elimina ningún nodo
• Parcialmente Tentativa: se eliminan algunos nodos.

El criterio básico de poda es eliminar los nodos repetidos, ya sea total, es decir no permitirlos en la lista CERRADOS ni ABIERTOS o parcialmente, o sea, no permitirlos en la lista ABIERTOS. Este criterio es denominado de no redundancia.

Además del criterio de no redundancia, existen otros criterios de poda que utilizan información heurística.

Subconjunto de ancho e:Se eliminan los nodos cuya función heurística difiera del mínimo en más de cierta cantidad e.

Subconjunto F(x): Se eliminan los nodos que no cuenten con la propiedad F(x), la determinación de F(x) dependerá del dominio.

Heurística Decreciente: Se eliminan los nodos cuya función heurística sea mayor que la de su predecesor. Intuitivamente esto indicaría eliminar los nodos que nos alejen del objetivo.

La búsqueda A* se basa en reducir al mínimo el costo total del camino. El método

Depth Firstinformado reduce al mínimo h(n), pero si bien es eficiente no es completa ni óptima. Por otro lado, la búsqueda con costo uniforme reduce g(n) y sí es completa y óptima, pero no eficiente. La idea de A* es combinar ambas para aprovechar sus ventajas respectivas. Definimos entonces una función f(n) como:

f(n) = g(n) + h(n)

La función f(n) representa el costo estimado del camino más corto que pasa por n. Dado que g es el costo hasta n y h el costo estimado desde n.

Si se elige la h cumpliendo determinada condición se puede demostrar que la estrategia que elija el nodo que minimice f(n) es completa y óptima. La restricción que hace que h sea denominada heurística admisible, consiste en elegir una función que nunca sobreestime el costo de alcanzar la meta. Si h es admisible entonces f(n) nunca sobreestimará el costo real del camino más corto (barato) que pase por n.

Muchas veces no es posible o fácil hallar una función heurística que siempre subestime el costo hasta la meta o por lo menos garantizar que así lo hace. Hay que tomar en cuenta que si h es muy chico entonces perderíamos eficiencia (el caso paradigmático sería que h(n) = 0 para todo n lo que implica recorrer todo el árbol). Muchas veces se utiliza una función que en algunos casos pueda sobreestimar un poco.

Consiste en ordenar los número del 1 al 8 como se ve en la figura, de un estado desordenado como el de la izquierda se llega a la solución en el cuadro de la derecha.

Los movimientos son desplazar espacio en blanco hacia abajo, arriba o los costados (sin salir del cuadro) y el número tapado pasa a ocupar el lugar donde estaba el blanco. Es similar al conocido juego del 15. Una heurística adecuada para este juego es por ejemplo el número de fichas fuera de lugar. En la figura vemos un árbol de dos niveles:

La expansión vista puede ser parte del árbol de búsqueda de una estrategia ancho primero. El árbol muestra una expansión con la poda utilizando el criterio de no redundancia. Una estrategia A* nos brinda una solución óptima y bastante eficiente. Es posible utilizar la heurística mencionada ya que es admisible.

Actividad

• Completar el árbol de búsqueda para las siguientes estrategias:
  • Profundidad primero
  • Ancho Primero
  • Profundidad Primero Informado (h(n) = nro. de piezas fuera de lugar)

Hay problemas en los cuales el camino desde el estado inicial hasta la solución no es relevante. Son problemas en los cuales se puede establecer la condición que debe cumplir un estado para ser el estado final y que el sólo hecho de expresarlo ya es solución al problema. Por ejemplo en el juego de las 8 reinas, que consisten poner 8 reinas en un tablero de ajedrez sin que se puedan comer entre sí, no importa como se llega a la disposición de las mismas ya que esta disposición es la solución en sí. Si pudiéramos mostrar o dibujar el estado final no habría problema. Otro problema que tiene estas características es el de disponer las áreas de un chip VLSI. Para este tipo de problemas los algoritmos de mejoramiento iterativo son muy útiles. Se basa en disponer una configuración y luego ir cambiándola para mejorar su calidad hasta llegar a la solución óptima (o en muchos casos subóptima). La optimización de funciones puede encararse con este tipo de algoritmos.

Hillclimbing (Escalada a la cima)

Este método también es denominado disminución de gradiente. Este algoritmo sólo mantiene un nodo y a partir de pequeños cambios va mejorando. Básicamente consiste en utilizar el criterio de único sucesor (en la etapa de refinamiento se mantiene sólo un nodo) y exigiendo que la función heurística sea estrictamente decreciente. Tiene la hipótesis de que al ir hacia mínimos locales se puede alcanzar un mínimo global. Se presenta el riesgo de quedar atrapado por mínimos locales (o máximo si se considera la función de evaluación como costo en vez de calidad). Otro riesgo es el de llegar a una planicie donde no haya variaciones, es decir lugares donde el espacio de estado tenga a la función de evaluación plana.

Para evitar esos problemas se puede aplicar la estrategia de restart aleatorio (reinicio aleatorio). Es decir realizar varias búsquedas con estado de inicio aleatorio hasta parar o hasta que no haya avance significativo. El algoritmo de la figura tiene dos ciclos: uno itera hasta llegar a un optimo local, el otro comienza una nueva búsqueda. Se deben guardar los resultados de cada iteración para obtener el mejor.

Endurecimiento Simulado (Simulated Annealing)

El endurecimiento (o recocido, o fusión) simulado consiste en que: en vez de empezar otra vez cuando se llega a un máximo local, se retrocede algunos pasos (para escapar del máximo local). El algoritmo es similar al Hillclimbing, pero en vez de optar por el mejor sucesor se elige uno al azar, si éste es mejor se avanza, pero sino se avanza con una probabilidad determinada (menor que uno). La probabilidad disminuye exponencialmente con lo malo que sea el nuevo estado.

Para eso se utiliza un parámetro T (temperatura) que a medida que disminuye es menos probable que se acepten los estados malos. Esta técnica se basa en una analogía con el proceso de llegar al equilibrio termal mediante el enfriamiento gradual. En el algoritmo, la función de evaluación correspondería a energía del sistema en ese estado.

A continuación se ve un pseudocódigo del algoritmo:

Simulated annealing

vc:= estado_inicial

inicializar temperatura T

repetir

            repetir

                  vn := seleccionar un sucesor de vc

                 ∆E := h(vn) – h(vc)

                si ∆E > 0 entonces

                         vc  := vn

               sino

                           si random(0,1) < e ^{∆E / T} entonces    vc := vn fin si                                                             

                  fin si

            hasta que (condición de terminación)

           T := g(T,t)

            t:= t +1

hasta que (criterio se parada)

El algoritmo de simulated annealing presentado tiene varias iteraciones, la función random(0,1) retorna un número al azar entre 0 y 1, la temperatura disminuye mediante la función g(T,t) (g(T,t) <T para todo t). El agoritmo termina para algún valor pequeño de T establecido en el criterio de parada.

Actividad

• Realizar el árbol de búsqueda para el ejemplo de ir de A hasta E y para el puzzle de las 8 fichas.
• Realizar los árboles de búsqueda para el grafico del ejemplo pero tomando como partida y final distintas ciudades