XIII SIMPÓSIO DE ESPECIALISTAS EM PLANEJAMENTO DA OPERAÇÃO E EXPANSÃO ELÉTRICA XIII SEPOPE 18 a 21 de Maio 2014 May – 18th to 21st – 2014
XIII SYMPOSIUM OF SPECIALISTS IN ELECTRIC OPERATIONAL AND EXPANSION PLANNING
FOZ DO IGUAÇU (PR) BRAZIL
Aplicação do Método de Penalização Hiperbólica na Classificação de Curvas de Carga Luiz Antonio Alves de Oliveira Centro de Pesquisas de Energia Elétrica-CEPEL, Av. Horácio de Macedo, 354, Cidade Universitária, Rio de Janeiro RJ, CEP 21941-911 e-mail
[email protected] Adilson Elias Xavier Universidade Federal do Rio de Janeiro-UFRJ Coordenação dos Programas de Pós-Graduação e Pesquisa em Engenharia-COPPE Av. Horácio de Macedo, 2030, Cidade Universitária, Rio de Janeiro RJ, CEP 21941-972 e-mail
[email protected] José Francisco Moreira Pessanha Centro de Pesquisas de Energia Elétrica-CEPEL, Av. Horácio de Macedo, 354, Cidade Universitária, Rio de Janeiro RJ, CEP 21941-911 e-mail
[email protected] SUMÁRIO Os perfis típicos da demanda diária por eletricidade são informações fundamentais em diversas etapas do planejamento e da operação de sistemas elétricos de potência. Por exemplo, no cálculo das tarifas que remuneram o serviço de distribuição de eletricidade, na avaliação das perdas de energia, no despacho das unidades geradoras, na previsão de demanda e no dimensionamento do sistema. Uma forma automática e eficiente de identificar os perfis diários típicos presentes nos registros de carga consiste na aplicação de técnicas de reconhecimento de padrões, como a análise de agrupamentos na série horária da carga. Na literatura técnica são encontrados diferentes métodos para análise de agrupamentos que podem ser empregados na identificação de perfis de carga, por exemplo, os métodos estatísticos de classificação hierárquica e não hierárquica, mapa auto-organizável e fuzzy clustering method. Contudo, recentemente, o método da penalização hiperbólica, baseado em programação matemática, tem se apresentado como um dos mais promissores algoritmos de análise de agrupamentos. Portanto, neste trabalho propõe-se descrever e investigar o uso do método de penalização hiperbólica na identificação dos perfis diários típicos da carga. Palavras-Chave
Operação de Sistemas Interligados, Análise de Agrupamento, Programação não diferenciável, Progamação não linear.
1. Introdução A forma de como a demanda por energia elétrica evolui ao longo do dia é uma informação fundamental em diversas etapas do planejamento e da operação de sistemas elétricos de potência. Por exemplo, no cálculo das tarifas que remuneram o serviço de distribuição de eletricidade, na avaliação das perdas de energia, no despacho das unidades geradoras, na previsão de demanda e no dimensionamento da capacidade do sistema. Esta informação encontra-se na curva de carga diária (Fig. 1) que descreve a trajetória da demanda por energia elétrica ao longo das horas do dia.
Figura 1. Exemplo de Curva de Carga
O perfil da curva de carga reflete os usos da energia elétrica pelos consumidores, a composição do mercado por classe de consumo e variam segundo os dias da semana (Fig. 2), períodos do ano, feriados, dias especiais (jogos da seleção, final de novela, e outros eventos) e variáveis climáticas. Por exemplo, os feriados e dias especiais caracterizam-se por apresentarem perfis horários semelhantes aos observados no final de semana. Portanto, as curvas de carga diárias apresentam padrões regulares e previsíveis, denominados tipologias.
Figura 2. Perfis de carga por dia da semana
1
Uma forma automática e eficiente de identificar as tipologias presentes nos registros de carga consiste na aplicação de técnicas de reconhecimento de padrões, em particular a análise de agrupamentos na série horária da carga. De forma resumida, os métodos de análise de agrupamentos têm por finalidade a classificação de objetos em grupos, de tal forma que os objetos semelhantes sejam classificados no mesmo grupo, enquanto objetos distintos sejam classificados em grupos diferentes. Para avaliar a semelhança entre os objetos, os algoritmos de análise de agrupamentos empregam alguma medida de dissimilaridade ou distância, sendo que objetos semelhantes são aqueles que guardam uma proximidade entre eles, enquanto objetos diferentes são aqueles que estão distantes. Por meio da análise de agrupamentos é possível identificar uma estrutura natural de agrupamento no conjunto de medições de curva de carga e como resultado obter a identificação de um reduzido conjunto de perfis típicos ou tipologias que descrevem o comportamento diário da demanda. Na literatura técnica [1,2,3] são encontrados diferentes métodos para análise de agrupamentos que podem ser empregados na identificação de perfis de carga, por exemplo, os métodos estatísticos de classificação hierárquica e não hierárquica [4], mapa auto-organizável [1,5] e fuzzy clustering method [5]. Contudo, entre os vários métodos disponíveis, o método da penalização hiperbólica [6,7], baseado em programação matemática, tem se apresentado como um dos mais promissores algoritmos de análise de agrupamentos. Portanto, neste trabalho propõe-se descrever e investigar o uso do método de penalização hiperbólica na identificação dos perfis diários típicos da carga. O artigo está organizado em quatro seções. A seguir, na seção 2, é descrita a análise de agrupamentos baseada no método de penalização hiperbólica (HSCM - Hyperbolic Smoothing Clustering Method) [6,7]. Para ilustrar a aplicação do método proposto, na seção 3 são apresentados os resultados de um experimento computacional conduzido com registros de carga do Sistema Interligado Nacional (SIN) durante um período de 2 anos. Por fim, na seção 4, são resumidas as principais conclusões do trabalho.
2. Método de penalização hiperbólica para análise de agrupamentos Seja S = {s1,..., sm} um conjunto de m objetos em um espaço euclidiano de dimensão n a serem agrupados em um determinado número q de grupos disjuntos (clusters). Adicionalmente, seja xi, i = 1 ,..., q os centróides dos q grupos, onde cada xi Є Rn. O conjunto das coordenadas dos centróides é representado por X Є Rnq. Em um problema de análise de agrupamentos, o objetivo consiste em encontrar as coordenadas dos centróides que proporcionem a maior homogeneidade interna dos clusters e a maior separação entre eles. Assim, dado um objeto sj Є S, deve-se classificá-lo no cluster com o centróide mais próximo. Portanto, inicialmente calcula-se a distância euclidiana de sj ao centroid em X que está mais próximo: z j = min s j − xi xi∈X
2
(1)
O cálculo da distância zj é exemplificado na Fig. 3, onde sj representa um objeto conectado aos centroides x1, x2, x3 e x4. A homogeneidade interna dos grupos é alcançada com a minimização da soma dos quadrados das distâncias zj dos objetos aos centroides dos clusters nos quais os objetos são classificados. Assim, a análise de agrupamentos pode ser formulada como um problema MSSC (Minimum Sum of Squares Clustering) [6,7]: m
Minimizar
∑
z 2j
(2)
j =1
sujeito a z j = min s j − xi , j = 1,..., m i =1,...,q
2
2
Figura 3. Cálculo da distância Zj entre o objeto sj e o centroide mais próximo Cada zj deve necessariamente satisfazer o seguinte conjunto de inequações: z j − s j − xi
≤ 0, i = 1,..., q
2
(3)
Substituindo as restrições de igualdade do problema (2) pelas inequações (3), produz-se o seguinte problema relaxado: m
∑
Minimizar
z 2j
(4)
j =1
sujeito a z j − s j − xi
2
≤ 0, j = 1,..., m; i = 1,..., q
Desde que a variável zj não é limitada inferiormente, a solução ótima do problema relaxado será zj=0 , j=1,...,m. A fim de alcançar este resultado, deve-se modificar o problema (4). Primeiro, com a introdução de uma função φ(y)=max{0,y} no conjunto de inequações em (4): q
∑ϕ (z - || s j
j
- x i ||2 ) = 0, j = 1,..., m
(5)
i =1
Usando (5) no lugar do conjunto das restrições de desigualdades em (4) tem-se um problema equivalente, inclusive com zj, j=1,...,m ilimitado inferiormente. Considerando que a função objetivo do problema (4) irá forçar cada zj j=1,...,m, para baixo, pode-se pensar em um delimitador por meio da inclusão de uma pertubação ε em (5), conforme a seguir: m
Minimizar
∑
z 2j
(6)
j =1
sujeito a q
∑ϕ(z - || s - x || ) ≥ ε , j = 1,...,m para ε >0. j
j
i
2
i=1
Desde que a viabilidade do problema (2) é o limite de (6) quando ε→0+ pode-se considerar resolver (2) por uma seqüência de problemas parecidos com (6) em que os valores de ε seguem uma trajetória decrescente e se aproximam de zero. Analisando o problema (6), a definição da função φ impõe uma estrutura extremamente rígida e não diferenciável, o que torna a sua solução
3
computacional muito difícil. Em vista disso, o método numérico adotado para resolver o problema utiliza uma abordagem de suavização. A partir dessa perspectiva, define-se a função:
φ ( y,τ ) = ( y + y 2 + τ 2 ) / 2 para y real e τ >0
(7)
A função φ (7) possui as seguintes propriedades: (a) φ ( y,τ ) > ϕ (y) ∀ τ > 0 (b)
φ ( y,τ ) = ϕ ( y ) lim τ →0
(c) φ ( y,τ ) é um incremento convexo C∞ na função de variável y Substituindo a função ϕ (y) no problema (6) pela função φ definida em (7), obtém-se a seguinte formulação: m
∑
Minimizar
z 2j
(8)
j =1
sujeito a q
∑φ (z - || s j
j
- x i ||2 ,τ ) ≥ ε , j = 1,..., m
i =1
A distância euclideana ||sj-xi|| é o único componente não diferenciável do problema (8). Então para obter um problema completamente diferenciável é ainda necessário suavizar. Para esse propósito, define-se a função θ: n
θ ( s j , xi , γ ) =
∑ (s
l
j
- x li ) 2 + γ 2 para γ >0
(9)
l =1
A função θ (8) possui as seguintes propriedades (a)
lim θ ( s
j
, xi , γ ) = s j − xi
y→0
2
(b) θ Є C∞
Em (8), substituindo a distância
s j − xi
pela função θ obtém-se o seguinte problema
2
diferenciável: m
Minimizar
∑
z 2j
(10)
j =1
sujeito a q
∑φ(z
j
−θ ( s j , xi , γ ),τ ) ≥ ε , j = 1,..., m
i =1
As propriedades da função φ e da função θ permitem procurar a solução do problema (6) pela solução de uma seqüência de subproblemas semelhantes a (10), produzidos pelo decréscimo dos
4
parâmetros γ →0 , τ →0 e ε→0. Desde que zj ≥ 0 j=1,...,m, na função objetivo, o processo de minimização irá reduzindo estes valores. Por outro lado, dado qualquer conjunto de centróides xi i=1,...,q usando a propriedade (c) da função de suavização hiperbólica φ , as restrições do problema (10) são funções monótonas crescentes em zj. Estas restrições serão ativas e o problema (10) irá ser equivalente ao seguinte problema: m
∑
Minimizar
z 2j
(11)
j =1
sujeito a q
h j ( z j , x ) = ∑ φ ( z j −θ ( s j , xi , γ ),τ ) − ε = 0, j = 1,..., m i =1
A dimensão do espaço da variável de domínio do problema (11) é (nq + m). Como, em geral, o valor do parâmetro m, a cardinalidade do conjunto S das sj observações, é grande, o problema (11) tem um grande número de variáveis. No entanto, o problema tem uma estrutura separável, pois cada variável zj aparece apenas em uma restrição de igualdade. Portanto, como a derivada parcial de h(zj, x) com respeito a zj, j = 1,..., m não é igual a zero, pode-se utilizar o teorema da função implícita para calcular cada componente zj, j = 1,..., m em função dos centróides xi, i = 1, ... q. Desta forma, segue o problema irrestrito: m
Minimizar. f ( x) = ∑ z j ( x) 2
(12)
j =1
onde cada zj(x) resulta do calculo do zero em cada equação abaixo: q
h j ( z j , x ) = ∑ φ ( z j −θ ( s j , xi , γ ),τ ) − ε = 0, j = 1,..., m
(13)
i =1
Usando a propriedade (c) da função de suavização hiperbólica, cada termo φ acima é estritamente crescente com a variável zj e, portanto, a equação possui um único zero. Novamente, devido ao teorema da função implícita, as funções zj(x) possuem todas as derivadas com relação às variáveis xi, i = 1 ,..., q e dessa forma, é possível calcular o gradiente da função objetivo do problema (12): m
∇f ( x) = ∑ 2 z j ( x).∇z j ( x) ,
(14)
j =1
onde
∇z j ( x ) =
− ∇h j ( z j , x ) ∂h j ( z j , x) ∂z j
,
(15)
Assim, o problema (12) pode ser resolvido por qualquer método baseado em derivadas de primeira ordem. Finalmente deve-se enfatizar que o problema (12) é definido em um espaço (nq)-dimensional. É um problema pequeno desde que o número de clusters q é, em geral, pequeno para aplicações reais. Assim, a solução do problema original de agrupamento pode ser obtido pelo uso do algoritmo de agrupamento com suavização hiperbólica (HSC) [6,7], descrito abaixo: Inicialização:
Faça k=1 e escolha valores iniciais no intervalo ]0,1[ para x0,γ0, τ1 e ε
5
1
Principal: Repita até que o critério de parada seja satisfeito Resolva problema (12) com γ=γk , τ=τk e ε = ε k começando com um ponto inicial xk-1 e seja xk a solução obtida. Faça k:=k+1; γk+1=ρ1 γk ; τk+1= ρ2 τk ; ε
k+1
= ρ3 ε k ;
A solução do problema de clusterização é obtida em teoria pela solução de uma seqüência infinita de problemas de otimização. No algoritmo HSC, cada problema minimizado é irrestrito e de baixa dimensão. Os parâmetros ρ1 , ρ2 e ρ3 respectivamente fazem com que γ, τ e ε se aproximem de zero, portanto, as restrições dos subproblemas como dadas em (11) tendem para (8). Dessa forma, o algoritmo faz com que ε vá para zero de forma simultânea. Assim, o problema resolvido aproxima-se gradualmente do problema original.
3. Experimento Computacional Nesta seção são apresentados os principais resultados obtidos pela aplicação do método HSCM na classificação, em 10 clusters, dos perfis diários da carga do SIN registrados ao longo de um período de 2 anos. Antes da aplicação do HSCM, os perfis diários foram previamente padronizados pelas respectivas demandas médias diárias. Na sequência, na Tabela I são apresentadas as composições dos agrupamentos indentificados por dia da semana. Já na tabela II, são mostradas as composições dos agrupamentos segundo as estações do ano. A visualização das curvas classificadas em cada cluster é apresentada na Fig. 5, juntamente com os centróides em cada cluster (perfis médios)
Grupo
Freqüência
1 2 3 4 5 6 7 8 9 10
161 118 86 72 60 76 75 53 28 1
Domingo
44.74 % 92.40 % 78.57 %
Segunda
Terça
Quarta
Quinta
25.47 % 22.88 % 17.44 % 20.83 % 1.67 % 2.63 % 1.33 %
26.09 % 22.88 % 20.93 % 16.67 %
22.98 % 22.88 % 27.91 % 12.50 % 1.67 %
24.22 % 23.73 % 29.07 % 11.11 % 1.67 % 1.33 %
3.57 % 100.00 %
3.57 %
1.33 % 5.66 % 7.14 %
1.24 % 7.63 % 4.65 % 38.89 % 95.00 % 2.63 % 1.33 % 1.89 %
3.95 % 1.33 %
Sexta
Sábado
46.05 % 93.33 %
7.14 %
Tabela I Composição dos agrupamentos segundo os dias da semana
Grupo 1 2 3 4 5 6 7 8 9 10
Freqüência 161 118 86 72 60 76 75 53 28 1
Primavera 4.97 % 22.03 % 22.09 % 83.33 % 15.00 % 46.05 % 14.67 % 9.43 % 25.00 %
Verão 31.36 % 77.91 % 16.67 % 53.95 % 10.67 % 35.71 % 100.00 %
Outono 40.99 % 30.51 %
Inverno 54.04 % 16.10 %
43.33 %
41.67 %
37.33 % 41.51 % 35.71 %
37.33 % 49.06 % 3.57 %
Tabela II Composição dos agrupamentos segundo as estações do ano
6
Figura 5. Grupos identificados na massa de dados e respectivos centróides (em verde) 2.6
1.4
2.4 1.2 2.2
1
2
1.8
p.u.
p.u.
0.8
1.6
0.6 1.4
1.2
0.4
1 0.2 0.8
0
2
4
6
8
10
12 tempo (horas)
14
16
18
20
22
0 0
24
Grupo 1 – Dias úteis, Outono - Inverno
2
4
6
8
10
12 tempo (horas)
14
16
18
20
22
24
Grupo 2 – Dias úteis típicos 1.4
1.2
1.3
1
1.2
0.8
1.1
p.u.
p.u.
1.4
0.6
1
0.4
0.9
0.2
0
0.8
0
2
4
6
8
10
12 tempo (horas)
14
16
18
20
22
0.7
24
Grupo 3 – Dias úteis, Verão
0
2
4
6
8
10
12 tempo (horas)
14
16
18
20
22
24
Grupo 4 – Dias úteis, Primavera 1.3
2.5
1.2
2
1.1 p.u.
1.4
3
p.u.
3.5
1.5
1
1
0.9
0.5
0
0.8
0
2
4
6
8
10
12 tempo (horas)
14
16
18
20
22
0.7
24
Grupo 5 – Segunda-feira, Outono -Inverno
0
2
4
6
8
10
12 tempo (horas)
14
16
18
20
22
24
Grupo 6 – Sábados, Domingos, Primavera-Verão
1.4
1.5
1.3
1.2 1
p.u.
p.u.
1.1
1
0.5 0.9
0.8
0.7
0
2
4
6
8
10
12 tempo (horas)
14
16
18
20
22
0 0
24
Grupo 7 – Sábados, Outono - Inverno
2
4
6
8
10
12 tempo (horas)
14
16
18
20
22
24
Grupo 8 – Domingo, Outono - Inverno
1.4
1.3
1.2
p.u.
1.1
1
0.9
0.8
0.7
0
2
4
6
8
10
12 tempo (horas)
14
16
18
20
22
24
Grupo 9 – Domingo Típico
Grupo 10 – Outlier
Conforme indicado nas Tabelas I e II, o grupo 1 é constituído por perfis dos dias úteis, com predominância no outono e no inverno. O grupo 2 também é formado por perfis dos dias úteis, porém com uma distribuição mais equilibrada entre as estações do ano. O grupo 3 é mais um cluster formado por perfis dos dias úteis, contudo com predominância do verão (77,91% dos perfis analisados). De forma distinta, no grupo 4 há uma predominância de dias úteis na primavera. O grupo 5 é constituído principalmente por perfis da segunda-feira (95% dos perfis analisados) concentrados no outono e no inverno. Ressalta-se que os centroides dos grupos 1 e 5 são similares. As diferenças entre eles devemse a presença deletéria de falhas em algumas curvas classificadas no grupo 5. Dessa forma, fica
7
patente a imprescindibilidade de uma etapa de tratamento de dados anterior ao processamento pela análise de agrupamentos. O grupo 6 é constituído por observações associadas aos sábados e aos domingos em que predominan os dias de primavera e verão. O grupo 7 é principalmente constituído por observações associadas aos sábados (93,33% dos perfis analisados) bem distribuidos entre as estações do ano. Já o grupo 8 é principalmente constituído por observações associadas aos domingos (92,40%) com predomínio no período de outono e inverno. O grupo 9 é principalmente constituído por observações associadas aos domingos (78,57%) e com reduzida participação dos perfis de inverno. Por fim, o grupo 10 apresenta apenas uma curva com observações aberrantes. Ademais, um grupo com apenas uma observação definitivamente não possui qualquer significância para efeitos práticos e representa um dado aberrante. Essa situação ressalta a importância do tratamento de dados de curva de carga. As associações entre grupos e dias da semana mostradas na Tabela I podem ser visualizadas no mapa perceptivo obtido pela análise de correspondência simples e ilustrado na Fig. 6, onde os pontos representam cada um dos 10 grupos e os triângulos representam os sete dias da semana. Na Fig. 6, os dias úteis, sábados e domingos ocupam regiões distintas no mapa, refletindo o fato de que os perfis dos dias úteis, sábados e domingos são diferenciados.
Figura 6. Mapa Perceptivo entre grupos e dias da semana
A seguir, na Fig. 7, o contraste entre os perfis dos grupos 1 (com 95% dos perfis no período outono-inverno) e 3 (com 78% dos perfis no verão), ambos formados por dias úteis, permite visualizar o efeito do horário de verão sobre a demanda de ponta. Naturalmente, o mesmo efeito não é observado no constraste dos centroides dos gruops 3 (verão) e 4 (com 83% dos perfis na primavera), conforme ilustrado na Fig. 8. Ao final dessa seção, vale registrar que, de forma geral, os resultados computacionais da determinação das tipologias de carga corroboram o conhecimento aprioristico sobre os perfis das curvas de carga, nos diferentes dias da semana e períodos do ano.
8
Figura 7. Contraste entre os centroides do grupo 1 (Verão) e do grupo 3 (Outono-Inverno).
Figura 7. Contraste entre os centroides do grupo 3 (Verão) e do grupo 4 (Primavera).
4. Conclusões Neste artigo foi apresentado o método de penalização hiperbólica (HSCM - Hyperbolic Smoothing Clustering Method) [6,7], cuja finalidade consiste em realizar a classificação não supervisionada de uma lista de objetos. O método é uma alternativa atratente aos tradicionais algoritmos frequentemente empregados na construção de tipologias de curvas de carga, tais como o K-Means, o método de Ward, as Nuvens dinâmicas e os métodos baseados em lógica fuzzy e redes neurais artificiais para análise de agruapmentos. O método HSCM foi aplicado em uma massa de dados com 730 perfis de carga diários do Sistema Interligado Nacional e mesmo na presença de ruídos nos dados o HSCM conseguiu
9
identificar perfis típicos que corroboram o conhecimento aprioristico sobre os perfis das curvas de carga, nos diferentes dias da semana e períodos do ano.
5. Bibliografia [1] DEBREGEAS, A. and HÉBRAIL, G. “Interactive Interpretation of Kohonen Maps Applied to Curves”, International Conference on Knowledge Discovery and Data Mining, New York, August, 1998. [2] JAIN, A.K.; DUIN, R.P.W.; MAO, J. “Statistical Pattern Recognition: A Review”, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 22, no 1, January 2000. [3] PESSANHA, J.F.M.; VELASQUEZ, R.M.G.; MELO, A.C.G.; CALDAS, R.P. "Técnicas de Cluster Analysis na construção de tipologias de curva de carga”, XV Seminário Nacional de Distribuição de Energia Elétrica, Salvador 2002. [4] JOHNSON, R., WICHERN, D.W. Applied Multivariate Statistical Analysis. Fourth ed. PrenticeHall, Englewood Cliffs, NJ, 1998. [5] JANG, J.S.R.; SUN, C.T.; MIZUTANI, E Neuro-Fuzzy and Soft Computing: A Computational Approach to Learming and Machine Intelligence, Prentice Hall Inc, 1997. [6] XAVIER, A. E., “The hyperbolic smoothing clustering method”, Pattern Recognition, Volume 43, Issue 3, March 2010, Pages 731-737, ISSN 0031-3203. [7] XAVIER, A. E., XAVIER, V. L. 2011 “Solving the minimum sum-of-squares clustering problem by hyperbolic smoothing and partition into boundary and gravitational regions”, Pattern Recognition, v.44, p. 70-77.
10
