1

Camilla Leimann PiresCarolina Prado

Ronaldo Funchal

Profª Drª Alzenira da Rosa Abaide

ESTUDO SOBRE ALGORITMOS GENÉTICOS COMO FERRAMENTA DE

OTIMIZAÇÃO EM SISTEMAS DE POTÊNCIA

Introdução; Metodologia dos Algoritmos Genéticos; Estudo de caso; Vantagens e Desvantagens; Conclusões.

2

3

AG é uma técnica de busca e otimização baseada nos processos biológicos de seleção natural e implementada por sistemas computacionais;

AG começaram a ser estudados por John Holland no começo dos anos 70, onde se deu inicio a uma pesquisa sobre algoritmos que manipulavam strings de 0 e 1, a qual ele chamou de cromossomos.

Algoritmos Genéticos (AG) são modelos computacionais inspirados nos mecanismos da evolução natural para resolver problemas de otimização;

De acordo com a teoria de Darwin, o princípio da seleção privilegia os indivíduos mais aptos com maior longevidade e, portanto, com maior probabilidade de reprodução.

Indivíduos com mais descendentes tem mais chance de perpetuarem seus códigos genéticos nas próximas gerações.

Códigos genéticos constituem a identidade de cada indivíduo e estão representados nos cromossomos.

4

Estes princípios são imitados na construção de algoritmos computacionais que buscam uma melhor solução através da evolução de populações de soluções codificadas através de cromossomos artificiais;

Nos AGs: um cromossomo é uma estrutura de dados que representa uma das possíveis soluções do espaço de busca do problema;

O método funciona a partir da criação de uma população de possíveis respostas para o problema a ser tratado, para depois submetê-lo ao processo de evolução.

A busca se dá a partir de uma população inicial, que combinando os melhores representantes desta população, obtêm uma nova, que passa a substituir a anterior.

5

6

Avaliação: avalia-se a aptidão das soluções (indivíduos da população), fazendo uma análise para que se estabeleça o quão bem elas respondem ao problema proposto;

Seleção: indivíduos são selecionados para a reprodução. A probabilidade de uma dada solução ser selecionada é proporcional a sua aptidão;

Cruzamento: características das soluções escolhidas são recombinadas, gerando novos indivíduos;

7

Mutação: características dos indivíduos resultantes do processo de reprodução são alteradas, acrescentando assim variedade à população;

Atualização: os indivíduos criados nesta geração são inseridos na população;

Finalização: verificam se as condições de encerramento da evolução foram atingidas, retornando para a etapa de avaliação em caso negativo e encerrando a execução em caso positivo.

8

De forma geral:O indivíduo que evolui é a solução para um dado problema.

Este indivíduo faz parte de uma população composta de possíveis soluções ao problema.

Cada indivíduo (solução) recebe uma pontuação de aptidão (ou fitness score) que indica quão boa é a solução para o problema.

A solução com fitness score mais alto se reproduzem, sendo que os genes dos descendentes sofrem recombinação e mutação, repetindo esse processo até que algum critério de parada seja atingido.

9

Operadores genéticos: Seleção → Cruzamento → Mutação.

Seleção: escolhe os elementos da população que participarão do processo de reprodução.

Selecionar os pais dos indivíduos que estarão presentes na nova população.

Membros da população mais adaptados ao ambiente tem maior chance de reprodução, ou seja, com valor de aptidão mais elevado.

A forma mais conhecida de fazer essa seleção é pelo algoritmo de Monte Carlo, conhecido também por Seleção por Roleta.

10

Operadores genéticos: Seleção → Cruzamento → Mutação.

Cruzamento, recombinação ou crossover:

Tem a função de combinar os cromossomos dos pais para gerar cromossomos dos filhos. Dentre as técnicas de cruzamento destacam-se a de cruzamento em um ponto e cruzamento uniforme.

11

Operadores genéticos: Seleção → Cruzamento → Mutação.

Mutação: é responsável pela inserção de pequenas mudanças aleatórias nos cromossomos dos filhos. Existem também diversos tipos de operadores de mutação, entre eles a mutação de bit, mutação por troca, entre outros.

12

Estudo de caso foi realizado por Reinaldo Burian (2009) com o titulo de “Algoritmos Genéticos na Alocação de Dispositivos de Proteção de Distribuição de Energia Elétrica”.

O objetivo é comparar índices de desempenho de um circuito, na medida em que elementos de proteção de sobrecorrente forem sendo acrescentados, e então determinar a melhor configuração para o caso analisado através da utilização de algoritmos genéticos.

13

Os índices de confiabilidade em sistemas de distribuição de energia elétrica representam quão bom e confiável é o desempenho do sistema.

Garantem o fornecimento de energia seguro e adequado da concessionária ao consumidor.

Os índices de desempenho fornecem informações à uma base de dados histórica da concessionária, que registra informações como número de faltas, tempo fora do ar e número de consumidores afetados.

Essas informações são usadas para verificar se o sistema atingiu resultados esperados.

14

Para o estudo foi considerado os seguintes índices de desempenho:

SAIDI – Índice da duração de interrupção média do sistema, que define a duração da interrupção média por consumidor durante o ano em minutos de interrupção.

SAIFI – Índice de frequência de interrupção média por consumidor, que define a frequência de interrupções sustentadas para consumidores que experimentam faltas permanentes em número de interrupções.

15

Foram considerados os seguintes valores para a base de cálculo do circuito:

Número de faltas por km de circuito por ano: 0,1367Faltas permanentes: 20%Faltas temporárias: 80%Restauração manual: 2,0 horasReparo para linhas 3Φ: 3,0 horasReparo para linhas 1Φ: 2,5 horas

16

Caso 1: circuito com disjuntor na subestação de energia elétrica sem capacidade de religamento.

17

Caso 2: Circuito com religamento no disjuntor da subestação.

Nesta situação para qualquer ocorrência de falta temporária no circuito o disjuntor será sensibilizado, e de acordo com sua programação e ajustes entrará em ciclo de religamento a fim de manter o fornecimento de energia elétrica.

18

Caso 3: circuito com religamento no disjuntor da subestação em coordenação com fusíveis nas laterais dos circuitos.

Os fusíveis devem atuar interrompendo faltas nas laterais antes que o dispositivo religadores entre em ciclo de religamento para o caso de faltas permanentes. Se houver faltas temporárias, o religador atua nessa situação funcionando como um “filtro de faltas temporária”.

19

Caso 4: circuito com religadores distribuídos pelo circuito.

O circuito foi dividido em zonas de acordo com a região de atuação do dispositivo de proteção, a fim de facilitar o cálculo dos índices de qualidade:

Zona 1: região à jusante do elemento com capacidade de religamento na subestação (R) até à montante do religador R4.

Zona 2: à jusante do religador R4 até à montante dos religadores R7 e R5. Zona 3: à jusante do religador R5. Zona 4: à jusante do religador R7.

20

Valores de SAIFI e SAIDI para cada caso.

Pode-se observar pelos resultados encontrados que com a adição de dispositivos de proteção de sobrecorrente, como religador associado ao disjuntor e religador associado a fusível, o circuito obteve uma grande melhora nos seus índices de desempenho.

Modelo SAIFI SAIDI

1 31,1731 65,6927

2 6,2346 15,7962

3 2,1650 5,5199

4 1,0432 2,7666

21

TEIAA: programa que realiza o cálculo de índices de desempenho um circuito de distribuição de energia elétrica.TEIAG: programa que incorpora o programa TEIAA e realiza a implementação do algoritmo genético.

TEIAA TEIAG

22

Primeiramente é necessário assumir a solução potencial para o problema, que é modelado por uma estrutura cromossômica, onde são aplicados operadores genéticos como: mutação, crossover, adaptação e evolução.

A partir de uma representação dos equipamentos de proteção alocados como “strings” (ou cromossomos), com pesos e custos correspondentes, calculou-se o fator de fitness (ff):

S = Disjuntor de Subestação R = Religador

η = Fator de normalização F = Fusível

23

Gene: é um equipamento em uma determinada posição na rede de distribuição de energia elétrica.

Cromossomo: é uma palavra, onde cada gene corresponde a um trecho.

Indivíduo: solução pronta com os equipamentos (genes) alocados, representando o registro inteiro.

24

Por exemplo:

A alocação de um religador corresponde ao conceito gene que é considerado como um parâmetro. Uma mudança em um parâmetro é uma mutação ou um conjunto de parâmetros que induz a uma possível solução correspondente a um cromossomo. Um indivíduo é uma solução composta por um conjunto de parâmetros e duas variáveis de AG adicionais (conjunto de equipamentos alocados). Uma dessas variáveis é o fator de fitness. A outra variável de controle é o operador genético descrito, que corresponde à decisão do julgador, ou seja, o que será feito com o cromossomo.O termo geração significa “todos os indivíduos” (ou todas as soluções) presentes em uma dada iteração.

25

O AG desenvolve-se com base nas funções:

Copiar (5%): o indivíduo permanece o mesmo na próxima geração.

Crossover (89%): o indivíduo é escolhido para alterar um número de genes (parâmetros) com outro indivíduo, criando um novo elemento.

Mutação (1%): um dos genes deverá ser aleatoriamente alterado.

Descartar (5%): nenhum dos genes deve continuar nas próximas gerações.

26

As simulações no TEIAA os resultados foram importados para o TEIAG para realização da melhor configuração do circuito em análise através do algoritmo genético.

O AG realizou a varredura de um grande número de soluções e configurações, dentro de um universo de 50 gerações de configurações (cromossomos).

Índice Valor

SAIDI 2,7694

SAIFI 1,0438

Custos S 60 unidades de valor

Numero S 1

Custo R 280 unidades de valor

Numero R 3

Custo F 25 unidades de valor

Numero F 9

Custo Total 365 unidades de valor

27

São robustos e aplicáveis a grande variedade de problemas;

É uma técnica adequada para funções multimodais e de comportamento complexo;

Não são afetados por descontinuidades; Apresentam bom desempenho para problemas em

grande escala; Permitem flexibilidade no tratamento do problema ser

resolvido.

Dificuldade de achar o ótimo global exato; Requer grande número de avaliações; Grandes número de configurações que podem complicar a

resolução do problema.

No entanto, estas desvantagens podem ser atenuadas com o avanço das técnicas e capacidades computacionais.

28

Os AG são métodos de busca e otimização que simulam processos naturais de evolução;

O processo de evolução resulta numa nova população com melhores soluções do problema;

É uma técnica eficiente na busca de soluções ótimas ou próximas do ótimo;

São empregados em uma variedade de problemas complexos; Não impõem limitações muitas vezes encontradas em outros

métodos de busca tradicionais.

29

OBRIGADO

30