Clase 15 — Algoritmos Genéticos Multiobjetivo: NPGA y Elitismo (última clase)

Resumen Ejecutivo

Última clase del curso. Se cierran los dos algoritmos genéticos multiobjetivo que quedaban pendientes del tema, ambos con la misma estructura genética y un pequeño "clic" en la fase de evaluación/selección:

NPGA (Niched Pareto Genetic Algorithm): selección por torneo contra un subconjunto de la población, con niching (nichos) como criterio de desempate para favorecer la diversidad y la exploración.
Algoritmo elitista con conjunto élite (archivo de Pareto): se almacenan las mejores soluciones no dominadas encontradas; cuando el archivo crece demasiado, se recorta con clustering manteniendo la diversidad.

Cierre con notas de examen (el multiobjetivo no entra) y comentarios sobre la corrección de la actividad 3.

⚠️ El multiobjetivo NO entra en el examen (hubo que elegir qué temas entraban). Basta practicar el modelo de examen y los ejercicios de clase.

Conceptos Clave

NPGA (Niched Pareto Genetic Algorithm): selección por torneo donde dos candidatos compiten contra un subconjunto de la población (no entre sí directamente); gana el que es no dominado por el subconjunto. ⚠️
Niching (nichos): ante un empate, se mide la densidad de vecinos de cada candidato (por distancia) y gana el de menos vecinos, para escapar de óptimos locales y diversificar.
Elitismo / conjunto élite: archivo externo donde se guardan las soluciones no dominadas halladas durante la búsqueda, para no perderlas en la mutación.
Recorte por clustering: cuando el conjunto élite supera un tamaño máximo, se agrupan las soluciones y se eliminan las más cercanas (distancia menor), conservando diversidad.
Motivación común: todos estos algoritmos son el genético base + una idea creativa en la evaluación para converger mejor a la frontera de Pareto.

Desarrollo del Temario

1. NPGA — Niched Pareto Genetic Algorithm

La estructura es la del genético; el cambio está entre la evaluación y la selección, en cómo se hace el torneo.

Mecánica del torneo: 1. Se eligen dos individuos candidatos (A y B). 2. En lugar de compararlos directamente, se toma un subconjunto de la población. 3. Cada candidato "pelea" contra ese subconjunto: se cuenta a cuántos domina / por cuántos es dominado. Si un candidato es no dominado por el subconjunto y el otro sí, gana el primero. 4. Si hay empate → entra el niching.

Niching (desempate por diversidad): - Se estima la densidad de soluciones alrededor de cada candidato (igual que en clustering: se elige una distancia —euclídea, de bits…— y se cuentan los vecinos dentro de un radio). - Gana el candidato con menos vecinos (zona menos explorada), favoreciendo la exploración del espacio.

flowchart TB
    T["Torneo: candidatos A y B"]
    SUB["Cada uno compite contra un subconjunto"]
    DOM{"¿Empate en dominancia?"}
    WIN["Gana el no dominado"]
    NICHE["Niching: cuenta vecinos por distancia"]
    DIV["Gana el de MENOS vecinos (más diversidad)"]
    T --> SUB --> DOM
    DOM -->|No| WIN
    DOM -->|Sí| NICHE --> DIV

Ejemplo de clase (maximización, utilidad vs. satisfacción del cliente, 6 individuos): los no dominados son A, D, E, F (B y C quedan dominados). En un torneo B vs F, F domina a B; ante empates se recurre a contar vecinos (B suele estar más "rodeado", así que se prefiere F para diversificar).

2. Algoritmo elitista con conjunto élite (archivo de Pareto)

Problema que resuelve: en el ciclo genético, la mutación (o el cruce) puede destruir una buena solución ya encontrada. Solución: guardarla aparte.

Mecánica: 1. Mantener un conjunto élite (archivo) con las soluciones no dominadas encontradas hasta el momento (aquí no se hacen rangos 1-2-3, solo no dominadas). 2. En cada nueva generación, actualizar el archivo: si un nuevo individuo domina a otros del archivo, se reemplazan. 3. La selección/torneo se hace a partir del conjunto élite.

Recorte por clustering: guardar todas las soluciones es costoso en memoria (problema típico de big data; conviene pensar en vectores dinámicos). Por eso el archivo tiene un tamaño máximo: - Si el nº de no dominadas ≤ tamaño máximo → se usan tal cual. - Si lo supera → se aplica clustering: se miden distancias entre todas las soluciones y se elimina una de las dos más cercanas (distancia mínima), repitiendo hasta ajustar el tamaño. Así se limita el conjunto favoreciendo la diversidad (mayor distancia = mejor cobertura de la frontera).

Idea transversal de la clase: estos algoritmos nacen de que alguien se topó con un problema concreto (perder soluciones, empates, memoria) y añadió un pequeño truco al genético base; luego se generaliza y se publica.

3. Notas finales y corrección de la actividad 3

Examen: el multiobjetivo no entra. Practicar el modelo de examen y los ejercicios; las variaciones serán pequeñas. Suerte.
Actividad 3 (algoritmo genético en un fichero .m): el algoritmo se daba hecho; solo había que cambiar tres funciones/parámetros y explicar el código (no obligatoriamente línea por línea, pero sí las funciones y parámetros importantes).
Penalizaba fuerte no subir el archivo de código y no demostrar la ejecución (gráficas de evolución de la población, óptimo encontrado).
Se exigía portada e índice, extensión ~4-5 páginas (no ser estricta, pero entregas de 18-20 páginas o pegar todo el código son malas prácticas).
Buena práctica general (aunque no se penalizara aquí): introducción, conclusiones y bibliografía bien citada.

Preguntas de Autoevaluación

En el NPGA, ¿contra quién compiten los candidatos en el torneo y cómo se decide el ganador?
¿Qué es el niching y cuándo se aplica? ¿Por qué gana el individuo con menos vecinos?
¿Cómo se mide la densidad de vecinos de una solución?
¿Qué problema del ciclo genético resuelve el conjunto élite (archivo de Pareto)?
¿Cuándo y cómo se actualiza el conjunto élite al generar una nueva población?
¿Por qué hay que limitar el tamaño del archivo de soluciones no dominadas?
Explica el recorte por clustering: ¿qué solución se elimina y por qué favorece la diversidad?
¿Qué tienen en común NPGA, el algoritmo elitista y el MOGA visto en la clase anterior?
¿Entra la optimización multiobjetivo en el examen? ¿En qué conviene centrarse?
En la actividad 3, ¿qué penalizaba más en la corrección?