Clase 10 — Estrategias Evolutivas y Preparación del Examen

Resumen Ejecutivo

Sesión en dos bloques. El primero cierra el tema de modelos de computación evolutiva con los algoritmos que extienden los AG a codificaciones de números reales: estrategias evolutivas \((1+1)\), \((\mu, \lambda)\) y \((\mu+\lambda)\), operador de mutación gaussiana y regla del 1/5 para equilibrar exploración/explotación. El segundo bloque es una sesión completa de preparación del examen: estructura del examen, consejos de estrategia y ejercicios resueltos de los cuatro tipos de preguntas que caen (complejidad, búsqueda exhaustiva, PSO y algoritmos genéticos).

Conceptos Clave

Algoritmos evolutivos: extensión de los AG que trabajan con codificación de números reales en lugar de binaria. Misma secuencia: inicialización → evaluación → cruce → mutación → selección. ⚠️ EXAMEN
Mutación gaussiana: el cambio aplicado a un gen real se extrae de una distribución normal \(\mathcal{N}(0, \sigma)\); la mayoría de cambios serán pequeños (explotación), con posibilidad de saltos grandes (exploración). ⚠️ EXAMEN
Estrategia \((1+1)\): un único padre genera un único hijo; compiten entre sí y pasa el de mejor fitness. No es poblacional. ⚠️ EXAMEN
Estrategia \((\mu, \lambda)\): \(\mu\) padres generan \(\lambda\) hijos; los padres se descartan y de los hijos se seleccionan los \(\mu\) mejores para la siguiente generación. ⚠️ EXAMEN
Estrategia \((\mu + \lambda)\): igual que la anterior pero padres e hijos compiten juntos; pasan los \(\mu\) mejores del pool combinado. Mayor estabilidad que \((\mu, \lambda)\). ⚠️ EXAMEN
Regla del 1/5: heurística para ajustar \(\sigma\) dinámicamente. Si la proporción de mutaciones exitosas \(p_s > 0.2\), se multiplica \(\sigma\) (más exploración); si \(p_s < 0.2\), se divide \(\sigma\) (más explotación). ⚠️ EXAMEN
Cruce por promedio: en codificación real, el cruce más habitual es obtener el hijo como la media aritmética de los dos padres.
Notación de estrategias: el operador + indica que padres e hijos compiten; la , (coma) indica que los padres se desechan y solo sobreviven hijos.

Desarrollo del Temario

1. Algoritmos Evolutivos: relación con los AG

Los algoritmos evolutivos no son un concepto radicalmente nuevo: comparten la misma estructura que los AG clásicos (población, selección, cruce, mutación). La diferencia clave es la codificación:

AG clásico	Algoritmo evolutivo
Cromosomas binarios (0/1)	Vectores de números reales
Mutación: flip de bit	Mutación: suma de \(\mathcal{N}(0,\sigma)\)
Cruce: intercambio de segmentos	Cruce: promedio aritmético

El término "evolutivo" hace referencia al énfasis en la mejora del operador de mutación y del cruce, no a un cambio de paradigma.

2. Mutación con distribución normal

El nuevo valor de un gen se calcula como:

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

Donde \(\sigma\) es la desviación estándar (parámetro libre). La distribución normal garantiza que:

El 68 % de los cambios cae en \([-\sigma, +\sigma]\) → cambios pequeños, explotación.
Solo un 4.6 % supera \(2\sigma\) → saltos ocasionales, exploración.
El tamaño de los cambios es simétrico alrededor de 0 (ni sesgado hacia positivos ni negativos).

Si \(\sigma\) es pequeño: búsqueda local intensa (explotación). Si \(\sigma\) es grande: saltos amplios por el espacio (exploración).

3. Estrategias evolutivas

3.1 Estrategia \((1+1)\)

Población: un único individuo (padre).
Descendencia: un único hijo por mutación gaussiana.
Selección: se evalúan padre e hijo; pasa el que tenga mejor fitness.
Particularidad: no es estrictamente poblacional (solo hay un individuo), pero entra dentro del marco de los evolutivos.
Comportamiento: alta convergencia local si \(\sigma\) es pequeño; riesgo de estancamiento sin diversidad.

3.2 Estrategia \((\mu, \lambda)\) — coma

\(\mu\): tamaño de la población de padres.
\(\lambda\): número de hijos generados (\(\lambda > \mu\)).
Selección: los padres se descartan completamente; de los \(\lambda\) hijos se seleccionan los \(\mu\) mejores para la siguiente generación.
Implicación: puede perder calidad si los hijos son peores que los padres (menor estabilidad). Favorece la exploración al renovar completamente la población.

3.3 Estrategia \((\mu + \lambda)\) — más

Igual que la anterior salvo que padres e hijos compiten juntos.
Se seleccionan los \(\mu\) mejores del pool \(\{\)padres \(\cup\) hijos\(\}\).
Mayor estabilidad y explotación porque los padres buenos nunca se pierden.
El operador + es la señal de que hay competencia entre generaciones.

graph TD
    A["Padres (μ)"] --> B["Operadores de cruce y mutación"]
    B --> C["Hijos (λ)"]
    C --> D{Estrategia}
    D -- "coma (μ,λ)" --> E["Seleccionar μ mejores\nsolo de hijos"]
    D -- "más (μ+λ)" --> F["Seleccionar μ mejores\nde padres ∪ hijos"]
    E --> G[Siguiente generación]
    F --> G

4. Cruce en números reales

El operador de cruce más usado en algoritmos evolutivos es el cruce por promedio:

\[\text{hijo} = \frac{\text{padre}_1 + \text{padre}_2}{2}\]

Para cromosomas de varias dimensiones, el promedio se aplica componente a componente. Es análogo al cruce de dos puntos en binario pero produce un hijo que siempre cae entre los dos padres.

5. Regla del 1/5 (ajuste dinámico de \(\sigma\))

⚠️ EXAMEN

Heurística para mantener el equilibrio exploración/explotación ajustando \(\sigma\) en cada iteración. La idea es que la proporción óptima de mutaciones exitosas es \(p_s = 0.2\) (un quinto):

\[\sigma_{t+1} = \begin{cases} \sigma_t / c & \text{si } p_s > 0{,}2 \quad \text{(reducir: más explotación)} \\ \sigma_t \cdot c & \text{si } p_s < 0{,}2 \quad \text{(aumentar: más exploración)} \\ \sigma_t & \text{si } p_s = 0{,}2 \end{cases}\]

Donde \(c \in [0.8, 1)\) es una constante (típicamente entre 0.8 y 1). Cuando hay más del 20 % de éxitos, el algoritmo está explotando bien y conviene reducir \(\sigma\). Cuando hay menos, conviene aumentar \(\sigma\) para buscar más ampliamente.

6. Estructura del Examen (información del profesor)

⚠️ EXAMEN

El examen es a mano (no se permite MATLAB por el problema de Copilot). Duración: 2 horas. Cuatro preguntas, todas con el mismo peso (2.5 puntos cada una).

Pregunta	Tema
1	Complejidad computacional: contar operaciones de un polinomio (método directo y método de Horner).
2	Búsqueda exhaustiva: generar combinaciones, aplicar restricciones y elegir la mejor.
3	PSO (nube de partículas): iterar las ecuaciones de velocidad y posición para 2 partículas y 2 iteraciones.
4	Algoritmos genéticos: selección por torneo, cruce simple y mutación con tabla de probabilidades.

Estrategia recomendada por el profesor: contestar primero las preguntas más cortas (complejidad y búsqueda exhaustiva aseguran el 5); luego PSO y AG, que son más largos pero mecánicos.

7. Ejercicios de preparación resueltos en clase

7.1 Complejidad: contar operaciones

Ejemplo: Polinomio \(p(x) = a_n x^n + \ldots + a_1 x + a_0\).

Método directo: contar multiplicaciones para calcular \(x^k\): para \(x^8\) se necesitan 7 multiplicaciones (\(x \cdot x \cdot \ldots\)). ⚠️ EXAMEN

Método de Horner (factorización): reescribir el polinomio de forma anidada:

\[p(x) = (\ldots((a_n \cdot x + a_{n-1}) \cdot x + a_{n-2}) \cdot x + \ldots) \cdot x + a_0\]

Cada paréntesis requiere 1 multiplicación y 1 suma, reduciendo drásticamente el número de operaciones. Importante: Horner no siempre reduce operaciones — verificar el cálculo. ⚠️ EXAMEN

7.2 Búsqueda exhaustiva: 3 edificios en 5 fincas

Enunciado del ejemplo: se desean construir 3 edificios en 5 fincas. Las fincas 3 y 5 no pueden tener edificios simultáneamente. Minimizar el coste.

Total de combinaciones: \(\binom{5}{3} = 10\).
Paso 1: listar las 10 combinaciones posibles.
Paso 2: eliminar las que violan la restricción (contienen fincas 3 y 5 a la vez).
Paso 3: calcular el coste de las combinaciones válidas y seleccionar la mínima.

Clave para el examen: escribir la fórmula combinatoria, listar las soluciones, marcar las inválidas, calcular los costes y declarar la óptima. No escribir "5 sobre 3" — escribir "combinaciones de 5 sobre 3". ⚠️ EXAMEN

7.3 PSO: iteración manual

Ecuaciones del PSO: ⚠️ EXAMEN

\[v_{i,t+1} = w \cdot v_{i,t} + c_1 r_1 (pbest_i - x_{i,t}) + c_2 r_2 (gbest - x_{i,t})\]

\[x_{i,t+1} = x_{i,t} + v_{i,t+1}\]

Pasos para el examen:

Evaluar el fitness de cada partícula en la posición inicial.
Registrar \(pbest\) (mejor posición personal) y \(gbest\) (mejor global).
Calcular la nueva velocidad con la fórmula anterior.
Calcular la nueva posición.
Repetir para cada iteración solicitada.

Truco: si la velocidad inicial es \((0, 0)\) y la posición inicial es \(pbest\), muchos términos se anulan — detectarlo ahorra tiempo en el examen.

7.4 Algoritmos genéticos: selección, cruce y mutación

Selección por torneo: se comparan parejas; pasa el individuo con mayor fitness. En caso de empate, elegir cualquiera (indicarlo explícitamente). ⚠️ EXAMEN

Cruce simple (un punto): dado el punto de cruce \(k\), el hijo toma los primeros \(k\) genes del padre 1 y el resto del padre 2. El cruce siempre genera dos hijos.

Mutación con tabla de probabilidades: se da una tabla de valores aleatorios por gen. Si el valor supera el umbral (normalmente \(p_m = 0.2\)), el bit muta (0→1 o 1→0). ⚠️ EXAMEN

Pasos completos:

Evaluar fitness de todos los individuos.
Selección por torneo → obtener padres.
Cruce → obtener hijos.
Mutación según tabla → hijos mutados.
Evaluar fitness de los hijos mutados.
Reportar la nueva generación y el mejor individuo.

Preguntas de Autoevaluación

¿Cuál es la diferencia principal entre un algoritmo genético clásico y un algoritmo evolutivo? ¿Qué cambia en la codificación?
Explica la mutación gaussiana. ¿Qué efecto tiene aumentar o reducir \(\sigma\)?
Define las estrategias \((1+1)\), \((\mu,\lambda)\) y \((\mu+\lambda)\). ¿Qué significa el operador + frente a la , en la notación?
En la estrategia \((\mu,\lambda)\), ¿qué ocurre con los padres tras generar los hijos? ¿Y en \((\mu+\lambda)\)?
¿Cuál estrategia tiene mayor estabilidad y por qué?
Explica la regla del 1/5. ¿Qué indica que \(p_s > 0.2\)? ¿Qué ajuste se hace a \(\sigma\)?
¿Cómo funciona el cruce por promedio en codificación real? ¿En qué se diferencia del cruce de un punto binario?
El examen tiene 4 preguntas de igual valor. ¿Qué estrategia de tiempo recomienda el profesor?
Dado un polinomio de grado 8, ¿cuántas multiplicaciones requiere el método directo? ¿Y con Horner?
En PSO, si la velocidad inicial es \((0,0)\) y la posición es igual al \(pbest\) personal, ¿cómo simplifica eso el cálculo de la primera iteración?
En un AG con 6 individuos y selección por torneo 2-a-2, ¿cómo se organizan las parejas? ¿Qué pasa en caso de empate?
Dada la tabla de mutación con umbral 0.2, identifica qué genes mutan si los valores aleatorios son: [0.15, 0.35, 0.28, 0.09, 0.41, 0.18].