UNIVERSIDADE FEDERAL DE OURO PRETO
ESCOLA DE MINAS - EM
COLEGIADO CURSO DE ENGENHARIA DE CONTROLE E
AUTOMAÇÃO - CECAU
INSTALAÇÃO DE CAPACITORES PARA REDUÇÃO
DAS PERDAS EM UMA REDE DE DISTRIBUIÇÃO DE
ENERGIA ELÉTRICA VIA ALGORITMOS GENÉTICOS
MONOGRAFIA DE GRADUAÇÃO EM
ENGENHARIA DE CONTROLE E AUTOMAÇÃO
Douglas Morais Maurício
Ouro Preto , 2007
DOUGLAS MORAIS MAURÍCIO
INSTALAÇÃO DE CAPACITORES PARA REDUÇÃO
DE PERDAS EM REDES DE DISTRIBUIÇÃO DE ENERGIA
ELÉTRICA VIA ALGORITMOS GENÉTICOS
Monografia apresentada ao Curso de
Engenharia de Controle e Automação
da Universidade Federal de Ouro
Preto como parte dos requisitos para a
obtenção de Grau em Engenheiro de
Controle e Automação.
Orientador: Agnaldo J. Rocha Reis
Co-orientador: Marcone Jamilson Freitas Souza
Ouro Preto
Escola de Minas – UFOP
Agosto/2007
ii
iii
Aos meus pais, verdadeiros responsáveis
por tudo que sou e sempre serei.
iv
AGRADECIMENTOS
Agradeço aos meus pais, exemplos de vida para mim, por todo esforço e luta para que
eu pudesse chegar até aqui. À minha irmã Vivi e ao Coiso por também contribuírem
nessa caminhada. Aos meus tios e tias por todo incentivo e apoio. Aos meus velhos
amigos e aos novos que fiz nesses anos de curso. Ao professor Agnaldo, por toda à
disponibilidade e empenho em me ajudar. À Talytha, simplesmente por fazer parte da
minha vida.
v
“Jamais considere seus estudos como uma obrigação,
mas como uma oportunidade invejável para aprender
a conhecer a influência libertadora da beleza do
reino do espírito, para seu próprio prazer pessoal e
para proveito, da comunidade à qual
seu futuro trabalho pertencer.”
Albert Einstein
vi
SUMÁRIO
LISTA DE FIGURAS................................................................................................VIII
LISTA DE TABELAS...................................................................................................IX
LISTA DE ABREVIATURAS E SIGLAS...................................................................X
I
INTRODUÇÃO......................................................................................................13
1.1
1.2
OBJETIVO.................................................................................................................................,,14
METODOLOGIA..........................................................................................................................14
II
REVISÃO BIBLIOGRÁFICA.............................................................................15
2.1
O CONROLE DA ENERGIA REATIVA..................................................................................................15
2.2
POTÊNCIA ATIVA E POTÊNCIA REATIVA.........................................................................................16
2.3
CONSEQÜÊNCIAS DO EXCESSO DE ENERGIA REATIVA NAS REDES E
INSTALAÇÕES.............................................................................................................................................17
2.3.1
2.3.2
2.3.3
Perdas na rede.....................................................................................................................17
Quedas de tensão.................................................................................................................17
Sub-utlização da capacidade instalada...............................................................................18
2.4
COMPENSAÇÃO ATRAVÉS DA INJEÇÃO CLÁSSICA DE REATIVOS............................................18
2.5
CAPACITOR..............................................................................................................................................18
2.6
CONFIGURAÇÃO TÍPICA DOS CAPACITORES..................................................................................19
2.6.1
2.6.2
2.6.3
Banco fixo...........................................................................................................................19
Banco semi-automático......................................................................................................20
Banco automático...............................................................................................................20
2.7
OS ALGORITMOS GENÉTICOS..............................................................................................................21
2.8
CODIFICAÇÃO DOS INDIVÍDUOS...........................................................................................................23
2.8.1
2.9
O uso de codificação real...................................................................................................24
POPULAÇÃO INICIAL.............................................................................................................................. 25
2.10
AVALIAÇÃO DOS INDIVÍDUOS............................................................................................................ 26
2.11
RESTRIÇÕES............................................................................................................................................. 26
2.11.1
2.11.2
2.11.3
2.11.4
2.12
Função de Penalidade..................................................................................................... 27
Eliminação de soluções................................................................................................... 27
Reparo da solução........................................................................................................... 27
Decodificadores de cromossomos................................................................................... 27
MÉTODOS DE SELEÇÃO DE INDIVÍDUOS....................................................................................... 28
2.12.1
Roleta Estocástica........................................................................................................... 28
2.12.2
Torneio Estocástico........................................................................................................ 29
2.12.3
Elitismo.......................................................................................................................... .29
2.13 OPERADORES GENÉTICOS................................................................................................. 30
2.13.1
Recombinação ou Crossover.......................................................................................... 30
2.13.2
Mutação.......................................................................................................................... 32
2.14
2.15
CONVERGÊNCIA DO AG.....................................................................................................................33
TÉCNICAS PARA MANTER A DIVERSIDADE POPULACIONAL
EM ALGORITMOS GENÉTICOS ............................................................................................................33
2.15.1
2.15.2
Compartilhamento de Recursos...................................................................................... 34
Evolução Cooperativa....................................................................................................... 35
vii
2.16
III
O ALGORITMO GENÉTICO SIMPLES (AGS)..................................................................... 36
METODOLOGIA............................................................................................... 37
3.1
DEFINIÇÃO DO PROBLEMA.................................................................................................................. 37
3.1.1
3.1.2
3.1.3
Formulação básica para o problema de fluxo de carga.................................................... 37
Um exemplo de cálculo de fluxo de carga.......................................................................... 40
Resolução do fluxo de carga para o IEEE 14 Node Test Feeder....................................... 42
3.2
BASE DE DADOS .......................................................................................................................................42
3.3
ETAPA DE MODELAGEM DO PROBLEMA ...........................................................................................43
3.3.1
3.3.2
3.3.3
3.3.4
3.4
A Representação da solução............................................................................................... 44
Definição da Função de Avaliação utilizada........................................................................44
Definição da Função de Seleção.......................................................................................... 44
Definição dos Operadores Genéticos utilizados...................................................................45
VALIDAÇÃO DO MODELO COMPUTACIONAL ..................................................................................45
3.4.1
3.4.2
Linguagem de programação proposta................................................................................ 45
Características do AG proposto...........................................................................................46
IV RESULTADOS OBTIDOS.....................................................................................49
4.1
DISCUSSÃO DOS RESULTADOS OBTIDOS....................................................................................... 50
V CONCLUSÃO E TRABALHOS FUTUROS ......................................................52
REFERÊNCIAS BIBLIOGRÁFICAS....................................................................... 53
viii
LISTA DE FIGURAS
FIGURA 2.1 – TRIÂNGULO DAS POTÊNCIAS.............................................................16
FIGURA 2.2 - O CAPACITOR ..........................................................................................19
FIGURA 2.3 - FUNÇÃO MULTIMODAL DE DIFÍCIL MAXIMIZAÇÃO.................... 22
FIGURA 2.4 - EXEMPLO DE CODIFICAÇÃO BINÁRIA DE UM INDIVÍDUO.........23
FIGURA 2.5 - SEGMENTAÇÃO DE UM ESPAÇO DE PARÂMETROS
DE 3 VARIÁVEIS.............................................................................................................. 26
FIGURA 2.6 - EXEMPLO ILUSTRATIVO DE UMA ROLETA ESTOCÁSTICA......... 29
FIGURA 2.7 - DESEMPENHO DO AG COM ELISTISMO............................................ 30
FIGURA 2.8 - CROSSOVER DE 1 PONTO......................................................................31
FIGURA 2.9 - CROSSOVER MULTI-PONTOS............................................................... 31
FIGURA 2.10 - CROSSOVER UNIFORME..................................................................... 32
FIGURA 2.12 – MUTAÇÃO.............................................................................................. 33
FIGURA 2.12 - FUNÇÃO SHARING LINEAR ................................................................35
FIGURA 3.1 - TRÊS BARRAS UTILIZADAS PARA O EXEMPLO DE CÁLCULO DE
FLUXO DE CARGA...........................................................................................................41
FIGURA 3.2 - RESOLUÇÃO DO EXEMPLO DE FLUXO DE CARGA.........................41
FIGURA 3.3 - TOPOLOGIA DO IEEE 14 NODE TEST FEEDER..................................43
FIGURA 3.4 - GRÁFICO DA FUNÇÃO A SER MINIMIZADA.....................................47
FIGURA 3.5 - SAÍDA GRÁFICA PARA UMA DAS SIMULAÇÕES FEITAS...............50
FIGURA 3.6 - ANÁLISE DE PROBABILIDADE EMPÍRICA.........................................51
ix
LISTA DE TABELAS
TABELA 3.1 – TIPOS DE BARRAS DO SISTEMA........................................................38
TABELA 3.2 - CARACTERÍSTICAS DO AG PROPOSTO............................................ 46
TABELA 3.3 – DADOS DAS PERDAS ATIVAS GERADAS.........................................48
TABELA 3.4 – DADOS DO TIPO DE CAPACITOR UTILIZADO.................................48
TABELA 3.5 – RESULTADOS OBTIDOS COM 8 SIMULAÇÕES................................49
x
LISTA DE ABREVIATURAS E SIGLAS
FP
Fator de Potência
FPi
Fator de Potência Inicial
FPf
Fator de Potência Final
pi
Probabilidade de sobrevivência do indivíduo i
fi
Avaliação do indivíduo i
AG
Algoritmos Genéticos
PFC
Problema do Fluxo de Carga
PAC
Problema de Alocação de Capacitores
xi
RESUMO
Sabe-se que o maior volume de perdas ocorre nos sistemas de distribuição
de energia elétrica. Capacitores são largamente utilizados nos alimentadores primários
dos sistemas de distribuição para compensar potência reativa e conseqüentemente obter
melhor perfil de tensão, reduções das perdas de potência e energia e aumento da
capacidade da rede de distribuição em atender carga ativa. Os benefícios reais obtidos
com a instalação de capacitores em sistemas de distribuição dependem das
características dos equipamentos e da forma como é feita essa instalação.
Especificamente, dependem do número e tamanho dos capacitores, de sua localização,
do tipo (fixos ou chaveados) e do esquema de controle utilizado. Neste trabalho, o PAC
(Problema de Alocação de Capacitores), tratado restringe-se ao problema de encontrar a
localização, o número e a dimensão dos capacitores a serem instalados. A decisão do
local ótimo de instalação de bancos de capacitores corresponde a um problema de
otimização combinatória, para o qual, muitos métodos de solução têm sido propostos.
Diante da natureza do PAC os métodos de solução que mais se destacam são os da
categoria das metaheurísticas. Neste trabalho foi utilizado o método metaheurístico dos
Algoritmos Genéticos. A aplicação foi desenvolvida em linguagem Matlab, utilizando
como fonte de dados o IEEE 14 Node Test Feeder.
xii
ABSTRACT
It is well known that the major portion of active power losses happen in the
electric power distribution feeders. The capacitors are broadly used in the primary
feeders to compensate reactive power and consequently to obtain better voltage profile,
reductions of power and energy losses, and increase the distribution network capacity in
supplying active power demand. The real advantages obtained with installation of
capacitors in distribution systems depend of characteristics and way as is made this
installation. Specifically it depend of number and size of capacitors, localization, types
(fix or switched) and control project used. In this monograph, the PAC (Capacitors
Allocation Problem) studied restrict it to find the placement number and size of
capacitors that will be installed. The decision for capacitors bank optimal place
installation is a combinatorial optimization problem, which many solve methods had
been considered. In face nature of PAC, methods for solve it that most detach are the
metaheuristhics category. In this monograph was used metaheuristic method of Genetic
Algorithms. The application was developed in Matlab language programation, using
IEEE 14 Node Test Feeder as base data.
13
I
INTRODUÇÃO
Capacitores são fontes de energia reativa. Os objetivos de sua aplicação
em sistemas de potência é a compensação de energias reativas produzidas por cargas
indutivas ou reatâncias de linhas. Quando adequadamente utilizados, permitem a
obtenção de um conjunto de benefícios correlatos que incluem a redução de perdas de
energia, correção dos perfis de tensões, controle dos fluxos de potência, melhoria do
fator de potência e aumento da capacidade dos sistemas. No contexto desse trabalho, a
instalação de capacitores é avaliada conjuntamente sob a ótica de redução de perdas e
do conseqüente aumento do lucro na distribuição de energia. Aspectos operacionais
também são levados em conta, pois geram restrições que não podem ser desprezadas
quando se planeja instalar capacitores em uma rede elétrica real. As perdas técnicas
podem ser reduzidas pela instalação de capacitores em pontos adequados da rede,
proporcionando “geração” de energia reativa nas proximidades das cargas. Dessa forma,
diminui-se (ou, no limite, elimina-se) a componente associada ao fluxo de corrente
reativa nas linhas.
Os benefícios reais obtidos com a instalação de capacitores em sistemas
de distribuição dependem das características dos equipamentos e da forma como é feita
essa instalação. Especificamente, dependem do número e tamanho dos capacitores, de
sua localização, do tipo (fixos ou chaveados) e do esquema de controle utilizado. Nesta
monografia, o PAC (Problema de Alocação de Capacitores) tratado restringe-se ao
problema de encontrar a localização, o número e a dimensão dos capacitores a serem
instalados.
Antes da década de 50 os capacitores para redução de perdas eram
colocados nas subestações, no início dos alimentadores. Com a constatação da
vantagem de instalá-los em pontos mais próximos às cargas e do aparecimento de
equipamentos de menor porte, que podiam ser instalados em postes de distribuição, o
problema de encontrar sua melhor localização se tornou mais complexo.
Sabe-se que o PAC é um problema de otimização combinatória de difícil
solução e que muitos métodos têm sido propostos para solucioná-lo. Um esquema
classificatório das técnicas de solução já propostas pode ser encontrado em Ng et al.
(2000). Dentre os muitos enfoques possíveis, destacam-se as metaheurísticas, já que
métodos exatos não são para tratar redes de tamanho real. Já foram realizados outros
14
trabalhos utilizando-se métodos metaheurísticos como Busca Tabu e Simulated
Annealing.
Esta monografia apresenta uma proposta para solução do PAC, com uma abordagem via
algoritmos genéticos (AG).
1.1 Objetivo
Determinar a localização e o tamanho dos bancos capacitores a serem
instalados de forma que seja obtida uma redução significativa das perdas elétricas com
conseqüente aumento do lucro financeiro oriundo da distribuição
1.2 Metodologia
A partir dos dados colhidos do IEEE 14 Node Test Feeder, que simula
uma rede elétrica de distribuição, cuja estrutura é radial (disponibilizado pelo IEEE Institute of Electrical and Electronics Engineers), a representação do PAC deverá ser a
de um cromossomo cujos alelos assumem valores inteiros (correspondentes ao número
de capacitores a serem instalados) e inicialmente são todos iguais a zero. A dimensão
desse cromossomo é igual a número de barras em que se podem alocar os capacitores.
Se o alelo correspondente a uma barra i apresenta algum valor diferente de zero, isso
significa que deverá naquela barra i ser instalado um banco com número de capacitores
correspondente ao valor do alelo, caso contrário à barra não receberá capacitores.
15
II REVISÃO BIBLIOGRÁFICA
2.1 O controle da energia reativa
O controle da energia reativa consumida pelas indústrias e prédios
comerciais está vinculado à isenção dos faturamentos adicionais nas contas de energia
(excedente de energia reativa) e, intimamente ligado à qualidade de energia das
instalações. A injeção de energia reativa em sistemas com cargas distorcidas (que
contêm harmônicas) e a necessária isenção de transientes de manobra são um desafio
que os profissionais da área de aplicação de equipamentos devem conhecer. A energia
reativa indutiva, utilizada por determinadas cargas para a criação dos campos elétricos e
magnéticos, circula pela rede elétrica aumentando a potência total transportada e
distribuída pelas concessionárias de energia elétrica sem se converter em trabalho útil.
Para minimizar esse tráfego de potência reativa na rede, utiliza-se, via de regra, a
inclusão de bancos de capacitores numa dada instalação.
O oposto da energia reativa indutiva é a energia reativa capacitiva, e por isto
ela é expressa na mesma unidade, porém com sinal contrário. A energia reativa
capacitiva é normalmente fornecida ao sistema elétrico por capacitores. Outra forma de
se explicar energia reativa é considerando-se o sincronismo entre tensão e corrente.
Quando temos apenas cargas resistivas, a tensão e a corrente estão perfeitamente em
fase. Ao ligarmos uma carga indutiva (motor), a corrente se "atrasa" em relação à
tensão. As cargas capacitivas fazem o oposto, ou seja, "atrasam" a tensão em relação à
corrente. Por esta razão é que utilizamos capacitores para corrigir o baixo fator de
potência causado pelas cargas indutivas da maioria das instalações elétricas. A energia
total (ou aparente) é a soma vetorial da energia reativa (indutiva e capacitiva) com a
energia ativa, aquela necessária às cargas resistivas. Como as energias ativas e reativas
têm 90° de defasagem entre si, a soma vetorial resulta em:
Etotal = Eativa 2 + Ereativa 2
16
2.2 Potência Ativa e Potência Reativa
A Potência Ativa é a potência que efetivamente realiza trabalho gerando
calor, luz, movimento etc., sendo medida em watts [W]. Já a Potência Reativa é a
potência usada apenas para criar e manter os campos eletromagnéticos das cargas
indutivas. Assim, enquanto a potência ativa é sempre consumida na execução de
trabalho, a potência reativa, além de não produzir trabalho, circula entre a carga e a
fonte de alimentação, ocupando um espaço no sistema elétrico que poderia ser utilizado
para fornecer mais energia ativa. Podemos definir o fator de potência (cos φ) a partir da
relação entre a potência ativa e a potência aparente (medida em volt ampères [VA]). Ele
indica a eficiência do uso da energia. Um alto fator de potência indica uma eficiência
alta e inversamente, um fator de potência baixo indica baixa eficiência. Um triângulo
retângulo é freqüentemente utilizado para representar as relações entre KW, KVAr, e
KVA. Define-se fator de potência como sendo o quociente entre a potência ativa (KW)
e a potência aparente (KVA). A Figura 2.1 ilustra o “Triângulo das Potências” de onde,
através dos conceitos de trigonometria, o Fator de Potência (cos φ) pode ser calculado.
cos ϕ =
KW
KVA
= FP
(2.1)
Figura 2.1 – Triângulo das Potências.
FONTE: DORNELLAS, 1996.
17
2.3 Conseqüências do excesso de energia reativa nas redes e instalações
Sabe-se que uma das principais conseqüências decorrentes do excesso de
energia reativa nas redes e instalações elétricas são os baixos valores de fator de
potência. Essa condição resulta em aumento da corrente total que circula nas redes de
distribuição de energia elétrica da Concessionária e das unidades consumidoras,
podendo sobrecarregar as subestações, as linhas de transmissão e distribuição,
prejudicando assim a estabilidade e as condições de aproveitamento. Segue abaixo
alguns exemplos dos principais problemas causados por um baixo FP. São eles:
2.3.1 Perdas na rede
As perdas de energia elétrica ocorrem em forma de calor e são
proporcionais ao quadrado da corrente total. Como essa corrente cresce com excesso de
energia reativa, estabelece-se uma relação direta entre o incremento das perdas e o baixo
fator de potência, provocando aumento do aquecimento de condutores e equipamentos.
Redução das perdas (%) = (1-FPi²/FPf ²) x 100
(2.2)
Onde FPi e FPf são os fatores de potência inicial e final , respectivamente.
2.3.2 Quedas de Tensão
O aumento da corrente devido ao excesso reativo leva à queda de tensão
acentuada, podendo ocasionar a interrupção do fornecimento de energia elétrica e a
sobrecarga em certos elementos da rede. Esse risco é acentuado, sobretudo durante os
períodos nos quais a rede é fortemente solicitada. As quedas de tensão podem provocar
ainda, diminuição da intensidade luminosa nas lâmpadas e aumento da corrente nos
motores.
18
2.3.3 Sub-utilização da capacidade instalada
A energia reativa ao sobrecarregar uma instalação elétrica inviabiliza a
sua utilização, condicionando a instalação de novas cargas a investimentos que seriam
evitáveis se houvesse um controle da quantidade de energia elétrica presente na
instalação. O “espaço” ocupado pela energia reativa poderia ser então utilizado para o
atendimento de novas cargas.
A seguir será descrita uma solução muito utilizada para a correção de baixo
fator de potência.
2.4 A compensação através da injeção clássica de reativos
Nas últimas décadas, a injeção de reativos tem sido uma valiosa
ferramenta para melhorar a regulação de tensão e a eficiência de equipamentos, e
reduzir perdas e correntes elétricas nos circuitos de instalações industriais e comerciais
de grande porte. Do ponto de vista do consumidor, sua popularização ocorreu em
maiores proporções quando as concessionárias passaram a multar os consumidores que
apresentassem valores médios mensais de fator de potência menores que um valor fixo,
definido inicialmente em 85% (atualmente esse valor, definido pela Portaria 1569, de
1993, é de 92%).
Com isso, veio então uma maneira de se compensar a energia reativa que
circula pelo sistema elétrico, que consiste em “produzi-la” o mais próximo possível da
carga através do uso de capacitores. Instalando-se capacitores junto às cargas indutivas,
a circulação de energia reativa fica limitada a estes equipamentos. Na prática a energia
reativa passa a ser fornecida pelos capacitores, liberando parte da capacidade do sistema
elétrico e das instalações das unidades consumidoras. Assim é comumente conhecida
“compensação de energia reativa”.
2.5 Capacitor
Os formatos típicos consistem em dois eletrodos ou placas que armazenam
cargas opostas. Estas duas placas são condutoras e são separadas por um isolante ou por
um dielétrico. A carga é armazenada na superfície das placas, no limite com o
dielétrico. Devido ao fato de cada placa armazenar cargas iguais, porém opostas, a carga
19
total no dispositivo é sempre zero. A Figura 2.2 ilustra o modelo básico e o símbolo de
um capacitor.
Figura 2.2 – Capacitor.
FONTE: DORNELLAS, 1996.
2.6 Configurações típicas dos capacitores
No que diz respeito às configurações dos capacitores, para
compensação de energia reativa, elas podem ser dispostas da seguinte forma:
2.6.1 Banco fixo
Os capacitores são instalados junto às cargas, ligados diretamente nos
barramentos. A injeção de energia reativa é fixa, independe da carga e tem como
principais características: baixo custo, impossibilidade de controle e, possibilidade de
sobretensões, devido à sobrecompensações em período de baixa carga, e de pagamento
de tarifação de energia reativa, no período da madrugada (reativo capacitivo).
20
2.6.2 Banco semi-automático
Os capacitores são inseridos no sistema simultaneamente à carga,
podendo ser ligados e alimentados no mesmo dispositivo de manobra desta. Esta
configuração possui como características principais:
•
Aumento do investimento inicial, pela necessidade de associar cada carga a um
respectivo capacitor. Quanto maior a diversidade operacional das cargas, mais
capacitores serão necessários ao sistema;
•
Nem sempre o dispositivo de manobra da carga permite fisicamente a ligação
dos capacitores, sendo às vezes necessário dotá-los de dispositivo de manobra
independente, comandado pelo dispositivo de operação da carga (alimentação da
bobina do contator do capacitor por contato auxiliar do contator ou sinal de
operação), aumentando assim os custos;
•
Probabilidade de problemas operacionais e defeitos, em razão de ligamentos
consecutivos ou “repiques de contatores” sem que os capacitores tenham sido
descarregados;
•
Queima de dispositivos de acionamento estático a semicondutores na manobra
dos capacitores (e.g. inversores de freqüência e soft starters)
2.6.3 Banco automático
O sistema foi concebido para atender a cargas variáveis, e pode ser
entendido como uma evolução das outras configurações. Os capacitores são montados
em bancos centralizados, manobrados em grupos por contatores distintos. O controle da
manobra é feito por um dispositivo eletrônico dedicado, que recebe informações da
corrente da carga através de transformador de corrente instalado na entrada do quadro
geral. Com esta informação e com o ajuste do fator de potência desejado, o controlador
manobra os capacitores conforme lógica programável e interface com o usuário. Apesar
de ser uma solução bastante empregada, a aplicação deste sistema em cargas com perfil
sem muita variação pode apresentar alguns problemas operacionais:
21
•
inserção de transitórios na rede quando da entrada dos capacitores em razão do
in rush (período de energização) destes. Nota-se a influência da partida dos
capacitores na qualidade da tensão de fornecimento;
•
Efeito de flicker e sobretensão devido a sobrecompensação de reativo, pois a
resposta do sistema é lenta e os capacitores podem levar dezenas de segundos
até serem desativados, após o desligamento da carga. Neste período, a
sobrecompensação pode comprometer as outras cargas em operação;
•
Defeitos em razão de ligamentos consecutivos ou “repiques de contatores” sem
que os capacitores tenham sido descarregados;
•
Queima de dispositivos de acionamento estático a semicondutores, quando da
manobra dos capacitores (e.g. inversores de freqüência e soft starters).
2.7 Os Algoritmos Genéticos
Os Algoritmos Genéticos (AG) são sistemas adaptativos que imitam alguns
mecanismos observados na evolução natural das espécies. Os primeiros passos neste
campo foram dados por John Holland no início dos anos 70, que acreditou ser possível
resolver alguns problemas através de processos de evolução semelhantes.
AG são algoritmos de busca e otimização global, baseados nos mecanismos
de seleção natural e da genética. Eles empregam uma estratégia de busca paralela e
estruturada, mas aleatória, que é voltada em direção ao reforço da busca de pontos de
"alta aptidão", ou seja, pontos nos quais a função a ser minimizada (ou maximizada)
tem valores relativamente baixos (ou altos). Apesar de usar componentes aleatórios, eles
não fazem caminhadas aleatórias não-direcionadas, pois exploram informações
históricas para encontrar novos pontos de busca onde são esperados melhores
desempenhos. Isto é feito através de processos iterativos, onde cada iteração é chamada
de geração.
Durante cada iteração, os princípios de seleção e reprodução são aplicados a
uma população de candidatos que pode variar, dependendo da complexidade do
problema e dos recursos computacionais disponíveis. Através da seleção, determinamse quais indivíduos conseguirão se reproduzir, gerando um número determinado de
22
descendentes para a próxima geração, com uma probabilidade determinada pelo seu
índice de aptidão. Em outras palavras, os indivíduos com maior adaptação relativa têm
maiores chances de se reproduzir.
A Figura 2.3 ilustra um problema de maximização de difícil solução.
Algoritmos de exclusão de semi-espaços (utilizam sub-gradientes para definir um plano
que divide o espaço em dois semi-espaços, sendo que a função decresce em apenas um
desses dois semi-espaços) teriam pequenas chances de convergir para este problema já
que dependem da convexidade dos funcionais de otimização e a multimodalidade é um
caso particular de não convexidade. Já os algoritmos de direção de busca só
convergiriam ao ótimo global caso partissem de algum ponto da bacia de atração do
mesmo, o que é improvável dado o tamanho reduzido da mesma. O funcionamento dos
algoritmos estocásticos dá aos mesmos maior possibilidade de alcançar o ótimo global
deste tipo de problema, tornando a escolha dos mesmos indicada apesar de seu custo
computacional mais elevado [15].
Figura 2.3 – Função multimodal de difícil maximização.
FONTE:LACERDA, 2004.
23
2.8 Codificação dos indivíduos
Os indivíduos são compostos por palavras genéticas (genótipo) sendo que
cada grupo de caracteres que compõem essa palavra representa uma das variáveis de
otimização (cromossomo). O fenótipo é a tradução dessa palavra para valores reais.
Os AG foram inicialmente concebidos seguindo uma analogia forte com a
representação cromossômica dos indivíduos. Com isso, uma representação trivial dos
mesmos seria uma estrutura binária, onde cada bit representaria um gene, cada conjunto
de genes representaria um cromossomo e o conjunto de cromossomos representaria um
indivíduo.
A
Figura
2.4
apresenta
um
exemplo
em
que
foi
adotada
codificação
binária
Figura 2.4 - Exemplo de codificação binária de um indivíduo.
FONTE: CARRANO, 2004.
Outras codificações também podem ser utilizadas, conforme o tipo de
problema.
Abaixo são mostrados os tipos de codificações mais usados além da codificação binária:
1. Real: creal = [3.45 2.81 − 9.07],
2. Inteira: cint = [3 2 1 4 5 6 8 7 3];
3. Caracteres: ccar = [A C E B E];
4. Regras: creg = [R1 R2 · · · Rn];
24
2.8.1 O uso de codificação real
Em algumas situações, as codificações baseadas em strings binários não
possuem um desempenho aceitável, motivo que levou vários pesquisadores a buscar
novas formas de representar o alfabeto de cromossomos. Embora existam argumentos
favoráveis à utilização da codificação binária, como a maximização do paralelismo
implícito (a capacidade dos AG processarem schematas ao invés de cromossomos
individuais), eles não apresentam desempenho satisfatório em espaços de busca
contínuos. Também, devido à redundância, a decodificação pode não pertencer ao
domínio do parâmetro original.
Uma alternativa para espaços de busca contínuos é a codificação real, que
abre a possibilidade de se trabalhar com grandes domínios para as variáveis (genes).
Esta alternativa apresenta soluções muito próximas da formulação natural dos
problemas e evita processos de codificação/decodificação, o que conduz ao aumento da
velocidade dos AG (HERRERA, 1996).
Em um alfabeto real, um cromossomo é um vetor, onde seus elementos são
números de ponto flutuante, sendo o próprio cromossomo uma solução do problema.
Além do mais, os valores dos genes dos cromossomos são mantidos dentro de um
intervalo estabelecido pelas variáveis que eles representam. Tal requerimento deve ser
observado pelos operadores genéticos. A literatura apresenta vários modelos que
satisfazem às restrições anteriores.
Como argumentos em favor da codificação real, HERRERA (1996) cita:
1. A possibilidade de trabalhar com grandes domínios para as variáveis, o que é difícil
atingir em implementações binárias, onde o aumento do domínio pode significar
sacrifício da precisão;
2. A capacidade de explorar a “gradualidade” das funções com variáveis contínuas. O
conceito de gradualidade refere-se ao fato de que pequenas alterações nas variáveis
correspondem a pequenas mudanças nas funções;
3. A capacidade de ajuste local das soluções, como conseqüência do item anterior;
25
4. A representação das soluções é muito próxima da formulação natural de muitos
problemas, ou seja, não há diferenças entre o genótipo (codificação) e o fenótipo
(espaço de busca);
5.
Os processos de codificação/decodificação, necessários nos alfabetos binários, são
evitados, aumentando a velocidade dos AG.
2.9 População inicial
Na abordagem clássica dos algoritmos genéticos a população inicial é gerada
de forma aleatória. Porém, outras lógicas podem ser aplicadas. Pode-se, por exemplo,
gerar uma população inicial determinística (gerando um “grid” do espaço de
parâmetros) visando garantir um espalhamento dessa população em todo o espaço de
parâmetro. Uma outra forma menos drástica de garantir essa diversidade e que apresenta
resultados positivos é a divisão do espaço de parâmetros em subconjuntos (Figura 2.5).
Caso o número de indivíduos em um destes subconjuntos seja menor que um valor
estipulado desloca-se um indivíduo do subconjunto mais populoso para o mesmo. O
tamanho da população pode afetar o desempenho global e a eficiência dos algoritmos
genéticos. Populações muito pequenas têm grandes chances de perder a diversidade
necessária para convergir a uma boa solução, pois fornecem uma pequena cobertura do
espaço de busca do problema. Entretanto, se a população tiver muitos indivíduos, o
algoritmo poderá perder grande parte de sua eficiência pela demora em avaliar a função
de aptidão de todo o conjunto a cada iteração, alem de ser necessário trabalhar com
maiores recursos computacionais.
Em alguns problemas não se pode gerar uma população puramente aleatória,
já que isso criaria uma população composta, quase em sua totalidade por soluções
infactíveis. Problemas combinatórios (problemas de redes) têm essa característica.
Nesses casos é necessário procurar heurísticas que gerem redes viáveis para composição
da população inicial [17].
26
Figura 2.5 - Segmentação de um espaço de parâmetros de 3 variáveis.
FONTE: CARRANO, 2004.
2.10 Avaliação dos indivíduos
A avaliação estabelece um elo entre o algoritmo genético e o mundo
externo. A mesma deve ser feita através de uma função que melhor representa o
problema (a função objetivo, por exemplo, é uma escolha muito comum) e tem por
objetivo fornecer uma medida de adequação de cada indivíduo da população ao seu
habitat. Comparando mais uma vez com a teoria Darwiniana, a função de avaliação
(fitness function) está para um algoritmo genético assim como o meio ambiente está
para seres vivos. Estas funções de avaliação são específicas de cada problema.
2.11 Restrições
Apesar dos operadores de cruzamento e mutação garantirem que os
indivíduos gerados estejam dentro de certo domínio não se pode garantir que estes
objetivos obedeçam a uma determinada restrição g(x). Existem quatro formas básicas de
tratamento de restrições em AG:
- Função Penalidade (Penalty Function);
- Eliminação de Soluções;
- Reparo das Soluções;
- Decodificadores de Cromossomos.
27
2.11.1 Função Penalidade
As potenciais soluções são geradas sem considerar as restrições. A fitness
das soluções que violarem as restrições acrescenta-se uma parcela de penalização.
• Se o problema é de maximização essa parcela tem valor negativo;
• Se o problema é de minimização essa parcela tem valor positivo.
Várias funções podem ser utilizadas para penalização.
As mais usuais são:
- Função logarítmica;
- Função linear;
- Função quadrática.
2.11.2 Eliminação de Soluções
As soluções que violarem as restrições são eliminadas fitness = 0.
• Geram-se novas soluções para completar a população;
• Parte dos novos indivíduos pode ser descartada por baixo desempenho.
Esta técnica deve ser utilizada em problemas onde a probabilidade de
geração
de soluções que violem as restrições seja pequena.
2.11.3 Reparo da Solução
As soluções que violem as restrições são corrigidas por um algoritmo de
reparo de soluções específico. Algoritmos de reparo de soluções podem acarretar em um
demasiado custo computacional, fazendo com que a aplicação desta técnica também
dependa da probabilidade de se gerar soluções que violem as restrições.
2.11.4 Decodificadores de Cromossomos
É utilizado um mapeador da representação que garante a transformação de
um cromossomo em uma solução válida. Estes decodificadores podem ser operadores
genéticos desenvolvidos especificamente para o problema. Os decodificadores de
cromossomos podem ser complexos e acarretar em um alto custo computacional.
Quando utilizado de forma adequada esta técnica oferece um bom desempenho ao AG.
28
2.12 Métodos de Seleção de Indivíduos
Os métodos de seleção em AG têm a função de determinar quais indivíduos
irão sobreviver e então sofrer cruzamento e mutação. A seleção é baseada na fitness dos
indivíduos: indivíduos mais aptos têm maior probabilidade de serem escolhidos para
reprodução.
Assim, seja fi a avaliação do indivíduo i na população, a probabilidade pi de
sobrevivência do indivíduo é dada por:
pi =
fi
N
∑ j = 1 fi
(2.3)
Existem vários métodos de se fazer a seleção em AG, sendo que os três mais
conhecidos são:
- Roleta estocástica;
- Torneio estocástico;
- Elitismo.
2.12.1 Roleta Estocástica
É o método mais conhecido de seleção em algoritmos genéticos. Foi
proposto por GOLDBERG (1989). A cada elemento da população é determinado um
espaço na roleta, proporcional a sua probabilidade de sobrevivência. Indivíduos com
maior fitness ocupam uma maior área na roleta, e tem, portanto, maior chance de serem
escolhidos. A cada vez que a roleta é girada é escolhido um novo indivíduo para a
população. O processo se repete até que a população esteja completa. Um exemplo
ilustrativo desta técnica é mostrado na Figura 2.6, onde podemos notar que o indivíduo
1 por possui a maior fitness ocupa a maior “fatia” da roleta e consequentemente da
maior probabilidade de ser escolhida quando a roleta for girada.
29
Figura 2 6 - Exemplo ilustrativo de uma Roleta Estocástica
FONTE: CARRANO, 2004.
2.12.2 Torneio Estocástico
Neste método, utilizam-se sucessivas disputas para realizar a seleção
de indivíduos. Para selecionar k indivíduos, realizam-se k disputas, cada disputa
envolvendo n indivíduos escolhidos ao acaso. O indivíduo de maior aptidão na
disputa é selecionado para a população intermediária. O processo repete-se até
preencher a população intermediária. Geralmente é utilizado n = 3.
2.12.3 Elitismo
O elitismo é um método presente em quase todas as implementações
de AG. Ele garante que o melhor indivíduo encontrado esteja presente antes da seleção
na geração atual. O Elitismo foi proposto por DE JONG (1975), um dos trabalhos pioneiros
sobre AG. A Figura 2.7 mostra o desempenho do melhor cromossomo em cada geração,
usando o AG com e sem Elitismo, com os valores plotados no gráfico representando a
média de n execuções do AG em um problema de maximização. Claramente mostrado
que, neste problema, o AG com elitismo encontra a solução de forma mais rápida do
30
que o AG sem elitismos (vale ressaltar que, em algumas execuções, o AG
ocasionalmente encontra mínimos (ou máximos) locais, tornando a média dos melhores
cromossomos menor que o mínimo (ou máximo) da função) [6].
Figura 2.7 – Desempenho do AG com Elitismo em um problema de maximização.
FONTE: LACERDA, 2004.
2.13 Operadores Genéticos
2.13.1 Recombinação ou Crossover
O operador de crossover ou recombinação é baseado na reprodução
sexuada dos seres vivos e cria novos indivíduos por intermédio da combinação de dois
ou mais indivíduos. A idéia intuitiva por trás do operador de crossover é a troca de
informação entre diferentes soluções candidatas. No algoritmo genético clássico, é
atribuída uma probabilidade de crossover fixa aos indivíduos da população. É o
operador principal.
O operador de crossover mais comumente empregado é o crossover de um
ponto, existindo também o crossover multi-pontos e o crossover uniforme (também
conhecido como máscara). Resumidamente o crossover de um ponto baseia-se na
escolha (de forma aleatória) de um ponto de corte nos cromossomos-pai, onde um filho
herdará de um dos pais a porção à esquerda do ponto de corte e do outro pai, a porção à
direita. No caso, o outro filho herdará dos pais as porções contrárias às herdadas pelo
primeiro filho gerado.
31
O crossover multi-pontos é semelhante ao crossover de um ponto, com a
diferença de que são escolhidas mais de um ponto de corte. Já o crossover uniforme
utiliza um cromosso-padrão (palavra de referência) para gerar os filhos. Onde um gene
igual a 1 na palavra de referência implica na troca de valor do gene no mesmo alelo do
cromossomo-pai. Quando o valor for 0 o valor do gene não se altera.
As Figuras 2.8, 2.9 e 2.10, ilustram cada um dos tipos de crossover (em
codificação binária) citados:
Figura 2.8 - Crossover de 1 ponto.
FONTE: CARRANO, 2004.
Figura 2.9 - Crossover Multi-pontos.
FONTE: CARRANO, 2004.
32
Figura 2.10 - Crossover Uniforme.
FONTE: CARRANO, 2004.
2.13.2 Mutação
O operador de mutação modifica aleatoriamente um ou mais genes de um
cromossomo. A probabilidade de ocorrência de mutação em um gene é denominada
taxa de mutação. Usualmente, são atribuídos valores pequenos para a taxa de mutação.
A idéia intuitiva por trás desse operador é a criação de variabilidade extra na população,
mas sem destruir o progresso já obtido no decorrer do processo evolutivo, ou seja, a
variabilidade deve se comportar como uma perturbação de efeito localizado. O operador
de mutação elimina o problema do mínimo (ou máximo, dependendo do problema)
local.
Considerando codificação binária, o operador de mutação padrão
simplesmente troca o valor do gene selecionado Assim, se um gene selecionado para
mutação tiver valor 1, passará para 0 após a aplicação do operador e vice-versa.
(HOLLAND, 1992). A figura 2.11 mostra o exemplo de uma mutação com código binário
de representação de indivíduos.
33
Figura 2.11 – Mutação.
FONTE: CARRANO, 2004.
2.14 Convergência do AG
Na prática, o critério mais utilizado para determinar a convergência de um
algoritmo genético é o número de gerações, já que os critérios utilizados em algoritmos
determinísticos não se aplicam a este tipo de algoritmo. Porém outros critérios podem
ser pensados, como:
• Estabilização da fitness média da população durante gerações;
• Estabilização da fitness do melhor indivíduo durante m gerações;
• Perda de diversidade da população;
• Alcance do ótimo desejado caso o mesmo seja conhecido (validação de algoritmo).
A utilização dos três primeiros métodos citados acima é de suma
importância, uma vez que as fragilidades nos algoritmos genéticos podem fazer com
que as mesmas ocorram sem o alcance de um resultado realmente ótimo.
2.15 Técnicas para manter a diversidade populacional em algoritmos genéticos
Um dos grandes problemas em algoritmos genéticos é o problema de
convergência prematura, onde alguns indivíduos relativamente bem adaptados tendem a
dominar a população, mesmo sendo não ótimos, fazendo que o algoritmo convirja a um
ótimo local. Para tentar escapar deste problema algumas técnicas podem ser utilizadas
em conjunto com Algoritmos Genéticos, aqui são apresentadas duas técnicas de
importante relevância:
34
• Compartilhamento de Recursos (Sharing);
• Evolução Cooperativa.
2.15.1 Compartilhamento de Recursos
Esta técnica explora o que na natureza é conhecido como nicho, que estão
dentro do ambiente e suportam diferentes tipos de vidas (espécies ou organismos). O
número de organismos contidos no nicho é determinado pela fertilidade do nicho e pela
eficiência de cada organismo na exploração dessa fertilidade. CAVICCHIO (1970) foi o
autor de uma das primeiras propostas de introdução de nicho em algoritmos genéticos.
O mecanismo proposto por ele é chamado de pré-seleção (preselection), e determina
que um descendente substituirá o indivíduo pai se o valor de fitness dele for maior que o
do pai. Segundo o mesmo, este procedimento tende a manter diversidade da população,
pois indivíduos tendem a substituir indivíduos similares a eles mesmos.
DE JONG (1975) propôs outro mecanismo, denominado pelo mesmo de
crowding. Neste esquema, a substituição de indivíduos na população é modificada para
fazer com que novos indivíduos substituam outros similares com menor valor para a
função de fitness dentro da população Já GOLDBERG & RICHARDSON (1987)
propuseram outro mecanismo de compartilhamento de recursos, conhecido como
sharing. Esta ferramenta propõe a redução do valor de fitness de indivíduos que têm
membros altamente similares dentro da população. Um esquema prático que
diretamente usa compartilhamento para induzir nicho e espécie é mostrada na figura
2.12. Neste esquema, uma função sharing é definida para determinar a vizinhança e o
grau de compartilhamento para cada indivíduo da população O resultado deste
mecanismo é a limitação do crescimento descontrolado de espécies particulares dentro
de uma população.
35
Figura 2.12 – Função Sharing Linear
FONTE: CARRANO, 2004.
2.15.2 Evolução Cooperativa
Outra abordagem que lida com problemas complexos é a evolução
cooperativa, proposta por POTTER (1997) e DE JONG (1975). Essa arquitetura modela
um ecossistema consistindo de duas ou mais espécies. Nessa técnica, isolam-se as
espécies geneticamente, ou seja, só há cruzamento entre espécies. Restrições de
cruzamento são forçadas simplesmente por evoluir as espécies em populações
separadas. As espécies interagem entre si dentro de um modelo de domínio
compartilhado e têm um relacionamento cooperativo. Para avaliar uma população são
formadas colaborações com representantes de cada espécie. Há muitos métodos
possíveis para escolher os representantes com os quais colaborar. Em alguns casos é
apropriado permitir que o melhor indivíduo corrente de cada população seja o
representante. Os indivíduos não são avaliados isoladamente, eles são combinados
primeiro em algum domínio dependente com um representante de cada uma das outras
espécies. POTTER (1997) se refere a isto como uma colaboração porque os indivíduos
serão julgados no final em quão bem eles trabalham juntos para resolver o problema
objetivo. Se a evolução estagnar, pode ser que existam poucas espécies no ecossistema
com o qual se deseja construir uma boa solução, então uma nova espécie será criada e
sua população aleatoriamente inicializada. A estagnação pode ser descoberta
monitorando a qualidade das colaborações. No algoritmo, a cada geração é feita uma
36
cooperação entre as populações, onde é atribuído um valor de aptidão para a população
que está sendo avaliada. A cada n gerações, se a população que está sendo avaliada
possui um valor de aptidão muito baixo, essa população é descartada, e então se cria
uma nova população, a qual irá substituí-la nas próximas gerações.
2.16 O Algoritmo Genético Simples (AGS)
Em grande parte da bibliografia o algoritmo proposto para algoritmos
genéticos é AGS (do inglês, Simple Genetic Algorithm.) O AGS utiliza codificação
binária, crossover de um ponto de corte, população e probabilidade de crossover e
mutação fixas além de não usar rankeamento. Porém esta estrutura básica pode ser
utilizada na implementação de qualquer algoritmo genético, podendo-se acrescentar
outras codificações e ferramentas.
O algoritmo AGS segue abaixo:
Gera população inicial;
Avalia a população inicial;
conv Å false;
Faça Enquanto conv = false
Seleciona a população usando a roleta estocástica;
Faz crossover
Faz mutação;
Avalia a população;
Encontra o melhor indivíduo;
Testa critério de convergência;
Se convergiu
conv Å true;
Caso contrário
conv Å false;
Fim Se
Fim Faça
Apresenta o melhor resultado encontrado
37
III
METODOLOGIA
Este capítulo tem como objetivo, apresentar a implementação do modelo
computacional proposto. A metaheurística escolhida para a implementação do modelo
foi a dos algoritmos genéticos. A escolha dessa metaheurística é justificada quando
analisamos a natureza do problema (uma vez que métodos determinísticos apresentam
resultados pouco satisfatórios) e também a robustez dos algoritmos genéticos.
3.1 Definição do problema
O Problema de Alocação de Capacitores (PAC) a ser resolvido consiste em,
a partir de um conjunto de locais candidatos ao recebimento de capacitores fazer com
que o algoritmo genético possa encontrar a melhor configuração para essa alocação,
onde uma solução ótima em potencial é avaliada a partir do fluxo de carga calculado
para cada configuração.
3.1.1 Formulação básica para o problema de fluxo de carga
O objetivo básico do Programa de Fluxo de Carga (PFC) consiste em
determinar os módulos e ângulos das tensões das barras do sistema. Depois de
calculadas as magnitudes das tensões nodais Vk e os ângulos θ k de todas as barras k do
sistema, pode-se calcular qualquer outra variável de interesse como, por exemplo, a
potência ativa e reativa de qualquer barra, os fluxos de potências nas linhas de
transmissão e transformadores, as perdas ativas totais na transmissão, etc. Para calcular
os valores de θ k e Vk de todas as barras k do sistema, utiliza-se um procedimento
iterativo, onde as diferenças entre as potências ativa e reativa especificadas e calculadas
para a k-ésima barra devem ser reduzidas a valores inferiores aos erros especificados.
Para isto, monta-se um sistema de equações algébricas não-lineares, definido através
das expressões:
38
ΔPk = Pkesp − Pk (Vk , θ k ) ≅ 0
para as barras do tipo PQ e PV
ΔQk = Qkesp − Qk (Vk , θ k ) ≅ 0
para as barras do tipo PQ
(3.1)
Onde Pkesp e Qkesp são respectivamente as potências líquidas ativa e reativa especificadas
para a k-ésima barra sob consideração; Pk e Qk são respectivamente as potências
líquidas ativa e reativa calculadas para a k-ésima barra sob consideração. As barras do
tipo PQ são aquelas associadas às barras de carga do sistema. As barras do tipo PV são
utilizadas para representar as barras de geração ou barras de tensão controlada, onde
estão ligados condensadores e compensadores síncronos ou estáticos. A barra Vθ,
também denominada como barra de referência (swing bus ou slack bus) ou de balanço,
fornece a referência angular do sistema e serve para fechar o balanço de potências ativa
e reativa ao final do processo de resolução do fluxo. Neste trabalho foram consideradas
apenas a barras do tipo PQ, PV e Vθ, esquematizadas na Tabela 3.1.
Tabela 3.1 – Tipos de Barras do sistema
Tipo
Dados
Incógnitas
PQ
Pk e Qk
Vk e θ k
PV
Pk e Vk
Qk e θ k
Vθ
Vk e θ k
Pk e Qk
Após a resolução do sistema de equações obtido com a aplicação da equação (3.1) às
barras do sistema, têm-se os valores das magnitudes de tensão Vk e dos ângulos θ k para
todas as barras. As barras PQ passam a ter todos os valores Pk , Qk Vk e θ k conhecidos.
Para as barras PV fica faltando Qk e para a barra Vθ fica faltando Pk e Qk . Esses valores
desconhecidos são calculados através da aplicação direta das equações de potências
ativa e reativa em uma barra k definidas matematicamente como:
39
Pk = Vk
Q k = Vk
∑V
(G km cosθ km + Bkmsenθ km )
∑V
(G kmsenθ km − Bkm cosθ km )
m∈Ω L
m∈Ω L
m
m
(3.2)
Onde Ω L é o conjunto que representa todas as barras ligadas à barra k
incluindo a própria barra k; Vm representa o módulo da tensão na barra m; θ km
representa o ângulo da tensão entre a barra k e a barra m, definido pela expressão
θ km = θ k - θ m ; G km e Bkm são os elementos da matriz admitância das barras, definida
pela expressão Ykm = G km + j Bkm A matriz admitância das barras é uma matriz esparsa
que tem suas linhas e colunas associadas às barras do sistema, como por exemplo:
•
Y33 representa o elemento que corresponde à barra 3.
•
Y23 representa o elemento que corresponde à ligação da barra 2 com a barra 3.
Sempre que entre os nós k e m não existirem linhas ou transformadores tem-se Ykm = 0.
Os elementos da matriz admitância das barras são definidos matematicamente da
seguinte forma:
Ykk = jb shkm +
∑ (a
m∈Ω k
Ykm = a km y km
2
km
y km jb shkm )
(3.3)
Onde Ω k é o conjunto que representa todas as barras ligadas à barra k; b shk
é a susceptância shunt ligada à barra k; y km é a admitância série existente entre a barra k
e a barra m; a km representa o Tap do transformador existente entre a barra k e a barra m;
e b shkm é a susceptância shunt existente entre a barra k e a barra m. Note que, se o
elemento existente entre as barras k e m for uma linha de transmissão tem-se a km = 1 e
se for um transformador tem-se b shkm = 0. A admitância série y km existente entre a barra k
e a barra m é definida como:
40
rkm
xkm
ykm = gkm + jbkm = 2
−
j
2 +x2
rkm+x2km
rkm
km
Onde g
km
e b
km
(3.4)
são respectivamente a condutância série e a susceptância série
existentes entre a barra k e a barra m; r 2 + x 2 são respectivamente a resistência
km
km
série e a reatância série existentes entre a barra k e a barra m. As perdas de potências
ativa e reativa entre as barras k e m podem ser calculadas, respectivamente, por:
Ploss = Pkm + Pmk
Q loss = Q km + Q mk
(3.5)
Onde Pkm , Qkm , Pmk e Qmk são respectivamente os fluxos de potências ativa e reativa da
barra k para a barra m e da barra m para a barra k, definidos matematicamente como:
Pkm = (a km Vk ) 2 g km − (a km Vm )Vm g km cosθ km − (a km Vk )Vm b kmsenθ km
Q km = − Vk2 (a 2km b km + b shkm ) + (a km Vk )Vm b km cosθ km − (a km Vk )Vm g km senθ km
(3.6)
2
Pmk = Vm g km − (a km Vk )Vm g km cosθ km + (a km Vk )Vm b km senθ km
2
Q mk = − Vm (b km + b shkm ) + (a km Vk )Vm b km cosθ km + (a km Vk )Vm g km senθ km
(3.7)
Sendo que, para linhas de transmissão tem-se a km = 1 e para transformadores em fase
tem-se b shkm = 0.
3.1.2 Um exemplo de cálculo de fluxo de carga
Sabe-se que o fluxo de carga (do inglês load flow) ou fluxo de potência (do
inglês power flow) consiste na obtenção das condições de operação (magnitude e ângulo
de fase dos fasores tensão nodal, a partir dos quais podem ser determinados os fluxo de
potência ativa e reativa) em regime permanente de uma rede de energia elétrica com
topologia e níveis de geração e consumos conhecidos. A seguir é mostrado um exemplo
de resolução de fluxo de carga para 3 barras.
41
Figura 3.1 – Três barras utilizadas para o exemplo de cálculo de fluxo de carga
FONTE: CASTRO, 2005.
Onde a barra 1 é a barra slack e as barras 2 e 3 são barras de carga. As tensões e ângulos
das barras e as impedâncias nas linhas são:
Após serem feito os cálculos temos:
Figura 3.2 – Resolução do exemplo de fluxo de carga
FONTE: CASTRO, 2005.
Onde:
42
3.1.3 Resolução do Fluxo de Carga para o IEEE 14 Node Test Feeder
O método utilizado para a resolução do Problema de Fluxo de Carga, dado
pelo sistemas de equações (3.1), foi o método de Newton-Raphson. Este método foi
implementado em uma rotina do MATLAB®, dentro do toolbox chamado
MATPOWER.
3.2 Base de dados
É importante salientar que os dados de toda a rede de distribuição elétrica
analisada neste trabalho, foram obtidos através do IEEE 14 Node Test Feeder, que
simula uma rede elétrica real e está disponível em:
https://www.ee.washington.edu/research/pstca/pf14/pg_tca14bus.htm
Encontra-se no formato cdf, o qual o toolbox MATPOWER converte para um formato
próprio para que assim seja calculado o fluxo de carga. A figura 3.3 mostra a topologia
do IEEE 14 Node Test Feeder.
43
Figura 3.3 – Topologia do IEEE 14 Node Test Feeder.
FONTE: IBA, 1994.
3.3 Etapa de modelagem do problema
Nesta etapa são apresentadas todas as representações do problema proposto,
para que assim o algoritmo genético possa ser empregado de maneira efetiva.
Esta etapa é composta por:
•
Representação da solução
•
Definição da Função de Avaliação utilizada
•
Definição da Função de Seleção Utilizada
•
Definição dos Operadores Genéticos utilizados
44
3.3.1 A Representação da solução
A representação escolhida para a solução ou cromossomo na linguagem dos
Algoritmos Genéticos, foi a codificação real (ponto flutuante).
Segundo ROMÃO (1996), uma alternativa para os espaços de busca
contínuos é a codificação real, que abre a possibilidade de se trabalhar com grandes
domínios para as variáveis (genes). Esta alternativa apresenta soluções muito próximas
da formulação natural dos problemas e evita processos de codificação/decodificação, o
que conduz ao aumento da velocidade dos AG (HERRERA, 1996).
A solução para o problema de alocação de capacitores, devido aos
parâmetros utilizados para a mesma (custo dos capacitores e perdas ativas da rede),
encontra-se no domínio de espaço contínuo. Assim, fica justificada a escolha da
codificação real para a representação da solução.
3.3.2 Definição da Função de Avaliação Utilizada
A função de avaliação utilizada nesta monografia baseia-se nos valores das
perdas ativas da rede de distribuição elétrica analisada. Quando escolhida uma
determinada configuração para se alocar os capacitores na rede, é então calculado para
essa configuração um fluxo de carga. A partir do fluxo de carga calculado, analisam-se
as perdas ativas geradas pela alocação dos capacitores. Dessa forma, as configurações
que geram as menores perdas ativas têm maior probabilidade de sobreviverem e se
reproduzirem dentro do processo dos AG.
3.3.3 Definição da Função de Seleção
A função de seleção utilizada foi a chamado “Roleta Estocástica”. Ela
baseia-se no cálculo acumulativo das probabilidades de sobrevivência. Como a
função de avaliação utilizada tem como parâmetro as perdas ativas geradas, as
probabilidades de sobrevivência são calculadas a partir dos valores dessas perdas
ativas.
Após ser feito esse cálculo, um número aleatório é então gerado e é
verificado se esse número está entre algum intervalo das probabilidades
acumulativas de sobrevivência (utilizando as perdas ativas), caso esteja é escolhido
45
o indivíduo que possui a probabilidade superior do intervalo em que se encontra o
número aleatório.
3.3.4 Definição dos Operadores Genéticos utilizados
Como a representação da solução neste modelo é codificada como ponto
flutuante, é necessário definir os operadores genéticos apropriados para manipular essa
representação. Os operadores genéticos considerados nesta implementação são apenas o
operador de crossover e o operador de mutação.
O operador crossover utilizado nesta monografia foi o crossover simples de
um ponto (MICHALEWICZ, 1994), que trata de uma variação do crossover
convencional de 1 ponto adaptado para representação real.
O operador de mutação foi a mutação uniforme que consiste n a simples
_
substituição de um gene por um número aleatório. Ou seja, dado um cromossomo p com
o j-ésimo gene selecionado para mutação é produzido um cromossomo c da seguinte
forma:
⎧U (ai , bi )
ci = ⎨
⎩ pi
(3.8)
Onde ci = U (ai , bi ) , se i = j e ci = pi , caso contrário .
3.4 Validação do Modelo Computacional
3.4.1 Linguagem de programação proposta
A linguagem de programação escolhida para implementar o modelo
computacional foi a Matlab. Dentre os principais motivos para essa escolha está a
questão possibilidade de integração com o toolbox MATPOWER utilizado para o
cálculo do fluxo de carga, que é um parâmetro essencial para a solução do problema.
Outro motivo interessante que motiva a escolha dessa linguagem de
programação é a agradável interface com o usuário e a possibilidade de saídas gráficas
muito interessantes.
46
3.4.2 Características do AG proposto
Quando falamos das características do algoritmo genético, trata-se da
percentagem de crossover e mutação, o número de gerações e o tamanho da população.
Para o AG proposto neste trabalho, foram conseguidos resultados satisfatórios com as
características apresentadas na Tabela 3.2:
Tabela 3.2 – Características do AG proposto
Característica
Valor
Tamanho da população
12
Taxa de mutação
0.2
Taxa de Crossover
0.8
Gerações
100
Outro importante atributo funcional que caracteriza o AG proposto é a sua
inicialização randômica. A inicialização compreende a etapa de geração de uma solução
inicial. Em muitos casos os AG inicializados com soluções iniciais integralmente
aleatórias podem conduzir a resultados insatisfatórios. Uma alternativa a este tipo de
abordagem é a inicialização de soluções geradas a partir de uma heurística mais limitada
como a descida de encosta. Neste trabalho usa-se a inicialização de soluções aleatórias,
porém definidas dentro de um intervalo de busca baseado na menor e maior perda ativa
calculadas no fluxo de carga pelo MATPOWER. Dentro do intervalo proposto, a função
a ser minimizada tem o aspecto demonstrado na figura 3.4.
47
13
12
11
C(x,y) = Ac+La
10
9
8
7
6
5
4
3
0
2
4
6
X
8
10
12
Figura 3.4 – Gráfico da função a ser minimizada.
A equação da função a ser minimizada pelo AG é dada por:
C ( x , y ) = Ac + L a
(3.9)
Sujeita a : Fluxo de carga calculado
Número de capacitores alocados
Onde, C(x,y) é a função Custo Total, Ac é o custo da alocação dos capacitores e La é a
perda ativa gerada.
Para o teste do AG proposto, foram calculados fluxos de carga, onde se
utilizou a seguinte proposta:
•
Geração aleatória, no intervalo de 1 a 3, do número de capacitores;
•
Geração aleatória, no intervalo de 1 a 14, da barra que recebe os
capacitores.
48
Depois de calculados os fluxos de carga, utilizou-se então a menor e a maior perda ativa
gerada como limite inferior e limite superior, respectivamente, para a geração da
população inicial do AG. A Tabela 3.3 mostra as 12 perdas ativas geradas.
Tabela 3.3 - Dados das perdas ativas geradas
Fluxo de carga
calculado
1
N º de capacitores
alocados
2
Barra que recebeu
os capacitores
5
Perda ativa gerada
(em MW)
6.539
2
3
9
5.771
3
2
11
7.845
4
2
8
5.167
5
1
6
9.332
6
1
7
8.213
7
2
10
7.926
8
2
10
7.926
9
2
2
9.384
10
2
2
9.384
11
2
6
7.846
12
3
4
3.624
No que diz respeito aos dados dos capacitores, foram utilizados os dados
apresentados na Tabela 3.4.
Tabela 3.4 – Dados do tipo de capacitor utilizado
Tipo de bancos de
Capacitância (KVAR)
Custo por unidade (R$)
capacitores
Fixo
50
1070,60
Os dados sobre o capacitor utilizado na monografia podem ser obtidos em:

ww2.prefeitura.sp.gov.br/secretarias/servicos_e_obras/licitacoes/caderno_insumos.doc-
49
IV RESULTADOS OBTIDOS
Os resultados foram obtidos utilizando o MATLAB 7.04.365 (R14) Service
pack 2, sendo o programa executado em um computador INTEL CORE2DUO 1.8GHZ,
1GB de RAM, Sistema Operacional Windows XP Professional versão 2002 Service
pack 2.
Realizaram-se 8 simulações a fim de avaliar o modelo, onde como índice de
desempenho foi utilizado o próprio valor da função a ser minimizada. Quanto menor a
perda melhor é a solução para o problema de alocação de capacitores. A Tabela 3.5
apresenta os resultados obtidos.
Tabela 3.5 – Resultados obtidos com 8 simulações
Nº de
capacitores
Barra
6
Perda
Ativa
(MW)
3.6856
Geração
da
Solução
4
3
1
11
3.6382
81
2
11
3.7324
5
1
2
3.6754
48
3
12
3.6714
69
2
13
3.6826
4
2
12
3.6510
64
2
7
3.6249
48
Desvio = 0.012562
50
4.1 Discussão dos resultados obtidos
As perdas ativas geradas são baixas, onde algumas delas se aproximam
bastante da mínima global (menor valor de perda na Tabela 3.4). Isso significa que boas
soluções foram geradas pelo AG proposto.
Também foi constatado que para valores iniciais muito fora dos intervalos
definidos através dos fluxos de carga calculados, isto é, ampliando-se bastante o espaço
de busca do AG, ocorre uma grande dependência de boas soluções iniciais para que o
AG trabalhe de maneira satisfatória para o problema dado.
Foram disponibilizadas saídas gráficas para as simulações feitas no Matlab,
onde se pode constatar que o sistema se estabiliza bem, perto da perda ativa mínima
desejada. A figura 3.5 demonstra uma das simulações feitas.
Perdas ativas ao longo das gerações
12
Melhor
Média
11
10
Custo
9
8
7
6
5
4
3
0
10
20
30
40
50
60
Geração
70
80
90
Figura 3.5 – Saída gráfica para uma das simulações feitas.
100
51
Onde “Melhor” caracteriza a menor perda ativa obtida e “Média” a própria
média das perdas ativas.
Foi feita também uma análise de probabilidade empírica, onde foram
definidos valores alvo: fácil (3.7), médio (3.65) e difícil (3.62). Então foram feitas 100
execuções do algoritmo, interrompendo-se quando o valor alvo era encontrado. O tempo
que o algoritmo levava para alcançar o valor alvo foi gravado e ordenado de forma
crescente. De posse dos tempos, foi feita a associação de cada tempo t
probabilidade p = (i − 1 ) / 100 .
i
2
i
a uma
(3.10)
Assim, foi construído o gráfico t x p apresentado na figura 3.6.
i
i
Análise de Probabilidade Empírica
3
2.5
Tempo(s)
2
1.5
1
0.5
0
0
0.1
0.2
0.3
0.4
0.5
pi
0.6
0.7
0.8
0.9
1
Figura 3.6 – Análise de probabilidade empírica.
Pela figura podemos perceber, por exemplo, que em 3 segundos temos uma
probabilidade de praticamente 100% (1) de atingir o valor alvo fácil (no caso, o valor é
3.7).
52
V CONCLUSÃO E TRABALHOS FUTUROS
Este trabalho possibilitou a investigação do PAC utilizando como método
de solução uma metaheurística que foi a dos AG. Através dos resultados obtidos foi
constatado que o AG proposto mostrou-se eficaz na procura de boas soluções para o
PAC.
Constatou-se também neste trabalho que a representação de solução em
codificação de ponto flutuante (AG contínuo) facilitou muito a implementação do
modelo computacional e mostro-se adequada à procura de soluções para o PAC.
Através dos resultados obtidos podemos constatar que a abordagem do
problema via algoritmos genéticos mostrou-se eficaz, reduzindo as perdas ativas da rede
elétrica. Com a devida adaptação poderá ser uma valiosa ferramenta para equipes de
planejamento das companhias do setor elétrico.
Como sugestão para trabalhos futuros fica a de uma melhora da
inicialização do algoritmo genético, aplicando-se alguma heurística (GRASP, por
exemplo) a fim de conseguir boas soluções iniciais. Outro ponto que pode melhorar o
desempenho deste AG é adaptá-lo para que ele se torne um Algoritmo Memético, que se
trata de um algoritmo evolutivo em que uma busca local é parte decisiva na evolução.
Essa busca pode ser caracterizada como um refinamento local dentro do espaço de
busca. (MOSCATO&NORMAN, 1992)
O uso de outros tipos de capacitores (que não somente os de 50KVAr) e a presença de
diferentes tipos de banco de capacitores (semi-automáticos e automáticos) também
deverão ser investigados.
53
REFERÊNCIAS BIBLIOGRÁFICAS
[1] BARAN, M.; Wu, F.F. Optimal sizing of capacitors placed on a radial distribution
system. IEEE Transactions on Power Delivery, Vol. 4, No 1,pp. 735-743, January
(1989).
[2] CARPENTIER, J. M. - "Application of Newton’s Methods to Load Flow Problems",
Power Systems Computer Conference, London, 1963.
[3] CARRANO, Eduardo Gontijo " Algoritmos Genéticos - Fundamentação Teórica e
Aplicaçoes" , Unicamp, 2004.
[4]
CASTRO,
A.
Cálculo
de
Fluxo
de
Carga
,
2005
disponível
em
<http://www.dsee.fee.unicamp.br/%7Eccastro/cursos/it601/it601.html>
Acesso em 14 jul.2007
[5] CAVICCHIO JR, D.J. Adaptative search using simulated evolution. PhD Thesis,
University of Michigan, Ann Arbor, MI 1970.
[6] DAVIS, L. Handbook of genetic algorithms. Van Nostrand Reinhold, New York,
1991
[7] DE JONG, K.A. Analysis of the behavior of a class of genetic adaptative systems.
PhD thesis, University of Michigan, Ann Arbor, 1975.
[8] DORNELLAS, C. R. R; FALCÃO, D.M.; BOMFIM, A. L. B. - Otimização do
Despacho de Reativos Utilizando Algoritmos Genéticos, XI Congresso Brasileiro de
Automática - Anais vol 1, São Paulo, 02-06 Set (1996).
[9] GOLDBERG, D. E.; RICHARDSON, J. Genetic algorithms with sharing for
multimodal function optimization. In: International Conference on Genetic Algorithms,
2. Proceedings New Jersey: [S.n.], 1987. p.41-49.
54
[10] GOLDBERG, D. E. Genetic Algorithms in Search, Optimization and Machine
Learning, University of Alabama, Addison Wesley Publishing Company, 1989.
[11] HERRERA, F.; LOZANO, M.; VERDEGAY, J. L. Tackling real-coded genetic
algorithms: operators and tools for behavioural analysis. Artificial
Intelligence Review, v. 12, n. 4, p. 265-319, Ago. 1998.
[12] HOLLAND, J. H. Adaptation in Natural and Artificial Systems, Univ. of Michigan
Press., Ann Arbor, Michigan, 1975.
[13] IBA, Kenji - "Reactive Power Optimization by Genetic Algorithm", IEEE Trans.
on Power Systems, pp. 685-692, vol. 9, no. 02, May, 1994.
[14] LACERDA, Estéfane G. M. de "Algoritmos Genéticos e as outras técnicas de
otimização", UFRN, 2004
[15] MITCHELL, M. An Introduction to Genetic Algorithms , Massachusetts: MIT
Press,1 ed, 1998.
[16] MONTICELLI, A. J. - Fluxo de Carga em Redes de Energia Elétrica, Ed. Edgard
Blücher Ltda, São Paulo, 1983.
[17] MICHALEWICZ, Z. Genetic Algorithm s + Data Structures = Evolution
Programs. 3.ed. Springer - Verlag , 1994
[18] POTTER, M.A The design and analysis of a computational model of cooperative
coevolution. PhD thesis, George Mason University, 1997.
[19] ROMÃO, W. & COELHO, A. A. R. Controladores PID adaptativos: algoritmos e
simulações. Cadernos de METEP, Universidade Estadual de Maringá, 1996.
[20] SOARES, Gustavo Luis - "Algoritmo Genético: Estudo, Novas Técnicas e
Aplicações", Dissertação de Mestrado, UFMG, Belo Horizonte, 1997.
55
[21] ZIMMERMAN, R., G., D. MATPOWER: A MATLAB® Power System Simulation
Package, MATPOWER® homepage: http://www.pserc.cornell.edu/matpower/