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

Resumo Técnico: Algoritmos Exatos e Evolutivos para o Planejamento Sequencial de Topologias de Transmissão Multiobjetivo

Formulação do Problema
O artigo aborda o planejamento de topologia de transmissão para o dia seguinte como um problema de otimização sequencial multiobjetivo. O objetivo é determinar uma sequência de topologias de rede ao longo de um horizonte de 24 horas (24 passos de tempo) para gerenciar o congestionamento da rede. O problema é definido por quatro objetivos operacionais que refletem critérios de decisão reais do Operador do Sistema de Transmissão (TSO), todos os quais devem ser minimizados:

1. Carga máxima de linha no pior caso ($LF_1$): A máxima utilização da capacidade de qualquer linha de transmissão sob contingências de segurança $N-1$ ao longo de todo o horizonte.
2. Profundidade topológica ($d$): O número máximo de barras adicionais criadas pela abertura de acopladores de barra (divisão de nós) em relação à topologia de referência (todos os acopladores fechados) em qualquer ponto no tempo.
3. Número de ações de comutação ($w$): A contagem total de mudanças de topologia (comutações) realizadas ao longo do período de 24 horas.
4. Utilização de topologias não de referência ($z$): O número de passos de tempo em que a rede opera em uma configuração diferente da topologia de referência padrão.

O estudo utiliza dados operacionais reais da rede de alta tensão holandesa gerenciada pelo TSO TenneT, focando em um dia altamente congestionado onde a topologia de referência frequentemente excede 100% de carga sob condições $N-1$.

Metodologia
Os autores propõem e comparam dois algoritmos complementares: um método de enumeração exata e uma heurística evolutiva adaptada.

1. O Algoritmo de Blocos (Método Exato):

   • Conceito Central: Este algoritmo explora a estrutura de blocos temporais das estratégias viáveis. Em vez de avaliar cada passo de tempo independentemente, ele divide o horizonte de 24 horas em intervalos contíguos e não sobrepostos (blocos) onde a topologia permanece constante.
   • Mecanismo: Enumera sistematicamente todas as configurações de blocos possíveis, atribuições de topologia de referência e níveis de profundidade. Ao pré-calculá-los valores de fluxo de carga para todas as topologias disponíveis por passo de tempo, o algoritmo avalia combinações de blocos para identificar a frente de Pareto completa.
   • Complexidade: Para limites operacionais fixos de profundidade máxima ($d_{max}$) e contagem máxima de comutações ($s_{max}$), a contagem de avaliações cresce polinomialmente com o horizonte de planejamento. O algoritmo filtra estratégias com base na ordenação não dominada, aproveitando o fato de que três dos quatro objetivos são inteiros discretos para identificar eficientemente soluções Pareto-ótimas.

2. Algoritmo Evolutivo Multiobjetivo (MOEA):

   • Estrutura: Baseado no NSGA-III, selecionado por sua eficácia em problemas de muitos objetivos (quatro objetivos).
   • Representação: Utiliza codificação direta de comprimento variável onde cada gene representa a topologia para um passo de tempo específico.
   • Inicialização: Emprega uma estratégia de amostragem "guiada por estrutura" em vez de inicialização aleatória uniforme. Gera populações iniciais equilibrando contagens específicas de comutação e profundidades topológicas para garantir diversidade nas dimensões relevantes do espaço objetivo.
   • Variação: Utiliza crossover de $k$ pontos (com $k=2$) para preservar a coerência temporal e mutação de redefinição aleatória para garantir viabilidade dentro do conjunto de topologias disponíveis para cada passo de tempo.

Principais Contribuições

1. Formalização: O problema é formalmente definido como uma otimização multiobjetivo sequencial com quatro objetivos específicos relevantes para TSOs, indo além de formulações de único objetivo ou de passos de tempo isolados.
2. Enumeração Exata: O desenvolvimento do "algoritmo de blocos", que computa a frente de Pareto completa para um dia congestionado do mundo real em menos de três minutos. Fornece um benchmark de verdade fundamental para esta classe de problemas.
3. Heurística Adaptada: O design de um MOEA especializado com inicialização guiada por estrutura e operadores de variação específicos do problema, avaliado contra a frente exata usando Distância Geracional Invertida Mais (IGD+) e uma nova métrica de cobertura multi-frente.
4. Validação Empírica: Um estudo comparativo usando dados do TenneT demonstrando que a enumeração exata é computacionalmente viável e supera a busca evolutiva na recuperação do conjunto completo de estratégias ótimas.

Resultados

• Desempenho do Algoritmo de Blocos: O método exato enumerou com sucesso a frente de Pareto completa, identificando 83 pontos únicos no espaço objetivo (representando 163.807.652 estratégias distintas). Constatou-se que alcançar $LF_1 < 100\%$ (segurança $N-1$ total) exige abandonar completamente a topologia de referência durante horas congestionadas e operar com maiores profundidades topológicas.
• Desempenho do MOEA: O algoritmo evolutivo convergiu em direção à frente de Pareto, mas falhou em recuperar o conjunto exato de soluções.
  • A configuração de melhor desempenho (tamanho de população 1.621, taxa de mutação 0,10) recuperou apenas aproximadamente 6% dos pontos Pareto-óptimos únicos encontrados pelo algoritmo de blocos.
  • O MOEA teve dificuldade em encontrar soluções com $LF_1 < 100\%$, que foram identificadas pelo método exato.
  • A cobertura foi particularmente baixa para estratégias envolvendo muitas topologias não de referência (regiões extremas do espaço de busca).
• Comparação: Embora o MOEA tenha mostrado convergência inicial rápida (dentro de 5 minutos), ele estagnou e não conseguiu igualar a completude do algoritmo de blocos. A capacidade do algoritmo de blocos de enumerar todas as estratégias viáveis permitiu-lhe identificar trade-offs que a heurística perdeu.

Significado e Alegações
O artigo alega que a complexidade combinatória de otimizar estratégias topológicas ao longo de um horizonte de 24 horas, frequentemente percebida como intratável, pode ser resolvida de forma exata e eficiente explorando a estrutura de blocos temporais do problema.

• Suporte à Decisão: O algoritmo de blocos fornece aos TSOs um menu completo de estratégias Pareto-ótimas, permitindo que os operadores selecionem ações com base em prioridades diárias específicas (por exemplo, minimizar comutações versus maximizar segurança).
• Benchmarking: A frente exata serve como um benchmark rigoroso de verdade fundamental para avaliar futuros métodos heurísticos e baseados em aprendizado.
• Viabilidade: O estudo demonstra que a enumeração exata não é apenas teoricamente possível, mas praticamente viável para cenários de rede do mundo real altamente congestionados, desafiando a suposição de que heurísticas são estritamente necessárias para tais problemas.

Os autores reconhecem limitações, incluindo o uso de aproximações de fluxo de potência DC, previsões determinísticas e a dependência de conjuntos de dados pré-calculados. Sugerem que trabalhos futuros poderiam envolver formulações estocásticas, otimização robusta e a aplicação de aprendizado por imitação para contornar o gargalo do pré-cálculo. No entanto, dentro do escopo do estudo, o algoritmo de blocos é apresentado como o método preferido por sua exatidão, velocidade e completude.