Calidad del conjunto de soluciones candidatas codificadas por el nodo.
Cantidad de la información que se puede ganar expandiendo un nodo dado y la importancia de la información para guiar la búsqueda.
En todos estos casos la calidad el nodo se estima numéricamente por una función de evaluación heurística f(n). Una función de evaluación heurística es una función que hace corresponder situaciones del problema con números. Es decir, ofrece una medida conceptual de la distancia entre un estado dado y el estado objetivo. En general depende de la descripción de n (la descripción del objetivo, la información obtenida hasta ese punto de la búsqueda y cualquier conocimiento extra sobre el dominio del problema).
El proceso de construcción de funciones heurísticas bien puede ser considerado un proceso de descubrimiento, pues es muy difícil articular el mecanismo por el cual se llega a estas funciones. Sin embargo, se puede formular el siguiente paradigma general: las heurísticas se descubren consultando modelos simplificados del dominio del problema.
Estos valores son usados para determinar cual operación ejecutar a continuación, típicamente seleccionando la operación que conduce a la situación con máxima o mínima evaluación. Un inconveniente de los métodos heurísticos es que en ocasiones no es posible conocer la calidad de la solución, es decir, cuán cerca está el óptimo (x*) la solución heurística encontrada (xheu); si por ejemplo, el problema es de maximización lo único que sabemos es que xheu ( x*. Una forma simple de evaluar la calidad de una solución heurística es generar aleatoriamente varias soluciones y si son similares a la misma entonces cabría poner en duda la efectividad de la heurística.
Algunas consideraciones sobre las funciones heurísticas son:
a) La función debe dar un estimado útil y realista del mérito de un estado particular.
b) La evaluación de la función en general no debe requerir un gran cálculo en su aplicación. Si la evaluación de la función es computacionalmente compleja puede ser más eficiente hacer una búsqueda a ciegas en lugar de gastar recurso (tiempo y memoria) en el cálculo de la función.
c) Frecuentemente el costo de una solución exacta a un problema flexibilizado es una buena heurística para el problema original. Un problema flexibilizado es uno obtenido a partir del problema original simplificando las restricciones sobre los operadores. La idea es que el número exacto de movimientos requeridos para resolver un problema más simple puede ser fácil de calcular y puede servir como un estimado de la cantidad de movimientos necesitados para resolver el problema original.
d) Es siempre mejor usar una función heurística con valores más altos que otras, siempre que esta no este sobreestimada. Para un problema puede haber una colección de heurísticas admisibles h1,…,hm. Si una de ellas domina a las otras, es decir alcanza valores mayores para todos los nodos, se debe seleccionar esta. Si ninguna es dominante lo mejor es definir una heurística compuesta de la forma siguiente:h(n)=max(p(n),…,hh1(n)).De esta forma h dominará todas las heurísticas individuales.
e) Otra forma de inventar una buena heurística es usar información estadística. Esto puede ser hecho realizando una búsqueda sobre una cantidad de problemas de entrenamiento, por ejemplo, en el juego de las ocho piezas cien configuraciones generadas aleatoriamente.
f) Frecuentemente es posible seleccionar rasgos de un estado que contribuyen a su evaluación heurística. La función de evaluación heurística puede ser construida como una combinación lineal de estos rasgos. Los rasgos pueden tener un peso que indique su importancia.
g) Otro tipo de modelo flexibilizado para un problema son los modelos analógicos. Aquí el modelo auxiliar flexibilizado extrae su potencia no de simplificar la estructura del problema a resolver sino de usar procesos de búsqueda que fueron empleados con éxito en problemas análogos. Esto se retoma posteriormente al estudiar el razonamiento por analogía.
Ejemplo: El problema de las ocho reinas
Asumiendo la variante incremental del juego, es decir poner las reinas una a una de modo que no se ataquen mutuamente, supóngase que se tienen situadas tres reinas y tenemos que decidir donde colocar la cuarta. El papel de la heurística aquí sería ofrecer un criterio para decidir cual de las tres posiciones indicadas es la más promisoria de conducir a una solución satisfactoria.
Al deducir una heurística para este problema podemos razonar que para poder colocar las ocho reinas tenemos que dejar libres la mayor cantidad de opciones como sea posible para futuras adiciones de reinas.
Esto significa determinar la cantidad de casillas en las filas no utilizadas que quedarían no atacadas al colocar la cuarta reina en A, B o C. Una casilla candidata será preferida si deja la mayor cantidad de casillas no atacadas en el resto del tablero. Consecuentemente el número de casillas no atacadas constituye una medida de su mérito, es decir, es la función de evaluación heurística para este problema.
Al calcular la función heurística para las posiciones A, B y C se tiene:
f(A) = 8
f(B) = 9
f(C)= 10
Otra alternativa o enfoque heurístico es el siguiente. Las filas no usadas no tienen igual estatus ya que aquellas con pocas casillas no atacadas tienden a quedar bloqueadas más rápidamente que filas con muchas casillas no atacadas. Consecuentemente, si queremos minimizar la posibilidad de un futuro bloqueo debemos focalizar nuestra atención sobre la fila con menor número de casillas no atacadas, sea f" esta heurística. Para esta función tenemos,
f"(A) = 1
f"(B) = 1
f"(C)= 2
Nótese que con esta heurística C también es la alternativa preferida. Además, si alguna opción candidata toma valor cero para f o f" no tiene sentido considerarla pues eventualmente será un nodo muerto, la función f" supera a f en que esta detecta todos los nodos muertos predichos por f y muchos más.
Como se vio antes el objetivo de este juego es reordenar una configuración inicial dada de ocho piezas sobre un tablero de tres por tres en una configuración final.
En el reordenamiento sólo se permite desplazar fichas a la casilla vacía, siempre que sea adyacente, es decir la regla es:
Una pieza puede moverse de la posición X a la Y Si la posición X es adyacente a Y y
la posición Y está vacía.
Una solución típica para este problema requiere alrededor de veinte pasos, aunque este número varía dependiendo del estado inicial. El factor de ramificación es aproximadamente tres (cuando la casilla vacía está en el centro hay cuatro movimientos posibles y cuando está en una esquina hay dos). Esto significa que una búsqueda exhaustiva a profundidad veinte podría requerir cerca de 320 = 3.5×109 estados. Eliminando los estados repetidos quedarían 9! = 362, 880 ordenamientos diferentes. Esta es aún una cantidad grande de estados por lo que se requiere encontrar una buena función heurística.
Un razonamiento a seguir para construir la función heurística para este problema es estimar cuán cerca un estado está del objetivo. Hay dos variantes comúnmente usadas para estimar la proximidad de un estado a otro:
i) Cantidad de piezas mal ubicadas, aquellas por las cuales los dos estados difieren, llamada p.
ii) La suma de las distancias (horizontal y vertical) de las piezas a sus posiciones en el estado objetivo, llamada h2. Esta función heurística se conoce como distancia Manhattan.
Al aplicar estas heurísticas al planteamiento anterior se tiene
h1(A) = 2 h1(B) = 3 h1(C) = 4
h2(A) = 2 h2(B) = 4 h2(C) = 4
Ambas funciones indican que A es la mejor opción y por eso debe ser explorado antes que B o C.
La variante de encontrar funciones heurísticas flexibilizando el modelo del problema se puede ilustrar con este juego. A partir de la regla que gobierna el juego se pueden generar tres problemas flexibilizados removiendo una o más de las condiciones:
(a) Una ficha se puede mover de X a Y si X está adyacente a Y (elimina la condición que Y esté vacío)
(b) Una ficha se puede mover de X a Y si Y está vacía (elimina la condición de que ambas sean adyacentes)
(c) Una ficha se puede mover de X a Y (elimina ambas condiciones)
La cantidad de movimientos requeridos para resolver el problema (a) es exactamente igual a la distancia Manhattan.
La cantidad de movimientos requeridos para resolver el problema (C) es exactamente igual a la cantidad de fichas fuera de lugar, es decir que están en una posición diferente a la que deben tener en el estado objetivo; la cual coincide con H1.
La función h1 es más barata pero menos precisa que h2.
En el caso del problema (b) la cantidad de movimientos requeridos para resolverlo es la cantidad de veces que la posición vacía tiene que ser intercambiada con otra ficha, lo cual sugiere otro estimado heurístico para el problema original.
Propiedades de las funciones de evaluación heurística
a. Heurísticas admisibles.
Una función de evaluación heurística se denomina admisible si ella nunca sobrestima el costo real de alcanzar el objetivo.
b. Heurística más informada.
Para dos heurísticas admisibles f1 y f2, si f1(n) ( f2(n), para cualquier estado n en el espacio de búsqueda, se dice que la heurística f2 es más informada que f1.
Si una heurística f2 es más informada que f1, entonces el conjunto de estados examinados por f2 es un subconjunto de los expandidos por f1.
Bibliografía
Rafael Bello, Presentación Power Point, Inteligencia Artificial, Universidad Central de Las Villas, Cuba, Abril 2005.
Rafael Bello, Métodos de Solución de Problemas de la Inteligencia Artificial, Universidad Central de Las Villas, 2007.
Ivan Bratko, Prolog programming for Artificial Intelligence. Addison-Wesley Publishing Company, Reading, Mass, 1986.
| Página siguiente |