Exact and Evolutionary Algorithms for Sequential Multi-Objective Transmission Topology Planning

Resumen Técnico: Algoritmos Exactos y Evolutivos para la Planificación Secuencial de la Topología de Transmisión Multiobjetivo

Formulación del Problema
El artículo aborda la planificación de la topología de transmisión para el día siguiente como un problema de optimización secuencial multiobjetivo. El objetivo es determinar una secuencia de topologías de red a lo largo de un horizonte de 24 horas (24 pasos de tiempo) para gestionar la congestión de la red. El problema se define mediante cuatro objetivos operativos que reflejan criterios reales de decisión de los Operadores del Sistema de Transmisión (OST), todos los cuales deben minimizarse:

1. Carga máxima de línea en el peor caso ($LF_1$): La máxima utilización de la capacidad de cualquier línea de transmisión bajo contingencias de seguridad $N-1$ a lo largo de todo el horizonte.
2. Profundidad topológica ($d$): El número máximo de barras adicionales creadas al abrir acopladores de barras (división de nodos) en relación con la topología de referencia (todos los acopladores cerrados) en cualquier punto del tiempo.
3. Número de acciones de conmutación ($w$): El recuento total de cambios de topología (conmutaciones) realizados durante el período de 24 horas.
4. Utilización de topologías no referenciales ($z$): El número de pasos de tiempo en los que la red opera en una configuración diferente a la topología de referencia predeterminada.

El estudio utiliza datos operativos reales de la red de alta tensión holandesa gestionada por TenneT OST, centrándose en un día altamente congestionado donde la topología de referencia excede frecuentemente el 100% de carga bajo condiciones $N-1$.

Metodología
Los autores proponen y comparan dos algoritmos complementarios: un método de enumeración exacta y una heurística evolutiva adaptada.

1. El Algoritmo de Bloques (Método Exacto):

   • Concepto Central: Este algoritmo explota la estructura de bloques temporales de las estrategias factibles. En lugar de evaluar cada paso de tiempo de forma independiente, divide el horizonte de 24 horas en intervalos contiguos y no superpuestos (bloques) donde la topología permanece constante.
   • Mecanismo: Enumera sistemáticamente todas las configuraciones de bloques posibles, asignaciones de topología de referencia y niveles de profundidad. Mediante el precálculo de los valores de flujo de carga para todas las topologías disponibles por paso de tiempo, el algoritmo evalúa combinaciones de bloques para identificar la frontera de Pareto completa.
   • Complejidad: Para límites operativos fijos sobre la profundidad máxima ($d_{max}$) y el recuento máximo de conmutaciones ($s_{max}$), el número de evaluaciones crece polinomialmente con el horizonte de planificación. El algoritmo filtra estrategias basándose en la clasificación de no dominancia, aprovechando el hecho de que tres de los cuatro objetivos son enteros discretos para identificar eficientemente soluciones óptimas de Pareto.

2. Algoritmo Evolutivo Multiobjetivo (MOEA):

   • Marco: Basado en NSGA-III, seleccionado por su eficacia en problemas de muchos objetivos (cuatro objetivos).
   • Representación: Utiliza una codificación directa de longitud variable donde cada gen representa la topología para un paso de tiempo específico.
   • Inicialización: Emplea una estrategia de muestreo "guiada por la estructura" en lugar de una inicialización aleatoria uniforme. Genera poblaciones iniciales equilibrando recuentos específicos de conmutaciones y profundidades topológicas para garantizar la diversidad en las dimensiones relevantes del espacio de objetivos.
   • Variación: Utiliza cruce de $k$ puntos (con $k=2$) para preservar la coherencia temporal y mutación de reinicio aleatorio para garantizar la factibilidad dentro del conjunto de topologías disponibles para cada paso de tiempo.

Contribuciones Clave

1. Formalización: El problema se define formalmente como una optimización secuencial multiobjetivo con cuatro objetivos específicos relevantes para el OST, superando las formulaciones de objetivo único o de pasos de tiempo aislados.
2. Enumeración Exacta: El desarrollo del "algoritmo de bloques", que calcula la frontera de Pareto completa para un día congestionado del mundo real en menos de tres minutos. Proporciona un punto de referencia de verdad fundamental para esta clase de problemas.
3. Heurística Adaptada: El diseño de un MOEA especializado con inicialización guiada por la estructura y operadores de variación específicos del problema, evaluado frente a la frontera exacta utilizando la Distancia Generacional Inversa Plus (IGD+) y una nueva métrica de cobertura multi-frontera.
4. Validación Empírica: Un estudio comparativo utilizando datos de TenneT que demuestra que la enumeración exacta es computacionalmente viable y supera a la búsqueda evolutiva en la recuperación del conjunto completo de estrategias óptimas.

Resultados

• Rendimiento del Algoritmo de Bloques: El método exacto enumeró con éxito la frontera de Pareto completa, identificando 83 puntos únicos en el espacio de objetivos (que representan 163.807.652 estrategias distintas). Descubrió que lograr $LF_1 < 100\%$ (seguridad completa $N-1$) requiere abandonar la topología de referencia por completo durante las horas de congestión y operar a mayores profundidades topológicas.
• Rendimiento del MOEA: El algoritmo evolutivo convergió hacia la frontera de Pareto pero no logró recuperar el conjunto exacto de soluciones.
  • La configuración de mejor rendimiento (tamaño de población 1.621, tasa de mutación 0,10) recuperó solo aproximadamente el 6% de los puntos óptimos de Pareto únicos encontrados por el algoritmo de bloques.
  • El MOEA tuvo dificultades para encontrar soluciones con $LF_1 < 100\%$, las cuales fueron identificadas por el método exacto.
  • La cobertura fue particularmente baja para estrategias que involucran muchas topologías no referenciales (regiones extremas del espacio de búsqueda).
• Comparación: Aunque el MOEA mostró una convergencia inicial rápida (dentro de los 5 minutos), se estancó y no pudo igualar la completitud del algoritmo de bloques. La capacidad del algoritmo de bloques para enumerar todas las estrategias factibles le permitió identificar compensaciones que la heurística pasó por alto.

Significado y Afirmaciones
El artículo afirma que la complejidad combinatoria de optimizar estrategias topológicas a lo largo de un horizonte de 24 horas, a menudo percibida como intratable, puede resolverse de manera exacta y eficiente explotando la estructura de bloques temporales del problema.

• Apoyo a la Decisión: El algoritmo de bloques proporciona a los OST un menú completo de estrategias óptimas de Pareto, permitiendo a los operadores seleccionar acciones basadas en prioridades diarias específicas (por ejemplo, minimizar conmutaciones frente a maximizar la seguridad).
• Puntos de Referencia: La frontera exacta sirve como un punto de referencia riguroso de verdad fundamental para evaluar futuros métodos heurísticos y basados en aprendizaje.
• Viabilidad: El estudio demuestra que la enumeración exacta no solo es teóricamente posible, sino prácticamente viable para escenarios de red del mundo real altamente congestionados, desafiando la suposición de que las heurísticas son estrictamente necesarias para tales problemas.

Los autores reconocen limitaciones, incluido el uso de aproximaciones de flujo de potencia de corriente continua, pronósticos deterministas y la dependencia de conjuntos de datos precalculados. Sugieren que el trabajo futuro podría involucrar formulaciones estocásticas, optimización robusta y la aplicación de aprendizaje por imitación para evitar el cuello de botella del precálculo. Sin embargo, dentro del alcance del estudio, el algoritmo de bloques se presenta como el método preferido por su exactitud, velocidad y completitud.