016 — Diseño y validación de heurísticas

← Clase anterior · Índice de la parte · Clase siguiente →

Parte: 01 — IA simbólica, búsqueda, lógica y planificación
Nivel: fundamentos · Horas estimadas: 4
Laboratorio: search · Estado: EXECUTABLE_CORE

🎯 Propósito

Comprender diseño y validación de heurísticas dentro de la evolución de la inteligencia artificial, implementar un experimento mínimo verificable y distinguir qué parte constituye evidencia frente a una afirmación todavía no comprobada.

📚 Resultados de aprendizaje

Al finalizar podrás:

1. Explicar diseño y validación de heurísticas usando los conceptos admisibilidad, consistencia, dominancia, costo.
2. Ejecutar el laboratorio con una semilla explícita y revisar su contrato JSON.
3. Identificar al menos un supuesto, una limitación y un riesgo de aplicación.
4. Comparar el enfoque con la etapa anterior de la ruta de aprendizaje.
5. Producir una evidencia reproducible y una conclusión que no exceda los datos.

🧩 Conceptos centrales

admisibilidad, consistencia, dominancia, costo

🗺️ Ubicación en el mapa de la IA

Las garantías de A (clase 015) valen lo que valga su heurística: esta clase estudia qué hace a una heurística correcta (admisibilidad, consistencia) y buena (dominancia, factor de ramificación efectivo). La idea central — derivar heurísticas resolviendo problemas relajados* — reaparece en toda la IA: las heurísticas de los planificadores PDDL (clase 023) son relajaciones automáticas, y las bases de datos de patrones anticipan la idea de precomputar conocimiento que luego guía la búsqueda, como hoy hacen las funciones de valor aprendidas en RL.

📖 Fundamentos

✅ Admisibilidad

Una heurística h es admisible si nunca sobreestima el costo real mínimo al objetivo:

∀n:  0 ≤ h(n) ≤ h*(n)        donde h*(n) = costo óptimo real de n al objetivo

Es una garantía de optimismo: la solución puede ser peor de lo que h promete, nunca mejor. Con h admisible, A en árbol devuelve siempre una solución óptima: si devolviera una subóptima de costo C > C, algún nodo del camino óptimo tendría f(n) = g(n) + h(n) ≤ C* < C y habría sido expandido antes.

🔗 Consistencia (monotonía)

h es consistente si cumple la desigualdad triangular con cada arista:

∀n, a, n' sucesor:  h(n) ≤ c(n, a, n') + h(n')      y  h(objetivo) = 0

Consistencia ⇒ admisibilidad (se prueba por inducción sobre la longitud del camino al objetivo), pero no al revés. Su consecuencia operativa: los valores f son no decrecientes a lo largo de cualquier camino, así que la primera vez que A en grafo expande un estado ya lo hace con su g óptimo y nunca hay que reabrir nodos*. Casi todas las heurísticas naturales (distancias geométricas, relajaciones) son consistentes; construir una admisible-pero-inconsistente requiere cierto esfuerzo deliberado.

🏆 Dominancia y calidad

Si h2(n) ≥ h1(n) para todo n (ambas admisibles), h2 domina a h1 y A con h2 nunca expande más nodos que con h1 (salvo empates en f = C). Regla práctica: entre heurísticas admisibles, gana la más grande. De hecho, el máximo de varias admisibles es admisible y las domina a todas:

h(n) = max(h1(n), h2(n), ..., hk(n))

La calidad se mide empíricamente con el factor de ramificación efectivo b: si A expandió N nodos para una solución a profundidad d, b es la solución de N + 1 = 1 + b* + (b*)² + ... + (b*)^d. Una heurística buena acerca b a 1. Para el 8-puzzle a profundidad d = 12 (datos de AIMA): IDS expande 3 644 035 nodos (b ≈ 2,78), A con fichas mal colocadas 227 (b ≈ 1,42), A con Manhattan 73 (b* ≈ 1,24).

🛠️ De dónde salen: problemas relajados

Método sistemático: eliminar restricciones del problema. El costo óptimo del problema relajado es una cota inferior del original (todo camino del original sigue siendo válido en el relajado), luego es admisible; y como se calcula sobre el problema relajado resuelto exactamente, suele ser consistente.

• 8-puzzle, regla original: "una ficha se mueve a la casilla adyacente vacía".
• Relajación 1: "una ficha se mueve a cualquier casilla" → h1 = número de fichas mal colocadas.
• Relajación 2: "una ficha se mueve a una casilla adyacente (aunque esté ocupada)" → h2 = suma de distancias Manhattan. h2 domina a h1.
• Rutas en mapa: relajar "moverse por carreteras" a "volar en línea recta" → distancia euclídea.

Otras dos fuentes: bases de datos de patrones (resolver exhaustivamente subproblemas — p. ej. solo las fichas 1-4 — y tabular los costos exactos, Culberson y Schaeffer 1998) y aprendizaje de h a partir de instancias resueltas (sin garantía de admisibilidad, salvo que se acote).

⚖️ El trade-off real

Una heurística más informada expande menos nodos pero cuesta más por nodo. El tiempo total es ≈ nodos_expandidos × (costo_generación + costo_h). Una h perfecta (h = h) reduce la búsqueda a seguir el camino óptimo, pero calcular h equivale a resolver el problema. El punto óptimo está en heurísticas baratas y razonablemente informadas — o precomputadas, pagando memoria en vez de tiempo.

🧮 Ejemplo trabajado

Estado del 8-puzzle (0 = hueco) y objetivo estándar:

estado s:  7 2 4        objetivo:  0 1 2
           5 0 6                   3 4 5
           8 3 1                   6 7 8

h1 (fichas mal colocadas): comparando casilla a casilla, las 8 fichas están fuera de su lugar → h1(s) = 8.

h2 (Manhattan): distancia |Δfila| + |Δcolumna| de cada ficha a su posición objetivo:

h2(s) = 3+1+2+1+2+3+2+2 = 16. El costo real es h*(s) = 26 (instancia usada en AIMA): ambas son cotas inferiores (8 ≤ 16 ≤ 26 ✔) y h2 domina a h1, así que A con h2 expandirá menos nodos. Nótese cuánta información pierde h1: sabe que las fichas están mal, no cuán lejos*.

📊 Propiedades y comparación

flowchart TD
    P["Problema original<br/>(restricciones completas)"] -->|"eliminar restricción R1"| R1["Relajación 1<br/>→ h1"]
    P -->|"eliminar restricción R2"| R2["Relajación 2<br/>→ h2"]
    P -->|"resolver subproblema<br/>exhaustivamente"| PDB["Base de patrones<br/>→ h3"]
    R1 --> M["h = max(h1, h2, h3)<br/>admisible y dominante"]
    R2 --> M
    PDB --> M
    M --> A["A* / IDA*"]
    A --> V["Validación empírica:<br/>nodos expandidos, b*,<br/>tiempo total de reloj"]
    V -->|"h demasiado cara<br/>o poco informada"| P

⚠️ Errores conceptuales frecuentes

1. "Si h es admisible, A* es rápido." Admisibilidad garantiza optimalidad del resultado, no eficiencia: h = 0 es admisible y da UCS. La velocidad depende de cuán cerca esté h de h*.
2. Confundir admisible con consistente. Toda consistente es admisible; lo inverso es falso. Con admisible-no-consistente, A* en grafo debe permitir reabrir nodos o pierde optimalidad.
3. Sumar heurísticas admisibles y asumir que la suma es admisible. En general sobreestima (cuenta los mismos movimientos dos veces). Solo es válido si son aditivas/disjuntas (p. ej. bases de patrones disjuntas, donde cada movimiento se acredita a un solo patrón). La combinación siempre segura es max.
4. Escalar la heurística "para que busque más rápido" y esperar optimalidad. w·h con w > 1 (weighted A) puede sobreestimar: gana velocidad y pierde la garantía, acotando el resultado por w·C. Es un trade-off legítimo, pero hay que declararlo.
5. Validar solo con una instancia. La calidad de una heurística se reporta sobre un conjunto de instancias (media de nodos expandidos, b*, tiempo total), no sobre el caso donde funcionó bien.

🚀 Del aprendizaje a la operación

En producción, la heurística se elige con benchmarks del dominio real, no con intuición: hay que medir nodos expandidos, tiempo de reloj y memoria sobre cargas representativas, y repetir la medición cuando el dominio cambia (un mapa con obras rompe la calibración de una h aprendida). Las bases de patrones exigen decidir cuánta memoria dedicar al precómputo y regenerarla en cada cambio de dominio. Y si se usan heurísticas aprendidas sin garantía de admisibilidad, el sistema debe declarar que las soluciones pueden ser subóptimas y acotar empíricamente cuánto.

🧪 Laboratorio

python lab.py

El laboratorio llama a ai_evolution.labs.run_lab("search"). Esta decisión evita 183 implementaciones divergentes: cada clase tiene un entrypoint propio, pero los motores didácticos se prueban como una biblioteca común.

🔍 Evidencia esperada

• tipo de laboratorio y semilla;
• entradas o decisiones observables;
• resultado estructurado;
• lista evidence con hechos que pueden inspeccionarse;
• lista limitations que impide presentar la demo como producción.

📓 Notebooks

• 📓 notebook.ipynb: recorrido guiado con la materia resumida.
• ✍️ notebook_student.ipynb: ejercicios para resolver.
• ✅ notebook_solution.ipynb: solución de referencia explicada.

📝 Evaluación

Consulta assessment.md para preguntas y criterio de aceptación.

⚠️ Errores comunes

❓ Preguntas frecuentes

¿Debo usar una API comercial?
No. El núcleo funciona localmente. Las extensiones LIVE se documentan por separado.

¿El laboratorio representa una implementación industrial?
No por sí solo. Enseña el contrato y el patrón; producción exige integración, seguridad, observabilidad, pruebas y operación.

¿Dónde profundizo?
Revisa las especializaciones enlazadas en el README raíz y la ruta siguiente.

🔗 Referencias

• Russell, S. y Norvig, P. (2021). AIMA (4.ª ed.), §3.6 "Heuristic Functions". https://aima.cs.berkeley.edu/ — uso: desarrollo extendido del tema
• Pearl, J. (1984). Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley — el tratado clásico sobre heurísticas admisibles y su análisis.
• Culberson, J. C. y Schaeffer, J. (1998). "Pattern Databases". Computational Intelligence, 14(3). https://doi.org/10.1111/0824-7935.00065 — uso: fuente primaria del mecanismo estudiado
• Felner, A., Korf, R. E. y Hanan, S. (2004). "Additive Pattern Database Heuristics". JAIR, 22. https://doi.org/10.1613/jair.1480 — uso: fuente primaria del mecanismo estudiado

📜 Papers que fundamentan esta clase

Bloque generado por python scripts/link_papers_to_classes.py. La fuente es papers/catalog/papers.json.

Cada ficha explica el problema anterior, la matemática mínima, los límites y los errores de atribución más frecuentes. Para leerlas con método: cómo leer un paper de IA · anexos matemáticos.

📚 Bibliografía de apoyo

Bloque generado por python scripts/link_sources_to_classes.py. Cada obra lleva su localizador verificado en sources/bibliography.json.

Los papers dicen de dónde salió el mecanismo. Estas obras lo desarrollan con el espacio que una clase no tiene: teoría completa, demostraciones y ejercicios.

⬅️ Clase anterior

015 — Costo uniforme, búsqueda voraz y A*

➡️ Siguiente clase

017 — Juegos: minimax y poda alfa-beta

📝 Evaluación completa

❓ Preguntas

1. Define diseño y validación de heurísticas sin usar una marca o framework como definición.
2. Explica la relación entre admisibilidad, consistencia, dominancia, costo.
3. Ejecuta lab.py dos veces con la misma semilla. ¿Qué debe conservarse?
4. Identifica una afirmación permitida y una afirmación exagerada sobre el resultado.
5. Propón una prueba negativa o un caso límite.

🏆 Reto verificable

Amplía el resultado del laboratorio con una clave student_extension que incluya:

• el supuesto que estás probando;
• una medición o comprobación;
• la conclusión;
• una limitación.

✅ Criterio de aceptación

• [ ] lab.py termina con código 0.
• [ ] El resultado contiene kind, seed, evidence y limitations.
• [ ] La extensión no modifica el comportamiento de otras clases.
• [ ] La interpretación referencia datos impresos por el laboratorio.
• [ ] Se declara al menos un riesgo o condición de no uso.