ads:
Algoritmo para obtenção de planos de
restabelecimento para sistemas de distribuição de
grande porte
Moussa Reda Mansour
Dissertação apresentada à Escola de
Engenharia de São Carlos, da Univer-
sidade de São Paulo, como parte dos
requisitos para obtenção do Título de
Mestre em Engenharia Elétrica.
Orientador: Prof. Dr. João Bosco Augusto London Junior
São Carlos
2009
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
ads:
“Dedico este trabalho ao meu avô Moussa (in memoriam).”
“Lutar e vencer todas as batalhas não é a glória suprema.
A glória suprema consiste em quebrar a resistência do inimigo sem lutar.”
(Sun Tzu)
Agradecimentos
Aos meus pais, Reda e Fatme, pelo amor
e pela confiança que me d eram.
As minha s irmãs, Noura, Sara e Eva por todo o
apoio moral e c arinh o que me passaram.
Ao meu cunhado Shadi pela valiosa amizade que criamos.
Ao professor Dr. João Bosco A. Londo n Jr. pela orientação,
dedicação e con fiança para o sucesso do projeto de pesquisa.
Ao professor Dr. Alexand re Cláudio B. Delbem,
pela co-orientação e apoio neste projeto de pesquisa.
Ao meu grande amigo Narnia (Marcelo Nanni) por me apresentar
o maravilh oso mundo dos Sistemas Elétricos de Potência.
Aos professores do LACo-SEP (Laboratório de Análise
Computacional e m Sistemas Elétricos de Potência), Newton Geraldo Bretas,
Luís Fernando Costa alberto e Rodrigo Andrade Ramos.
Aos meus amigos e colegas Escama (Marcelo Castoldi), Doido (Robson Dutra),
Pernin ha (Raphael Benedito), Valdick Soriano (Leandro Brolin),
A len da (Elmer), Pedrão Fenômeno (Pedro), Perd igão (Rodrigo Salim),
Banqueiro (R afael Borges), Zero 2 (Fabiolo), Aderbaalll (Carlisson), Krow (Carol),
Augustus (Aug usto), Jaja (Saulo), Madlein ( Madale ine), Marceleza (Marcelo),
Cabelera (Marcel), Prodígio (Edson), Japoneis Doido (Marcelo Suetake),
Gordin ( Gabriel) , Mulher Maravilha (Karen), Maranhão (Antonio) e Fabin (Fabinho).
A todos meus a migos e colegas cujo nome não foi citado acima.
E à FAPESP, pelo apoio financeiro.
Resumo
MANSOUR, M. R., Algoritmo p ara obtenção de planos de restabelecimento para sis-
temas de distribuição de grande porte. São Carlos, 2009, 110p. Dissertação
(Mestrado) - Escola de Engen haria de São Carlos, Universidade de São Paulo.
A elaboração de planos de restabelecimento de energia (PRE) de forma rápida,
para re-energização de sistemas de distribuição radiais (SDR), faz-se necessária para
lidar com situaçõ es que deixam regiões dos SDR sem energia. Tais situações podem
ser causadas por faltas permanentes ou pela necessidade de isolar zonas dos SDR para
serviços de manutenção.
Dentre os objetivos de um PRE, destacam-se: (i) Reduzir o número de consumi-
dores interrompidos (ou nenhum), e (ii) minimizar o número de manobras; que devem
ser atendidos sem desrespeitar os limites operac iona is dos equipamentos. Conseqüen-
temente, a obtenção de PRE em SDR é um problema com múltiplos objetivos, alguns
conflitantes.
As principais técnicas desenvolvidas para obtenção de PRE em S DR baseiam-se em
Algoritmos Evolutivos (AE). A limitação da maioria dessas técnicas é a nece ssidade de
simplificações n a rede, para lidar com SDR de grande porte, que limitam consideravel-
mente a possibilida de de obtenç ão de um PRE adequado.
Propõe-se, neste trabalho, o desenvolvimento e implantação computacional de um
algoritmo para obtenção de PRE em SDR, que consiga lidar com sistemas de grande
porte sem a necessidade de simplificações, isto é, considerando uma grande p arte (ou a
totalidade) d e linhas, barras, cargas e chaves do sistema.
O algoritmo proposto baseia-se em um AE multi-objetivo e na estrutura de dados,
para armazenamento d e grafos, denominada Representação Nó-Profundidade (RNP),
bem como em dois operadores genéticos que foram desenvolvido s para manipular de
forma eficie nte os dados armazenados na RNP.
Em razão de se basear em um AE multi-objetivo, o algoritmo proposto possibilita
uma investigação mais ampla do espaço de busca. Por outro lado, fazendo uso da
RNP, para representar computacionalmente os SDR, e de seus operadores genéticos,
o algoritmo proposto aumenta significativamente a eficiência da busca por adequados
PRE. Isto porque aqueles operadores geram apenas configurações radiais, nas quais
todos os consumidores são atendidos.
Para comprovar a eficiência do algoritmo proposto, várias simulações computacionais
foram realizadas, utilizando o sistema de distribuição real, de uma companhia Brasileira,
que possui 3.860 b arras, 635 chaves, 3 subestações e 23 alimentadores.
Palavras-chave: Restauração de Energia, Sistemas de Distribuição de Grande
porte, Estrutura de Dados, R epre sentação Nó-Profundidade, Algoritmo Evolutivo Multi-
objetivo, NSGA-II.
Abstract
MANSOUR, M. R., Algorithm for elaboration of pla ns for service restoration to large-
scale distribution systems. Sao Carlos, 2009. 110p. Dissertation (Master study),
Engineering S cho ol of Sao Carlos, University of Sao Paulo.
An elaborated and fast energy restoration plan (ERP) is required to deal with steady
faults in radial distribution systems (RDS). That is, after a faulted zone has been identi-
fied and isolated by the relays, it is desired to elabor ate a proper ERP to restore energy
on that zone. Moreover, during the normal system operation, it is frequently necessary
to elaborate ERP to isolate zones to execute routine tasks of network maintenance.
Some of the objectives of an ERP are: (i) very few interrupted customers (or none),
and (ii) operating a minimal number of switches, while at the same time respecting
security constraints. As a consequence, the service restoration is a multiple objective
problem, with some d egre e of conflict.
The main methods developed for elab ora tion of ERP are based on Evolutionary
Algorithms (EA). The limitation of the majority of these methods is th e necessity of
network simplific ation s to work with large-scale RDS. In general, these simplifications
restrict th e achievement of an adequate ERP.
This work proposes the development an d implementation of an algorithm for elabo -
ration of ERP, which can deal with large-scale RDS without requiring network simpli-
fications, that is, considering a large number (or all) of lines, buses, loads and switches
of t he system.
The proposed algorithm is based on a multi-objective EA, on a new graph tree encod-
ing called Node-depth Encoding (NDE), as well as on two genetic operators developed
to efficiently manipulate a graph trees stored in NDEs.
Using a multi-objective EA, the proposed algorithm enables a better exploration of
the search space. On the other hand, using NDE and its operators, the efficiency of the
search is increased when the proposed algorithm is used generating proper ERP, because
those o perators gen erate only radial configuration s where all consumers are attended.
The efficiency of the proposed algorithm is shown using a Brazilian distribution
system with 3,8 60 buses, 635 switches, 3 substations and 23 feeders.
Key-words: Energy Restoration, Large-Scale Distribution System, Data Structure,
Node-Depth Encoding, Multi-Objective Evolutionary Algorithms, NSGA-II.
Sumário
Resumo vii
Abstract ix
Lista de Figuras xv
Lista de Tabelas xix
Lista de Abreviaturas e Siglas xxi
1 Introdução 23
1.1 Sistema d e Distribuição . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.2 Restabelecimento de Energia em Sistemas de Distribuição Radiais . . . 25
1.3 Objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
1.4 Organização d a Dissertação . . . . . . . . . . . . . . . . . . . . . . . . . 28
2 Revisão Bibliográfica 31
2.1 Considerações Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3 Fundamentos de Algoritmos Evolutivos 37
3.1 Base Bioló gica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.1.1 O Pr ocesso Evolutivo . . . . . . . . . . . . . . . . . . . . . . . . 38
3.1.2 Terminologia Básica . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.2 Algoritmos Evolu tivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.2.1 AEs de Última Geraç ão . . . . . . . . . . . . . . . . . . . . . . . 43
3.3 Operadores Genéticos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.3.1 Seleção . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.3.2 Cruzamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.3.3 Mutação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.3.4 Elitismo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4 Algoritmos Evolutivos para Otimização Multi-Objetivo 47
4.1 Otimização Multi-Objetivo . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.1.1 Problemas de Otimização Multi-Objetivo . . . . . . . . . . . . . 47
4.1.2 Metas em Otimizaç ão Multi-Objetivo . . . . . . . . . . . . . . . 52
4.1.3 Diferenças entre Otimização Multi-Objetivo e a Otimização Mono-
Objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.1.4 Técnicas Tradicionais para MOOP . . . . . . . . . . . . . . . . . 54
4.2 Algoritmos Evolu tivos para Otimização Multi-Objetivo . . . . . . . . . 59
4.2.1 NSGA-II: Elitist Non-Dominanted Sorting Genetic Algorithm . . 61
5 Estruturas de Dados para AEs Aplicados a Problemas de Projeto de
Redes 67
5.1 Principais Conceitos da Teoria de Grafos . . . . . . . . . . . . . . . . . 67
5.2 Representações de PPRs para AEs . . . . . . . . . . . . . . . . . . . . . 69
5.3 Representação Nó-Profundidade . . . . . . . . . . . . . . . . . . . . . . 70
5.3.1 Operador 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
5.3.2 Operador 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
6 Fluxo de Carga 77
6.1 Considerações Iniciais . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
6.2 Método Backward/Forward de Soma de Correntes . . . . . . . . . . . . 79
6.3 Método Backward/Forward da Soma de Potências . . . . . . . . . . . . 81
7 Algoritmo Evolutivo para Reconfiguração de SDR 83
7.1 Restabelecimento: um prob lema especial de reconfig uraç ão de SDR . . 83
7.2 Formulação Matemática . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
7.3 Avaliação das soluções . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
7.3.1 Extensão da RNP para fluxo de carga . . . . . . . . . . . . . . . 90
7.3.2 Método Backward/Forward com RNP . . . . . . . . . . . . . . . 93
7.3.3 Cálculo do número de manobras . . . . . . . . . . . . . . . . . . 95
7.4 Algoritmo E volutivo para Restabelecimento de SDR . . . . . . . . . . . 98
7.5 Comentários Adicionais . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
8 Algoritmo Proposto para Restabelecimento de Energia para SDR 101
8.1 Formulação Matemática . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
8.2 Algoritmo P roposto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
8.3 Exemplo Ilu strativo da Aplicação do PRN . . . . . . . . . . . . . . . . 104
9 Testes e Resultados 111
9.1 Testes Realizados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
9.2 Resultados das Simulações no SDR Real de São Carlos . . . . . . . . . 114
9.2.1 Falta Única . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
9.2.2 Múltiplas Faltas . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
9.3 Resultados das Simulações no SDR Real de São Carlos Duplicado . . . 123
9.4 Comentá rios Adicionais . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
10 Conclusões 129
10.1 Publicações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
Referências Bibliográficas 133
Lista de Figuras
FIGURA 1.1 Representação de um sistema de distribuição. . . . . . . . . . 24
FIGURA 3.1 Exemplo da aplicação do operador de cruzamento em um ponto. 45
FIGURA 3.2 Exemplo da a plica ção do operado r de mutação. . . . . . . . . 45
FIGURA 4 .1 Exemplo que ilustra o preço e o desempenho para 5 alternativas
de co mpra de comput ado res. . . . . . . . . . . . . . . . . . . . . . . . . . 50
FIGURA 4.2 Soluções de Par eto-ó timas locais e global. . . . . . . . . . . . . 52
FIGURA 4.3 Diferente s distribuições de soluções na fronteira de Pareto. . . 52
FIGURA 4.4 O método do somatório de pesos. . . . . . . . . . . . . . . . . 55
FIGURA 4.5 Método de restrições ǫ (Deb, 2001). . . . . . . . . . . . . . . . 56
FIGURA 4.6 Método de programação de metas lexicográficas ( Deb, 2001). . 58
FIGURA 4.7 Ordenação por não dominância (Deb , 2001). . . . . . . . . . . 62
FIGURA 4.8 Esquema d o mod elo NSGA-II (Deb , 2001). . . . . . . . . . . . 65
FIGURA 5.1 Exemplo de u m grafo. . . . . . . . . . . . . . . . . . . . . . . . 68
FIGURA 5.2 Exemplo de u m grafo e sua RNP . . . . . . . . . . . . . . . . . 71
FIGURA 5.3 Ilustração d os passos do ope rad or 1 . . . . . . . . . . . . . . . 73
FIGURA 5.4 Ilustração d os passos do ope rad or 2. . . . . . . . . . . . . . . . 75
FIGURA 6.1 Exemplo de u m SDR. . . . . . . . . . . . . . . . . . . . . . . . 78
FIGURA 6.2 Sistema d e distribuiçã o radial. . . . . . . . . . . . . . . . . . . 80
FIGURA 7.1 SDR co m 3 alimentadores. . . . . . . . . . . . . . . . . . . . . 84
FIGURA 7.2 SDR em falta no setor 15. . . . . . . . . . . . . . . . . . . . . 85
FIGURA 7.3 Se tores a jusante do setor em falta desconectados do SDR. . . 85
FIGURA 7.4 Nova configuração. . . . . . . . . . . . . . . . . . . . . . . . . 86
FIGURA 7.5 SDR co m dois alimentadores. . . . . . . . . . . . . . . . . . . . 91
FIGURA 7.6 Agru pamento das linhas e barras em setores. . . . . . . . . . . 91
FIGURA 7.7 Grafo rep resentando setores do SDR da Figura 7.6. . . . . . . 91
FIGURA 7.8 Árvore do setor C, com o nó adicional. . . . . . . . . . . . . . 92
FIGURA 7.9 Operações de manobras necessárias para isolar o seto r em falta. 96
FIGURA 8.1 SDR co m 8 alimentadores. . . . . . . . . . . . . . . . . . . . . 105
FIGURA 8.2 SDR co m falta no setor 4. . . . . . . . . . . . . . . . . . . . . 106
FIGURA 8.3 SDR resta belecido. . . . . . . . . . . . . . . . . . . . . . . . . 106
FIGURA 8.4 Melho r configu raçã o alterada. . . . . . . . . . . . . . . . . . . 107
FIGURA 8.5 Melhor configuração alterada gerada no meio do processo iter-
ativo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
FIGURA 8.6 Melho r configu raçã o gerada no final do processo iterativo. . . . 109
FIGURA 9.1 Primeir a Fronteira de Pareto após a falta única no setor 3668. 116
FIGURA 9.2 Red uçã o das perdas por geraçã o para falta única no setor 3668 . 117
FIGURA 9.3 Aumento das manobras por geração para falta única no setor
3668. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
FIGURA 9.4 Manobras e perdas resistivas linearizadas para falta ún ica no
setor 36 68. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
FIGURA 9.5 Primeir a Fronteira de Pareto (múltiplas faltas). . . . . . . . . 119
FIGURA 9.6 Red uçã o das perdas por geraçã o (múltiplas faltas). . . . . . . . 121
FIGURA 9.7 Aumento das manobras por geração (múltiplas faltas). . . . . 121
FIGURA 9.8 Man obra s e perdas resistivas linearizadas (múltiplas faltas). . . 122
FIGURA 9.9 Primeira Fronteira de Pareto após as múltiplas faltas no SDR
duplicado. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
FIGURA 9.10 Reduç ão das perdas por geração para múltiplas faltas no SDR
duplicado. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
FIGURA 9.11 Redução das manobras por geração para múltiplas faltas no
SDR duplicado. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
FIGURA 9.12 Manobras e perdas resistivas linearizadas para múltiplas faltas
no S DR dup licado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
Lista de Tabelas
TABELA 2.1 Classificação das publicações segundo a técnica utilizada. . . . 32
TABELA 4.1 Diferentes modelos de MOEAS. . . . . . . . . . . . . . . . . . 61
TABELA 5.1 Grau de cada um dos nós do grafo da figura 5.1. . . . . . . . . 68
TABELA 5.2 Principais representaçõe s de PPRs para AEs. . . . . . . . . . 70
TABELA 7.1 Manobras de chaves - caso 1. . . . . . . . . . . . . . . . . . . . 97
TABELA 7.2 Manobras de chaves - caso 2. . . . . . . . . . . . . . . . . . . . 97
TABELA 7.3 Manobras de chaves - caso 3. . . . . . . . . . . . . . . . . . . . 97
TABELA 9.1 Configurações da primeira Fronteira de Pareto após a falta única.114
TABELA 9.1 Configur ações da primeira Fronteira de Pareto após a falta
única. (continuação) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
TABELA 9.2 Comparativo entre os métodos AERT e PRN par a falta única
no seto r 366 8. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
TABELA 9.3 Configurações da primeira Fronteira de Pareto (múltiplas faltas).119
TABELA 9.3 Configurações da primeira Fronteira de Pareto após múltiplas
faltas ( continuação). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
TABELA 9.4 Comparativo entre os métodos AERT e PRN em múltiplas faltas.122
TABELA 9.5 Configurações da primeira Fronteira de Pareto após múltiplas
faltas n o SDR duplic ado . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
TABELA 9.5 Configurações da primeira Fronteira de Pareto após múltiplas
faltas no S DR duplicad o(co ntinuação). . . . . . . . . . . . . . . . . . . . 125
TABELA 9.6 Comparativo entre os métodos AERT e PRN em múltiplas faltas.127
Lista de Abreviaturas e Siglas
ǫ-MOEA . . . . . . . . . . . . . . ǫ-dominance Multi-Objective Evolutionary Algorithm
AE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Algoritmo Evolutivo
AG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Algoritmo Genético
BH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Busca Heurística
BT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Busca Tabu
BTR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Busca Tabu Reativa
DEC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Dura ção Equivalente por Consumidor
DRO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Depths Recombination Operator
EHO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Evolutionary History Operator
EE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Estratégias Evolutivas
FEC . . . . . . . . . . . . . . . Frequência Equivalente de Interrupção por Consumidor
PE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Programação Evolutiva
PG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Programação Genética
SA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Simulated Anneling
MOO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Multi-Objective Optimization
MOEA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Multi-Objective Evolutionary Algorithm
MOGA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Multiple Objective Genetic Algorithm
MOOP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Multi-Objective Optimization Problem
MPF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Modelo Pai-Filho
Micro-GA . . . . . . . . . . . . . . . . . . . . . . . Multi-Objecti ve Micro-Genetic Algorithm
MOMGA-I . . . . . . . . . . . . . . . . . . . . . . Multi-Objective Messy Genetic Algorithm I
MOMGA-II . . . . . . . . . . . . . . . . . . . . Multi-Objective Messy Genetic Algorithm II
NA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Normalmente Aberta
NDDE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Node-Depth-Degree Encoding
NDRO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Node Depth Recombination Operator
NF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Normalmente Fechada
NPGA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Niched-Pareto Genetic Algorithm
NS2R . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . NSGA-II com RNP
NSGA . . . . . . . . . . . . . . . . . . . . . . . . .Non-Dominanted Sorting Genetic Algorithm
NSGA-II . . . . . . . . . . . . . . Elitist Non-Dominanted Sorting Genetic Algorithm
PESA-I . . . . . . . . . . . . . . . . . . . . . . .Pareto Envelope-Base Selection Algorithm I
PESA-II . . . . . . . . . . . . . . . . . . . . Pareto Envelope-Base Selection Algorithm II
PAES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Pareto-Archived Evolutionary Strategy
PPR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Problema de Projeto de Redes
PPES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Predator-Prey Evolutionary Strategy
PRN . . . . . . . . . Programa para Restabelecimento de SDRs utilizando o NS2R
REMOEA . . . . . . . . . . Rudolph’s Elitist Multi-Objective Evolutionary Algorithm
RNP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Representação Nó-Profundidade
SI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Sistemas Inteligentes
SDR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Sistema de Distribuição Radial
SEP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Sistema Elétrico de Potência
SPEA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Strenght Pareto Evolutionary Algorithm
SPEA2 . . . . . . . . . . . . . . . . . . . . . . . . . . Strenght Pareto Evolutionary Algorithm 2
TGA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Thermodynamical Genetic Algorithm
VEGA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Vector Evaluated Genetic Algorithm
WBGA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Weight Based Genetic Algorithm
23
Capítulo 1
Introdução
Em razão do aumento da demanda de energia elétric a e da expansão dos sistemas
elétricos de potência (SEP), para manter o suprimento de energia elétrica, obedecendo
à trilogia de continuidade, qualidade e economia de serviço (Miller, 1987), torna-se
necessário, cada vez mais, o desenvolvimento de ferramentas computacionais de auxílio
à operação dos SEP.
Os SEP podem ser divididos nos três grandes b locos (Kagan et al., 2005):
• Sistema de geração: composto pelas usinas de geração de energia elétrica, que
geram a energia elétrica a partir da conversão eletr omecâ nica de energia. A fonte
primária de ene rgia pode ser a ág ua, o carvão, o óleo, a fissão nuclear, etc;
• Sistema de transmissão: composto basicamente p or linhas de transmissão e
transformadores reguladores, que conectam os pontos de geração aos pontos de
consumo (at é as subestações de d istribuiç ão) ;
• Sistema de distribuição: composto por subestações abaixadora s e circuitos elétri-
cos (chamados alimentadores). É responsável pelo fornecimento de energia às
áreas u rban as, rurais ou grandes empresas consumidoras.
Este trabalho trata do problema de Restabelecimento de energia em Sistemas de
Distribuição Radiais de méd ia tensão.
24 1.1. Sistema de Distribuição
1.1 Sistema de Distribuição
O sistema de Distribuiçã o pode ser dividid o em:
• Sistema (ou rede) de Distribuição Primária (ou Distribuição de Média
Tensão): opera geralmente em redes radiais aéreas na tensão de 13,8kV. É pro-
jetado com possibilidade de transferência de blocos de cargas entre circuitos para
o atendimento da ope raçã o em condições de contingências ou para manutenção
preve ntiva e/ou corretiva. Esse sistema atende aos consumidores primários (indus-
triais de médio porte, conjuntos comerciais, grandes hospitais, shopping centers,
instalações de iluminação pública, etc) e aos transformadores de distribuição que,
por sua ve z, suprem os sistemas de distribuição secundária ou de baixa tensão;
• Sistema (ou rede) de Distribuição Secundária (ou Distribuição de Baixa
Tensão): opera geralmente em redes radiais ou em malha com tensões de 220/127V
ou 380/220V. Atende aos consumidores de baixa tensão, pequeno s comércios e in-
dústrias e, principalmente, os consumidores domésticos. Essa parte do sistema de
distribuição usualmente não conta com recurso para o atendimento de contingên-
cias.
Figura 1 .1: Re pre sentação de um sistema de distribuição.
A Figura 1.1 ilustra o diagrama unifilar de um sistema de distribuição dividid o em
Rede Primária e Secundária, onde TR é um transformador, D é um disjuntor, NF é
uma chave Normalmente Fechada e NA é uma chave Normalmente Aberta.
1.2. Restabelecimento de Energia em Sistemas de Distribuição Radiais 25
1.2 Restabelecimento de Energia em Sistemas de Distribuição
Radiais
No crescente mercado competitivo as distribuidoras de energia elétrica têm en-
frenta do muitos desafios relacionados com os objetivos de melhorar a qualidade e con-
fiabilidade do serviço de fornecimento de energia elétrica. Ou seja, a energia deve ser
entr egu e ao consumidor de forma contínua, com a tensão mais constante possível, sem
conteúdo harmônico, com mínimas perdas de potência ativa e máxima margem de se-
gurança em ter mos de estabilidad e de tensão.
A característica radial da maioria dos sistemas de distribuição simplifica a operação
e proteção dos mesmos, porém diminui a confiabilidade desses sistemas em relação
à continuidade do fornecimento de energia elétrica, que é geralmente avaliada p elas
empresas de d istribu ição, a partir das ocorrência s no sistema de distribuição.
A contabilização da continuidade de fornecimento de energia aos consumidores é
avaliada após um determinado período, por exemplo, o ano, através de índices opera-
tivos, como por exemplo (Kag an et al., 2005):
• Duração Equivalente por Consumidor (DEC): representa o espaço de tempo
em que, em média, cada consumidor, na áre a em estudo, teve seu fornecimento
de en erg ia elétrica interrompido no período considerado;
• Frequência Equivalente de Interrupção por Consumidor (FEC): repre-
senta o número de interrupções que, em média, cada consumidor, na área de
estudo, sofreu, no período considerado;
Face ao exposto, a reconfiguração de redes é uma ferramenta importante na au-
tomação dos Sistemas de Distribuição R adia is (SDR), pois é um dos principais recur-
sos para manutenção da qualidade e confiabilidade do fornecimento de energia elétrica
(Kagan e Oliveira, 1996).
As interrupções no fornecimento de energia nos SDR são inevitáveis, isto em virtude
da execução de obras de expansão, intervenções de manutenção preventiva em compo-
nentes da rede ou pela atuação de um dispositivo de pro teçã o em decorrência de faltas
permanentes. Desta forma, o agrupamento de vários pontos de carga em blocos sep-
arados por chaves, que operam no estado Normalmente Aberto (NA) e Normalmente
26 1.2. Restabelecimento de Energia em Sistemas de Distribuição R adiais
Fechado (NF), foi uma solução encontrada para melhorar a confia bilidade dos SDR
sem incorrer em gastos excessivos. Assim, a partir da reconfiguração da rede, isto é,
da operação de chaves, é possível a troca de carga entre os alimentadores em caso de
inter rupção em algum p o nto da rede. Nessas situações, torna-se necessário um plano de
restabelecimento de energia, que consiste, basicamente, em determinar um conjunto de
manobras d e chaves para restringir as interrupções à menor parte possível do sistema.
Vale destacar ainda que em condições normais de operação, p ode-se utilizar a re-
configuração de redes, através da manobra de chaves NA e NF, para reduzir as perdas
totais por efeito joule (Gomes et al., 2005; Sarfi et al., 1995) e/ou para balanceamento
de carga entre os alimentadores (Chen et al., 2000), aliviando os alimentadores que
estão com carregamento crítico. Nesse c ontexto, a reconfiguração permite a redução de
queda de tensão (Mantovani et al., 2000) e alívio de trechos da rede com sobrecarga
(Strogatz, 20 01) (corrente elétrica em níveis acima do suportado pelos cabos).
Como menciona do anteriormente, reconfiguração de redes também pode ser aplicada
numa condição mais extrema, como, por exemplo, na ocorrência d e contingên cias como
faltas permanentes (Inagaki et al., 2006; Kumar et al., 2008). Tal aplicação é o foco
deste projeto de pesquisa. Nesse caso, torna-se necessário a obtenção de um plano de
restabelecimento de energia elaborado e rápido. Ou seja, depois de o setor
1
em falta
ter sido identificado e isolado, pela atuação do sistema de proteção, é de interesse dos
operadores encontrar um plano apropriado para o restabelecimento da energia na área
que h avia ficado sem energia.
Um plano de restabelecimento de energia adequado tem como principais necessidades
práticas:
• Encontrar um plano em intervalo de tempo o mais curto possível (tempo-real);
• O número de manobras deve ser mínimo
2
;
• Reduzido número de consumidores interrompidos;
• Nenhum componente sobrecarregado;
1
Um setor corresponde a um conjunto de barras e linhas sem a presença de chaves seccionadoras.
2
Busca-se um reduzido número de chaveamentos basicamente por dois motivos: a operação frequente
das ch aves reduz a expectativa de vida destas; quanto mais manobras, maior o tempo para implementar
o plano (as chaves são em geral operadas manualmente).
1.2. Restabelecimento de Energia em Sistemas de Distribuição Radiais 27
• A estrutura radial (sem formar anéis) do sistema deve ser mantida;
• Reduzir o total de perdas resistivas;
• Reduzir quedas de tensão.
Face ao exposto, o restabelecimento de energia é um problema com múltiplos ob-
jetivos, alguns co nflita ntes. Naturalmente, outros objetivos, além dos supracitados,
podem ser considerados na formulação do problema.
Devido ao problema de explosão combinatória, as técnicas de programação matemática
não são utilizadas nos problemas de restabelecimento de energia em SDR de grande
porte. A maioria dos Algoritmos Evolutivos (AEs) são uma técnica alternativa que têm
se mostrado capaz de lidar com essa dificuldade, porém produzem muitas configurações
não factíveis
3
quando a plica dos em SDR de tamanho real (dos Santos, 2004).
O desempenho de um AE convencional
4
, para r estabelecimento de energia em SDR,
é afetado p rincip almente pelos seguintes fatores:
1. A estrutura de dados adotada: a elaboração de plano s de restabelecimento via AEs
requer um algoritmo de busca em grafo. Assim o desempenho dos AEs torna-se
fortemente afetado pela forma com que as árvores de grafo são computacional-
mente representadas;
2. Os operadores genéticos adotados, que podem produzir muitas con figura ções não
factíveis; e
3. A conversão de um problema multi-objetivo em um mono-objetivo através da
utilização de fatores de ponderação.
Buscando melhorar o desempenho dos AEs para o tratamento do PRE, em (Santos,
Delbem e Bretas, 2008b) o SDR foi representado computacionalmente através de uma
nova estrutura de dados, denominada Representação Nó-Profundida de (RNP). Associ-
ados a essa estrutura há dois operadores que permitem a realização de poda ou enxerto
3
No contexto em pauta, configurações factíveis são configurações radiais, que atendem a todos os
consumidores respeitando os limites de operação do sistema.
4
AEs convencionais são aqueles que convertem um problema de otimização multi-objetivo em um
problema mono-objetivo através da utilização de uma função agregação e de fatores de ponderação.
28 1.4. Organização da Dissertação
nas árvores da flor esta de grafo armazenada na RNP. Os alimentadores podem ser vis-
tos como árvores da floresta que, por sua vez, representa um SDR. Em outras palavras,
os operadores da RNP modificam a floresta d e grafo g eran do uma somente configu-
rações factíveis. A garantia de geração de somente con figur ações factíveis, aumenta
significativamente a eficiência da busca por melhores configurações do AE .
Vale destacar que a utilização da RNP possibilita ainda outra vantagem para o
tratamento do pr oble ma de restabelecimento de energia. Cada configuração gerada
através da RNP e d e seus operadores possui sempre todos os seus nós ordenados de
acordo com uma relação conhecid a como pai-filho. Essa ordenação possibilita a execução
de um fluxo de carga extremamente rápido. Trabalhando com outras estruturas de
dados e operadores, para possibilitar a utilização de um fluxo de carga rápido, torna-se
necessário executar um algoritmo de ordenação toda vez que uma nova configuração for
gerada, par a organiz ar os nós de acordo com o Modelo Pai-Filho (MPF).
Recentemente, as técnicas de AEs Multi-Objetivo (MOEA, do inglês Multi-Objective
Evolutionary Algorithm) têm sido aplicadas para o prob lema de restabelecimento de
energia em SDR, com resultados que se mostram bastante promissores. Por exemp lo,
Kumar et al. (2008) aplicou a técn ica NSGA-II (Elitist Non-Dominanted Sorting Genetic
Algorithm).
1.3 Objetivo
O principal objetivo deste trabalho é a elaboração de um programa computacional
que possibilite a obtenção de planos de restabelecimento de energia, em SDRs de grande
porte, considerando todas as suas linhas, barramentos, cargas e chaves. Para isso,
utilizar-se-á a estrutura de dados RNP e seus operadores, bem como uma versão modi-
ficada do NSGA-II.
1.4 Organização da Dissertação
Os próximos Capítulos desta dissertação estão organizados da seguinte forma:
• O Capítulo 2 revisa os principais trabalhos desenvolvidos para tratar o problema
de re stabelecimento de energia em SDR;
1.4. Organização da Dissertação 29
• O Capítulo 3 descreve fundamentos dos AEs;
• O Capítulo 4 introduz conceitos de otimização multi-objetivo, descrevendo as
técnicas tradicionais para resolver problemas de otimização multi-objetivo; e a
técnica NSGA-2;
• O Capítulo 5 apresenta os conceitos básicos da teoria de grafos e o Problema de
Projeto de Redes (PPRs) pa ra AE, bem como a estrutura de dados denominada
RNP;
• O Capítulo 6 revisa métodos para cálculo de fluxo de carga para SDR.
• O Capítulo 7 apresenta os estudos realizados sobre o método desenvolvido em (dos
Santos, 2008).
• O Capítulo 8 apresenta o NS2R, isto é, o AE p roposto neste trabalho para a
obtenção d e planos de restabe lecimento de energia em SDR;
• O Capítu lo 9 apresenta testes comprobatórios da eficiência do NS2R, juntamente
com a a nálise dos resultados; e
• O Capítulo 10 apresenta as conclusões do trabalho, bem como as publicações
originadas desta pesquisa.
31
Capítulo 2
Revisão Bibliográfica
Destacam-se, neste Capítu lo, algumas das principais técnicas para geração de planos
de restabelecimento de energia em SDR encontradas na literatura.
Em (Curcic et al., 1996) é apresentada uma análise de diversos artigos publica-
dos entre os anos 1987 e 1994, relacionados a restabelecimento de energia em SDRs.
Ressalta-se, nesse artigo, a impor tânc ia do rápido processamento computacional, bem
como as vantagens e desvantagens em se utilizar uma topologia de rede radial. No total
foram revisados 19 artigos, os quais estão classificados segundo a técnica utiliz ada , con-
forme indicado na Tabela 2. Nessa análise, foram explorados os tipos de faltas possíveis
para SDR: na s linhas, barras e transformadores.
Diversos trabalhos publicados em 2000 utilizaram Algoritmos Evolutivos (AEs) e
lógica fuzzy para resolver o problema de restabele cimento de energia em SDR.
Em (Augugliaro et al., 2000) foram utilizadas Estratégias Evolutivas (EE), com uma
definição fuzzy de múltiplos objetivos que compõem um prob lema de restabelecimento
de energia em SDR, tais objetivos sendo conflitantes. Foi considerado que o estado de
operação normal p ossibilita o controle remoto das chaves, de bancos de capacitores e
conexões de cargas. Desta forma, após a ocorrência de uma falta permanente, torna-se
possíve l executar remotamente ações para restabelecer energia nas áreas afetadas. Na
formulaç ão do problema duas funções foram consideradas como principais: minimização
de perdas resistivas e a maximização da quantidade de cargas a ser restabelecida. As
configurações geradas são avaliadas através de conjuntos fuzzy. Como restrições foram
consideradas: a permanência da estrutura radial do SDR, carregamento nos transfor-
32 2. Revisão Bibliográfica
Tabela 2.1: Classificaçã o das publicações segundo a técnica utilizada.
Técnica Trabalhos publicados
Sistemas Inteligentes (SI)
(Teo, 1992)
(Kim et al., 1992)
(Liu et al., 1988)
(Fujii et al., 1992)
(Kendrew e Graham, 1989)
(Okuda et al., 1988)
(Srinivasan et al., 1994)
Busca Heurística (BH)
(Shirmohammadi, 1992)
(Wu et al., 1991)
(Hsu et al., 1992)
(Devi et al., 1990)
(Devi et al., 1991)
(Morelato e Monticelli, 1989)
(Nahman e Strbac, 1994)
Método do gradiente efetivo dual
(Aoki, Nara, Itoh, Satoh e
Kuwabara, 1989)
(Aoki, Nara e Satoh, 1989)
Busca Tabu (BT) e caminho mínimo
(Dialynas e Michos, 1989)
(Sarma et al., 1990)
Programação inteira binária e branch and bound (Chen et al., 1989)
madores, carregamento das linhas e queda de tensão nas barras. Testes foram realizados
em um SDR inicialmente malhado contendo 98 setores, 81 barras de c arga e 24 bancos
de ca pac itore s. Considerou-se apenas a oco rrênc ia de uma única falta.
A formulação híbrida apresentada em (Hsiao e Chen, 2000) faz uso de conjunto
fuzzy e de AE. Conjunto fuzzy é utilizado para modelar as funções objetivo e avaliar a
natureza imprecisa que estas apresentam,; já AE é utilizado para resolver o problema
de otimização. Na formulação do problema foram consideradas cinco funções obje-
tivo: área fora de serviço, número de operações de chaveamento, queda de tensão nas
barras, carregamento nas linh as e carregamento nos transformadores. Como restrições
foram consideradas, manter a estrutura radial do SDR e a sequência d e operações de
chaveamento. Testes foram realizados em um SDR contendo 2 transformadores, 10 ali-
menta dor es, 102 ramos, 102 barras, 217 ch aves NF e 13 chaves NA. Foram considerados
três casos distintos: uma única falta, múltiplas faltas e múltiplas faltas deixando uma
grande área fora de serviço.
Toune et al. (2002) realizaram um estudo comparativo de 4 algoritmos heurísticos
utilizados para restabelecimento de energia em SDR. Os algoritmos estudados foram:
Busca Tabu (BT), Busca Tabu Reativa (BTR), Simulated Anneling (SA) e AEs. O
2. Revisão Bibliográfica 33
estudo foi realizado considerando o objetivo de encontrar, após a ocorrência de uma
falta, planos de restabelecimento de energia que sejam capazes de minimizar o número
de consumidores sem energia. Como restrições foram consideradas: manter a estrutura
radial do SDR, queda de tensão, carregamento nos transformadores e carregamento nas
linhas. Apresentou-se a formulação matemática de cada um dos algoritmo s e foram
realizadas comparações qualitativa s e quantitativas entres os mesmos. Realizaram-se
testes e m um SDR contendo 3 alimentadores e 60 barras.
Em (Shin et al., 2004) foi utilizada uma abordagem híbrida, combinando AEs e
BTs, para resolver o problema de restabelecimento de energia e reconfiguração ótima
de redes em SDR. No referido trabalho uma configuração é dita ótima se o plano de
restabelecimento minimiza as perdas e atende as restrições operacionais do sistema,
mante ndo a red e radial. O algoritmo pro posto procura utilizar as propriedades que
os AEs e BTs têm de melhor, dando origem ao método denominado AG-Tabu. Na
formulaç ão do problema foram avaliados o custo das perdas resistivas e o custo tota l
após a interrupção e reconexão do sistema d evido a ocorrência de uma falta. Como
restrições foram consideradas: carregamento nos transformadores, carregamento nas
linhas e manutenção da estrutura radial do SDR. Testes foram realizados em um SDR
com 7 a limentadores e 38 barras, com a ocorrência de uma única falta .
Delbem et al. ( 2005 ) propuseram uma nova codificação para SDRs ba seada em
Cadeia de Grafos, de modo a melhorar o desempenho dos AEs. A partir dessa codifi-
cação foram desenvolvidos operadores de reprodu ção não conven cion ais, que possibilita
a geração de configurações factíveis, a partir de uma configuração já existente. Uti-
lizando conceitos de grafos e, partindo do princípio que uma árvore de grafo pode ser
representada por cadeias conectando a raiz às folhas, o co njunto de todas essas cadeias
armazenadas adequadamente representa um alimentador de um SDR. Portanto, o con-
junto de todos os alimentadores representa um sistema completo. A técnica proposta
pode lidar com problemas multi-objetivo, utilizando sub-populações, que é semelhante
à técnica empregada em (R. Benayoun e Laritchev, 1971). Testes foram realizados em
um SDR de grande porte composto de 1471 barras, 249 chaves, 3 subestações e 23
alimentadores. Como restrições foram consideradas: queda de tensão, carregamento
nas linhas e carregamento nos transformadores. A estrutura radial do SDR é sempre
uma condição satisfeita no problema, pois os operadores de reprodução propostos ger am
34 2. Revisão Bibliográfica
apenas configurações factíveis. O artigo trata de uma falta por vez. Foram consider-
adas faltas em setores críticos da rede, por exemplo, que isolem todo um alimentador.
Vale destacar que a técnica foi aplicada ao problema de reconfiguração de SDR, sendo
testada em restabelecimento de energia, redução de perdas resistivas e planejamento de
SDR.
Em (Inagaki et al., 2006) utilizou-se uma abordagem multi-objetivo baseada na
obtenção de soluções pertencentes ao conjunto de Pareto (ver Capítulo 4). Para encon-
trar essas soluções são utilizados AEs. Desta forma, um número maior de configurações
é disponibilizado para o o perador decidir qual se adapt a melhor ao problema. Uma com-
binação de AEs e SA é realizada com o objetivo de melhorar a precisão das soluções.
Na formula ção do pro blema foram c onside rado s dois objetivos: reduzir a área fora de
serviço após uma falta e o número de operações (ou manobras) de chaveamento. Como
restrições foram consideradas: manter a estrutura radial do SDR, a energia deve ser
restabelecida às áreas a jusante do setor em falta, carreg amento nas linhas, carrega-
mento nos transformadores e queda de tensão. Testes foram realizados em um SDR
com 4 transformadores, 6 alimentadores e 78 barras de carga. Apenas a ocorrência
de uma única falta foi abordada nos testes. Vale destacar que os objetivos priorizam
consumidores c omo hospitais, shopping centers, etc.
Buscando melhorar o desempenho dos AEs para o tratamento do problema de resta-
belecimento de energia, em (Santos, Delbem e Bretas, 2008b) o SDR foi representado
computacionalmente através de uma nova estrutura de dados, de nomin ada Represen-
tação Nó-Profundidade (RNP). Associados a essa estrutura há dois operadores que
permitem a realização de poda ou enxerto nas árvores da floresta de grafo armazenada
na RNP. Os alimentadores podem ser vistos como árvores da floresta que, por sua vez,
representa um SDR. Em outras palavras, os operadores da RNP modificam a floresta
de grafo gerando somente configurações factíveis. A garantia de geração somente de
configurações factíveis, aumenta significativamente a eficiência da busca por melhores
configurações do AE, este trabalho será ap resentado no Capítulo 7 .
Recentemente Kumar et al. (2008) desenvolveram um algoritmo para restabeleci-
mento de energia em SDR, baseado no algoritmo de otimização multi-objetivo proposto
por (Deb et al., 2000), denominado NSGA-II. Modificações no NSGA-II foram realizadas
para melhorar o processamento computacional do mesmo. Os resultados obtidos pelo
2.1. Considerações Finais 35
método proposto, denominado NSGA-II avançado, foram comparados com os resultados
obtidos pelo NSGA-II básico proposto por (Deb et al., 2000) e por AE mono-objetivo.
O método proposto conseguiu obter os mesmos resultados encontrados p e las outras téc-
nicas, porém com um melhor tempo computacional. Isso deve -se à implementação do
NSGA-II utilizando a estrutura de dados apresentada em (Jensen, 2003). Na formulação
do problema foram considerados quatro objetivos: reduzir a área fora de serviço, mini-
mização do número de manobras (tanto para chaves remotamente controladas, qua nto
para chaves manualmente contro lada s) e minimizar as perdas resistivas. Como restriçõe s
foram consideradas: manter a estrutura radial do SDR, qued a de tensão, c arreg amento
da r ede, priorizar o restabelecimento para cargas “especiais”, como hospitais e grandes
cent ros industriais. Testes foram realizados em quatro SDR, todos de pequeno porte.
A dimensão varia de 13 barras e 10 chaves até 173 barras e 75 chaves.
2.1 Considerações Finais
Conforme apresentado neste capítulo, a maioria das técnicas para obtenção de planos
de restabelecimento de energia, em SDR, baseia-se em AEs convencionais, isto é, aque-
les que convertem um problema de otimização multi-objetivo em um problema mono-
objetivo através da utilização de fatores de ponderação.
Vale destacar, entretanto, que as técnicas baseadas em AEs convencionais possuem
ainda algumas limitações, restringindo a aplicação das mesmas para SDR de pequeno
porte ou para modelos simplificados de SDR de grande pote. Isso em razão de o desem-
penho de um AE convencional ser fortemente afetado pelos seguintes fatores:
1. A estrutu ra de dados adotada: como a busca por planos d e restabelecimento via
AEs exige normalmente busca em grafo, o desempenho dos AEs torna-se forte-
mente afetado pela forma com que as árvores de grafo são computacionalmente
representadas;
2. Os operadores genéticos adotados, que podem produzir muitas con figura ções não
factíveis; e
3. A conversão de um problema multi-objetivo em um mono-objetivo através da
utilização de fatores de ponderação.
36 2.1. Con sideraç ões Finais
Na tentativa de obter um algoritmo para obtenção de planos de restabelecimento de
energia mais eficiente, aplicável em SDR de grande porte sem simplificações, propõe-se,
neste projeto, o desenvolvimento de um algoritmo baseado no NSGA-II e na estrutura
de d ado s RNP e seus operadores.
Em razão de o algoritmo proposto basear-se no NSGA-II, o mesmo vai possibilitar
o tratamento do problema multi-objetivo de obtenção de planos de restabelec imento
de en ergia de forma direta, sem a necessidade de converter o problema original em
um problema mono-objetivo. Importa lembrar que para possibilitar o tratamento de
problemas multi-objetivos, o NSGA-II faz uso da ordenação elitista po r dominância
cha mada de Pareto Ranking (será apresentada no Capítulo 4).
As vantagens de utilizar a RNP e seus operadores, para representar e manipular
computacionalmente os SDR, são as seguintes:
1. Abordagens baseadas na RNP, para problemas que requerem a manipulação de
grafos, têm apresentado melhor desempenho computacional em relação àquelas
que u tilizam outra s estruturas de dados (Delbem et al., 2004);
2. A utilização dos op era dor es da RNP, ao invés dos operadores genéticos conven-
cionais, au menta significativamente a eficiência da busca por melhores soluções
(configurações), pois a RNP e seus operadores produzem somente configurações
factíveis;
3. A RNP de um SDR possui, naturalmente, as barras de cada árvore (alimentador)
ordenadas segundo o MPF. Com isso, evita-se o uso de um algoritmo de busca para
obter tal modelo. Assim, o fluxo de carga pelo MPF com RNP é mais eficiente
que flu xos de carga convencionais para SDR.
37
Capítulo 3
Fundamentos de Algoritmos
Evolutivos
Os Algoritmos Evolutivos (AEs) são métodos de otimização e busca inspirados nos
princípios da Teoria de Darwin, isto é, são baseados em princ ípios que são encontrados
na evolução dos sistemas biológicos. Este capítulo introduz os principais conceitos
sobre AEs os quais receberam maior atenção dos pesquisadores após a proposta dos
Algoritmos Genéticos (AGs) por John Holland (Hayes-Roth, 1975) e a popularização
dos mesmos por meio dos trabalhos de David Goldberg (Goldberg, 1989). Na seção 3.1.1
é apresentada a base biológica dos AEs. Na Seção 3.2 são descritos os AEs, bem como
as subáreas que vêm se destacado da co mputa ção evolutiva. Na Seção 3.3 são descritos
os o peradores ge nétic os.
Para escrever este Capítulo utilizou-se (Gabriel e Delbem, 2008) como referência
principal.
3.1 Base Biológica
OS AEs podem ser vistos como técnicas de Computação Bioinspirada (Teuscher
et al., 2003) ou Computação Natural (Ballard, 1999). Tais áreas de pesquisa abordam
uma série de técnicas computacionais fundamentadas em conceitos Biológicos. As téc-
nicas evolutivas apresentam conceitos cuja origem está em diversos campos da Biologia,
em especial em idéias evolucionistas e na Genética. Esta Seção foca nesses conceitos e
38 3.1. Base Biológica
resume a termino logia empregad a na definição de AEs.
3.1.1 O Processo Evolutivo
Conforme dito anteriormente, os AEs baseiam-se nos processos evolutivos que ocor-
rem n a natureza. Como principais componentes dos sistemas evolutivos têm-se (Arciszewski
e Jong , 2001):
• Populações de indivíduos: uma ou mais populações concorrem por recursos limi-
tados;
• Fitness: reflete a habilidad e de um indivíduo para sobreviver ou reproduzir-se;
• A noção de mudanças dinâmicas nas popu lações devido ao nascimento e morte
dos indivíduos;
• Os conceitos de variabilidade e hereditariedade, ou seja, os novos indivíduos pos-
suem muitas das características de seus pais, embora não sejam idênticos.
Tais conceitos foram inspirados no neodarwinismo (Ridley, 1996), que admite que
os principais fatores evolutivos são a mutação, a recombinação e a seleção natural,
os qu ais são resumidos a seguir:
• Mutação Gênica
A origem da variabilidade é a mutação, processo pelo qual o gene
1
sofre alterações
em sua estrutura. Tais alterações são modificações na sequência de bases do DNA.
Essa molécula, quando duplicada, produz cópias idênticas de si, ou seja, diferentes
da original (sem mutação), transmitindo hereditariamente a mudança . Isso pode
acarretar a alteração da sequência de aminoácidos da proteína, mo dific and o o
metabolismo celular, podendo favorecer o organismo ou mesmo ser letal.
• Recombinação Gênica
O processo evolu tivo seria relativamente lento se não fosse possível colocar juntas,
em um mesmo indivíduo, mutações ocorridas em indivíduos da geração anterior.
1
Gene é um segmento de DNA que contém uma informação codificada para determinada carac-
terística ou processo que a célula tem ou executa (Amabis e Martho, 1985).
3.1. Base Biológica 39
O fenômeno que possibilita esse evento é a reprodução sexuada. É importante
considerar que a seleção natural não atua aceitando ou rejeitando mudanças in-
dividuais, mas sim escolhendo as melhores co mbinaçõ es gênicas entre todas as
variações presentes na população.
• Seleção Natural
A seleçã o natura l é consequência de dois fatores:
1. Os membros de uma espécie diferem entre si;
2. A espécie produz descendência em maior número de indivíduos que de fato
podem sobreviver.
Os indivíduos mais aptos a sobreviver são aqueles que, graças à variabilidade
genética, herdaram a combinação gênica mais adaptada para determinadas condições
naturais.
3.1.2 Terminologia Básica
Apresenta -se, a seguir, a terminologia necessária para o estudo de AEs (Sait e
Youssef, 1999).
Cromossomo, Genes e Alelos
A estrutura que codifica como os organismos são construídos é chamada cromos-
somo. Os cromossomos associam-se de modo a formar um organismo e seu número
varia de uma espécie para outra (Amabis e Martho, 1985). O conjunto completo de
cromossomos de um ser vivo é chamado genótipo e as características do organismo
gerado com base no genótipo constituem o fenótipo. De forma similar, a represen-
tação de soluções de um problema podem ser codificadas em uma estrutura da dados
cha mada cromossomo.
Os cromossomos são codificados em um conjunto de símbolos chamados genes.
Os diferentes valores de um gen e são chamados alelos. A posição do gene em u m
cromossomo é d eno minad a locus (Lamont e Veldhuizen, 2002).
A representação das soluções candidatas ( ou seja, os indivíduo s) é o primeiro estágio
40 3.1. Base Biológica
da elaboração de um AE e é cru cial para o desempenho do algoritmo. Essa etapa consiste
em defin ir o genótipo e a forma como este é mapeado no fenótipo .
A codificação mais simples é a representação binária: o ge nótipo é definido como
um arranjo de 0s e 1s. É necessário definir o tamanho do arranjo, bem como o ma-
peamento genótipo-fenótipo. Entretanto, em muitas aplicações do mundo real, a rep-
resenta ção binária pode apresentar fraco poder de expressão (Deb, 2001), não sendo
eficiente na representação das possíveis soluções. Uma alternativa empregada é a rep-
resentação em ponto-flutuante ou representação oral, segundo a qual as soluções
são arranjos de números reais. Essa representação é usualmente empregada quando os
genes são distribuídos em um intervalo contínuo, em vez de um conjunto de valores
discretos (An drew, 2004) .
Fitness
O valor de fitness de um indivíduo (seja um genótipo ou um cromossomo) é um
núme ro positivo que mede o quanto adequado é o indivíduo, que representa uma
solução. Em problemas de otimização, o fitness pode ser o custo da solução. Se o
problema for de minimizaçã o, as soluções de maior fitness são as de menor custo.
Pais, Operadores de Reprodução e Descendentes
Os AEs trabalham sobre um ou mais cromossomos a fim de gerar novas soluções,
cha mada s descendentes. Os operadores que traba lham sobre cromossomos, chamados
operadores de reprodução, são a recombinação (também conhecido como crossover)
e a mutação. Esses operadores fazem analogia aos principais mecan ismos da evolução
natural, ou seja, a recombinação e a mutação gênica . A recombinação é aplicada,
em geral, a um par de cromossomos. Os indivíduos selecionados para o proce sso de
recombinação são chamados pais. A mutação é aplicada a um simples cromossomo,
modificando-o aleatoriamente.
Geração e Seleção
A geração é uma iteração do AE, na qual os indivíduos da população atual são
selecionados e recombinados e/ou mutados, gerando descend entes. Devido à criação
3.2. Algoritmos Evolutivos 41
de novos descendentes, o tamanho da população cresce; deste modo um mecanismo de
seleção controla esse tamanho.
A ideia básica da seleção é a seguinte: seja uma população de tamanh o M e seja N
d
o número de descendentes, então, para a próxima geração, são selecionados M novos
indivíduos (N
d
pode ser maior que M ). Cada AE desenvolve, com base nesse princípio,
uma estratégia de seleç ão.
3.2 Algoritmos Evolutivos
Os AEs funcionam basicame nte da seguinte forma:
1. Primeiramente é criada uma população inicial com soluções aleatórias;
2. A partir da pop ulaç ão atual, é gerada uma nova população. Os novos indivíduos
desta nova população, são criados a través do uso dos oper ado res genéticos. Esta
tarefa é realizada aplicando-se o operador de cruzamento nos indivíduos com o
melhor fitness, que são escolhid os através de um processo chamado de seleção;
3. Retornar para o item 2 até atender à condição de parada;
O Algo ritmo 1 mostra o pseudocódigo d e um AE.
Os AEs são utilizados para proble mas de o timizaç ão em de corrê ncia de ser o método
preferencialmente utilizado pela natureza, que é considerada por muitos como o sistema
mais perfeito. Além disso, resolvem problemas com modelos matemáticos complexos de
modo simples, sendo de fácil acoplamento com outras técnicas (hib ridação)(dos Santos,
2004).
Existem várias subáreas na Computação Evolutiva, das quais destacam-se:
Algoritmos Genéticos (AG)
Tais algo ritmos foram propostos por Holland na década de 1970 e trabalham com
populações d e indivíduos (cromossomos), que durante o processo de evolução são sub-
metidos aos procedimentos de seleção e reprodução. Deste modo o algoritmo consegue
aproveitar das melhores soluções e ao mesmo tempo explorar o espaço de busca.
42 3.2. Algoritmos Evolutivos
Algoritmo 1 Algoritmo Evolutivo.
1: //Inicia o contador de tempo
2: g ← 1
3: IniciaPopulação(P
g
)
4: //Avalia o fitness dos indivíduos P
g
5: Avalia(P
g
)
6: //Verifica o critério de parada
7: while critério de parada não é atingido do
8: //Incrementa a geração
9: g ← g + 1
10: //Seleciona os in divídu os para a geração dos descendentes
11: P
g
← Seleciona(P
g−1
)
12: //Realiza o cru zamento dos pais selecionados
13: Cruzamento(P
g
)
14: //Realiza a mutação sobre a nova população
15: Muta(P
g
)
16: //Avalia o fitness dos indivíduos P
g
17: Avalia(P
g
)
18: end while
Programação Evolutiva (PE)
Foi proposta por Lawrence J. Fogel na década de 1960, originalmente como uma
estratégia de otimização estocástica similar aos AGs. No entanto, enfatiza o relaciona-
mento entre os progenitor es e seus descendentes aos invés de tentar emular operadores
genéticos e spe cíficos observados na natureza (Castro, 2001).
A PE também opera com populações, mas apenas diferentes níveis de mutação são
efetuados sobre os progenitores na criação de novas soluções. O tamanho da população
não necessita ser mantido constante, como também não é necessário um número fixo de
descendentes p or progen itor. A PE trabalh a com representações mais flexíveis que as
empregadas pelos AGs por não efetua rem recombinaçõ es.
Programação Genética (PG)
A Programação Genética (PG) foi proposta e m (Koza, 1989) e pode ser visa como
uma extensão dos AGs. A PG difere dos AEs devido a sua representação, seus op-
eradores de reprodução e seus métodos de avaliação do fitness. Introduzida a para
solucionar os problemas de aprendizado de máquina, a PG busca a construçã o au-
tomática de progra mas de computadores. Os indivíduos são codificados na forma de
3.2. Algoritmos Evolutivos 43
árvor es, onde cada nó folha contém constantes, variáveis ou parâmetros para a execução
de procedimentos e funções. Os nós internos contém operações primária s.
Os operadores de reprodução utilizados são operadores de r ecombinação e mutação
específicos para representações por árvores. Na recombinação, partes das árvores são
trocadas, o ponto de corte na árvore é escolhido de forma a evitar a criaçã o de operações
inválidas. Na mutação, o valor de um nó ou subárvore é alterado. Se o nó escolhido
para a mutação for um nó interno, este será alterado para ter uma nova operação ou
função. No caso de mutação de subárvore, a subárvore selecionada é substituída por
uma nova subárvore gerada aleatoriamente.
O processo de avaliação ocorre por meio da execução do programa representado
pela árvore do indivíduo. Se este resolver o problema prop o sto ou se aproximar da
resposta correta, te rá um valor de fitness elevado; caso contrário, seu fitness será baixo.
Geralmente, os algoritmos de PG utilizam somente o operador de recombinaç ão no
processo de busca pelas melhores soluções.
Estratégias Evolutivas (EE)
Propostas originalmente para tratarem problemas técnicos de otimização como al-
ternativa aos métodos convencionais. Operam co m cromossomos na forma de vetores
de números reais e or igina lmente na proporção (1 + 1), isto é, cada progenitor gera um
herdeiro por geração, normalmente por mutações distribuídas. Caso esse descendente
seja melhor que seu progenitor, ele lhe toma o lugar. Essas estratégias foram estendidas
para as proporções (m + 1), isto é, m progenitores geram um herdeiro por geração, e
(m+n), isto é, m progenitores geram n herdeiros por geração. As EE tiveram estratégias
de recombinações introduzid as no seu processo evolutivo (Castro, 2001).
3.2.1 AEs de Última Geração
Nos últimos dez anos vários estudos ut ilizan do modelos probabilísticos para as pop-
ulações em AEs foram desenvolvidos buscando aumentar o desempenho de algoritmos
de busca populacionais (ou baseados em populações). O sucesso dessas novas técnicas
para uma diversidade de problemas complexos e de larga-escala, que ainda não eram
resolvidos satisfatóriamente pelos AEs da primeira geração, fez esses novos algoritmos
44 3.3. Operadores Genéticos
merecerem uma nova classificação para distingui-los dos AEs convencionais da primeira
geração (Goldberg, 1989). Esse novos AEs na literatura também têm sido chamados
Algoritmos de Estimação de Distribuição. Dentre esses destacam-se: ECGA (Harik
et al., 20 06) , BOA (Pelikan et al., 2000) e h-BOA (Pelikan, 2005).
3.3 Operadores Genéticos
Nesta Seção são abordados os principais aspectos dos operadores genéticos utilizados
nos AEs.
3.3.1 Seleção
O objetivo deste operador é escolher um ou mais indivíduos para gerar um ou mais
descendentes para a próxima população do processo evolutivo. Os indivíduos com o
melhor gra u de fitness têm uma maior probabilidade de serem escolhidos nesta etapa.
Existe, na literatura, uma grande variedade de estratégias de seleção. Porém, as
mais u tilizad as são a seleção por torneio, roda da roleta e ranking.
Na seleção por torneio, são realizadas várias competições entre d uas ou mais
soluções, e a melho r solução é a escolhida. Na roda da roleta, geralmente, os pais são
selecionados com probabilidade pro porcional aos seus fitness. Para tal seleção usa-se a
expressão 3 .1 (Michalewicz, 1992).
P
i
=
F
i
N
i=1
(F
i
)
(3.1)
onde, F
i
é o fitness da solução i e N é o tamanho da população. Logo, é gerado
um valor aleatório k, no intervalo de 0 a P T OT AL (Soma de tod os os valores de
fitness). Finalmente, o indivíduo selecionado é o primeiro que possui uma probabilidade
de seleção maior que k. Na seleção por ranking, são ordenadas as soluções de acordo
com o seu valor de fitness (sendo o ranking 1 pertencente a p ior solução e o ranking N
pertencente a melhor solução, N sendo o número de soluções). Com isso, determina-se
a probabilidade de seleção para cada solução. Logo, a escolha das soluções progen itora s
é refere nte ao valor do ranking.
3.3. Operadores Genéticos 45
3.3.2 Cruzamento
O operador de cruzamento gera as soluções descendentes das soluções progenitoras.
Basicament e, para cada duas das soluções progenitoras selecionadas corta-se o seu vetor
de símbolos em uma posição aleatória, produzindo duas cabeças e duas caudas. Em
seguida as caudas são trocadas, ge ran do dois novos indivíduos (Figura 3.1).
Figura 3 .1: Exe mplo da aplicaçã o do operador de cruzamento em um ponto.
Existem diversas variações desse operador, vários deles são específicos para deter-
minado problema (Goldberg, 1989).
3.3.3 Mutação
Este operador gera uma determinada taxa de “perturbação” em um determinado
núme ro de soluções, isto é, gera pequenas alterações em um determinado número de
soluções, com o objetivo de explorar o espaço de busca (Figura 3.2) e manter a d i-
versidad e das soluçõ es. Deste forma, o AE tende a não ter uma convergência rápida,
evitando a sua estabilização em regiões chamadas de mínimos locais, nos quais os AEs
sempre estão sujeitos a cair.
Figura 3 .2: Exe mplo da aplicaçã o do operador de mutação.
46 3.3. Operadores Genéticos
3.3.4 Elitismo
Existe um grande risco de perder os melhores indivíduos na transição de uma geração
para outra, isto devido à aplicação dos operadores de mutação e cruzamento. Desse
modo, o objetivo do operador de elitismo é preservar os melhores indivíduos para as
próxima s gerações que possam surgir, sem que esses sofram alguma alteração. Assim,
as melh ore s soluções não se deterioram.
47
Capítulo 4
Algoritmos Evolutivos para
Otimização Multi-Objetivo
Este Capítulo introduz os principais aspectos da otimização multi-objetivo e algu-
mas das p rinc ipais técnicas de Algoritmos Evolutivos Multi-Objetivo (MOEA, do inglês
Multi-Objective Evolutionary Algorithm).
Para escrever este Capítulo utilizou-se (Ticona e Delbem, 2008) como referência
principal.
4.1 Otimização Multi-Objetivo
Esta seção introduz as noção básicas de Otimização Multi-objetivo ( MOO, do inglês
Multi-Objective Optimization). Na Seção 4.1.1 são apresentados os principais conceit os
da área. Na Seção 4.1.2 são definidas as metas em MOO. Na Seção 4.1.3 são explicadas
as principais diferenças entre MOO e otimização mono-objetivo (objetivo simples). Na
Seção 4.1.4 são a presentadas as principais técnicas convencionais para resolver MOO.
4.1.1 Problemas de Otimização Multi-Objetivo
Um Problema de Otimiz ação Multi-Objetivo (MOOP, do inglês Multi-Objective Op-
timization Problem) possui um conjunto de funções objetivo a serem otimizadas (max-
imizar ou minimizar). Além disso, possui restrições que devem ser satisfeitas para que
uma solução seja factível ao problema. O enunciado geral de um MOOP é o seguinte
48 4.1. Otimização Multi-Objetivo
(Deb, 20 01) :
Maximizar/Minimizar f
m
(x), m = 1, 2, .., N
obj
;
sujeito a: g
j
(x) ≤ 0, j = 1, 2, ..., NR
des
;
h
k
(x) = 0, k = 1, 2, .., NR
igu
;
x
(inf)
i
≤ x
i
≤ x
(sup)
i
, i = 1, 2, .., N
var
(4.1)
onde x é um vetor de N
var
variáveis de decisão, x = (x
1
, x
2
, ..., x
N
var
)
T
, também denom-
inado de solução. Os valores x
(inf)
i
e x
(sup)
i
representam os limite s inferior e superior,
respectivamente, para a variável x
i
. Esses limite s definem o espaço de variáveis de
decisão ou espaço de decisão S
dec
. As NR
des
desigualdades (g
j
) e as NR
igu
igual-
dades (h
k
) são chamadas de funções de restrição. Uma solução x factível satisfaz as
NR
igu
+ NR
des
funções de restrição e os 2N
var
limites. Caso contrário, a solução não
será factível. O conjunto de todas as soluções factíveis formam a região factível ou
espaço de busca S
fact
.
Cada função f
m
(x) pode ser maximizada ou minimizada. Porém, para trabal-
har com os algoritmos de otimização, é necessário converter todas as funções para
serem apenas de maximização ou minimização. O vetor de funções objetivo f(x) =
[f
1
(x), f
2
(x), ..., f
N
obj
(x)] compõe um e spaço multidimensional chamado espaço de ob-
jetivos S
obj
. Para cada solução x no espaço de decisão, existe um f(x) em S
obj
. Esta é
uma diferença fundamental em re laçã o à otimização de objetivos simples, cujo espa ço de
objetivos é unidimensional. O mapeamento ocorre então entre um vetor x (de dimensão
N
var
) e um vetor f(x) (de dimensão N
obj
). Por exemplo, se cada elemento de x e f (x)
são números reais, então f(x) estaria mapeada como f(x) : ℜ
N
var
→ ℜ
N
obj
.
Solução Pareto-Ót imas
As funções objetivo empregadas nos MOOPs são em geral conflitantes entre si.
Uma função objetivo f
1
é conflitante com uma outra função f
2
quando não é possível
melhorar o valor de f
1
sem piorar o valor da função f
2
. Um exemplo prático de objetivos
conflitantes são preço e desempenho na compra de equipamentos, como por exemplo,
computadores. Os equipamentos de maior custo apresentam usualmente um melhor
4.1. Otimização Multi-Objetivo 49
desempenho e vice-ve rsa. Assim, em uma compra devem ser considerados vários modelos
de compu tad ores com diversos valores nos objetivos de preço e desempenho. Se ambos
os objetivo s p ossuem a mesma importância (ou prioridade), não há como afirmar, por
exemplo, que ce rta redu ção do preço compensa determinada perda do desempenho.
Em um MOOP, emprega-se o conceito de dominânca de Pareto para comparar
duas soluções factíveis de um problema. Dadas duas soluções x e y, diz-se que x domina
y (denotado como x ≺
y) se as seguintes condição forem satisfeitas:
1. A solução x é pelo menos igual a y em todas as funções objetivo;
2. A solução x é superior a y em pelo menos uma função objetivo.
Desta forma, existe um conjunto de soluções que possuem vantagens em desempenho
mas que não são melhores em custo e vice-versa. Ou seja, existe um conjunto de alterna-
tivas ótimas que são não dominadas entre si nos objetivos de custo e desempenho. Em
um MOOP, o conjunto de soluções não dominadas é chamado de conjunto Pareto-
ótimo, que representa as soluções ótimas do problema. A fronteira de Pareto é o
conjunto dos valores das funções objetivo das soluções do conjunto Pareto-ótimo. A
figura 4.1 ilustra: os valores de preço e desempenho (de 0 a 10 0) para cinco alterna-
tivas para o exemplo de compra de computadores; as relações de dominância entre as
soluções; o conjunto Pareto-Ótimo; e a fronteira de Pareto.
De a cord o com as 5 alternativas de compra, indicadas na Figura 4.1, temos:
• Relação de dominância: 3 ≺
2, 5 ≺ 1, 5 ≺ 2;
• Conjunto de Pareto-ótimo: {3, 4, 5};
• Fronteira de Pareto: in dica da na figura 4.1.
Dominância de Pareto: Definição e Propriedades
Nesta seção serão apresentados, de forma mais formal, os conceitos descritos ante-
riormente.
Definição 4.1.1 Uma solução x domina uma solução y ( x ≺
y) se as seguintes
condições são satisfeitas:
50 4.1. Otimização Multi-Objetivo
Figura 4.1: Exemplo que ilustra o preço e o desempenho para 5 alternativas de compra
de co mput ado res.
1. A solução x não é pior que y em nenhum dos N
obj
, ou seja, f
m
(x) ≤ f
m
(y) para
todo m = 1, 2, ..., N
obj
;
2. A solução x é estritamente melhor que y pelo menos em um objetivo, ou seja,
f
m
(x) < f
m
(y) pelo menos para um valor de m.
Vale ressaltar que a definição 4 .1.1 é aplicada em um MOOP onde as funções objetivo
devem ser minimizadas. Se ambas as condições desta definição são satisfeitas, pode-se
dizer que:
1. y é dominada por x;
2. x não é dominada por y;
3. x não é inferior que y.
Na figura 4.1 temos que a solução 5 domina a solução 1 (5 ≺
1), e a solução 3 domina
a soluçã o 2 (3 ≺
2).
A rela ção de dominância satisfaz as seguintes propriedades:
1. Não é reflexiva. Conforme a definição 4.1.1, uma solução não pode ser dominada
por si mesma;
4.1. Otimização Multi-Objetivo 51
2. Não é simétrica, ou seja, x ≺ y não implica que y ≺ x;
3. É transitiva, isto é, se x ≺
y e y ≺ z então x ≺ z.
Essas propriedades caracterizam a relação de dominância como uma relação de or-
dem parcial estrita (Deb, 2001). Um con junto de soluções para um MOOP, pode ser
dividido em um conjunto de soluções do minad as e não- domin ada s empregando o oper-
ador de d ominâ ncia .
Definição 4.1.2 Dado um conjunto de soluções P, o conjunto de soluções não-dominados
P
′
é formado por:
P
′
= {x ∈ P e y ∈ P|∃y : y≺
x}. (4.2)
Quando um conjunto de soluções P corresponde ao conjunto de soluções factíveis de
um MOOP (P = S
fact
), o conjunto não-dominado P
′
é chamado de conjunto Pareto-
ótimo. Utiliza-se também em MOOP o conceito de otimalidade local. Um conjunto
Paret o-ótimo local é definido conforme segue:
Definição 4.1.3 Dado um conjunto de soluções P e ǫ, um número positivo arbitraria-
mente pequeno, o conjunto Pareto-ótimo local P
′′
é formado por:
P
′′
= {x ∈ P e y ∈ P|∃y : y ≺ x ∧ y − x
∞
≤ ǫ} (4.3)
A Figura 4.2 ilustra dois conjuntos Pareto-ótimos que são não-dominados local-
mente , mostrando a sua vizinhança no seu espaço de objetivos e no espaço de variáveis.
Finalmente, a fronteira de Pareto de um MOOP pode ser definida:
Definição 4.1.4 Dado um MOOP com f
m
, m = 1, 2, ..., N
obj
funções objetivo, e cujo
conjunto Pa reto-ótimo é P
′
, a fronteira de Pareto PF é formada por:
PF = {f(x)|x ∈ P
′
}, (4.4)
onde f(x) = [f
1
(x), f
2
(x), ..., f
N
obj
(x)] é o vetor de funções objetivo para a solução x
52 4.1. Otimização Multi-Objetivo
Figura 4 .2: Solu ções de Pareto-ótimas locais e global.
4.1.2 Metas em Otimização Multi-Obj etivo
Em (Deb, 2001) são destacadas três impo rtantes metas em otimização multi-objetivo:
1. Encontrar um conjunto de soluções que esteja o mais próximo possível da fronteira
de Pareto;
2. Encontrar um conjunto de soluções com a maior diversidade possível;
3. Realizar as duas metas anteriores com a maior eficiência computacional possível.
A primeira meta é comum a qualquer processo de otimização. Soluçõ es muito dis-
tant es da fronteira de Pareto não são desejáveis. Por outro lado, encontrar a maior
diversida de dentro das soluções é a meta específica para otimização multi-objetivo. A
figura 4.3a ilustra uma distribuição quase uniforme das soluções na fro nteira de Pareto.
A figura 4.3b ilustra a fronteira com soluções apenas em algumas regiões, isto é, com
baixa diversidade. É necessário assegurar a maior cobertura possível da fronteira.
Figura 4.3: Diferentes distribuições de soluções na fronteira de Pareto.
4.1. Otimização Multi-Objetivo 53
Como em MOOP trabalha-se com o espaço de decisões e o espaço de objetivos, é
também desejável que as soluções estejam adequadamente distribuídas em ambos os
espaços. Em geral, a diversidade em um desses espaços garante também a diversi-
dade no outro. Entretanto, para alguns problemas isso não acontece. Tendo em vista
que encontrar um conjunto de soluções uniformemente distribuído é uma tarefa que
pode consumir consideráveis recursos computacionais (Deb, 2001), é necessário que tais
soluções sejam obtidas eficientemente.
4.1.3 Diferenças entre Otimização Multi-Objetivo e a Otimização Mono-
Objetivo
Em Deb (2001) identificam-se três importantes aspectos que difere ncia m a otimiza-
ção multi-objetivo e a otimização mono-objetivo, estes sendo:
1. Em problemas de otimiza ção com um único objetivo (otimização mono-objetivo),
a meta é encontrar uma solução ótima global. Se a função objetivo de sses proble-
mas for multimodal, poderia existir mais de um ótimo global. Neste caso, todos
os ótimos são equivalentes. Por outro lado, em MOOP, determinar um conjunto
de soluções da fronteira de Pareto é tão importante quanto preservar a diversi-
dade neste conjunto. Um algoritmo eficiente para otimização multi-objetivo deve
considerar ambo s os aspect os;
2. Um MOOP trabalha com dois espaços, das variáveis e dos objetivos. Por outro
lado, problemas de objetivo simples trabalham unicamente no espaço de variáveis,
pois procuram apenas uma solução no espaço de objetivos. Manter a diversidade
em ambos espaços complica mais o problema, dado que a proximidade de duas
soluções no espaço de variáveis não implica proximidade no espaço de objetivos;
3. Os métodos tradicionais de otimização multi-objetivo reduzem o conjunto de
funções objetivo a uma função simples que pondera cada objetivo. Estes métodos
podem também tratar cada objetivo separadamente, utilizando os d emais obje-
tivos como restrições. Portanto, um MOOP pode ser convertido, por meio de
algumas t écnic as, em um problema de otimização simples.
54 4.1. Otimização Multi-Objetivo
4.1.4 Técnicas Tradicionais para MOOP
Nesta seção serão descritas as principais técnicas clássicas usadas em MOOP: so-
matório de pesos, métodos de restrições ǫ e programação por metas.
Somatório de pesos
O método de somatório de pesos consiste em criar uma função objetivo somando
cada objetivo multiplicado por um peso (Deb, 2001). Os pesos são fornecidos como
parâmetros. A escolha dos pesos é um problema importante que depende da relevância
de cada objetivo. É necessário realizar a normalização de cada função objetivo dado
que os diferentes objetivos podem ter diferentes magnitudes. Por exemplo, o preço de
um carro pode variar de R$4.000 a R $30.0 00; enquanto o conforto pode estar entre 0%
e 100 %.
Uma vez que os objetivos estejam normalizados, pode-se formular uma função F (x)
que soma os objetivos normalizados e multiplicados por seus respectivos pesos. Assim,
um MOOP pode ser formulado como segue:
Minimizar F(x) =
N
obj
m=1
w
m
f
m
(x),
sujeito a: g
j
(x) ≤ 0, j = 1, 2, ..., NR
des
;
h
k
(x) = 0, k = 1, 2, .., NR
igu
;
x
(inf)
i
≤ x
i
≤ x
(sup)
i
, i = 1, 2, .., N
var
(4.5)
onde w
m
∈ [0, 1] é o peso para cada função objetivo f
m
. Pode-se mostrar que a solução
do problema na Equação 4.5 pertence ao conjunto Pareto-ótimo se os pesos são po sitivos
para todo os objetivos. Além disso, pode-se garantir que se um MOO P é convexo
(Deb, 2001), qualquer solução Pareto-ótima pode ser encontrada usando o método de
somatório do s pe sos, empregan do diferentes combinações de valores de w
m
.
Seja um MOOP com dois objetivos. O espaço de objetivos e a Fronteira de Pareto
são mostrados na Figura 4.4. Tem-se um vetor de pesos w = (w
1
, w
2
) para cada objetivo.
Dado um vetor de pesos w é possível plotar o contorno de F no espaço de objetivos.
Dado que F é uma combinação linear dos objet ivos, obtém-se uma linha reta. Encontrar
o mínimo valor da equação 4.5 é equivalente a achar uma linha de contorno com um
4.1. Otimização Multi-Objetivo 55
Figura 4 .4: O método do somatório de pesos.
valor mínimo para F .
A Figura 4.4 mostra várias linhas de contorno para F , sendo que a linha d é tan-
gencial a um pondo do espaço de objetivos (A). Esse ponto encontra-se na Fronteira de
Paret o e, consequentemente, é uma solução Pareto-ótima. Modifican do os valores para
w
1
e w
2
encontra-se uma outra solução Pareto-ótima.
Embora esse método seja simples, precisa de várias iterações para atingir toda a
fronte ira de Pareto. No caso de um MOOP não convexo, este método não é capaz
de determinar todas as soluções. Além disso, a aplicação de vetor de pesos uniforme-
mente distribuídos não garante que seja obtido um conjunt o de soluções uniformemente
distribuídas.
Método de restrições ǫ
Haimes et al. (1971) sugeriram uma reformulação de MOOPs considerando qualquer
objetivo, mantendo restritos os d emais objetivos com valores definidos pelo usuá rio. A
formulaç ão adotada é descrita a seguir:
56 4.1. Otimização Multi-Objetivo
Minimizar f
u
(x), m = 1, 2, .., N
obj
;
sujeito a: f
m
(x) ≤ ǫ
m
, m = 1, 2, .., N
obj
e m = u;
g
j
(x) ≤ 0, j = 1, 2, ..., NR
des
;
h
k
(x) = 0, k = 1, 2, .., NR
igu
;
x
(inf)
i
≤ x
i
≤ x
(sup)
i
, i = 1, 2, .., N
var
(4.6)
onde cada ǫ
m
representa um limite máximo para o valor de f
m
. Por exemplo, para
um MOOP não convexo de dois objetivos f
1
e f
2
, escolhe-se f
2
para ser minimizado e
manté m-se f
1
com a re strição f
1
< ǫ
1
.
Figura 4 .5: Mét odo de restrições ǫ (Deb, 2001).
A Figura 4.5 apresenta o espaço de objetivos e vários valores para ǫ
1
. O mínimo
para f
2
depende d a escolha do ǫ. Por exemplo, usando ǫ
c
1
, o valor mínimo para f
2
é o
ponto C. Então, empregand o valores diferentes de ǫ, encontram-se diferentes soluções
Paret o-ótima s.
Desta forma, o método de restrições ǫ pode ser usado para gerar soluções Pareto-
ótimas independentemente de o espaço de objetivos ser convexo, não convexo ou discreto
(Deb, 2001). Esse método precisa que a escolha do vetor ǫ esteja em uma região factível
para cada objetivo. Por exemplo, na Figura 4.5, se for escolhido ǫ
a
1
, nenhuma solução
será obtida. Assim, como no somatório de pesos, são necessárias várias iterações para
determinar a fronteira de Pareto e o uso de uma distribuição uniforme de ǫ não garante
um con junto de soluções com a mesma distribuição.
4.1. Otimização Multi-Objetivo 57
Programação por metas
Esta técnica tenta encontrar soluções que possam atingir uma meta pré-determinada
para uma ou mais funções objetivo. Caso não exista uma solução factível que alcance
as met as para tod os os objetivos, esta minimiza os desvios em relação às metas.
Considere uma função f(x) para ser minimizada dentro do espaço de busca S
fact
.
Para cada objetivo é escolhido, pelo usuário, um valor meta z. Então, o problema é
formulad o para encontrar uma solução cujo valor em f seja igual a z.
Para resolver um problema de p rog ramaçã o por metas, cada meta é conve rtida em
uma restrição de igualdade. Busca-se então minimizar todos os desvios em relação às
metas. Existem várias formas de trabalhar com esses problemas, estas descritas a seguir:
• Programação de metas com pesos: pa ra um problema com N
obj
objetivos,
formula-se uma função somando os desvios pa ra cada um dos N
obj
objetivos. A
formulaç ão geral desse problema pode ser descrita da seguinte fo rma:
Minimizar F(x) =
N
obj
m=1
(α
m
φ
m
+ β
m
η
m
),
sujeito a: f(x) − φ
m
+ η
m
= z
m
, m = 1, 2, ..., N
Obj
;
x ∈ S
fact
,
φ
m
, η
m
≥ 0,
(4.7)
onde α
m
e β
m
são os pesos dos desvios positivo e negativo (α
m
e η
m
, respectiva-
mente ) para o j-ésimo objetivo, z
m
é a meta para a função f
m
e S
fact
é o espaço
de decisão factível. As soluções obtidas por este métodos dependem considerav-
elment e da escolha dos valores para α
m
e β
m
. Além disso, segundo (Deb, 2001),
este método possui dificuldades similares ao método do somatório de pesos;
• Programação de metas lexicográficas: aqui metas são organizadas em vários
níveis de prioridade. Resolvem-se sequencialmente vários problemas de progra-
mação de metas. Inicialmente, as metas de primeira ordem de prioridade são
consideradas na formulação do problema. Caso existam múltiplas soluções, as
metas de segunda ordem de prioridade são consideradas formulando outro prob-
58 4.1. Otimização Multi-Objetivo
lema para minimizar apenas os desvios para as metas de segunda ord em. As metas
de primeira ordem de prioridade são usadas como restrições. O processo continua
com os demais níveis de prioridade até que seja enc ontrada uma única solução.
Utilizando esse método, é encontrada frequentemente uma solução Pareto-ótima.
A Figura 4.6 mostra um espaço de objetivos para as funções f
1
e f
2
. Se f
1
é
mais importante, minimiza-se f
1
primeiro e obtém-se as soluções das regiões AB
e CD nas quais f
1
é mínima. Dado que existem múltiplas soluções, minimiza-se
f
2
somente nas regiões AB e CD, encontradas na iteração anterior. A solução é
o ponto D, que corresponde ao mínimo para f
2
. Então, D é a solução para todo
o problema de prog ramaç ão de metas lexicográficas.
Figura 4 .6: Mét odo de progra mação de metas lexicográficas (Deb, 2001).
• Programação de metas min-max: neste método é minimizado o máximo
desvio em rela ção às metas. A formulação adotada é a seguinte:
Minimizar δ,
sujeito a: α
m
φ
m
+ β
m
η
m
≤ δ, m = 1, 2, .., N
obj
;
f
j
(x) − φ
m
+ η
m
= z
m
,
x ∈ S
fact
,
φ
m
, η
m
≤ 0,
(4.8)
onde δ é o desvio máximo para qualquer meta, φ
m
e η
m
são os desvios positivos
e negativos para cada objetivos, α
m
e β
m
representam os pesos para cada desvio.
Este mé todo re quer também a escolha dos pesos α
m
e β
m
.
4.2. Algoritmos Evolutivos para Otimização Multi-Objetivo 59
Vantagens e desvantagens das técnicas tradicionais
A principal vantagem das técnicas tradicionais é que possuem provas de convergên-
cia que garantem encontrar pelo menos uma solu ção Pareto-ótima (Coello et al., 2002).
Todas as técnicas descritas neste Capítulo reduzem o MOOP para um problema de obje-
tivo simples. Cada técnica utiliza uma forma diferente de redução e introduz parâmetros
adicionais. A escolha desses parâmetros afeta diretamente os resultad os o btido s. Cada
vez que os p arâ metros são modificados, é nece ssário resolver um novo problema de
otimização simples. Portanto, para encontrar cada solução Pareto-ótima, precisa-se
solucionar u m prob lema de objetivo simples.
Alguns métodos não garantem soluções ao longo de toda a fronteira de Pareto.
Se esta não é convexa, o método do somatório de pesos não encontra certas soluções,
independentemente dos pesos escolhidos.
Finalmente, todas as técnicas descritas precisam de parâmetros adicionais, tais como
pesos, metas e vetores de restrição. Além disso, a distribuição uniforme desses parâmet-
ros não garante a diversidade das soluções Pareto-ótimas. Porém, existem técnicas
alternativas para tratar MOOPs. Dentre dessas técnicas, destacam-se os AEs que ap-
resenta m vários aspectos positivos que motivam a aplicação dos mesmos.
4.2 Algoritmos Evolutivos para Otimização Multi-Objetivo
Os AEs são promissores para serem empregados em MOOP, em razão de apre-
sentar em as seguintes características: tr aba lham com mais de uma função simultane-
ament e; não precisam de informações adicionais e são capazes de escapar de ótimos
locais. Essa seção apresenta os conceitos envolvidos no desenvolvimento de AEs para
MOOPs.
A primeira implementação de AEs para MOOPs foi proposta por Schaffer (1985).
O modelo sugerido foi denominado VEGA (do inglês Vector Evaluated Genetic Algo-
rithm). Schaffer fez uma modificação no AG convencional para avaliar cada objetivo
separadamente. Cont udo , o método proposto não obtém uma diversidade adequada nas
soluções ao longo da front eira de Pareto.
Goldberg (1989) propôs diversas abordagens para estender a aplicação de AEs para
60 4.2. Algoritmos Evolutivos para Otimização Multi-Objetivo
MOOPs. Uma das pro postas utiliza um procedimento para ordenação de soluções
baseado no conceito de dominância. Nesse método, o valor de fitness para uma solução
i é proporcional ao número de soluções que i domina. Desta forma, as soluções não
dominadas são enfatizadas obtendo maior quantidade d e cópia s na lista de reprodução.
Para manter a diversidade das soluções, Goldberg sugeriu o emprego de um método
de compartilhamento (Goldberg, 1989), que permite levar em conta a densida de de
soluções em uma vizinhança no espaço de busca. Assim, soluções que estejam melhor
espalhadas n a fronteira de Pareto têm um melhor valor de compartilhamento.
Uma diversidade de modelos de MOEAs foram propostos baseados nessas idéias
iniciais. A principal diferença dos MOEAs, em relação aos AEs tradicionais, é o operador
de seleção, dado que a comparação entre duas soluções é efetuada com base no conceito
de dominância de Pareto. Em alguns métodos, o valor de fitness é proporcional à
dominância da solução, outros métodos u tilizam apenas a dominância de Pareto e n ão
calculam o valor de fitness com base no nível de dominância. Em ( Coello et al., 2002)
apresentam-se três grandes vantagens da aplicação dos MOEAs para MOOP com relação
às té cnic as tradicionais:
1. Não introduzem parâmetros adicionais no problema;
2. Trabalham diretamente com várias funções usando o conceito de dominância de
Paret o;
3. Um con junto diversificado de soluções pode ser encontrado apenas em uma exe-
cução d o MOEA.
De acor do com Deb (2001), modelos de MOEA são classificados em dois tipos:
1. Não elitistas: modelos que não utiliza m alguma forma de elistismo nas suas
iterações;
2. Elitistas: modelos que empregam alguma forma de elitismo.
A Tabela 4.1 enumera os principais modelos de MOEAs. A seguir será apresentada
o NSGA-II, que é a técnica utilizada neste projeto, por ser uma das técnicas mais
utilizadas na literatura e por apresentar um bom d esempenho qu ando aplicada ao PRE,
conforme pode ser visto em (Kumar et al., 20 08).
4.2. Algoritmos Evolutivos para Otimização Multi-Objetivo 61
Tabela 4.1: Diferentes modelos de MOEAS.
Sigla Autoria Elitista
VEGA(Vector Evaluated Genetic Algorithm) (Schaffer, 1985) Não
WBGA(Weight Based Genetic Algorithm) (Hajela e Lin, 1992) Não
MOGA(Multiple Objective Genetic Algorithm) (Fonseca e Fleming, 1993) Não
NSGA(Non-Dominated Sorting Genetic Algorithm) (Srinivas e Deb, 1994) Não
NPGA(Niched-Pareto Genetic Algorithm) (Horn et al., 1994) Não
PPES(Predator-Prey Evolutionary Strategy) (Laumanns et al., 1998) Não
REMOEA(Rudolph’s Elitist Multi-Objective Evolution-
ary Algorithm)
(Rudolph, 2001) Sim
NSGA-II(Elistist Non-Dominated Sorting Genetic Algo-
rithm)
(Deb et al., 2000; Deb e Sun-
dar, 2006a)
Sim
SPEA, SPEA2(Strenght Pareto Evolutionary Algorithm)
1 e 2
(Zitzler e Thiele, 1999; Zit-
zler et al., 2001)
Sim
TGA(Thermodynamical Genetic Algorithm) (Kita et al., 1996) Sim
PAES(Pareto-Archived Evolutionary Strategy) (Knowles e Corne, 1999) Sim
MOMGA-I, MOMGA-II(Multi-Objective Messy Genetic
Algorithm) I e II
(Van Veldhuizen, 1999) Sim
Micro-GA(Multi-Objective Micro-Genetic Algorithm) (Coello et al., 2002) Sim
PESA-I, PESA-II(Pareto Envelope-Base Selection Algo-
rithm)
(Corne et al., 2000; Corne
et al., 2001)
Sim
ǫ-MOEA(ǫ-dominance Multi-Objective Evolutionary Al-
gorithm)
(Deb et al., 2005) Sim
4.2.1 NSGA-II: Elitist Non-Dominanted Sorting Genetic Algorithm
Proposto por Deb et al. (2000), o algoritmo Elitist Non-Dominanted Sorting Ge-
netic Algorithm (NSGA-II) baseia-se na ordenação eletista por dominância chamada de
Pareto ranking. Esse procedimento consiste em classificar as soluçõ es de um conjunto
M em diversas fronteiras (F
1
, F
2
, ..., F
k
, onde k é o número de fronteiras) conforme o
grau de d ominâ ncia de cada solução. Deste modo, a fronteira F
1
contém as soluções não
dominadas de todo o conjunto de soluções M , F
2
contêm as soluções não dominadas de
M −F
1
, F
3
contêm as soluções não dominadas de M −(F
1
∪F
2
) e assim sucessivamente.
O procedimento de ordenação por não dominância proposto por Deb et al. (2000) é
descrito no algor itmo 2. Para cada solução i, contida em P , são calculados dois valores:
• nd
i
, o número de soluções que dominam a solução i;
• U
i
, o con junto de soluções que são dominadas pela solução i.
As linhas 1-15 do Algoritmo 2 calculam tais valores para as soluções em M. Além
disso, as soluções com nd
i
= 0 estão contidas na fronteira F
1
. Em seguida, as linhas
62 4.2. Algoritmos Evolutivos para Otimização Multi-Objetivo
17-29 percorrem o conjunto de soluções dominadas U
i
para cada solução i em F
1
. O
contador nd
j
, de cada solução j em U
i
, é decrementado em 1. Se nd
j
= 0, então a
solução j pertence à próxima fronteira, neste caso, F
2
. A iteração das linhas 17-29 é
repetida até que todas as soluções estejam classificadas em uma fronteira. A Figura 4.7
ilustra este procedimento aplicado às soluções que minimizam f
1
e f
2
.
Figura 4 .7: Ord ena ção por não dominânc ia (Deb, 2001).
O algoritmo NSGA-II trabalha com duas populações, denotadas por P e Q, ambas
de tamanho N
ind
. As populações P e Q em cada iteração t = 1, 2, ..., N
iter
são denotadas
por P
t
e Q
t
, respectivamente. Na primeira geração, os indivíduos iniciais da população
P
1
geram as soluções em Q
1
, através da aplicação dos operadores g ené ticos. Em seguida,
estabelece-se um processo competitivo para preencher N
ind
vagas para a solução P
t+1
,
entr e 2 ∗ N
ind
indivíduos contido em R
t
= P
t
∪ Q
t
. Esta operação é realizada utilizando
a ordenação por não dominância em R
t
, encaminhando a s soluções não dominadas
contidas nas fronteiras diretamente para a próxima geração (elitismo).
Para garantir a diversidade na fronteira, o NSGA-II emprega uma estimativa de
densidade das soluções que rodeiam cada indivíduo da po pu lação . Assim, calcula-
se a média da distância das duas soluções adjacentes a cada indivíduo para todos os
objetivos. Esse valor é denominado distância de multidão. O Algoritmo 3 descreve os
passos para calcular tal valor, onde crowdist
n
é o valor da distância de multid ão do
n-ésimo indivíduo d o conjunto M (denotado como M
n
) e f
m
(M
n
) é o valor da m-ésima
função objetivo para o n-ésimo indivíduo.
O fitness de cada solução i é determinado pelos seguintes valores:
4.2. Algoritmos Evolutivos para Otimização Multi-Objetivo 63
Algoritmo 2 Ordenação por não-dominância
1: for solução i ∈ M do
2: nd
i
← 0
3: U
i
← φ
4: for solução j = i e j ∈ M do
5: if i ≺ j then
6: U
i
← U
i
∪ {j}
7: end if
8: if j ≺ i then
9: nd
i
← nd
i
+ 1
10: end if
11: end for
12: if nd
i
= 0 then
13: F
1
← F
1
∪ {i}
14: end if
15: end for
16: k ← 1
17: while F
k
= φ do
18: T emp ← φ
19: for solução i ∈ F
k
do
20: for solução j ∈ U
i
do
21: n
j
← n
j
− 1
22: if n
j
= 0 then
23: T emp ← T emp ∪ {j}
24: end if
25: end for
26: end for
27: k ← k + 1
28: F
k
← T emp
29: end while
Algoritmo 3 Cálculo da distância de multidão.
1: for solução n ← 1, 2, ..., |M| do
2: dist
n
← 0
3: end for
4: for m ← 1, 2, ..., N
obj
do
5: Classificar M por f
m
, e m ordem decrescente
6: crowdist
1
← crowdist
|M|
← ∞
7: for n ← 2, ..., |M| − 1 do
8: Classificar M por f
m
, e m ordem decre scente
9: crowdist
n
← crowdist
n
+
f
m
(M
n+1
)−f
m
(M
n−1
)
f
max
m
−f
min
m
10: end for
11: end for
64 4.2. Algoritmos Evolutivos para Otimização Multi-Objetivo
1. rank
i
= k, o valor de ranking i é igual ao número da fronteira F
k
à qual i pertence;
2. crowdist
i
, o valor de distância de multidão de i.
O NSGA-II emprega um processo de seleção por torneio, que é guiado por um
novo operador denominado crowded-comparison operator (≺
c
). Em tal abordagem,
duas soluções são comparadas para escolher qual dela s vai gerar descendentes na nova
população. Uma solução i é escolhida sobre uma solução j se:
1. i possui um ranking menor que j, o u seja, rank
i
< rank
j
;
2. Se ambas as soluções possuem o mesmo ranking e i possui um maior valor de
distância d e multidão, ou seja, rank
i
= rank
j
e corwdist
i
> crowdist
j
.
O cálculo da distância de mutidão permite que as soluções melhores espalhadas
passem a ocupar as útlimas vagas disponíveis de P
t+1
, garantindo a diversidade das
soluções. A população Q
t+1
é gerada utilizando os operadore s de seleção por torneio,
recombinação e mutação em P
t+1
. O NSGA-II continua por N
iter
iterações e as soluções
finais encontram-se em P
N
iter
∪Q
N
iter
. A sequência de passos do pelo NSGA-II é descrita
no Algo ritmo 4. A Figura 4.8 ilustra o esquema para uma iteração do NSGA-II.
Algoritmo 4 NSGA-II.
1: Criar uma população de soluções aleatórias P
1
de N
ind
indivíduos
2: Ordenar P
1
utilizando o algor itmo 2
3: Gerar a população Q
1
de tamanho N
ind
, a plica ndo os operad ores genéticos em P
1
4: for geração t ← 1, 2, ..., N
iter
do
5: Aplicar a lgorit mo 2 em R
t
← P
t
∪ Q
t
6: k ← 1
7: while |P
t+1
+ F
k
| ≤ N
ind
do
8: Aplicar algoritmo 3 em F
k
9: P
t+1
← P
t+1
∪ F
k
10: k ← k + 1
11: end while
12: Aplicar o a lgor itmo 3 em F
k
13: Classificar a fronteira F
k
pelo ranking e a distância usando o operador (≺
c
)
14: Copiar as p rimeiras N
ind
− |P
t+1
| solu ções de F
k
para P
t+1
15: Gerar a n ova população Q
t+1
aplicando o s operadores gen ético s em P
t+1
16: end for
17: P
final
← P
t
18: Q
final
← Q
t
4.2. Algoritmos Evolutivos para Otimização Multi-Objetivo 65
Figura 4 .8: Esque ma do modelo NSGA-II (Deb, 2001).
Complexidade Computacional
A complexidade do NSGA-II, no pior caso, é (Ticona e Delbem, 200 8):
• Na etapa de ordenação por não dominância da população R é necessário comparar
cada uma das 2∗N soluções com 2∗N −1 soluções, para cada um dos M objetivos.
Isto r esulta no total de comparações de ordem O(M ∗ N
2
);
• Na etapa de cálculo da distância de multidão, o pio r caso ocorre quando todas as
soluções da população R estão na fronteira F
1
, logo, é necessário ordenar F
1
para
cada objetivo M , isto resultando na ordem de O(M ∗ N ∗ logN);
• Finalmente, para selecionar as N melhores soluções da fronteira F
1
, para a n ova
população P
t+1
, é utilizado o operador ≺
c
, o que resulta em uma ordem de O(M ∗
N
2
).
Logo, a complexidade de tempo total do algoritmo NSGA-II é O(M ∗ N
2
) (Deb,
2001).
67
Capítulo 5
Estruturas de Dados para AEs
Aplicados a Problemas de Projeto
de Redes
Este capítulo esta organizado da seguinte forma: primeiramente, na Seção 5.1 , são
apresentados os conceitos básicos da teoria de grafos necessários para o entendimento da
estrutura de da dos RNP, que é utilizada neste trabalho para representar computacional-
mente SDRs. Na Seção 5.2 são apresentadas representações de Problemas de Projeto
de Redes (PPRs) pa ra AEs e, na Seção 5.3, é descrita a RNP.
5.1 Principais Conceitos da Teoria de Grafos
Uma diversidade de problemas pode ser representada por meio de diagramas que
consistem em um conjunto de pontos e linhas que conectam alguns desses pontos. Um
exemplo conveniente são as redes elétricas, as quais, basicamente, consistem de um con-
junto de barras e de ramos que as interconectam, onde cada barra pode ser representada
por um ponto, e as conexões entre as mesmas podem ser repre sentadas pelas linhas. A
abstração matemática d e problema s desse tipo dá lugar ao conceito de grafo.
Um grafo G consiste de um conjunto finito N(G) de elementos, chamados nós, e
um conjunto finito E(G) de pares de nós não-ordenados, chamados arestas. Um grafo
é simbolicamente representado por G = (N, E). Se u e v são dois nós de um grafo, e se
68 5.1. Principais Conceitos da Teoria de Grafos
o par u, v é uma aresta denotada por e, diz-se que e conecta u e v, como pode ser visto
na Figu ra 5.1. Neste caso, a aresta u, v é dita incidente ao nó u e ao nó v.
A ordem de um grafo G é dada pelo número de elementos do conjunto finito N(G),
ou seja, pelo número de nós de G. O tamanho de um grafo G é dado pelo seu número
de arestas, isto é, o tamanho N(E).Assim, a ordem do grafo da Figura 5.1 é 4 e seu
tamanho também é 4. O grau de um nó é dad o pelo número de arestas que lhe são
incidentes. A Tabela 5.1 apresenta o grau de cada nó do grafo da Figura 5.1.
Figura 5 .1: Exe mplo de um grafo.
Tabela 5.1: Grau de cada um dos nós do grafo da figura 5.1.
Nó Grau
W 1
U 2
V 2
Z 3
Dado um grafo G, uma seqüência de arestas {s
0
, s
1
}, {s
1
, s
2
},...,{s
m−2
, s
m−1
},
{s
m−1
, s
m
}, em que todas as arestas são distintas, é chamada de caminho, isto é,
um caminho é uma seqüência de nós, tal que de cada um dos nó s exista uma única
aresta distinta para o nó seguinte. Alem disso, se os nós s
0
, s
1
, s
2
,..., s
m−1
e s
m
são
distinto s, nenhum dos nós se repete, e ntão o caminho é chamado de cadeia ou cam-
inho simples. O comprimento do caminho é o número de arestas que o camin ho usa.
Se somente os nós s
0
e s
m
são iguais, o caminh o é chamado de ciclo.
Da Figura 5.1, tem-se:
• Exemplo de um caminho: {w, z}, {z, u} e {u, v};
• Exemplo de uma cadeia: {u, v}, {v, z} e {z, w};
• Exemplo de um ciclo: {u, v}, {v, z} e {z, u};
5.2. Representações de PPRs para AEs 69
Um par de nós de um grafo é um par conexo, se existir um caminho entre esses
nós. Um grafo G é um grafo conexo, se todo par de nós em G é um par conexo.
Diz-se que H é um subgrafo conexo máximo de um grafo G, se um único subgrafo
conexo contendo H é o próprio H. Um subgrafo conexo H máximo também é chamado
de componente. Um grafo G é conexo se o número de seus componentes for igual a
um.
Um grafo acíclico é um grafo sem ciclos. Uma árvore é um grafo acíclico conexo.
Uma floresta é um gr afo formado por um conjunto de árvores. Logo cada componente
de uma floresta é uma árvore. Quando uma floresta tem apenas uma árvore, ela é uma
floresta c one xa. Assim, uma árvore é uma floresta conexa.
Geralmente, ch ama-se um dos nós de uma árvore de nó raiz. Este é tomado como
uma referê ncia e pode ter grau maior ou igual a um. Nós que possuem grau um são
cha mado s de nós terminais, e xceto se for o nó raiz. Uma árvore geradora (spanning
tree) de um grafo G é qualquer subárvore de G que contenha todos os nós de G.
5.2 Representações de PPRs para AEs
Para escrever esta seção utilizou-se (de Lima e Delbem, 2007) como referência .
Nos capítulos anteriores fora m apresentados os AEs como ferramenta poderosa de
otimização inspiradas na teoria da evolução natural. No entando, AEs com codificações
convencionais tem sido ineficientes para Prob lemas de Projeto de Redes (PPRs)(de Lima
e Delbem, 2007), em especial para grandes sistemas. Tais abordagens evolutivas geram
muitos componentes desconexos ou grafos acíclicos quando aplicad os a grandes sistemas,
enquanto que em PPRs geralmente busca-se a produção de árvores (ou florestas) ger-
adoras. Dependendo da codificação adotada, a produção de tais grafos pod e consumir
uma grande parte do tempo de execução, o qual reduz a eficiência dos AEs. Além disso,
as redes produzidas podem ser mu ito diferentes de seus pais, reduzindo demasiadamente
a convergência dos AEs.
Os PPRs envolvem problemas do mundo real das diversas áreas da engenharia e
ciências, tais como circuitos elétricos, roteamento de veículos, redes de computadores e
sistemas d e distribuição de energia elétrica. Com o objetivo de melhorar a eficiência dos
AEs para PPRs, novas codificações têm sido propostas as quais têm produzido aumento
70 5.3. Representação Nó-Profundidade
significativo da eficiência dos AEs. Uma dessas configurações é a Representação Nó-
Profundidade (RNP) (Delbem et al., 2004) que te m como vantagem a capacidade de
trabalhar co m redes correspo nde ndo a florestas.
As estruturas de dados para AEs aplicad as a PPRs devem lidar com representações
de árvores geradoras de grafos (Gross e Yellen, 2004), pois as soluções de PPRs, em
geral, envolvem árvores geradoras de um grafo que representa o problema.
Ao longo dos anos diversas representações de PPRs para AEs. Na Tabela 5.2 são
apresentadas as principais delas, dentre quais destaca-se a RNP, que têm sido aplicada
para o problema de reconfiguração de SDR e apresentado ótimos resultados com uma
redução considerável do tempo de processamento e na quantidade de memória RAM
utilizada (do s Santos, 2008).
Destaca-se que no presente projeto foi utilizada a RNP para mod elar um SDR (ver
Capítulo 7) .
Tabela 5.2: Prin cipa is representações de PPRs para AEs.
Representações de PPRs Referência
Vetor Características (Sinclair, 1995)
Predecessores ou Codificação Determinante (Abuali et al., 1995)
Número de Prüfer (Prüfer, 1918)
Blob Code (Picciotto, 1999)
Tendência de Ligação e Nó (Palmer, 1994)
Chaves Aleatórias para Redes (Rothlauf et al., 2002)
Conjunto de Arestas (Raidl, 2000)
Representação Nó-Profundidade (Delbem et al., 2004)
Precedentes Diretos (Carvalho et al., 2001)
Permutação Baseada em Árvore (Zhou e Gen, 2003)
D-Based (Zhou et al., 2007)
Ajuste Adaptativo das Ligações (SOAK et al., 2005)
Sub-Conjunto de Comprimento Fixo (Julstrom, 1994)
Dandelion Code (Raidl e Julstrom, 2003; Pic-
ciotto, 1999)
Representação Nó-Profundidade e Grau (de Lima e Delbem, 2007)
5.3 Representação Nó-Profundidade
A Representação Nó-Profundidade (RNP), proposta por (Delbem et al., 2004),
baseia-se nos conceitos de nó e profundidade de nó em um grafo acíclico e conexo
(árvo re). Basicamente, a RNP é composta por uma lista line ar c ontendo os nós da
5.3. Representação Nó-Profundidade 71
árvor e, e suas respec tivas profund ida des. Essa lista é formada por pares (n
x
, p
x
), onde
n
x
representa o nó da árvore e p
x
a profundida de do nó. A ordem em que os pare s são
dispostos na lista é importante.
Computacionalmente, esta lista é formada por uma matriz de dimensã o 2 x n, onde
n é o número de nós de uma determinada árvore. De tal forma que, cada par (n
x
, p
x
) é
armazenado em uma determinada co luna da matriz, onde p
x
e n
x
são armazenados na
primeira e na segunda linha respectivamente (Figura 5.2b). Para armazenar um nó e a
sua resp ectiva profundidade na RNP, é utilizada um algoritmo de busca em profundidade
(Cormen, 2002). Desta maneira, começando a busca a partir do nó raiz da árvore, é
produzida uma lista de pares (n
x
, p
x
) em uma sequência ap ropr iada enquanto um nó
n
x
é visitado .
Para o entendimento de como uma árvore é armazenada na RNP, será realiza da
uma análise da Figura 5.2b, que apresenta a RNP para a árvore geradora representada
por linhas espessas no grafo da Figura 5.2a. Inicialmente é armazenado o nó raiz
da árvore, no caso o nó 1, com profundidade igual a 0. Logo, realiza-se uma busca
em profundidade na árvore, através dos ramos conectados ao nó raiz, para armazenar
os demais nós junta mente co m suas respect ivas profundidades, as quais são sempre
calculadas em relação a o nó raiz.
Figura 5 .2: Exe mplo de um grafo e sua RNP
A codificação para uma floresta é composta pela uniã o das codificações de todas
as árvores da mesma. Assim, a estrutura de dados da floresta pode ser facilmente
implementada utilizando uma lista de ponteiros, onde cada ponteiro indica a RNP de
uma árvo re da floresta.
Para facilitar a manipulação da floresta armazenada em RNPs, criaram-se dois op-
72 5.3. Representação Nó-Profundidade
eradores bastante similares, chamados de operador 1 e operador 2 (Delbem et al.,
2004). Ambos os operadores transferem uma sub-árvore (parte podada) de uma árvore
A
de
(árvo re origem) para uma árvore A
para
(árvo re destino). Entretanto, no operador 1
a raiz da sub-árvore podada será a raiz dessa subárvore na nova árvore A
para
; já no
operador 2, um novo nó (diferente da raiz) é escolhido para ser a nova raiz da sub-árvore
em A
para
(Delbem et al., 2004).
O operador 1 requer a definição prévia de dois n ós: o nó de poda p, que indica a
raiz da sub-árvore que será podada; e o nó adjacente a, que é o nó da árvore A
para
,
onde a sub-árvore será inserida. Além desses dois nós, o operador 2 requer ainda o nó
r, que será a nova raiz da sub-árvore que será transferida.
5.3.1 Operador 1
Para descrição do operador 1, considera-se que os nós p e a sejam previamente
escolhidos. A RNP é implementada utilizando-se matrizes, send o conhe cido s os índices
de p(i
p
) e a(i
a
) (Figura 5.3 a) nas matrizes A
de
e A
para
, r espectivamente.
O o perador 1 pode ser descrito a través dos seguintes passos (Figura 5.3):
1. Determinam-se as posições (i
p
, i
l
) dos índices na árvore A
de
, correspondente à
sub-árvore enraizada no nó p. Conhecido i
p
, é necessário encontrar apenas i
l
, que
corresponde ao índice do último nó na sub-árvore que tem o nó p como raiz. O
conjunto (i
p
, i
l
) corresponde ao nó p, em i
p
, e consecutivos nós x na segunda linha
da matriz A
de
, tal que i
x
> i
p
e p
x
> p
p
(ent re as linhas tracejadas na Figura
5.3a), p
x
é a pr ofund idad e do nó x;
2. Copiam-se os dados do conjunto (i
p
, i
l
), da árvore A
de
, em uma matriz temporária
A
tmp
(contendo os dados da sub-árvore que está sendo transferida); ver Figura
5.3b. A profundidade de cada nó x, do conjunto (i
p
, i
l
), é atualizada utilizando a
seguinte equação: p
x
= p
x
− p
p
+ p
a
+ 1, onde: p
x
, p
p
e p
a
são as profundidades
dos nós x, p e a, r espectivamente;
3. Cria-se a matriz A
para
′
, contendo os nós A
para
e inserindo depois a matriz A
tmp
na
posição i
a
+ 1 de A
para
, isto é, gera-se uma nova árvore que conecta a sub-árvore
na á rvore A
para
′
(Figura 5.3c );
5.3. Representação Nó-Profundidade 73
4. Constrói-se uma matriz A
de
′
, qu e po ssua os nós A
de
, sem os nós de A
tmp
;
5. Atualiza-se a floresta, fazendo com que a estrutura de dados que antes apontava
para A
de
e A
para
, a ponte agora para A
de
′
e A
para
′
.
Figura 5 .3: Ilustraçã o dos passos do operado r 1
5.3.2 Operador 2
Para a descrição do operador 2, considera-se que um conjunto de nós seja previa-
mente determinado: o nó de poda p, o novo nó raiz r e o nó adjacente a. Os nós p e r
74 5.3. Representação Nó-Profundidade
pertencem à árvo re A
de
, e o nó a à A
para
;
As diferenças do operador 1 para o 2 estão nos pa ssos 2 e 3 do procedimento do
operador 1 (ver Operador 1), isto é, a formação da sub-árvore cortada e como a mesma
é armazenada em um vetor temporário tmp são diferentes. Os passos 2 e 3, para o
operador 2, são de scritos na sequência. As Figuras 5.4a, 5.4b, 5.4c e 5 .4d ilustram um
exemplo destes passos para as mesmas arvorés A
de
e A
para
utilizadas na aplicação do
operador 1, ilustrado na Figu ra 5.3.
O procedimento da cópia da sub-árvore, para o operador 2, pode ser dividida em
dois passos: o primeiro é similar ao passo 2 do operador 1, com a diferença de que, no
operador 2, troca-se o índice i
p
por i
r
No segundo passo consideram-se os nós de r até p de A
de
, isto é r
0
, r
1
, r
2
,..., r
n
,
onde r
0
= r e r
n
= p, como raízes de sub-árvores (ver os nós destacados na Figura
5.4a). O algoritmo pa ra o segun do passo deve copiar a sub-árvore enraizada em r
i
(i = 1, 2, ..., n), sem a sub-árvore enraizada em r
i−1
(veja Figura 5.4b) e armazena o
resultado das sub-árvores, na matriz temporária A
tmp2
(veja Figura 5.4c). Em seguida
o operador 2 cria a matriz A
para
′
, contendo os nós de A
para
e inserindo depois a matriz
A
tmp2
na posição i
a
+ 1 de A
para
. Ou seja, cria-se uma nova árvore que conecta a
sub-árvore na árvore A
para
′
(ver Figura 5.4d).
5.3. Representação Nó-Profundidade 75
Figura 5 .4: Ilu straçã o dos passos do operador 2.
77
Capítulo 6
Fluxo de Carga
Este Capítulo introduz, de maneira sucinta, alguns dos principais métodos para
cálculo de fluxo de carga usados em SDR. Na Seção 6.1 são apresentadas as consid-
erações iniciais sobre o estudo de fluxo de carga. Na Seção 6.3 é descrito o método
Backward/Forward de soma de correntes. Na Seção 6.3 é descrito o método Back-
ward/Forward de soma de potências.
6.1 Considerações Iniciais
O estudo de fluxo de carga (ou fluxo de p o tên cia) em uma rede de energia elétrica
consiste na obtenção das condições de operação da mesma (tensões complexas nas bar-
ras, fluxos de potência nas linhas e transformadores), em função da topologia da red e e
dos seus n íveis de demanda e geração de potência.
Métodos convencionais para o cálculo de fluxo de carga em redes de transmissão de
energia elétrica, tais como o método de Newton-Raphon, Desacoplado Rápido e versões
modificadas dos mesmos (Monticelli, 1983; Monticelli et al., 1990), podem apresentar um
mal desempenho quando aplicados em redes de distribuição. Principalmente para redes
radiais com grande número de barras. Isso ocorre devido às características particulares
dos SDRs, dentre as quais podemos citar: baixa relação X/R (reatância/resistência) dos
parâmetros dos alimentadores, trechos com impedâncias relativamente baixas
1
associa-
1
Representação de chaves seccionadoras, reguladores de tensão e trechos pequenos de linhas entre
cargas muito próximas.
78 6.1. Considerações Iniciais
dos a trechos com impedância s altas e grande número de ba rras de carga distribuídas.
Em razão dessas características, as matrizes associadas aos SDRs são mal-condicionadas,
dificultando o cálculo de fluxo de carga através dos métodos tradicionais supracitados
(Das et al., 1994), que exigem a fatoração de matrizes, pois, afetam a convergência
daqueles métodos exigindo um grande número de iterações, podendo causar, até mesmo,
diverg ênc ia do processo iterativo.
Face ao exposto, diversos métodos para o cálculo de fluxo de carga para SDRs foram
propostos, os quais são divididos em du as categoria s (Srinivas, 2000):
• Métodos backward/forward;
• Métodos baseados na matriz de impedância nodal implícita.
Os métodos backward/forward são bastante empregados em SDRs(ou fracamente
malhados). A rede, nestes métodos, é representada como um grafo acíclico (árvore),
cujo n ó raiz corresponde à subesta ção (ver Figura 6.1).
Figura 6 .1: Exe mplo de um SDR.
Esses métodos são também conhecidos como métodos de varredura direta/inversa,
devido ao fato de apresentarem um processo iterativo que faz um percurso das barras
extremas em direção à subestação e vice-versa. Nestes métodos, primeiramente realiza-
se a etapa Backward, que partindo das barras extremas (nós folhas) e usando um valor
inicial das tensões nodais, consiste em calcular as corrent es ou fluxos de potência nas
linhas até a subestação (nó raiz). Ap ó s esta etapa, realiza-se a etapa Forward, que
a partir do resultado da injeção de corrente ou potência da subestação , e do valor
conhecido da tensão nessa barra, são calculados novamente os valores de tensão das
6.2. Método Backward/Forward de Soma de Correntes 79
barras da rede, até as barras extremas. Tal procedimento é repetido até que os valores de
tensão de duas iterações consecutivas não variem mais que uma determinada tolerância,
bem próxima a zero (mistake). Este método, a princípio, tem duas versões, sendo estas:
• Soma de Correntes (Shirmohammadi et al., 1988);
• Soma de Potências (Baran e Wu, 1989; Cespedes, 1990).
Os métodos baseados na matriz de impedância nodal implícita baseiam-se na for-
mação e fatoração da matriz de admitância no da l e injeções de corrente equivalentes.
Nesses métodos, o efeito da fonte e das cargas é representado s ep ara damente por super-
posição (Srinivas, 2000; Chen et al., 1991).
6.2 Método Backward/Forward de Soma de Correntes
O método de soma de correntes (Shirmohammadi et al., 1988) foi desenvolvido
inicialmente para SDRs, podendo ser aplicado a sistemas de distribuição fracamente
malhados. Tal método é conceitualmente simples e apresenta desempenho eficiente. O
procedimento para o cálculo de fluxo de carga desse método é composto pelos seguintes
passos:
1. Inicialmente deve-se especificar a tensão do nó raiz e assumir, como estimativa
inicial, tensão igual a 1 (um) p.u. com ângulo de 0 (zero) graus para todas as
demais ba rras do SDR;
2. Cálculo da corrente nodal: na iteração k, a injeção de corre nte nodal
˙
I
(k)
é
calculada segu ndo a expressão:,
˙
I
(k)
i
= (
˙
S
i
/
˙
V
(k−1)
i
)
∗
−
˙
Y
sh
i
˙
V
k−1
i
, i = 1, 2, ..., n, (6.1)
onde
˙
V
(k−1)
i
é a tensão na barra i, calculada durante (k − 1)-ésima iteração;
˙
S
i
é a injeção de potência complexa especificada na barra i;
˙
Y
sh
i
é a soma de todos
os elementos shunt da barra i; e n é o número total de barras da representaçã o
radial do sistema. O símbolo (.)
∗
indica o conjugado do valor complexo entre
parênteses;
80 6.2. Método Backward/Forward de Soma de Correntes
3. Backward: Na iteração k, a partir das linhas c one ctad as às barras extremas d o
grafo (barras com maiores profundidades) e movendo-se até as linhas conectad as
à barra raiz (com profundidade zero), calcula-se a corrente (
˙
F
L
) na linha L, que
liga uma barra L2 à sua barra antecessora L1, conforme ilustrado na Figura 6.2,
da segu inte forma:
˙
F
(k)
L
= −
˙
I
(k)
L2
+
(Corrente nas linhas que saem do nó L2), (6.2)
onde L = p, p − 1, ..., 1,
˙
I
(k)
L2
é a in jeção de corrente no nó L2 e p é o número de
linhas qu e o sistema possui;
4. Forward: as tensões complexas das barras são atualizadas, iniciand o pelas barras
que estão conectadas à barra raiz (subestação) e seguindo até as barras extremas.
Seja L a linha que liga uma barra L2 à sua barra antecessora L1, a tensão de
L2 é calculada usando a atualização da tensão na iteração k de L1 e o fluxo de
corrente na linha calculado no passo 3:
˙
V
(k)
L2
=
˙
V
(k)
L1
−
˙
Z
L
˙
F
(k)
L
, L = 1, 2, ..., p, (6.3)
onde
˙
Z
L
é a impedância série da linha L;
5. Os passos 2, 3 e 4 são repe tidos até que seja alcançado o critério de convergência.
Figura 6 .2: S istema de distribuição radial.
Adota -se como critério de convergência o maior erro de potência ativa e reativa
nas barras do sistema, tal que este erro seja menor que um ǫ. Conforme descrito nos
passos acima, em cada iteração é calculada a injeção de corrente e, posteriormente, as
6.3. Método Backward/Forward da Soma de Potências 81
tensões da s barras do sistema. Assim, a potência complexa injetada na barr a i (ou
a potência complexa líquida na barra i) na iteração k,
˙
S
(k)
i
, é calculada utilizando a
expressão 6 .4.
˙
S
(k)
i
=
˙
V
(k)
i
˙
I
(k)∗
i
−
˙
Y
i
|
˙
V
(k)
i
|
2
, i = 1, 2, ..., n. (6.4)
O e rro de pot ência ativa e reativa na barra i é calculado da seguinte forma:
∆P
(k)
i
= Re[
˙
S
(k)
i
−
˙
S
i
]
∆Q
(k)
i
= Im[
˙
S
(k)
i
−
˙
S
i
].
i = 1, 2, ..., n
(6.5)
6.3 Método Backward/Forward da Soma de Potências
O método da soma de potências (Baran e Wu, 1989; Cespedes, 1990) é o método
mais difundido na literatura. Tal método é relativamente simples do ponto de vista
conceitual e apresenta um desempenho eficiente na resolução de pr oblema s de fluxo de
carga radial(Brandini, 20 00) .
Na e tap a Backward são utilizadas as equações de fluxo de carga 6.6 e 6.7:
P
i−1
= P
i
+ r
i
P
′
2
i
+ Q
′
2
i
V
2
i
+ P
Li
(6.6)
Q
i−1
= Q
i
+ x
i
P
′
2
i
+ Q
′
2
i
V
2
i
+ Q
Li
, (6.7)
onde:
• P
i
é o fluxo de po tên cia ativa no ramo i;
• Q
i
é o fluxo de po tên cia reativa no ramo i;
• P
Li
é a injeção de potência a tiva líquida na barra i;
• Q
Li
é a injeção de potência r eativa líquida na barra i;
82 6.3. Método Backward/Forward da Soma de Potências
• P
′
i
= P
i
+ P
Li
;
• Q
′
i
= Q
i
+ Q
Li
.
Na etapa Forward, as Equações 6.8 e 6.9 são utilizadas para atua lizar as tensões nas
barras.
V
2
i+1
= V
2
i
− (r
i
P
i
+ x
i
Q
i
) + (r
2
i
+ x
2
i
)
P
2
i
+ Q
2
i
V
2
i
, (6.8)
δ
i+1
= δ
i
− tan
−1
(
k
1
k
2
), (6.9)
onde,
• V
i
é a ten são na barra i;
• δ
i
é o ân gulo na barra i;
• r
i
é a resistência em série na linha que conecta a barra i;
• x
i
é a rea tân cia em série na linha que conecta i;
• k
1
=
P
i
x
i
−Q
i
r
i
V
i
;
• k
2
= V
i
−
P
i
x
i
−Q
i
r
i
V
i
.
O cálculo do fluxo de carga através deste método é composto pelos seguintes passos:
1. Assumir que as tensões iniciais em todas as barras são iguais à tensão da subestação
(nó r aiz);
2. Backward: calcular os fluxos de potência ativa e reativa para cada linha usando
as e quações 6.6 e 6.7;
3. Forward: calcular a tensão e o ângulo de cada barra utilizando as equações 6.8
e 6.9;
4. Como critério de convergência, verificar a variação da tensão e do ângulo na
iteração atual com a iteração anterior. Se a diferença for maior ou igual a uma
tolerância próxima de zero, repita o processo a partir do item 2; caso contrário,
encerram-se o s cálculo s.
83
Capítulo 7
Algoritmo Evolutivo para
Reconfiguração de SDR
Neste Capítulo é apresentado, de forma sucinta, o trabalho desenvolvido em (Santos,
Delbem e Bretas, 2008b), o qual é utilizado como base para o desenvolvimento do
presente trabalho. Para escrever este capítulo utilizou-se como re ferênc ia o texto de
qualificação de doutorado de Augusto Cesar dos Santos (dos Santos, 2008). Na Seção 7.1
é descrito o problema de restabelecimento de energia de SDR. Na Seção 7.2 é apresent ada
a formulação do problema de restabelecimento de energia de SDR. Na Seção 7.3 é
descrita a forma como são avaliadas as soluções geradas pelo AE para reconfiguração
de SDR. Na S eção 7.4 é apresentado o AE para reconfiguração de SDR.
7.1 Restabelecimento: um problema especial de reconfigu-
ração de SDR
Um SDR pode ter a sua topologia representada por grafos (ver Capítulo 5). A
Figura 7.1 mostra um SDR com 3 alimentadores. Cada nó do sistema representa um
setor e as arestas interligando as barras são chaves seccionadoras. As arestas em linha
cheia representam chaves NF (Normalmente Fechadas), enquanto as arestas em linha
pontilhada representam as chaves NA (Normalmente Abertas). As barras 1, 2 e 3
encontram-se em uma subestação.
Na ocorrência de uma falta no sistema, o setor em falta deve ser isolado do SDR
84 7.1. Restabelecimento: um problema especial de reconfiguração de SDR
Figura 7 .1: S DR com 3 alimentadores.
abrindo-se todas as chaves que o conecta ao restante do sistema. Consequentemente,
as áreas a justante do setor em falta também ficarão sem ene rgia. Torna-se, então,
necessário, recone ctar as áreas desenergizadas aos setores supridos de eletricidade, por
meio do fechamento de chaves (Santos, Delbem e Bretas, 2008b).
A Figura 7.2 mostra um exemplo de reconfiguração de SDR para restabelecimento de
energia. Considerando que o setor 15 em falta., o mesmo deve ser isolado do restante do
SDR. Esse pr ocedimento pode ser realizado abrindo-se as chaves A e B. Após a abertura
dessas chaves, os setores 16 e 17 estarão em uma área fora de serviço, representados
na Figura 7.3. Neste caso, o objetivo da reconfiguração é encontrar outro caminho que
forneça energia a esses setores sem violar as restrições operacionais do sistema. Para
isso, ne ste exemplo, existem os seguintes caminhos:
1. Fecha-se a chave C, conectando a área fora de serviço ao alimentador 2;
2. Fecha-se a chave D, conectando a área fora de serviço ao alimentador 1;
3. Fecha-se a chave E, conectando a área fora de serviço ao alimentador 3;
4. Fecha-se a chave F, conectando a área fora de serviço ao alimentador 3;
5. Fecha-se a chave G, conectando a área fora de serviço ao alimentador 1.
A Figura 7.4 mostra a nova configuração fechando a chave F. Após encontrar uma
nova configuração para o SDR, restab ele cen do a energia neste, é necessário que as
seguintes restrições tenham sido satisfeitas (Inagaki et al., 2006):
7.1. Restabelecimento: um problema especial de reconfiguração de SDR 85
Figura 7 .2: SDR em falta no setor 15.
Figura 7 .3: S etor es a jusante do setor em falta desconectados do SDR.
86 7.2. Formulação Matemática
1. Manter a estrutura radial após o serviço de restabelecimento;
2. Atender, quando possível, todas as áreas a jusante do setor e m falta, isto é, os
setores que fic aram fora de serviço;
3. A capacidade limite do transformador não deve ser excedida pelo montante de
carga d e cada alimentador do sistema;
4. A capacidade das linhas e chaves não deve ser ultrapassada pela c o rrente elétrica
em cada ramo ;
5. A queda de tensão em qualquer barra do SDR não deve exceder o limite permis-
sível.
Além disso, o problema de reconfiguração em SDR, neste tra balh o, envolve a mini-
mização d e dois objetivos:
1. Minimizar o número de manobras de operação de chaveamento;
2. Minimizar o total de perdas resistivas.
Figura 7 .4: Nova configuração.
7.2 Formulação Matemática
Para obter a formulação matemática para problemas de reconfiguração de SDR,
consideram-se os seguintes objetivos: minimização das áreas fora de serviço, do número
7.2. Formulação Matemática 87
de operaç ões de chaveamentos e do total de perdas resistivas, sem violar as restrições de
carga e tensão. Também devem ser levados em consideração as 5 restrições operacionais
apresentadas na seção anterior.
Assim, o problema geral de reconfiguração de SDR pode ser formulado como segue
(Delbem et al., 2005):
Min. E(F )
s.a. : H(F) = 0
I(F ) ≤ 0
F é uma flo resta,
(7.1)
onde:
• F - grafo correspondente a uma configuração do sistema, onde cada árvore corre-
sponde a um alimentador ligado a uma subestação;
• E(F ) - função objetivo;
• H(F ) - restrições de igualdade representando as equações de fluxo de carga;
• I(F ) - restrições de desigualdade representando as equações opera cionais do sis-
tema.
A função E(F ) contém, em geral, os seguintes componentes:
• φ(F ) - quantidade de cargas fora de serviço para uma topologia radial da rede
(uma flo resta F);
• ϕ(F ) - perdas resistivas no sistema para F ;
• ψ(F, F
0
) - número de operações de chaveamento para obter uma dada configuração
F , a partir da configuração original F
0
.
As restrições de igualdade correspondem às equações de fluxo de carga. Um sistema
linear do t ipo Ax = b pode representá-las, onde:
• A - matriz de incidência de F ;
88 7.2. Formulação Matemática
• x - vetor de corrente de linha ;
• b - vetor com as injeções d e correntes (de carga) nas barras (bi ≤ 0), ou injeções
de co rrentes nas subestações (b
i
> 0).
As restrições operacionais de I(F) para problemas de reconfiguração de SDR geral-
mente incluem:
• Um limitante superior de corrente
x
j
para cada corrente de linha x
j
. A maior
taxa x
j
/
x
j
é denominada carregamento da rede;
• A máxima injeção de corrente
b
i
possíve l para cada subestação i, onde a maior
taxa b
i
/
b
i
é den omina da carregamento da subestação;
• Um limitante inferior para a tensão no nó v
. Seja v
i
a tensão na ba rra i e v
b
a
tensão base no sistema; a maior taxa v
i
/v
b
é denominada maior taxa de tensão.
O vetor de tensão v é dado por Y v = b, onde Y é a matriz de admitância nodal
(Y = AY
x
A
T
, c om Y
x
sendo a matriz de admitân cia diagonal).
É comum a utilização do modelo de corrente constante e ordenação das barras se-
gundo o modelo pai-filho (MPF) (Delbem et al., 2005), em problemas de reconfiguração
de SDR. Assim, através do fluxo de carga, calculam-se os fluxos de corrente das barras
partindo-se dos nós terminais (nós folhas) em direção à subestação (nó raiz); enquanto
as tensões podem ser obtidas de forma encadeada partindo da subestação até as barras
terminais.
A função objetivo para problemas envolvendo reconfiguração de SDR geralmente
é não linear, descontínua e com vários ótimos locais, dificultando a utilização de Pro-
gramação Matemática. Quando os AE são empregados para a resolução desse tipo de
problema, algumas modificações são realizadas na formulação apresentada na expressão
7.1. São inseridos fatores de pena lidad es (Goldberg, 1989) a fim de penalizar as config-
urações da rede que violarem as restrições operacion ais I(F ). Assim, o problema pode
ser r eformulado como segue:
Min. E(F ) + |ΩI(F )|
s.a. : H(F) = 0
F é uma floresta,
(7.2)
7.2. Formulação Matemática 89
onde Ω é uma matriz diagonal c om os seguintes elementos:
w
11
=
w
x
, se, pelo menos para um j, x
j
>
x
j
0, caso contrário;
w
22
=
w
s
, se, pelo menos para um i, b
i
>
b
i
0, caso contrário;
w
33
=
w
v
, se, pelo menos para um i, v
i
< v
0, caso contrário.
Os pesos w
x
, w
s
e w
v
são valores positivos e, |.| é a norma infinita usual ( Gradshteyn e
Ryzhik, 2 000) , isto é, a norma L
1
de u m vetor z de tamanho n é dada por
n
r=1
|Z
r
|.
A formulação do problema anterior pode ser simplificada através da utilização a RNP
e de seus operadores. Estes operadores realizam mo difica ções em uma floresta para a
produção de novas florestas (configurações de SDR), que correspondam a configurações
radiais factíveis. Dessa forma, utilizando a RNP, o problema descrito na Equação 7.2
pode ser reescrito como segue:
Min. E(F ) + |ΩI(F )|
s.a. : H(F) = 0
F é dado pelos o peradores da RNP.
(7.3)
A RNP de um SDR possui, naturalmente, as barras de cada árvore (alimentador)
ordenadas segundo o MPF. Com isso, evita-se a utiliza ção de um algoritmo de busca
(Cormen, 2002) p ara obter tal modelo. Assim, o fluxo de carga pelo MPF com RNP
é mais eficiente que fluxos de carga convencionais para SDR (Santos, Nanni, Mansour,
Delbem, London e Bretas, 2008). Além d isso, o uso de MPF garante qu e as restrições de
igualdade (H(F)) na Equação 7.3 sejam satisfeitas. Assim, fazendo uso da propriedade
da RNP de permitir o armazenamento dos nós de acordo com o MPF, pode-se escrever
90 7.3. Avaliação das soluções
o pro blema de restabele cimento de SDR da seguinte forma:
Min. E(F ) + |ΩI(F )|
s.a. : Utilizar MPF com RNP
F é da do pelos operadores d a RNP.
(7.4)
A utilização da RNP e seus operadores juntamente com o fluxo de carga pelo MPF
tornam a modelagem matemática do problema mais simples, isso é facilmente percebido
comparando a Equação 7.4 com a Equação 7.1. Além disso, com esta formulação são
geradas exclusivamente configurações factíveis. Assim, somente as restrições de queda
de tensão, carregamento na rede e nos transformadores são consideradas na formulação
matemática d o proble ma.
7.3 Avaliação das soluções
Esta seção apresenta a forma co mo se realiza a avaliação das soluções no trabalho
proposto em (dos Santos, 2008). Basicamente, esta avaliação é realizada através do
cálculo do fluxo de carga (ver Capítulo 6), com exceção do número de operações de
chaveamento. O fluxo d e carga utilizado é similar aos apresentados anteriormente,
porém sofre algumas alterações devido ao uso da RNP.
7.3.1 Extensão da RNP para fluxo de carga
Geralmente, em SDR reais nem todos os trechos entre as barras são separados por
chaves seccionadoras, logo, denomina-se setor o conjunto de barras e linhas não sepa-
radas por chaves seccionadoras. Vale ressaltar que em muitos trabalhos, as barras de
carga de um setor são modeladas como se estivessem concentradas em um único ponto.
Esse procedimento reduz o grau de confiabilidade do sistema.
Procurando reproduzir um S DR real, c om a maior fidelidade possível, em (dos San-
tos, 2008) utilizou-se a RNP em do is níveis diferentes: a RNP do alimentador e a RNP
do setor. Considere os 2 alimentadores da Figura 7.5. As barras em azul pertencem
ao alimentador 1 e as barras em preto ao alimentador 2. Nas Figuras 7.5 e 7.6, os
retângulos são barras em subestações, círculos são barras do SDR (barras de carga,
7.3. Avaliação das soluções 91
extremidade de chaves, ponto de conexão de duas ou mais linhas), linh as pontilhadas
são chaves seccionadoras NF, linhas cheias são linhas do SDR e linhas interrompidas
são chaves seccionadoras NA.
Figura 7 .5: S DR com dois alimentadores.
A Figura 7.6 mostra o agrupamento das barras e linhas não separadas por chaves
na Figura 7.5, desta forma, tem-se um grafo em que todas as arest as são chaves sec-
cionadoras, conforme a Figu ra 7.7.
Figura 7 .6: Agru pa mento das linhas e barras em setores.
Figura 7 .7: Grafo re presentando setores do SDR da Figura 7.6.
A Figura 7.7 possui 2 RNPs, uma para o alimentador 1 (cor azu l) e outra para o
alimentador 2 (cor preta), denominadas RNP do alimentador. As chaves seccionadoras
NF são as arestas em azul e preto e a chave aberta é a aresta em vermelho. Assim, temos
uma estrutura NP
1
que armazena o endereço de memória da RNP do alimentador 1, e
a estrutura NP
2
armazena o en dere ço de memória da RNP do alimentador 2:
92 7.3. Avaliação das soluções
NP
1
=
0 1 2 2
A B D C
,
NP
2
=
0 1 2
E G F
.
A partir da Figura 7.6 cada trecho de linhas e barras não separadas por chaves pode
ser analisado como uma árvore de grafo, isto é, é possível tamb ém associar RNP’s aos
setores. Cada setor pode ter mais de um nó raiz, dependendo do sentido em que está
sendo alimentado. Assim, pode haver mais de uma árvore representando cada setor.
Para finalidade de fluxo de carga, acrescenta-se a cada uma dessas árvores o nó adjacente
ao seu nó raiz. A figura 7.8 mostra o setor C da figura 7.6 com os seus respectivos nós
adjacentes (cor azul).
Figura 7 .8: Árvore do setor C, com o nó adicional.
A RNP do setor pode ser representada de forma semelhante à RNP do alimentador,
onde as árvores foram armazenadas em estruturas denotadas por N P
i
. Para a RNP do
setor, denota-se B
sr
, onde s representa o setor em análise e r o setor pelo qual a energia
cheg a ao setor s. Conforme pode ser visto na Figura 7.8, para o mesmo setor s pode
existir mais d e um setor r.
Para a Figura 7.8, o fluxo de corrente pode chegar ao setor C por dois caminhos
diferentes, através do setor B ou do setor F . Assim, têm-se B
sr
= B
CB
para o setor B
e B
sr
= B
CF
para o setor F . As RNPs possíveis para o setor C são:
7.3. Avaliação das soluções 93
B
CB
=
0 1 2
3 6 7
,
B
CF
=
0 1 2
10 7 6
.
Para descobrir qual das configurações acima deve ser utilizada é necessário realizar
uma análise da RNP do alimentador. Deste modo, analisando o alimentador 1, descobre-
se que o setor C está conectado ao setor B, conforme abaixo:
NP
1
=
0 1 2 2
A B D C
.
Porta nto, no exemplo da Figura 7.8, o setor B é o r correto.
Importa destacar que a determinação de todas as RNPs de cada setor pode ser
executada por um procedimento off-line, deixando todas as estruturas prontas para
serem utilizadas pelo fluxo d e carg a on-line.
7.3.2 Método Backward/Forward com RNP
O método de restabelecimento de SDR p roposto em (dos Santos, 2008) utiliza o
equivalente monofásico e o modelo de corrente constante para o cálculo de fluxo de carg a.
Isto em razão das características específicas dos SDR e da necessidade de encontrar
configurações em um curto tempo de processamento.
Método Computacional
O algoritmo de fluxo de carga proposto em (d os Santos, 2008) é composto por duas
subrotinas:
• Subrotina CORRENTES: obtém as correntes a jusante por meio do processo
backward para todas as barras de um alimentador;
• Subrotina TENSÕES: utiliza as correntes a jusante para obter as tensões nas
barras do mesmo alimentador, por meio do processo forward.
94 7.3. Avaliação das soluções
Em razão de estar sendo utilizado o modelo de corrente constante, a convergência é
atingida em um único ciclo.
No Algoritmo 5 é descrita a subrotina CORRENTES, observe que a ordem dos
nós visitados é no sentido dos nós termina is para a raíz, ordem que está pre-determinada
nas RNPs do alimentador e do setor. A carga de uma barra m é denominada I(m) e a
sua cor rente jusante é denominada J(m).
Algoritmo 5 Subrotina CORRENTES.
1: for k ← |NP |, |NP | − 1, ..., 1 do
2: u ← N P.prof(k) − 1
3: s ← N P.no(k)
4: r ← N P.no(u)
5: //A corrente jusante em todas as barras em NP recebem zero
6: J(N P ) ← 0
7: while q ← |B
sr
|, |B
sr
| − 1, ..., 1 do
8: p ← B
sr
.prof(q) − 1
9: m ← B
sr
.no(p)
10: n ← B
sr
.no(q)
11: J(m) ← J(m) + J(n) + I(n)
12: end while
13: end for
Algoritmo 6 Subrotina TENSÕES.
1: for k ← 1, 2, ..., |NP | do
2: u ← N P.prof(k) − 1
3: s ← N P.no(k)
4: r ← N P.no(u)
5: //A tensão nas barras da subestação geralmente é 13.8 kV
6: B
sr
← V
sub
7: while q ← 1, 2, ..., |B
sr
| do
8: p ← B
sr
.prof(q) − 1
9: m ← B
sr
.no(p)
10: n ← B
sr
.no(q)
11: Calcular a queda de tensão na rede entre as barras m e n
12: ∆V ← Z
mn
∗ (J(n) + I(n))
13: V (n) ← V (m) − ∆V
14: end while
15: end for
No Algoritmo 6 é descrita a subrotina TENSÕES, observe agora que a ordem
dos nós visitados é no sentido do nó raiz para os nós terminais. Essa ordem já está
7.3. Avaliação das soluções 95
determinada nas RNPs d o alimentador e do setor. Os dados necessários para obter
as tensões em cada barra são a corrente na barra I(n), a tensão a montante da barra
n, V (m), e a impedância Z
mn
entr e as barras m e n.
Os dados retornados pelas subrotinas apresentadas acima são utiliza dos pelo algo-
ritmo principal d o fluxo de carga utilizando a RNP, este descrito no Algo ritmo 7.
Algoritmo 7 Fluxo de carga.
1: //Para cada estrutura N P
i
de F
2: for i ← 1, 2, ..., |F | do
3: CORRENTES(F → NP
i
)
4: TENSOES(F → NP
i
)
5: end for
7.3.3 Cálculo do número de manobras
Cada configuração gerada pela aplicação dos operadores da RNP é avaliada por
um fluxo de carga e pelo número de man obra s necessárias para implementar essa nova
configuração, deter minan do assim a sua a dequ ação para o problema de reconfiguração
de SDR. Em geral, determina-se o número de manobras a partir de comparações entre
vetore s binários que armazenam o estado das chaves ( 1 - abe rta; 0 - fechada ) de
cada configuração. O custo computacional deste procedimento é relativamente a lto,
pois é criado um vetor de estado atual das chaves para cada nova configuração gerada
e realiza-se uma comparação deste com o vetor da config uraç ão inicial. O tamanho
de cada vetor é equivalente ao número de chaves (m) no SDR. Assim, o tempo para
percorrer cada vetor é bem maior que o tempo de realizar uma modificação no SDR
pelos operadores genéticos da RNP, que requerem tempo computacional da ordem do
tamanho do a limentador do SDR, em geral, um número bem menor que m.
Em (dos Santos, 2008) foi proposto um algoritmo que determina o número de
manobras de forma mais eficiente, melhorando, deste modo, o desempenho computa-
cional. Para esta formulação são utilizados dois vetores: um com o estado das chaves
na configuração inicial e outro, de tamanho G
max
(nú mero máximo de gerações), que
armazena a quantidade de chaves alteradas em relação à configuração inicial.
Na ocorrência de uma falta, o procedimento de isolar o seto r em falta e conectar os
setores a jusante do mesmo ao SDR exige manobras de chaves que nem sempre ocorrerão
96 7.3. Avaliação das soluções
aos pares. Para ilustrar esse procedimento, o SDR da Figura 7.9 tém o setor 15 em falta.
As chaves A e B são abertas para isolar tal setor, com isso são realizadas 2 manobras
de chaves. Com este procedimento, os setores 16 e 17 ficaram desconectados do SDR.
Para reconectá-los novamente, é necessário fechar uma chave (dentre as chaves C, D, E,
F ou G) que os conectam a algum alimentador, isto custará 1 manobra de chave. Deste
modo, na primeira a ltera ção de topolo gia foram necessárias 3 manobras de chaves.
Figura 7 .9: Operações de manobras necessárias para isolar o setor em falta.
Após o procedimento descrito acima, as chaves alteradas ocorrer ão em pares, isto é,
quando uma chave é aberta, outra deve ser fechada. O estado das chaves é dividido em
3 configurações, assim é possível determinar o número de manobras para originar uma
determinada c onfig ura ção:
1. Configuração inicial (o)
1
;
2. Configuração alterada (x);
3. Configuração final (y).
Considerando que uma configuração y origino u-se de alterações em uma configuração
x, têm-se 3 possibilidade para calcular o número de chaves alteradas da configuração y;
1. Os estados das duas chaves alteradas em y, em relação a x, são diferentes dos
estados dessas chaves em o. Deste modo, o número de chaves alteradas de y será
o nú mero de chaves alteradas de x mais 2;
1
Na configuração initial o setor em falta se encontra isolado e a energia restabelecida ao setores a
jusante.
7.3. Avaliação das soluções 97
Tabela 7.1: Man obr as de chaves - caso 1.
Configuraçõ es
Chaves o x y
1 1 1 0
2 1 0 0
3 0 1 1
4 0 0 1
5 1 1 1
2. Os estados das duas chaves alteradas em y, em relação a x, são iguais aos estados
dessas chaves em o. Deste modo, o número de chaves alteradas de y será o número
de chaves alteradas de x menos 2;
Tabela 7.2: Man obr as de chaves - caso 2.
Configuraçõ es
Chaves o x y
1 1 1 1
2 1 0 1
3 0 1 0
4 0 0 0
5 1 1 1
3. O estado de uma das chaves alteradas em y, em relação a x, é igual ao estado
dessa chave em o e, o estado da outra chave alterada é diferente. Deste modo, o
núme ro de chaves alteradas de y será igual ao número de chaves alteradas de x.
Tabela 7.3: Man obr as de chaves - caso 3.
Configuraçõ es
Chaves o x y
1 1 1 1
2 1 0 1
3 0 1 1
4 0 0 0
5 1 1 0
Em todos os casos acima, são necessárias 2 mudanças de chaves em x para originar y,
porém não garante que essas mudanç as sejam efetivas, ou seja, em rela ção à configuração
inicial o. Por esse motivo, não se pode simplesmente dizer que o número de manobras
necessárias p ara implantar y é o número de manobras para implantar x mais 2.
98 7.4. Algoritmo Evolutivo para Restabelecimento de SDR
7.4 Algoritmo Evolutivo para Restabelecimento de SDR
Em (dos Santos, 2008), foi desenvolvido um alg oritmo evolutivo que busca estraté-
gias para restabelecer energia , em SDR de grande porte, após a ocorrência de uma ou
múltip las faltas. Devido à radialidade do sistema, uma área fora de serviço pode ser con-
siderada como uma subárvore de grafo, tornando po ssível a aplicação dos operadores
da RNP (ver Capítulo 5) para conectá-la a uma outra árvore (alimentador), quando
possíve l. A aplicação desses operadores gera um novo indivíduo na população, que
representa uma configuração factível. Porém, este indivíduo pode violar as restrições
operacionais do sistema, inviabilizando o uso de tal configuração na p rática. Desta
forma, é necessário encontrar uma nova configuração que atenda áquelas restrições.
Para suprir este problema, o AE proposto em (Santos, Delbem e Bretas, 2008b) inicia a
sua busca por melhores configurações partindo de uma configuração factível e, a partir
de ta l, é capaz de produ zir soluções melhores e adequad as para utilização na prática.
Basicament e, o AE proposto em (dos Santos, 2 008 ) trabalha em paralelo com várias
subpopulações armazenada s em tabelas (R. Benayoun e Laritchev, 1973). Os me lhor es
indivíduos para cada característica (perdas resistivas, queda de tensão, carregamento
da rede, carregamento da subestação/transformadores) do problema são armazenados
em sua respectiva subpopulação. Uma subpopulação foi criada para armazenar os in-
divíduos avaliados por uma função agregação.
Alguns pa râmetr os são estabelecido s para o desempenho do AE:
1. O tamanho de uma subpopulação S
pi
, indica o número máximo de indivíduos que
podem permanecer em uma subpopulação P
i
de u ma geração para outra;
2. O número máximo de geração (G
max
).
As soluç ões gerada s pelo AE, dependendo do grau de adaptação do indivíduo a cada
objetivo (característica do problema em uma subpopulação P
i
) do problema, podem ser
armazenadas ou descartad as. Inicialmente, é gerado apenas um indivíduo em cada pop-
ulação i (corresponde à configuração original F
0
). Na etapa de seleção de sobreviventes
acrescenta-se um novo indivíduo a subpopula ção , apenas se o número de indivíduos for
menor que S
pi
ou, se a sua adequaç ão ao objetivo daquela subpopulação for melhor que
pelo menos um indivíduo da mesma. Dependendo do critério de seleção, um indivíduo
7.5. Comentários Adicionais 99
pode ser incluído em mais de um conjunto. Como a população é estacionária, os novos
indivíduos substituem os pior es, desta forma, mantendo os melhores in divídu os.
Para aumentar a diversidade da população geral, os indivíduos selecionado para a
reprodução podem ser escolhidos de qualquer tabela. Com isso, o AE consegue escapar
de possíveis ótimos locais, aumentando assim a possibilidade de en contrar uma solução
global, ou, soluções bem próximas a um ótimo global.
A escolha do operador de reprodução é feita segundo uma taxa de adaptação variável.
O algoritmo inicia usando a mesma taxa de probabilidade para os dois operadores
(OP 1 = OP 2 = 0, 50). Suponha que o operador 1 foi escolhido para gerar um novo
indivíduo. Se o indivíduo gerado tiver sucesso, ou seja, for acrescentado a uma ou mais
subpopulações, aumenta-se OP 1 para 0,51 e, como consequência, OP 2 é reduzido para
0,49, e assim por diante. Os resultados apresentados em (Santos, Delbem e Bretas,
2008b; Santos, Delbem e Bretas, 2008a) mostram que esse ajuste dinâmico, do processo
de escolha d os operadores, melhora con sideravelmente o desempenho do algoritmo.
A cada novo indivíduo gerado, a rotina de fluxo de carga com R NP é executada
para avaliar a adaptação do mesmo.
7.5 Comentários Adicionais
A simplicação do problema utilizando a RNP e seus operadores reduz o tempo
de processamento, devido a produção exclusiva de configuração factíveis e a avaliação
relativamente rápida de cada configuração por um fluxo de carga mais eficiente. Foi
implementado um AE que utiliza o método de tabelas para trata r o problema de re-
configuração. As configurações encontradas pelo AE atendem as restrições operacionais
e minimizam tanto manobras quanto o total de perdas resistivas. Porém este não ap-
resenta um bom mapea mento do proble ma, pois não gera uma Fronteira de Pareto,
diminu indo assim o número de configurações possíveis de serem implementadas em um
SDR.
Deste modo , propõe-se, neste trabalho, substituir o método de t abelas por alguma
técnica de MOEA, gerando assim uma Fronteira de Pareto, de forma a conseguir en-
contrar configurações melhores das obtidas em (Santos, Delbem e Bretas, 2008b ).
101
Capítulo 8
Algoritmo Proposto para
Restabelecimento de Energia para
SDR
Neste Capítulo apresenta-se o algoritmo proposto para obtenção d e planos de resta-
belecimento para SDR de grande porte, que se baseia no trabalho apresentado em
(Santos, Delbem e Bretas, 2008b), descrito no capítulo 7, e na técnica NSGA-II.
O NSGA-II é a técnica de MOEA mais utilizada na literatura e já foi aplicada para
resolver o problema de restabelecimento em SDR (Kumar et al., 2008). Porém, o NSGA-
II não apresenta bons resultados quando aplicado em problemas com um grande número
de funç ões objetivo (geralmente acima de três objetivos), conforme abord ad o em (Deb e
Sundar, 2006b). Deste modo, para lidar com o problema de restabele cimento de energia
em SDR, foram necessárias algumas modifica ções no NSGA-II. Tais modifica ções serão
descritas a seguir. Na Seção 8.1 é apresentada a formulaçã o matemática utilizada no
AE proposto. Na Seção 8.2 é descrito o AE proposto e na Seção 8.3, é apresentado um
exemplo ilustrativo da sua aplicaçã o.
8.1 Formulação Matemática
Os AEs convencionais, ou mono-objetivos, quando aplicados para o problema multi-
objetivo de restabelecimento de energia em SDR, fazem uso de uma função agreg açã o
102 8.1. Formulação Matemática
e perdem eficiência qu and o aplicados em SDR de grande porte (Kumar et a l., 2008 ).
Para contornar esse problema, em (Santos, Delbem e Bretas, 2008b) desenvolveu-se
um AE para reconfigura ção de SDR que faz uso da RNP e de seus operadores. Destaca-
se o fato de tais operadores gera rem apenas config ura ções factíveis. Além disso, em
razão de a RNP permitir o armazenamento dos nós de a cord o com o MPF, em (Santos,
Delbem e Bretas, 2008b) o problema de restabelecimento foi formulado de uma forma
mais simples (veja Equação 7.4).
O AE proposto neste trabalho também faz uso da RNP e dos seus operadores,
entr etanto baseia-se no NSGA-II. Assim, são necessárias algumas modificaçõe s na for-
mulaç ão do problema de restabelecimento de energia proposta em (Santos, Delbem e
Bretas, 200 8b) .
Na formulação que está sendo proposta neste trab alh o consideram-se duas funções
objetivo: a primeira é o número de operações de chaveame nto, que deve ser o menor
possíve l para garantir um rápido restabelecimento de energia; e a segunda é uma função
agregação que contempla os demais objetivos do problema de restabelecimento (perdas
resistiva s, restrições operacionais dent re outros). Dessa forma, o problema descrito na
Equação 7 .4 é reescrito como segue:
Min. E = [e
1
(F ) |ΩI
′
(F )|]
s.a.
Utilizar MPF com RNP
F é dado pelos operadores da RNP,
(8.1)
onde E é um vetor de duas funções objetivo: e
1
(F ) é o número de operações de chavea-
mento ; e |ΩI
′
(F )| é a função agregação composta pelas restrições operacionais (queda
de tenção, carregamento da rede e carregamento do sistema) e pelas perdas resistivas.
A penalidade Ω é uma matriz diagonal composta pelos seguintes elementos:
w
11
=
w
x
, se, pelo menos para um j, x
j
>
x
j
0, caso contrário;
8.2. Algoritmo Proposto 103
w
22
=
w
s
, se, pelo menos para um i, b
i
>
b
i
0, caso contrário;
w
33
=
w
v
, se, pelo menos para um i, v
i
< v
0, caso contrário.
onde,
• Um limitante superior de corrente
x
j
para cada corrente de linha x
j
. A maior
taxa x
j
/
x
j
é denominada car rega mento da rede;
• A máxima injeção de corrente
b
i
possíve l para cada subestação i, onde a maior
taxa b
i
/
b
i
é denominada carregamento da subestação;
• Um limitante inferior para a tensão no nó v
. Seja v
i
a tensão na barra i e v
b
a
tensão base n o sistema; a maior taxa v
i
/v
b
é den omina da maior taxa de tensão.
Conforme mencionado anteriormente, o NSGA-II não apresenta um b o m desem-
penho para problemas com mais de três funções objetivo, como descrito em Deb e
Sundar (2006b). No AE proposto, o NSGA-II não apresenta bom desempen ho para
mais de duas funções objetivo. Eis a razão de a formulação propost a (8.1) utilizar
apenas duas funções objetivo.
8.2 Algoritmo Proposto
Como mencionado anteriormente, o algoritmo proposto (NS2R) baseia-se na RNP e
no NSGA-II. Porém, de vido à utilização da RNP, são necessárias algumas modificações
no NSGA-II tradicional, apresentado no Cap ítulo 4, pois no NS2R as populações P e Q
são geradas pelos operadores da RNP. Lembrando que no NSGA-II tradicional, aquelas
populações são geradas por operadores genéticos tradicionais.
Inicialmente, o oper ado r 1 é utilizado para conectar a área fora de serviço a al-
gum alimentador, gerando assim o primeiro indivíduo d a população P
1
. Este indivíduo
representa uma configuração factível e através dele são gerados os demais N
ind
− 1
104 8.3. Exemplo Ilustrativo da Aplicação do PRN
indivíduos restantes da população P
1
. Os demais passos são similares ao algoritmo 4
(ver Seção 4.2.1), com exceção da geração das populações, conforme discutido anterior-
mente .
Algoritmo 8 NS2R
1: Criar o primeiro indivíduo da população P
1
usando o operador 1
2: Criar os demais N
ind
− 1 indivíduos da população P
1
usando o operador 1
3: Aplicar Algoritmo 2, para classificar P
1
por não dominância
4: Pais ← selecionar os indivíduos progenitores em P
1
utilizando o o perador ≺
c
5: Gerar a população Q
1
de tamanho N
ind
, a plica ndo o operador 1 em Pais
6: for geração t ← 1, 2, ..., G
max
do
7: Aplicar Algo ritmo 2, para classificar R
t
← P
t
∪ Q
t
por não dominância
8: k ← 1
9: P
t+1
← {}
10: while |P
t+1
+ F
k
| ≤ N
ind
do
11: Aplicar algoritmo 3 em F
k
, p ara calcular as distâncias de multidão
12: P
t+1
← P
t+1
∪ F
k
13: k ← k + 1
14: end while
15: Aplicar o Algo ritmo 3 em F
k
, para calc ular as distâncias de multidão
16: Classificar a fronteira F
k
pelo ranking e a distância usando o operador ≺
c
17: Copiar as p rimeiras N
ind
− |P
t+1
| solu ções de F
k
para P
t+1
18: P ais ← selecionar indivíduos progenitores em P
t+1
pelo o operador ≺
c
19: Op ←decidir-operador(operador1, operador2, t)
20: Gerar a n ova população Q
t+1
aplicando o operador Op em P ais
21: t ← t + 1
22: end for
23: P
final
← P
t
24: Q
final
← Q
t
O algoritmo NS2R foi implementado computacionalmente dando origem ao Pro-
grama para obtenção de planos de Restabelecimento de energia em SDRs utilizando o
NS2R (PR N).
8.3 Exemplo Ilustrativo da Aplicação do PRN
Para ilustrar o fun cion amento do PRN, considere o SDR composto por 93 barras,
25 setores, 8 alimentares e 30 chaves, que é uma versão modificada do SDR utilizado
em (Kagan, 1999). Após aplicar o proced imendo apresentado no Capít ulo 7, Seção 7.3.1,
este SDR é representado da forma ilustrada na Figura 8.1, onde os círculos são os setores,
os retângulos os alimentadores, as linhas cheias são as chaves NF e as linhas trasejada s
8.3. Exemplo Ilustrativo da Aplicação do PRN 105
são chaves NA.
Figura 8 .1: S DR com 8 alimentadores.
Vamos considerar que o setor 4, em vermelho na Figura 8.2, está em falta. Em
seguida esse setor é isolado do restante do SDR. Esse procedimento pode ser realizado
abrindo-se as chaves c13 e c18 (em azul na Figura 8.3). Após a abertura dessas chaves, o
setor 5 ficou sem fornecimento de energia elétrica. Nessa situação o PRN deve encontra r
outro caminho que forneça energia a esse setor, sem violar as restrições operacionais do
sistema. Para isso, nesse exemplo, a chave c21 (em azul na Figura 8.3) foi fechada.
Assim, nessa primeira etapa foram necessárias 3 manobras para isolar o setor faltoso e
restabelecer energia no SDR.
Após a obtenção dessa configuração inicial, ilustrada na Figura 8.3, avalia-se a
mesma através do fluxo de carga baseado na RNP e do número de manobras necessárias
para implementá-la, determinando assim a sua adequação para o problema de restab-
elecimento de energia. Obtêm-se os seguintes resultados:
• Perdas resistivas = 1403,33kW;
• Carregamento da rede = 103,00%;
• Carregamento do Sistema = 70,25%;
• Queda de tensão = 7,32%.
106 8.3. Exemplo Ilustrativo da Aplicação do PRN
Figura 8 .2: S DR com falta no setor 4.
Figura 8 .3: S DR restabe lecido .
8.3. Exemplo Ilustrativo da Aplicação do PRN 107
Verifica-se então que os limites operacionais do sistema não foram obedecidos, que no
caso são o carregamento da rede que têm que estar abaixo dos 100%, e a que da de tensão
que têm que ser menor que 7%, conforme a especificação da ANEEL(Agência Nacional
de Energia Elétrica) (ANEEL, 2008). Desta forma, de acordo co m o Algoritmo 8,
tomando por base essa primeira configuração, são cr iada s as populações P
1
e Q
1
.
Na Figura 8.4 apresenta-se a melhor configuração obtida, em termos de função
agregação, a partir da união das populações P
1
e Q
1
. Para obter essa configuração,
a partir da configuração inicial, as chaves c17 e c14 foram abertas e as chaves c22 e
c20 foram fechadas, resultando um total de 4 manobras. Assim, para implantar essa
configuração são necessárias 7 manobras, pois para obter a configuração inicial foram
realizadas 3 ma nob ras (ver Capítulo 7, Seção 7.3.3).
Figura 8 .4: Melh or configura ção alterada.
O resultado do fluxo de carga, baseado na RNP, para essa configuração fornece os
seguintes resultados:
• Perdas resistivas = 1331,53kW;
• Carregamento da rede = 97,80%;
• Carregamento do Sistema = 78,15%;
• Queda de tensão = 7,13%.
Após a obtenção das pop ulaç ões P
1
e Q
1
, de acordo com o Algoritmo 8, o PRN e ntra
108 8.3. Exemplo Ilustrativo da Aplicação do PRN
em um processo iterativo para encontrar configurações melhores das que foram ge rada s
até o p resente momento. Desta fora, até atingir o critério de parada (o úmero máximo
de gerações neste problema é igual a 30), o PRN gera várias configurações factíveis,
avaliando-as e mantendo as melhores.
Na Figura 8.5 é ilustrada a melhor configu raç ão gerada no meio do processo iterativo,
isto é, na iteração 15. Observa-se que , em relação à con figu raçã o inicial, a chave c17
foi aberta e a chave c22 foi fechada, resultando um total de 2 manobras. Assim, para
implantar essa configuração são necessárias 5 manobras, pois para obter a configuração
inicial foram rea lizad as 3 manobras.
Figura 8 .5: Melh or config uraç ão alterada gerada no meio do processo iterativo.
O resultado do fluxo de carga, baseado na RNP, para essa configuração fornece os
seguintes resultados:
• Perdas resistivas = 1329,36kW;
• Carregamento da rede = 85,58%;
• Carregamento do Sistema = 78,15%;
• Queda de tensão = 7,06%.
Atingid o o número máximo de iterações, são obtidas as popula ções P
final
e Q
final
,
que contêm as melhores configurações geradas pelo PRN. Na Figura 8.6 é ilustrada
a melhor configuração, em termos de função agregação. Observa-se que, em relação à
8.3. Exemplo Ilustrativo da Aplicação do PRN 109
configuração inicial, as chaves c7, c17 e c25 foram abertas e as chaves c4, c22 e c26 foram
fechad as, resultando um total de 6 manobras. Assim, para implantar essa configuração
são necessárias 9 manobras, pois para obter a configuração inicial foram realizadas 3
manobras são n ecessárias 9 manobr as.
O resultado do fluxo de carga, baseado na RNP, para essa configuração fornece os
seguintes resultados:
• Perdas resistivas = 1324,40kW;
• Carregamento da rede = 73,77%;
• Carregamento do Sistema = 78,15%;
• Queda de tensão = 6,92%V.
Figura 8 .6: Melhor config ura ção gerada no final do processo iterativo.
111
Capítulo 9
Testes e Resultados
Os testes realizados, descritos neste Capítulo, visam comprovar a eficiê ncia do PRN.
Foi utilizado um SDR real de grande porte sem simplificações (foram consideradas todas
as linhas, chaves e barras do sistema). O sistema é composto de: 3860 barras, 635 chaves,
3 subestações com 2 transformadores com pot ência de 50MVA e 1 transformador de
25MVA e 23 alimentadores. O sistema utilizado corresponde ao SDR da cidade de São
Carlos/SP.
O PRN foi implementado num computador convencional com processador Turion64
X2; 2 Gbytes de memória RAM, Sistema operacional Linu x, distribuição Ubuntu 8.04;
e o GCC (GNU Compiler Collection) com compilador de linguagem C. Os resultados
obtidos pelo PRN são comparados com os obtidos pelo programa desenvolvido em (dos
Santos, 2008), que será aqui denominado AERT (Algoritmo Evolutivo utilizando a RNP
e o Método de Tabelas).
Na Seção 9.1 são apresentados os parâmetros utilizados nos programas PRN e AERT.
Na Seção 9.2 são apresentados os resultados das simulações com falta únicas e multifaltas
no SDR real da cidade de São Carlos/SP. Na Seção 9.3 o SDR real de São Carlos/SP
tem o seu tamanho duplicado para avaliar a eficiência do PRN com um número mais
elevado de barras, chaves, linhas e cargas.
9.1 Testes Realizados
Os parâmetros u tiliza dos para análise do PRN, são:
112 9.1. Testes Realizados
1. Número máximo de gerações: G
max
= 200;
2. Número de indivíduos nas populações P e Q: N
ind
= 110.
Na formulação matemática 8.1 a função agregação é f(x) = δ
1
x
1
+δ
2
x
2
+δ
3
x
3
+δ
4
x
4
,
onde, x
1
, x
2
, x
3
e x
4
correspondem respectivamente a: perdas resistivas em kW, má ximo
carregamento da rede em p.u., máximo carregamento do sistema em p.u., máxima queda
de te nsão em p.u.; δ
i
é o peso de c ada objetivo x
i
, sen do:
δ
i
=
100, se, uma restrição foi violada para pelo menos uma barra
0, caso contrário,
para i = 2, 3, 4 e δ
1
= 1.
Os objetivos a serem minimizados em cada execução do PRN foram:
1. Redução do número de manobras;
2. Redução da função agregação.
Para o AERT, tem-se apenas uma função objetivo, que consiste de uma função
agregação composta por 5 objetivos: f(x) = δ
1
x
1
+ δ
2
x
2
+ δ
3
x
3
+ δ
4
x
4
+ δ
5
x
5
, onde:
x
1
, x
2
, x
3
, x
4
e x
5
correspondem respectivamente a: perdas resistivas em kW, operações
de chaveamento, máximo carregamento da rede em p.u., máximo carregamento d o sis-
tema em p.u., máxima queda de tensão em p.u.; δ
i
é o peso de cada objetivo x
i
, sendo:
δ
i
=
100, se, uma restrição foi violada para pelo menos uma barra
0, caso contrário,
para i = 3, 4, 5, δ
1
= 1 e δ
2
= 2.
Para este programa foram utilizados os seguintes parâmetros: 10000 indivíduos
(G
max
= 10000), e os melhores indivíduos de uma população (de tamanho 20) são
mantid os.
As configurações encontradas por ambos os programas (PRN e AERT) são avaliadas
de a cord o com as seguintes características:
9.1. Testes Realizados 113
• Número de manobras de chaveamento necessário para a implementação do plano
de re stabelecimento;
• Total de perdas resistivas em kW;
• A maior queda de tensão (%), que é dada pela expressão:
max
V
b
− V
i
V
b
, (9.1)
onde, V
b
= 13800V e V
i
é a ten são na barra i.
• O maior carregamento da rede (%), que é dado pela expressão:
max
I
c
I
ij
, (9.2)
onde, I
c
é a corrente calculada na linha ij e I
ij
é a corrente máxima suportada
na lin ha ij.
• Carregamento máximo do SDR (%), que corresponde ao carregamento do trans-
formador mais sobrec arre gad o do SDR, dado pela expressão:
CarT
i
=
S
∗
j
+P erdas
j
T
i
,
max {CarT
i
}
(9.3)
onde CarT
i
é o carregamento no transformador i, S
∗
j
é a potência complexa na
barra j, P erdas
j
são as perdas na barra j e T
i
é o máximo carregamento suportado
no tr ansformad or i.
Em todas as simulações realizadas ambos os programas foram executados 20 vezes.
Para o AERT, considerou-se como melhor configuração aquela que apresentou a menor
função agregação na população analisada; para o PRN, considerou-se como melhor
configuração aquela que apresentou o menor número de manobras, menor queda de
tensão e menor perdas resistivas, simultaneamente, isto é, a configuração selecionada é
aquela que garante a continuidade do fornecimento de energia, com o menor número de
chaveamento e perdas resistivas.
114 9.2. Resultados das Simulações no SDR Real de São Carlos
9.2 Resultados das Simulações no SDR Real de São Carlos
A seguir serão considerados testes com falta única no setor 3668, que perte nce ao
alimentador mais sobrecarregado do SDR, bem como múltiplas faltas, estas localizadas
no seto res 3668, 3542 e 1031 do SDR.
9.2.1 Falta Única
Após a ocorrência da falta no setor 3668, o serviço do maior alimentador do SDR é
inter rompid o e a primeira topologia da rede, após isolar os setores defeituosos, possui
as segu intes características:
• Perdas resistivas = 415,02kW;
• Carregamento da rede = 139,60%;
• Carregamento do Sistema = 52,72%;
• Queda de tensão = 5,02%.
Após a execução do PRN várias Fronteiras de Pareto, de diferentes níveis, foram
geradas. Isto o c orre em razão d a complexidade do p rob lema de restabelecimento de
energia em SDR. Para facilitar a análise dos resultados, na Figura 9.1 e na Tabela 9 .1,
foram ap resentadas apenas as configurações da primeira Fronteira de Pareto.
Tabela 9.1: Configurações da primeira Fronteira de Pareto após a falta
única.
Função Perdas Queda Carregamento Carregamento
Agregação Resistivas de Tensão da Rede do Sistema Manobras
[kW] [%] [%] [%]
522,28 382,68 4,39 139,60 52,78 5
480,25 357,50 4,14 122,74 52,81 9
512,64 373,04 4,39 139,60 52,78 7
480,25 357,50 4,14 122,74 52,71 9
480,25 357,50 4,14 122,74 53,08 9
480,25 357,50 4,14 122,74 52,81 9
480,25 357,50 4,14 122,74 50,82 9
269,85 269,85 3,14 82,54 51,05 39
267,76 267,76 3,14 82,54 76,07 41
400,66 400,66 5,63 103,00 56,12 29
464,16 346,66 4,08 117,50 54,90 15
272,79 272,79 3,14 82,54 52,89 37
471,80 349,05 4,14 122,74 52,78 11
9.2. Resultados das Simulações no SDR Real de São Carlos 115
Tabela 9.1: Configurações da primeira Fronteira de Pareto após a falta
única. (continuação)
Função Perdas Queda Carregamento Carregamento
Agregação Resistivas de Tensão da Rede do Sistema Manobras
[kW] [%] [%] [%]
289,87 289,87 3,14 82,54 52,98 35
416,61 416,61 5,50 101,03 47,12 17
412,07 412,07 5,50 101,03 52,68 21
261,76 261,76 3,13 71,61 50,89 57
266,09 266,09 3,14 82,54 74,80 43
264,79 264,79 3,13 82,54 75,40 49
413,71 413,71 5,50 101,03 55,22 19
264,79 264,79 3,13 82,54 74,94 49
409,68 409,68 5,50 101,03 53,80 23
409,68 409,68 5,50 101,03 53,80 23
264,55 264,55 3,13 82,54 52,77 51
409,68 409,68 5,50 101,03 53,80 23
261,76 261,76 3,13 71,61 51,16 57
259,93 259,93 3,13 71,61 54,86 65
408,70 408,70 5,50 101,03 50,89 25
265,26 265,26 3,13 82,54 53,37 47
261,46 261,46 3,13 71,61 52,72 59
261,11 261,11 3,13 71,61 75,47 63
265,68 265,68 3,13 82,54 78,46 45
408,70 408,70 5,50 101,03 52,78 25
408,52 408,52 5,50 101,03 47,14 27
408,52 408,52 5,50 101,03 47,14 27
262,12 262,12 3,13 74,23 50,24 55
259,76 259,76 3,13 71,61 70,02 67
464,16 346,66 4,08 117,50 52,77 15
261,76 261,76 3,13 71,61 48,12 57
264,45 264,45 3,13 82,54 52,78 53
467,47 347,34 4,10 120,12 55,16 13
290,90 290,90 3,14 82,54 76,52 33
259,19 259,19 3,13 71,61 69,27 69
292,28 292,28 3,14 82,54 76,26 31
264,45 264,45 3,13 82,54 48,92 53
261,22 261,22 3,13 71,61 54,71 61
Analisando a Tabela 9.1, percebe-se que em determinadas configurações o valor da
função agregação não é igual ao de perdas resistivas, isso ocorre pelo fato de algumas
restrições estarem sendo penalizadas na função de agregação por violarem os limites
operacionais dos equipamentos. A Figura 9.2 mostra a reduçã o total de perdas resistivas
para a melhor configuração em cada geração (considera-se melhor configuração em cada
geração aquela que apresentar o menor valor de função agr egaç ão). Para essas mesmas
configurações, a Figura 9.3 mostra as manobras. Como os objetivos são conflitantes,
percebe-se que quando ocorre uma r edu ção nas perdas resistivas aumenta a necessidade
de manobras no sistema, isto pode ser facilmente observado na Figura 9.4, nesta figura
116 9.2. Resultados das Simulações no SDR Real de São Carlos
0
10
20
30
40
50
60
70
80
250 300 350 400 450 500 550
Manobras
Funcao Agregacao
Figura 9 .1: Pr imeira Fronteira de Pareto após a falta única no setor 3668.
são linearizados o número de manobras e o de perdas de cada configuração. Estes
resultados foram obtidos utilizando semente 6, para o gerado r de números aleatórios, e
o tempo d e processamento foi de 3250ms.
Análise Comparativa
Testes foram realizados utilizando o programa AERT, aplicando a falta no mesmo
setor 3668. A Tabela 9.2 mostra um comparativo entre os dois programas (AERT e
PRN).
Tabela 9.2: Comparativo entre os métodos AERT e PRN para falta única no setor 3668.
AERT PRN
Média Desvio Padrão Média Desvio Padrão
Perdas Resistivas [kW] 325,49 33,78 355,50 37,47
Queda de Tensão [%] 4,95 1,12 4,17 0,70
Carregamento da Rede [%] 107,62 10,55 98,85 18,49
Carregamento do Sistema [%] 55,97 5,66 52,74 3,22
Manobras 21,90 4,23 14,8 6,19
Tempo [ms] 2564,50 163,63 3110,00 165,40
Analisando a Tabela 9.2, nota-se que o PRN conseguiu uma maior reduç ão no
núme ro de manobras, consequentemente, o AERT obteve um valor de perdas resistivas
menor. Para ambos os prog ramas, com exceção do carregamento da rede, as restrições
9.2. Resultados das Simulações no SDR Real de São Carlos 117
250
300
350
400
450
0 50 100 150 200
Perdas Resistivas[kW]
Geracao
Figura 9 .2: Re duç ão das perdas por gera ção para falta única no setor 3668.
0
10
20
30
40
50
60
70
0 50 100 150 200
Manobras
Geracao
Figura 9 .3: Aume nto das manobras por geração para falta única no setor 3668.
118 9.2. Resultados das Simulações no SDR Real de São Carlos
0
0.2
0.4
0.6
0.8
1
1.2
0 50 100 150 200
Perdas Resistivas[kW] | Manobras
Geracao
Perdas Resistivas[kW]
Manobras
Figura 9 .4: Ma nob ras e perdas resistivas linearizadas para falta únic a no setor 3668.
operacionais não são violadas. O carre gamento da rede viola os limites no AERT dev-
ido ao setor em falta ser do alimentador mais sobrecarregado do SDR, mesmo gerando
apenas configurações factíveis. A vantagem do PRN, neste asp e cto, é que é gerada
uma Fronteira de Pareto contendo diversas configurações factíveis, aumentando assim
a possibilidade de ser encontrada uma solução que não viole os limites operacionais, ao
contrário do AERT que gera apenas uma solução por geração.
9.2.2 Múltiplas Faltas
O serviço de fornecimento de energia elétrica é interrompido após a ocorrência das
faltas nos setores 3668, 3542 e 1031, assim, a primeira topologia da rede, após isolar os
setores de feituosos, possui as seguintes características:
• Perdas resistivas = 447,63kW;
• Carregamento da rede = 83,15%;
• Carregamento do Sistema = 55,07%;
• Queda de tensão = 4,72%.
A Figur a 9.5 e a Tanela 9.3 apresentada apenas as configurações da primeira Fron-
teira d e Pareto.
9.2. Resultados das Simulações no SDR Real de São Carlos 119
0
10
20
30
40
50
60
70
80
250 300 350 400 450
Manobras
Funcao Agregacao
Figura 9.5: Primeira Fronteira de Pareto (múltiplas faltas).
Tabela 9.3: Configurações da primeira Fronteira de Pareto (múltiplas
faltas).
Função Perdas Queda Carregamento Carregamento
Agregação Resistivas de Tensão da Rede do Sistema Manobras
[kW] [%] [%] [%]
440,92 440,92 4,93 80,71 62,14 11
429,94 429,94 4,69 77,66 62,14 13
440,92 440,92 4,93 80,71 61,69 11
429,94 429,94 4,69 77,66 61,65 13
440,92 440,92 4,93 80,71 62,14 11
440,92 440,92 4,93 80,71 62,14 11
429,94 429,94 4,69 77,66 61,65 13
440,92 440,92 4,93 80,71 62,14 11
440,92 440,92 4,93 80,71 62,14 11
421,49 421,49 4,69 77,66 61,65 15
440,92 440,92 4,93 80,71 62,09 11
421,49 421,49 4,69 77,66 62,09 15
421,49 421,49 4,69 77,66 62,09 15
415,55 415,55 4,69 77,66 61,15 17
421,49 421,49 4,69 77,66 62,14 15
421,49 421,49 4,69 77,66 62,13 15
415,55 415,55 4,69 77,66 62,14 17
372,34 372,34 3,39 86,96 62,09 19
415,55 415,55 4,69 77,66 63,28 17
421,49 421,49 4,69 77,66 62,14 15
337,42 337,42 3,25 88,00 62,08 25
358,04 358,04 3,39 89,15 64,11 21
415,55 415,55 4,69 77,66 62,14 17
303,93 303,93 3,25 77,37 62,09 47
293,93 293,93 3,19 81,17 58,24 53
295,60 295,60 3,22 81,17 62,55 51
295,60 295,60 3,22 81,17 63,28 51
298,69 298,69 3,22 81,17 62,09 49
285,96 285,96 3,18 87,29 62,14 77
120 9.2. Resultados das Simulações no SDR Real de São Carlos
Tabela 9.3: Configurações da p rimeira Fronteira de Pareto após múlti-
plas faltas (continuação).
Função Perdas Queda Carregamento Carregamento
Agregação Resistivas de Tensão da Rede do Sistema Manobras
[kW] [%] [%] [%]
289,74 289,74 3,18 81,17 60,95 59
320,95 320,95 3,25 89,15 64,81 29
318,21 318,21 3,25 89,15 58,24 31
288,46 288,46 3,26 69,67 62,09 61
285,96 285,96 3,18 87,29 61,48 77
286,21 286,21 3,26 69,67 62,09 69
337,88 337,88 3,25 89,15 62,14 23
292,49 292,49 3,18 81,17 58,24 55
285,05 285,05 3,18 87,29 62,14 85
286,27 286,27 3,26 69,67 60,90 67
284,88 284,88 3,18 87,29 60,59 89
291,70 291,70 3,18 81,17 62,09 57
285,22 285,22 3,18 87,29 62,08 79
285,98 285,98 3,18 87,29 62,09 75
285,16 285,16 3,18 85,78 62,14 83
318,21 318,21 3,25 89,15 62,13 31
285,18 285,18 3,18 85,78 62,14 81
309,85 309,85 3,25 89,15 62,14 33
288,31 288,31 3,26 69,67 63,28 63
304,33 304,33 3,25 95,98 54,10 43
286,15 286,15 3,18 87,29 62,14 73
328,94 328,94 3,25 89,15 54,98 27
304,20 304,20 3,25 95,98 62,14 45
286,40 286,40 3,26 69,67 62,60 65
292,49 292,49 3,18 81,17 62,09 55
Analisando a Tabela 9.3 percebe-se que, ao contrário do ocorrido na Tabela 9.1, o
valor da função agregação é igual ao de perdas resistivas em todas as config ura ções. Isso
ocorre pelo fato de as configurações encontradas não violarem os limites operacionais
dos equipamentos. Considerando como melhor configu raçã o aquela q ue apresentar a
menor função agregação, a Figura 9.6 mostra a redução total das perdas resistivas para
a melhor configuração em cada geração. Para essas mesmas con figu rações, a Figu ra 9.7
mostra as manobras e na Figura 9.8 são mostrados os valores linearizados do número de
manobras e o de perdas de cada configuração. Estes resultados foram obtidos utilizando
semente 14, para o gerador de número ale atór ios, e o tempo de processamento foi de
3080ms.
9.2. Resultados das Simulações no SDR Real de São Carlos 121
250
300
350
400
450
0 50 100 150 200
Perdas Resistivas[kW]
Geracao
Figura 9 .6: Re duç ão das perdas por gera ção (múltiplas faltas).
0
10
20
30
40
50
60
70
0 50 100 150 200
Manobras
Geracao
Figura 9 .7: Aume nto das manobras por geração (múltiplas faltas).
122 9.2. Resultados das Simulações no SDR Real de São Carlos
0
0.2
0.4
0.6
0.8
1
1.2
0 50 100 150 200
Perdas Resistivas[kW] | Manobras
Geracao
Perdas Resistivas[kW]
Manobras
Figura 9 .8: Manob ras e perdas resistivas linearizadas (múltiplas faltas).
Análise Comparativa
Testes foram realizados utilizando o programa AERT, aplicando as faltas nos setores
3668, 3542 e 1031. A Tabela 9.4 mostra um comparativo entre os dois progra mas (AERT
e PRN).
Tabela 9.4: Comp arat ivo entre os métodos AERT e PRN em múltiplas faltas.
AERT PRN
Média Desvio Padrão Média Desvio Padrão
Perdas Resistivas [kW] 291,27 15,29 347,59 27,86
Queda de Tensão [%] 4,33 1,69 3,31 0,16
Carregamento da Rede [%] 90,84 12,54 92,63 8,26
Carregamento do Sistema [%] 59,76 6,12 54,52 3,38
Manobras 30,90 4,33 18,7 4,32
Tempo [ms] 2815,50 260,35 3230,50 159,92
Analisando a Tabela 9.4 nota- se que o PRN conseguiu uma maior redução no número
de manobras, consequentemente, o AERT obteve um valor de perdas resistivas. Os
limites o peracionais foram obedecidos por ambos os prog ramas.
9.3. Resultados das Simulações no SDR Real de São Carlos Duplicado 123
9.3 Resultados das Simulações no SDR Real de São Carlos
Duplicado
Objetivando verificar o quesito tempo de processamento computacional e analisar o
comportamento do PRN em SDRs maiores daquele utilizado até agora, o SDR da cidade
de São Carlos/SP foi duplicado. O SDR duplicado de São Carlos/SP é composto de:
7720 barras, 1270 chaves, 6 subestações com 4 transformadores com potência de 50MVA
e 2 transformadores de 2 5MVA e, 46 alimentadores.
Os objetivos e as penalidades na função agregação são os mesmos considerados no
PRN n as simulações anteriores. Os parâmetros utilizados para análise do PRN, são:
1. Número máximo de gerações: G
max
= 250;
2. Número de indivíduos nas populações P e Q: N
ind
= 110.
Para o AERT também foram considerados os mesmos objetivos e as penalidades
na função agregação utilizados nas simulações anteriores, porém foram definidos os
seguintes parâmetros: 15000 indivíduos (G
max
= 15000), e os melhores indivíduos de
uma população (de tamanho 20) são mant idos.
A seguir serão considerados testes com múltiplas faltas localizadas nos setores 182,
486, 504 do SDR, interrompendo assim o serviço de fornecimento de energia elétrica.
Logo, a primeira topologia da rede, após isolar os setores defeituosos, possui as seguintes
características:
• Perdas resistivas = 728,97kW;
• Carregamento da rede = 83,15%;
• Carregamento do Sistema = 44,64%;
• Queda de tensão = 4,72%.
A Figura 9.9 apresentada apenas as configurações da primeira Fronteira de Pareto.
As configurações mostradas na Figura 9.9 são ap resentadas na Tabela 9.5.
124 9.3. Resultados d as Simulaçõ es no SDR Real de São Carlos Duplicado
0
20
40
60
80
100
500 550 600 650 700 750 800
Manobras
Funcao Agregacao
Figura 9 .9: Pr imeira Fronteira de Pareto após as múltiplas faltas no SDR duplicado.
Tabela 9.5: Configurações da p rimeira Fronteira de Pareto após múlti-
plas faltas no SDR duplicado
Função Perdas Queda Carregamento Carregamento
Agregação Resistivas de Tensão da Rede do Sistema Manobras
[kW] [%] [%] [%]
728,97 728,97 4,72 83,15 44,64 11
728,97 728,97 4,72 83,15 55,07 11
728,97 728,97 4,72 83,15 55,07 11
728,97 728,97 4,72 83,15 55,07 11
686,05 686,05 3,33 83,15 55,07 13
728,97 728,97 4,72 83,15 55,39 11
686,05 686,05 3,33 83,15 54,68 13
673,02 673,02 3,33 77,63 55,07 15
686,05 686,05 3,33 83,15 55,07 13
728,97 728,97 4,72 83,15 55,07 11
728,97 728,97 4,72 83,15 55,07 11
686,05 686,05 3,33 83,15 55,07 13
663,38 663,38 3,33 77,63 54,02 17
617,69 617,69 3,33 88,00 58,43 27
663,38 663,38 3,33 77,63 55,07 17
663,38 663,38 3,33 77,63 55,07 17
660,29 660,29 3,33 77,63 56,30 19
583,05 583,05 3,25 86,52 60,81 53
610,27 610,27 3,33 85,14 69,49 33
586,52 586,52 3,25 89,15 55,07 47
652,91 652,91 3,33 77,63 54,02 21
607,18 607,18 3,33 85,14 55,07 35
567,57 567,57 3,25 78,21 55,17 71
548,03 548,03 3,25 66,51 55,07 83
548,03 548,03 3,25 66,51 54,02 83
635,15 635,15 3,33 77,63 59,99 23
566,17 566,17 3,25 74,24 55,07 73
542,51 542,51 3,25 77,18 55,07 101
625,50 625,50 3,33 77,63 55,34 25
9.3. Resultados das Simulações no SDR Real de São Carlos Duplicado 125
Tabela 9.5: Configu rações da primeira Fronteira de Pareto após múlti-
plas faltas no SDR duplicado(continuação).
Função Perdas Queda Carregamento Carregamento
Agregação Resistivas de Tensão da Rede do Sistema Manobras
[kW] [%] [%] [%]
584,01 584,01 3,25 89,15 55,39 51
580,77 580,77 3,25 84,34 55,70 57
595,18 595,18 3,25 89,15 55,07 39
572,61 572,61 3,25 79,11 55,07 63
542,99 542,99 3,25 66,95 53,33 95
546,60 546,60 3,25 66,95 53,33 91
548,60 548,60 3,25 78,21 55,07 79
663,38 663,38 3,33 77,63 55,07 17
614,59 614,59 3,33 77,63 59,14 29
549,50 549,50 3,25 78,21 55,07 77
588,44 588,44 3,25 89,15 54,02 43
594,11 594,11 3,25 89,15 55,07 41
612,02 612,02 3,33 88,00 55,62 31
580,22 580,22 3,25 84,34 55,07 59
585,18 585,18 3,25 89,15 55,39 49
587,16 587,16 3,25 89,15 54,68 45
569,92 569,92 3,25 78,21 54,02 69
606,20 606,20 3,33 85,14 55,07 37
581,72 581,73 3,25 86,09 55,47 55
541,32 541,32 3,25 77,18 71,00 103
663,38 663,38 3,33 77,63 55,07 17
579,64 579,64 3,25 84,34 54,68 61
569,92 569,92 3,25 78,21 54,02 69
572,61 572,61 3,25 79,11 59,19 63
540,82 540,82 3,25 77,18 55,07 105
546,88 546,88 3,25 66,51 55,07 85
543,99 543,99 3,25 66,95 55,07 93
541,32 541,32 3,25 77,18 71,30 103
542,85 542,85 3,25 66,95 55,07 97
550,22 550,22 3,25 78,21 59,21 75
571,55 571,55 3,25 79,11 59,19 65
546,60 546,60 3,25 66,95 55,07 91
663,38 663,38 3,33 77,63 55,07 17
Analisando a Tabela 9.5 percebe-se que o valor da função agregação é igua l ao de
perdas resistivas em todas as configurações, isso ocorre pelo fato de as configurações
encontradas não violarem os limites operacionais dos equipamentos. Considerando como
melhor configuração aquela que apresentar a menor função agregação, a Figura 9.10
mostra a redu ção total de perd as resistivas para a melhor configuração em cada geração.
Para essas mesmas configuraçõ es, a Figura 9.11 mostra as manobras e na Figura 9.12
são mostrados os valores linearizados do número de manobras e o de perdas de cada
configuração. Estes resultados foram obtidos utilizando semente 0, para o gerador de
núme ro aleatórios, e o tempo de proce ssamento foi de 4530ms.
126 9.3. Resultados d as Simulaçõ es no SDR Real de São Carlos Duplicado
550
600
650
700
750
800
0 50 100 150 200 250
Perdas Resistivas[kW]
Geracao
Figura 9 .10: Red uçã o das perdas por ger ação para múltiplas faltas no SDR duplicado.
10
20
30
40
50
60
70
80
90
100
110
0 50 100 150 200 250
Manobras
Geracao
Figura 9.11: Redução das manobras por geração para múltiplas faltas no SDR duplicado.
9.3. Resultados das Simulações no SDR Real de São Carlos Duplicado 127
0
0.2
0.4
0.6
0.8
1
1.2
0 50 100 150 200 250
Perdas Resistivas[kW] | Manobras
Geracao
Perdas Resistivas[kW]
Manobras
Figura 9.12: Manobras e perdas resistivas linearizadas para mú ltiplas faltas no SDR
duplicado.
Análise Comparativa
Testes foram realizados utilizand o o programa AERT, aplicando as faltas nos setores
182, 486 e 504. A Tabela 9.6 mostra um comparativo entre os dois programas (AERT
e PRN).
Tabela 9.6: Compara tivo entre os métodos AERT e PRN em múltiplas faltas.
AERT PRN
Média Desvio Padrão Média Desvio Padrão
Perdas Resistivas [kW] 552,58 17,23 634,36 27,55
Queda de Tensão [%] 4,10 1,57 3,52 0,53
Carregamento da Rede [%] 83,95 6,81 88,21 9,15
Carregamento do Sistema [%] 62,98 7,72 55,22 1,97
Manobras 36,20 5,71 24,10 7,91
Tempo [ms] 3307,00 334,81 4229,50 217,29
Analisando a Tabela 9.6, nota-se novamente que o PRN conseguiu uma maior re-
dução no número de manobras, consequentemente, o AERT ob teve um valor de perdas
resistiva s menor. Os limites operacionais em ambos os programas não foram violados.
No quesito tempo de processamento computacional, nota-se que é nec essário em média,
aproximadamente, 4230ms para o PRN encontrar uma Fronteira de Pareto que contenha
configurações factíveis que não violem os limites operacionais, no AERT este tempo é
128 9.4. Comentários Adicionais
inferior. Porém vale destacar que no AERT nã o é fornecida uma Fronteira de Paret o
que co ntenha diversas configurações factíveis.
9.4 Comentários Adicionais
O PRN mostrou-se uma ferramenta capaz de lidar com redes de grande porte, com
tempo de processamento red uzid o. A média de manobras encontradas nas 20 execuções
é baixa. Observa-se também que mesmo em problemas com número de barras elevado,
o algoritmo não incorreu em problema de explosão combinatória, como acontece com
as ferr amentas envolvendo PM.
Cada uma das populações P e Q contém 110 indivíduos. Ao final do processo, os
melhores indivíduos de P UQ são apresentados como configu rações, estas se encontram
na primeira Fronteira de Pareto, cabendo assim ao operador do sistema escolher a config-
uração mais adequada a se utilizar. Esta escolha pode envolver o número de manobras,
a qued a de tensão, a redução de perdas resistivas, além de outras possibilidad es.
129
Capítulo 10
Conclusões
O foco deste trabalho foi o problema de re stabelecimento de energia em SDR, que se
trata de um problema com múltiplos objetivos, normalmente conflitantes
1
, com funções
não lineares e desco ntínuas.
Dentre os objetivos de um PRE têm-se: (i) Reduzir o número de consumidores
inter rompid os (ou nenhum), e (ii) minimizar o número de manob ras; que devem ser
atendidos sem desrespeitar os limites operacionais dos equipamentos. Conseqüente-
mente , a obtenção de PRE em SDR é um problema com múltiplos objetivos, alguns
conflitantes.
A natureza das funções utilizadas no problema de restabelecimento de energia, em
SDR, inviabiliza a utilização de técnicas de programação matemática, pois as mesmas
ficam sujeitas a explosão combinatória. Assim, conforme mostrado no Capítulo 2, nas
últimas déca das diversas técnicas baseadas em AEs for am propostas para o tratamento
do problema em pauta. Embora essas técnicas tenham apresentado resultados satis-
fatórios, as mesmas p roduzem muitas soluções não factíveis, quand o aplicadas em SDR
considerados de g ran de porte, restring indo assim as suas aplicações.
No Capítulo 7 apresentou-se um AE que pode ser aplicado mesmo em SDR de gra nde
porte, proposto em (Santos, Delbem e Bretas, 2008b). O grande diferencial desse AE
é a utilização da RNP e de seus op era dore s, que possibilitam a geração apenas de
configurações factíveis. Dessa forma, aumenta significativamente a eficiência da busca
1
Por exemplo, para reduzir perdas resistivas é necessário um aumento do número de operações de
manobra.
130 10. Conclusões
por melhores soluções (configuraçõ es) do AE, pois diminui a possibilidade de geração de
soluções não factíveis. Esse AE faz uso do método de tabelas para lidar com problemas
multi-o bjetivo.
Neste trabalho desenvolveu-se um novo AE para obtenção de planos de restabelec-
imento de energia em SDR, que foi chamado de NS2R (NSGA-II com RNP), que se
baseia numa versão modificada do NSGA-II juntamente com a RNP e seus operadores.
Optou-se por utilizar como base o NSGA-II, em razão de o mesmo ser a técnica de
MOEA que tem apresentado melhor desempenho para o tratamento do problema de
restabelecimento de energia em SDR. Vale destacar ainda que foram propostas algumas
alterações no NSGA-II. Primeiro em razão da utilização da RNP e de seus operadores e
segundo porque o NSGA-II não é eficiente para solu ção de problemas com mais de três
objetivos.
O NS2R mod ela o problema considerando duas funçõ e s objetivo. A primeira é
o número de operações de chaveamento, que deve ser minimizado, e a segunda é uma
função agregação que incluí as demais restrições do problema. Ao final de sua execu ção ,
o NS2R gera várias fronteiras de pareto, porém, apresenta apenas a primeira fronteira,
em razão de a mesma conter as melhores soluções. Assim, cabe ao especialista do
sistema e scolher a solução (configuraç ão) que melhor atenda a sua necessidade.
O NS2R foi implementado computacionalmente dando origem ao PRN (Programa
para obtenção de planos de Restabelecimento de energia em SDRs utilizando o NS2R).
Para validar o PRN, o mesmo foi aplicado a dois SDR: o primeiro corresp on de
à cidade de São Carlos-SP, que é composto por 3860 barras e 635 chaves (que pode
ser considerado como um sistema de grande porte); e o segundo correspo nde ao SDR
da cidade de São Carlos du plica do. Importa destacar que nos testes realizados foram
consideradas todas as linhas, b arra s e chaves desse sistema.
Realizaram-se testes envolvendo faltas únicas e múltiplas e o tempo de processa-
mento médio necessário para encontrar configurações factíveis via o PRN foi de aprox-
imadamente 3 segundos. Por se tratar de uma técnica que analisa vários objetivos,
pode-se considerar como um tempo bastante pe queno .
Apresento u-se, também, um compa rativo entre o programa proposto (PRN) e o
AERT, proposto em (Santos, Delbem e Bretas, 2008b), que faz uso de um AE mono-
10.1. Publicações 131
objetivo juntamente com o método das tabelas. Os resultados de alguns testes indicam
que o PRN possibilita uma redução do número de manobras, porém com um aumento de
perdas. De uma forma mais geral, pode-se dizer que, em razão de basear-se no NSGA-
II, o PRN apresenta um melhor mapeamento do problema, em razão de possibilitar a
obtenção d as Fronteiras de Pareto.
O tempo de processamento de ambos os programas é bem próximo, isto em razão
de o PR N exigir um número menor de gerações para obtenção de boas soluções.
10.1 Publicações
1. A. C. Santos, M. Nanni, M. R. Mansour. A. C. B. Delbem, J. B. A. London
Jr., N. G. Bretas. “A Power Flow Method Computationally Efficient For Large-
Scale Distribution Systems”, 2008 IEEE PES Latin America Transmission and
Distribution Conference and Exposition, Bogota-Colombia, Aug. 2008.
2. M. R. Mansour; A. C. Santos.; J. B. A. London Jr.; A. C. B. Delbem; N. G. Bre-
tas. “Aplicação de Conjuntos Fuzzy para Definição do Critério de Parada de um
Algoritmo Evolutivo Desenvolvido para Reconfigura ção de Redes de Distribuição”,
Congresso d a Academia Trinacional das Ciências - C3N, Out., 2008.
3. M. R. Mansour, A. C. Santos.; J. B. A. London Jr.; A. C. B. Delbem; N. G. Bre-
tas. “Aplicação de Conjuntos Fuzzy para Avaliação das Funções Multi-Objetivo
de um Algoritmo Evolutivo para a Reconfiguração de Sistemas de Distribuição de
Energia Elétrica”, Simpósio Brasileiro de Pesquisa Operacional - XL SBPO, João
Pessoa-PB, Set., 2008.
4. M. R. Mansour; A. C. Santos.; J. B. A. London Jr.; A. C. B. Delbem; N.
G. Bretas. “Energy Restoration in Distribution Systems using Multi-Objective
Evolut iona ry Algorithm and an Efficient Data Structure”, PowerTech, Bucharest,
Romenia, 20 09.
REFERÊNCIAS BIBLIOGRÁFICAS 133
Referências Bibliográficas
Abuali, F. N., Wainwright, R. L. and Schoenefeld, D. A. (1995). Determinant factor-
ization: A new encoding scheme for spannin g trees applied to the probabilistic
minimum spanning tree problem,
In Eschelman, L. (Ed.), Proceedings of the Sixth
Inter natio nal Conference on Genetic Algorithms, Morgan Kaufmann, pp. 470–477.
Amabis, J. M. an d Martho, G. R. (1985).
Curso Básico de Biologia, Editora Moderna
Ltda., São Paulo.
Andrew, A. M. (2004). Introduction to evolutionary computing, by a. e. eiben and j. e.
smith (natural computing series), springer, berlin, 2003, hardback, xv + 299 pp.,
isbn 3-5 40-4 018 4-9,
Robotica 22(3): 349–349.
ANEEL (2008). Proced imentos de distribuição de energia elétrica no sistema elétrico
nacional - prodist, Qualidade de energia eletrica: Agência nacional de energia
elétrica-aneel.
Aoki, K., Nara, K., Itoh, M., Satoh, T. and Kuwabara, H. (1989). A new algorithm for
service restoration in distribution systems, Power Delivery, IEEE Transactions on
4(3): 18 32– 183 9.
Aoki, K., Nara, K. and Satoh, T. (1989). New configuration algo rithm for distribution
system - priority c onstra ined emergency service restoration,
Proceedings of IFAC
Conference on Power Systems and Power Plant Control, pp. 443–44 8.
Arciszewski, T. and Jong, K. A. D. (2001). Evolutionary computation in civil en-
gineering: research frontiers,
Civil and structural engineering computing: 2001
pp. 1 61– 184 .
134 Referências Bibliográficas
Augugliaro, A., Dusonchet, L. and Sanseverino, E. R. (2000). Multiobjective service
restoration in distribution networks using an evolutionary approach and fuzzy sets,
Inter natio nal Journal of Electrical Power & Energy Systems 22: 103–110.
Ballard, D. H. (1999).
An Introdu ctio n to Natural Computation, MIT Press, Cambridge,
MA, USA.
Baran, M. and Wu, F. (1989). Optimal sizing of capacitors placed on a radial d istribu-
tion system,
Power Delivery, IEEE Transactions on 4(1): 735–743.
Brandini, A. C. (2000).
Análise crítica de algoritmos de fluxo de carga usados em
sistemas de distribuição radial, Dissertação de Mestrado, FEIS-UNESP.
Carvalho, P., Ferreira, L. and Barruncho, L. (2001). On spanning-tree recombination
in evolutionary large-scale network problems - application to electrical distribution
planning,
Evolut iona ry Computation , IEEE Transactions on 5(6): 623–630.
Castro, R. E. (2001).
Otimização de Estruturas com Multi-objetivos via Algoritmos
Genéticos de Pa reto, Tese de Doutorado, COPPE/UFRJ.
Cespedes, R. (1990). New method for the analysis of distribution networks,
Power
Delivery, IEEE Transactions on 5(1): 391–396.
Chen, C., Lin, C., Wu, C. and Kang, M. (2000). Feeder reconfiguration for distribution
system contingencies by object oriented programming, Power Engineering Society
Summer Meeting, 2000. IEEE 1: 431–436 vol. 1.
Chen, C. S ., Wu, J. S. and Moo, C. S. (1989). Fault restoration by optimizing switch
configuration in distribu tion systems, J. Chin. Inst. Eng. 12: 781–789.
Chen, T.-H., Chen, M.-S., Hwang, K.-J., Kotas, P. and Chebli, E. (1991). Distribution
system power flow analysis-a rigid approach, Power Delivery, IEEE Transactions
on 6(3): 1 146 –11 52.
Coello, C., Veldhuizem, D. and Lamont, G. (2002).
Evolut iona ry Algorithms for Solving
Multi-Objective Problems, Kluwer Academic Publishers, New York.
Cormen, T. H. (200 2). Algoritmos: Teoria e Prática, Campus.
Referências Bibliográficas 135
Corne, D., Knowles, J. D. and Oates, M. J. (2000). The pareto envelope-based se-
lection algorithm for multi-objective opt imisation,
PPSN VI: Proceedings of the
6th International Conference on Parallel Problem Solving from Nature, Springer-
Verlag, London, UK, pp. 839–848.
Corne, D. W., Jerram, N. R., Knowles, J. D. and J, M. (2001). Pesa-ii: Region-based se-
lection in evolutionary multiobjective optimization,
Proceedings of the Genetic and
Evolut iona ry Computation Conference (GECCO2001), Morgan Kaufmann Pub-
lishers, pp. 283– 290 .
Curcic, S., Özveren, C. S., Crowe, L. and Lo, P. K. L. (1996). Electric power distribution
network restoration: a survey of papers and a review of the restoration problem,
Electric power systems research 35: 73–86.
Das, D., Nagi, H. S. and Kothari, D. P. (1994). Novel method for solving ra dial dis-
tribution networks,
Generation, Transmission and Distribution, IEE Proceedings-
141(4): 291–298.
de Lima, T. W. and Delbem, A. C. B. (2007). Estruturas de dados eficientes para
algoritmos evolutivos aplicados ao projeto de redes,
Relatório Técnico 301. Notas
Didáticas do ICMC-USP.
Deb, K. (2001).
Multi-objective optimization using evolutionary altorithms, Wiley, New
York.
Deb, K., Agrawal, S., Pratap, A. and Meyar ivan, T. (2000). A fast elitist non-
dominated sorting genetic algorithm for multi-object ive optimization: Nsga-ii,
Springer, pp . 849–85 8.
Deb, K., Mohan, M. and Mishra, S. (2005). Evaluating the e-domination based multi-
objective evolutionary algorithm for a quick computation of pareto-optimal solu-
tions,
Evol. Compu t. 13(4 ): 501–52 5.
Deb, K. and Sundar, J. (2006a). Reference point based multi-objective optimization us-
ing evolutionary algorithms,
GECCO ’06: Proceeding s of the 8th annual confere nce
on Genetic and evolutionary computation, ACM, New York, NY, USA, pp. 635–
642.
136 Referências Bibliográficas
Deb, K. and Sundar, J. (2006b). Reference point based multi-objective optimization us-
ing evolutionary algorithms,
GECCO ’06: Proceeding s of the 8th annual co nferen ce
on Genetic and evolutionary computation, ACM, New York, NY, USA, pp. 635–
642.
Delbem, A. C. B., de Carvalho, A. C. P. L. F., Policastro, C. A., Pinto, A. K. O., Honda,
K. and Garcia, A. C. (2004). Node-depth encoding for evolutionary algorithms
applied t o network design, GECCO (1), pp. 678–687.
Delbem, A., de Carvalho, A. and Bretas, N. (2005) . Main chain representation for evolu-
tionary algorithms applied to distribution system reconfiguration,
Power Systems,
IEEE Transactio ns on 20(1): 425–4 36.
Devi, S., Gupta, D. P. S. and Sargunaraj, S. (1990). A search technique for restoring
power supply in complex distribution systems,
In power systems for the year 2000
and beyond. Proc. 6t h Nat. Power Sys. Conf., McGraw-Hill, New Delhi, pp. 122–
125.
Devi, S., Sen Gupta, D. and Sarguna raj, S. (1991). Optimal resto ra tion of supply
following a fault on large distribution systems,
Advances in Power System Control,
Operation and Management, 1991. APSCOM-91., 1991 International Conference
on p p. 508–5 13 vol.2.
Dialynas, E. N. and Michos, D. G. (1989). Interactive modeling of supply restoration
procedures in distribution system operation,
Power Engineering Review, IEEE
9(7): 71 –71 .
dos Santos, A. C. (2004).
Restabelecimento de energia considerando todas as barras e
chaves de um sistemas de distribuição real, Dissertação de Mestrado, EESC/USP.
dos Santos, A. C. (2008). Algoritmo evolutivo computacionalmente eficiente para recon-
figuração de sistemas de distribuição. Texto do exame de qualificação de doutorado
em Engenharia Elétric a/USP/ EESC.
Fonseca, C. and Fleming, P. (1993). Genetic algorithms for multiobjective optimization:
Formulation, discussion and generalization,
Proceedings of the Fifth International
Conference on Genetic Algorithms, Morgan Kauffman Publishers, San Mateo -
California, pp. 4 16– 423.
Referências Bibliográficas 137
Fujii, Y., Miura, A., Miura, A., Tsukamoto, J., Youssef, M. G. and Noguchi, Y. (1992).
On-line expert system for power distribution system control,
Inter natio nal Journal
of E lectric al Power & Energy Systems 14: 45–53.
Gabriel, P. H. R. and Delbem, A. C. B. (2008). Fundamentos de algoritmos evolutivos,
Relatório téc nico . Notas Didáticas do ICMC-USP, 75.
Goldberg, D. E. (1989).
Genetic Algorithms in Search, Optimization and Machine
Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA.
Gomes, F., Carneiro, S., J., Pereira, J., Vinagre, M., Garcia, P., Oliveira , E. and Araujo,
L. (2005). A new distribution system reconfiguration approach using optima l power
flow technique and sensitivity analysis for loss reduction,
Power Engineering Society
General Mee ting , 2005 . IEEE pp. 897–901 Vol. 1.
Gradshte yn, I. S. and Ryzhik, I. M. (2000).
Tables os Integrals, Series, and Products,
Academic Press, San Diego.
Gross, J. L. an d Yellen, J. (2004).
Handbook of Graph Theory, CRC Pr ess.
Haimes, Y., Lasdon, L. and Wismer, D. (1971). On a bicriterion formulation of the
problems of integrated system identification and system optimization,
Systems,
Man and Cybernetics, IEEE Transactions on 1(3): 2 96– 297 .
Hajela, P. and Lin, C. Y. (1992). Genetic search strategies in multicriterion optimal
desig,
Structural Optimisation 4: 99–107.
Harik, G. R., Lob o, F. G. and Sastry, K. (2006).
Linkage Learning via Probabilistic
Modeling in the Extended Compact Genetic Algorithm (ECGA).
Hayes-Roth, F. (1975). Review of " ada pta tion in natural and artificial systems by john
h. ho lland ", the u. of michigan press, 1975,
SIGART Bull. (53): 15–15.
Horn, J., Horn, J., Nafpliotis, N., Nafpliotis, N., Goldberg, D. E. and Goldberg, D. E.
(1994). A niched pareto genetic algorithm for multiobjective optimiza tion,
In
Proceedings of the First IEEE Conference on Evolutionary Computation, IEEE
World Congress on Computatio nal Intelligence, pp. 82–87.
138 Referências Bibliográficas
Hsiao, Y. T. and Chen, C. Y. (2000). Enhancement of restoration service in distribu-
tion systems using a combination fuzzy-ga method,
IEEE Transactions on Power
Systems 15: 1394–1400.
Hsu, Y.-Y., Huang, H.-M., Kuo, H.-C., Peng, S., Chang, C., Chang, K., Yu, H., Chow,
C. and Kuo, R. (1992). Distribution system service restoration using a heuristic
search approa ch,
Power Delivery, IEEE Transactions on 7(2): 734–740.
Inagaki, J., Nakajima, J. and Haseyama, M. (2006). A multiobjective service restoration
method for p ower distribution systems, Circuits and Systems, 2006. ISCAS 2006.
Proceedings. 2006 IEEE International Symposium on pp. 4 pp.–.
Jensen, M. (2003). Reducing the run-time complexity of multiobjective eas: The nsga-ii
and other algorithms, Evolutionary Computation, IEEE Transactions on 7(5): 503–
515.
Julstrom, B. A. (1994). Codings and operators in two genetic algorithms for the leaf-
constrained minimum spanning tree problem,
Inter natio nal Journal of Applied
Mathematics and Computer Science 3(14): 385–396.
Kagan, N. (1999).
Configuração de Redes de Distribuição através de Algoritmos
Genéticos e Tomada de Decisão Fuzzy, Tese de Livre Docência, EP-USP.
Kagan, N., de Oliveira, C. C. B. and Robba, E. J. (2005).
Introdução aos Sistemas de
Distribuição de Energia Elétrica, Edgard Blücher, São Paulo.
Kagan, N. and Oliveira, C. C. B. (1996). Reconfiguração de sistema de distribuição
de energia elétrica através de ferramenta para solução de problemas de de-
cisão com múltiplos objetivos e incertezas.,
CONGRESSO BRASILEIRO DE
AUTOMÁTICA (11): 268–276.
Kendrew, T. J. and Graham, J. (198 9). Applying expert system technology to auto-
mated distribution feeder deployment and sectionalizing, American Power Conj.,
USA, p p. 563–5 68.
Kim, H., Ko, Y. and Jung, K.-H. (1992). Algorithm of transferring the load of the
faulted substation transformer using the best-first search method,
Power Delivery,
IEEE Transactio ns on 7(3): 1434– 144 2.
Referências Bibliográficas 139
Kita, H., Yabumoto, Y., Mori, N. and Nishikawa, Y. (1996). Multi-objective optimiza-
tion by means of the thermodynamical genetic algorithm,
PPSN IV: Proceedings
of the 4th International Conference on Parallel Problem Solving from Nature,
Springer-Ver lag, London, UK, pp. 504–512.
Knowles, J. and Corne, D. (1999). The pareto archived evolution strategy: A new base-
line algorithm for pareto multiobjective optimization,
Congress on Evolutionary
Computation, IEEE Se rvice Center, Washington, pp. 98–105.
Koza , J. R. (1989). Hierarchical genetic algorithms operating on populations of com-
puter programs, in N. S. Sridharan (ed.), Proceedings of the Eleventh International
Joint Conference on Artificial Intelligence IJCAI-89, Vol. 1, Morgan Kaufmann,
pp. 7 68– 774 .
Kumar, Y., Das, B. and Sharma, J. (2008). Multiobjective, multiconstraint service
restoration of electric power distribution system with priority customers,
Power
Delivery, IEEE Transactions on 23(1): 261–270.
Lamont, G. B. and Veldhuizen, D. A. V. (2002).
Evolut iona ry Algorithms for Solving
Multi-Objective Problems, Kluwer Academic Publishers, Norwell, MA, USA.
Laumanns, M., Rudolph, G. and paul Schwefel, H. (1998). A spatial predator-prey
approach to multi-objective optimization: A preliminary study, Proceedings of the
Paralle l Proble m Solving from Natu re, Springer, pp. 241–249.
Liu, C.-C., Lee, S. and Venkata, S. (1988). An expert system operational aid for restora-
tion an d loss reduction of distribution systems, Power Systems, IEEE Transactions
on 3(2): 6 19– 626 .
Mantovani, J., Casari, F. and Romero, R. (200 0). Reconfiguração de sistemas de
distribuição radia is utilizando o critério de queda de tensão, SBA Controle e
Automação 11: 150–159.
Michale wicz, Z. (1992).
Genetic Algorithms + Data Structures = Evolution Programs,
Springer-Ver lag, New York.
Miller, R. H. (1 987 ).
Operação de Sistemas de Potência, McGrawHill.
140 Referências Bibliográficas
Montic elli, A., Garcia, A. and Saavedra, O. (1990). Fast decoupled load flow: hypoth-
esis, derivations, and testin g,
Power Systems, IEEE Transac tion s on 5(4): 1425–
1431.
Montic elli, A. J. (1983). Fluxo de Carga em Redes de Energia Elétrica, Edgard Blücher,
São Paulo .
Morelato, A. L. and Monticelli, A. (1989). Heuristic search approach to distribution
system restor ation ,
Power Engineering Review, IEEE 9(10): 65–66.
Nahman, J. and Strbac, G. (1994). A new algorithm for service restoration in large-scale
urban d istribut ion systems, Electric power systems research 29: 181–192.
Okuda, K., Watanabe, H., Wang, F., Yamazaki, K. and Baba, T. (1988). An applica-
tion of knowledge engineering for fault restoration operation in secondary power
systems, Electr. Eng. Jpn. 108: 51–59.
Palmer, C. C. (1994).
An approach to a problem in network design using genetic
algorithms, Tese de Doutorado, Brooklyn, NY, USA.
Pelikan, M. (2005).
Hierarch ical Bayesian Optimization Algorithm: Toward a New
Generation of Evolutionary Algorithms, Studies in Fuz ziness and Soft Computing,
1 ed n, Spring er.
Pelikan, M., Goldberg, D. E. and Cantú-paz, E. E. (2000). Linkage problem, distribution
estimation, an d bayesian networks,
Evol. Compu t. 8(3): 31 1–34 0.
Picciotto, S . (1999).
How to Encode a Tree, Tese de Doutorado.
Prüfer, H. (1918). Neuer beweis eines satzes ueber permutationen,
Archiv für
Mathematik und Physik, (27): 742–744.
R. Benayoun, J. de Montgolfier, J. T. and Laritchev, O. (1971). Linear program-
ming with multiple objective functions: Step method (stem), Mathematical
Programming 1: 366–375.
R. Benayoun, J. de Montgolfier, J. T. and Laritchev, O. (1973). Linear program-
ming with multiple objective functions: Step method (stem),
Journal Mathematical
Programming 1(1): 366–375.
Referências Bibliográficas 141
Raidl, G. and Julstrom, B. (2003). Edge sets: an effective evolutionary coding of
spanning tree s,
Evolut iona ry Computation , IEEE Transactions on 7(3): 225–239.
Raidl, G. R. (2000). An efficient evolutionary algorithm for the degree-constrained
minimum spanning tree problem, Evolutionary Computation, 2000. Proceedings
of t he 2000 Congre ss on, Vol. 1, pp. 104–111 vol.1.
Ridley, M. (1996).
Evolut ion, Backwell Science, Cambridge, MA, USA.
Rothlauf, F., Goldberg, D. E. and Heinzl, A. (2002). Network random keys: a
tree representation scheme for genetic and evolutionary algorithms,
Evolut iona ry
Computation 10.
Rudolph, G. (2001). Evolutionary search under partially ordered fitness sets,
In
Proceedings of the International Symposium on Information Science Innovations in
Engineering of Natural and Artificial Intelligent Systems (ISI 20 01, ICSC Acade mic
Press, pp . 818–82 2.
Sait, S. M. and Youssef, H. (1999).
Iterative Computer Algorit hms with Applications
in Engineering: Solving Combinatorial Optimization Problems, IEEE Computer
Society Press, Los Alamitos, CA, USA.
Santos, A. C. d., Delbem, A. C. B. and Bretas, N. G. (2008a). A multiobjective
evolu tiona ry algorithm with node-depth encoding for energy restoration,
Natural
Computation, 2008. ICNC ’08. Fourth International Conference on 6: 417–422.
Santos, A. C., Nanni, M., Mansour, M. R., Delbem, A. C. B., London, J. B. A. and
Bretas, N. G. (2008). A p ower flow method computationally efficient for large-scale
distribution systems,
Transmission and Distribution Conference and Exposition:
Latin America, 2008 IEEE/PES pp. 1–6.
Santos, A., Delbem, A. and Bretas, N. (2008b). Energy re storation for large-scale
distribution system using ea and a new data structure,
Power and Energy Society
General Meeting - Conversion and Delivery of Electrical Energy in the 21st Century,
2008 IEEE pp. 1 –8.
Sarfi, R., Salama, M. and Chikhani, A. (1995). Distribution system reconfiguration
for loss reduction: an algorithm based on network portioning theory,
IEEE Power
Industry Comp ute r Application Conference pp. 503–509.
142 Referências Bibliográficas
Sarma, N. D. R., Prasad, V. C. and Pao, K. S. P. (1990). Network reconfiguration in
distribution nertwork for service restoration,
In power systems for the year 2000
and beyond. Proc. 6th Nat. Power Sys. Conf., McGraw-Hill, pp. 131–135.
Sch affer, J. D. (1 985 ). Multiple objective optimization with vector evalu ated genetic
algorithms,
Proceedings of the 1st International Conference on Genetic Algorithms,
L. Er lbau m Associates Inc., Hillsdale, NJ, USA, pp. 93–100.
Shin, D. J., Kim, J. O., Kim, T. K., Choo, J. B. and Singh, C. (2004). Optimal service
restoration and reconfiguration of n etwork using genetic-tabu algorithm, Electric
power systems research 20: 422–436.
Shirmohammadi, D. (1992). Service restorat ion in distribution networks via network
reconfiguration,
Power Delivery, IEEE Transactions on 7(2): 952–958.
Shirmohammadi, D., Hong, H., Semlyen, A. and Luo, G. (1988). A compensation-based
power flow method for weakly meshed distribution and transmission networks,
Power Systems, IEEE Transactions on 3(2): 753–762.
Sinclair, M. C. (1995). Minimum cost topology optimisation of the cost 239 european
optical n etwork,
In, Sp ring er-Verlag, pp. 26–29.
SOAK, S.-M., CORNE, D. and AHN, B.-H. (2005). A new evolutionary algorithm for
spanning-tree based communication network d esign,
IEICE Trans Commun E88-
B(10): 4 090 –40 93.
Srinivas, M. (2000). Distribution load flows: a brief review,
Power Engineering Society
Winter Meeting , 2000. IEEE 2: 942–945 vol.2.
Srinivas, N. and Deb, K. (1994). Multiobjective optimization using nondominated sort-
ing in gen etic algorithms,
Evolut iona ry Computation 2(3): 221–2 48.
Srinivasan, D., Liew, A., Chang, C. and Chen, J. (1 994) . Intelligent operation of dis-
tribution network,
Generation, Transmission and Distribution, IEE Proceedings-
141(2): 106–116.
Strogatz, S. H. (200 1). Exploring complex networks,
Nature 410: 268–276.
Teo, C. Y. (1992). A computer aided system to automate the restoration of electrical
power supply, Electric power systems research 24: 119–125.
Referências Bibliográficas 143
Teuscher, C., Mange, D. and Tempesti, G. (2003). Bio-inspired computing tissues:
Towards machines that evolve,
Grow, and Learn , BioSystems 68: 2 35– 244.
Ticona, W. G. C. and Delbem, A. C. B. (2008). Algoritmos evolutivos para otimização
multi-o bjetivo,
Relatório técnico. Notas Didáticas do ICMC-USP, 76.
Toune, S., Fudo, H., Genji, T., Fukuyama, Y. and Nakanishi, Y. (2002). Comparative
study of modern heuristic algorithms to service restoration in distribution systems,
Power Delivery, IEEE Transactions on 17(1): 173–181.
Van Veldhuizen, D. A. (1999).
Multiobjective Evolutionary Algorithms: Classifications,
Analyses, and New Innova tion s, Tese de Doutorado, Wright-Patterson AFB, OH.
Wu, J., Tomsovic, K. and Chen, C. (1991). A heuristic search appro ach to feeder
switching operations for overload, faults, unbalanced flow and maintenance,
Power
Delivery, IEEE Transactions on 6(4): 1579–1586.
Zhou, G. and Gen, M. (200 3). A genetic algorithm approach on tree-like telecommuni-
cation n etwork design problem,
Operational Research Societyn 10(53): 248– 254 .
Zhou, G., Meng, Z., Cao, Z. and Cao, J. (2007 ). A new tree encoding for the degree-
constrained spanning tree problem,
CIS ’07: Proceedings of the 2007 International
Conference on Computational Intelligence and Security, IEEE Computer Society,
Washington, DC, USA, pp. 85–90.
Zitzler, E ., Laumanns, M. and Thiele, L. (2001). Spea2: Improving the strength pareto
evolu tiona ry algorithm,
Technical report.
Zitzler, E. and Thiele, L. (1999). Multiobjective evolutionary algorithms: a c ompar ative
case study and the strength pareto approach,
Evolut iona ry Computation, IEEE
Transactions on 3(4): 257–2 71.
Livros Grátis
( http://www.livrosgratis.com.br )
Milhares de Livros para Download:
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas
Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
