NSGA-II desde cero: el algoritmo que optimiza sin elegir

Por qué optimización multi-objetivo

En ingeniería real nunca optimizas una sola cosa. Un ala de avión más ligera probablemente sea más débil. Un perfil aerodinámico más eficiente puede ser más difícil de fabricar. Necesitas encontrar el conjunto de diseños donde no puedes mejorar un objetivo sin empeorar otro — el frente de Pareto. NSGA-II (Non-dominated Sorting Genetic Algorithm II), publicado por Deb et al. en 2002, es el algoritmo más usado para esta tarea con más de 40.000 citas académicas.

A diferencia de los algoritmos de optimización clásicos que convierten múltiples objetivos en uno solo mediante pesos (weighted sum), NSGA-II mantiene los objetivos separados y encuentra todo el frente de Pareto en una sola ejecución.

Concepto 1: Dominancia de Pareto

Una solución x₁ domina a x₂ si: (1) x₁ no es peor que x₂ en ningún objetivo, Y (2) x₁ es estrictamente mejor en al menos un objetivo.

Matemáticamente (asumiendo minimización): f_i(x₁) <= f_i(x₂) para todo i, y existe al menos un j tal que f_j(x₁) < f_j(x₂).

El frente de Pareto es el conjunto de soluciones no-dominadas — diseños que no son dominados por ningún otro diseño en la población. Visualízalo: dos objetivos (minimizar C_d, maximizar -C_l). El punto A (C_d=0.010, C_l=0.50) domina al punto B (C_d=0.012, C_l=0.50). Pero ni A (0.010, 0.50) ni C (0.008, 0.45) domina al otro — ambos son Pareto-óptimos y pertenecen al frente.

Concepto 2: Non-dominated sorting

Es el primer mecanismo fundamental de NSGA-II. Clasifica la población en frentes:

• Frente 1: todas las soluciones no-dominadas de la población
• Se elimina el Frente 1. Frente 2: soluciones no-dominadas entre las restantes
• Se repite hasta que todas las soluciones tienen asignado un frente

El algoritmo es O(M*N^2): para cada solución, se calcula (a) contador de dominación n_p (cuántas la dominan), (b) conjunto S_p (soluciones que ella domina). Las soluciones con n_p = 0 pertenecen al Frente 1. Se eliminan y se decrementa n_p de las que dominaban, repitiendo el proceso.

Concepto 3: Crowding distance

Non-dominated sorting nos dice a qué frente pertenece cada solución, pero no cómo comparar soluciones DENTRO del mismo frente. NSGA-II usa crowding distance — una medida de cuán "sola" está una solución en el espacio de objetivos.

Para cada objetivo, se ordenan las soluciones por ese objetivo. Para cada solución, se suma la distancia normalizada entre sus dos vecinas. Esto se repite para todos los objetivos y se acumula. Las soluciones en los extremos reciben crowding distance infinita (para preservar los extremos del frente de Pareto).

Esto promueve diversidad: las soluciones en regiones poco pobladas son preferidas, evitando que el algoritmo converja a un único cúmulo de soluciones similares.

El algoritmo paso a paso

1. Inicializar población P₀ de tamaño N aleatoriamente.
2. Evaluar objetivos para todos los individuos.
3. Non-dominated sort de P_t en frentes.
4. Selección por torneo binario: se eligen 2 individuos al azar, gana el de mejor frente (menor índice). Si mismo frente, gana el de mayor crowding distance. Así se crea el mating pool.
5. Simulated Binary Crossover (SBX) y Polynomial Mutation para crear descendencia Q_t de tamaño N.
6. Combinar padres e hijos: R_t = P_t U Q_t (tamaño 2N).
7. Non-dominated sort de R_t. Llenar nueva población P_t+1 añadiendo frentes completos en orden hasta alcanzar N. Si un frente entra parcialmente, se ordena por crowding distance y se toman los mejores.
8. Repetir desde el paso 3 durante G generaciones.

Este mecanismo se llama elitismo: los mejores padres compiten directamente con los hijos para permanecer en la siguiente generación, garantizando que la calidad del frente de Pareto nunca empeora.

Implementación en Python

import numpy as np

def dominates(a, b):
    """Verifica si la solucion a domina a b (minimizacion)."""
    return all(a <= b) and any(a < b)

def non_dominated_sort(objectives):
    """Devuelve lista de frentes, cada frente es lista de indices."""
    n = len(objectives)
    domination_count = np.zeros(n, dtype=int)
    dominated_set = [[] for _ in range(n)]
    fronts = [[]]
    
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            if dominates(objectives[i], objectives[j]):
                dominated_set[i].append(j)
            elif dominates(objectives[j], objectives[i]):
                domination_count[i] += 1
        if domination_count[i] == 0:
            fronts[0].append(i)
    
    i = 0
    while len(fronts[i]) > 0:
        next_front = []
        for p in fronts[i]:
            for q in dominated_set[p]:
                domination_count[q] -= 1
                if domination_count[q] == 0:
                    next_front.append(q)
        i += 1
        fronts.append(next_front)
    
    return fronts[:-1]  # Eliminar ultimo frente vacio

def crowding_distance(objectives, front):
    """Calcula crowding distance para soluciones en un frente."""
    n_obj = objectives.shape[1]
    distances = np.zeros(len(front))
    for m in range(n_obj):
        idx = np.array(front)
        sorted_idx = idx[np.argsort(objectives[idx, m])]
        dist_pos = {v: k for k, v in enumerate(front)}
        distances[dist_pos[sorted_idx[0]]] = np.inf
        distances[dist_pos[sorted_idx[-1]]] = np.inf
        f_range = objectives[sorted_idx[-1], m] - objectives[sorted_idx[0], m]
        if f_range == 0:
            continue
        for k in range(1, len(front) - 1):
            pos = dist_pos[sorted_idx[k]]
            distances[pos] += (objectives[sorted_idx[k+1], m] -
                              objectives[sorted_idx[k-1], m]) / f_range
    return distances

Visualización del frente de Pareto

Para problemas con 2 objetivos, el frente de Pareto es una curva en el espacio de objetivos. Para 3 objetivos, es una superficie. Para más dimensiones, la visualización se complica — se usan gráficos de coordenadas paralelas o reducción de dimensionalidad (PCA).

La evolución del frente de Pareto a través de las generaciones es una de las visualizaciones más informativas: la Generación 1 muestra una nube dispersa, la Generación 50 muestra un frente bien definido aproximándose a la superficie Pareto-óptima real.

NSGA-II en la práctica: parámetros y trucos

• Tamaño de población: 50-200 para 2-3 objetivos, hasta 500 para 5+ objetivos. Poblaciones mayores mantienen diversidad pero aumentan el coste.
• Generaciones: 50-300. La convergencia se alcanza típicamente cuando el indicador de hipervolumen se estabiliza.
• Probabilidad de cruce: 0.9. Probabilidad de mutación: 1/n_vars.
• Índices de distribución: eta_c = 20 (cruce), eta_m = 20 (mutación). Valores más altos = hijos más parecidos a los padres.
• Coste computacional: dominado por la evaluación de objetivos (ej. ejecutar CFD). El overhead de NSGA-II es despreciable comparado con el coste de simulación.

Limitaciones y extensiones

NSGA-II sufre más allá de 3-4 objetivos porque: (a) casi todas las soluciones pasan a ser no-dominadas, (b) crowding distance pierde efectividad en altas dimensiones. NSGA-III (Deb & Jain, 2014) aborda esto con selección basada en puntos de referencia.

Para objetivos costosos (CFD, FEA), se prefiere NSGA-II asistido por surrogate: entrenar un modelo de Gaussian Process con los diseños ya evaluados y usarlo para pre-filtrar candidatos antes de ejecutar la simulación real. Esta técnica la exploramos en el artículo sobre optimización bayesiana.