Análise Comparativa entre Algoritmos Evolutivos Multi-Objetivos Aplicados ao Problema de Redução de Perdas em Sistemas de Distribuição de Grande Porte

´ ANALISE COMPARATIVA ENTRE ALGORITMOS EVOLUTIVOS ˜ DE PERDAS EM MULTI-OBJETIVOS APLICADOS AO PROBLEMA DE REDUC ¸ AO ˜ SISTEMAS DE DISTRIBUIC ¸ AO DE GRANDE PORTE Danilo Sipoli Sanches∗, Leandro Tolomeu Marques†, Henrique Fernandes Borges†, ´ udio B. Delbem†, Joa ˜ o Bosco A. London Jr.† Alexandre Cla ∗

Av. Alberto Carazzai, 1640 Universidade Tecnol´ ogica Federal do Paran´ a Corn´elio Proc´ opio, Paran´ a, Brasil †

Av. Trabalhador S˜ ao-carlense, 400 Universidade de S˜ ao Paulo S˜ ao Carlos, S˜ ao Paulo, Brasil

Emails: [email protected], [email protected], [email protected], [email protected], [email protected] Abstract— Distribution systems reconfiguration for power loss reduction is usually formulated as a nonlinear, multi-objective, combinatorial and multi-constrained optimization problem. Recently three approaches were proposed to solve this problem, they were called AEMT, NSNP and AEMT-SND. All these approaches use a new encoding to computationally represent the electrical topology of the Distribution Systems (DSs), called Node-Depth Encoding (NDE).The AEMT combines a Multi-Objective Evolutionary Algorithm based on subpopulations tables with NDE. On the other hand, the NSNP combines NDE with a modified version of the NSGA-II (Non-Dominated Sorting Genetic Algorithm). The AEMT-SND is a combination of both AEMT and NSNP, that is, as the AEMT-SND stores the non-dominated solutions from Pareto fronts (calculated as the NSGA-II does) into additional subpopulation tables. This paper presents a comparative analysis among those three approaches applied to the power loss reduction problem in DSs. In order to do this several computational simulations were performed considering the real DS of S˜ ao Carlos-SP city and also other three DSs that were built from this real DS with size varying from two to eight times the DS of S˜ ao Carlos-SP city. Keywords— Large-Scale Distribution System, Node-depth Encoding, MOEA, NSGA-II, Network Reconfiguration Problem, Power Loss Reduction. Resumo— O problema de reconfigura¸c˜ ao de sistemas de distribui¸c˜ ao para redu¸c˜ ao de perdas de potˆ encia ´ e geralmente formulado como um problema de otimiza¸c˜ ao n˜ ao linear, multi-objetivo, combinatorial e sujeito a v´ arias restri¸c˜ oes. Para solucionar esse problema recentemente foram propostos trˆ es m´ etodos: o AEMT, o NSNP e o AEMT-SND. Todos esses m´ etodos fazem uso da estrutura de dados chamada Representa¸ca ˜o N´ o-Profundidade (RNP) para representa¸ca ˜o computacional da topologia el´ etrica dos Sistemas de Distribui¸c˜ ao (SDs). O AEMT combina o Algoritmo Evolutivo Multiobjetivo (AEMO) baseado em tabelas de subpopula¸c˜ oes com a RNP. J´ a o NSNP utiliza a RNP ´ e uma vers˜ ao modificada do NSGA-II (do inglˆ es, Non-Dominated Sorting Genetic Algorithm). Enquanto isso o AEMT-SND ´ e um novo AEMO que incorpora no AEMT elementos do NSGA-II, armazenando solu¸co ˜es n˜ ao dominadas da fronteira de Pareto (calculadas como no NSGA-II) em tabelas de subpopula¸c˜ ao adicionais. Este artigo apresenta uma an´ alise comparativa desses trˆ es m´ etodos, aplicadas ao problema de redu¸c˜ ao de perdas de potˆ encia em SDs. Para tanto, foram realizadas diversas simula¸co ˜es computacionais considerando o SD real da cidade de S˜ ao Carlos-SP e suas vers˜ oes duplicada, quadruplicada e octuplicada. Keywords— Sistema de Distribui¸ca ˜o de Grande Porte, Representa¸c˜ ao N´ o-Profundidade, MOEA, NSGA-II, Problema de Reconfigura¸ca ˜o de Redes, Redu¸ca ˜o de Perdas.

1

Introdu¸ c˜ ao

Existem diversas estrat´egias para solu¸c˜ ao do problema de redu¸c˜ ao de perdas de potˆencia em sistemas de distribui¸c˜ ao, tais como aloca¸c˜ ao de capacitores, recondicionamento de linhas de distribui¸c˜ ao, reconfigura¸c˜ ao de redes, etc. Analisando a rela¸c˜ ao custo-benef´ıcio das estrat´egias poss´ıveis para esse fim, destaca-se o processo de reconfigura¸ca˜o de redes, seguido pela aloca¸c˜ao de capacitores. Reconfigura¸c˜ ao de Redes em Sistemas de Distribui¸c˜ ao (RRSDs) ´e o processo de mudan¸ca da topologia desse sistema, por meio da altera¸c˜ao dos estados aberto/fechado das chaves seccionadoras, que pode ser utilizado para tratamento de diver-

sos problemas, como, por exemplo: redu¸c˜ao de perdas de potˆencia, aliviar componentes que estejam sobre-carregados, restabelecer energia para setores que ficaram sem energia ap´os a ocorrˆencia de faltas permanentes, dentre outros. Eis a raz˜ao de esses problemas serem chamados de problemas de reconfigura¸c˜ao de redes em sistemas de distribui¸c˜ao. Devido ao elevado n´ umero de chaves seccionadoras de um Sistema de Distribui¸c˜ao (SD), bem como `as caracter´ısticas n˜ao lineares das restri¸c˜oes utilizadas para modelar o comportamento el´etrico do sistema, RRSDs ´e um problema de otimiza¸c˜ao n˜ao linear, multi-objetivo, combinatorial com restri¸c˜oes n˜ao diferenci´aveis. Dessa forma, a solu¸c˜ao para esse problema exige a inves-

tiga¸c˜ ao do estado de diversas chaves seccionadoras. Diversos Algoritmos Evolutivos (AEs) tˆem sido desenvolvidos para tratamento dos problemas de RRSDs (Zhu, 2002; Hong and Ho, 2005). Os resultados obtidos atrav´es desses algoritmos superam os obtidos por metodologias baseadas em programa¸c˜ ao matem´ atica e t´ecnicas de inteligˆencia artificial convencional. Entretanto, a maioria dos AEs demanda um alto custo computacional (tempo de execu¸c˜ ao), quando aplicados em SDs de grande porte (Delbem et al., 2005). A fim de melhorar o desempenho dos AEs nos problemas de RRSDs, os m´etodos propostos em (Mansour et al., 2009; Santos et al., 2010; Sanches et al., 2011) usam uma nova estrutura de dados, denominada Representa¸c˜ao N´oProfundidade (RNP), e seus operadores gen´eticos (Delbem et al., 2004). Como foi mostrado em (Mansour et al., 2009; Santos et al., 2010; Sanches et al., 2011), a RNP pode melhorar o desempenho obtido pelos algoritmos evolutivos em problemas de RRSDs devido ` as suas seguintes propriedades: (i) A RNP e seus operadores produzem exclusivamente configura¸c˜ oes fact´ıveis, isto ´e, redes radiais capazes de fornecer energia para todo o sistema1 ; (ii) A RNP pode gerar muito mais configura¸c˜ oes fact´ıveis em rela¸c˜ ao ` as outras estruturas de dados para um mesmo per´ıodo de tempo, tendo em vista que a RNP apresenta uma √ complexidade computacional de ordem (O( n), onde n ´e o n´ umero de v´ertices do grafo); (iii) Cada configura¸c˜ ao gerada pela RNP e seus operadores possui todos os n´ os ordenados de acordo com uma rela¸c˜ao conhecida como Modelo Pai-Filho, possibilitando, assim, a execu¸c˜ ao de um algoritmo de fluxo de carga de varredura direta/inversa de forma mais eficiente. Trabalhando com outras estruturas de dados e operadores, antes de aplicar um algoritmo de fluxo de carga ´e necess´ ario executar um algoritmo de ordena¸c˜ ao, toda vez que uma nova configura¸c˜ ao for gerada, para organizar os n´os de acordo com o Modelo Pai-Filho (Shirmohammadi et al., 1988), (Srinivas, 2000). O m´etodo proposto em (Santos et al., 2010) usa RNP em conjunto com um Algoritmo Evolutivo Multi-Objetivo (AEMO) baseado no m´etodo de Tabelas. Ou seja, o m´etodo trabalhando em paralelo com v´ arias subpopula¸c˜ oes armazenadas em tabelas, onde as melhores solu¸c˜ oes (ou configura¸c˜ oes do SD), para cada caracter´ıstica do problema, s˜ ao armazenadas em suas respectivas tabelas. Os resultados de diversas simula¸c˜ oes computacionais apresentados em (Santos et al., 2010) demonstram que o AEMO com RNP (AEMT) ´e uma alternativa eficiente para lidar 1 O termo “todo o sistema” significa todas as partes conectadas de um SD. Em algumas situa¸c˜ oes n˜ ao ´ e poss´ıvel conectar uma ´ area fora de servi¸co em raz˜ ao da falta de chaves.

com problemas de RRSDs de grande porte. Por outro lado, o m´etodo proposto em (Mansour et al., 2009) utiliza a RNP e uma vers˜ ao modificada do NSGA-II (do inglˆes, Elitist NonDominated Sorting Genetic Algorithm). Uma das principais vantagens do NSGA-II ´e possibilitar o tratamento de v´arios objetivos sem a necessidade de fatores de pondera¸c˜ao. Os resultados de diversas simula¸c˜oes computacionais apresentados em (Mansour et al., 2009; Mansour et al., 2010) demonstram que a vers˜ao modificada do NSGAII combinado com a RNP (NSNP) ´e capaz de obter solu¸c˜oes eficientes para tratar problemas de RRSDs de grande porte em tempo real. O m´etodo proposto em (Sanches et al., 2011), denominado MEAN-SND, procura combinar os melhores aspectos dos m´etodos propostos em (Mansour et al., 2009; Santos et al., 2010). Assim como o m´etodo MEAN, o MEAN-SND trabalha em paralelo com v´arias subpopula¸c˜oes armazenadas em tabelas. Entretanto, o MEANSND faz uso de tabelas adicionais de subpopula¸c˜oes n˜ao dominadas, que armazenam as solu¸c˜oes n˜ao dominadas obtidas durante as gera¸c˜oes (calculadas da mesma forma que no NSNP). Este artigo apresenta uma an´alise comparativa dos m´etodos AEMT, NSNP e AEMT-SND, aplicadas ao problema de redu¸c˜ao de perdas de potˆencia em SDs. Para tanto, ser˜ao apresentadas diversas simula¸c˜oes computacionais considerando o SD real da cidade de S˜ao Carlos-SP e suas vers˜oes duplicada, quadruplicada e octuplicada.

2

Modelando Problemas de RRSDs

Apresenta-se, a seguir, uma formula¸c˜ao geral para problemas de RRSDs, que pode ser utilizada para formular diversos problemas. Entretanto, ser´ a tratado neste artigo o problema de redu¸c˜ao de perdas de potˆencia. Este problema consiste basicamente na determina¸c˜ao de uma configura¸c˜ao radial que minimize as perdas resistivas sem a viola¸c˜ao das restri¸c˜oes operacionais do sistema. Uma formula¸c˜ao geral para problemas de RRSDs ´e descrito em (Delbem et al., 2005) e (Santos et al., 2010), que tamb´em descrevem uma segunda formula¸c˜ao assumindo uma Estrutura de Dados Adequada (EDA) para representa¸c˜ao computacional da topologia el´etrica dos SDs, isto ´e, uma estrutura que armazena as barras de acordo com o Modelo Pai-Filho e que produza apenas configura¸c˜oes fact´ıveis. Um problema gen´erico de RRSD pode ser formulado como segue:

Min. E(F ) + |ΩI 0 (F )|

(1)

s.a. Calcular o fluxo de carga utilizando a EDA F ´e dado pelos operadores do AE atrav´es da EDA,

onde A ´e a matriz incidˆencia de F , e Yx ´e a matriz de admitˆancia diagonal), e b ´e um vetor que cont´em as correntes complexas nas barras (bk ≤ 0) ou injetadas nas subesta¸c˜oes (bk > 0). A matriz diagonal Ω ´e dada como se segue:

Onde: • F floresta de grafo correspondente a uma configura¸c˜ ao do sistema, onde: cada n´ o representa um setor e as arestas, interligando os n´ os, representam chaves seccionadoras. Consequentemente, cada ´ arvore representa um alimentador ligado em uma subesta¸c˜ ao ou em uma ´ area fora de servi¸co;

• Ω ´e uma matriz diagonal cujos elementos s˜ ao fatores de penalidade para as configura¸c˜ oes da rede que violarem as restri¸c˜oes operacionais, e | . | em 1 ´e a normaL1 de um vetor. A fun¸c˜ ao E(F ) cont´em, em geral, um ou mais dos seguintes componentes: • Φ(F ) n´ umero de barras com cargas fora de servi¸co para uma determinada topologia radial da rede (uma floresta F ); • φ(F ) perdas resistivas no sistema para F ; • ψ(F, F 0 ) ´e n´ umero de opera¸c˜ oes de chaveamento necess´ ario para obter uma dada configura¸c˜ ao F , a partir da configura¸c˜ ao F 0 .

• A m´ axima magnitude de inje¸c˜ ao de corrente bi poss´ıvel para cada subesta¸c˜ ao, onde i significa um barramento na subesta¸c˜ ao. A maior raz˜ ao B(F ) = bi /b¯i ´e denominada carregamento da subesta¸c˜ ao da configura¸c˜ ao F ; • Um limitante inferior para magnitude de tens˜ ao nodal. Seja vk a magnitude de tens˜ao nodal na barra k, e vb a tens˜ ao base do sistema; a menor raz˜ ao V (F ) = 1 − (vk /vb ) ´e denominada raz˜ ao de tens˜ ao da configura¸c˜ao F. O vetor de tens˜ ao v ´e dado por Y v = b, onde Y ´e a matriz de admitˆ ancia nodal, que pode ser calculada por meio da express˜ ao (Y = AYx AT ,



ws , se, B(F ) > 1 0, caso contr´ario;

w22 =

 w33 =

wv , se, V (F ) > 0.1 0, caso contr´ario,

onde os pesos w11 , w22 and w33 s˜ao valores positivos. Os m´etodos AEMT, NSNP e AEMT-SND utilizam a RNP como uma estrutura de dados adequada. Como alternativa, a Representa¸c˜ ao por Cadeias de Grafo foi utilizado em (Delbem et al., 2005). A literatura de AEMO mostra que fun¸c˜oes objetivo do tipo agrega¸c˜ao, como, por exemplo, E(F ) + |ΩI(F )| (equa¸c˜ao 1), para tratar problemas multi-objetivos, restringem o espa¸co de busca, podendo assim limitar a qualidade das solu¸c˜oes encontradas (Deb, 2001). V´arias abordagens tˆem sido desenvolvidas para trabalhar com v´arios objetivos e restri¸c˜oes, sem esse limite. Em (Mansour et al., 2009) a fun¸c˜ao agrega¸c˜ao foi decomposta e o problema (ver equa¸c˜ao 1) ´e reformulado como se segue:

As restri¸c˜ oes operacionais I(F ) para problemas de RRSDs geralmente incluem: • Um limitante superior para magnitude de corrente xj para cada magnitude de corrente de linha xj na linha j. A maior raz˜ ao X(F ) = xj /x¯j ´e denominada carregamento da rede da configura¸c˜ ao F ;

wx , se, X(F ) > 1 0, caso contr´ario;

w11 =

• E(F ) fun¸c˜ ao objetivo; • I(F ) restri¸c˜ oes de desigualdade representando as restri¸c˜ oes operacionais da rede;



Min. E = [e1 (F ) |ΩI 0 (F )|]

(2)

s.a. Calcular o fluxo de carga utilizando a EDA F ´e dado pelos operadores do AE atrav´es da EDA, onde E ´e um vetor de duas fun¸c˜oes objetivo: e1 (F ) ´e o n´ umero de opera¸c˜oes de chaveamentos; e |ΩI 0 (F )| ´e uma fun¸c˜ao agrega¸c˜ao composta pelas demais restri¸c˜oes operacionais e objetivos do problema. 3

Representa¸ c˜ ao N´ o-Profundidade

Um grafo G ´e um par (N (G), E(G)), onde N (G) ´e um conjunto finito de elementos denominados n´os e E(G) ´e um conjunto finito de elementos denominados arestas. Um SD pode ser representado por grafos, onde os n´os representam os setores2 e 2 Um setor corresponde a um conjunto de barras e linhas sem a presen¸ca de chaves seccionadoras.

as arestas interligando as barras representam as chaves seccionadoras. A RNP (Delbem et al., 2004) ´e uma representa¸c˜ ao de ´ arvore de grafos3 baseado nos conceitos de n´ o e profundidade de um n´ o4 de uma ´ arvore de grafo e consiste basicamente de uma lista contendo os n´ os da ´ arvore e suas respectivas profundidades, formando pares do tipo (nx; px), onde nx ´e o n´o da ´ arvore e px a profundidade do n´ o. A ordem em que os pares s˜ ao dispostos na lista ´e importante. Uma busca em profundidade em uma ´ arvore de grafo pode produzir uma ordena¸c˜ ao adequada inserindo um par (nx; dx) na lista quando o n´ o nx ´e visitado pela busca. Este processamento pode ser executado off-line. A Fig. 1.(a) representa um grafo, onde as linhas espessas indicam a ´ arvore geradora do grafo. A Fig. 1.(b) representa a correspondente RNP desta ´arvore geradora, assumindo o n´ o 1 como raiz. V´arias RNPs possibilitam a representa¸c˜ ao de uma Floresta (um SD). A estrutura de dados da floresta pode ser facilmente implementada usando uma matriz de ponteiros, onde cada ponteiro indica a RNP de uma ´ arvore (cada ´ arvore corresponderia a um alimentador do SD).

4

AEMO com RNP e Solu¸ c˜ oes N˜ ao Dominadas

Conforme apresentado em (Sanches et al., 2011), o m´etodo AEMT-SND combina as principais caracter´ısticas dos m´etodos AEMT (Santos, 2009; Santos et al., 2010) e NSNP (Mansour et al., 2009; Mansour et al., 2010) e, da mesma forma que estes dois u ´ltimos, utiliza a RNP e seus operadores. Assim como o m´etodo AEMT, o AEMT-SND ´e baseado na ideia de tabelas de subpopula¸c˜oes. Contudo, o AEMT-SND utiliza novas tabelas de subpopula¸c˜ao n˜ao dominadas que usam uma t´ecnica de n˜ao dominˆancia para inserir diversidade entre as solu¸c˜oes, como no m´etodo NSNP. Essas tabelas armazenam solu¸c˜oes n˜ao dominadas obtidas durante as avalia¸c˜oes. As tabelas de subpopula¸c˜ao relacionadas com as fun¸c˜oes objetivo e restri¸c˜oes operacionais s˜ ao preenchidas como proposto no AEMT. No entanto, as tabelas de n˜ao dominˆancia s˜ao preenchidas de acordo com o grau de n˜ao dominˆancia de cada solu¸c˜ao, isto ´e, solu¸c˜oes que n˜ao s˜ ao dominadas por nenhuma outra solu¸c˜ao s˜ao armazenadas na tabela F1 ; solu¸c˜oes que s˜ao dominadas apenas pelas solu¸c˜oes contidas na tabela F1 s˜ao armazenadas na tabela F2 ; e solu¸c˜oes que s˜ao dominadas apenas pelas solu¸c˜oes contidas nas tabelas F1 e F2 s˜ao armazenadas na tabela F3 . A fun¸c˜ao distˆancia de multid˜ao proposta em (Deb, 2001) ´e usada a fim de assegurar a diversidade entre as solu¸c˜oes contidas nas tabelas de subpopula¸c˜ao n˜ao dominadas. Alguns parˆametros devem ser estabelecidos: • Gmax ´e o n´ umero m´aximo de indiv´ıduos ger´ tamb´em utilizado ados pelo AEMT-SND. E como o crit´erio de parada;

Figura 1: Uma ´ arvore geradora de grafo e a respectiva RNP Para facilitar a manipula¸c˜ ao da floresta armazenada em RNPs, com baixo tempo de processamento computacional, criaram-se dois operadores (PAO - Preserve Ancestor Operator) e (CAO - Change Ancestor Operator). Tais operadores realizam poda ou enxerto nas ´ arvores da floresta de forma a gerar modifica¸c˜ oes na floresta. Mais informa¸c˜ oes sobre RNP e seus operadores, aplicados em problemas de RRSD, podem ser encontradas em (Santos et al., 2010). 3 Uma ´ arvore de grafo ´ e um subgrafo conexo e ac´ıclico de um grafo. 4 A profundidade de um n´ o ´ e a distˆ ancia do caminho u ´nico a partir da raiz da ´ arvore at´ e o respectivo n´ o.

• Spi ´e o tamanho da tabela de subpopula¸c˜ ao Pi , indicando quantos indiv´ıduos podem ser armazenadas em Pi , com i = 1, .., 5. As cinco tabelas de subpopula¸c˜ao Pi s˜ao: P1 indiv´ıduos com as menores perdas de potencia; P2 - indiv´ıduos com as menores taxas de tens˜ao; P3 - indiv´ıduos com os menores carregamentos de rede; P4 - indiv´ıduos com os menores carregamentos da subesta¸c˜ao; e P5 indiv´ıduos com os menores valores de fun¸c˜ ao agrega¸c˜ao. Essa fun¸c˜ao agrega¸c˜ao envolve perdas de potencia, n´ umero de opera¸c˜oes de chaveamento e restri¸c˜oes operacionais (queda de tens˜ao, carregamento de rede e carrega´ importante salienmento de subesta¸c˜ao). E tar que todas as reconfigura¸c˜oes geradas pelo AEMT-SND s˜ao fact´ıveis, isto ´e, s˜ao redes radiais capazes de fornecer energia para todo o sistema respeitando as suas restri¸c˜oes de opera¸c˜ao. • Sf i ´e o tamanho da tabela de subpopula¸c˜ ao n˜ao dominadas Fi , ou seja, indica quantos in-

div´ıduos podem ser armazenados em Fi , com i = 1, 2, 3. O algoritmo 1 descreve o pseudo-c´ odigo do AEMT-SND. Algorithm 1: Pseudoc´ odigo do AEMTSND begin Inicia o contador de gera¸c˜ ao g Gera¸c˜ ao das popula¸c˜ oes iniciais Pi (g0 ) baseado na ´ arvore geradora original F0 Avalia os indiv´ıduos da popula¸c˜ ao inicial Classifica¸c˜ ao da popula¸c˜ ao P (g) pelo algoritmo de n˜ ao dominˆ ancia Cria¸c˜ ao da tabela de n˜ ao dominˆ ancia Fi while crit´erio de parada n˜ ao ´e atingido do Selecionar estocasticamente uma popula¸c˜ ao (Pi e Fi ) Selecionar estocasticamente um indiv´ıduo(Is ) na popula¸c˜ ao selecionada Decidir por PAO or CAO e armazenas em OP Aplicar OP para produzir um novo indiv´ıduo Ig e a partir deIs Avalia o novo indiv´ıduo Ig Selecionar deterministicamente os sobreviventes de P (g) e Ig e armazenar em P (g + 1) Verificar se Ig ´e dominado pelas solu¸c˜ oes em P (g + 1) e Fi pelo algoritmo de n˜ ao dominˆ ancia Aplicar o algoritmo [crowing-distance] em Fi e Ig Atualizar as tabelas de n˜ ao dominˆ ancia Fi Incrementar o contador de gera¸c˜ ao g end

5

Estudo de Caso - Testes e Resultados

A fim de comparar os m´etodos AEMT, NSNP e AEMT-SND para tratamento do problema da RPP, o sistema de distribui¸c˜ ao real da cidade de S˜ ao Carlos (aqui chamado de Sistema 1) foi utilizado para compor outros 3 SDs: Sistema 2, Sistema 3 e Sistema 4. O Sistema 2 ´e composto por dois Sistemas 1 interconectados por 13 novas chaves NA; o Sistema 3 ´e composto por quatro Sistemas 1 interconectados por 49 chaves NA adicionais; e, finalmente, o Sistema 4 ´e composto por oito Sistemas 1 interconectados por 110 novas chaves NA (para maiores detalhes sobre esses sistemas ver (Santos et al., 2010)).

Esses SDs possuem as seguintes caracter´ısticas gerais: Sistema 1 (S1): 3.860 barras, 532 setores, 632 chaves (sendo 509 NF e 123 NA), 3 subesta¸c˜oes e 23 alimentadores; Sistema 2 (S2): 7.720 barras, 1.064 setores, 1.277 chaves (sendo 1.018 NF e 259 NA), 6 subesta¸c˜oes e 46 alimentadores; Sistema 3 (S3): 15.440 barras, 2.128 setores, 2.577 chaves (sendo 2.036 NF e 541 NA), 12 subesta¸c˜oes e 92 alimentadores; Sistema 4 (S4): 30.880 barras, 4.256 setores, 5.166 chaves (sendo 4.072 NF e 1.094 NA), 24 subesta¸c˜oes e 184 alimentadores. Os m´etodos foram executados utilizando-se um computador com processador Core 2 Quad 2.4GHz, 8GB de mem´oria RAM, Sistema Operacional Linux Ubuntu vers˜ao 10.04, e a linguagem de compilador C gcc-4.4. Os parˆametros utilizados na simula¸c˜ao foram: • NSNP: N = 200 e Gmax = 10.000; • AEMT: Sp1,..,p5 = 5 e Gmax = 100.000; e • AEMT-SND: Sp1,..,p5 = 5, Gmax = 100.000 e Sf 1 = 20, Sf 2 = 40 e Sf 2 = 20. O valor dos pesos w11 , w22 e w33 utilizados nas simula¸c˜oes foram:  100, se, X(F)> 1 w11 = 0, caso contr´ario;  w22 =

 w33 =

100, se, B(F)> 1 0, caso contr´ario;

100, se, V(F)> 0, 1 0, caso contr´ario,

O AEMT-SND ´e robusto em rela¸c˜ao a varia¸c˜oes dos pesos wii . Esses valores devem ser suficientemente altos a fim de penalizar solu¸c˜oes infact´ıveis (pesos variando de 10 a 100 s˜ao em geral adequados). O AEMT-SND utiliza duas fun¸c˜oes minimiza¸c˜ao como crit´erio de inser¸c˜ao na tabela de subpopula¸c˜ao n˜ao dominadas: (1) n´ umero de opera¸c˜oes de chaveamento e (2) fun¸c˜ao agrega¸c˜ao. Essa fun¸c˜ao agrega¸c˜ao ´e descrita a seguir: f (F ) = φ(F ) + w11 X(F ) + w22 B(F )+ +w33 V (F )

(3)

sendo que as perdas de potencia φ(F ) est˜ ao em KW, X(F ), B(F ), e V (F ) foram definidas na se¸c˜ao 2. A Tabela 1 apresenta os resultados obtidos atrav´es dos trˆes m´etodos (AEMT-SND, AEMT e NSNP) aplicados aos Sistemas 1, 2, 3 e 4. Estes resultados referem-se a porcentagem de redu¸c˜ao de

Tabela 1: RPP percentual nos Sistemas 1, 2, 3 e 4 proporcionadas pelos m´etodos AEMT-SND, NSNP e AEMT para 50 ensaios em cada um. Redu¸c˜ ao de Perdas(%) AEMT NSNP AEMT-SND Min. 13,95 12,64 15,21 M´edia 16,12 15,34 16,53 S1 Max. 16,92 16,35 16,90 DP* 0,84 0,85 0,32 Tempo(s) 30,11 8,78 23,17 Min. 14,21 11,02 14,23 M´edia 15,71 14,08 15,83 S2 Max. 16,69 15,32 16,71 DP* 0,59 0,83 0,59 Tempo(s) 34,28 13,30 28,15 Min. 13,16 8,99 19,83 M´edia 18,37 12,45 22,45 S3 Max. 22,50 15,06 24,06 DP* 2,47 1,35 1,01 Tempo(s) 34,00 16,92 30,68 Min. 17,65 4,47 21,43 M´edia 20,70 6,71 23,75 S4 Max. 24,15 7,92 25,34 DP* 1,82 0,77 0,83 Tempo(s) 27,41 19,74 30,36 *Desvio Padr˜ ao J´ a nas Figuras 2 e 3 s˜ ao ilustradas as fronteiras de Pareto encontradas pelos m´etodos AEMT-SND, AEMT e NSNP para o menor e o maior sistema simulado, ou seja, para os Sistemas 1 e 4, respectivamente. Por meio da Figura 2 ´e poss´ıvel observar que a principal contribui¸c˜ao do m´etodo AEMT ´e encontrar solu¸c˜ oes no extremo da fronteira. Por outro lado, o m´etodo NSNP

Tabela 2: Valores das perdas de potˆencia e das restri¸c˜oes operacionais resultantes da aplica¸c˜ao do m´etodo AEMT-SND para os Sistemas 1, 2, 3 e 4.

Perdas de Potˆencia [KW] Queda de Tens˜ao [%] Car. da Rede [%] Car. do Sistema [%] Perdas de Potˆencia [KW] Queda de Tens˜ao [%] Car. da Rede [%] Car. do Sistema [%] Perdas de Potˆencia [KW] Queda de Tens˜ao [%] Car. da Rede [%] Car. do Sistema [%] Perdas de Potˆencia [KW] Queda de Tens˜ao [%] Car. da Rede [%] Car. do Sistema [%]

S1

S2

S3

S4

M´edia 234,76 3,17 56,83 56,32 473,61 3,17 60,78 56,46 872,77 4,48 91,83 77,06 1716,17 4,13 97,85 87,13

DP* 0,89 0,00 1,34 0,30 3,32 0,00 1,93 0,37 11,39 1,84 13,57 16,34 18,64 1,43 2,34 10,15

pode encontrar solu¸c˜oes melhores distribu´ıdas na fronteira. A integra¸c˜ao das caracter´ısticas desses dois m´etodos, feita no AEMT-SND, resulta em uma melhor distribui¸c˜ao das solu¸c˜oes por toda a fronteira, al´em de um melhor mapeamento no extremo da mesma, alcan¸cando um maior valor de redu¸c˜ao de perdas de potˆencia. 90 NSNP AEMT AEMT−SND

80

70 NUMEROS DE MANOBRAS

perdas de potˆencia (valores m´ aximo, m´ınimo, m´edio e desvio padr˜ ao) e o tempo de processamento (em segundos) requerido por cada abordagem. Os valores foram obtidos com base nos resultados de 50 simula¸c˜ oes realizadas para cada uma das trˆes metodologias. Como pode ser observado na Tabela 1, o m´etodo AEMT-SND obteve os melhores resultados em rela¸c˜ ao ` a redu¸c˜ ao de perdas de potˆencia, encontrando valores maiores de redu¸c˜ ao de perdas para os quatro sistemas. Importa destacar o melhor desempenho da metodologia AEMT-SND para o Sistema 4, que ´e um Sistema composto por mais de 30.000 barras, aumentando ainda mais a complexidade na busca pela melhor configura¸c˜ao. Para tanto, a metodologia AEMT-SND obteve o valor m´edio de 23,75%, enquanto que os m´etodos AEMT e NSNP obtiveram 20,70% e 6,71%, respectivamente. A Tabela 2 sintetiza os resultados de perdas de potˆencia e restri¸c˜ oes operacionais obtidos pelo m´etodo AEMT-SND, que obteve o melhor desempenho para os sistemas 1, 2, 3 e 4.

60

50

40

30

20

10

0 220

230

240

250 260 PERDAS DE POTENCIA [KW]

270

280

Figura 2: Fronteiras de Pareto encontradas atrav´es do AEMT, NSNP e AEMT-SND para o Sistema 1. Na Figura 3 observa-se que, aplicado ao Sistema 4, o m´etodo AEMT-SND continua com as solu¸c˜oes distribu´ıdas por toda a fronteira, mantendo um melhor mapeamento no extremo da mesma, e, consequentemente, alcan¸cando valores maiores de redu¸c˜ao de perdas de potˆencia em rela¸c˜ao as outras duas metodologias. Entretanto, com menor saliˆencia na regi˜ao intermedi´aria. Outro aspecto importante a ser destacado na Figura 3 ´e a perda de diversidade na fronteira de Pareto do m´etodo NSNP, indicando que o

290

NSNP n˜ ao apresenta bons resultados quando aplicado em problemas mais complexos, ou seja, em sistemas de distribui¸c˜ ao com elevado n´ umero de chaves (Sistema 4). 800 NSNP AEMT AEMT−SND 700

NUMEROS DE MANOBRAS

600

500

Os resultados das simula¸c˜oes computacionais apresentados neste artigo mostraram que o AEMT-SND ´e capaz de encontrar boas solu¸c˜oes, garantindo um melhor mapeamento das solu¸c˜oes na fronteira de Pareto para SDs de grande porte. A an´alise estat´ıstica realizada a partir de 50 ensaios para cada m´etodo analisado mostra que o AEMT-SND tem um desempenho melhor do que os outros dois (AEMT e NSNP), uma vez que o AEMT-SND encontrou as configura¸c˜oes com maiores redu¸c˜oes de perda de potˆencia.

400

300

Agradecimentos

200

Os autores agradecem `a FAPESP, ao CNPq e a CAPES pelo apoio financeiro dado a esta pesquisa.

100

0 1700

1800

1900 2000 2100 PERDAS DE POTENCIA [KW]

2200

2300

Figura 3: Fronteiras de Pareto encontradas atrav´es do AEMT, NSNP e AEMT-SND para o Sistema 4.

6

Conclus˜ oes

O presente trabalho apresentou uma an´ alise comparativa entre trˆes AEMO, com RNP, para solucionar o problema da redu¸c˜ ao de perdas de potˆencia por meio de reconfigura¸c˜ ao de redes em SDs reais de grande porte (com milhares de barras e chaves). O NSNP, uma vers˜ ao modificada do NSGA-II combinado com a RNP apresentado em (Mansour et al., 2009; Mansour et al., 2010), foi capaz de encontrar solu¸c˜ oes eficientes para tratar o problema em quest˜ ao. Entretanto, quando aplicado em SDs de grandes dimens˜ oes, com grande n´ umero de barras e chaves como o Sistema 4, este m´etodo perde diversidade na fronteira de Pareto e apresenta resultados que pouco minimizam as perdas el´etrica. J´ a o AEMT, apresentado em (Santos, 2009; Santos et al., 2010), foi capaz de encontrar, nos quatro sistemas simulados, configura¸c˜ oes que proporcionaram redu¸c˜ ao de perdas de potˆencia maiores do que o NSNP. Por´em, as solu¸c˜ oes encontradas por esse AEMO se concentram nos extremos da fronteira de Pareto e com uma menor saliˆencia na regi˜ ao intermedi´ aria da fronteira de Pareto. Al´em desses dois m´etodos, foi tamb´em analisada a performance do AEMTSND, proposto em (Sanches et al., 2011). Assim como o AEMT, o AEMT-SND ´e baseado na ideia de tabelas de subpopula¸c˜ ao. Este m´etodo possui tabelas de subpopula¸c˜ ao adicionais que armazenam solu¸c˜ oes n˜ ao-dominadas (calculadas como no NSNP), chamadas tabelas de subpopula¸c˜ ao n˜ ao dominadas. Elas garantem a diversidade entra as solu¸c˜ oes melhorando significativamente o desempenho do AEMO para o problema da redu¸c˜ ao de perdas de potˆencia.

Referˆ encias Deb, K. (2001). Multi-objective optimization using evolutionary altorithms, Wiley, New York. Delbem, A. C. B., de Carvalho, A. C. P. L. F., Policastro, C. A., Pinto, A. K. O., Honda, K. and Garcia, A. C. (2004). Node-depth encoding for evolutionary algorithms applied to network design, GECCO (1), pp. 678–687. Delbem, A., de Carvalho, A. and Bretas, N. (2005). Main chain representation for evolutionary algorithms applied to distribution system reconfiguration, Power Systems, IEEE Transactions on 20(1): 425–436. Hong, Y.-Y. and Ho, S.-Y. (2005). Determination of network configuration considering multiobjective in distribution systems using genetic algorithms, Power Systems, IEEE Transactions on 20(2): 1062 – 1069. Mansour, M., Santos, A., London, J., Delbem, A. and Bretas, N. (2009). Energy restoration in distribution systems using multi-objective evolutionary algorithm and an efficient data structure, PowerTech, 2009 IEEE Bucharest pp. 1 –7. Mansour, M., Santos, A., London, J., Delbem, A. and Bretas, N. (2010). Representa¸c˜ ao n´o-profundidade e algoritmos evolutivos aplicados ao problema de reestabelecimento de energia em sistemas de distribui¸c˜ao de energia, Congresso Brasileiro de Autom´ atica, 2010 pp. 1 –7. Sanches, D., Mansour, M., London, J., Delbem, A. and Santos, A. (2011). Integrating relevant aspects of moeas to solve loss reduction problem in large-scale distribution systems, PowerTech, 2011 IEEE Trondheim, pp. 1 –6.

Santos, A. C. (2009). Algoritmo evolutivo computacionalmente eficiente para reconfigura¸c˜ ao de sistemas de distribui¸c˜ao, EESC/USP. [Online]. Dispon´ıvel em: http://www.teses.usp.br/teses/disponiveis/1 8/18154/tde-27052009-144709/pt-br.php. Santos, A., Delbem, A., London, J. and Bretas, N. (2010). Node-depth encoding and multiobjective evolutionary algorithm applied to large-scale distribution system reconfiguration, Power Systems, IEEE Transactions on 25(3): 1254 –1265. Shirmohammadi, D., Hong, H., Semlyen, A. and Luo, G. (1988). A compensation-based power flow method for weakly meshed distribution and transmission networks, Power Systems, IEEE Transactions on 3(2): 753–762. Srinivas, M. (2000). Distribution load flows: a brief review, Power Engineering Society Winter Meeting, 2000. IEEE 2: 942–945 vol.2. Zhu, J. Z. (2002). Optimal reconfiguration of electrical distribution network using the refined genetic algorithm, Electric Power Systems Research 62(1): 37–42.