Clase 14 — Optimización Multiobjetivo con Algoritmos Genéticos

Resumen Ejecutivo

Primera de las dos sesiones finales. Tras un repaso de cómo afrontar el examen (basarse en el modelo de examen y en los ejercicios de clase, no tanto en exámenes de años anteriores porque ya no se puede usar software), se desarrolla la optimización multiobjetivo:

Repaso de dominancia y frontera de Pareto (visto en Optimización I).
Métodos exactos: suma ponderada y método ε-constraint / lexicográfico.
Adaptación de los algoritmos genéticos al caso multiobjetivo mediante un paso de ranking por dominancia antes de la selección: el ranking de Goldberg y una variante por número de dominadores (MOGA).

⚠️ Sobre el examen: las únicas fórmulas a memorizar son las de PSO (nube de partículas) y ACO (hormigas); del resto (Horner, genéticos) hay que saber los pasos del algoritmo. Los problemas son pequeños (pocas iteraciones/combinaciones). No se puede usar software.

Conceptos Clave

Problema multiobjetivo: varias funciones objetivo (con restricciones) que suelen estar en conflicto (minimizar coste y tiempo, maximizar ganancia, minimizar emisiones). ⚠️ EXAMEN
Dominancia: una solución \(x_1\) domina a \(x_2\) si es mejor o igual en todos los objetivos y estrictamente mejor en al menos uno. ⚠️ EXAMEN
Conjunto de Pareto: soluciones no dominadas por ninguna otra. Frontera de Pareto: su imagen en el espacio de objetivos. ⚠️ EXAMEN
Suma ponderada: combinar los objetivos en una sola función con pesos que suman 1 (100%). Sirve cuando es fácil fijar prioridades. ⚠️ EXAMEN
Método ε-constraint: optimizar el objetivo más importante y convertir los demás en restricciones con un margen (ε) de tolerancia. Es exacto.
Ranking de Goldberg: asignar rango 1 a las no dominadas, retirarlas, rango 2 a las siguientes no dominadas, etc. (iterativo). ⚠️ EXAMEN
Ranking MOGA (por nº de dominadores): rango = 1 + número de individuos que dominan a la solución (en una sola pasada).

Desarrollo del Temario

1. El problema multiobjetivo

En la vida real, modelar con un solo objetivo a menudo no basta. Ejemplos: minimizar coste y tiempo, maximizar ganancias y minimizar gases contaminantes. La forma clásica es construir una función objetivo que englobe todas — pero no siempre es fácil decidir cómo combinarlas.

2. Dominancia y frontera de Pareto

Ejemplo (elegir empleo): dos objetivos = salario (maximizar) y cercanía a casa (maximizar).

Opción	Salario	Localización
A	bajo	muy buena
B	alto	mala
C	medio	media
D	bajo-medio	mala

A vs B: ninguno domina al otro (A mejor en localización, B mejor en salario) → ambos en la frontera.
C: queda en medio; según los pesos puede preferirse o no.
D: está dominado por C (peor o igual en ambos) → fuera de la frontera.

\[x_1 \preceq x_2 \iff \forall i:\ f_i(x_1) \le f_i(x_2)\ \land\ \exists j:\ f_j(x_1) < f_j(x_2)\]

(para minimización; el signo de dominancia es el "≺/≻ curvado"). El conjunto de Pareto son las soluciones no dominadas; la frontera de Pareto es su representación en el espacio de objetivos. Las soluciones dominadas quedan "dentro" (factibles pero no preferidas).

3. Métodos exactos

3.1 Suma ponderada

Asignar un peso a cada objetivo (que sumen 1) y optimizar la combinación. Útil cuando se sabe qué objetivo priorizar. En los ejercicios, si un peso es 0,8 el otro es 0,2 (álgebra sencilla).

3.2 Método ε-constraint (aproximación lexicográfica)

Resolver optimizando el objetivo más importante (\(f_1\)).
Volver a optimizar sobre \(f_2\), añadiendo una restricción con un margen ε sobre \(f_1\) (cuánto se está dispuesto a ceder en \(f_1\) para mejorar \(f_2\)).

Ejemplo: minimizar tiempo (gana C), luego minimizar coste permitiendo un colchón ε = 0,5 sobre el tiempo → puede cambiar la solución elegida. Sigue siendo método exacto (maneja ε explícitos).

4. Algoritmos genéticos multiobjetivo

El algoritmo genético es el mismo de siempre (codificar → evaluar → seleccionar → cruzar → mutar → repetir). El único cambio es un paso intermedio entre evaluación y selección: en vez de tender al óptimo, se converge a la frontera de Pareto asignando un ranking por dominancia.

flowchart LR
    P[Población] --> E[Evaluar en todas las f_i]
    E --> R[Ranking por dominancia]
    R --> S[Selección por probabilidad del ranking]
    S --> C[Cruce] --> M[Mutación] --> E2[Re-evaluar]
    E2 --> R

4.1 Ranking de Goldberg (iterativo)

Las soluciones no dominadas de la población → frente 1 (ranking 1).
Se retiran y se buscan las no dominadas del resto → frente 2 (ranking 2).
Se repite hasta clasificar toda la población.

A menor ranking, mayor probabilidad en la selección.

Ejemplo (minimización, 6 individuos): las que no domina nadie (A, B, C, D, E) → frente 1; F está dominada por C → frente 2.

4.2 Ranking MOGA (por número de dominadores)

Variante en una sola pasada: para cada individuo, ranking = 1 si no lo domina nadie; si lo dominan, ranking = número de individuos que lo dominan (N). Suele dar resultados equivalentes al de Goldberg, pero sin retirar frentes iterativamente.

ranking(x) = 1 + |{ y ∈ Población : y domina a x }|

4.3 Del ranking al fitness (idoneidad)

Con el ranking se asigna un fitness mediante una función decreciente (técnica usada con variables ordinales en estadística): 1. Ordenar por ranking (sort). 2. Asignar pesos decrecientes (p.ej. 1; 0,8; 0,6; 0,4; 0,2). 3. Repartir el peso entre los individuos con el mismo ranking (media) para que sea justo.

Ese fitness da la probabilidad de selección. Después se aplica el ciclo genético normal sobre la codificación de las variables (no sobre los objetivos): selección con toque aleatorio, cruce (p.ej. 2 puntos), mutación, re-evaluar y volver a rankear.

Este algoritmo base es el Multi-Objective Genetic Algorithm (MOGA). En la siguiente clase se ven dos variantes más.

Preguntas de Autoevaluación

Define formalmente cuándo una solución domina a otra. ¿Qué es el conjunto de Pareto y qué la frontera de Pareto?
Dado el ejemplo del empleo, ¿por qué D está dominado pero A y B no se dominan entre sí?
¿Cuándo conviene la suma ponderada y cuándo el método ε-constraint? ¿Ambos son exactos?
¿Cuál es el único paso que cambia en un algoritmo genético para hacerlo multiobjetivo?
Aplica el ranking de Goldberg a una población de 6 individuos en minimización.
Diferencia el ranking de Goldberg del ranking MOGA por número de dominadores. ¿Dan resultados distintos?
¿Cómo se pasa de un ranking a un fitness y por qué hay que repartir el peso entre individuos con el mismo ranking?
En un genético multiobjetivo, ¿sobre qué se aplican cruce y mutación: sobre los objetivos o sobre la codificación de las variables?
¿Por qué el algoritmo "converge a la frontera de Pareto" y no a un único óptimo?
¿Qué fórmulas hay que memorizar de cara al examen y de qué algoritmos basta con conocer los pasos?