Upload
ngokhanh
View
219
Download
2
Embed Size (px)
Citation preview
UNIVERSIDADE FEDERAL DA BAHIA
ESCOLA POLITÉCNICA
DEPARTAMENTO DE ENGENHARIA ELÉTRICA
PROGRAMA DE PÓS-GRADUAÇÃO EM ENGENHARIA ELÉTRICA
MIGUEL PEREIRA SANTOS NETO
RECONFIGURAÇÃO DE SISTEMAS ELÉTRICOS DE
DISTRIBUIÇÃO UTILIZANDO ALGORITMO HÍBRIDO
Salvador
2014
i
MIGUEL PEREIRA SANTOS NETO
RECONFIGURAÇÃO DE SISTEMAS ELÉTRICOS DE
DISTRIBUIÇÃO UTILIZANDO ALGORITMO HÍBRIDO
Dissertação de mestrado apresentada ao
Programa de Pós-Graduação em Engenharia Elétrica,
da Universidade Federal da Bahia, como parte dos
requisitos para a obtenção do título de Mestre em
Engenharia Elétrica.
Área de concentração: Sistemas de Potência.
ORIENTADOR: Prof. Dr. Niraldo Roberto Ferreira
Salvador
2014
ii
S237 Santos Neto, Miguel Pereira
Reconfiguração de sistemas elétricos de distribuição utilizando
algoritmo híbrido / Miguel Pereira Santos Neto. – Salvador, 2014.
f. : il. color. 94
Orientador: Prof. Dr. Niraldo Roberto Ferreira.
Dissertação (mestrado) – Universidade Federal da Bahia.
Escola Politécnica, 2014.
1. Energia elétrica - distribuição. 2. Algoritmo. 2. Redes
elétricas. I. Ferreira, Niraldo Roberto. II. Universidade Federal da
Bahia. III. Título.
CDD: 621.3192
iii
MIGUEL PEREIRA SANTOS NETO
RECONFIGURAÇÃO DE SISTEMAS ELÉTRICOS DE
DISTRIBUIÇÃO UTILIZANDO ALGORITMO HÍBRIDO
Dissertação de mestrado apresentada como parte dos requisitos para obtenção do grau de
Mestre em Engenharia Elétrica do curso de Pós-Graduação em Engenharia Elétrica da
Universidade Federal da Bahia.
Banca Examinado
Salvador, 18 de julho de 2014.
iv
Dedico este trabalho aos meus pais, aos meus familiares e
a minha esposa pela dedicação e apoio em todos os
momentos difíceis.
v
Ao Programa de Pós-Graduação em Engenharia Elétrica,
PPGEE, pela oportunidade de realização de trabalhos em
minha área de pesquisa.
Aos colegas do PPGEE pelo seu auxílio nas tarefas
desenvolvidas durante o curso e apoio na revisão deste
trabalho.
vi
RESUMO
A Reconfiguração de Sistemas Elétricos de Distribuição Radial é uma ferramenta
importante para o planejamento e/ou operação do sistema e consiste em uma técnica de
modificar a topologia da rede por meio da abertura e/ou fechamento de chaves com o objetivo
de minimizar as perdas de potência ativa do sistema. Trata-se de um problema de otimização,
sujeito a restrições de radialidade, de difícil solução devido a sua natureza discreta e
combinatorial. A explosão combinatorial para problemas dessa natureza é iminente e se
agrava à medida que o número de chaves manobráveis aumenta, causando um elevado tempo
de processamento de algoritmos que em muitos casos torna o método de otimização inviável.
Com o avanço dos sistemas digitais de processamento de dados, técnicas modernas de
otimização vêm sendo propostas baseadas em algoritmos heurísticos que utilizam a intuição a
respeito do problema e de sua estrutura para resolvê-lo de forma rápida. Com isso, neste
trabalho é apresentada uma metodologia híbrida para resolver o problema da Reconfiguração
de Sistemas de Distribuição Radial de Energia Elétrica. A estratégia consiste em combinar
técnicas, encontradas na literatura, para redução do esforço computacional e intensificação da
busca ao Algoritmo de formigas Ant System. Assim, o algoritmo híbrido (AS_hibrido),
proposto neste trabalho, foi construído por meio da associação de Metaheurísticas (Ant System
e Busca Tabu) com métodos auxiliares de simplificação de rotinas computacionais (Método
de Aceleração e Fluxo de Carga Simplificado) e estratégias de redução da convergência
prematura (Deposição exponencial do feromônio). Para testar a eficácia da metodologia
proposta foram realizados testes com sistemas de 16, 33, 69 e 84 barras, estes resultados são
comparados com os resultados encontrados na literatura. O AS_hibrido convergiu em todos
os sistemas testados com valores de perda de potência condizentes com a literatura,
apresentando redução do esforço computacional em relação a outros algoritmos testados neste
trabalho. Além disso, A metodologia de construções das configurações do AS_hibrido garante
que todas as topologias exploradas sejam puramente radiais, dispensando assim a verificação.
Palavras-chaves: Reconfiguração. Algoritmo de formigas. Ant System. Algoritmo
de formigas hibrido. Rede de Distribuição. Busca Tabu. Sistemas Elétricos de
Distribuição. Rede Radial.
vii
ABSTRACT
The Reconfiguration of Radial Distribution Systems Electrical is an important tool for
planning and/or operation of the system and consists of a technique to modify the topology of
the network by opening and/or closing keys with the goal to minimize losses active power
system. This is an optimization problem, subject to restrictions of radial, difficult to solve due
to its discrete and combinatorial nature. The combinatorial explosion for such problems is
imminent and worsens as the number of operable keys increases, causing a high time
processing algorithms that in many cases makes the method impractical optimization. With
the advancement of digital data processing system, modern optimization techniques have been
proposed based on heuristic algorithms using intuition about the problem and its structure to
solve it quickly. Thus, this work presents a hybrid methodology to solve the problem of
reconfiguration of Radial Electric Power Distribution Systems. The strategy consists in
combining methods of reducing the computational effort and the intensification of the search
algorithm Ant System. Thus, the hybrid algorithm (AS_hibrido) , proposed in this paper, was
constructed through the combination of metaheuristics (Tabu Search and Ant System) with
auxiliary methods of simplify computational routines (Method of Acceleration and Load Flow
Simplified) and strategies of reduction of the premature convergence (exponential pheromone
deposition). To demonstrate the effectiveness of the proposed methodology, tests were
performed with distribution systems of 16, 33, 69 and 84 buses, these results are compared
with results found in literature. The AS_hibrido converged in all systems tested with values of
loss of power consistent with the literature, with reduced computational effort compared to
other algorithms tested in this work. Furthermore, the methodology of building configurations
AS_hibrido ensures that all topologies explored are purely radial, thus no verification.
Keywords: Reconfiguration. Ants Algorithm. Ant System. Algorithm Hybrid
Ant. Distribution Network. Tabu Search. Electricity distribution systems. Radial
network.
viii
SUMÁRIO
1 INTRODUÇÃO ................................................................................................................ 1
1.1 O PROBLEMA DA RECONFIGURAÇÃO DE SED ................................................ 2 1.2 PROBLEMATIZAÇÃO .............................................................................................. 3 1.3 OBJETIVOS ................................................................................................................ 4
1.3.1 Gerais .................................................................................................................... 4 1.3.2 Específicos ............................................................................................................ 4
1.4 PUBLICAÇÕES E/OU SUBMISSÕES DECORRENTES DA PESQUISA .............. 4 1.5 ESTRUTURA DA DISSERTAÇÃO ........................................................................... 5
2 METODOLOGIAS PARA RECONFIGURAÇÃO DE SISTEMA ELÉTRICO DE
DISTRIBUIÇÃO ...................................................................................................................... 7
2.1 MÉTODOS HEURÍSTICOS ....................................................................................... 8
2.2 METAHEURÍSTICA COLÔNIA DE FORMIGAS ................................................... 9
2.2.1 Inspiração biológica .............................................................................................. 9
2.2.2 Comparação entre Formigas Reais e Formigas Artificiais ................................. 11
2.2.3 Breve histórico .................................................................................................... 12 2.2.4 Ant System ......................................................................................................... 13 2.2.5 Operador de Pesquisa Local do ACO com Busca Tabu ..................................... 15
2.2.6 Método de Aceleração do Algoritmo Colônia de Formigas ............................... 18 2.2.7 Método de Decaimento Exponencial do Feromônio .......................................... 21
3 FLUXO DE CARGA PARA SISTEMAS RADIAIS ................................................... 25
3.1 MÉTODO DA SOMA DE POTÊNCIAS (MSP) ...................................................... 25
3.2 MÉTODO SIMPLIFICADO ..................................................................................... 29
4 ALGORITMO HÍBRIDO PARA RECONFIGURAÇÃO DE SISTEMAS
ELÉTRICOS DE DISTRIBUIÇÃO ..................................................................................... 31
4.1 ANT SYSTEM PARA RECONFIGURAÇÃO DE REDES ..................................... 32
4.1.1 Exemplo: Sistema de 5 barras – Construção de configurações radiais .............. 36
4.2 IMPLEMENTAÇÃO DO ANT SYSTEM .................................................................. 40
4.3 ANT SYSTEM COMBINADO COM BUSCA TABU (AS_BT) ............................... 41 4.4 ANT SYSTEM COMBINADO COM MÉTODO DE ACELERAÇÃO (AS_MA) .... 45
4.5 ANT SYSTEM COM DECAIMENTO EXPONENCIAL DO FEROMÔNIO
(AS_DEF) ............................................................................................................................. 47 4.6 ANT SYSTEM COM FLUXO DE POTÊNCIA SIMPLIFICADO (AS_FS) ............. 50
4.7 IMPLEMENTAÇÃO COMPUTACIONAL DO ALGORITMO AS_HIBRIDO ..... 51
5 RESULTADO DAS SIMULAÇÕES ............................................................................ 55
5.1 SISTEMA DE 16 BARRAS ...................................................................................... 55 5.2 SISTEMA DE 33 BARRAS ...................................................................................... 58 5.3 SISTEMA DE 69 BARRAS ...................................................................................... 60
5.4 SISTEMA DE 84 BARRAS ...................................................................................... 63
6 CONCLUSÃO E SUGESTÕES PARA TRABALHOS FUTUROS .......................... 67
ix
6.1 CONSIDERAÇÕES FINAIS .................................................................................... 67
6.2 PROPOSTAS DE DESENVOLVIMENTOS FUTUROS ........................................ 68
REFERÊNCIAS BIBLIOGRÁFICAS ................................................................................. 71
APÊNDICE A ......................................................................................................................... 75
DADOS DOS SISTEMAS TESTADOS .............................................................................. 75 A1 SISTEMA DE 16 BARRAS ........................................................................................... 75
A2 SISTEMA DE 33 BARRAS ........................................................................................... 77 A3 SISTEMA DE 69 BARRAS ........................................................................................... 79 A4 SISTEMA DE 84 BARRAS ........................................................................................... 81
x
LISTA DE ILUSTRAÇÕES
Figura 1: Rota escolhida pela maioria das formigas................................................................. 10
Figura 2: Escolha da rota .......................................................................................................... 13
Figura 3: Algoritmo do ACO ................................................................................................... 15
Figura 4: Estratégia de Busca Local ......................................................................................... 16
Figura 5: (a) Trilha construída pela formiga k1, (b) Trilha construída pela formiga k2 e (c)
Trilhas frequentemente visitadas pelas formigas k1 e k2. ........................................................ 19
Figura 6: Algoritmo de aceleração combinado com ACO. ...................................................... 19
Figura 7: Processo de detecção na redução padrão. ................................................................. 20
Figura 8: Comportamento da taxa de evaporação em função de ( 0 = 0,99) ....................... 22
Figura 9: Comportamento da taxa de evaporação em função de 0 ( = 50) .......................... 23
Figura 10: Convergência do algoritmo sem a utilização do Decaimento Exponencial do
Feromônio ................................................................................................................................. 24
Figura 11: Convergência do algoritmo utilização o Decaimento Exponencial do Feromônio 24
Figura 12: Ramo de um Sistema de Distribuição ..................................................................... 26
Figura 13: Sistema de Distribuição para o exemplo do funcionamento do MSP ..................... 27
Figura 14: Estado dos nós e das ligações. ................................................................................ 33
Figura 15: Escolha aleatória das ligações ................................................................................. 34
Figura 16: Fluxograma do gerador de configurações radiais utilizando colônia de formigas. 37
Figura 17: Exploração da colônia de formigas – posicionamento inicial................................. 37
Figura 18: Exploração da colônia de formigas - 1° iteração .................................................... 38
Figura 19: Exploração da colônia de formigas - 2° iteração .................................................... 38
Figura 20: Exploração da colônia de formigas - 3° iteração .................................................... 39
Figura 21: Exploração da colônia de formigas - 4° iteração .................................................... 39
Figura 22: Fluxograma Ant System aplicado ao problema de Reconfiguração. ....................... 40
Figura 23: Configuração Radial para o Sistema de Distribuição de 16 barras ......................... 42
Figura 24: Identificação dos nós de derivação que limitam os ramos que contém as chaves
abertas ....................................................................................................................................... 42
Figura 25: Fluxograma do Algoritmo de Formigas com Busca Tabu ...................................... 44
Figura 26: Rede de quatro nós de carga e 7 ligações................................................................ 45
Figura 27: Configurações radiais obtidas da rede inicial. ........................................................ 46
Figura 28: Fluxograma do Algoritmo de Formigas com Método de Aceleração ..................... 48
xi
Figura 29: Fluxograma do AS com Decaimento Exponencial do Feromônio ......................... 49
Figura 30: Fluxograma do AS combinado com Fluxo de Potência Simplificado ................... 50
Figura 31: Fluxograma do Algoritmo híbrido AS_hibrido ...................................................... 53
Figura 32: Sistema de 16 barras – Configuração inicial. .......................................................... 56
Figura 33: Tempo de execução dos algoritmos testados para o Sistema de 16 barras. ............ 57
Figura 34: Tensões obtidas para o sistema de 16 barras........................................................... 57
Figura 35: Sistema de 33 barras – Configuração inicial. .......................................................... 58
Figura 36: Tempo de execução dos algoritmos testados para o Sistema de 33 barras. ............ 59
Figura 37: Tensões obtidas para o sistema de 33 barras........................................................... 60
Figura 38: Sistema de 69 barras – Configuração inicial. .......................................................... 61
Figura 39: Tempo de execução dos algoritmos testados para o Sistema de 69 barras. ............ 62
Figura 40: Tensões obtidas para o sistema de 69 barras........................................................... 62
Figura 41: Sistema de 84 barras – Configuração inicial. .......................................................... 63
Figura 42: Tempo de execução dos algoritmos testados para o Sistema de 84 barras. ............ 65
Figura 43: Tensões obtidas para o sistema de 84 barras........................................................... 65
xii
LISTA DE TABELAS
Tabela 1: Dados do sistema exemplo ....................................................................................... 28
Tabela 2: Resultados das iterações ........................................................................................... 29
Tabela 3: Posições da roleta ..................................................................................................... 35
Tabela 4: Arredondamento da probabilidade nas ligações ....................................................... 35
Tabela 5: Intervalos numéricos para construção da roleta ....................................................... 36
Tabela 6: Vizinhos imediatos das chave abertas ...................................................................... 43
Tabela 7: Chaves abertas após a permutação ........................................................................... 43
Tabela 8: Contabilizando a frequência de visitas nas ligações ................................................. 46
Tabela 9: Registro das ligações que alcançaram o limite de visitas nas últimas iterações....... 46
Tabela 10: Parâmetros de entrada para as simulações computacionais.................................... 55
Tabela 11: Resultados obtidos para o sistema de 16 barras ..................................................... 56
Tabela 12: Resultados obtidos para o sistema de 33 barras ..................................................... 59
Tabela 13: Resultados obtidos para o sistema de 69 barras ..................................................... 61
Tabela 14: Resultados obtidos para o sistema de 84 barras ..................................................... 64
xiii
LISTA DE ABREVIATURAS
ACO: Ant Colony Optmization
ACS: Ant Colony System
AS: Ant System
AS_ANT: Simulated Annealing combinado com algoritmo de formigas
AS_BT: Ant System combinado com Busca Tabu
AS_DEF: Ant System combinado com Decaimento exponencial do feromônio
AS_FS: Ant System combinado com fluxo de potência simplificado
AS_HIBRIDO: Ant System híbrido
AS_MA: Ant System combinado com Método de Aceleração
BT: Busca Tabu
DEF: Decaimento Exponencial do Feromônio
MA: Método de Aceleração do Ant System
MMAS: Máx-Mín Ant System
MSP: Método de Soma de Potências
MSPC: Método de Soma de Potências Completo
MSPS: Método de Soma de Potências Simplificado
PREACO: Pattern Reduction Enhanced Ant Colony Optimization
PVC: Problema do Caixeiro Viajante
RSED: Reconfiguração de sistemas de Elétricos de Distribuição
SA: Simulated Annealing
SED: Sistema Elétrico de Distribuição
1
1 INTRODUÇÃO
O Setor Elétrico Brasileiro opera, atualmente, em um modelo no qual as empresas de
energia são induzidas a propor estratégias que visem à melhoria da eficiência dos serviços de
distribuição, principalmente no que tange a confiabilidade e a redução das perdas. As perdas
representam custos adicionais para a empresa de distribuição, custos estes que não podem ser
eliminados, mas sim minimizados. Para isto, algumas técnicas podem ser utilizadas, como por
exemplo: recondutoramento, instalação de banco de capacitores, elevação da tensão da rede e
reconfiguração da rede de distribuição. Dentre estas técnicas, a opção pela reconfiguração é a
que exige menor investimento para a empresa distribuidora de energia elétrica, pois permite a
utilização de recursos já existentes no sistema, conforme GOMES (2005).
Assim, o estudo de Reconfiguração dos Sistemas Elétricos de Distribuição propõe
determinar uma topologia da rede elétrica que pode proporcionar não só redução das perdas
de potência ativa, mas também o aprimoramento de outros requisitos de desempenho do
sistema, tais como (OLIVEIRA, 2009):
Balanceamento de carga: permite aliviar alimentadores da rede com carregamento
crítico, resultando em redução de perdas, maior confiabilidade e segurança;
Isolamento de trechos: a reconfiguração permite o isolamento de um trecho da rede
que tenha apresentado defeito permanente;
Restabelecimento: consiste no retorno da rede ao estado original após o reparo de
um trecho defeituoso, através de realocação de carga;
Planejamento da operação: a reconfiguração é uma tentativa a ser considerada para
o planejamento visando a determinação da topologia da rede durante o período
diário de operação;
Planejamento de médio e longo prazo: a reconfiguração permite determinar a
topologia em que a rede irá operar no futuro, dentro de um horizonte de
planejamento de 5 a 10 anos;
Planejamento de manutenção: a manutenção de linhas de distribuição implica na
retirada temporária de serviço destas linhas, através do isolamento do trecho
correspondente;
2
Aumento das margens de carregamento: a reconfiguração permite o aumento da
margem de carregamento dos Sistemas Elétricos de Distribuição (SED),
contribuindo para a melhoria da estabilidade de tensão nestes sistemas;
Continuidade e qualidade: a confiabilidade e a qualidade do serviço de distribuição
de energia elétrica consideram a continuidade do fornecimento deste insumo.
De uma forma geral, a reconfiguração dos Sistemas Elétricos de Distribuição (SED)
pode ser usada como uma ferramenta de planejamento e/ou de controle em tempo real da
operação do sistema. A operação online requer respostas rápidas para que possam ser
tomadas as devidas ações de controle no comando automático dos sistemas. Visa-se a
restauração dos serviços pelo isolamento de zonas de fornecimento com defeitos do tipo
curto-circuito ou mesmo um balanceamento de carga com o propósito de reduzir as perdas. Já
no planejamento da operação o tempo de obtenção das respostas não assume um papel tão
importante quanto no caso anterior. No planejamento da operação buscam-se configurações
com vistas a obter uma estratégia ótima de operação com minimização de perdas, atendimento
da demanda diária com boa qualidade de serviço (perfil adequado da magnitude das tensões,
confiabilidade etc). Além da redução dos custos de operação (MANTOVANI et al., 2000).
1.1 O PROBLEMA DA RECONFIGURAÇÃO DE SED
A reconfiguração da rede é um problema que envolve a modificação do estado
(aberto-fechado) das chaves de interligação, de forma a modificar a topologia da rede. Trata-
se portanto, de um problema combinatorial1 e sujeito às restrições operacionais e de cargas. A
dimensão do espaço de busca, incluindo configurações factíveis e não factíveis, vai depender
do número de chaves manobráveis e pode ser determinado pela relação 2n, onde “n”
representa o número de chaves envolvidas na busca de uma configuração ótima. É possível
verificar por essa relação combinatória que quanto maior o número de chaves manobráveis
mais complexa e difícil se torna a resolução do problema. O crescimento do número de
possibilidades é denominado explosão combinatorial. Além disso, vale ressaltar que algumas
destas configurações não são permitidas, ou porque levam a um sistema desconectado com
várias ilhas ou a sistemas não radiais. Outras ainda não são factíveis, por violarem as
restrições operacionais e de carga do problema (AMASIFEN et al., 2005; GOMES, 2005;
DELBEM, 2002, apud PEREIRA, 2010).
1 É um problema que possui um conjunto finito de soluções viáveis, porém pode ser muito grande.
3
Devido a estes fatores, a busca examinando-se todas as configurações possíveis torna
o processo oneroso e inviável para sistemas reais (MANTOVANI et al., 2000).
Um dos primeiros trabalhos sobre reconfiguração de redes de distribuição com
objetivo de minimizar as perdas técnicas2 foi apresentado por Merlin & Back (1975),
utilizando a técnica de otimização discreta conhecida na literatura como Branch and Bound3.
Entretanto, sua aplicação para sistemas reais não é tão simples devido ao alto esforço
computacional exigido (GOMES, 2005).
Pesquisas têm sido feitas para se encontrar métodos que resolvam o problema de
reconfiguração de forma a proporcionar um esforço computacional cada vez menor. Com este
intuito, é possível encontrar na literatura alguns trabalhos que utilizam diferentes técnicas e
métodos de inteligência artificial4 aplicados a reconfiguração de redes. Alguns métodos
podem ser citados, como por exemplo, Simulated Annealing (CHANG & KUO, 1994),
algoritmo genético (AMASIFEN et al., 2005), Colônia de formigas (SU et al., 2005) e Busca
Tabu (ABDELAZIZ et al., 2010).
Dentre estes métodos, o Algoritmo Colônia de Formigas ou ACO (Ant Colony
Optmization) vem se destacando devido a sua eficiência em resolver problemas de
reconfiguração de redes. Nas últimas décadas, modificações no método vêm sendo propostas
no intuito de viabilizar a sua aplicação para sistemas de grande porte. Algumas destas técnicas
perpassam pela utilização de métodos eficientes de eliminar redundâncias computacionais,
utilização de um método simplificado de fluxo de potência, aplicação de um método de
pesquisa local e uso de estratégias que impeçam a convergência prematura do ACO. Assim, o
principal desafio consiste em melhoria da qualidade da solução e na redução do esforço
computacional.
1.2 PROBLEMATIZAÇÃO
Em relação à utilização do Algoritmo Colônia de Formigas para resolver o problema
de Reconfiguração de Sistemas Elétricos de Distribuição surgem os seguintes
questionamentos: Como reduzir o esforço computacional sem proporcionar degradação da
2 É a energia ou demanda que se perde durante seu transporte.
3 É um algoritmo para encontrar soluções ótimas em problemas de otimização, especialmente em otimização
combinatória. 4 São dispositivos computacionais que possuam ou multipliquem a capacidade racional do ser humano de
resolver problemas.
4
qualidade da solução? Quais melhoramentos podem ser obtidos no algoritmo utilizando a
Busca Tabu como método de pesquisa local? Como minimizar o efeito da convergência
prematura?
1.3 OBJETIVOS
1.3.1 Gerais
Contribuir para o estudo da reconfiguração ótima de redes em Sistemas Elétricos de
Distribuição, utilizando modelo híbrido de otimização por Colônia de Formigas com Busca
Tabu, tendo em vista a redução do esforço computacional e a obtenção de boas soluções para
o problema.
1.3.2 Específicos
Analisar as características da Reconfiguração Ótima dos Sistemas Elétricos de
Distribuição;
Estudar o método heurístico ACO e suas variantes;
Pesquisar métodos que diminuam o custo computacional do Algoritmo Colônia de
Formigas;
Analisar o algoritmo Busca Tabu para executar pesquisa local no ACO;
Descrever o fluxograma do algoritmo híbrido;
Pesquisar dados para os Sistemas Elétricos de Distribuição a fim de realizar as
simulações;
Implementar os algoritmos propostos utilizando o ambiente de programação do
Matlab;
Realizar as simulações;
Analisar os resultados.
1.4 PUBLICAÇÕES E/OU SUBMISSÕES DECORRENTES DA
PESQUISA
SANTOS NETO, M. P.; FERREIRA, N. R. Reconfiguração de Sistemas Elétricos
de Distribuição Utilizando Colônia de Formigas Combinado com Busca Tabu. In:
5
V Simpósio Brasileiro de Sistemas Elétricos-SBSE 2014, Foz do Iguaçu – PR,
2014.
SANTOS NETO, M. P.; FERREIRA, N. R. Reconfiguração de Sistemas Elétricos
de Distribuição Utilizando Algoritmo de Formigas com Método de Aceleração. In:
V Simpósio Brasileiro de Sistemas Elétricos-SBSE 2014, Foz do Iguaçu - PR,
2014.
SANTOS NETO, M. P.; SANTOS, L. L.; FERREIRA, N. R. Reconfiguração de
Sistemas Elétricos de Distribuição Utilizando Simulated Annealing Combinado
com Algoritmo de Formigas. In: V Simpósio Brasileiro de Sistemas Elétricos-
SBSE 2014, Foz do Iguaçu - PR. 2014.
SANTOS NETO, M. P.; FERREIRA, N. R. Ant System rápido com Busca Tabu
Aplicado à Reconfiguração de Sistemas Elétricos de Distribuição. In: XX
Congresso Brasileiro de Automática 2014, Belo Horizonte – MG, 2014. (Aceito
para publicação)
1.5 ESTRUTURA DA DISSERTAÇÃO
Este trabalho está estruturado da seguinte maneira: o Capitulo 1 apresenta a
introdução, o Capítulo 2 apresenta metodologias que podem ser utilizadas para reconfiguração
de sistemas elétricos de distribuição, os principais conceitos relacionados à meta-heurística
ACO, além de uma análise das estratégias fundamentais para entendimento do algoritmo
híbrido proposto; o Capítulo 3 apresenta o método para cálculo do fluxo de potência; o
Capítulo 4 apresenta a construção dos algoritmos combinados com as diversas estratégias,
culminando com a implementação do AS_hibrido; o Capítulo 5 apresenta os resultados
obtidos para os sistemas experimentais que foram adotados, bem como as comparações com
outros resultados obtidos na literatura; e, finalmente, o Capítulo 6 apresenta as conclusões
obtidas decorrentes dos resultados alcançados no presente trabalho, assim como tópicos
promissores para propostas de trabalhos futuros.
7
2 METODOLOGIAS PARA RECONFIGURAÇÃO DE
SISTEMA ELÉTRICO DE DISTRIBUIÇÃO
Os métodos de otimização baseiam-se na utilização de técnicas que tem por escopo a
otimização de alguma(s) função(ões) objetivo sujeito(s) a um conjunto de restrições.
Os problemas de otimização podem ser classificados em determinísticos (método
clássico) e não-determinísticos. O modelo é dito determinístico sempre que para um
determinado conjunto de dados de entrada se produz a mesma solução. São baseados nos
cálculos de derivadas de primeira e segunda ordem ou de uma aproximação dessas derivadas.
Possuem como limitações (MEDEIROS & KRIPKA, 2012):
Dificuldades em identificar soluções ótimas globais, pois são dependentes do
ponto de partida;
Dificuldade de trabalhar com variáveis discretas;
Dificuldade de operar com funções não diferenciáveis;
Necessidade de que a função objetivo seja contínua e diferenciável no espaço de
busca.
O modelo é dito não-determinístico se para um mesmo conjunto de dados de entrada é
possível produzir soluções distintas, pois procuram imitar fenômenos ou processos
encontrados na natureza, ou seja, são compostos por um conjunto de regras e métodos que
conduzem à resolução relativamente rápida de problemas complexos, mas não asseguram que
esta seja a melhor. Com isso, obtêm-se ganhos em termos da eficiência computacional em
detrimento da precisão das respostas encontradas. Usam somente a avaliação da função
objetivo e introduzem no processo de otimização dados e parâmetros estocásticos5, além de
não empregar o cálculo de derivadas, mas sim atuam diretamente na busca das soluções no
espaço viável (MEDEIROS & KRIPKA, 2012).
Em problemas de reconfiguração, devido à natureza discreta (chave aberta-fechada) e
à possibilidade de explosão combinatorial inerente ao modelo, a resolução do mesmo por
técnicas de otimização determinística torna-se pouco atraente, dando espaço para algoritmos
não-determinísticos baseados em heurísticas (PEREIRA, 2010).
5 São parâmetros que tem origem em eventos aleatórios.
8
2.1 MÉTODOS HEURÍSTICOS
Os métodos heurísticos podem ser definidos como sendo técnicas de procura por boas
soluções em um problema de otimização a um custo computacionalmente compensatório
(FRAGA, 2006).
Os métodos heurísticos podem ser classificados em: (FRAGA, 2006)
Heurísticas construtivas (MCDERMOTT et al., 1999) – As soluções são
construídas elemento a elemento, seguindo algum critério de classificação, até que
se tenha uma solução viável;
Heurísticas de refinamento (CHAVES et al., 2012) – Partem de uma solução
inicial viável qualquer e tentam melhorá-la através de operações diversas, até que
não seja mais possível ou exista algum outro critério de parada;
Heurísticas hibridas (ZHOU & DENG, 2009) – Combinam estratégias de duas ou
mais heurísticas;
Metaheurísticas (OLIVEIRA, 2009) – É um método heurístico utilizado para
resolver de forma genérica problemas de otimização. Utilizam combinação de
escolhas aleatórias e conhecimento histórico dos resultados anteriores adquiridos
pelo método para se guiarem e realizar suas buscas pelo espaço de pesquisa em
vizinhanças dentro do espaço de pesquisa, o que evita paradas prematuras em
ótimos locais.
Podem ser classificados com base na forma de exploração do espaço de soluções,
em pelo menos duas categorias:
Busca local – É feita através de movimentos aplicados sobre a solução corrente,
em busca de uma outra solução de melhor qualidade em sua vizinhança;
Busca populacional – Armazena um conjunto de boas soluções e as combina de
formas diversas. Esta combinação tenta reunir os bons atributos presentes nas
soluções e gerar uma outra ainda melhor.
Por se tratar de um método promissor, na literatura é possível encontrar muitos
trabalhos que utilizam as metaheurísticas para resolver problemas combinatoriais, como em
Dorigo et al. (1996) com o Ant System, Chiang e Jean-Jumeau (1990) com o Simulated
Annealling, Choi e Kim (2000) com o Genetic Algorithm, Fraga (2006) com o Tabu Search.
9
2.2 METAHEURÍSTICA COLÔNIA DE FORMIGAS
Conforme Bonebeau et al. (1999, apud FRAGA, 2006) a otimização por Colônia de
Formigas ou ACO (Ant Colony Optmization) é uma metaheurística que busca, através de
formigas artificiais, possíveis resultados, ótimos ou próximos deste, no contexto de um dado
problema.
São considerados um dos algoritmos mais bem sucedidos de inteligência coletiva, por
possuir um elevado nível de organização e tem sido aplicado em diversas classes de
problemas combinatoriais, como no problema do caixeiro viajante (DORIGO, 1992),
problema quadrático de alocação (MANIEZZO & COLORNI, 1999), problemas de
agendamento – scheduling (COLORNI et al., 1994), roteamento de veículos
(BULLNHEIMER et al., 1999), roteamento de redes (BONABEAU et al., 1998) , coloração
de grafos (COSTA & HERTZ, 1997).
Em sistemas elétricos, podem-se citar algumas de suas aplicações como alocação de
banco de capacitores (CHANG, 2008), alocação de chaves de manobras (TSENG & LIU,
2002), alocação de unidades geradoras (SISHAJ et al., 2006), despacho econômico (HOU et
al., 2002), fluxo de carga (VLACHOGIANNIS et al., 2005), planejamento de circuitos
primários (GOMEZ et al., 2004) e reconfiguração de Sistemas Elétricos de Distribuição (SU
et al., 2005).
Para se aplicar o método Ant Colony Optimization (ACO) a algum problema de
otimização combinatorial, é necessário que o mesmo possa ser descrito por um conjunto de
pontos adjacentes por onde os agentes possam se movimentar. No caso de Reconfiguração de
Sistemas Elétricos de Distribuição, estes pontos representam as barras do sistema e as arestas
que interligam estes pontos são as linhas de distribuição (PEREIRA, 2010).
2.2.1 Inspiração biológica
A observação do comportamento coletivo e o alto padrão de organização das formigas,
na natureza, chamam a atenção dos pesquisadores. Isso porque, em seu habitat natural, as
formigas sempre conseguem descobrir o menor caminho entre o formigueiro e uma fonte de
alimento. Observou-se que para alcançar este objetivo, elas utilizam da cooperação e de um
mecanismo de comunicação indireta chamada feromônio (SOUZA et al., 2010).
10
A Figura 1 ilustra o comportamento das formigas em busca da fonte de alimento. Na
figura (desde (a) até (c)), nota-se como a quantidade de feromônio (representada por linhas
tracejadas) sobre os caminhos aumenta conforme as formigas se deslocam.
Figura 1: Rota escolhida pela maioria das formigas.
(Do próprio autor)
Este comportamento pode ser descrito conforme FRAGA (2006) e PEREIRA (2010)
da seguinte forma:
Inicialmente as formigas exploram aleatoriamente a área ao redor do formigueiro à
procura de comida. Enquanto se deslocam depositam sobre o solo uma substância
volátil chamada feromônio, que as auxiliam em sua exploração. Desta forma, a
trilha ou caminho estabelecido pela formiga ficará marcado por um rastro dessa
substância química. Quando esta descobre uma fonte de alimento, retorna à
colônia seguindo este caminho, reforçando o depósito de feromônio;
As formigas que percorreram o menor caminho até a fonte de alimento, retornam à
colônia antes daquelas que escolhem caminhos mais longos. Portanto, o caminho
de menor comprimento possuirá uma maior concentração de feromônio que as
demais e, consequentemente, atrairá um número maior de formigas. As demais
formigas sentem a presença da substância química no solo e tendem a escolher o
caminho com maior concentração, reforçando o feromônio sobre ele;
11
Com o tempo, o feromônio sofre processo de evaporação e a concentração dessa
substância nos caminhos pouco visitados ou não utilizados vão diminuindo,
evitando que estes continuem a influenciar na decisão das formigas.
2.2.2 Comparação entre Formigas Reais e Formigas Artificiais
Segundo Dorigo et al. (1999) e Payá-Zaforteza et al. (2010), As formigas “artificiais”
criadas para o algoritmo proposto possuem muitas semelhanças e diferenças com relação às
formigas “reais” encontradas na natureza. Entre as semelhanças encontradas destacam-se:
Cooperação entre os indivíduos da colônia: Tanto na natureza quanto no mundo
virtual as formigas cooperam entre si através da deposição e remoção do
feromônio;
Trilha de feromônio: O feromônio depositado pelas formigas atuam nas duas
realidades, modificando o ambiente e, consequentemente, fixando o aprendizado
gerado pelas formigas;
A busca por caminhos mais curtos: As formigas virtuais ou reais partilham alguns
objetivos em comum, como encontrar o caminho mais curto;
Inteligência/coletividade: Nas duas realidades, a inteligência é obtida através da
coletividade, pois o comportamento individual é insuficiente ou aleatório;
Comportamento estocástico – A forma probabilística é característica às duas
realidades.
Entretanto as formigas “artificiais” possuem algumas características que não são
encontradas nas formigas “reais”. Sendo assim, Dorigo et al. (1999) destaca:
Natureza do movimento: Nas formigas reais, os movimentos são contínuos,
enquanto nas artificiais são discretos;
Memória: As formigas reais não possuem uma estrutura de memória como no caso
das virtuais, que as impeça de realizar movimentos;
Feromônio: O depósito de feromônio no mundo artificial ocorre com base na
qualidade da solução encontrada.
12
2.2.3 Breve histórico
A ideia surgiu com Marco Dorigo et al. (1996), por meio do algoritmo Ant System
(AS), utilizado, inicialmente, para resolver o problema do caixeiro viajante, por ser de
natureza NP-difícil6, ou seja, para solução de problemas combinacionais, e, portanto, para um
domínio de variáveis discretas (FRAGA, 2006).
A principal característica do Ant System é a atualização (incremento) do feromônio ao
final de cada ciclo somente para os agentes que conseguiram construir uma solução completa,
ou seja, uma rota/caminho interligando todas as cidades (problema do caixeiro viajante)
(PEREIRA, 2010).
A partir deste algoritmo, variantes do método foram propostos com o objetivo de
melhorar o desempenho do AS (REBELO, 2008).
A primeira melhoria introduzida, tendo como base o AS, foi chamada de estratégia
elitista. Consistia em dar um reforço adicional de feromônio aos arcos pertencentes à melhor
solução global (STÜTZLE & HOOS, 2000).
Outra importante melhoria feita no algoritmo AS foi a chamada AS rank. Nela a cada
iteração, as formigas são classificadas de acordo com sua performance e apenas uma fração
das melhores formigas poderá depositar feromônio (BULLNHEIMER et al., 1999).
Outra modificação do algoritmo AS padrão foi chamada de MAX-MIN Ant System
(MMAS). A principal característica é evitar a rápida convergência dos resultados e/ou a
possibilidade que a busca fique presa em ótimos locais. A estratégia do algoritmo é introduzir
limites máximos e mínimos à quantidade de feromônio presentes nos arcos (STÜTZLE &
HOOS, 2000).
Uma importante modificação realizada no algoritmo AS padrão é chamada de Ant
Colony System (ACS). Esta versão do ACO possui como diferencial, o fato de introduzir a
atualização local do feromônio. Esta atualização é feita sempre ao final de cada transição do
agente (STÜTZLE & HOOS, 2000).
6 São os problemas não-polinomiais em que não se conhece uma solução determinística capaz de ser executada
em tempo polinomial.
13
2.2.4 Ant System
Para entender o funcionamento do método ACO, a seguir é apresentado a formulação
do algoritmo Ant System aplicado ao problema do caixeiro viajante (PCV).
Na construção da rota, cada formiga deve escolher um caminho, dentre as
possibilidades de trilhas, tendo como base o seu conhecimento individual (distância entre as
cidades) e coletivo (quantidade de feromônio depositado nas ligações), conforme Figura 2. A
cada iteração o conhecimento coletivo é atualizado.
Figura 2: Escolha da rota
(Do próprio autor)
A escolha, então, deve ser feita de forma probabilística. Com isso, a probabilidade de
um agente k que se encontra em uma cidade j, possuindo Ψ (conjunto de cidades vizinhas de j
que não foram visitadas pelo agente k), visitar uma cidade z utilizando uma determinada trilha
é dada pela equação de transição (1):
zse
zse
ljljl
jzjz
kjz
P
0
,
(1)
onde Pkjz é a probabilidade do agente k visitar uma cidade z utilizando a trilha jz; τjz é a
quantidade de feromônio sobre a trilha jz; ηjz é uma informação heurística dada pelo inverso
da distância entre as cidades jz; α e β os pesos atribuídos ao feromônio e a informação
14
heurística, respectivamente e j compreende a cidade onde a formiga se encontra em um
determinado instante (PEREIRA, 2010).
Com base na equação (1) é possível verificar que a probabilidade de escolha de um
caminho é proporcional ao rastro de feromônio e a atratividade7 do mesmo. Em uma rápida
análise dos pesos, α e β, que podem ser atribuídos à quantidade de feromônio e à informação
heurística, respectivamente, é possível verificar que se α=0, então será considerado apenas a
distância entre as cidades, podendo proporcionar soluções de baixa qualidade. Por outro lado,
se for considerado β=0, estaria levando em consideração apenas a quantidade de feromônio, o
que poderia causar uma convergência prematura do método. Em ambos os casos, as rotas
encontradas poderiam não ser ótimas (BONABEAU; DORIGO; THERAULAZ, 1999, apud
PEREIRA 2010).
Após os agentes completarem um ciclo, as rotas interligando todas as cidades terão o
feromônio atualizado sobre os seus caminhos, conforme equação (2), também conhecida
como atualização global.
Na
k
kjz
jzjz
1
)()1()( (2)
Obedecendo ao critério estabelecido na equação (3):
contráriocaso
rotasuanajzconexãoautilizoukagenteose
kD
Q
kjz
,0
,
(3)
Onde ρ (0 , 1] é a taxa de evaporação do feromônio, Na é o número de formigas,
é a quantidade de feromônio deixada pelo agente k no percurso da rota jz, Q é um
parâmetro definido empiricamente de acordo com as características do problema e Dk é o
comprimento da rota construída pelo agente k.
A taxa de evaporação é utilizada para remover parte do feromônio, reduzindo a
quantidade da substância nos arcos. Isso evita que as formigas fiquem presas em ótimos locais
7 Característica que determina a capacidade das trilhas em atrair as formigas, representado pela informação
heurística.
15
e, ao mesmo tempo, diminui a probabilidade de escolha de arcos que não foram atualizados
recentemente (FRAGA, 2006).
O cálculo da informação heurística para o caso do caixeiro viajante pode ser
determinada fazendo:
jzdjz
1 (4)
Onde djz é a distância entre as cidades interligadas pela ligação jz.
A atualização tem como objetivo concentrar a pesquisa em regiões do espaço de busca
com distâncias reduzidas.
De forma geral, o pseudocódigo do ACO pode ser resumido conforme algoritmo da
Figura 3:
Figura 3: Algoritmo do ACO
(TSENG et al., 2010)
Uma vez que as soluções foram construídas, podem-se aplicar ações opcionais
chamadas busca local (TSENG et al., 2010).
2.2.5 Operador de Pesquisa Local do ACO com Busca Tabu
De um modo geral, a busca local no ACO pode ser usada de forma opcional para
melhorar a qualidade da solução. A estratégia é ilustrada na Figura 4.
O principal inconveniente das buscas locais é a estagnação em ótimos locais (uma
solução que é melhor que qualquer da sua vizinhança) e assim a solução atual fica presa em
sua vizinhança. Então surgem três principais formas de sair desta situação (ZVIETCOVICH,
2006):
1. Inicializar parâmetros e matrizes
2. Enquanto a condição não for satisfeita faça
3. s = Construir soluções
4. τ = Atualizar feromônio
5. Pesquisa local
6. End
7. Retornar solução
16
Voltar e começar a busca a partir de outra solução inicial – É adequado naqueles
casos em que os ótimos locais se distribuem aleatoriamente no espaço de soluções.
Porém, em muitos casos se observa que os ótimos locais tendem a concentrar-se
em pequenas regiões no espaço de soluções, o que dificulta a obtenção da solução
ótima;
Permitir movimentos de deterioração da solução atual – Essa estratégia consiste
em aceitar soluções correntes que sejam piores que a melhor solução atual segundo
algum critério de aceitação pré-estabelecido;
Modificar a estrutura da vizinhança – Consiste na utilização de alguma
metaheurística com o objetivo de melhorar o algoritmo de busca local, evitando
que o procedimento fique preso em um ótimo local.
Nos últimos anos a metaheurística Busca Tabu vem se destacando, dentre as
heurísticas de melhoramento, por se mostrar um método eficiente, dotado de memória
adaptativa de curto e longo prazo (GUIMARÃES & CASTRO, 2005).
Solução inicial Si fornecida
por algum algoritmo de
construção.
Encontrar Sv correspondente a
melhor solução da vizinha de Si.
Sv ϵ N(Si)
Sv é melhor
que Si?
Fim
não
Início
Si = Svsim
Figura 4: Estratégia de Busca Local
(Tseng et al., 2010)
O algoritmo de Busca Tabu (BT) é um procedimento adaptativo, utilizado em
conjunto com outros métodos heurísticos, os guiando para a superação das limitações dos
ótimos locais, ou seja, oferece uma exploração contínua dentro de um espaço de busca, além
17
de forçar o algoritmo a explorar novas áreas, evitando a convergência prematura em ótimos
locais. Tem a sua forma básica estruturada nas ideias de Glover (1989, 1990) e é baseado em
procedimentos heurísticos8 que permitem explorar o espaço de busca e encontrar novas
soluções além daquelas encontradas em uma busca local.
A BT consiste de movimentos que partem de uma solução corrente em busca de outras
soluções até que o critério de parada seja satisfeito. Cada solução x dentro do espaço de busca
Y (x ϵ Y), tem uma solução vizinha N(x), tal que N(x)Y, e cada solução vizinha x’ ϵ N(x) é
alcançado partindo de x por uma operação chamada movimento.
Usualmente os sistemas de distribuição operam na forma radial por serem mais
econômicos e mais simples de serem projetados. Com isso, uma solução para este problema x
pertencente ao espaço de busca Y (x ϵ Y) deve incluir a restrição da radialidade. A restrição
da radialidade é um problema de difícil representação matemática e, por isso deve ser tratado
adequadamente tendo o intuito de não gerar esforço computacional excessivo devido às
verificações de radialidade, ou seja, deve possuir um método eficiente de gerar novas soluções
que sempre sejam radiais.
Segundo Guimarães e Castro. (2005), o algoritmo BT é diferente de um algoritmo de
busca local, pois permite o uso inteligente do histórico da pesquisa para influenciar os seus
procedimentos de busca do futuro, devido à diversificação do procedimento. Esta estratégia é
obtida por meio do uso de uma memória constituída por duas listas que podem ser:
Lista Tabu – É a memória de curto prazo, onde contêm as soluções recentemente
visitadas. Assim, quando novas soluções surgem e são melhores que as
armazenadas anteriormente, a solução armazenada é retirada da memória e
armazenada a nova solução;
Lista Elite – É a memória de longo prazo, onde são armazenadas as melhores
soluções visitadas.
Durante a procura por um ótimo global, o algoritmo mantém duas listas: Lista Elite
(memória de longo prazo) e Lista tabu (memória de curto prazo). As melhores soluções
visitadas são armazenadas na Lista Elite. A Lista Tabu contém as soluções recentemente
visitadas. Todas as vezes que uma nova solução ou um movimento é feito, ele é comparado
com as soluções gravadas na Lista Tabu. Se a nova solução está na Lista Tabu ela é
8 Um algoritmo é heurístico quando utiliza a intuição a respeito do problema e de sua estrutura para resolvê-lo de
forma rápida.
18
considerada ilegal e então é descartada. Esta estratégia impede o retorno a configurações
anteriormente visitadas evitando ciclagem. As soluções são mantidas na Lista Tabu durante
um certo número de operações conhecido com Período Tabu. À medida que as iterações
prosseguem, soluções antigas são apagadas da Lista Tabu enquanto as novas são incorporadas
nela.
Em alguns casos o número de configurações vizinhas pode ser muito grande, e avaliar
a função objetivo de cada uma dessas configurações para encontrar aquela que apresente
melhor desempenho, pode demandar um elevado esforço computacional. Por isso, pode ser
utilizada a estratégia de diminuir o tamanho da vizinhança, ou da lista de configurações
candidatas, visando diminuir este esforço.
A definição e caracterização eficiente da vizinhança de uma configuração
proporcionam que a busca continue além do mínimo local, permitindo movimentos que não
aprimoram o valor da função objetivo, além de modificações na estrutura da vizinhança de
soluções subsequentes, entretanto isso depende do problema.
2.2.6 Método de Aceleração do Algoritmo Colônia de Formigas
A constante busca pelo melhoramento do método ACO atrai, cada vez mais
pesquisadores, a estudar estratégias que possam ser incorporadas a este algoritmo com o
objetivo de reduzir o esforço e o tempo computacional. Nesse intuito, (TSENG et al., 2010)
apresentou um algoritmo de aceleração aplicado ao problema do caixeiro viajante que,
incorporada ao ACO, possibilita a diminuição da redundância de cálculos durante o processo
de convergência e ,consequentemente, redução significativa no tempo computacional.
A proposta do algoritmo é motivada pela observação de que trilhas que possuem
pouca tendência de modificar durante o processo de formação, podem ser consideradas como
parte das soluções finais e, portanto, podem ser comprimidos e removidos para eliminar a
redundância computacional nas iterações posteriores (TSAI et al., 2009).
A Figura 5 mostra um exemplo de redundância de movimentos que podem ocorrer
durante a iteração “N” de duas formigas k1 e k2 (TSENG et al., 2010).
Para o problema do caixeiro viajante, numa excursão de 5 cidades, realizadas por duas
formigas, a Figura 5 mostra em (a) a exploração da formiga k1, construindo o caminho 1-2-5-
3-4-1, enquanto em (b) a formiga k2 em sua exploração constrói o caminho 1-3-2-5-4-1 e
19
finalmente em (c) temos a trilha 1-4 e 2-5 sendo usadas pelas duas formigas. O ideal seria não
repetir a rotina de cálculos, ou seja, se a ligação for frequentemente visitada, então pode ser
ocultada do espaço de busca para evitar redundância computacional (TSENG et al., 2010).
Figura 5: (a) Trilha construída pela formiga k1, (b) Trilha construída pela formiga k2 e (c)
Trilhas frequentemente visitadas pelas formigas k1 e k2.
Adaptado de (TSENG et al., 2010)
O algoritmo de aceleração tem por objetivo identificar estas ligações visando redução
do tempo computacional. O algoritmo pode ser visto na Figura 6:
Figura 6: Algoritmo de aceleração combinado com ACO.
(TSENG et al., 2010)
Comparando o algoritmo apresentado na Figura 6 com o algoritmo padrão do ACO
Figura 3, verifica-se a introdução de uma rotina na linha 6, chamada Redução Padrão. O
procedimento do algoritmo de redução padrão é composto por três operações, conforme
(TSAI et al., 2013):
Detecção: Tem a responsabilidade de detectar as subsoluções que possuem a
tendência de não serem modificadas, devido ao fato destas arestas estarem sendo
visitadas com maior frequência;
Compressão: Responsável por armazenar as subsoluções detectadas pelo
procedimento anterior;
1. Inicializar parâmetros e matrizes
2. Enquanto a condição não for satisfeita faça
3. s = Construir soluções
4. τ = Atualizar feromônio
5. Pesquisa local
6. Redução padrão
7. End
8. Retornar solução
20
Remoção: Responsável por retirar as subsoluções detectadas e comprimidas nos
procedimentos anteriores, do espaço de busca do AS.
O operador de detecção é responsável pela identificação das ligações que possuem alta
probabilidade de fazer parte da solução final. A Figura 7 mostra o algoritmo de redução
padrão:
Figura 7: Processo de detecção na redução padrão.
(TSENG et al., 2010)
Onde n é o comprimento da solução, υ é a matriz registradora de visitas das formigas,
ω é o limite usado para determinar se uma ligação ejz pode ser comprimida, ζ é a matriz
registradora das ligações que alcançaram o limite de visitas (ligações comuns). O limite ω
pode ser estabelecido pela quantidade de formigas m que atravessam uma determinada
ligação em um determinado intervalo de iterações π, ou seja, para uma quantidade π de
iterações é verificado quais ligações alcançaram o limite ω de visitas. Modificando os
parâmetros m e π poderemos estabelecer o limite adequado para melhor eficiência do
algoritmo. Dessa forma, quanto menor o valor de ω mais rápido o algoritmo AS converge, por
outro lado, pode proporcionar redução da qualidade da solução. (TSENG et al., 2010).
O registro de quantas vezes cada ligação é atravessada pelas formigas é feita por meio
da matriz υ, como mostrado nas linhas 2 à 4. A atualização desta matriz é feita a cada
expedição do algoritmo AS até que se atinja o intervalo π iterações. Atingido o limite de
iterações, a matriz υ será inicializada para nova contabilização de visitas, ou seja, o intervalo
de iterações (π) é um parâmetro estabelecido para inicialização da contabilização de visitas
nas ligações dado pela matriz υ.
Para cada expedição do AS, a matriz υ é analisada para verificar quais ligações
alcançaram o limite pré-estabelecido ω de visitas. Se uma ligação da matriz υ possuir um
1. % Registrar o número de vezes que cada ligação é atravessada
2. Para i=1:n
3. υjz υjz+1
4. Fim para i
5. % Fazer as ligações atravessadas ω ou mais vezes como comuns
6. Para cada ligação ejz
7. Se υjz ≥ ω
8. ζjz1
9. Fim se
10. Fim para
21
número de visitas maior ou igual ao limite pré-estabelecido ω, então esta ligação será
considerada uma das componentes da solução do problema.
O registro das ligações que alcançaram o limite ω é realizado por meio da matriz ζ, de
forma que, se υjz for maior que ω, então ζjz 1, como descrito nas linhas 6 à 10.
Uma vez conhecida a matriz ζ, o próximo passo é comprimir e remover estas
subsoluções. O primeiro e importante passo é modificar o cálculo da probabilidade expresso
na equação (1), para garantir que o AS sempre selecione a ligação que tenha alcançado
ζjz 1, por esta ter uma alta probabilidade de ser parte da solução final (TSENG et al., 2010;
TSAI et al., 2013).
Dessa forma, o método de cálculo da probabilidade do ACO expresso pela equação (1)
deve ser modificado, como mostrado na equação (5):
zse
zse
ljljl
jzjz
jz
kjz
P
,0
,
1,1
(5)
Esta modificação, mostrada na equação (5), garantirá que o ACO sempre escolherá a
ligação jz comum, se , e assim ter uma alta probabilidade de ser uma solução parcial.
Ou em outras palavras, o algoritmo será forçado a selecionar uma determinada ligação jz para
ser a próxima subsolução se (TSENG et al., 2010; TSAI et al., 2013).
2.2.7 Método de Decaimento Exponencial do Feromônio
Em SHERAFAT et al. (2008) é proposto uma modificação na forma de evaporação do
feromônio depositado pelas formigas durante a execução do algoritmo. O método está
baseado em utilizar uma função exponencial na equação (2). A escolha pela função
exponencial é bastante propícia, devido à possibilidade de gerar valores da taxa de evaporação
compreendidos no intervalo [0,1] com velocidade de crescimento controlado para evitar a
convergência prematura. A modificação da taxa de evaporação é calculada pela equação (6).
22
),(exp0
1
t
t
(6)
onde, t representa o passo de tempo (número de iterações), t é a taxa de evaporação que
decresce com o tempo, 0 e são constantes que dependem do problema. Estes valores são
escolhidos de acordo com a dimensão do problema e devem ser atribuídos e simulados até se
obter os parâmetros adequados para o problema.
Uma análise mais detalhada do comportamento de t na equação (6) pode ser feita
simulando para diversos valores de 0 e .
A Figura 8, ilustra a variação da taxa de evaporação mantendo 0 constante e
modificando o parâmetro . Assim, para valores maiores de , o valor da taxa de evaporação
tende a um crescimento mais lento.
Figura 8: Comportamento da taxa de evaporação em função de ( 0 = 0,99)
(Do próprio autor)
A Figura 9, ilustra o comportamento de t mantendo constante. Dessa forma, para
valores maiores de 0 , a taxa de evaporação tende a iniciar em valores próximos a zero. Neste
trabalho, utilizaram-se valores de 0 compreendidos no intervalo [0,85; 0,99].
0
0,1
0,2
0,3
0,4
0,5
0,6
0,7
0,8
0,9
1
1,1
1
24
47
70
93
11
6
13
9
16
2
18
5
20
8
23
1
25
4
27
7
30
0
32
3
34
6
36
9
39
2
41
5
43
8
46
1
48
4
50
7
53
0
55
3
57
6
59
9
Taxa
de
eva
po
raçã
o
N° de iterações
ф=50
ф=100
ф=200
ф=300
ф=600
23
A utilização da equação (6) faz com que o algoritmo evite convergências prematuras e
consequente estagnação, principalmente para problemas com número maior de nós.
Figura 9: Comportamento da taxa de evaporação em função de ρo ( = 50)
(Do próprio autor)
Com isso, nas primeiras iterações a evaporação do feromônio será mais lenta,
propiciando uma exploração mais intensa no início das iterações. Esta característica deve-se
ao aumento da aleatoriedade na escolha das trilhas durante a construção da rota. Com o
tempo, a taxa de evaporação do feromônio vai aumentando gradativamente devido à variação
exponencial de t .
Os gráficos da Figura 10 e Figura 11 mostram o comportamento do algoritmo, durante
a exploração do espaço de busca, sem a utilização da técnica de Decaimento Exponencial do
Feromônio e com a utilização do método, respectivamente. No primeiro caso, a exploração
tende a explorar um espaço de busca reduzido, por conta do fortalecimento excessivo e
prematuro de feromônio em determinadas trilhas, reduzindo a eficiência do algoritmo de
formigas para sistemas que requerem muitas explorações. No segundo caso, devido ao
decaimento exponencial do feromônio, o algoritmo mantem uma exploração maior do espaço
de busca em comparação com o primeiro caso, devido à forma de evaporação do feromônio,
assim, como resultado o algoritmo irá minimizar o efeito da convergência prematura.
Com a utilização do método de Decaimento Exponencial do Feromônio, o algoritmo
apresenta um comportamento exploratório do espaço de busca maior quando comparado ao
0
0,1
0,2
0,3
0,4
0,5
0,6
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Taxa d
e ev
ap
ora
ção
N° de iterações
ρo=0,7
ρo=0,80
ρo=0,90
ρo=0,99
24
algoritmo com taxa de evaporação constante. Esse fato deve-se à minimização da evaporação
excessiva do feromônio nas ligações, evitando que o algoritmo fique preso em soluções
locais. Esse fato faz com que o algoritmo explore mais o espaço de busca ampliando as
chances de encontrar soluções melhores.
Figura 10: Convergência do algoritmo sem a utilização do Decaimento Exponencial do
Feromônio
(Do próprio autor)
Figura 11: Convergência do algoritmo utilização o Decaimento Exponencial do Feromônio
(Do próprio autor)
25
3 FLUXO DE CARGA PARA SISTEMAS RADIAIS
O cálculo do fluxo de carga em problemas de reconfiguração de redes é parte
fundamental para o desempenho eficiente do método, devido à necessidade de avaliar a
função objetivo (calcular as perdas de potência ativa) para cada configuração gerada pelo
algoritmo, o que proporciona um elevado esforço computacional ao método. Por isso, é
necessário utilizar um método de fluxo de potência rápido e eficiente (RUDNICK et al.,
1997).
De uma forma geral, os métodos de cálculo do fluxo de carga tradicionais9 não são
adequados para serem aplicados em sistemas de distribuição. Assim, é necessário adaptar,
para os sistemas de distribuição, um método de cálculo que tenha características específicas,
como: (i): Operação em configuração radial, (ii) Relação entre a resistência e reatância (R/X)
elevada, comparados com os valores típicos encontrados em sistemas de sub-transmissão e
transmissão. A primeira característica é uma vantagem porque simplifica consideravelmente a
complexidade do problema, entretanto, a segunda característica é uma desvantagem porque
pode produzir divergência quando utilizam-se métodos tradicionais como o de Newton10
(ZVIETCOVICH, 2006).
No nosso trabalho utilizamos o Método de Soma de Potências (MSP) proposto em
(SOUZA et al., 2010) para o cálculo do fluxo de carga para redes de distribuição radiais, por
ser um método eficiente. Utilizamos também um método simplificado do MSP, baseado em
(BARAN & WU, 1989), para avaliar de forma ainda mais rápida a qualidade de uma operação
de chaveamento candidata durante o procedimento de reconfiguração.
3.1 MÉTODO DA SOMA DE POTÊNCIAS (MSP)
Trata-se de um método eficiente na resolução de problemas de fluxo de carga radial e
relativamente simples de programar (LORENZETI, 2004).
O MSP é um método de cálculo de fluxo de carga iterativo nas variáveis perdas de
potência ativa e reativa do tipo forward-backward. Ou seja, se começa supondo que as perdas
em todos os trechos são nulas (ou tenha outro valor qualquer) e em cada iteração as
estimativas dessas perdas vão melhorando. Com a tensão da barra da subestação sendo dada e
9 Como o método de Gauss-Seidel, Newton-Raphson, desacoplado Rápido etc.
10 Mais informações sobre o método pode ser encontrada em (GOMES, 2005)
26
as perdas consideradas nulas, se calcula a tensão em todas as barras ligadas diretamente à
subestação. Depois, se calculam as tensões em todas as barras ligadas àquelas que estão
ligadas diretamente à subestação (cujas tensões já foram calculadas) e assim por diante. Findo
esse primeiro estágio (forward) se tem valores aproximados de todas as tensões de barra.
Aproximados porque foram calculados supondo que as perdas eram nulas. Com os valores de
tensão conhecidos, se calculam as perdas em todos os trechos e então se corrigem os fluxos
num processo backward. O processo completo (forward-backward) continua enquanto a
variação nas perdas totais for maior que uma tolerância previamente escolhida ou se
eventualmente o limite de iterações for excedido (SOUZA, 2005).
Supondo uma ligação m iniciando em nó i e chegando ao nó j e Ψ um conjunto de x
ligações partindo do nó j, conforme Figura 12.
Figura 12: Ramo de um Sistema de Distribuição
(Do próprio autor)
Então os fluxos no final do trecho j se expressam do seguinte modo, equações (7) e
(8):
,)(
xx
Px
P
jL
Pm
P (7)
,)(
xx
Qx
Q
jL
Qm
Q (8)
em que, Pm e Qm é o fluxo de potência ativa e reativa no fim da ligação m, PLj e QLj é a
potência ativa e reativa instalada na barra j, Px e Qx é a potência ativa e reativa instalada na
barra localizada no final da ligação x e ΔPx e ΔQx é a perda de potência ativa e reativa na
ligação x, respectivamente .
Se o nó for terminal, então Ψ é um conjunto vazio. Além disso, se for a iteração inicial
consideram-se nulas as perdas de potência ativa e reativa.
A tensão no nó j depende da tensão no nó inicial i e se expressa da seguinte forma:
27
,2 BAA
jV
(9)
sendo,
,)(2
2
mQ
mX
mP
mRi
VA (10)
,)22()22(m
Qm
Pm
Xm
RB (11)
em que Rm e Xm é a resistência e a reatância da ligação m.
Após todas as tensões terem sido calculadas, os fluxos nos diversos trechos podem ser
obtidos considerando as estimativas das perdas de potência ativa e reativa.
2
)22(
jV
mQ
mPR
mP
(12)
m
R
mP
mX
mQ
(13)
O processo iterativo do MSP converge quando o erro absoluto entre as perdas totais de
uma iteração e a iteração precedente é menor que uma tolerância pré-estabelecida.
Para melhor entendimento do princípio de funcionamento do método adotaremos o
exemplo encontrado em Souza (2005) que consta de um pequeno sistema de distribuição,
conforme Figura 13. Os dados deste sistema podem ser vistos na Tabela 1.
Figura 13: Sistema de Distribuição para o exemplo do funcionamento do MSP
(SOUZA, 2005)
Desprezando-se inicialmente todas as perdas, o fluxo no final do trecho 1,
compreendido entre as barras 0 e 1, é simplesmente a soma de todas as cargas instaladas:
P1 = 1,76 MW e Q1 = 1,32 MVAr.
28
Tabela 1: Dados do sistema exemplo
(SOUZA, 2005)
De Para R (Ω) X (Ω) PL (kW) QL (kVAr)
0 1 3 4 0,64 0,48
1 2 4 5 0,8 0,6
1 3 4 3 0,32 0,24
Para o cálculo da tensão na barra 1, procede-se calculando as variáveis auxiliares:
66,84)32,1476,13(2
28,13A
121)232,1276,1()2423( B
A tensão na barra 1 é:
kVV 985,1212166,8466,84
Conhecendo-se a tensão na barra 1, procede-se de forma similar para o calculo das
tensões nas demais barras. Assim, para a barra 2:
1012,78)6,058,04(2
2985,12A
41)26,028,0()2524( B
kVV 488,12411012,781012,78
Os fluxos no fim dos trechos 2 e 3, por serem trechos terminais, são sempre iguais às
cargas instaladas em suas respectivas barras finais.
Para a iteração 1, as perdas são corrigidas a partir das tensões calculadas na iteração 0.
Dessa forma, as perdas no trecho 1 passam a ser:
MWP 08612,02985,12
)232,1276,1(3
1
MVArQ 11482,03
08612,04
1
O método iterativo prossegue até que o critério de parada seja satisfeito. Para o
exemplo, o método converge em três iterações com tolerância de 10-3
, conforme Tabela 2.
29
Tabela 2: Resultados das iterações
(SOUZA, 2005)
ΔP ΔQ P Q A B V Iterações
0 0 1,76 1,3200 84,66000 121,0000 12,985
0 0 0 0,80 0,6000 78,10117 41,0000 12,488
0 0 0,32 0,2400 82,30117 4,0000 12,829
0 0 - - - - -
0,0861 0,1148 1,7895 1,3550 84,4315 125,9606 12,966
1 0,0257 0,0321 0,8000 0,6000 77,8568 41,0000 12,468
0,0039 0,0029 0,3200 0,2400 82,0568 4,0000 12,810
0,011954 0,14981 - - - - -
0,0899 0,1199 1,7896 1,3551 84,4307 125,9763 12,966
2 0,0257 0,0322 0,8000 0,6000 77,8561 41,0000 12,468
0,0039 0,0029 0,3200 0,2400 82,0561 4,0000 12,810
0,11954 0,15497 - - - - -
0,0899 0,1199 1,7600 1,3551 84,4307 125,9763 12,966
3 0,0257 0,0322 0,8000 0,6000 77,8561 41,0000 12,468
0,0039 0,0029 0,3200 0,2400 82,0561 4,0000 12,810
0,11956 0,15499 - - - - -
3.2 MÉTODO SIMPLIFICADO
O método MSP pode ser simplificado conforme proposto por (BARAN & WU, 1989).
A estratégia visa reduzir o esforço computacional utilizando uma solução aproximada para
estimar a redução da perda de potência da configuração radial corrente fornecida pelas
formigas. Assim, será obtido em cada iteração um valor aproximado da perda de potência,
mas que servirá para direcionar as formigas na busca da configuração ótima. O uso do MSP
simplificado no lugar do MSP completo é baseado no fato de ambos terem a mesma
configuração ótima.
Ao final de todas as iterações, o ACO utilizará a melhor configuração obtida para
determinar a perda de potência pelo método MSP completo, obtendo assim a solução ótima
do problema. As modificações foram feitas considerando que Vj2≈1 pu, dessa forma a
equação (12) ficará modificada conforme equação (14):
)22(
mQ
mPR
mP
(14)
Consequentemente, as equações (9), (10) e (11) podem ser suprimidas da rotina do
MSP completo. Outra simplificação foi feita utilizando uma modificação na tolerância do
MSP simplificado, ou seja, ɛ=100.
31
4 ALGORITMO HÍBRIDO PARA RECONFIGURAÇÃO DE
SISTEMAS ELÉTRICOS DE DISTRIBUIÇÃO
Os Sistemas Elétricos de Distribuição são projetados de tal forma que, em caso de
necessidade operacional é possível modificar a topologia inicial da rede, através de chaves de
manobras colocadas em pontos estratégicos do sistema, visando, dentre outros objetivos,
minimizar a perda de potência ativa total nos alimentadores, de forma a atender ao
consumidor final. A este processo é dado o nome de Reconfiguração de Sistemas
Elétricos de Distribuição (RSED).
Dessa forma, a formulação do problema de reconfiguração de redes pode ser feita
como segue:
,total
PMinimizar (15)
tendo como restrições:
i. Equações de fluxo de carga;
ii. Limite de magnitude das correntes nos ramos: Ii ≤ Imax,i, ∀ i, i ϵ NR;
iii. Limite de magnitude das tensões nodais: Vmin ≤ Vj ≤ Vmáx, ∀ j, j ϵ Nb;
iv. Configuração da rede radial;
Nb e NR são o conjunto de barras e ramos do sistema, respectivamente, ΔPtotal são as
perdas de potência ativa totais na rede, Ii e Imax,i são a magnitude da corrente e o limite
máximo de corrente em cada trecho i, respectivamente. Vj é a magnitude da tensão no nó j,
Vmin e Vmáx são os limites mínimo e máximo da tensão, respectivamente.
O problema de otimização com restrições expresso por (15) pode ser convertido num
problema irrestrito cuja função objetivo incorpore a restrição de corrente máxima nos trechos
e de tensão mínima ou máxima nas barras (PEREIRA, 2010; SOUZA et al., 2011).
]2)max(2
)min
[(2
)max(total
PF VjVj jVV
iIiI (16)
Sendo λ e γ o fator de penalidade da corrente e da tensão, respectivamente. O termo do
somatório, da corrente e da tensão, impõe um custo maior à função objetivo que é, por sua
vez, intensificado com o aumento da violação.
32
Esta seção aborda a metodologia utilizada para construção do Algoritmo Híbrido
aplicado a problemas de Reconfiguração de Sistemas Elétricos de Distribuição, desde a
construção das configurações radiais até as combinações realizadas entre o Ant System e os
métodos de Busca Tabu (BT), Método de Aceleração (MA), Decaimento Exponencial do
Feromônio (DEF) e Fluxo Simplificado (FS).
4.1 ANT SYSTEM PARA RECONFIGURAÇÃO DE REDES
O algoritmo Ant System para reconfiguração de redes pode ser descrito de forma
simplificada como:
1° passo: Ler os dados da rede, os parâmetros do algoritmo (peso do feromônio, peso
da informação heurística, taxa de evaporação, feromônio inicial) e depositar uma quantidade
inicial de feromônio em todas as ligações;
2° passo: Posicionar uma formiga em cada nó fonte;
3° passo: Selecionar uma das formigas, aleatoriamente, para realizar o movimento;
4° passo: Quando um agente k se encontra sobre a barra j ele seleciona a barra vizinha
z (diretamente conectada à barra j) a ser visitada, baseado na concentração de feromônio sobre
a linha (j,z), representada por τjz e no inverso da resistência R desta linha, representada por
ηjz = (Rjz)-1
. Esta seleção é feita aleatoriamente conforme a relação probabilística estabelecida
na equação (1).
5° passo: Executa o Método de Soma de Potências para calcular fluxos, correntes,
tensões e as perdas ativas totais;
6° passo: Calcular o valor da função objetivo correspondente à configuração atual;
7° passo: Em seguida, atualiza-se o feromônio sobre a melhor topologia (menor valor
de perdas ativas) dentre as encontradas pelos agentes, conforme equação (17).
contráriocaso
ialogtopomelhorapertencerjz
jz
jzjzjz
ρ)(
τρτρ)(
1
1 se
(17)
33
De forma que a quantidade de feromônio deixada pelos agentes no percurso da rota jz
é definida por Δτjz = FA/F, onde FA representa o fator de ajuste (depende do problema) e F
corresponde ao valor da função objetivo;
8° passo: Se o número máximo de expedições não for atingido, volta o passo 2;
9° passo: Se o número máximo de expedições for atingido, fim do algoritmo.
Apresentar a configuração radial final, indicando suas ligações e as perdas totais.
Para garantir que as configurações construídas sejam sempre radiais utilizou-se o
critério de Souza et al. (2010) que tem como base estabelecer regras para as formigas
artificiais durante seu deslocamento.
Durante a escolha das ligações que formam uma configuração radial, assumiremos os
seguintes critérios, conforme ilustrado na Figura 14:
Um nó pode assumir dois estados: ligado ou desligado;
Uma ligação pode assumir três estados: desativada, ativável ou ativada;
Se uma ligação está ativável, então um de seus nós deve estar ligado e o outro não. Se
uma ligação está ativada, então seus dois nós devem estar necessariamente ligados. Por fim,
se uma ligação está desativada, então seus dois nós devem estar necessariamente desligados.
Figura 14: Estado dos nós e das ligações.
Do próprio autor
Inicialmente todos os nós fontes estão ligados e os de carga desligados, de modo que
nenhuma ligação esteja ativada. Uma das formigas posicionadas em nós ligados se deslocará
respeitando as seguintes regras:
As formigas se deslocam exclusivamente por ligações ativáveis;
Quando uma formiga chega ao nó desligado da ligação ativável que tenha
percorrido, este nó torna-se ligado e a ligação ativada, surgindo outra formiga para
ocupar o nó originalmente ligado deixado por ela;
34
O percurso de uma formiga se completa quando ela não puder mais seguir por
ligações ativáveis;
A expedição termina quando nenhuma formiga tiver mais mobilidade, ou seja,
quando não houver mais nenhuma ligação ativável. Neste ponto, teremos
construído uma configuração radial;
A escolha de qual formiga fará o próximo movimento é de forma aleatória
(randômica), de tal maneira que todas tenham a mesma chance de ser escolhida;
A probabilidade de cada ligação ser escolhida é calculada conforme equação (1);
O sorteio da ligação a ser escolhida pela formiga é feito utilizando a estratégia da
roleta.
Durante o desenvolvimento da pesquisa, foram testadas duas maneiras de construção
da roleta. Como segue:
a) Método 1: Vetor de posições
Supondo uma formiga posicionada em determinado nó, com a probabilidade das
ligações 1 e 2 calculados, pela equação (1), em 44,7% (aproximado para 45%) e 55,3%
(aproximado para 55%), respectivamente, conforme Figura 15.
Figura 15: Escolha aleatória das ligações
(Do próprio autor)
Com a probabilidade de cada trecho calculada, constrói-se um vetor de 100 posições,
de forma que, cada trecho ocupará espaço de acordo com a sua probabilidade. Assim, ter-se-á
um vetor de posições, expresso pela Tabela 3, para o caso da Figura 15:
Gera-se randomicamente um número entre 1 e 100 e busca-se na roleta a ligação
correspondente. Supondo que o número sorteado randomicamente tenha sido 26, logo o
trecho escolhido para a formiga visitar é o 1.
35
Tabela 3: Posições da roleta
(Do próprio autor)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
Uma análise mais detalhada deste método permite verificar que as aproximações
realizadas nos cálculos das probabilidades para construção da roleta pode proporcionar
limitações quando o sistema possui muitas ramificações, ou seja, valores de probabilidade
muito baixos que podem ser aproximados para zero.
Veja, por exemplo, o que acontece com a escolha probabilística de uma formiga
iniciando a exploração, ou seja, saindo da fonte (subestação) na busca por uma configuração
para a rede de 84 barras11
. Assim, utilizando a equação (1) será obtido as seguintes
probabilidades nas trilhas:
Tabela 4: Arredondamento da probabilidade nas ligações
(Do próprio autor)
Ligação 1 11 15 25 30 43 47 56 65 73 77
Probabilid.
1,8% 11,2% 5,3% 21,2% 1,7% 27,9% 0,8% 1,1% 27,7% 0,4% 0,9%
Arredond. 2 11 5 21 2 28 1 1 28 0 1
Com base no calculo das probabilidades verifica-se que a ligação 73 não ocupará
posição nenhuma no vetor de 100 posições da roleta, pois o baixo valor da probabilidade
resultou em 0% (valor aproximado).
b) Método 2: Intervalos numéricos
O método 2 propõe uma estratégia para evitar o procedimento de arredondamento dos
valores de probabilidade, tornando o sorteio mais justo. A estratégia consiste em gerar um
vetor de intervalos numéricos com base nas probabilidades calculadas.
11
Sistema pode ser encontrado em (GOMES, 2005).
36
Os intervalos são calculados tomando 0 como referência e somando a probabilidade
em cada trecho ao valor acumulado destas. Assim, para a ligação 1, somando 0 e 0,018,
teremos o intervalo [0 – 0,018]. Para a ligação 11, somando 0,018 à 0,112 teremos os limites
inferior e superior 0,018 e 0,130, respectivamente. Para a ligação 15, soma 0,130 e 0,053,
resultando no intervalo (0,130 – 0,183]. O procedimento é repetido para todas as chaves.
Assim, ao final do procedimento teremos intervalos numéricos representativos de cada
ligação, conforme Tabela 5.
Em seguida, sorteia-se um número aleatório entre 0 e 1 (para o presente trabalho foi
utilizado a função “rand” do matlab). O valor gerado vai estar necessariamente contido em um
dos intervalos estabelecidos. Supondo que para o caso apresentado na Tabela 5 o valor
sorteado aleatoriamente tenha sido 0,9890. Logo, a formiga vai escolher visitar a ligação 73.
Tabela 5: Intervalos numéricos para construção da roleta
(Do próprio autor)
Intervalo Probabilidade Ligação
[0 - 0,018] 0,018 1
(0,018 - 0,130] 0,112 11
(0,130 - 0,183] 0,053 15
(0,183 - 0,395] 0,212 25
(0,395 - 0,412] 0,017 30
(0,412 - 0,691] 0,279 43
(0,691 - 0,699] 0,008 47
(0,699 - 0,710] 0,011 56
(0,710 - 0,987] 0,277 65
(0,987 - 0,991] 0,004 73
(0,991 – 1,000] 0,009 77
Como pode ser observado, pelo método 2 é possível explorar todas as trilhas,
incluindo as que possuem valores baixos de probabilidade, como é o caso da ligação 73, de
forma a ampliar o espaço de busca da colônia de formigas. Vale ressaltar que utilizando o
método 1, a ligação 73 era impossível de ser explorada pelas formigas, uma vez que não
ocupava posição nenhuma na roleta. Para o algoritmo proposto neste trabalho, foi utilizado o
método 2, por ser mais eficiente.
4.1.1 Exemplo: Sistema de 5 barras – Construção de configurações radiais
A Figura 16 descreve o algoritmo de formigas utilizado para gerar as configurações
radiais.
37
Fazer todos os nós
fontes ligados e os nós
de carga desligados
Posicionar uma
formiga em cada
nó ligado
Existe
ligação
ativável?
Escolher uma das
ligações ativáveis
com probabilidade
calculada
Deslocar a formiga
que esteja no nó
ligado da ligação
ativável selecionada
Configuração
radial gerada
Fim
Escolher
aleatoriamente
uma formiga do nó
ligado para realizar
o movimento
sim
não
Início
Figura 16: Fluxograma do gerador de configurações radiais utilizando colônia de formigas.
Adaptado de (SOUZA et al., 2010)
Para melhor entendimento da estratégia utilizada pelas formigas para gerar somente
configurações radiais, utilizou-se o sistema composto por 5 barras. Para este sistema,
considera-se que a barra 1 seja a subestação e que cada linha deste sistema tem apenas uma
chave manobrável. O número de chaves manobráveis é igual ao número de linhas (ligações).
Para iniciar a expedição, posiciona-se uma formiga no nó 1 (subestação), conforme
Figura 17. Desta forma, o agente poderá se deslocar pelas ligações ativáveis 1 ou 2. Este
agente utilizará o critério estabelecido pela expressão (1) e pelo método 2 da roleta para fazer
a escolha probabilística do próximo nó a ser visitado.
Figura 17: Exploração da colônia de formigas – posicionamento inicial
(Do próprio autor)
38
Supondo que a formiga tenha escolhido visitar o nó 2, conforme Figura 18, surgindo
uma outra para ficar em seu lugar, no nó 1. Com isso, agora os nós 1 e 2 estarão ligados,
devido à presença dos agentes nestes, fazendo com que a ligação 1 esteja no estado ativado.
Dessa forma, as formigas podem se deslocar pelas ligações ativáveis 2, 3 e 4. As ligações 5, 6
e 7 encontram-se no estado desativado.
Figura 18: Exploração da colônia de formigas - 1° iteração
(Do próprio autor)
O próximo passo agora é escolher, dentre os dois agentes, qual formiga será indicada
para realizar o movimento. No algoritmo proposto neste trabalho, foi adotado o critério de que
todas as formigas possuem a mesma chance de ser escolhida. Assim, utilizamos a função
randômica do Matlab para sortear aleatoriamente o agente.
Supondo que a formiga posicionada no nó 2 tenha sido escolhida aleatoriamente para
se deslocar. Logo ela pode se movimentar para o nó 3 (pela ligação 3) ou para o nó 4 (pela
ligação 4). O procedimento de escolher um caminho, dentre as possibilidades de trilhas é feita
utilizando a expressão (1) e o método 2 da roleta. Assim, surge agora a topologia mostrada na
Figura 19.
Figura 19: Exploração da colônia de formigas - 2° iteração
(Do próprio autor)
39
Para a topologia mostrada na Figura 19, qualquer uma das formigas posicionadas nos
nós 1, 2 e 4 pode ser escolhida para se deslocar. Escolhendo de forma randômica a formiga do
nó 1, verifica-se que só existe um único caminho, nesta situação não é necessário a escolha
probabilística, logo, a formiga se deslocará para o nó 3, passando-o para o estado ligado. Este
movimento torna as ligações 3 e 5 ativadas. Ao final da 3° iteração, a topologia construída até
o momento é a da Figura 20.
Figura 20: Exploração da colônia de formigas - 3° iteração
(Do próprio autor)
A 4° iteração ocorre de forma semelhante à 3° iteração. Para o estado dos nós e das
ligações apresentadas na Figura 20, verifica-se que as únicas formigas que podem se deslocar
são as posicionadas nos nós 3 e 4. Supondo que a formiga escolhida randomicamente para se
movimentar foi a do nó 4, que por sua vez, só possui um único caminho para se deslocar,
sendo neste caso, desnecessário a escolha probabilística. Logo, a formiga se deslocará para o
nó 5, passando-o para o estado ligado e a ligação 6 desativada permanentemente, enquanto a
ligação 7 ficará ativada, conforme Figura 21.
Figura 21: Exploração da colônia de formigas - 4° iteração
(Do próprio autor)
Após a 4° iteração a expedição termina, pois nenhuma formiga terá mais mobilidade,
ou seja, não há mais nenhuma ligação ativável. Assim, ao final de cada expedição sempre se
terá formado uma configuração radial.
40
4.2 IMPLEMENTAÇÃO DO ANT SYSTEM
A Figura 22 mostra a implementação do algoritmo Ant System para resolver problemas
de Reconfiguração de Sistemas Elétricos de Distribuição. Assim, a partir da configuração
radial construída pelas formigas no item 4.1, inicia-se a avaliação da função objetivo pelo
método de soma de potências, conforme descrito em 3.1 e, por fim, a evaporação e deposição
do feromônio. As iterações continuam até que o número de expedições seja alcançado.
Início
Ler os dados da rede
e os parâmetros do
algoritmo
Depositar uma
quantidade inicial de
feromônio em todas
as ligações
Incrementar o
contador de
expedições
Fazer todos os nós
fontes ligados e os nós
de carga desligados
Incrementar o
contador de
expedições
Posicionar uma
formiga em cada
nó ligado
Existe
ligação
ativável?
Escolher uma das
ligações ativáveis
com probabilidade
calculada
Deslocar a formiga
que esteja no nó
ligado da ligação
ativável selecionada
Executar o MSP:
calcular fluxos e
as perdas ativas
totais
Atualizar a carga
de feromônio das
ligações do melhor
global
Última
expedição?
Apresentar a
configuração radial
final indicando suas
ligações e as perdas
totais.
Fimsim
Escolher
aleatoriamente
uma formiga do nó
ligado para realizar
o movimento
sim
não
Calcular o valor da
função objetivo
correspondente a
configuração atual
não
Figura 22: Fluxograma Ant System aplicado ao problema de Reconfiguração.
(SOUZA et al, 2010)
41
4.3 ANT SYSTEM COMBINADO COM BUSCA TABU (AS_BT)
Após as formigas construírem uma configuração radial pelo critério estabelecido no
item 4.1, inicia-se a pesquisa local com a Busca Tabu. Inicialmente a Lista Tabu e a Lista
Elite estão vazias sendo preenchidas à medida que a exploração for sendo executada. Se a
Busca Tabu encontrar uma solução que melhore a configuração corrente fornecida pelas
formigas, então atualiza-se a carga de feromônio com base nesta configuração, caso contrário
faz-se a atualização do feromônio com a configuração encontrada pelas formigas. A avaliação
da configuração radial é realizada utilizando o método de soma de potências, conforme
descrito em 3.1.
Neste trabalho, a metaheurística Busca Tabu (BT) utiliza a estratégia de permutação
das ligações abertas para poder gerar novas configurações. Entretanto, a garantia da
radialidade deve ser assegurada, sendo necessário, em muitos casos, adicionar ao algoritmo
uma rotina de verificação, como em Abdelaziz et al. (2010). Estes apresentaram uma
estratégia para checar a radialidade de configurações obtidas pela BT, entretanto há a
desvantagem de aumentar o esforço computacional.
O autor propõe uma estratégia de permutação das ligações abertas a partir da solução
corrente e radial fornecida pelo algoritmo de formigas, de forma a garantir que todas as
configurações geradas sejam também radiais. Essa metodologia tem a vantagem de dispensar
a verificação de radialidade e, assim, reduzir o esforço computacional da BT.
Para garantir que as novas soluções da BT sejam também radiais utilizou-se o seguinte
procedimento:
Com a topologia radial fornecida pelo AS, identificar os nós de derivação que
limitam os ramos que contém as chaves abertas;
Identificar as ligações fechadas, vizinhas e adjacentes às chaves abertas e que
esteja limitada pelos nós de derivação;
Fechar uma chave aberta e abrir uma ligação vizinha e adjacente a esta;
Realizar todas as permutações possíveis até que não haja mais combinações entre
as ligações (vizinhas e adjacentes às chaves abertas da configuração inicial).
42
O método de permutação pode ser melhor entendido recorrendo-se a um exemplo com
um sistema de 16 barras, das quais 3 são fontes. A configuração inicial foi obtida pela
abertura das chaves 15, 21 e 26, conforme se vê na Figura 23.
Utilizando o procedimento descrito anteriormente, devem-se identificar inicialmente
os nós de derivação que limitam os ramos que contém as chaves abertas. Dessa forma, para a
chave 15 será identificado os nós 4 e 9, para a chave 21 os nós 8 e 13 e, por fim, para a chave
26 os nós 4 e 13, conforme Figura 24.
Figura 23: Configuração Radial para o Sistema de Distribuição de 16 barras
Souza et al. (2010)
Figura 24: Identificação dos nós de derivação que limitam os ramos que contém as chaves
abertas
(Do próprio autor)
O próximo passo agora é identificar as ligações fechadas, vizinhas e adjacentes
contidas nestes ramos, conforme Tabela 6.
Ligações ativadas
- - - - Ligações interrompidas
Centro de carga
43
Tabela 6: Vizinhos imediatos das chave abertas
(Do próprio autor)
Chaves
vizinhas
Chaves
abertas
Chaves
vizinhas
12 15 19
17 21 24
14 26 25
A permutação será realizada fechando uma chave aberta do ramo e abrindo uma
ligação vizinha e adjacente a esta.
Assim, fechando a chave 15 e abrindo a chave 12 será obtida uma nova configuração
gerada pela abertura das chaves 12, 21 e 26. Da mesma forma, fechando a chave 21 e abrindo
a 17 teremos agora as chaves abertas 15, 17 e 26. O procedimento é repetido para todas as
chaves vizinhas.
Desta forma, para este exemplo, no final da permutação serão obtidas 6 configurações
geradas na Busca Tabu, conforme Tabela 7, e uma configuração construída pelo ACO.
Tabela 7: Chaves abertas após a permutação
(Do próprio autor)
Método de exploração Chaves abertas na configuração
Chaves abertas no AS 15-21-26
Chaves abertas na BT
12-21-26
19-21-26
15-17-26
15-24-26
15-21-14
15-21-25
Com base no algoritmo Ant System (AS) da seção 4.2 e nas regras estabelecidas para a
Busca Tabu (BT), o algoritmo proposto (AS_BT) para Configuração Ótima de Redes de
Distribuição pode ser apresentado conforme Figura 25.
44
Início
Ler os dados da rede
e os parâmetros do
algoritmo híbrido
Depositar uma
quantidade inicial
de feromônio em
todas as ligações
Incrementar o
contador de
expedições
Fazer todos os
nós fontes ligados
e os nós de carga
desligados
Incrementar o
contador de
expedições
Posicionar uma
formiga em cada
nó ligado
Existe ligação
ativável?
Buscar vizinhos
factíveis a partir
da configuração
radial corrente
não
Deslocar a formiga que
esteja no nó ligado da
ligação ativável
selecionada
Analisar
configuração?
É tabu?
sim sim
Executar o MSP:
calcular fluxos e
as perdas ativas
totais
Atualizar Lista
tabu e Lista Elite
não
Escolher a melhor
solução da
expedição
Atualizar a carga
de feromônio do
melhor global
Última
expedição?
Apresentar a
configuração radial
final indicando suas
ligações e as perdas
totais.
Fim
não
sim
não
Escolher
aleatoriamente uma
formiga do nó ligado
para realizar o
movimento
sim
Escolher uma das
ligações ativáveis
com probabilidade
calculada
Calcular o valor da
função objetivo
correspondente a
configuração atual
Figura 25: Fluxograma do Algoritmo de Formigas com Busca Tabu
(Do próprio autor)
45
4.4 ANT SYSTEM COMBINADO COM MÉTODO DE ACELERAÇÃO
(AS_MA)
O método de aceleração do algoritmo de formigas proposto por (TSENG et al., 2010),
foi inicialmente aplicado ao problema do caixeiro viajante. Segundo os autores, a estratégia
proporcionou redução significativa do esforço computacional do algoritmo.
O presente trabalho utiliza o método de aceleração do algoritmo de formigas aplicado
ao problema de Reconfiguração dos Sistemas Elétricos de Distribuição. O princípio de
funcionamento do método em problemas de reconfiguração pode ser explicado recorrendo-se
à rede de quatro nós de carga, uma subestação, e sete ligações, mostrado na Figura 26.
Figura 26: Rede de quatro nós de carga e 7 ligações.
(PEREIRA, 2010)
Adotando-se para este exemplo o critério de que em 4 iterações12
(π=4 iterações), se
qualquer ligação da configuração for visitada por m=4 formigas, então ela será considerada
uma subsolução do problema. Desta forma, o limite estabelecido para este intervalo de
iterações é de 4 formigas, ω=4.
Os valores de π e m devem ser atribuídos e simulados até se obter os parâmetros
adequados para o problema. Quanto menor o valor de m em relação a π, menor o esforço
computacional, porém pode degradar a qualidade da solução.
Considerando-se que após as 4 iterações do AS tenham-se obtidas as configurações
radiais da Figura 27.
12
Para cada iteração, as formigas constroem uma configuração radial.
46
Para esta 4° iteração, a frequência de visitas das formigas (υjz) à ligação (ejz) é
registrada utilizando a matriz υ, conforme Tabela 8.
Figura 27: Configurações radiais obtidas da rede inicial.
(PEREIRA, 2010)
Tabela 8: Contabilizando a frequência de visitas nas ligações
(do próprio autor)
ejz 1 2 3 4 5 6 7
υjz 3 3 2 3 1 4 0
A atualização da matriz υ é feita a cada configuração radial construída pelas formigas
até que se atinja o intervalo π iterações. Atingido o limite de iterações, a matriz υ será
inicializada para nova contabilização de visitas.
Com base nos dados da Tabela 8 e sabendo-se que ω=4, obtêm-se a matriz ζ, que
identifica as ligações que alcançaram o limite estabelecido ω, conforme Tabela 9.
Tabela 9: Registro das ligações que alcançaram o limite de visitas nas últimas iterações
(do próprio autor)
ejz 1 2 3 4 5 6 7
ζjz 0 0 0 0 0 1 0
47
Assim, para este exemplo, somente a ligação 6 foi identificada como subsolução do
problema, pois em suas 4 iterações, 4 formigas passaram por este caminho. A atualização da
matriz ζ é realizada ao final das π iterações e inicializada somente no início do AS.
Após o procedimento de detecção (Tabela 8 e Tabela 9), a matriz ζ poderá ser utilizada
para compressão e remoção de redundâncias computacionais nas próximas iterações do AS.
Assim, se dentre as rotas disponíveis for identificada alguma como sendo solução parcial do
problema (ζ 1), então a formiga escolherá obrigatoriamente esta trilha, como descrito no
item 2.2.6.
As configurações construídas são avaliadas pelo método de soma de potências,
conforme descrito em 3.1 e o feromônio das trilhas são atualizados de acordo com a regra
proposta pelas expressões (2) e (3).
Com base no algoritmo Ant System (AS) do item 4.2 e no Método de Aceleração
proposto para configuração ótima de redes de Distribuição, esquematizou-se um fluxograma
apresentado conforme Figura 28.
4.5 ANT SYSTEM COM DECAIMENTO EXPONENCIAL DO
FEROMÔNIO (AS_DEF)
Conforme descrito no item 2.2.1, durante as expedições das formigas na natureza, elas
utilizam um mecanismo de comunicação indireta por meio do feromônio. A quantidade desta
substância nas trilhas depende diretamente da frequência de deposição e evaporação. Assim, a
trilha que possuir maior concentração de feromônio tenderá a ser a mais visitada.
Para o caso das formigas artificiais, a saturação muito rápida de feromônio em certas
trilhas pode proporcionar convergência prematura do algoritmo e a consequente estagnação
em ótimos locais. A minimização deste efeito pode ser obtida utilizando a estratégia de
modificar a taxa de evaporação de forma gradativa, e assim proporcionar um decaimento
exponencial do feromônio, potencializando o Ant System a explorar um espaço de busca
maior, conforme descrito no item 2.2.7.
Com base no algoritmo Ant System proposto na seção 4.2 e na estratégia de
decaimento exponencial do feromônio, seção 2.2.7, esquematizou-se um fluxograma
apresentado conforme Figura 29.
48
Início
Ler os dados da rede e os
parâmetros do algoritmo
híbrido
Depositar uma
quantidade inicial de
feromônio em todas
as ligações
Incrementar o
contador de
expedições
Fazer todos os nós
fontes ligados e os nós
de carga desligados
Incrementar o
contador de
expedições
Posicionar uma
formiga em cada
nó ligado
Existe
ligação
ativável?
Existe
ligação
comum?
Escolher uma das
ligações ativáveis
com probabilidade
calculada
Deslocar a formiga
que esteja no nó
ligado da ligação
ativável selecionada
Executar o MSP:
calcular fluxos e
as perdas ativas
totais
Atualizar a carga
de feromônio das
ligações do
melhor global
Última
expedição?
Apresentar a
configuração radial
final indicando suas
ligações e as perdas
totais.
Fim
Registrar o
número de vezes
que cada ligação
é visitada
Registrar as ligações
frequentemente
visitadas como
comuns
sim
Escolher
aleatoriamente
uma formiga do nó
ligado para realizar
o movimento
sim
sim
não
não
Calcular o valor da
função objetivo
correspondente a
configuração atual
não
Figura 28: Fluxograma do Algoritmo de Formigas com Método de Aceleração
(Do próprio autor)
49
Início
Ler os dados da rede
e os parâmetros do
algoritmo
Depositar uma
quantidade inicial de
feromônio em todas
as ligações
Incrementar o
contador de
expedições
Fazer todos os nós
fontes ligados e os nós
de carga desligados
Incrementar o
contador de
expedições
Posicionar uma
formiga em cada
nó ligado
Existe
ligação
ativável?
Escolher uma das
ligações ativáveis
com probabilidade
calculada
Deslocar a formiga
que esteja no nó
ligado da ligação
ativável selecionada
Executar o MSP:
calcular fluxos e
as perdas ativas
totais
Atualizar a carga de
feromônio das
ligações do melhor
global
Última
expedição?
Apresentar a
configuração radial
final indicando suas
ligações e as perdas
totais.
Fimsim
Escolher
aleatoriamente
uma formiga do nó
ligado para realizar
o movimento
sim
não
Calcular o valor da
função objetivo
correspondente a
configuração atual
não
Calcular a taxa de
evaporação
utilizando
decaimento
exponencial
Figura 29: Fluxograma do AS com Decaimento Exponencial do Feromônio
(Do próprio autor)
50
4.6 ANT SYSTEM COM FLUXO DE POTÊNCIA SIMPLIFICADO
(AS_FS)
O algoritmo AS_FS pode ser visto na Figura 30.
Figura 30: Fluxograma do AS combinado com Fluxo de Potência Simplificado
(Do próprio autor)
Início
Ler os dados da rede
e os parâmetros do
algoritmo
Depositar uma
quantidade inicial de
feromônio em todas
as ligações
Incrementar o
contador de
expedições
Fazer todos os nós
fontes ligados e os nós
de carga desligados
Incrementar o
contador de
expedições
Posicionar uma
formiga em cada
nó ligado
Existe
ligação
ativável?
Escolher uma das
ligações ativáveis
com probabilidade
calculada
Deslocar a formiga
que esteja no nó
ligado da ligação
ativável selecionada
Atualizar a carga
de feromônio das
ligações do
melhor global
Última
expedição?
Apresentar a
configuração radial
final indicando suas
ligações e as perdas
totais.
Fim
sim
Escolher
aleatoriamente
uma formiga do nó
ligado para realizar
o movimento
sim
não
Calcular o valor da
função objetivo
correspondente a
configuração atual
não
Executar o MSP
simplificado:
Calcular fluxos
e as perdas
ativa totais
A config. é
melhor que a
global?
Executar o MSP
completo
sim
não
51
O cálculo do fluxo de potência é uma rotina utilizada pelo algoritmo de formigas para
avaliação das configurações radiais geradas. Durante a execução do Ant System, esta análise
deve ser realizada diversas vezes, acarretando um elevado esforço computacional ao método.
Assim, uma alternativa de poder tornar o AS mais eficiente, em questão de esforço
computacional, é alterar a metodologia de cálculo do fluxo de potência.
A estratégia consiste em utilizar o procedimento de cálculo do Fluxo de Potência
Simplificado proposto por (BARAN & WU, 1989) conforme descrito em 3.2. para avaliação
das configurações radiais construídas pelas formigas. Esta simplificação passará a oferecer
valores aproximados do fluxo de potência, porém suficientes para direcionar o algoritmo de
formigas para as melhores configurações. Encontrada uma topologia melhor que a global,
obtido pelo método simplificado, o MSP Completo é executado, como descrito em 3.1. Dessa
forma, o MSP completo somente será utilizado se for encontrado uma configuração melhor
que a corrente. Esta alternância é utilizada para determinação da tensão e da corrente para
avaliação das restrições.
4.7 IMPLEMENTAÇÃO COMPUTACIONAL DO ALGORITMO
AS_HIBRIDO
O algoritmo convenientemente chamado neste trabalho por AS_hibrido é o resultado
da combinação do Ant System (AS) com a Busca Tabu (BT), o Método de Aceleração (MA),
o Decaimento exponencial do Feromônio (DEF) e o Fluxo de Potência Simplificado (FS),
conforme Figura 31.
O algoritmo inicia lendo os dados da rede e os parâmetros do algoritmo híbrido, as
formigas depositam uma quantidade inicial de feromônio em todas as ligações de forma que
todos os ramos fiquem com a mesma concentração e, por fim, incrementar o contador de
expedições.
Em seguida os agentes iniciam a construção da configuração. Neste trabalho, adotou-
se a estratégia proposta por (SOUZA et al., 2010) para estabelecer as regras de movimento
das formigas, por apresentar a vantagem de gerar somente configurações radiais.
Adicionalmente a estas regras, o autor programou o bloco “Escolher aleatoriamente uma
formiga do nó ligado para realizar o movimento”, de forma que, qualquer formiga que estiver
em condições de realizar o movimento terá a mesma chance de ser escolhida. Desta forma,
enquanto existir ligações ativáveis as formigas realizarão movimento obedecendo a critérios
52
probabilísticos, se existir ligações identificas como comuns (ligações que possuem grande
chance de fazer parte da solução final), estas serão escolhidas prioritariamente não
necessitando de cálculos probabilísticos e nem da roleta. Esta técnica de identificação
antecipada de subsoluções, doravante chamada neste trabalho por Método de Aceleração, foi
utilizada por (TSENG et al., 2010) para resolver o Problema do Caixeiro Viajante e adaptada
pelo autor para Reconfiguração de Sistemas Elétricos de Distribuição.
Após as formigas construírem uma configuração radial, inicia-se a pesquisa local
utilizando uma adaptação da metaheurística Busca Tabu proposta inicialmente por
(GLOVER, 1989). A adaptação visa garantir que todas as configurações geradas na Busca
Tabu (BT) sejam puramente radiais, para isso o autor utilizou a estratégia de permutação das
ligações abertas para realizar a pesquisa de vizinhança da BT. Desta forma, enquanto existir
configurações vizinhanças para serem analisadas e esta não pertencer a Lista Tabu, avalia-se a
solução com o Método de Soma de Potências Simplificado (MSPS), se a solução for melhor
que a corrente, então se calcula as perdas ativas e reativas, as tensões e as correntes utilizando
o Método de Soma de Potências Completo (MSPC) e, por fim, determina-se o valor da função
objetivo. Vale ressaltar que o autor utilizou o MSPS com o objetivo apenas de direcionar o
algoritmo para uma solução melhor que a atual. Dessa forma, o MSPC somente será acionado
se houver configuração radial que minimize as perdas de potência ativa, agregando ao
algoritmo a vantagem de minimizar o esforço computacional que poderia ser proporcionado
pela avaliação de todas as soluções pelo MSPC.
Não existindo vizinhos para serem analisados, escolhe-se a melhor solução da
expedição para poder atualizar o feromônio das ligações. Este procedimento é realizado por
meio de duas etapas, a primeira é a evaporação do feromônio de todas as trilhas e a segunda é
a deposição de certa quantidade da substância volátil nas ligações que compõem a solução
parcial. Esta atualização deve ser realizada de forma criteriosa para evitar que o algoritmo
estabilize muito cedo em uma solução local. Assim, visando minimizar o efeito da
convergência prematura proporcionada pela concentração excessiva de feromônio em
algumas trilhas, o autor aplicou a estratégia apresentada por (SHERAFAT et al., 2008). Neste
trabalho, o método convenientemente chamado de Deposição Exponencial do Feromônio foi
adaptado para utilização em problemas de Reconfiguração de Sistemas Elétricos de
Distribuição.
53
Início
Ler os dados da rede
e os parâmetros do
algoritmo híbrido
Depositar uma
quantidade inicial
de feromônio em
todas as ligações
Incrementar o
contador de
expedições
Fazer todos os
nós fontes ligados
e os nós de carga
desligados
Incrementar o
contador de
expedições
Posicionar uma
formiga em cada
nó ligado
Existe ligação
ativável?
Existe ligação
comum?
Buscar vizinhos
factíveis a partir
da configuração
radial corrente
não
Escolher uma das
ligações ativáveis
com probabilidade
calculada
Deslocar a formiga que
esteja no nó ligado da
ligação ativável
selecionada
Analisar
configuração?
É tabu?
sim sim
Executar o MSP
simplificado:
Calcular fluxos
e as perdas
ativa totais
Atualizar Lista
tabu e Lista Elite
não
Escolher a melhor
solução da
expedição
Atualizar a carga
de feromônio
Última
expedição?
Apresentar a
configuração radial
final indicando
suas ligações e as
perdas totais.
Fim
Registrar o
número de vezes
que cada ligação
é visitada
Registrar as ligações
frequentemente
visitadas como
comuns
não
sim
não
Escolher
aleatoriamente uma
formiga do nó ligado
para realizar o
movimento
sim
sim
não
Calcular a taxa de
evaporação utilizando
decaimento exponencial
Calcular o valor da
função objetivo
correspondente a
configuração atual
A config. é
melhor que a
global?
não
simCalcular o MSP
completo
Figura 31: Fluxograma do Algoritmo híbrido AS_hibrido
(Do próprio autor)
54
Ao final, executa-se os dois blocos que compõe a rotina computacional do Método de
Aceleração. O primeiro registra o número de vezes que cada ligação é visitada e a segunda
registra as ligações identificadas como comuns (subsoluções).
Se for a última expedição, o algoritmo apresenta a configuração radial final indicando
suas ligações e as perdas totais, caso contrário, incrementa o contador de expedições e executa
o algoritmo para uma nova exploração.
55
5 RESULTADO DAS SIMULAÇÕES
Para verificar o comportamento do algoritmo proposto neste trabalho, são
apresentados, neste capítulo, os resultados dos testes realizados em quatro sistemas de
distribuição conhecidos da literatura, a saber: 16 barras (SOUZA et al., 2010), 33 barras
(BARAN & WU, 1989), 69 barras (CHIANG & JEAN-JUMEAU, 1990) e 84 barras
(GOMES, 2005). Os parâmetros de entrada dos algoritmos foram atribuídos com base em
diversas simulações, utilizando a estratégia de tentativa e erro, até se obter os valores que
proporcionassem o melhor desempenho. Os resultados podem ser vistos na Tabela 10.
Tabela 10: Parâmetros de entrada para as simulações computacionais
(Do próprio autor)
Parâmetros Símb. 16
barras
33
barras
69
barras
84
barras
Valor do feromônio inicial τ0 1 1 1 1
Peso do feromônio α 1,0 0,8 0,5 0,1
Peso da informação heurística β 2,0 1,0 0,8 0,2
Tolerância do MSP simplificado εs 10-0
10-0
10-0
10-0
Tolerância do MSP completo ε 10-3
10-3
10-3
10-3
Número de iterações do AS It_AS 20 30 30 60
Número de ciclos por iteração do AS Ciclos 10 10 10 10
Comprimento da Lista Tabu LT 50 200 300 700
Intervalo das visitas do MA π 5 5 10 10
N° de formigas por ligação no MA m 4 5 8 8
Taxa de decaimento exponencial ρ0 0,85 0,90 0,99 0,99
Constante de decaimento exponencial ϕ 100 150 200 600
Limite máximo de corrente nas linhas Imax 0,02 0,03 0,02 0,02
Limite mínimo de tensão nas barras Vmín 0,95 0,93 0,95 0,95
Limite máximo de tensão nas barras Vmáx 1,05 1,05 1,05 1,05
Os algoritmos foram implementados em Matlab®
R2010b, computador Intel (R), Core
(TM) i5, 2,60 GHz e 4,0 GB de memória RAM.
5.1 SISTEMA DE 16 BARRAS
O primeiro sistema utilizado para teste foi o de tensão nominal 23 kV e potência base
100 MVA encontrado em (SOUZA et al., 2010). Este possui 16 barras, 3 alimentadores
(barras 1,2 e 3), 3 laços e 16 chaves seccionadoras, sendo originalmente 13 chaves fechadas e
3 chaves abertas. A configuração inicial do sistema apresenta perdas de 511,4 kW. As chaves
de interconexão para a configuração inicial são 15-21-26. É comum este sistema ser descrito
56
como sendo de 14 barras, devido ao fato de considerar as barras que compõem as subestações
como uma só, porém neste trabalho foram consideradas as três barras com suas respectivas
subestações. Os dados de barra e de linha deste sistema podem ser vistos no apêndice A.
A Figura 32 ilustra a configuração inicial do sistema de 16 barras.
Figura 32: Sistema de 16 barras – Configuração inicial.
(SOUZA et al., 2010)
Os resultados encontrados para o sistema de 16 barras são apresentados na Tabela 11 e
Figura 33.
Tabela 11: Resultados obtidos para o sistema de 16 barras
(Do próprio autor)
Algoritmo Perdas
(kW)
Redução
(%)
Chaves abertas
Conf. inicial 511,4 - 15-21-26
Algoritmo híbrido proposto
AS_hibrido 466,1 8,86 17-19-26
Algoritmos construídos e testados durante pesquisa
AS 466,1 8,86 17-19-26
AS_BT 466,1 8,86 17-19-26
AS_MA 466,1 8,86 17-19-26
AS_DEF 466,1 8,86 17-19-26
AS_FS 466,1 8,86 17-19-26
Soluções encontradas na literatura
(SU et al., 2005)
Colônia de formigas 466,1 8,86 17-19-26
(CHANG, 2008)
Colônia de Formigas 466,1 8,86 17-19-26
(CHANG et al., 1994)
Simulated annealing 466,1 8,86 17-19-26
Ligações ativadas
- - - - Ligações interrompidas
Centro de carga
57
Figura 33: Tempo de execução dos algoritmos testados para o Sistema de 16 barras.
(Do próprio autor)
Para o sistema de 16 barras, a configuração final e as perdas obtidas pelo Ant System
Híbrido (AS_hibrido) são iguais aos melhores resultados encontrados na literatura por (SU et
al., 2005), (CHANG, 2008) e (CHANG & KUO 1994) e aos resultados encontrados pelos
algoritmos construídos e testados durante a pesquisa. Contudo, dentre os métodos testados, o
AS_ hibrido apresentou a vantagem de resolver o mesmo problema em tempo computacional
menor.
Para as simulações do sistema de 16 barras adotou-se um limite mínimo de tensão de
0,95 pu e um limite máximo de corrente de 0,02 pu. Na Figura 34 são apresentados os níveis
das magnitudes de tensão encontrados para as configurações inicial e final deste sistema.
Figura 34: Tensões obtidas para o sistema de 16 barras.
(Do próprio autor)
0,48 seg.
0,27 seg.
0,36 seg.
0,49 seg.
0,31 seg.
0,15 seg.
AS AS_BT AS_MA AS_DEF AS_FS AS_HÍBRIDO
0,97
0,97
0,98
0,98
0,99
0,99
1,00
1,00
1,01
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
Va
lor
de
Ten
são
(p
u)
Barras
Depois da Reconfiguração Antes da Reconfiguração
58
A topologia final proporciona uma distribuição de tensão melhor, quando comparado
com a topologia inicial, com menor perda de potência ativa possível nos alimentadores.
Assim, para a configuração inicial, a menor tensão se encontra na barra 12 com valor de
0,9693 pu. Enquanto que a topologia final, a menor tensão se encontra na barra 12 com valor
de 0,9716 pu.
5.2 SISTEMA DE 33 BARRAS
O segundo sistema utilizado para teste foi o de tensão nominal 12,66 kV e potência
base 10 MVA encontrado em (BARAN & WU, 1989). Este possui 33 barras, um alimentador
(barra 1 é a subestação), 5 laços e 37 chaves seccionadoras, sendo originalmente 32 chaves
fechadas e 5 chaves abertas (chaves de 33 a 37). A configuração inicial do sistema apresenta
perdas de 202,68 kW. As chaves de interconexão para a configuração inicial são 33-34-35-36-
37. Os dados de barra e de linha deste sistema podem ser vistos no apêndice A.
A Figura 35 ilustra a configuração inicial do sistema de 33 barras.
Figura 35: Sistema de 33 barras – Configuração inicial.
(PEREIRA, 2010)
Os resultados encontrados para o sistema de 33 barras são apresentados na Tabela 12 e
Figura 36.
Ligações ativadas
- - - - Ligações interrompidas
Centro de carga
59
Tabela 12: Resultados obtidos para o sistema de 33 barras
(Do próprio autor)
Algoritmo Perdas
(kW)
Redução
(%)
Chaves abertas
Conf. inicial 202,68 - 33-34-35-36-37
Algoritmo híbrido proposto
AS_hibrido 139,55 31,15 7-9-14-32-37
Algoritmos construídos e testados durante pesquisa
AS 139,55 31,15 7-9-14-32-37
AS_BT 139,55 31,15 7-9-14-32-37
AS_MA 139,55 31,15 7-9-14-32-37
AS_DEF 139,55 31,15 7-9-14-32-37
AS_FS 139,55 31,15 7-9-14-32-37
Soluções encontradas na literatura
(ZVIETCOVICH, 2006)
Busca em Vizinhança
Variável
139,55 31,15 7-9-14-32-37
(CHANG et al., 1994)
Simulated annealing 139,70 31,07 7-9-14-32-37
Figura 36: Tempo de execução dos algoritmos testados para o Sistema de 33 barras.
(Do próprio autor)
Para o sistema de 33 barras, a configuração final e as perdas obtidas pelo Ant System
Híbrido (AS_hibrido) são iguais aos melhores resultados encontrados na literatura por
(ZVIETCOVICH, 2006) e (CHANG et al., 1994) e aos resultados encontrados pelos
algoritmos construídos e testados durante a pesquisa. Contudo, dentre os métodos testados, o
AS_ hibrido apresentou a vantagem de resolver o mesmo problema em tempo computacional
menor.
Para as simulações do sistema de 33 barras adotou-se um limite mínimo de tensão de
0,93 pu e um limite máximo de corrente de 0,03 pu. Na Figura 37 são apresentados os níveis
das magnitudes de tensão encontrados para as configurações inicial e final deste sistema.
1,69 seg.
1,23 seg.
1,47 seg.
1,71 seg.
1,03 seg.
0,47 seg.
AS AS_BT AS_MA AS_DEF AS_FS AS_HÍBRIDO
60
Figura 37: Tensões obtidas para o sistema de 33 barras.
(Do próprio autor)
A topologia final proporciona uma distribuição de tensão melhor, quando comparado
com a topologia inicial, com menor perda de potência ativa possível nos alimentadores.
Assim, para a configuração inicial, a menor tensão se encontra na barra 18 com valor de
0,9131 pu. Enquanto que a topologia final, a menor tensão se encontra na barra 32 com valor
de 0,9378 pu.
5.3 SISTEMA DE 69 BARRAS
O Terceiro sistema utilizado para teste foi o de tensão nominal 12,66 kV e potência
base 10 MVA encontrado em (CHIANG & JEAN-JUMEAU, 1990). Este possui 69 barras,
um alimentador (barra 1 é a subestação), 73 chaves seccionadoras, sendo originalmente 68
chaves fechadas e 5 chaves abertas (chaves de 70 a 74). A configuração inicial do sistema
apresenta perdas de 20,91 kW. As chaves de interconexão para a configuração inicial são 70-
71-72-73-74. Os dados de barra e de linha deste sistema podem ser vistos no apêndice A.
A Figura 38 ilustra a configuração inicial do sistema de 69 barras.
0,9
0,91
0,92
0,93
0,94
0,95
0,96
0,97
0,98
0,99
1
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33
Va
lor
de
Ten
são
(p
u)
Barras
Depois da Reconfiguração Antes da Reconfiguração
61
Figura 38: Sistema de 69 barras – Configuração inicial.
(PEREIRA, 2010)
Os resultados encontrados para o sistema de 69 barras são apresentados na Tabela 13 e
Figura 39.
Tabela 13: Resultados obtidos para o sistema de 69 barras
(Do próprio autor)
Algoritmo Perdas
(kW)
Redução
(%)
Chaves
abertas
Conf. inicial 20,91 - 70-71-72-73-74
Algoritmo híbrido proposto
AS_hibrido 9,34 55,33 14-57-62-70-71
Algoritmos construídos e testados durante pesquisa
AS 9,34 55,33 14-57-62-70-71
AS_BT 9,34 55,33 14-57-62-70-71
AS_MA 9,34 55,33 14-57-62-70-71
AS_DEF 9,34 55,33 14-57-62-70-71
AS_FS 9,34 55,33 14-57-62-70-71
Soluções encontradas na literatura
(MANTOVANI et al., 2000)
Algoritmo heurístico 9,34 55,33 14-57-62-70-71
(ZVIETCOVICH, 2006)
Busca em Vizinhança
Variável
9,34 55,33 15-59-62-70-71
(CHANG et al., 1994)
Simulated annealing 9,40 52,32 15-56-62-70-71
Ligações ativadas
- - - - Ligações interrompidas
Centro de carga
62
Para o sistema de 69 barras, a configuração final e as perdas obtidas pelo Ant System
Híbrido (AS_hibrido) são iguais aos melhores resultados encontrados na literatura por
(ZVIETCOVICH, 2006) e (CHANG et al., 1994) e aos resultados encontrados pelos
algoritmos construídos e testados durante a pesquisa. Contudo, dentre os métodos testados, o
AS_ hibrido apresentou a vantagem de resolver o mesmo problema em tempo computacional
menor.
Figura 39: Tempo de execução dos algoritmos testados para o Sistema de 69 barras.
(Do próprio autor)
Para as simulações do sistema de 69 barras adotou-se um limite mínimo de tensão de
0,95 pu e um limite máximo de corrente de 0,02 pu. Na Figura 40 são apresentados os níveis
das magnitudes de tensão encontrados para as configurações inicial e final deste sistema.
Figura 40: Tensões obtidas para o sistema de 69 barras.
(Do próprio autor)
5,21 seg.
3,60 seg. 3,10 seg.
5,24 seg. 4,81 seg.
2,60 seg.
AS AS_BT AS_MA AS_DEF AS_FS AS_HÍBRIDO
0,97
0,98
0,99
1,00
1,01
0 3 6 9 12 15 18 21 24 27 30 33 36 39 42 45 48 51 54 57 60 63 66 69 72 75
Va
lor
de
Ten
são
(p
u)
Barras
Antes da Reconfiguração Depois da Reconfiguração
63
A topologia final proporciona uma distribuição de tensão melhor, quando comparado
com a topologia inicial, com menor perda de potência ativa possível nos alimentadores.
Assim, para a configuração inicial, a menor tensão se encontra na barra 66 com valor de
0,9720 pu. Enquanto que a topologia final, a menor tensão se encontra na barra 62 com valor
de 0,9825 pu.
5.4 SISTEMA DE 84 BARRAS
O quarto teste foi realizado com o sistema de distribuição prático da Taiwan Power
Company (TPC) de 11,4 kV e potência base 10 MVA encontrado em (GOMES, 2005). Este
possui 11 alimentadores e 83 barras. A rede possui uma carga de 30750 kW e 22300 kVAr.
Considera-se que as cargas sejam equilibradas e a potência constante.
A Figura 41 ilustra a configuração inicial do sistema de 84 barras.
Figura 41: Sistema de 84 barras – Configuração inicial.
(SU et al., 2005)
Considera-se que exista uma chave em cada ramo do alimentador totalizando 83 barras
normalmente fechadas e 13 chaves normalmente abertas (chaves de 84 a 96). A configuração
Ligações ativadas
- - - - Ligações interrompidas
Centro de carga
64
inicial do sistema apresenta perdas de 531,99 kW. As chaves de interconexão para a
configuração inicial são 84-85-86-87-88-89-90-91-92-93-94-95-96. Os dados de barra e de
linha deste sistema podem ser vistos no apêndice A.
Os resultados encontrados para o sistema de 84 barras são apresentados na Tabela 14 e
Figura 42.
Tabela 14: Resultados obtidos para o sistema de 84 barras
(Do próprio autor)
Algoritmo Perdas
(kW)
Redução
(%)
Chaves abertas
Conf. inicial 531,99 - 84-85-86-87-88-89-90-91-
92-93-94-95-96
AS_hibrido 469,88 11,68 7-13-34-39-42-55-62-72-83-
86-89-90-92
Algoritmos construídos e testados durante pesquisa
AS 470,10 11,63 7-13-34-39-55-61-83-86-72-
89-90-92-95
AS_BT 470,05 11,64 7-13-34-39-42-55-63-72-83-
86-89-90-92
AS_MA 470,10 11,63 7-13-34-39-55-61-83-86-72-
89-90-92-95
AS_DEF 470,05 11,64 7-13-34-39-42-55-63-72-83-
86-89-90-92
AS_FS 470,10 11,63 7-13-34-39-55-61-83-86-72-
89-90-92-95
Soluções encontradas na literatura
(SU et al., 2005)
Ant Colony System 469,88 11,68
7-13-34-39-41-55-62-72-83-
86-89-90-92
(SOUZA, 2013)
Algoritmo GRASP 469,88 11,68
7-13-34-39-42-55-62-72-83-
86-89-90-92
(OLIVEIRA, 2009)
Programação não
Linear Inteira Mista
469,88 11,68 7-13-34-39-42-55-62-72-83-
86-89-90-92
Para o sistema de 84 barras, a configuração final e as perdas obtidas pelo Ant System
Híbrido (AS_hibrido) são coerentes aos resultados encontrados na literatura por (SU et al.,
2005) e aos resultados encontrados pelos algoritmos construídos e testados durante a
pesquisa. Contudo, dentre os métodos testados, o AS_ hibrido apresentou a vantagem de
resolver o mesmo problema em tempo computacional menor.
65
Figura 42: Tempo de execução dos algoritmos testados para o Sistema de 84 barras.
(Do próprio autor)
Para as simulações do sistema de 84 barras adotou-se um limite mínimo de tensão de
0,95 pu e um limite máximo de corrente de 0,02 pu. Na Figura 43 são apresentados os níveis
das magnitudes de tensão encontrados para as configurações inicial e final deste sistema.
Figura 43: Tensões obtidas para o sistema de 84 barras.
(Do próprio autor)
A topologia final proporciona uma distribuição de tensão melhor, quando comparado
com a topologia inicial, com menor perda de potência ativa possível nos alimentadores.
Assim, para a configuração inicial, a menor tensão se encontra na barra 10 com valor de
0,9285 pu. Enquanto que a topologia final, a menor tensão se encontra na barra 72 com valor
de 0,9532 pu.
247,40 seg.
165,53 seg. 157,33 seg.
249,55 seg. 234,55 seg.
73,54 seg.
AS AS_BT AS_MA AS_DEF AS_FS AS_HÍBRIDO
0,92
0,93
0,94
0,95
0,96
0,97
0,98
0,99
1,00
1,01
0 3 6 9 12 15 18 21 24 27 30 33 36 39 42 45 48 51 54 57 60 63 66 69 72 75 78 81 84 87 90
Va
lor
de
Ten
são
(p
u)
Barras
Depois da Reconfiguração Antes da Reconfiguração
67
6 CONCLUSÃO E SUGESTÕES PARA TRABALHOS
FUTUROS
6.1 CONSIDERAÇÕES FINAIS
Esta dissertação apresentou uma metodologia para resolver o problema da
reconfiguração ótima de Sistemas Elétricos de Distribuição Radial, com o objetivo de
melhorar o desempenho do Método de Otimização por Colônia de Formigas (Ant System),
tendo em vista a obtenção de boas soluções para o problema em um tempo computacional
viável.
Para tanto, foi desenvolvido um algoritmo híbrido (AS_hibrido) resultado da
associação das Metaheurísticas Colônia de Formigas e Busca Tabu, com métodos auxiliares
de simplificação de rotinas computacionais e, também, estratégia de redução da convergência
prematura do AS.
Para testar o desempenho do método foram utilizados os sistemas de 16, 33, 69 e 84
barras. O algoritmo proposto apresentou resultados satisfatórios. As topologias finais para os
sistemas teste foram iguais aos melhores resultados encontrados na literatura, sendo que o
AS_hibrido forneceu a solução ótima em tempo computacional menor que os demais
algoritmos testados. Assim, para o sistema de 16 barras o AS_hibrido encontrou a melhor
solução em 0,15 segundo, computando uma ganho percentual do tempo de processamento de
68,75% em comparação com o AS simples. Para o sistema de 33 barras o AS_hibrido
encontrou a melhor solução em 0,47 segundo, computando uma ganho percentual do tempo
de processamento de 72,19% em comparação com o AS simples. Para o sistema de 69 barras
o AS_hibrido encontrou a melhor solução em 2,60 segundo, computando uma ganho
percentual do tempo de processamento de 50,10% em comparação com o AS simples. Por
fim, para o sistema de 84 barras o AS_hibrido encontrou a melhor solução em 73,54 segundo,
computando uma ganho percentual do tempo de processamento de 70,27% em comparação
com o AS simples.
A metodologia utilizada neste trabalho para construção das topologias, tanto na fase
das formigas quanto na pesquisa de vizinhança com a Busca Tabu, tem a vantagem de
fornecer sempre configurações radiais, dispensando assim a verificação da radialidade e o
esforço computacional decorrente desta.
68
A pesquisa local na vizinhança das configurações geradas pelas formigas contribuiu
para melhorar a solução, além de proporcionar redução do esforço computacional. Esta
característica deveu-se ao fato de que o algoritmo de formigas, que possui um esforço
computacional maior do que a busca tabu, necessitou gerar menos configurações.
O Método de Aceleração e a Simplificado do fluxo de Potência apresentaram
eficiência na eliminação do esforço computacional, proporcionando melhorias significativas
no tempo de convergência do algoritmo AS_hibrido.
O critério da Deposição Exponencial do Feromônio foi utilizado com sucesso visando
reduzir a convergência prematura proporcionada pela evaporação excessiva do feromônio.
Esta modificação proporcionou melhora substancial na qualidade da solução do AS,
principalmente para o sistema de 84 barras testado neste trabalho. Esta característica deve-se
ao fato de que o algoritmo, utilizando a taxa de evaporação variando exponencialmente,
mantem uma exploração maior do espaço de busca em comparação com o caso em que a taxa
de feromônio é constante. Isto porque, devido à modificação da forma de evaporação do
feromônio, o algoritmo irá minimizar o efeito da convergência prematura. Além disso, à
medida que o sistema torna-se maior, o algoritmo de formigas necessitará de mais iterações
para encontrar uma boa solução, tornando-o mais vulnerável a esta limitação.
Conforme testes realizados nos sistemas de 16, 33, 69 e 84 barra, o AS_híbrido obteve
um desempenho satisfatório utilizando a versão mais simples e básica do Algoritmo de
Formigas (Ant System), podendo a metodologia ser aplicada a versões melhoradas como o
Máx-Mín Ant System (MMAS) e o Ant Colony System (ACS). De forma complementar, o
AS_híbrido pode ser ainda combinado com a Simulated Annealing e programado em um
ambiente como o C++.
Por tanto, os métodos abordados neste trabalho podem ser empregados como
importantes ferramentas de melhoria do desempenho do ACO, quando aplicados a resolver
problemas de Reconfiguração de Sistemas Elétricos de Distribuição, fornecendo soluções de
boa qualidade em tempo computacional aceitável.
6.2 PROPOSTAS DE DESENVOLVIMENTOS FUTUROS
Seguindo a linha de pesquisa desenvolvida nesta dissertação e tendo em vista os
resultados obtidos, alguns tópicos tornam-se promissores para propostas de trabalhos futuros:
69
Implementar o algoritmo híbrido utilizando o Máx-Mín Ant System (MMAS) e o
Ant Colony System (ACS);
Combinar o Simulated Annealing com o AS_híbrido;
Utilizar o C++ para implementar o programa empregando técnicas específicas de
ordenação e fatoração a fim de reduzir as redundâncias.
71
REFERÊNCIAS BIBLIOGRÁFICAS
ABDELAZIZ A. Y.; MOHAMED F. M.; MECHAMER S. F.; BADR M. A. L. “Distribution
System Reconfiguration using a modified Tabu Search Algorithm,” Electric Power
Systems Research, Vol. 80, pp: 943-953, August 2010.
AMASIFEN, J. C. C.; ROMERO, R. A.; MATOVANI, J. R. S. Algoritmos evolutivos
dedicados a Reconfiguração de redes radiais de distribuição sob demandas fixas e
vairáveis – Estudo dos operadores genéticos e parâmetros de controle. Revista Controle
e Automação, Vol. 16, N° 3, pp. 303-317, Agosto e Setembro 2005.
BARAN, M. E. & WU, F. F., “Network Reconfiguration in Distribution Systems for Loss
Reduction and Load Balancing,” IEEE Transactions on Power Delivery, Vol. 4, pp:
1401-1407, Apr. 1989.
BONABEAU, E.; HENAUX, F.; GUÉRIN, S.; SNYERS, D.; KUNTZ, P.; THERAULAZ, G.
“Routing in telecommunication networks with “Smart” ant-like agentes”. In
Proceedings of IATA’98, Second International Workshop on Intelligent Agents for
Telecommunication Applications, volume Lectures Notes in AI vol. 1437, Berlin,
Germany. Springer Verlag. 1998.
BULLNHEIMER, B.; HARTL, R. F.; STRAUSS, C. “An improved ant system algorithm for
the vehicle routing problem”. Annals of Operations Research, v. 89, p. 319–328, 1999.
CHANG, C-F. “Reconfiguration and Capacitor Placement for Loss Reduction of
Distribution Systems by Ant Colony Search Algorithm”. IEEE Transactions on Power
Systems, vol. 23, n° 4, pp. 1747-1755, Nov. 2008.
CHANG, H.-C.; KUO, C.-C. “Network reconfiguration in distribution systems using
simulated annealing”. Electric Power Systems Research, Vol. 29, N° 3, 227-238, 1994.
CHAVES, A. A.; SENNE, E. L. F.; YANASSE, H. H. “Uma nova heurística para o
problema de minimização de trocas de ferramentas”. Gest. Prod., São Carlos, Vol. 19, n°
1, pp. 17-30, 2012.
CHIANG, H.-D.; JEAN-JUMEAU, R. “Optimal Network Reconfigurations in Distribution
Systems: Part 1: A New Formulation and A Solution Methodology”, IEEE Transactions
on Power Delivery, v. 5, n. 4 , pp. 1902-1909, Nov. 1990.
CHOI, J.-H.; KIM J.-C. “Network reconfiguration at the power distribution system with
dispersed generations for loss reduction”. In: Proceedings of the IEEE Power
Engineering Society Winter Meeting, v. 4, pp. 2363-2367, Singapore, Jan. 2000.
COLORNI, A.; DORIGO, M.; MANIEZZO, V.; TRUBIAN, M. “Ant System for job shop
scheduling”. JORBEL – Belgian Journal of Operations Research, Statistics and Computer
Science, vol. 34(1), p. 39–53, 1994.
72
COSTA, D.; HERTZ, A. “Ants can colour graphs”. Journal of the Operational Research
Society, Vol. 48, pp. 295–305, 1997.
DORIGO, M. Optimization, learning and natural algorithms. PhD thesis, Dipartimento di
elettronica e informazione, Politecnico di Milano, Italian, 1992.
DORIGO, M.; CARO, G. Di; GAMBARDELLA, L. M. “Ant Algorithms for Discrete
Optimization”. Artificial Life, v. 5, n. 2, p. 137–172, 1999.
DORIGO, M; MANIEZZO, V.; COLORNI, A. “Ant system: optimization by a colony of
coooperating agentes”. IEEE Transaction on systems, Man, and Cybernetics, Part. B:
Cybernetics, vol. 26, pp. 29-41, Feb. 1996.
FRAGA, M. C. P. Uma Metodologia Híbrida Colônia de Formigas – Busca Tabu –
Reconexão por Caminhos para Resolução do Problema de Roteamento de Veículos com
Janelas de tempo. Dissertação de Mestrado. Belo Horizonte, Brasil. CEFET – MG, 2006.
GLOVER, F. “Tabu Search, Part I”. ORSA Journal on Computing, Vol. 1, pp. 190-206,
1989.
GLOVER, F. “Tabu Search, Part II”. ORSA Journal on Computing, Vol. 2, pp. 4-32, 1990.
GOMES, F. V. 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. Rio
de Janeiro, Brasil. COPPE/UFRJ, 2005.
GOMEZ, J. F.; KHODR, H. M.; DE OLIVEIRA, P. M.; OCQUE, L.; YUSTA, J. M.;
URDANETA, A. J. “Ant colony system algorihm for the planning of primary
distribution circuits”. IEEE Transactions on Power Systems, vol. 19, pp. 996-1004, May
2004.
GUIMARÃES, M. A. N.; CASTRO, C. A. "Reconfiguration of distribution systems for loss
reduction using tabu search." Proc. 2005 IEEE Power System Computation Conf. Vol. 1,
pp. 1-6, August 2005.
HOU, Y-H; WU, Y-W; LU, L-J; XIONG, X-Y. “Generalized ant colony optmization for
economic dispatch of power systems”. In: Proceedings of International Conference on
Power System Technology, PowerCon 2002, vol. 1, pp. 225-229, Oct. 2002.
LORENZETI, J. F. C. Reconfiguração de Sistemas de Distribuição de Energia Elétrica para
a Melhoria das Condições de Operação com Relação à Estabilidade de Tensão.
Dissertação de Mestrado, Universidade Estadual de Campinas (UNICAMP), São Paulo,
2004.
MANIEZZO, V.; COLORNI, A. “The ant system applied to the quadratic assignment
problem”. IEEE Transactions on Knowledge and Data Engineering, vol. 11, pp. 769-778,
Sep./Oct. 1999.
73
MANTOVANI, J. R. S.; CASARI, F.; ROMERO, R. A. “Reconfiguração de Sistemas de
Distribuição Radiais Utilizando o Critério de Queda de Tensão”. Revista Controle e
Automação, Vol. 11, N° 3, PP. 150-159, 2000.
MCDERMOTT, T. E.; DREZGA, I.; BROADWATER, R. P. “A heuristic nonlinear
constructive method of distribution system reconfiguration”. IEEE Transactions on
Power System, vol. 14, n° 2, pp. 478-483, may 1999.
MEDEIROS, G. F.; KRIPKA, M. “Algumas Aplicações de Métodos Heurísticos na
Otimização de Estruturas”. Revista CIATEC – UPF, Vol. 4, p.p.19-32, 2012.
MERLIN, A.; BACK, G. “Search for minimum-loss operational spanning tree
configuration for urban power distribution system”. In: Proceedings of the 5th
Power
System Conference, pp. 1-18, Cambridge, Sep. 1975.
OLIVEIRA, L. W. Reconfiguração e Alocação Ótima de Capacitores em Sistemas de
Distribuição. Tese de Doutorado. Rio de Janeiro, Brasil, Universidade Federal do Rio de
Janeiro, 2009.
PAYÁ-ZAFORTEZA, I., YEPES V.; GONZÁLEZ-VIDOSA F.; HOSPITALER. A. “On the
Weibull cost estimation of building frames designed by simulated annealing”.
Meccanica, v. 45, pp. 693-704, 2010.
PEREIRA, F. S. Reconfiguração Ótima de Sistemas de Distribuição de Energia Elétrica
Baseado no Comportamento de Colônia de Formigas. Tese de Doutorado. São Paulo,
Brasil, Universidade de São Paulo, 2010.
REBELO, F. S. Otimização por Colônia de Formigas para Ambientes com Domínio de
Variáveis Contínuas. Monografia de Conclusão de Curso. Santa Catarina, Brasil.
UDESC, 2008.
RUDNICK, H.; HARNISCH, I.; SANHUEZA, R. "Reconfiguration of electric distribution
systems." Revista de la Facultad de Ingeniería-Universidad de Tarapacá, Vol. 4, 1997.
SHERAFAT, E.; HAFEZI, L.; SHEKARIAN, M. H. “A Modified ACO: Improving
Performance by Avoiding Premature Convergence”. Proceedings of the International
Conference on Genetic and Evolutionary Methods (GEM), pp. 158-161, 2008.
SISHAJ, P. S.; PADHY, N. P.; ANAND, R. S. “An ant colony system approach for unit
commitment problem”. International Journal of Electrical Power & Energy Systems, vol.
28, n° 5, pp. 293-358, June 2006.
SOUZA, B. A. “Como Funciona o MSP e o Que Precisa ser Modificado?”. Apostila do
curso de Engenharia Elétrica. Universidade Federal de Campina Grande. Rio Grande do
Norte. 13 p. 2005.
74
SOUZA, B. A.; SILVA, J. P. S.; FERREIRA, N. R.. “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, São Paulo,
2010.
SOUZA, B. A.; SILVA, J. P. S.; FERREIRA, N. R.; RAMOS, LEROY, U. R. “Aplicação de
Algoritmo Colônia de Formigas na Reconfiguração de Redes Elétricas de Distribuição”.
X SBAI – Simpósio Brasileiro de Automação Inteligente. Minas Gerais, Brasil, 2011.
SOUZA, S. S. F. “Algoritmo GRASP Especializado Aplicado ao Problema de
Reconfiguração de Alimentadores em Sistemas de Distribuição Radial”. Dissertação de
Mestrado. Ilha Solteira, Brasil, Univ. Estadual Paulista Júlio de Mesquita Filho, 2013.
STÜTZLE, T.; HOOS, H. H. “Max-Min Ant System”. Future Generation Computer Systems.
Vol. 16, pp. 889-914, 2000.
SU, T. C.; CHANG C. F.; CHIOU J. P. “Distribution Network Reconfiguration for Loss
Reduction by Ant Colony Search Algorithm,” Electric Power Systems Research, vol. 75,
pp. 190-199. August 2005.
TSAI, C. W.; LEE, C. Y.; CHIANG, M. C.; YANG, C. S. “A fast VQ Codebook Generation
Algorithm Via Pattern Reduction”. Pattern Recognition Letters, vol. 30, pp. 653-660,
2009.
TSAI, C. W.; TSENG, S. P.; YANG, C. S.; CHIANG, M. C. “PREACO: A Fast ant Colony
Optimization For Codebook Generation”. Applied Soft Computing, Vol. 13, pp. 3008-
3020, June 2013.
TSENG, J-H; LIU, Y-H. “Application of the ant colony system for optimum switch
adjustment”. In: IEEE/PES Transmission and Distribution Conference and Exhibition:
Asia Pacific, vol. 2, pp. 751-756, Oct. 2002.
TSENG, S. P.; TSAI, C. W.; CHIANG, M. C.; YANG, C. S. “A Fast Ant Colony
Optimization for Traveling Salesman Problem”. Evolutionary Computation (CEC), 2010
IEEE Congress on, pp. 1-6, July 2010.
VLACHOGIANNIS, J. G.; HATZIARGYRIOU, N. D.; LEE, K. Y. “Ant colony system-
based algorithm for constrained load flow problem”. IEEE Transactions on Power
Systems, vol. 20, n° 3, pp. 1241-1249, Aug. 2005.
ZHOU, P.; DENG, Q. “Hybridizing Fast Taboo Search with ant Colony Optmization
Algorithm for Solving Large Scale permutation Flow Shop Scheduling Problem”. IEEE
International Conference on Granular Computing, pp. 809-813, 2009.
ZVIETCOVICH, W. G. Reconfiguração de Sistemas de Distribuição de Energia Elétrica
Utilizando a Metaheurística Busca Tabu em Vizinhança Variável. Dissertação de
Mestrado. São Paulo, Brasil, Univ. Estadual Paulista Júlio de Mesquita Filho, 2006.
75
APÊNDICE A
DADOS DOS SISTEMAS TESTADOS
A1 SISTEMA DE 16 BARRAS
Linha Barra
inicial
Barra
final
Resistência
(pu)
Reatância
(pu)
Potência
(MW)
Potência
(MVAr)
11 1 4 0,075 0,1 2,000 1,600
12 4 5 0,08 0,11 3,000 0,400
13 4 6 0,09 0,18 2,000 -0,400
14 6 7 0,04 0,04 15,000 1,200
16 2 8 0,11 0,11 4,000 2,700
18 8 9 0,08 0,11 5,000 1,800
17 8 10 0,11 0,11 1,000 0,900
19 9 11 0,11 0,11 0,600 -0,500
20 9 12 0,08 0,11 4,500 -1,700
22 3 13 0,11 0,11 1,000 0,900
24 13 14 0,09 0,12 1,000 -1,100
23 13 15 0,08 0,11 1,000 0,900
25 15 16 0,04 0,04 2,100 -0,800
15 5 11 0,04 0,04
21 10 14 0,04 0,04
26 7 16 0,12 0,12
76
A2 SISTEMA DE 33 BARRAS
Linha Barra
inicial
Barra
final
Resistência
(Ω)
Reatância
(Ω)
Potência
(KW)
Potência
(KVAr)
1 1 2 0,0922 0,0470 100 60
2 2 3 0,4930 0,2511 90 40
3 3 4 0,3660 0,1864 120 80
4 4 5 0,3811 0,1941 60 30
5 5 6 0,8190 0,7070 60 20
6 6 7 0,1872 0,6188 200 100
7 7 8 0,7114 0,2351 200 100
8 8 9 1,0300 0,7400 60 20
9 9 10 1,0440 0,7400 60 20
10 10 11 0,1966 0,0650 45 30
11 11 12 0,3744 0,1238 60 35
12 12 13 1,4680 1,1550 60 35
13 13 14 0,5416 0,7129 120 80
14 14 15 0,5910 0,5260 60 10
15 15 16 0,7463 0,5450 60 20
16 16 17 1,2890 1,7210 60 20
17 17 18 0,7320 0,5740 90 40
18 2 19 0,1640 0,1565 90 40
19 19 20 1,5042 1,3554 90 40
20 20 21 0,4095 0,4784 90 40
21 21 22 0,7089 0,9373 90 40
22 3 23 0,4512 0,3083 90 50
23 23 24 0,8980 0,7091 420 200
24 24 25 0,8960 0,7011 420 200
25 6 26 0,2030 0,1034 60 25
26 26 27 0,2842 0,1447 60 25
27 27 28 1,0590 0,9337 60 20
28 28 29 0,8042 0,7006 120 70
29 29 30 0,5075 0,2585 200 600
30 30 31 0,9744 0,9630 150 70
31 31 32 0,3105 0,3619 210 100
32 32 33 0,3410 0,5302 60 40
33 8 21 2,0000 2,0000
34 9 15 2,0000 2,0000
35 12 22 2,0000 2,0000
36 18 33 0,5000 0,5000
37 25 29 0,5000 0,5000
77
A3 SISTEMA DE 69 BARRAS
Linha Barra
inicial
Barra
final
Resistência
(Ω)
Reatância
(Ω)
Potência
(KW)
Potência
(KVAr)
1 1 2 0,0005 0,0012 0 0
2 2 3 0,0005 0,0012 0 0
3 3 4 0 0 0 0
4 4 5 0,0015 0,0036 0 0
5 5 6 0,0251 0,0294 0 0
6 6 7 0,3660 0,1864 0,8780 0,7200
7 7 8 0,3811 0,1941 13,4550 0,7200
8 8 9 0,0922 0,0470 24,8870 17,8100
9 9 10 0,0493 0,0251 10,0000 7,2080
10 10 11 0,8190 0,2707 9,3330 6,6660
11 11 12 0,1872 0,0619 48,5000 34,6090
12 12 13 0,7114 0,2351 48,5000 34,6090
13 13 14 1,0300 0,3400 2,7100 1,8210
14 14 15 1,0440 0,3450 2,7100 1,5210
15 15 16 1,0580 0,3496 0 0
16 16 17 0,1966 0,0650 15,1760 10,1980
17 17 18 0,3744 0,1238 16,5000 11,7750
18 18 19 0,0047 0,0016 16,5000 11,7750
19 19 20 0,3276 0,1083 0 0
20 20 21 0,2106 0,0696 0,3160 0,2120
21 21 22 0,3416 0,1129 37,9830 27,1000
22 22 23 0,0140 0,0046 1,7620 1,1840
23 23 24 0,1591 0,0526 0 0
24 24 25 0,3463 0,1145 9,3900 6,6700
25 25 26 0,7488 0,2475 0 0
26 26 27 0,3089 0,1021 4,6670 3,3300
27 27 28 0,1732 0,0572 4,6670 3,3301
28 3 29 0,0044 0,0108 8,6670 6,1850
29 29 30 0,0640 0,1565 8,6670 6,1850
30 30 31 0,3978 0,1315 0 0
31 31 32 0,0702 0,0232 0 0
32 32 33 0,3510 0,1160 0 0
33 33 34 0,8390 0,2816 4,5820 3,2600
34 34 35 1,7080 0,5646 6,5010 5,5490
35 35 36 1,4740 0,4873 1,9200 1,2900
36 4 37 0,0044 0,0108 8,6670 6,1850
37 37 38 0,0640 0,1565 8,6670 6,1850
38 38 39 0,1053 0,1230 0 0
39 39 40 0,0304 0,0355 8,0000 5,7090
40 40 41 0,0018 0,0021 8,0000 5,7090
41 41 42 0,7283 0,8509 0,3920 0,3250
42 42 43 0,3100 0,3623 0 0
43 43 44 0,0410 0,0478 2,0000 1,4270
44 44 45 0,0092 0,0116 0 0
45 45 46 0,1089 0,1373 3,0760 8,7870
78
Linha Barra
inicial
Barra
final
Resistência
(Ω)
Reatância
(Ω)
Potência
(KW)
Potência
(KVAr)
46 46 47 0,0009 0,0012 3,0760 8,7870
47 5 48 0,0034 0,0084 0 0
48 48 49 0,0851 0,2083 26,3500 18,8000
49 49 50 0,2898 0,7091 28,2260 91,4920
50 50 51 0,0822 0,2011 128,2260 91,4920
51 9 52 0,0928 0,0473 13,5120 9,4420
52 52 53 0,3319 0,1114 1,2020 0,8940
53 10 54 0,1740 0,0886 1,4490 1,1620
54 54 55 0,2030 0,1034 8,7870 6,3220
55 55 56 0,2842 0,1447 8,0000 5,7080
56 56 57 0,2813 0,1433 0 0
57 57 58 1,5900 0,5337 0 0
58 58 59 0,7837 0,2630 0 0
59 59 60 0,3042 0,1006 0,6670 24,0250
60 60 61 0,3861 0,1172 0 0
61 61 62 0,5075 0,2555 414,6670 295,9100
62 62 63 0,9740 0,0496 10,6670 7,6120
63 63 64 0,1450 0,0738 0 0
64 64 65 0,7105 0,3619 75,6700 53,8730
65 65 66 1,0410 0,5302 19,6700 13,9120
66 12 67 0,2012 0,0611 6,0000 4,2820
67 67 68 0,0047 0,0014 6,0000 4,2820
68 13 69 0,7394 0,2444 9,3330 6,6600
69 69 70 0,0047 0,0016 9,3330 6,6604
70 12 44 0,5000 0,5000
71 14 22 0,5000 0,5000
72 16 47 1,0000 1,0000
73 51 60 2,0000 2,0000
74 28 66 1,0000 1,0000
79
A4 SISTEMA DE 84 BARRAS
Linha Barra
inicial
Barra
final
Resistência
(Ω)
Reatância
(Ω)
Potência
(KW)
Potência
(KVAr)
1 1 2 0,1944 0,6624 0 0
2 2 3 0,2096 0,4304 100,00 50,00
3 3 4 0,2358 0,4842 300,00 200,00
4 4 5 0,0917 0,1883 350,00 250,00
5 5 6 0,2096 0,4304 220,00 100,00
6 6 7 0,0393 0,0807 1100,00 800,00
7 7 8 0,0405 0,1380 400,00 320,00
8 8 9 0,1048 0,2152 300,00 200,00
9 8 10 0,2358 0,4842 300,00 230,00
10 8 11 0,1048 0,2152 300,00 260,00
11 1 12 0,0786 0,1614 0 0
12 12 13 0,3406 0,6944 1200,00 800,00
13 13 14 0,0262 0,0538 800,00 600,00
14 13 15 0,0786 0,1614 700,00 500,00
15 1 16 0,1134 0,3864 0 0
16 16 17 0,0524 0,1076 300,00 150,00
17 17 18 0,0524 0,1076 500,00 350,00
18 18 19 0,1572 0,3228 700,00 400,00
19 19 20 0,0393 0,0807 1200,00 1000,00
20 20 21 0,1703 0,3497 300,00 300,00
21 21 22 0,2358 0,4842 400,00 350,00
22 22 23 0,1572 0,3228 50,00 20,00
23 22 24 0,1965 0,4035 50,00 20,00
24 24 25 0,1310 0,2690 50,00 10,00
25 1 26 0,0567 0,1932 50,00 30,00
26 26 27 0,1048 0,2152 100,00 60,00
27 27 28 0,2489 0,5111 100,00 70,00
28 28 29 0,0486 0,1656 1800,00 1300,00
29 29 30 0,1310 0,2690 200,00 120,00
30 1 31 0,1965 0,3960 0 0
31 31 32 0,1310 0,2690 1800,00 1600,00
32 32 33 0,1310 0,2690 200,00 150,00
33 33 34 0,0262 0,0538 200,00 100,00
34 34 35 0,1703 0,3497 800,00 600,00
35 35 36 0,0524 0,1076 100,00 60,00
36 36 37 0,4978 1,0222 100,00 60,00
37 37 38 0,0393 0,0807 20,00 10,00
38 38 39 0,0393 0,0807 20,00 10,00
39 39 40 0,0786 0,1614 20,00 10,00
40 40 41 0,2096 0,4304 20,00 10,00
41 39 42 0,1965 0,4035 200,00 160,00
42 42 43 0,2096 0,4304 50,00 30,00
43 1 44 0,0486 0,1656 0 0
44 44 45 0,0393 0,0807 30,00 20,00
45 45 46 0,1310 0,2690 800,00 700,00
46 46 47 0,2358 0,4842 200,00 150,00
47 1 48 0,2430 0,8280 0 0
80
Linha Barra
inicial
Barra
final
Resistência
(Ω)
Reatância
(Ω)
Potência
(KW)
Potência
(KVAr)
48 48 49 0,0655 0,1345 0 0
49 49 50 0,0655 0,1345 0 0
50 50 51 0,0393 0,0807 200,00 160,00
51 51 52 0,0786 0,1614 800,00 600,00
52 52 53 0,0393 0,0807 500,00 300,00
53 53 54 0,0786 0,1614 500,00 350,00
54 54 55 0,0524 0,1076 500,00 300,00
55 55 56 0,1310 0,2690 200,00 80,00
56 1 57 0,2268 0,7728 0 0
57 57 58 0,5371 1,1029 30,00 20,00
58 58 59 0,0524 0,1076 600,00 420,00
59 59 60 0,0405 0,1380 0 0
60 60 61 0,0393 0,0807 20,00 10,00
61 61 62 0,0262 0,0538 20,00 10,00
62 62 63 0,1048 0,2152 200,00 130,00
63 63 64 0,2358 0,4842 300,00 240,00
64 64 65 0,0243 0,0828 300,00 200,00
65 1 66 0,0486 0,1656 0 0
66 66 67 0,1703 0,3497 50,00 30,00
67 67 68 0,1215 0,4140 0 0
68 68 69 0,2187 0,7452 400,00 360,00
69 69 70 0,0486 0,1656 0 0
70 70 71 0,0729 0,2484 0 0
71 71 72 0,0567 0,1932 2000,00 1500,00
72 72 73 0,0262 0,0528 200,00 150,00
73 1 74 0,3240 1,1040 0 0
74 74 75 0,0324 0,1104 0 0
75 75 76 0,0567 0,1932 1200,00 950,00
76 76 77 0,0486 0,1656 300,00 180,00
77 1 78 0,2511 0,8556 0 0
78 78 79 0,1296 0,4416 400,00 360,00
79 79 80 0,0486 0,1656 2000,00 1300,00
80 80 81 0,1310 0,2640 200,00 140,00
81 81 82 0,1310 0,2640 500,00 360,00
82 82 83 0,0917 0,1883 100,00 30,00
83 83 84 0,3144 0,6456 400,00 360,00
84 6 56 0,1310 0,2690 0 0
85 8 61 0,1310 0,2690
86 12 44 0,1310 0,2690
87 13 73 0,3406 0,6994
88 14 77 0,4585 0,9415
89 15 19 0,5371 1,0824
90 17 27 0,0917 0,1883
91 21 84 0,0786 0,1614
92 29 33 0,0524 0,1076
93 30 40 0,0786 0,1614
94 35 47 0,0262 0,0538
95 41 43 0,1965 0,4035
96 54 65 0,0393 0,0807