Búsqueda heurística (página 2)

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.