Skip to content

Clase 11 — Programación Evolutiva, Evolución Diferencial y Estimación de Distribuciones

Resumen Ejecutivo

Continuación del bloque de modelos de computación evolutiva. Se presentan tres nuevas ramificaciones que comparten la base de los AG pero introducen mecanismos propios: programación evolutiva (mutación de especies con torneos estocásticos, sin cruce explícito), evolución diferencial (nueva fórmula de mutación basada en la diferencia vectorial entre individuos) y estimación de distribuciones (generación de la siguiente población a partir de un modelo probabilístico). Se menciona también la programación genética (evolución de estructuras de árbol) aunque no entra en el examen.

Conceptos Clave

  • Programación evolutiva: variante donde la unidad de evolución es la especie, no el individuo. Elimina el cruce y lo sustituye por torneos estocásticos para la selección. ⚠️ EXAMEN
  • Torneo estocástico: mecanismo de selección con doble aleatoriedad: número de enfrentamientos aleatorio y rivales elegidos aleatoriamente. Mide victorias acumuladas. ⚠️ EXAMEN
  • Evolución diferencial: nuevo operador de mutación que usa la diferencia entre vectores de individuos de la población en lugar de la distribución normal. Trabaja con números reales. ⚠️ EXAMEN
  • Vector base, vector objetivo y vectores de diferencia: los tres elementos que intervienen en la mutación diferencial.
  • Factor de escala \(F\): parámetro de la evolución diferencial que controla la amplitud de la perturbación. Análogo a \(\sigma\) en la mutación gaussiana.
  • Estimación de distribuciones (EDA): en vez de cruzar y mutar individuos directamente, se estima un modelo probabilístico de la distribución de los mejores individuos y se muestrea para generar la siguiente generación.
  • Programación genética: evolución de estructuras de árbol o grafo (funciones, programas). No entra en el examen pero se recomienda ver el video del foro.
  • Estocasticidad: característica que distingue los algoritmos evolutivos de los genéticos clásicos: múltiples capas de probabilidad (en mutación, selección, emparejamiento).

Desarrollo del Temario

1. Recapitulación: estrategias evolutivas (clase anterior)

Las estrategias vistas en la clase 10 — \((1+1)\), \((\mu,\lambda)\), \((\mu+\lambda)\) — diferenciaban en:

  • Si los padres se desechan (,) o compiten con los hijos (+).
  • Si la población es de un individuo o de \(\mu\) individuos.
  • Mutación siempre gaussiana; cruce por promedio.

Las clases que siguen profundizan en otras ramas que, en lugar de afinar el operador de mutación o selección dentro del mismo esquema, proponen cambios filosóficos en cómo se concibe la evolución.

2. Programación evolutiva

2.1 Concepto central

La programación evolutiva no trabaja con individuos de una población sino con especies. El cambio filosófico respecto a los AG y a las estrategias evolutivas es:

AG / Estrategias evolutivas Programación evolutiva
Individuos / Poblaciones Especies
Cruce entre parejas Sin cruce (solo mutación)
Selección determinista o ruleta Torneo estocástico

Al mutar una especie en lugar de un individuo, la diversidad se introduce de forma más agresiva. El cruce desaparece porque "cruzar dos especies" no tiene sentido en la analogía biológica.

2.2 Algoritmo

Inicializar población de N individuos/especies
Mientras no se cumpla criterio de parada:
    Para cada individuo:
        Aplicar mutación gaussiana → generar hijo
    Unir padres e hijos en un pool (2N individuos)
    Aplicar torneo estocástico para seleccionar N supervivientes
    Los N ganadores son la nueva generación

Nota: padres e hijos compiten juntos (similar a \((\mu+\lambda)\)).

2.3 Torneo estocástico

⚠️ EXAMEN

En los AG clásicos los torneos son deterministas (2 contra 2, pasa el mejor). El torneo estocástico añade dos capas de aleatoriedad:

  1. Número de enfrentamientos: cada individuo participa en un número aleatorio de combates.
  2. Elección de rivales: los rivales se eligen aleatoriamente de la población.

El criterio de selección es el número de victorias acumuladas: pasan los individuos con más victorias.

graph LR
    A[Individuo X] --> B{¿Cuántos combates?\naleatorio}
    B --> C[Rivales elegidos aleatoriamente]
    C --> D[Contar victorias\n fitness X > fitness rival]
    D --> E[Ranking por victorias]
    E --> F[Seleccionar los N mejores]

El efecto es una mayor diversificación de la selección: no siempre ganan los mismos, porque la suerte del sorteo influye.

Caso de empate: si dos individuos tienen el mismo número de victorias, se puede elegir cualquiera de los dos (indicarlo en el examen).

3. Evolución diferencial

3.1 Motivación

En la mutación gaussiana el cambio \(\delta\) es independiente de la población:

\[x'_i = x_i + \mathcal{N}(0, \sigma)\]

En la evolución diferencial, el cambio se construye a partir de la diferencia entre dos individuos de la misma población, lo que hace que la escala de la mutación se adapte automáticamente a la dispersión de la población:

\[v = x_{base} + F \cdot (x_{r1} - x_{r2})\]

Donde: - \(x_{base}\): individuo base (el "padre" al que se le aplica la perturbación). - \(x_{r1}, x_{r2}\): dos individuos distintos elegidos aleatoriamente de la población. - \(F\): factor de escala (parámetro libre, típicamente \(F \in [0.4, 1]\)). - \(v\): vector mutante (donante).

3.2 Proceso completo de la evolución diferencial

Para cada individuo objetivo \(x_{objetivo}\) de la población:

  1. Mutación: seleccionar aleatoriamente \(x_{base}\), \(x_{r1}\), \(x_{r2}\) (distintos entre sí y del objetivo). Calcular el vector mutante \(v = x_{base} + F \cdot (x_{r1} - x_{r2})\).

  2. Recombinación (cruce binomial): generar un vector de prueba \(u\) mezclando el individuo objetivo \(x_{objetivo}\) y el vector mutante \(v\), componente a componente, con probabilidad de cruce \(CR\):

\[u_j = \begin{cases} v_j & \text{si } rand_j < CR \text{ o } j = j_{rand} \\ x_{objetivo,j} & \text{en caso contrario} \end{cases}\]
  1. Selección: comparar \(f(u)\) con \(f(x_{objetivo})\); pasa el mejor (selección uno-a-uno).

⚠️ EXAMEN — La clave del diferencial es que el vector de mutación \(F \cdot (x_{r1} - x_{r2})\) escala automáticamente con la dispersión de la población: cuando la población converge, las diferencias son pequeñas y el algoritmo se vuelve más preciso (explotación natural).

3.3 Ventaja frente a la mutación gaussiana

Mutación gaussiana Evolución diferencial
\(\sigma\) fijo (o ajustado por regla del 1/5) Escala automática con la dispersión de la población
Independiente de los demás individuos Usa información de 3 individuos de la población
Parámetro crítico: \(\sigma\) Parámetros: \(F\) y \(CR\)

3.4 Inicialización

Aunque la teoría prescribe inicialización aleatoria, en la práctica se combina con heurísticas greedy (avaricioso) u otras búsquedas locales para arrancar con una población de calidad. Esto reduce el tiempo de convergencia. ⚠️ EXAMEN (concepto general aplicable a todos los algoritmos evolutivos).

4. Estimación de distribuciones (EDA)

4.1 Idea fundamental

Los EDA no manipulan individuos directamente. En su lugar:

  1. Se seleccionan los mejores individuos de la generación actual.
  2. Se estima un modelo probabilístico (distribución) que captura las características de esos individuos.
  3. Se muestrea ese modelo para generar la nueva generación.

La siguiente generación no se obtiene cruzando ni mutando — se muestrea de la distribución estimada.

4.2 Ventajas e inconvenientes

Ventaja Inconveniente
Captura dependencias entre variables Coste computacional de estimar el modelo
No requiere ajuste de operadores de cruce/mutación El modelo puede ser inadecuado si la distribución es compleja
Convergencia rápida en algunos problemas Riesgo de convergencia prematura si el modelo es demasiado simple

5. Programación genética (mención)

La programación genética evoluciona estructuras de árbol o grafo en lugar de vectores. Es la misma idea que los AG pero los individuos son programas, expresiones matemáticas o grafos computacionales. El cruce intercambia subárboles; la mutación modifica nodos o subárboles.

No entra en el examen. Se recomienda el video del foro para entender la idea intuitiva.

6. Resumen comparativo de los modelos evolutivos

Modelo Cruce Mutación Selección Particularidad
Estrategias evolutivas \((1+1)\) No Gaussiana Mejor de padre/hijo Un solo individuo
Estrategias evolutivas \((\mu,\lambda)\) Promedio Gaussiana \(\mu\) mejores hijos Padres desechados
Estrategias evolutivas \((\mu+\lambda)\) Promedio Gaussiana \(\mu\) mejores (padres+hijos) Mayor estabilidad
Programación evolutiva No Gaussiana Torneo estocástico Opera sobre especies
Evolución diferencial Binomial (\(CR\)) Diferencia vectorial Uno-a-uno Escala automática
EDA No aplica No aplica Mejor subconjunto Muestreo de modelo

⚠️ EXAMEN — Conocer las diferencias entre modelos.

Preguntas de Autoevaluación

  1. ¿Cuál es la diferencia filosófica entre la programación evolutiva y las estrategias evolutivas? ¿Por qué la programación evolutiva no usa cruce?
  2. Explica el torneo estocástico. ¿Qué dos elementos se aleatorizan? ¿Cómo se decide quién pasa a la siguiente generación?
  3. En la evolución diferencial, ¿cómo se calcula el vector mutante \(v\)? ¿Qué papel tiene el factor de escala \(F\)?
  4. ¿Por qué la evolución diferencial tiene "escala automática"? ¿Qué ocurre con las diferencias \((x_{r1} - x_{r2})\) cuando la población converge?
  5. Compara la mutación gaussiana con la mutación por evolución diferencial: parámetros, ventajas e inconvenientes de cada una.
  6. ¿Qué es el cruce binomial en la evolución diferencial? ¿Qué parámetro controla la probabilidad de tomar del vector mutante?
  7. Describe el ciclo completo de un EDA. ¿Qué sustituye al operador de cruce y mutación?
  8. ¿Qué ventaja ofrece inicializar la población con una heurística greedy en lugar de aleatoriamente?
  9. En la notación \((\mu + \lambda)\), ¿qué diferencia al símbolo + del símbolo ,? ¿Cuál favorece la explotación?
  10. ¿Por qué la programación genética no entra en el examen? ¿Cuál es su idea central?