X SBAI – Simpósio Brasileiro de Automação Inteligente 18 a 21 de setembro de 2011 São João del-Rei - MG - Brasil APLICAÇÃO DE ALGORITMO COLÔNIA DE FORMIGAS NA RECONFIGURAÇÃO DE REDES ELÉTRICAS DE DISTRIBUIÇÃO BENEMAR ALENCAR DE SOUZA1, JOSÉ DO PATROCÍNIO DOS SANTOS SILVA1, NIRALDO ROBERTO FERREIRA2 , LEROY UMASI RAMOS2. 1. Departamento de Engenharia Elétrica, Universidade Federal de Campina Grande Rua Aprigio Veloso, 822, 58429-900, Bodocongó, Campina Grande PB E-mails: [email protected], [email protected] 2. Departamento de Engenharia Elétrica, Universidade Federal da Bahia . Rua Aristides Novis, 02 Federação, 40210-630 Salvador-BA E-mails: [email protected], [email protected] Abstract In this article, the problem of find the optimal topological configuration of electrical distribution network is considered. The problem is formulated by taking the total active losses of the network as the objective function and equations of power flow, the capacity of the connections and the type of network configuration as constraints. To solve it we employ a heuristic inspired by the behavior of ant colony called Ant Colony Optimization – ACO. In cooperation, ants find the shortest path between the nest and a food source using a mechanism of indirect communication. A scheme in which the intermediate solutions are all feasible has been used to facilitate the search process. The algorithm was tested on a distribution network supplied by several sources, showing good results. Keywords Ant colony, ACO, Network configuration, Power flow, heuristic. Resumo O problema de encontrar a configuração ótima de uma rede elétrica de distribuição é formulado tomando a perda total de potência ativa na rede como a função objetivo e as equações do fluxo de potência, a capacidade das conexões e o tipo de configuração da rede (radial) como restrições. Para resolvê-lo emprega-se uma heurística inspirada no comportamento de colônias de formigas, chamada otimização por colônia de formigas ou ACO, do inglês ant colony optimization. Em cooperação, as formigas encontram o menor caminho entre o ninho e fontes de alimento utilizando um mecanismo de comunicação indireta. Uma estratégia de busca em que as soluções intermediárias são todas factíveis é proposta para aumentar a eficiência do algoritmo, o qual deu bons resultados ao ser testado com redes de distribuição supridas a partir de múltiplas subestações. Palavras-chave Colônia de formigas, ACO, reconfiguração de redes, fluxo de potência, heurística. 1 Introdução A maioria das redes elétricas primárias de distribuição opera na configuração radial, por questões de simplicidade operativa e para efetiva coordenação de seu sistema de proteção. Na ocorrência de uma falta, algumas chaves seccionadoras do alimentador, normalmente fechadas, são abertas para isolar os trechos afetados. Para restabelecer o serviço interrompido em decorrência das aberturas, outras chaves, normalmente abertas, são fechadas. As chaves operadas retomam à suas posições originais após a remoção da falta. Reconfiguração da rede assim, de caráter emergencial e interino, não é única. Sob condições operativas normais periodicamente promove-se a reconfiguração dos alimentadores de distribuição visando: redução das perdas de potência ativa e melhoramentos diversos: de continuidade do serviço, da confiabilidade do sistema ou do balanceamento da carga (Shirmohammadi e Hong, 1989), (Kargar et al, 2008). ISSN: 2175-8905 - Vol. X A minimização das perdas de potência ativa é um problema não linear e de natureza combinatória em razão dos estados das chaves manobráveis. Considerando-se as dimensões dos sistemas elétricos de médio e grande porte, a busca por uma solução ótima é uma tarefa árdua, pois requer a avaliação de um numero muito grande de possibilidades. Outro aspecto que eleva a complexidade do problema são os requisitos da rede ser radial e conexa (Souza et al, 2010). Diversas metodologias tem sido empregadas para lidar com o problema da reconfiguração, tais como, têmpera simulada (Cheng e Kou, 1994), algoritmos genéticos (Lin et al, 2000), métodos clássicos de otimização (Wagner et al, 1991), algoritmos evolutivos (Amasifen et al, 2005), regras heurísticas (Hsu et al, 1992) e colônia de formigas (Pereira et al, 2008). O algoritmo de formigas ou ACO foi idealizado para resolver problemas de otimização combinatória sendo inicialmente aplicado ao problema do caixeiro viajante (Dorigo e Gambardella, 1997) e depois para resolver o problema da configuração de redes (Perei- 757 X SBAI – Simpósio Brasileiro de Automação Inteligente 18 a 21 de setembro de 2011 São João del-Rei - MG - Brasil ra et al, 2008). Algumas aplicações do ACO para configurar redes foram propostas sem se desvincular do problema do caixeiro viajante, comprometendo assim a eficiência do algoritmo. Ao incorporar peculiaridades do problema na elaboração de uma versão do ACO (Souza et al, 2009), procurou-se evitar que as configurações intermediárias fossem infactíveis, porém até completá-las as formigas podiam fazer deslocamentos e cancelá-los, desperdiçando tempo de processamento. Posteriormente propôs-se um algoritmo tal que todas as soluções intermediárias eram factíveis, o que evita movimentos desnecessários das formigas e regras complicadas (Souza et al, 2010). Neste trabalho o algoritmo proposto é avaliado com novos casos, buscando verificar suas aplicabilidade e robustez, além de testar uma programação nova e mais abrangente, em Matlab®. 2 Algoritmo Colônia de Formigas 2.1 O comportamento das Formigas O ACO é uma heurística inspirada nas formigas, que conseguem descobrir os menores caminhos entre o formigueiro e uma fonte de alimento através da cooperação e de um mecanismo de comunicação indireta (Dorigo e Gambardella, 1997). Ao retornar ao ninho depois de ter encontrado uma fonte de alimento, a formiga deposita no caminho uma substância química denominada feromônio. Esta substância atrai outras formigas do ninho para a coleta do alimento encontrado. Se existirem várias trilhas de feromônio conduzindo a uma dada fonte, a seleção é probabilística com base na concentração da substância em cada uma delas. As formigas que percorrem a trilha menor até a fonte de alimento, retornam ao ninho mais cedo fazendo com que nela haja alta concentração de feromônio. Isso atrairá um grande número de formigas. Deste modo, a colônia é capaz de selecionar o menor caminho para uma determinada fonte de alimento de forma cooperativa. Tal processo é exemplificado na Figura 1. Inicialmente, as formigas partem do formigueiro de forma aleatória em busca do alimento (Figura 1a). Com o tempo, elas passam a percorrer o menor caminho, o qual é apontado pela maior concentração de feromônio (Figura 1b). formigueiro formigueiro obstáculo obstáculo fonte de alimento fonte de alimento (a) (b) Figura 1. Caminhos (a) iniciais aleatórios; (b) final e de comprimento mínimo ISSN: 2175-8905 - Vol. X 2.2 Formulação do Problema O problema de configuração ótima de redes radiais consiste em suprir n nós de carga a partir de p nósfontes mediante a ativação de n ligações das m existentes (m > n). Para a formulação do algoritmo é considerado que os nós têm estados binários e as ligações têm estados ternários: um nó pode estar ligado ou desligado, enquanto uma ligação pode ser desativada, ativável ou ativada. Durante a escolha das ligações que formam uma configuração radial, a ligação pode estar em um dos três estados, dependendo de seus nós. Se uma ligação está ativada então seus dois nós devem estar necessariamente ligados. Se inicialmente uma ligação está desativada então seus dois nós devem estar necessariamente desligados. Se uma ligação está ativável então um de seus nós deve estar ligado e o outro não. Explicando de outra forma, uma ligação está ativada quando tiver sido percorrida pela formiga. Do contrário, a ligação será considerada desativada se não há possibilidade de ser percorrida naquele instante, ou ativável se for uma das opções que a formiga tem naquele momento para seguir em sua expedição. A reconfiguração de redes de distribuição pode ser formulada como um problema de otimização não linear. Encontrar a solução consiste em selecionar dentre todas as configurações possíveis aquela em que as perdas totais de potência ativa sejam mínimas, satisfazendo a um conjunto de restrições. A capacidade de condução de corrente nas ligações é limitada, assim o problema pode ser formulado do seguinte modo: Minimizar ∆Ptotal, (1) tendo-se como restrições: i. equações de fluxo de carga, ii. capacidade das ligações Ii ≤ Imax,i , iii. configuração da rede radial. ∆Ptotal são as perdas de potência ativa totais na rede. A primeira restrição é intrínseca, haja vista que o valor da função objetivo (perdas totais de potência ativa) é calculado mediante um método computacional que tem por base as equações de fluxo. Aproveitando-se da terceira restrição emprega-se no cálculo do fluxo de carga o método da soma de potências (Cespedes, 1990), por ser de eficiência computacional reconhecida. A segunda restrição é efetiva e pode ser tratada de duas maneiras: (i) incorporando-a à função objetivo mediante funções de penalidade para onerar soluções que violem os limites impostos, tanto mais quanto maior for a violação; ou (ii) simplesmente descartando soluções que não satisfaçam os limites de capacidade dos trechos. Essa segunda alternativa é muito rígida e em geral inadequada. Portanto, se decidiu por adotar a primeira. Ou seja, o problema de otimização com restrição expresso por (1) é convertido em um problema de otimização irrestrita cuja função objetivo incorpora a restrição de corrente máxima nas ligações (Lin et al, 2000): 758 X SBAI – Simpósio Brasileiro de Automação Inteligente 18 a 21 de setembro de 2011 São João del-Rei - MG - Brasil ( F = ∆Ptotal + ∑ λ i max(0, I i − I max i ) )2 (2) i sendo λi um fator de peso, Ii a amplitude da corrente na ligação i cuja capacidade de condução é limitada em Imaxi. Os termos do somatório na expressão (2) é uma função de penalidade interior que onera toda eventual violação de restrição, tanto mais quanto maior for a violação. 2.3 Fluxo de Carga e o Cálculo das Perdas As perdas de potência são calculadas pelo método da soma de potência – MSP, um método de cálculo do fluxo de carga iterativo nas variáveis perdas de potência ativa e reativa do tipo forward-backward (Cespedes, 1990). As amplitudes das tensões de barra são calculadas seqüencialmente no sentido das subestações para as barras terminais. A tensão na barra final do trecho j depende da tensão na barra inicial i: V j = A + A2 − B , sendo A= e Vi 2 − ( R j Pj + X j Q j ) 2 B = ( R 2j + X 2j )( Pj2 + Q 2j ) . Rj e Xj são a resistência e a reatância do trecho j. Pj e Qj são os fluxos de potência ativa e reativa no fim do trecho, respectivamente. Após todas as tensões de barra ser calculadas, as estimativas das perdas de potência ativa e reativa podem ser refinadas: R( Pj2 + Q 2j ) ∆Pj = V j2 e ∆Q j = X j ∆Pj Rj . Sendo j o trecho que termina na barra j e Φ j o conjunto de todos os trechos que começam nessa mesma barra j. Então os fluxos no final do trecho j se expressam do seguinte modo: Pj = PL j + Q j = QL j + ∑ ( Pk + ∆Pk ) k ∈Φ j ∑ (Qk + ∆Qk ) k ∈Φ j sendo PL j e Q L j as potências da carga instalada na barra j, final do trecho j. No caso de j ser uma barra terminal, Φj é um conjunto vazio. Logo, Pj = PLj e Qj = QLj. Na iteração inicial consideram-se nulas as perdas de potência ativa e reativa nos diversos trechos e obtém-se uma estimativa inicial dos fluxos e do perfil de tensão. Uma iteração se completa quando o procedimento acima é repetido para todas as barras. O processo iterativo do MSP converge quando o erro absoluto percentual, entre as perdas totais de uma iteração e a ISSN: 2175-8905 - Vol. X iteração precedente é menor que uma tolerância préestabelecida. 2.4 Escolha Pseudo-Aleatória das Ligações no Percurso das Formigas A formiga escolhe a próxima barra a ser visitada com base em seu próprio conhecimento (resistência das ligações entre a barra que está e as vizinhas) e no conhecimento coletivo (quantidade de feromônio depositado em cada uma dessas mesmas ligações). O conhecimento coletivo é cumulativo, sendo alterado sempre que uma nova configuração radial se completa. A probabilidade de uma das ligações ativáveis ser escolhida por uma formiga para sair da barra em que se encontra para outra é dada pela seguinte expressão: τiα ηβi , se i ∈ Ψ α β Pi = ∑ τ j η j j∈Ψ 0 se i ∉ Ψ em que τi é a quantidade de feromônio na ligação i, ηi o inverso da resistência da ligação i, α o peso da carga de feromônio, β é o peso da resistência e Ψ o conjunto das ligações ativáveis. 2.5 Distribuição do Feromônio Tão logo as formigas completem uma configuração factível, são calculadas as perdas na rede e a carga de feromônio nas ligações ativadas da nova configuração é incrementada do seguinte modo: τi = τi + ∆τi , para ∀i ∈ Ω (3) sendo Ω o conjunto das ligações ativadas e ∆τi a carga incremental de feromônio na ligação i, que se expressa como: γ ∆τi = , F com F sendo a função objetivo (2) e γ um fator de ajuste. Assim, se consegue distinguir as soluções pela qualidade que apresentem: configurações com perdas menores, por serem soluções melhores, recebem um incremento de feromônio maior em suas ligações. Na realidade o feromônio é uma substância volátil (Dorigo e Gambardella, 1997). Essa propriedade evita que soluções antigas fiquem registradas de modo demasiadamente persistente, continuando a influenciar o processo de busca pela solução ótima e acabando por estagná-lo. A evaporação do feromônio foi incorporada ao algoritmo do seguinte modo: o número total de expedições é dividido em partes iguais denominado de ciclos, findo o qual a carga de feromônio é atualizada do seguinte modo: (1 − ρ)τi + ρ∆τi , se i ∈ Ω τi = se i ∉ Ω (1 − ρ)τi , (4) em que Ω é o conjunto das ligações ativadas da nova ligação, ∆τi é a carga incremental de feromônio na 759 X SBAI – Simpósio Brasileiro de Automação Inteligente 18 a 21 de setembro de 2011 São João del-Rei - MG - Brasil ligação i e ρ é a taxa de evaporação, um número entre 0 e 1. 2.6 Resolução do Problema com o Algoritmo de Formigas Inicialmente todos os nós-fontes estão ligados, enquanto os nós de carga estão todos desligados, de modo que nenhuma ligação está ativada. As formigas partem simultaneamente de nós ligados respeitando as seguintes regras: 1. As formigas se deslocam exclusivamente por ligações ativáveis; 2. Quando uma formiga chega ao nó desligado da ligação ativável que tenha percorrido: i. este nó torna-se ligado e a ligação ativada; ii. surge outra formiga para ocupar o nó originalmente ligado deixado por ela; 3. O percurso de uma formiga se completa quando ela não puder mais seguir por ligações ativáveis; 4. A expedição termina quando nenhuma formiga tiver mais mobilidade, ou seja, quando não houver nenhuma ligação ativável. Ao término de uma expedição sempre se terá determinado uma configuração radial. O número de formigas por expedição é variável. Começa igual ao número de nós-fontes e termina igual ao número de nós ligados. As formigas vão surgindo aleatoriamente de nós ligados e se movimentam por ligações ativáveis enquanto puderem. De acordo com as regras estabelecidas acima o ACO proposto para configuração ótima de redes de distribuição radial é aquele que se apresenta na figura 2. A carga de feromônio é atualizada aplicando-se (4) se expedição for a última de um ciclo. Do contrário se aplica (3). Início Ler os dados da rede e os parâmetros do ACO e do MSP Depositar uma quantidade inicial de feromônio τ0, em todas as liga- Incrementar o contador de expedição Incrementar o contador de expedição Fazer todos os nós-fontes ligados e os nós-de-carga desligados Executar o MSP: calcular fluxos e as perdas ativas totais Posicionar uma formiga em cada nó ligado Não Existe ligação ativável? Sim Calcular o valor da função objetivo correspondente à configuração atual empregando (2) Escolher uma das ligações ativáveis com probabilidade calculada por (8) Atualizar a carga de feromônio empregando (3) ou (4) Deslocar a formiga que esteja no nó ligado da ligação ativável selecionada e aplicar a regra 2 Não Última expedição ? Sim Apresentar a configuração radial final indicando suas ligações ativas e as perdas totais Figura 2. Fluxograma do ACO ISSN: 2175-8905 - Vol. X 3 Resultados O algoritmo de formiga foi programado em Matlab® e testado com uma rede elétrica de distribuição primária hipotética de doze barras e quatorze ligações suprida a partir de duas subestações, conforme esquematizado na Figura 3. A tensão de linha nas saídas das subestações, (barras 1 e 9), é 13,8 kV. Os dados da rede são apresentados na Tabela 1. A condição necessária, porém não suficiente para a rede ser radial é que quatro das quatorze ligações sejam desativadas, pois as barras de carga são apenas dez. Com o programa desenvolvido obteve-se a solução de perda mínima indicada na Tabela 2 e Figura 4. A tensão e os fluxos na configuração ótima são mostrados na Tabela 3 e os parâmetros do ACO empregados são mostrados na Tabela 4. Um limite para o número possível de configurações a partir da rede da Figura 3 é recomendada por Gomes (2005), ou seja, as combinações de quatorze ligações em grupo de quatro (ligações desativadas). De fato, o número de configurações radiais é bem menor. Testando cada uma das 1001 configurações obtidas ao se desativarem quatro ligações, descobriuse que apenas 373 delas são verdadeiramente radiais. As perdas totais nessa configuração ótima são de 0,4338 MW. Para se chegar a esse resultado foram realizados 20 ciclos de 10 iterações, totalizando 200 iterações. Os perfis de tensão da rede nas configurações inicial e ótima são mostrados na Figura 5 indicam uma melhoria geral nas tensões de barra em conseqüência da reconfiguração do sistema. 4 Conclusão Uma rede de distribuição primária reconfigurável suprida por múltiplas subestações foi empregado para testar o desempenho de um algoritmo de formigas com finalidade de minimizar as perdas totais de potência ativa. No início do processo a carga de feromônio é pequena e uniforme em todas as ligações da rede, prevalecendo o conhecimento individual dos agentes: escolha com base na resistência relativa das ligações. Com o decorrer das iterações há um crescimento sistemático da carga de feromônio vindo a prevalecer o conhecimento coletivo das formigas. O algoritmo tem a vantagem de gerar apenas soluções intermediárias radiais, o que reduz o espaço de Fim Figura 3. Configuração inicial da rede de distribuição a ser reconfigurada 760 X SBAI – Simpósio Brasileiro de Automação Inteligente 18 a 21 de setembro de 2011 São João del-Rei - MG - Brasil Tabela 1. Dados da rede de distribuição. de – para R, Ω 1- 2 2-3 5–4 8– 5 11 – 5 6–7 9–8 2 – 10 9 – 11 10 - 12 3–4 7–3 5 – 12 11 – 6 X, Ω 2 3 3 4 3 4 2 3 2 3 1 1 2 2 3 4 4 3 4 5 3 2 3 2 1 2 1 2 barra 2 3 4 5 6 7 8 10 11 12 – – – – Potência MW Mvar 0,4 0,6 0,6 0,5 0,6 0,4 0,8 0,2 0,9 0,1 0,8 0,2 0,7 0,1 0,7 0,4 0,8 0,2 0,6 0,5 – – – – – – – – Tabela 2. Redução de perdas com a reconfiguração da rede. Configuração Ligações desativadas Perdas, kW Redução de perdas Inicial 3, 4, 10 e 14 781,1 – Ótima 3, 5, 10 e 12 433,8 44,5% Tabela 3. Tensão e fluxo na configuração ótima. Barra 1 2 3 4 5 6 7 8 9 10 11 12 Tensão, p.u 1.0000 0.9405 0.8982 0.8923 0.9177 0.9395 0.9152 0.9620 1.0000 0.9240 0.9624 0.9079 Barra de 1 2 8 6 9 2 9 3 5 11 --- para 2 3 5 7 8 10 11 4 12 6 --- Fluxo, kW 2359.64 1203.43 1407.77 800.00 2169.55 700.00 2553.36 600.00 600.00 1717.05 --- Tensão de base: 13,8 kV. Tabela 4. Valor dos parâmetros utilizados. Parâmetros Peso da visibilidade, β Peso da carga de feromônio, α Taxa de evaporação, ρ Iterações Fator de ajuste, γ Tolerância no MSP Valor 1,0 1,0 0,10 200 10-2 10-3 Figura 4. Configuração ótima da rede busca, e está apto a lidar com redes supridas por múltiplas subestações. A técnica apresentou bom desempenho na obtenção da configuração ótima de sistemas elétricos de distribuição de pequeno porte. As pesquisas atuais são no sentido de dotar o algoritmo de eficiência em otimizar a configuração de redes de médio porte (com várias centenas de ligações). 5 Agradecimentos Este trabalho teve apoio do PROCAD/CAPES mediante concessão de bolsas de doutorado e de pósdoutorado. Também foi apoiado pelo CNPq que concedeu bolsa de iniciação científica. Os autores agradecem a essas agências. Referências Bibliográficas Amasifen, J.C.C., Romero, R., Mantovani, J.R.S. (2005). Algoritmos Evolutivos Dedicados à Reconfiguração de Redes Radiais de Distribuição sob Demandas Fixas e Variáveis – Estudo dos Operadores Genéticos e Parâmetros de Controle. Revista Controle e Automação, Vol.16 No3, PP.303-317. ISSN: 2175-8905 - Vol. X Figura 5. Perfis de tensão inicial e ótimo. R.G. Cespedes (1990). New method for the analysis of distribution networks. IEEE Trans. PWRD, vol. 5, n. 1; pp. 391-396. Cheng, H.C., Kou, C.C. (1994). Network Reconfiguration in Distribution Systems Using Simulated Annealing. Electric Power Systems Research. Vol.29, pp.227-238. Dorigo, M., Gambardella, L.M. (1997). Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem. IEEE Transactions on Evolutionary computation. Vol.1 No1, pp. 53-66. Gomes, F.V. (2005). Reconfiguração de Sistemas de Distribuição Utilizando Técnicas de Otimização Contínua e Heurística para Minimização de Custos. Tese de Doutorado, COPPE/UFRJ. Hsu,Y.Y., Huang, M.M., Kuo, H.C., Peng, S.K., Chang, C.W., Chang, K.J., Yu, H.S., Chow, C.E., Kuo, R.T. (1992). Distribution System Service Restoration Using a Heuristic Search 761 X SBAI – Simpósio Brasileiro de Automação Inteligente 18 a 21 de setembro de 2011 São João del-Rei - MG - Brasil Approach. IEEE Transaction on Power Delivery, Vol.7, No2, PP. 734-740. Kargar, H.K. (2008). Reconfiguration of large-Scale Deregulated Distribution Network for Minimizing Energy Supply Cost by Using BGA. In: The International Conference on Electrical Engineering 2008, Okinawa. Lin, W.M., Cheng, F.S., Tsay, M.T. (2000). Distribution Feeder Reconfiguration with Refined Genetic Algorithm. IEE Proceedings Generation, Transmission and Dsitribution, Vol.147 No 6, pp.349-354. Pereira, F.S., Vittory, K., Costa, G.R.M. (2008). Ant Colony Based Method for reconfiguration. In: IEEE PES Transmission and Distribution Conference and Exposition, 2008, Bogotá. Shirmohammadi, D., Honh,H.W. (1989). Reconfigu- ISSN: 2175-8905 - Vol. X ration of Electric Distribution Networks for Resistive Line Loss reduction. IEEE Transactions on Power Delivery, Vol.4 No2, pp.1492-1498. Souza, B.A., Cabral Neto, J.P., leite, M.F., Vittori, K. (2009). Configuração de Redes de Distribuição Via Algoritmo de Formigas. IX SBAI, Brasília. Souza, B.A., Silva, J.P.S., Ferreira, N.R. (2010). Configuração Ótima de Redes de Distribuição Aplicando Um Algoritmo Colônia de Formigas. In: IEEE PES Transmission and Distribution Latin America Conference and Exposition, 2010, São Paulo. Wagner, T.P., Chikhani, A.Y., Hackam, R. (1991). Feeder Reconfiguration from Loss Reduction: An Application of Distribution automation. IEEE Transactions on Power Delivery, Vol.6 No4, pp. 1922-1933. 762