Nono Simpósio de Mecânica Computacional
26 a 28 de maio de 2010
Universidade Federal de São João del-Rei MG
Associação Brasileira de Métodos Computacionais em Engenharia
UMA OTIMIZAÇÃO MULTIOBJETIVO PARA A DEFINIÇÃO DE UMA LINHA DE
TRANSMISSÃO ELÉTRICA VIA NSGA-II
André R. da Cruz
[email protected]
Mestrando em Engenharia Elétrica, UFMG, MG, Brasil
Oriane M. Neto
[email protected]
Departamento de Engenharia Elétrica, UFMG, MG, Brasil
Ricardo H. C. Takahashi
[email protected]
Departamento de Matemática, UFMG, MG, Brasil
Resumo. O presente trabalho otimiza concomitantemente as funções determinísticas de custo
e confiabilidade para uma linha de transmissão fictícia através do algoritmo genético multiobjetivo NSGA-II (Deb et al. (2000)). As soluções do conjunto Pareto ótimo apresentam um
conjunto de conexões, que possuem uma determinada taxa de falha e custo, que devem ser
inseridas na rede para que melhore o desempenho em relação a interrupções e os gastos da
transmissão de uma rede inicial com nós e ligações pré-determinados.
Keywords: Rede elétrica de transmissão, otimização multiobjetivo, algoritmos genéticos.
Nono Simpósio de Mecânica Computacional
1.
Universidade Federal de São João del-Rei MG ABMEC
INTRODUÇÃO
Apesar dos avanços tecnológicos e do aumento dos padrões de confiabilidade que ocorreram nas últimas décadas, a frequência das quedas das linhas de transmissão de energia não
diminuíram, embora a dimensão das interconexões e as interdependências entre as mesmas tenham aumentado (Hines and Blumsack (2008)).
Técnicas econômicas e eficazes são necessárias para a proteção do sistema através de modificações nos padrões de conexões da rede com o intuito de exigir menos esforço nos modos de
operação. A identificação dessas soluções envolve uma análise profunda e sistemática da rede
elétrica e da respectiva resposta à falhas.
A análise da vulnerabilidade e da robustez em relação às falhas da infraestrutura desses sistemas complexos, altamente distribuídos e interconectados, é considerada um problema difícil,
principalmente em casos em que somente métodos probabilísticos tradicionais são aplicados.
Dessa maneira, novas metodologias para análise de redes surgiram recentemente para caracterizar a resistência em relação às falhas e para identificar os elementos mais vulneráveis. Essas
técnicas podem ser encontradas nos trabalhos de Freeman (1979), Koonce et al. (2008), Hines
and Blumsack (2008) e Cadini et al. (2009).
O presente trabalho, utiliza uma metodologia para otimizar o custo e a confiabilidade de
uma rede fictícia de transmissão de energia elétrica, em que as ligações entre os nós são previamente determinadas. Dessa maneira, a metodologia pode ser aplicada nos casos em que se
deseja construir uma nova rede de transmissão ou efetuar uma manutenção sem adicionar conexões que não existiam previamente. O método identifica estratégias de combinação de novas
linhas, com diferentes taxas de falha, que serão adicionados para aumentar a confiabilidade do
serviço de transmissão ao mesmo tempo em que se minimiza os respectivos custos de implementação.
Esse problema possui um custo computacional elevado, uma vez que aumentando a dimensão o número de possíveis soluções cresce com custo combinatório (Cadini et al. (2010)). Por
esse fato, os algoritmos determinísticos de otimização não são boas alternativas para problemas
a partir de certa dimensão considerada. Portanto, as heurísticas, como por exemplo, as famílias
de algoritmos evolucionários, são boas alternativas para se buscar o ótimo ou uma solução satisfatória. No presente trabalho, usou-se o algoritmo genético multiobjetivo NSGA-II, elaborado
por Deb et al. (2000), para maximizar a confiabilidade global da rede (Zio (2007)) e minimizar
o custo com a instalação das conexões.
Essa metodologia foi aplicada em um modelo fictício de rede de transmissão de energia com
16 barramentos locais (vértices) ligados por 21 linhas e transformadores (arestas). A Figura 1
apresenta o grafo que descreve a topologia dessa rede.
O presente artigo está organizado da seguinte forma: a seção 2. apresenta as funções objetivos utilizadas no trabalho, ou seja, o modo como se avalia a confiabilidade global da rede
e o custo de inserção das conexões; a seção 3. apresenta rapidamente os algoritmos genéticos,
em especial o NGSA-II, e os fundamentos da otimização multiobjetivo; a seção 4. apresenta o
conjunto Pareto ótimo do problema com as soluções que possuem a identificação dos tipos de
cabos que devem ser inseridos na rede para que a confiabilidade e o custo sejam otimizados;
por fim, a seção 5. apresenta as conclusões finais e sugestões de trabalhos futuros.
2.
CONFIABILIDADE E CUSTO GLOBAL DE UMA REDE DE TRANSMISSÃO
Considere a rede apresentada na Figura 1, como o sistema de rede de transmissão. Ela
possui 16 barramentos locais ligados por 21 conexões. O grafo G(N, E), em que |N | = 16 é
o número de vértices e |E| = 21 é o número de arestas, pode ser representado por uma matriz
Nono Simpósio de Mecânica Computacional
Universidade Federal de São João del-Rei MG ABMEC
3
1
2
4
6
5
7
10
9
8
16
12
15
11
14
13
Figura 1: Modelo fictício de rede de transmissão de energia usado no trabalho.
de conexões A|E|×3 . Em A|E|×3 a k-ésima linha corresponde a uma conexão, de modo que a
primeira coluna armazena o vértice que liga ao outro da segunda coluna e vice-versa. A terceira
coluna armazena o peso da conexão, que no presente caso é a distância geográfica wij entre os
nós i e j. Ao contrário do trabalho de Cadini et al. (2010), que usou uma matriz de adjacência
(Latora and Marchiori (2001)) de ordem |N |, o presente trabalho usou uma representação mais
direta e econômica. A matriz transposta de conexões do problema pode ser visualizada na
Figura 2.


1

AT = 
 2
60
1
2
2
3
4
5
5
5
6
7
7
8
8
9
10
11
12
12
14
4
3
9
4
5
6
9
10
7
8
14
15
16
11
12
13
13
14
15
70
100
300
90
60
150
50
200
70
200
170
90
50
90
80
60
150
90
120
Figura 2: Matriz de conexões que modela a rede de transmissão de energia do problema.
Segundo Cadini et al. (2009), para extrair a informação sobre o comportamento de falha da
rede, os valores de probabilidade de sucesso pij , associados às conexões ij, devem ser incluídos
na análise do grafo. Assumindo, por simplicidade, que o tempo de falha segue uma distribuição
exponencial, temos que a probabilidade da linha (aresta) ij não falhar é:
pij = e−λij T
(1)
em que λij é a taxa de falha associada a linha ij e T é uma referência de tempo, no qual
assume-se no trabalho como sendo 1 ano.
Com base na matriz de conexões A = {aij } e na matriz de probabilidades de sucesso das
linhas P = {pij } (ou a matriz complementar de falhas Q = {qij }), a matriz D = {drmn } das
distâncias (de probabilidade) dos caminhos mais confiáveis entres os nós m e n (Zio (2007))
pode ser calculado como
(
)
(
)
1
1
drmn = min
= min
(2)
γmn
γmn
Πij∈γmn pij
Πij∈γmn (1 − qij )
em que a minimização é executada a partir do conjunto γmn de todos os possíveis caminhos
que ligam os vértices m a n e o produtório descreve a probabilidade de não acontecer falhas na
15

16 

70
Nono Simpósio de Mecânica Computacional
Universidade Federal de São João del-Rei MG ABMEC
trajetória sobre as arestas ij que constituem esse caminho. Note que 1 ≤ drij ≤ ∞, sendo o
menor valor correspondente a um caminho de confiabilidade perfeita conectando o vértice m a
n (pij = 1 para todas as arestas do caminho ótimo), e o maior valor corresponde a situação de
inexistência de caminho conectando m a n.
Em analogia com a definição de eficiência de redes, apresentado no trabalho de Latora and
Marchiori (2001), a confiabilidade de eficiência E r (G) de um grafo G pode ser definido como
(Zio (2007)):
E r (G) =
∑
1
εr
N (N − 1) m,n=1,N ;m̸=n mn
(3)
em que εrmn é a medida de confiabilidade do melhor caminho que liga o vértice m ao n e é
definido como
εrmn =
1
drmn
(4)
ou seja, é o inverso da distância de probabilidade do melhor caminho de confiabilidade que liga
m a n. Pode-se calcular facilmente esse valor através do algoritmo de menor caminho (Floyd
(1962)).
Os tipos de cabeamentos considerados no presente trabalho possuem taxas de interrupções
(falhas) anuais dadas pela Equação 5. Esse é o espaço de busca do problema, ou seja, devemos
determinar qual é o tipo de cabo para cada conexão que otimizará a confiabilidade e o custo da
rede de transmissão de energia da Figura 1.
λ1
λ2
λ3
λ4
λ5
=
=
=
=
=
0, 1564 interrupções/ano
0, 2267 interrupções/ano
0, 3740 interrupções/ano
0, 4338 interrupções/ano
0, 5400 interrupções/ano
(5)
O custo de investimento relacionado com inserção de uma nova linha de transmissão é,
em geral, dependente da qualidade requerida em termos de confiabilidade e do comprimento
dos cabos. Assim, o custo é assumido como diretamente proporcional ao comprimento wij e
inversamente proporcional à taxa de falha λij do cabeamento utilizado. Logo, a função de custo
da rede de transmissão é caracterizado pela Equação 6.
∑ wij
C(G) =
(6)
λ
ij
ij∈E
A função de custo mostrada no presente trabalho se aproxima mais da realidade do que a
que foi mostrado no trabalho de Cadini et al. (2010), uma vez que as informações das distâncias
geográficas sobre a localização dos nós são consideradas.
Assim, as Equações 3 e 6 são as funções objetivos a serem otimizadas pelo NSGA-II,
sendo que a primeira (confiabilidade) deve ser maximizada e a segunda (custo) minimizada. As
funções são conflitantes, de modo que para aumentar a confiabilidade é necessário uma rede de
custo maior.
Nono Simpósio de Mecânica Computacional
3.
Universidade Federal de São João del-Rei MG ABMEC
ALGORIMOS GENÉTICOS E OTIMIZAÇÃO MULTIOBJETIVO
Segundo o naturalista Charles Darwin (Darwin (1868)), a seleção natural é definida como
a preservação de indivíduos mais adaptados ao ambiente. Ou seja, na natureza, indivíduos mais
fortes e diversificados possuem maiores chances de competir, sobreviver e se reproduzir. Durante a evolução, indivíduos com características mais fracas geralmente são eliminados. Tais
características são controladas por unidades, denominadas genes, que formam um conjunto chamado cromossomo. Após gerações subsequentes, não somente os melhores indivíduos sobrevivem, mas também os melhores genes são transmitidos para os descendentes durante o processo
de recombinação ou cruzamento sexual (crossover). Essa analogia entre mecanismos de seleção natural e o processo de aprendizagem leva ao desenvolvimento dos Algoritmos Genéticos
(AGs).
Os AGs, introduzidos por John Holland em Holland (1962a) e Holland (1962b), são métodos computacionais de otimização baseados no mecanismo genético e na evoluçãao natural.
Nesse algoritmo, um conjunto de soluções tentativas (população) envolve regras probabilísticas
inspiradas em metáforas biológicas: em cada geração, os indivíduos tendem a ficar melhores ao
longo do período em que o processo de evolução continua. Em geral, AGs possuem as seguintes características (Goldberg (1989), Holland (1992)): (i) - AGs trabalham com um conjunto
de pontos (população); (ii) - AGs trabalham com um espaço de busca codificado; (iii) - AGs
necessitam somente da informação sobre a função objetivo para cada membro da população; e
(iv) - AGs executam transições probabilísticas.
Em qualquer AG, alguns operadores comuns são: inicialização, avaliação da função de
adequabilidade, seleção, mutação e recombinação. Em alguns outros, por exemplo, pode haver
busca local, nicho, dizimação, etc., dependendo do objetivo da aplicação. O trabalho de Goldberg (1989) citou quatro razões que fazem os AGs atrativos para aplicações: (i) - AGs podem
resolver problemas difíceis em um pequeno tempo de forma confiável; (ii) - a interface para a
construção de AGs com o modelo de problemas existentes é, geralmente, simples; (iii) - AGs
são extensíveis; e (iv) - AGs são fáceis de se hibridizar.
Em problemas de otimização multiobjetivo, não existe uma solução que é a melhor, no
sentido de ser o ótimo global com respeito a todos os objetivos. A otimização de um problema
com múltiplos funcionais geralmente leva a uma família de soluções não dominadas, chamado
de conjunto Pareto ótimo (ou simplesmente conjunto Pareto), em que cada componente de qualquer solução dentro do conjunto de Pareto pode ser aperfeiçoado somente pela degradação de
pelo menos um dos outros componentes. Nenhum ponto do conjunto de soluções não dominadas é absolutamente melhor do que outro nesse conjunto (Branke et al. (2008)).
Matematicamente, em um problema de otimização com vetor de função objetivo J ∈ Rm ,
se y ∈ Rn denota o vetor variável de decisão do problema e D ∈ Rn é o conjunto de todas
as soluções factíveis y, o conjunto de soluções Pareto ótimo ou não dominadas Y ⊂ D é
caracterizado, em minimização, por:
Y = {ȳ ∈ D
| @y ∈ D : Ji (y) ≤ Ji (ȳ) (1 ≤ i ≤ m)
e
J(y) ̸= J(ȳ)}
(7)
No presente trabalho, adotou-se o algoritmo genético multiobjetivo denominado NSGA-II
proposto em Deb et al. (2000). A ideia do Nondominated Sorting Genetic Algorithm (NSGA)
foi sugerida no trabalho de Goldberg (1989) e implementado em Srinivas and Deb (1994).
A principal característica é a ordenação pela não dominância, ou seja, o método de seleção
pelo ranking é utilizado para enfatizar bons pontos e um método de nicho é usado para manter
uma sub-população estável desses pontos. A eficiência do NSGA é determinada pela avaliação
dos múltiplos objetivos reduzido a uma única medida, pela definição dos números ordinais
de fronteiras (níveis do Pareto), ordenados de acordo com a não dominância. O NSGA-II
Nono Simpósio de Mecânica Computacional
Universidade Federal de São João del-Rei MG ABMEC
foi proposto por Deb et al. (2000), no qual foram introduzidos o fast nondominted sorting
procedure, um mecanismo de preservação elitista, e um operador de nicho sem a necessidade
de parâmetro para a preservação da diversidade da população (crowding distance comparison
operator), o qual é bem mais eficiente computacionalmente. Além disso, o NSGA-II também
incorpora um mecanismo de penalidade sem a necessidade de parâmetro.
No NSGA-II, particularizado para otimizar os funcionais representados pelas Equações 3
e 6, os indivíduos são vetores do R21 , em que cada índice representa uma conexão da rede
apresentado nas Figuras 1 e 2. Os índices dos vetores assumem valores que representam um
tipo de cabo entre aqueles apresentados pela Equação 5, que é espaço de busca do algoritmo.
As redes são inicializadas com cabos aleatoriamente distribuídos. O cruzamento, que ocorre
com uma probabilidade pc = 0, 75, é baseado em trocas de informação gênica a partir de
um índice dos vetores de dois pais, selecionados por torneio binário. A mutação, que possui
probabilidade pm = 0, 10 de acontecer, possibilita trocar as informações dos índices dos vetores
com valores do espaço de busca. São executadas 500 gerações sobre uma população de 80
vetores candidatos, aplicando-se todas as operações do NSGA-II. Ao final das gerações, tem-se
o conjunto Pareto com as melhores redes de transmissão não dominadas.
4.
RESULTADOS
Ao final da execução do NSGA-II, para o problema de otimização das linhas de transmissão
da rede apresentado nas Figuras 1 e 2, é encontrado o conjunto Pareto ótimo descrito pela Figura
3. O eixo horizontal representa os valores da função de confiabilidade gerados pela Equação 3 e
o eixo vertical apresenta os custos das redes avaliados pela Equação 6. A solução em losango é a
chamada solução utópica. As 80 soluções em asterisco são as soluções retornadas pelo NSGAII. Esse fato mostra a eficiência do otimizador, uma vez que o mesmo transformou todos os
candidatos em pontos bem espaçados sobre a fronteira ótima.
4
1.6
x 10
1.4
Custo
1.2
1
0.8
0.6
0.4
0.25
0.3
0.35
0.4
0.45
0.5
Confiabilidade
0.55
0.6
0.65
Figura 3: Conjunto Pareto ótimo para o problema de otimização da rede de transmissão de energia.
O Pareto apresenta soluções de redes não dominadas, do ponto de vista da otimização
multiobjetivo, com custos e confiabilidades distintos. Desse modo, o decisor pode escolher
dentro do conjunto a rede ideal de acordo com o investimento alocado para tal. Obviamente,
as redes mais confiáveis estão no lado direito da Figura 3 e são as mais custosas. Em geral,
elas possuem na estrutura os tipos de cabos mais custosos e consequentemente mais confiáveis,
principalmente em nós mais importantes do ponto de vista topológico da rede. Do outro lado
estão as redes mais baratas, porém mais instáveis.
Além da taxa de falha dos cabos, a distância geográfica entre os nós foi um fator importante
Nono Simpósio de Mecânica Computacional
Universidade Federal de São João del-Rei MG ABMEC
na determinação das soluções presentes no Pareto e por esse motivo as redes, nesse conjunto,
possuem diversas combinações de cabeamentos presentes no espaço de busca.
A solução mais custosa xc é apresentada na Figura 4, que possui o tipo de cabo mais confiável com taxa de falha de 0, 1567 interrupções/ano em todas as conexões, exceto nas conexões
1 − 2, 7 − 14, 8 − 15 e 15 − 16, que possuem cabos com confiabilidade 0, 2267 interrupções/ano. A função de confiabilidade avaliou essa rede em 0, 6330 e a função de custo a avaliou
em 1, 4037 · 104 .
xTc =
(
λ2
λ1
λ1
λ1
λ1
λ1
λ1
λ1
λ1
λ1
λ1
λ2
λ2
λ1
λ1
λ1
λ1
λ1
λ1
λ1
λ2
)
Figura 4: Solução mais custosa e mais confiável do Pareto que possui confiabilidade 0, 6330 e custo
1, 4037 · 104 .
A solução mais barata xb é apresentada na Figura 5, que possui o tipo de cabo menos
confiável com taxa de falha de 0, 5400 interrupções/ano em todas as conexões, exceto na conexão 12 − 14, que possui o cabo com taxa de falha de 0, 4338 interrupções/ano. A função de
confiabilidade avaliou essa rede em 0, 2679 e a função de custo a avaliou em 4, 3371 · 103 .
xTb =
(
λ5
λ5
λ5
λ5
λ5
λ5
λ5
λ5
λ5
λ5
λ5
λ5
λ5
λ5
λ5
λ5
λ5
λ5
λ4
λ5
λ5
Figura 5: Solução mais barata e menos confiável do Pareto que possui confiabilidade 0, 2679 e custo
4, 3371 · 103 .
Para se ter uma ideia de como os tipos de cabos se distribuíram sobre as soluções é apresentado a Figura 6, que mostra o gráfico da quantidade de cabos por tipo que foram alocados
nas conexões das 80 redes presentes no Pareto ótimo.
Quantidade de cabos usados por todas as soluções
1200
1000
800
600
400
200
0
0
1
2
3
λ
4
5
6
Figura 6: Quantidade de cabos por tipo distribuídos entre as 80 soluções Pareto ótimo.
5.
CONCLUSÕES E TRABALHOS FUTUROS
O presente trabalho otimizou as funções determinísticas de custo e confiabilidade para
uma rede de transmissão fixa. O método forneceu redes que são ótimas no ponto de vista da
otimização multiobjetivo. Cada rede possui um custo e uma confiabilidade associada que deve
)
Nono Simpósio de Mecânica Computacional
Universidade Federal de São João del-Rei MG ABMEC
ser levado em conta no momento de decidir qual linha de transmissão será implementada ou
qual tipo de manutenção executada.
O trabalho contribui no fato de selecionar as melhores redes de transmissão de acordo com
as funções de avaliação fornecidas. O método apresentado é mais rápido do que os métodos
estocásticos de simulação para avaliar as redes de transmissão e sem perda de generalidade
otimiza a topologia dado que as conexões entre os nós não se alteram.
As funções objetivos usadas no presente trabalho se aproximam mais da realidade, ao levar
em conta a informação geográfica da rede. Assim, os resultados obtidos são mais coerentes dos
que aqueles que foram apresentados no trabalho de Cadini et al. (2010).
Para trabalhos futuros, deseja-se:
• aplicar o método em modelos reais de rede de transmissão e comparar com outros resultados da literatura;
• otimizar redes de transmissão com outros objetivos que avaliam o custo e confiabilidade
para comparar os resultados encontrados;
• otimizar redes de transmissão com funcionais estocásticos que necessitam de simulação
de Monte Carlo e efetuar uma comparação crítica com os resultados obtidos na otimização
em que se usou funções objetivos determinísticas;
• aplicar otimização dinâmica para otimizar a rede de transmissão dado uma série temporal
de tendência de crescimento de demanda.
Referências
Branke, J., Deb, K., Miettinen, K., & Slowiński, R., eds, 2008. Multiobjective Optimization:
Interactive and Evolutionary Approaches. Springer-Verlag, Berlin, Heidelberg.
Cadini, F., Zio, E., & Petrescu, C., 2010. Optimal expansion of an existing electrical power
transmission network by multi-objective genetic algorithms. Reliability Engineering & System Safety, vol. 95, n. 3, pp. 173 – 181.
Cadini, F., Zio, E., & Petrescu, C.-A., 2009. Using centrality measures to rank the importance
of the components of a complex network infrastructure. Critical Information Infrastructure
Security: Third International Workshop, CRITIS 2008, Rome, Italy, October13-15, 2008.
Revised Papers, vol. 5508/2009, pp. 155–167.
Darwin, C., 1868. The variation of animals and plants under domestication. J. Murray, London.
Deb, K., Agrawal, S., Pratab, A., & Meyarivan, T., 2000. A fast elitist non-dominated sorting
genetic algorithm for multi-objective optimization: Nsga-ii. In Schoenauer, M., Deb, K.,
Rudolph, G., Yao, X., Lutton, E., Merelo, J. J., & Schwefel, H.-P., eds, Proceedings of the
Parallel Problem Solving from Nature VI Conference, pp. 849–858, Paris, France. Springer.
Lecture Notes in Computer Science No. 1917.
Floyd, R. W., 1962. Algorithm 97: Shortest path. Communications of the ACM, vol. 5, n. 6, pp.
345.
Freeman, L., 1979. Centrality in social networks: Conceptual clarification. Social Networks,
vol. 1, n. 3, pp. 215–239.
Nono Simpósio de Mecânica Computacional
Universidade Federal de São João del-Rei MG ABMEC
Goldberg, D. E., 1989. Genetic Algorithms in Search, Optimization and Machine Learning.
Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA.
Hines, P. & Blumsack, S., 2008. A centrality measure for electrical networks. In HICSS ’08:
Proceedings of the Proceedings of the 41st Annual Hawaii International Conference on System Sciences, pp. 185, Washington, DC, USA. IEEE Computer Society.
Holland, J. H., 1962a. Concerning efficient adaptive systems. Spartan Press.
Holland, J. H., 1962b. Outline for a logical theory of adaptive systems. J. ACM, vol. 9, n. 3, pp.
297–314.
Holland, J. H., 1992. Adaptation in natural and artificial systems. MIT Press, Cambridge, MA,
USA.
Koonce, A., Apostolakis, G., & Cook, B., 2008. Bulk power risk analysis: Ranking infrastructure elements according to their risk significance. International Journal of Electrical Power
& Energy Systems, vol. 30, n. 3, pp. 169 – 183.
Latora, V. & Marchiori, M., 2001. Efficient behavior of small-world networks. Phys. Rev. Lett.,
vol. 87, n. 19, pp. 198701.
Srinivas, N. & Deb, K., 1994. Multiobjective optimization using nondominated sorting in genetic algorithms. Evolutionary Computation, vol. 2, pp. 221–248.
Zio, E., 2007. From complexity science to reliability efficiency: a new way of looking at
complex network systems and critical infrastructures. International Journal of Critical Infrastructures, vol. 3, n. 3, pp. 488–508.
6.
DIREITOS AUTORAIS
Os autores são os únicos responsáveis pelo conteúdo do material impresso incluído no seu
trabalho.