033 — Algoritmos genéticos

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

Parte: 02 — IA probabilística, evolutiva y de decisión
Nivel: intermedio · Horas estimadas: 6
Laboratorio: optimization · Estado: EXECUTABLE_CORE

🎯 Propósito

Comprender algoritmos genéticos 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 algoritmos genéticos usando los conceptos población, mutación, cruce, selección.
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

población, mutación, cruce, selección

🗺️ Ubicación en el mapa de la IA

Hasta ahora la parte 02 razona y decide con modelos explícitos; los algoritmos genéticos (Holland, 1975; Goldberg, 1989) atacan otro problema: optimizar funciones sin gradiente, sin convexidad y sin forma cerrada, imitando la evolución darwiniana. Pertenecen a la familia de metaheurísticas poblacionales junto con PSO y ACO (034). En la práctica moderna optimizan hiperparámetros, arquitecturas neuronales (neuroevolución), planificación y diseño — y son el recordatorio histórico de que la búsqueda estocástica compite con el cálculo cuando el paisaje es hostil.

📖 Fundamentos

🧬 Metáfora y componentes

• Individuo (cromosoma): candidato a solución, codificado (bits, enteros, reales, permutaciones).
• Población: multiconjunto de N individuos; la diversidad es su capital.
• Fitness f(x): función a maximizar; única señal que guía la búsqueda.
• Selección: los más aptos se reproducen con mayor probabilidad — explota.
• Cruce (crossover): combina dos padres — recombina bloques buenos.
• Mutación: perturbación aleatoria pequeña — explora y evita estancamiento.
• Elitismo: copiar los k mejores intactos garantiza no perder lo logrado.

⚙️ Bucle canónico

P ← población inicial aleatoria (tamaño N), evaluar fitness
repetir hasta criterio de parada:
    E ← mejores k de P                       # elitismo
    repetir hasta llenar la nueva población:
        p₁, p₂ ← seleccionar(P)              # torneo o ruleta
        h₁, h₂ ← cruzar(p₁, p₂) con prob. pc # pc ≈ 0.6–0.9
        mutar(h₁), mutar(h₂) con prob. pm    # pm ≈ 1/longitud
    P ← E ∪ hijos; evaluar fitness
devolver el mejor individuo visto

Selección por torneo (tamaño t): elegir t individuos al azar y quedarse con el mejor; t controla la presión selectiva (t grande → convergencia rápida y pérdida de diversidad). Ruleta: probabilidad proporcional al fitness; sensible a la escala (un superindividuo temprano puede monopolizar).

Cruce de un punto en cadenas: cortar ambos padres en una posición y recombinar. Para permutaciones (TSP) el cruce debe preservar la validez (OX, PMX); para reales se usa cruce aritmético o SBX y mutación gaussiana.

📈 Por qué funciona (y cuándo no)

La intuición clásica es el teorema de esquemas de Holland: los patrones cortos, de bajo orden y fitness sobre el promedio ("bloques constructivos") reciben exponencialmente más copias en generaciones sucesivas. Es una intuición útil más que una garantía: el teorema tiene supuestos fuertes y no asegura convergencia al óptimo global. El teorema No Free Lunch (Wolpert & Macready, 1997) añade la advertencia definitiva: promediado sobre todos los problemas posibles, ningún optimizador supera a otro — un GA solo gana donde la estructura del problema casa con sus operadores.

🎛️ El equilibrio exploración/explotación

Todo el diseño (N, pc, pm, presión selectiva, elitismo) regula un único trade-off: explotar las buenas regiones halladas vs. seguir explorando. Convergencia prematura (población clonada en un óptimo local) es el modo de fallo dominante; sus antídotos: mutación suficiente, torneos pequeños, nichos o reinicios.

🧮 Ejemplo trabajado

OneMax: maximizar el número de unos en una cadena de 8 bits (óptimo = 8). Población N = 4, torneo de 2, cruce de un punto (punto 4), mutación de un bit, elitismo 1.

Generación 0                    fitness
A = 1 0 1 1 0 1 0 0               4
B = 0 1 1 0 1 0 1 0               4
C = 1 1 0 1 0 0 0 1               4
D = 0 0 0 1 0 1 0 0               2

Torneos: (A,D)→A  (B,C)→B  (C,D)→C  (A,B)→A (empate: primero)

Cruce A×B por el punto 4:
  A = 1011|0100, B = 0110|1010
  h₁ = 1011 1010 (f=5)   h₂ = 0110 0100 (f=3)
Cruce C×A por el punto 4:
  h₃ = 1101 0100 (f=4)   h₄ = 1011 0001 (f=4)

Mutación (1 bit al azar): h₂: bit 6 0→1 ⇒ 0110 0110 (f=4)

Generación 1 = {elite A(4), h₁(5), h₂(4), h₃(4)}
mejor: h₁ = 10111010 con f = 5  (mejora sobre 4)

Dos observaciones didácticas: (1) el cruce creó h₁ con 5 unos combinando la mitad izquierda rica de A con la derecha rica de B — el "bloque constructivo" en acción; (2) D, el peor, no sobrevivió a ningún torneo: presión selectiva. Repitiendo el proceso, OneMax converge al óptimo en pocas decenas de generaciones; con pm = 0 la población puede clonarse antes de llegar (convergencia prematura demostrable con este mismo ejemplo).

📊 Propiedades y comparación

flowchart TD
    I["Población inicial aleatoria"] --> Ev["Evaluar fitness"]
    Ev --> S["Selección por torneo<br/>(presión selectiva)"]
    S --> X["Cruce pc: recombinar<br/>bloques de los padres"]
    X --> M["Mutación pm: explorar<br/>vecindario"]
    M --> El["Elitismo: conservar<br/>los k mejores"]
    El --> Ev
    Ev --> C{"¿Criterio de parada?<br/>generaciones / estancamiento"}
    C -- sí --> R["Mejor individuo visto"]

⚠️ Errores conceptuales frecuentes

1. "El GA encuentra el óptimo global." No hay garantía práctica; devuelve el mejor visto. Se corre varias veces con semillas distintas y se reporta la distribución, no una corrida.
2. Confundir fitness alto en la población con progreso. Si toda la población es idéntica, el fitness medio es alto pero la búsqueda murió (convergencia prematura); hay que monitorear diversidad.
3. Mutación como protagonista. Con pm alto el GA degenera en búsqueda aleatoria; la mutación es un seguro contra pérdida de alelos, el cruce hace el trabajo de recombinación.
4. Codificación descuidada. Un cruce de un punto sobre una permutación produce hijos inválidos (ciudades repetidas en TSP); el operador debe respetar la semántica de la representación.
5. Comparar contra nada. Sin baseline (búsqueda aleatoria, hill climbing con reinicios) no se puede afirmar que el GA "funciona"; a menudo el baseline gana en problemas fáciles con presupuesto igual de evaluaciones.

🚀 Del aprendizaje a la operación

OneMax se evalúa en microsegundos; en problemas reales la evaluación del fitness domina el costo (simulaciones, entrenamientos), lo que impone paralelización, fitness aproximado (surrogates) y presupuestos estrictos de evaluaciones. Faltan además: sintonización de hiperparámetros del propio GA (meta-optimización), manejo de restricciones (penalización o reparación), y protocolo estadístico de comparación (múltiples semillas, tests no paramétricos) antes de reclamar superioridad sobre alternativas.

🧪 Laboratorio

python lab.py

El laboratorio llama a ai_evolution.labs.run_lab("optimization"). 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

• Holland, J. H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press (reed. MIT Press, 1992). — uso: desarrollo extendido del tema
• Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley. — uso: desarrollo extendido del tema
• Wolpert, D. H. & Macready, W. G. (1997). "No Free Lunch Theorems for Optimization". IEEE Trans. Evolutionary Computation, 1(1), 67-82. https://doi.org/10.1109/4235.585893 — uso: fuente primaria del mecanismo estudiado
• Eiben, A. E. & Smith, J. E. (2015). Introduction to Evolutionary Computing, 2.ª ed. Springer. https://doi.org/10.1007/978-3-662-44874-8 — uso: fuente primaria del mecanismo estudiado
• Russell, S. & Norvig, P. (2020). AIMA, 4.ª ed., cap. 4.1 (búsqueda local y evolutiva). https://aima.cs.berkeley.edu/ — uso: desarrollo extendido del tema

📜 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

032 — Lógica difusa y control aproximado

➡️ Siguiente clase

034 — Optimización por enjambre y colonia

📝 Evaluación completa

❓ Preguntas

1. Define algoritmos genéticos sin usar una marca o framework como definición.
2. Explica la relación entre población, mutación, cruce, selección.
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.