Explorando Algoritmos de Búsqueda en Inteligencia Artificial

Tipos de Estrategias de Búsqueda Informada

El enfoque general que consideramos se llama Best-First Search, la cual es idéntica al costo uniforme.

Heurísticas: Greedy Best-First Search

Esta técnica intenta expandir el nodo más cercano al objetivo para llegar a una solución rápidamente. Por lo tanto, evalúa los nodos utilizando sólo la función heurística; es decir, f(n) = h(n).

Algoritmo A*

Evalúa los nodos combinando el costo para alcanzar el nodo (g(n)) y el costo estimado para llegar desde el nodo a la meta (h(n)):

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

Como g(n) indica el costo de la ruta desde el nodo de inicio al nodo n, y h(n) es el costo estimado del camino más barato de n al objetivo, entonces f(n) es el costo estimado de la solución más barata a través de n.

Por lo tanto, si estamos tratando de encontrar la solución más barata, una cosa razonable para probar primero es el nodo con el valor más bajo de g(n) + h(n).

El algoritmo es idéntico a la búsqueda de costo uniforme, excepto que A* usa g(n) + h(n) en lugar de g(n).

Siempre que la función heurística cumpla ciertas condiciones, la búsqueda A* es completa y óptima.

Algoritmos de Búsqueda Local

Existen problemas donde el camino es irrelevante. Los algoritmos de búsqueda local son útiles cuando el camino no es relevante, por ejemplo, en el problema de las 8 reinas.

Dada las 8 reinas en el tablero (una por columna), nuestra función objetivo puede ser el número de pares de reinas que se atacan entre ellas. Entonces queremos minimizar la función objetivo, ya que una solución posible será aquella que tenga h=0.

Hill Climbing

Elige el nodo vecino que aumenta/disminuye el valor de la función objetivo.

El algoritmo se detiene si no encuentra un vecino que mejore el resultado.

Simulated Annealing

Si el vecino mejora el resultado, entonces se acepta el vecino.

Si no, la aceptación dependerá de qué tanto no mejora la función y de la iteración en la que se encuentra el algoritmo (valor de la temperatura).

Mientras mayor es la temperatura, más se acepta un resultado no mejor.

Algoritmos Genéticos

Estos algoritmos están inspirados en la reproducción sexual.

• Se tiene una población inicial de n individuos (nodos).
• Cada uno de ellos tiene asociado una función de fitness (objetivo).
• Se usa un mecanismo de selección (ruleta), donde el individuo que tenga mejor función de fitness tiene mayor probabilidad de ser seleccionado.

Podemos aplicar 2 clases de operadores sobre la población y así obtener la siguiente población:

• Mutación: algún elemento de la representación cambia aleatoriamente de valor.
• Cruzamiento: se eligen dos individuos, un punto de corte y se mezcla la primera parte del primer individuo con la segunda parte del segundo individuo.

Proceso general:

1. Iniciar aleatoriamente la población.
2. Calcular el fitness de la población.
3. Hasta convergencia, repetir:
   1. Seleccionar padres desde la población.
   2. Cruzarlos y generar la nueva población.
   3. Mutar la población.
   4. Calcular fitness para la nueva población.
4. Elitismo: Conservar el (los) mejor(es) de la población anterior.

Preguntas Frecuentes

1. Diferencie entre completitud y optimalidad.

Completitud se refiere a si el algoritmo es capaz de encontrar una solución, mientras que optimalidad se refiere a si el algoritmo es capaz de encontrar la solución óptima.

2. ¿Cómo se mide la complejidad del tiempo?

El tiempo a menudo se mide en términos del número de nodos generados durante la búsqueda.

3. Cuando los costos son iguales, ¿qué algoritmos de búsqueda son equivalentes?

Búsqueda de costo uniforme y búsqueda a lo ancho. Esto se debe a que, en ambos casos, los algoritmos considerarán los caminos con el mismo costo y siempre expandirán los nodos en el orden en que se encuentran en el espacio de búsqueda.

4. ¿Cuándo se recomienda usar un algoritmo de búsqueda local?

Respuesta: Los algoritmos de búsqueda local son útiles cuando el camino no es relevante y el tamaño del espacio de búsqueda es grande.