Clase 7 — Algoritmos Genéticos: estructura, codificación y operadores

Resumen Ejecutivo

Cambio de familia: dejamos los algoritmos de adaptación social (PSO, ABC, ACO) y entramos en los algoritmos genéticos (AG), una metaheurística bioinspirada en la evolución de Darwin. Aparecen en los años 70 y son discretos por naturaleza (codificación binaria), aunque hoy en día se aplican también a variables reales y de orden. Se estudian: la estructura canónica del AG (población → evaluación → selección → cruce → mutación → repetir), los dos modelos de generación (generacional vs estacionario), los criterios de parada, las tres codificaciones (binaria, real, de orden), y un catálogo de operadores de selección (torneo K, ranking, aleatoria, inversa, estocástica) y operadores de cruce (one-point, M-point, uniforme, real con media, de orden). Cierre con la actividad 2: comparativa AG vs ACO sobre dos datasets distintos según rama (ciencia de datos / informática). ⚠️ EXAMEN: estructura del algoritmo, mutación y por qué es necesaria, modelos generacional/estacionario, codificaciones, y al menos uno de cada tipo de operador (selección, cruce, mutación).

Conceptos Clave

Algoritmo Genético (AG): metaheurística poblacional bioinspirada en la evolución natural y la genética. Origen: años 70. ⚠️ EXAMEN
Función de aptitud (fitness): medida de "lo bueno" que es un individuo. En el algoritmo es la función objetivo (a veces transformada para que sea positiva y creciente). ⚠️ EXAMEN
Fenotipo: características observables del individuo. En el algoritmo, una solución candidata.
Genotipo / cromosoma: codificación de la solución. En el algoritmo, el vector que representa al individuo.
Generación: una iteración del algoritmo.
Mutación: cambio aleatorio puntual en un gen para evitar óptimos locales. ⚠️ EXAMEN: sin mutación el AG se estanca, en clase repetido tres veces.
Modelo generacional: padres reemplazados íntegramente por sus hijos en cada generación. ⚠️ EXAMEN
Modelo estacionario: un único hijo (o pocos) sustituye a un individuo de la población actual. Cambios graduales. ⚠️ EXAMEN
Criterios de parada: ⚠️ EXAMEN
Alcanzar el óptimo conocido (raro fuera de pruebas).
Convergencia / ausencia de mejora durante N iteraciones.
Número máximo de iteraciones.
Codificación binaria: vector de 0/1. Histórica, base de los AG. Permite representar casi cualquier número.
Codificación real: vector de números reales/flotantes. Adaptación moderna.
Codificación de orden: vector de permutaciones (típica del agente viajero, listas de tareas).
Selección por torneo K (tournament): se eligen K individuos al azar y se queda el mejor. K=2 es lo más común. ⚠️ EXAMEN
Selección por ranking: ordenar y asignar probabilidad según posición.
Selección aleatoria: todos con la misma probabilidad. Teórica, rompe la idea evolutiva.
Selección inversa: el primer cruce al azar; el segundo en subconjunto K aleatorio.
Selección estocástica (ruleta): probabilidad proporcional al fitness. ⚠️ EXAMEN
Cruce one-point (1 punto): un único punto de corte; intercambian colas. ⚠️ EXAMEN
Cruce M-point: M puntos de corte; alterna trozos del padre 1 y del padre 2.
Cruce uniforme: sin puntos de corte; máscara binaria gen a gen decide de qué padre se hereda. ⚠️ EXAMEN
Cruce con media (variables reales): hijo \(i = (\text{padre}_1[i] + \text{padre}_2[i]) / 2\) o cualquier combinación lineal.
Cruce de orden (OX): se preserva un segmento del padre 1; el resto se rellena en el orden del padre 2. ⚠️ EXAMEN — típico para agente viajero.

Desarrollo del Temario

1. De los algoritmos sociales a los algoritmos evolutivos

graph LR
    A[Bioinspirados] --> B[Adaptación social<br/>PSO, ACO, ABC]
    A --> C[Evolutivos<br/>Algoritmos genéticos]
    C --> D[Genéticos<br/>esta clase]

Los AG comparten estructura poblacional con PSO y ACO pero la metáfora cambia: ya no es comportamiento de enjambre (vecinos, comunicación local), sino selección natural y reproducción. La inspiración es directa: Darwin, los individuos más aptos sobreviven y se reproducen.

Por qué importa para informática: los AG no requieren derivadas, gradiente ni jacobiano. Funcionan con funciones objetivo no diferenciables, discretas, ruidosas, en cajas negras. Eso los hace especialmente útiles donde el cálculo clásico no entra. ⚠️ EXAMEN

2. Estructura canónica del algoritmo

flowchart LR
    A[Población inicial] --> B[Evaluar fitness]
    B --> C[Seleccionar padres]
    C --> D[Cruce → hijos]
    D --> E[Mutación]
    E --> F{¿Parada?}
    F -- no --> B
    F -- sí --> G[Mejor solución]

Cinco pasos:

Inicialización: generar una población al azar.
Evaluación: aplicar la función de aptitud a cada individuo.
Selección: elegir padres para reproducir (con sesgo hacia los mejores).
Cruce: combinar parejas de padres → hijos.
Mutación: alterar aleatoriamente algún gen con probabilidad muy baja.
Repetir hasta cumplir el criterio de parada.

⚠️ EXAMEN: el orden y los nombres de los pasos.

3. Por qué la mutación es imprescindible

Sin mutación el AG converge a óptimos locales y se estanca. La mutación es el equivalente al "salto" estocástico que permite escapar de la cuenca actual.

Frase de la profesora: "Sin esa mutación, así como los reyes, padres e hijos siempre están ahí: empezaba a haber problemas, no había mejora."

Probabilidades típicas: 0.001 – 0.05 por gen. Muy baja. Demasiada mutación rompe la convergencia.

4. Terminología biológica → algorítmica

Biología	Algoritmo
Aptitud	Función objetivo / fitness
Fenotipo	Solución candidata
Genotipo / cromosoma	Codificación de la solución (vector)
Gen	Componente del vector
Generación	Iteración
Mutación	Cambio aleatorio puntual
Población	Conjunto de soluciones
Selección natural	Operador de selección
Cruce / reproducción	Operador de cruce

5. Dos modelos de evolución poblacional

5.1 Modelo generacional ⚠️ EXAMEN

G_n  : [P1, P2, P3, P4]
       ↓ cruce + mutación
G_n+1: [H1, H2, H3, H4]   ← TODA la población se sustituye

Los padres mueren íntegramente; la nueva generación está formada solo por hijos. Cambios bruscos.

5.2 Modelo estacionario ⚠️ EXAMEN

G_n  : [P1, P2, P3, P4]
       padres P1+P2 → H1
       Comparas: ¿H1 es mejor que P_peor?
G_n+1: [P1, P2, P3, H1]   ← un único reemplazo

Solo se genera un hijo (o muy pocos) por generación. La nueva población mezcla padres e hijos. Cambios graduales.

"No piensen en biología; piensen en matemáticas." — la profesora justifica que la mezcla padre-hijo es un truco algorítmico, no una violación biológica.

6. Criterios de parada

Criterio	Cuándo usarlo
Alcanzar el óptimo	Solo en pruebas o comparativas con software de referencia.
Número máximo de iteraciones	Por seguridad, evita bucles infinitos. Típico: 1 000–10 000.
Convergencia / sin mejora durante N iteraciones	El más usado en la práctica con problemas reales. ⚠️ EXAMEN

7. Codificaciones

7.1 Binaria

Vector de 0/1. Histórica. Cada bit puede representar: - Presencia/ausencia de un atributo. - Bits que codifican un entero (representable casi cualquier número). - Bits que codifican un real con escalado.

Ejemplo (presencia de atributos): [1, 0, 1, 1, 0, 1, 0, 0].

7.2 Real

Vector de números reales / flotantes. Cada celda puede tomar cualquier valor en su dominio. Más natural para problemas de optimización continua.

Ejemplo: [5.6, 0.9, -2.1, 3.4].

Condición: la función objetivo debe poder evaluar la solución directamente desde estos valores.

7.3 De orden

Vector de permutaciones. Cada celda dice qué variable ocupa esa posición.

Ejemplo (agente viajero con 5 ciudades): [3, 1, 4, 5, 2] significa "visitar primero la 3, luego la 1, luego la 4...".

8. Operadores de selección

8.1 Selección por torneo K (más común) ⚠️ EXAMEN

1. Seleccionar K individuos al azar de la población.
2. Comparar sus fitness.
3. Devolver el mejor.

Con K=2 (binario): coger dos al azar y quedarse con el mejor. Se hace dos veces para conseguir la pareja.

Con K=3: coger tres al azar y quedarse con el mejor.

Empate: se elige cualquiera de los empatados.

Ventajas: muy fácil de implementar (un >=), converge bien.

8.2 Selección por ranking ⚠️ EXAMEN

Ordenar la población por fitness y asignar probabilidad según el ranking (no el valor absoluto del fitness). Suele aplicarse a subconjuntos / vecindades en lugar de a toda la población.

8.3 Selección aleatoria

Todos con la misma probabilidad. Rompe la idea evolutiva. Sirve para análisis teórico; en la práctica casi nunca se usa.

8.4 Selección inversa

Primer cruce al azar; segundo cruce en subconjunto K aleatorio. Mete aleatoriedad también en el K.

8.5 Selección estocástica (ruleta)

Probabilidad proporcional al fitness:

\[ P(i) = \frac{f(i)}{\sum_j f(j)} \]

Imagina una ruleta donde el sector de cada individuo es proporcional a su fitness. ⚠️ EXAMEN: el más guapo no siempre gana, pero tiene más oportunidades.

9. Operadores de cruce

9.1 One-point crossover (1 punto) ⚠️ EXAMEN

Punto de corte \(N\). El primer hijo copia los primeros \(N\) genes del padre 1 y los restantes del padre 2. El segundo hijo hace lo contrario.

Padre 1: 1 0 1 | 0 1 1
Padre 2: 0 1 0 | 1 0 0
        N=3
Hijo 1:  1 0 1   1 0 0
Hijo 2:  0 1 0   0 1 1

⚠️ EXAMEN — error típico: contar el punto al revés o partir a la mitad cuando no toca. Contar siempre desde la izquierda.

9.2 M-point crossover

M puntos de corte → alterna trozos de los dos padres.

M=2, puntos en 2 y 5:
Padre 1: 1 0 | 1 0 1 | 1
Padre 2: 0 1 | 0 1 0 | 0
Hijo 1:  1 0   0 1 0   1
Hijo 2:  0 1   1 0 1   0

⚠️ EXAMEN — si en el examen aparece M=2, hay que dar dos puntos de corte. Con M=1 se reduce al one-point.

9.3 Cruce uniforme ⚠️ EXAMEN

Sin puntos de corte. Una máscara binaria del mismo tamaño que el cromosoma decide gen a gen de qué padre se hereda. La máscara se construye por sorteo (probabilidad típica 0.5 por gen).

Padre 1:   1 0 1 0 1 1
Padre 2:   0 1 0 1 0 0
Máscara:   1 0 1 0 0 1
Hijo:      1 1 1 1 0 1   (donde la máscara es 1 → padre 1)

No confundir con mutación. El uniforme solo elige al hijo entre los genes de los padres; no introduce valores nuevos.

9.4 Cruce con números reales

La media (cruce aritmético) es la versión más sencilla:

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

Variantes: combinaciones lineales con peso \(\alpha \in [0,1]\) (\(\alpha \cdot p_1 + (1-\alpha) \cdot p_2\)). El hijo no se parece a ninguno en concreto sino a la mezcla.

9.5 Cruce de orden (OX) ⚠️ EXAMEN

Para codificación de orden (permutaciones, agente viajero). Mantener la condición de permutación válida:

1. Elegir un segmento del padre 1 (p. ej. posiciones 3-5).
2. Copiarlo intacto al hijo en la misma posición.
3. Recorrer el padre 2 en orden, eliminando los elementos ya
   presentes en el segmento copiado, y rellenar el resto de
   posiciones del hijo en ese orden.

Padre 1: A B [D E F] G H I
Padre 2: I H G A B C D E F

Quitamos D, E, F del padre 2:    I H G A B C
Rellenamos las posiciones libres del hijo en el orden del padre 2:
Hijo:    I H [D E F] G A B C   ← mantiene D E F + secuencia de P2

Aplicación típica: TSP. Ciclos hamiltonianos exigen no repetir ciudad, y este cruce lo garantiza.

10. Validación rápida de la función de aptitud

Por convención en AG:

\(f \geq 0\) siempre que sea posible.
Maximizar implícitamente (si el problema es minimizar, transformar: \(f' = M - f\) con \(M\) una constante grande).

Trampa habitual: en lugar de usar valor absoluto (no diferenciable; aparecen "picos"), trasladar la función con una constante positiva grande hasta que sea positiva. ⚠️ EXAMEN-conceptual.

11. Avance: mutación (próxima clase)

Pendiente para la siguiente sesión:

Mutación binaria: invertir un bit.
Mutación real: sumar un ruido gaussiano \(\mathcal{N}(0, \sigma)\).
Mutación de orden: swap entre dos posiciones.
Tasas típicas y por qué deben ser pequeñas.

12. Actividad 2 — Comparativa AG vs ACO

Igual para ciencia de datos e informática. Cambia el dataset:

Rama	Dataset	Problema
Ciencia de datos	Asistencia integral hospitalaria	Localización óptima de centros de salud / circuito
Informática	Precios de combustibles	Optimización sobre datos de precios

12.1 Reglas

Implementar un algoritmo genético y un algoritmo de adaptación social (típicamente ACO/hormigas).
Comparar ambas implementaciones: número de iteraciones, CPU time, calidad de la solución.
Lenguaje: MATLAB (no Python aunque el enunciado lo permita; preferencia explícita).
Entregable: PDF (no manuscrito), introducción al problema breve, descripción de cada algoritmo, parámetros usados y por qué, tablas de resultados, conclusión personal, bibliografía.
Rúbrica por demostración de comprensión del algoritmo, no por simple resolución de ejercicios.

Datasets ya subidos a documentación (no en carpeta, directamente). El de ACO se puede empezar ya; el de AG se cierra la próxima semana cuando se vean los operadores de mutación.

12.2 Recomendaciones de la profesora

No copiar el código directamente; los casos son específicos.
Tablas claras de resultados (un eje por variable).
Comparar al menos: iteraciones, tiempo de CPU, mejor fitness alcanzado, estabilidad.
Conclusión personal: cuál te gusta más y por qué.

Ejemplos / Ejercicios resueltos

Ejemplo 1 — Selección por torneo K=2

Población (fitness): \(\{ A: 13,\ B: 14,\ C: 9,\ D: 17,\ E: 11 \}\)

Iteración 1: tomamos \(\{A, D\}\) al azar → fitness 13 vs 17 → gana D. Iteración 2: tomamos \(\{B, E\}\) → fitness 14 vs 11 → gana B. Pareja seleccionada para cruzar: \((D, B)\).

Ejemplo 2 — One-point crossover en N=3

Padres (binarios de longitud 6):

Padre 1: 1 0 1 | 0 1 1
Padre 2: 0 1 0 | 1 0 0

Hijo 1: 1 0 1 1 0 0 (cabeza P1, cola P2). Hijo 2: 0 1 0 0 1 1 (cabeza P2, cola P1).

Ejemplo 3 — M-point con M=3 sobre cromosoma de longitud 7

Puntos de corte: 1, 4, 6.

Padre 1: 1 | 0 1 0 | 1 1 | 0
Padre 2: 0 | 1 0 1 | 0 0 | 1
Hijo 1:  1   1 0 1   1 1   1   (alterna P1, P2, P1, P2)
Hijo 2:  0   0 1 0   0 0   0

Ejemplo 4 — Cruce uniforme

Padres:

P1: 1 0 1 0 1 1
P2: 0 1 0 1 0 0

Máscara aleatoria: 1 0 1 0 0 1.

Hijo: 1 1 1 1 0 1   (donde mask=1 → de P1, donde mask=0 → de P2)

Ejemplo 5 — Cruce real con media

Padres (longitud 4):

P1: 5.6  0.9  -2.1  3.4
P2: 1.2  4.5   0.7  2.8
Hijo (media): 3.4  2.7  -0.7  3.1

Ejemplo 6 — Cruce de orden (OX) en TSP

Padre 1: A B D E F G H I. Segmento elegido: posiciones 3-5 → D E F. Padre 2: I H G A B C D E F.

Quitamos D, E, F de P2: I H G A B C.

Hijo:

[ . . D E F . . . . ]   ← segmento fijo
relleno con I H G A B C en orden:
[ I H D E F G A B C ]

Preguntas de Autoevaluación

¿En qué década nacieron los algoritmos genéticos y en qué metáfora natural se basan? Cita al menos un trabajo o autor de referencia.
Enumera los cinco pasos del bucle principal de un algoritmo genético en orden y explica brevemente qué hace cada uno.
¿Qué problema concreto soluciona la mutación? ¿Qué pasaría si la quitas? Cita el rango típico de probabilidades de mutación.
Diferencia modelo generacional y modelo estacionario. Pon un ejemplo de población antes/después en cada uno.
¿Qué tres criterios de parada hemos visto y cuál se usa más en la práctica con problemas reales? ¿Por qué?
Dada la población con fitness \(\{ A: 13, B: 14, C: 9, D: 17 \}\) y selección por torneo K=2 con torneo \((C, D)\), ¿cuál gana? Justifica.
Explica la selección estocástica (ruleta) con su fórmula. ¿Por qué un individuo "el más guapo" no siempre es elegido?
Realiza el cruce one-point con N=2 sobre los padres [1,1,0,0,1] y [0,0,1,1,0]. Da los dos hijos.
Realiza el cruce M-point con M=2 y puntos de corte 1 y 3 sobre los mismos padres del ejercicio anterior.
¿Cómo se construye un hijo con cruce uniforme? Aplica una máscara 1 0 1 0 1 sobre los padres del ejercicio 8.
Para variables reales, da una fórmula de cruce que tienda al padre 1 un 70% y al padre 2 un 30%.
¿Por qué el cruce de orden (OX) es el adecuado para el TSP y no, por ejemplo, el one-point binario?
¿Qué codificación usarías para: (a) qué objetos meter en una mochila, (b) la trayectoria óptima de un dron en \(\mathbb{R}^3\), (c) el orden de visita en una ruta de reparto?
Si la función objetivo puede tomar valores negativos, ¿cómo la transformas para que sirva como fitness en un AG canónico? ¿Por qué se evita el valor absoluto?
Explica con tus palabras por qué los AG "no requieren derivadas". ¿Qué ventaja te da eso frente a un método clásico de gradiente?
En la actividad 2, ¿qué dos algoritmos hay que comparar y qué métricas se piden como mínimo?