Fundamentos de Inteligencia Artificial: Algoritmos de Búsqueda y Optimización

1. Introducción a la Inteligencia Artificial

Definición: Desarrollo y utilización de ordenadores con los que se intenta reproducir los procesos de la inteligencia humana.

Objetivos

• Producir sistemas capaces de adoptar comportamientos que, realizados por personas, calificaríamos de inteligentes.
• Estudiar cómo hacer que las computadoras realicen tareas que, de momento, ejecutan mejor las personas.

Objeciones comunes

• Falta de creatividad (ej. Mozart).
• No computabilidad de los procesos del pensamiento.

2. Estrategias de Búsqueda

Un heurístico se utiliza para determinar el camino más corto a la solución de un problema, evitando explorar todo el espectro de soluciones y aumentando la eficiencia de los algoritmos. Un algoritmo es completo si garantiza obtener una solución si existe, y es óptimo si encuentra la solución de menor coste.

Algoritmos de búsqueda no informada

• Primero en profundidad (Depth-First): Se expande el nodo más profundo de la frontera. Utiliza una cola LIFO. Es completo, pero no óptimo. Complejidad temporal: O(b^m), espacial: O(bm).
• Primero en anchura (Breadth-First): Se expande el nodo menos profundo de los inexplorados. Utiliza una cola FIFO. Es óptimo (si los costes de los pasos son iguales) y completo. Complejidad: O(b^d).
• Bidireccional: Realiza dos búsquedas simultáneas, una desde el inicio y otra desde el final, deteniéndose cuando se encuentran.
• Coste uniforme: Extensión de la búsqueda en anchura. Expande el nodo con el camino de menor coste (función g) mediante una cola de prioridad. Es completo (si costes > 0) y óptimo.

Algoritmos avanzados y locales

• A*: Especialización de best-first que utiliza una función de evaluación f(n) = g(n) + h(n) para estimar el coste total. Es eficiente, aunque su complejidad puede limitar su uso para soluciones óptimas.
• Backtracking: Variante de la búsqueda en profundidad donde solo se expande un sucesor. Memoria: O(m).
• Búsqueda local: Operan con un solo estado y lo mejoran iterativamente.
  • Hill Climbing (Greedy local search): Busca el pico más alto sin mantener un árbol de búsqueda. Problemas: máximos locales, crestas y planicies.
  • Simulated Annealing: Permite movimientos hacia estados de menor calidad para escapar de máximos locales, reduciendo la probabilidad de estos movimientos con el tiempo.

3. Algoritmos Evolutivos y Probabilísticos

• Algoritmos Genéticos: Parten de un conjunto de soluciones candidatas (fenotipos) con propiedades (cromosomas o genotipos) que mutan y se combinan a través de generaciones. La función fitness mide la calidad de cada solución.
• EDAs (Estimation of Distribution Algorithms): Búsquedas heurísticas que utilizan funciones de probabilidad en lugar de operadores genéticos.
  • UMDA (Univariate Marginal Distribution Algorithm): Analiza la proporción de aparición de componentes en la población seleccionada, asumiendo codificación binaria.