Reconfiguración de redes eléctricas de media tensión...
51
Reconfiguración de redes eléctricas de media tensión utilizando técnicas evolutivas Dr. Ing. Jorge Mendoza Baeza Grupo Investigación CORE - PUCV FACULTAD DE INGENIERIA ESCUELA DE INGENIERIA ELECTRICA
Transcript of Reconfiguración de redes eléctricas de media tensión...
Reconfiguración de redes eléctricas de media tensión utilizando técnicas evolutivas
Dr. Ing. Jorge Mendoza Baeza
Grupo Investigación CORE - PUCV
FACULTAD DE INGENIERIA
ESCUELA DE
INGENIERIA ELECTRICA
Temario
1. Redes eléctricas de media tensión
2. ¿Que es la Reconfiguración?
3. Principales investigaciones
4. Optimización mono-objetivo (Algoritmos
Genéticos) aplicada a la reconfiguración
5. Optimización multiobjetivo (uGA2, SPEA2,
NSGA2, PESA2) aplicada a la reconfiguración
6. Comentarios finales
Sistema Eléctrico de Potencia
Inicio de un Red Distribución MT(Subestación 220/110/23 kV)
Estructura de una red de
distribución (Rural)
Estructura y funcionamiento
radial
Niveles de tensión entre
11.2 – 23 kV
Alimentadores con potencias
entre 2 – 10 MVA
Longitudes entre 5 – 40 km.
Estructura de una red de
distribución (Urbana)
Estructura enmallada,
funcionamiento radial
Niveles de tensión entre
11.2 – 23 kV
Alimentadores con potencias
entre 2 – 5 MVA
Longitudes entre 1 – 8 km.
Redes Distribución (Rurales)
Redes Distribución (Urbanas)
Reconfiguración
“Es un problema de optimización combinatorial en
el cual se busca una estructura radial de
funcionamiento de la red de media tensión con el
objetivo de mejorar indicadores que pueden ser
técnicos o económicos, sujeto a las restricciones
operacionales de la red”
¿Como se logra?
Equipos de Maniobra
Equipos de Protección
Equipos de seccionamiento
Otros
5 6
7
8
9 11
1012
13
1415
16
17
3 4
1
2
L1 L2 L3
L 13
L8
L9 L18
L 14
L15
L16
L 12
L 11
L 17
L4
L6
L7
5 6
7
8
9 11
1012
13
1415
16
17
3 4
1
2
L1 L2 L3
L10L 13
L8
L9 L18
L 14
L15
L16
L 12
L 11
L 17
L5
L4
L6
L7L 19
Revisión Bibliográfica1975: A. Merlin y G. Back (Heurístico)
1992: K. Nara, et at al. (Algoritmos Genéticos)
2000: A. Morton, et at al. (Búsqueda Exhaustiva)
2002: E. López, et at al. (Programación Dinámica)
2002: Y. Jeon, et at al. (Simulación Templada)
2005: Ching-Tzong, et at al. (Colonia de Hormigas)
Pérdidas
Modelos con otras
características
1997: V. Borozan et at al. (Desbalanceado)
2007: S. Bahadoorsingh et at al. (Costos)
2004: E. López et at al. (On-line)
2004: M. Arias et at al. (Compra de energía)
2001: R. Brown (Confiabilidad)
1996: R. Roytelman et. at. al (Coeficientes de Peso)
2004: Y. Hsiao, (Lógica difusa)
2006: E. Carrano et at al. (C.Construcción v/s costos fallas)Modelos
Multiobjetivo
2006: D. Das, (Lógica difusa)
2006: F. Mendoza et at al. (C. Construcción v/s ENS)
2008: J. Mendoza et at al. (uGA, Pérdidas v/s ENS)
2009: J. Mendoza et at al. (Técnicas evolutivas)
Ejemplo
Sistema Poloujadoff
3
2 4 5
1
3
2 4 5
1 3
2 4 5
1
3
2 4 5
1
1 2
3 4
DFL
2
DFL
2
DFL
2
D
DF
L1
D
DF
L1
D
DF
L1
L3
D D L3
D D
L3
D D
D
L4
D
D
L4
D
D
L4
D
D L5
D
D L5
D D L5
D
D L5
D
D
3
2 4 5
D
D
D
DF
DF
L1
L2
L3 L5
L4
1
D D
D
D
Loss (p.u)
1 0.0028
2 0.0053
3 0.0022
4 0.0025
Problema de optimización
Nr
b
bbi iRCLossesMinimizar1
2 )(
)J( imáx
C
j Cjii i
)(K ,
SF,
maxmin
i
C
k
i
CkVVV
C
i
s/a:
Ci: Configuración i
SF: Soluciones factibles (radialidad y conectividad)
Nr: Número de líneas de la red
Rb: Resistencia de la línea b
Ib: Corriente en la línea b
K, k: Barras totales y barras del sistema
J, j: Líneas totales y líneas del sistema
Características del problema
Problema combinatorial
No-lineal
Resolución Compleja
Las variables de decisión son discretas
Evaluación costosa
Algoritmos Genéticos (AG)
El AG es una técnica basada en la teoría de
evolución natural de las especies de Darwin
Esta teoría fue publicada en 1858 con el
título “El origen de las especies”
Darwin se percato que una especie que no
sufriera cambios, se volvería incompatible
con su ambiente. Así mismo las similitudes
entre hijos y padres, le sugirieron que ciertas
características eran hereditarias.
Algoritmos Genéticos (AG)
Este sistema fue desarrollado a mediados de los
60s y se dio a conocer en el libro denominado
“Adaptation in Natural and Artificial Systems” en
1975 escrito por John H. Holland
Esta técnica se basa en los mecanismos de
selección que utiliza la naturaleza, de acuerdo a
los cuales los individuos más aptos de una
población son los que sobreviven
La evolución de la población se realiza mediante
la aplicación de operadores genéticos
probabilísticos
Los aspectos más importantes son: codificación,
selección, operadores (cruza y mutación) y la
función objetivo
Algoritmo Genético
Diagrama de Flujo
Generar
Poblacion Inicial
Partida
Evaluar
Función
Objetivo
Criterio de
Término
Mejor
Individuo
Selección
Cruza
MutaciónElitismo
Resultado
Generar
Nueva
Población
si
no
Ejemplo
0
5
10
15
20
25
0 20 40 60 80 100 120 140
1207.1134.310261.210528.810266.11065.810209.2)( 2133445769 xxxxxxxy
Zx
xas
xyMinimizar
1275 .
)(
Ejemplo
Solución utilizando AG:
• Población Inicial: 10
• Número de generaciones: 6
• Probabilidad de cruza: 40% (Cruza en un punto)
• Probabilidad de mutación: 10% (Mutación en un punto)
1G APTITUD
1 1010110 86 10,07
2 0100110 38 8,75
3 1001101 77 15,51
4 0010011 19 10,40
5 0100010 34 7,52
6 1000111 71 18,18
7 1101010 106 6,52
8 0000111 7 12,90
9 0010110 22 8,99
10 0011110 30 7,12
105,96
POBLACIÓN
0
5
10
15
20
25
0 20 40 60 80 100 120 140
Ejemplo
0
5
10
15
20
25
0 20 40 60 80 100 120 140
P3:1101010
P4:0000111
H3: 1101011
H4: 0000110
1G APTITUD MUTACIÓN
(3)
1 1010110 86 10.07
2 0100110 38 8.75 P1
3 1001101 77 15.51 H1(2) 0100010 0110010 50 14.96
4 0010011 19 10.40 H2(2) 0100110 38 8.75
5 0100010 34 7.52 P2
6 1000111 71 18.18
7 1101010 106 6.52 P3 H3(5) 1101011 107 6.97
8 0000111 7 12.90 P4 H4(5) 0000110 6 12.21
9 0010110 22 8.99
10 0011110 30 7.12
105.96
POBLACIÓN CRUZA 40%
1 1010110 86 10.07 1 1010110 86 10.07
2 0100110 38 8.75 2 0100110 38 8.75
3 1001101 77 15.51 3 1001101 77 15.51
4 0010011 19 10.40 4 0010011 19 10.40
5 0100010 34 7.52 5 0100010 34 7.52
6 1000111 71 18.18 7 1101010 106 6.52
7 1101010 106 6.52 7 1101010 106 6.52
H3(5) 1101011 107 6.97 H3(5) 1101011 107 6.97
9 0010110 22 8.99 9 0010110 22 8.99
10 0011110 30 7.12 10 0011110 30 7.12
88.36
NUEVA POBLACIÓN ELITISMO
Ejemplo
2G APTITUD MUTACIÓN
1 1010110 86 10,07 1 1010110 86 10,07 1 1010110 86 10,07
2 0100110 38 8,75 2 0100110 38 8,75 2 0100110 38 8,75
3 1001101 77 15,51 3 1001101 77 15,51 7 1101010 106 6,52
4 0010011 19 10,40 4 0010011 19 10,40 4 0010011 19 10,40
5 0100010 34 7,52 5 0100010 34 7,52 5 0100010 34 7,52
7 1101010 106 6,52 (2) 7 1101010 106 6,52 7 1101010 106 6,52
7 1101010 106 6,52 P1 H5(3) 1100110 102 5,35 H5(3) 1100110 102 5,35 H5(3) 1100110 102 5,35
H3(5) 1101011 107 6,97 P2 H6(3) 0011010 0111010 58 18,4 H3(5) 1101011 107 6,97 H3(5) 1101011 107 6,97
9 0010110 22 8,99 P3 H7(5) 1101010 106 6,51 H7(5) 1101010 106 6,52 H7(5) 1101010 106 6,52
10 0011110 30 7,12 P4 H8(5) 0011111 31 7,13 10 0011110 30 7,12 10 0011110 30 7,12
88,36 75,74
ELITISMOPOBLACIÓN CRUZA 40% NUEVA POBLACIÓN
0
5
10
15
20
25
0 20 40 60 80 100 120 140
Ejemplo
3G APTITUD MUTACIÓN
1 1010110 86 10,07 P1 H9(3) 1011010 90 7,83 H9(3) 1011010 90 7,83
2 0100110 38 8,75 H9(3) 1011010 90 7,83 2 0100110 38 8,75 2 0100110 38 8,75
7 1101010 106 6,52 H10(3) 1100110 102 5,35 7 1101010 106 6,52 7 1101010 106 6,52
4 0010011 19 10,40 4 0010011 19 10,40 H5(3) 1100110 102 5,35
5 0100010 34 7,52 5 0100010 34 7,52 5 0100010 34 7,52
7 1101010 106 6,52 P2 H10(3) 1100110 102 5,35 H10(3) 1100110 102 5,35
H5(3) 1100110 102 5,35 (4) H5(3) 1100110 102 5,35 H5(3) 1100110 102 5,35
H3(5) 1101011 107 6,97 H3(5) 1101011 107 6,97 H3(5) 1101011 107 6,97
H7(5) 1101010 106 6,52 P3 H11(5) 1101110 1100110 102 5,35 H11(5) 1100110 102 5,35 H11(5) 1100110 102 5,35
10 0011110 30 7,12 P4 H12(5) 0011010 26 7,62 10 0011110 30 7,12 10 0011110 30 7,12
75,74 66,11
ELITISMOPOBLACIÓN CRUZA 40% NUEVA POBLACIÓN
0
5
10
15
20
25
0 20 40 60 80 100 120 140
Ejemplo
4G APTITUD MUTACIÓN
H9(3) 1011010 90 7,83 H9(3) 1011010 90 7,83 H9(3) 1011010 90 7,83
2 0100110 38 8,75 (6) 2 0100110 38 8,75 H5(3) 1100110 102 5,35
7 1101010 106 6,52 P1 7 1101010 106 6,52 7 1101010 106 6,52
H5(3) 1100110 102 5,35 H13(3) 1101011 107 6,96 H5(3) 1100110 102 5,35 H5(3) 1100110 102 5,35
5 0100010 34 7,52 H14(3) 1101010 106 6,51 5 0100010 34 7,52 5 0100010 34 7,52
H10(3) 1100110 102 5,35 H10(3) 1100110 102 5,35 H10(3) 1100110 102 5,35
H5(3) 1100110 102 5,35 H5(3) 1100110 102 5,35 H5(3) 1100110 102 5,35
H3(5) 1101011 107 6,97 P2 H14(3) 1101010 106 6,52 H14(3) 1101010 106 6,52
H11(5) 1100110 102 5,35 P3 H15(4) 1100110 1100100 100 5,16 H15(4) 1100100 100 5,16 H15(4) 1100100 100 5,16
10 0011110 30 7,12 P4 H16(4) 0011110 30 7,16 10 0011110 30 7,12 10 0011110 30 7,12
66,11 62,07
ELITISMOPOBLACIÓN CRUZA 40% NUEVA POBLACIÓN
0
5
10
15
20
25
0 20 40 60 80 100 120 140
Ejemplo
5G APTITUD MUTACIÓN
H9(3) 1011010 90 7,83 H9(3) 1011010 90 7,83 H15(4) 1100100 100 5,16
H5(3) 1100110 102 5,35 (4) H5(3) 1100110 102 5,35 H5(3) 1100110 102 5,35
7 1101010 106 6,52 P1 H16(4) 1101110 1100110 102 5,35 H16(4) 1100110 102 5,35 H16(4) 1100110 102 5,35
H5(3) 1100110 102 5,35 P2 H17(4) 1100010 3 8,39 H5(3) 1100110 102 5,35 H5(3) 1100110 102 5,35
5 0100010 34 7,52 5 0100010 34 7,52 5 0100010 34 7,52
H10(3) 1100110 102 5,35 H10(3) 1100110 102 5,35 H10(3) 1100110 102 5,35
H5(3) 1100110 102 5,35 P3 H18(3) 1100100 3 8,39 H5(3) 1100110 102 5,35 H5(3) 1100110 102 5,35
H14(3) 1101010 106 6,52 H19(3) 1100110 4 9,99 H14(3) 1101010 106 6,52 H14(3) 1101010 106 6,52
H15(4) 1100100 100 5,16 P4 H15(4) 1100100 100 5,16 H15(4) 1100100 100 5,16
10 0011110 30 7,12 10 0011110 30 7,12 10 0011110 30 7,12
62,07 58,23
ELITISMOPOBLACIÓN CRUZA 40% NUEVA POBLACIÓN
0
5
10
15
20
25
0 20 40 60 80 100 120 140
Ejemplo
6G APTITUD MUTACIÓN
H15(4) 1100100 100 5,16 P1 H15(4) 1100100 100 5,16 H15(4) 1100100 100 5,16
H5(3) 1100110 102 5,35 (1) H5(3) 1100110 102 5,35 H5(3) 1100110 102 5,35
H16(4) 1100110 102 5,35 H20(4) 1100010 98 5,23 H16(4) 1100110 102 5,35 H16(4) 1100110 102 5,35
H5(3) 1100110 102 5,35 H21(4) 0100100 1100100 100 5,16 H5(3) 1100110 102 5,35 H5(3) 1100110 102 5,35
5 0100010 34 7,52 P2 H21(4) 1100100 100 5,16 H21(4) 1100100 100 5,16
H10(3) 1100110 102 5,35 H10(3) 1100110 102 5,35 H10(3) 1100110 102 5,35
H5(3) 1100110 102 5,35 H5(3) 1100110 102 5,35 H5(3) 1100110 102 5,35
H14(3) 1101010 106 6,52 H14(3) 1101010 106 6,52 H14(3) 1101010 106 6,52
H15(4) 1100100 100 5,16 P3 H22(3) 1101110 110 8,65 H15(4) 1100100 100 5,16 H15(4) 1100100 100 5,16
10 0011110 30 7,12 P4 H23(3) 0010100 20 9,9 10 0011110 30 7,12 H15(4) 1100100 100 5,16
58,23 53,91
ELITISMOPOBLACIÓN CRUZA 40% NUEVA POBLACIÓN
0
5
10
15
20
25
0 20 40 60 80 100 120 140
Reconfiguración utilizando AG
... x x x x x x x x ... :1 xC
"Minimal Loss Reconfiguration using Genetic Algorithms with Restricted population and Addressed Operators: Real
Application", J. Mendoza, R. López, D. Morales, E. López, P. Dessante, R. Moraga, IEEE Trans. on Pow. Syst, Vol. 21,
Nº2, May 2006, 948-954
CODIFICACIÓN BINARIA
L6
L4
L1
1
L2
L7
L8
2 3
5 6
4
L5L3
.. ..11. 0 1 1 0 1 1 0 1 .11.. . :1
LLLLLLLL 87654321
C
L6
L4
L1
1
L2
L7
L8
2 3
5 6
4
L5L3
2002-Zhu Ref. Sw8 Sw5 Sw2
0 0 0 1 1 0 1 0 0 1 0 0
2004-Shin
2003-López
2000-Hsiao
Ref. w w w w w w w w
0 1 1 0 1 1 0 1
1992-Nara Ref. Sw1-Arc8 Sw1-Arc5 Sw1-Arc2
1 0 0 0 1 1 0 1 0 1 0 1 0 1 0 0
87654321
SSSSSSSS
Reconfiguración utilizando AG"Minimal Loss Reconfiguration using Genetic Algorithms with Restricted population and Addressed Operators: Real
Application", J. Mendoza, R. López, D. Morales, E. López, P. Dessante, R. Moraga, IEEE Trans. on Pow. Syst, Vol. 21,
Nº2, May 2006, 948-954
CODIFICACIÓN EN VALORES REALES
L6
L4
L1
1
L2
L7
L8
2 3
5 6
4
L5L3
12
3L6
L4
L1
1
L2
L7
L8
2 3
5 6
4
L5L3
3
]LLLL[3 Malla
]LLLL[2 Malla
]LLL[1 Malla
8765
6543
321
2006-MendozaRef 8 5 2:2 C
Reconfiguración: Operadores
Genéticos
Operadores Genéticos
]LLLL[3 Malla
]LLLL[2 Malla
]LLL[1 Malla
8765
6543
321
1 5 6437P1: P2:
1 5 7436H1: H2:
Cruza aleatoria
en un punto
Individuo
factibleIndividuos no factible
(Nuevo punto
aleatorio para la
cruza para este hijo)
1 4 6H1':
Cruza Mutación
1 2 3
3 4 5 6
5 6 7 8
743H2:
3 4 5 6
Bit seleccionado
para la mutación
Escoger un bit
desde el vector
de mallas 2
763H2':
L6
L4
L1
L3
1
L2
L7
L8
2 3
5 6
4
L5
Malla 1Malla 2
Malla 3
Sistemas de prueba
5 6
7
8
9 11
1012
13
1415
16
17
3 4
L1
L2 L
3
L4
L8
L13
L5
L6
L7
L9
L12 L15
L16
L18
L11
L14
L10
L19
L17
1
2
5
67
89
11
10
1213
15
16 17
3
4
1
2
14
18
19
20
21
22 23
24 25
26
27
28 29
30
31
3233
L1
L2
L3
L4
L8
L13
L5
L6
L7
L9
L15
L16
L18
L11
L14
L10
L19
L17
L20
L21
L22
L23
L24
L25
L26
L27
L28
L29
L30
L31
L32
L33
L34
L36
L35 L
37
L12
CIVANLAR BARAN
Sistema Líneas abiertas Pérdidas
Civanlar 17–18–19, [Civanlar]
10 – 11 – 19, [López], [Hong], [Zhu]
0.511 %
0.466 %
Baran 7–9–14 –32–37, [Goswami], [Zhu], [Romero]
7–10–14 –32–37, [Shirmohammadi]
1.395 %
1.402 %
López 9–17–25–27–28 –29–30–31–32–34–35, [Shirmohammadi]
9–17–22–25–27–28 –29–30–31–32–35, [López]
0.0946 %
0.0926 %
8 – 31 – 32 – 49 – 50 – 61 – 77 – 81 – 90 – 95 –178 – 201 –
531 – 599 – 638 – 645 – 649 – 662 – 674 – 757 – 767 – 820
– 822 – 828 – 840 – 851 – 873 – 888 – 922 – 924 – 927 –
928 – 929 – 937 – 938 – 940 – 942 – 943 – 945 – 946 – 947
– 952 – 956 – 958, [López]
0.3784 %
Sistema Real 30 – 35 – 50 – 79 – 90 – 95 – 178 – 198 – 203 – 429 – 505
– 598 – 637 – 645 – 649 – 673 – 688 – 757 – 767 – 820 –
828 – 851 – 919 – 921 – 922 – 923 – 924 – 928 – 929 – 931
– 936 – 937 – 938 – 939 – 940 – 941 – 942 – 946 – 947 –
952 – 956 – 958, [Merlin]
0.3692 %
Sistema Nodos Líneas Nº de
Mallas
Civanlar 17 19 3
Baran 33 37 5
López 25 35 11
Sistema Real 917 959 43
Sistema Líneas abiertas Pérdidas
Civanlar 10 – 11 – 19 0.466%
Baran 7–9–14–32–37 1.395%
López 9–22–25–27–28–29 –30–31–32–33–35 0.0919%
Sistema Real
8 – 35 – 62 – 75 – 87 – 88 – 198 – 203 – 289 – 505 – 598 –
755 – 820 – 850 – 870 – 872 – 877 – 918 – 920 – 921 – 922
– 923 – 928 – 929 – 930 – 931 – 933 – 936 – 937 – 938 –
939 – 940 – 944 – 945 – 946 – 947 – 949 – 951 – 952 – 953
– 954 – 957 – 959
0.3596 %
Aplicaciones: Reconfiguración a
mínimas pérdidas
Solución AG (Reales)
Solución otras referencias
Sistemas Individuos Generaciones Tiempos (s) Reducción
Civanlar 10 20 1.30 89 %
Baran 20 25 6.36 97 %
López 20 50 10.32 96 %
Sistemas Nº Individuos Generaciones Tiempos (s)
Civanlar 20 120 12.0
Baran 120 1000 227.4
López 100 1500 274.14
Aplicaciones: Reconfiguración a
mínimas pérdidas
Esfuerzos Computacionales (Parámetros del AG y tiempos de
simulación):
Solución
AG Real
Solución
AG Binario
Aplicaciones: Reconfiguración
Probabilista (mínimas pérdidas) Monte-Carlo
Distribución
Uniforme
Perfil de
demanda
Reconfiguración
Detreminística
Topologías
0
200
400
600
800
1000
1200
1 2 3 4 5 6 7 8 9 10 ...and
moreTopologies
Fre
qu
en
cy
Aplicaciones: Reconfiguración
minimizando Confiabilidad
Sistema Poloujadoff
3
2 4 5
1
3
2 4 5
1 3
2 4 5
1
3
2 4 5
1
1 2
3 4
DFL
2
DFL
2
DFL
2
D
DF
L1
D
DF
L1
D
DF
L1
L3
D D L3
D D
L3
D D
D
L4
D
D
L4
D
D
L4
D
D L5
D
D L5
D D L5
D
D L5
D
D
3
2 4 5
D
D
D
DF
DF
L1
L2
L3 L5
L4
1
D D
D
D
F (f/yr) T (h/yr) ENS (MWh/yr) D (h/f)
1 0.73 0.49 14.71 0.67
2 0.63 0.40 12.04 0.63
3 0.50 0.38 11.53 0.77
4 0.40 0.28 8.36 0.69
Aplicaciones: Reconfiguración
a mínima Confiabilidad
Sistema Civanlar Baran
Líneas abiertas 5 – 10 – 19 11 – 14 – 28 – 33 – 34
ENS (MWh/año) 68.865 8.615
0 5 10 15 20 2565
70
75
80
85
90
95
100
105
110
115
Generacion
EN
S (
MW
h/a
ño
)
Min ENS = 68.865
0 5 10 15 20 25 30 35 408.5
9
9.5
10
Generacion
EN
S (
MW
h/a
ño
)
Min ENS = 8.6156
CIVANLAR BARAN
Ejemplo: Aplicación
Multi-objetivo
Sistema Poloujadoff
3
2 4 5
1
3
2 4 5
1 3
2 4 5
1
3
2 4 5
1
1 2
3 4
DFL
2
DFL
2
DFL
2
D
DF
L1
D
DF
L1
D
DF
L1
L3
D D L3
D D
L3
D D
D
L4
D
D
L4
D
D
L4
D
D L5
D
D L5
D D L5
D
D L5
D
D
3
2 4 5
D
D
D
DF
DF
L1
L2
L3 L5
L4
1
D D
D
D
Loss (p.u) F (f/yr) T (h/yr) ENS (MWh/yr) D (h/f)
1 0.0028 0.73 0.49 14.71 0.67
2 0.0053 0.63 0.40 12.04 0.63
3 0.0022 0.50 0.38 11.53 0.77
4 0.0025 0.40 0.28 8.36 0.69
Problema de optimización
multiobjetivo
Nr
b
bbi iRCLossesMinimizar1
2 )(
)J( imáx
C
j Cjii i
)(K ,
SF,
maxmin
i
C
k
i
CkVVV
C
i
s/a:
Ci: Configuración i
SF: Soluciones factibles (radialidad y conectividad)
Nr: Número de líneas de la red
Rb: Resistencia de la línea b
Ib: Corriente en la línea b
K, k: Barras totales y barras del sistema
J, j: Líneas totales y líneas del sistema
Nc
i
iii kWUCEMinimizar1
)( NS
Optimización Multiobjetivo
Pasos básicos para resolver un problema de optimización multiobjetivo:
Definir las funciones objetivo
Encontrar las soluciones no inferiores del problema
Escoger alguna de las soluciones
pkxh
njxC
x
xfxfxff
k
j
T
m
...1 0)(
...1 0)(
)(),...,(),(min (x) min 21
Definición de dominancia
Un vector x=(x1,x2,..xk) se dice que domina a otro vector y=(y1,y2,..yk) si o solo si:
iiii yxkiyxki :),,1(),,,1(
En otras palabras, un vector domina a otro en el sentido de Pareto, cuando este es menor o igual respecto de todos sus componentes y estrictamente menor con respecto a al menos uno de ellos. Si x no
domina a la solución y e y no domina a x, se dice que ambos vectores son no dominados
Dominancia – Frontera de Pareto
S
x1
x2
Z
f2
f1
Espacio de las variables de
decisión
Espacio de las funciones
objetivo
: Individuos no dominados
: Individuos del conjunto factible
: Individuos que no pertenecen a la región factible
S : Región delimitada por el conjunto factible
Z : Imagen de S
Frente
de
Pareto
Algoritmos Multiobjetivos
EvolutivosMétodos basados en óptimos de Pareto:
MOGA (Multiobjective GA)
NSGA (Non-dominated sorting GA)
SPEA (Strength Pareto Evolutionary Algorithm)
NPGA (Niched Pareto GA)
PAES (Pareto Archived Evolution Strategy)
GA, GA2 (Micro GA 1 y 2)
NSGA, NSGA 2, (Non-dominated Sorting GA)
SPEA, SPEA 2 (Strength Pareto Evolutionary Algorithm)
Población Aleatoria
Reemplazable No reemplazable
Población Inicial
Selección (Torneo)
Cruza (Dos puntos)
Mutación (Uniforme)
Elitismo
Nueva Población
Convergencia
Filtro
N
S
Micro-AG
Memoria Externa
Micro Algoritmo Genético (GA - GA2)
Esta técnica basa su
mecanismo de búsqueda, a
través de la reducción del
chequeo de no dominancia
de los candidatos.
Además, considera el
posicionamiento geográfico
para mantener la diversidad
en el frente de Pareto (Malla
adaptiva)
Uso de memorias de
direccionamiento
(Reemplazable y No-
Reemplazable) GA GA2Coello Coello, C.A. and Toscano Pulido, G., “Multiobjective Optimization using a Micro-Genetic Algorithm”, in Lee
Spector, Erik Goodman, Annie Wu, William B. Langdon, Hans-Michael Voigt, Mitsuo Gen, Sandip Sen, Marco Dorigo,
Shahram Pezeshk, Max H. Garzon, and Edmund Burke, (editors), Proceedings of the Genetic and Evolutionary
Computation Conference (GECCO-2001), pp. 274--282, Morgan Kaufmann Publishers, San Francisco, California, July
2001
Non-Dominated Sorting GA2 (NSGA2)
Resuelve tres aspectos criticados en la versión anterior:
• Ordenamiento de soluciones no dominadas
• Ausencia de elitismo
• Necesidad de especificar parámetros adicionales para la preservación de diversidad en el frente.
Clasificación de la población por frente.
A cada individuo le asigna un indicador el cual dependerá del frente al cual pertenezcan
Incorpora un cálculo de distancia de apilamiento.
Población Inicial de tamaño N
Evaluar Población Inicial En Función Objetivos
Almacenar NuevosIndividuos Evaluados
Ordenar Mediante No-Dominancia
y Distancia de apilamiento
Seleccionar N/2 IndividuosMediante Torneo (Padres)
Aplicar Cruza Uniforme
Aplicar Mutación en un
punto (guiada)
Evaluar IndividuosCreados (Hijos)
Adjuntar a la Población depadres Los Hijos
Ordenar Mediante No-Dominanciay Distancia de apilamiento
Reemplazo de cromosoma
(Nueva población de tamaño N)
Criterio deCombergencia
No
Obtener Primer
Frente Solución
Si
Deb, K., S. Agrawal, A. Pratab and T. Meyarivan (2000). A Fast Elitist Non-Dominated Sorting
Genetic Algorithm for Multi-Objective Optimization: NSGA-II. Proceedings of the Parallel
Problem Solving from Nature VI Conference, pp. 849-858.
Strength Pareto Evolutionary Algorithm
(SPEA2)
Se diferencia del resto de técnicas
evolutivas, principalmente en la forma en
la que se asigna el “fitness” o aptitud a
los individuos.
Ésta considera para cada individuo de
la población
• Un índice llamado “Raw fitness”,
que representa a cuantos individuos
domina y por cuantos individuos es
dominado.
• Una técnica de estimación de
densidad, en la que se examina la
distancia de cada individuo a su
k-ésimo vecino
Archivo Externo P’(t) P(t)
Calcular Fitness de P’(t) y P(t)
Llenado de Archivo
Tamaño P’(t+1)
excede N’
Almacenar individuos no dominados en P’(t+1)
Población inicial Aleatoria
Mecanismo Truncación
Criterio de
Convergencia?
N
A:Elementos no
dominados en P’(t+1)
Selección sólo
de P’(t+1)
Aplicar Operadores Genéticos y
crear nueva población P(t+1)
t=t+1
S
SN
Zitzler, E., M. Laumanns and L. Thiele (2002). SPEA2: Improving the Strength Pareto Evolutionary Algorithm, in K.
Giannakoglou, D. Tsahalis, J. Periaux, P. Papailou and T. Fogarty (eds.) EUROGEN 2001, Evolutionary Methods for
Design, Optimization and Control with Applications to Industrial Problems, pp. 95--100, Athens, Greece.
Pareto Envelope Based Selection
(PESA 2)
Utiliza una pequeña memoria interna y
una gran memoria externa
Usa un hipercubo para mantener la
diversidad de las soluciones
Considera una selección basada en
regiones
Corne D.,Jerram N., Knowles J., Oates M., “PESA II: Region-based Selection in Evolutionary Multiobjective
Optimization”. In L. Spector E. D. Goodman, A. Wu, W. Langdon, H. Voigt, M. Gen, S. Sen, M. Dorigo, S. Pezeshk, M.
Garzon, and E. Burke, editors, Proceedings of the Genetic and Evolutionary Computation Conference (GECCO’2001),
pp. 283-290, San Francisco, California, 2001. Morgan Kaufmann Publishers.
Solución Topologías Pérdidas (%) ENS (MWh/año)
1 10 – 11 – 19 0.47 109.32
2 7 – 10 – 11 0.48 107.42
3 10 – 17 – 19 0.48 106.98
4 10 – 11 – 16 0.49 106.50
5 7 – 10 – 17 0.50 105.08
6 10 – 16 – 17 0.51 104.16
Aplicaciones: MO Civanlar
5 6
7
8
9 11
1012
13
1415
16
17
3 4
1
2
L1 L2 L3
L10 L 13
L8
L9L
18
L 14
L 15
L 16
L 12
L 11
L17
L5
L4
L6
L7
L 19
0.45 0.5 0.55 0.6102
104
106
108
110
Pérdidas (%)
EN
S (
MW
h/a
ño
)
0 1 2 3 4 5 6 7100
150
200
250
300
350
400
Pérdidas (%)
EN
S (
MW
h/a
ño
)
Aplicaciones: MO
Baran
1
9 8
7 6
5
4
3
2
10
11
13
14 15
16 17 18
19
20
21
22 23
24 25
29
30
31
32
27
28
33
L1
L2
L3
L4
L5
L6
L7
L8
L9
L10
L11
L12
L13
L14
L15
L16
L18
L19
L20
L21
L23
L24
L26
L27
L30
L31
L32
L33
L34
L35
L36
L37
12
L17
L22
26L
25
L28
L29
Topologías Pérdidas (%) ENS (MWh/año)
7-9-14-32-37 1.40 6.71
7-10-14-32-37 1.40 6.68
7-11-14-32-37 1.41 6.63
7-9-14-17-37 1.48 6.60
7-10-14-17-37 1.48 6.57
7-9-14-32-37 1.48 6.52
7-11-14-17-37 1.60 6.52
10-14-32-33-37 1.64 6.46
11-14-32-33-37 1.68 6.38
11-14-17-33-37 1.73 6.36
1.4 1.6 1.8 2 2.2
6.3
6.4
6.5
6.6
6.7
Pérdidas (%)
EN
S (
MW
h/a
ño
)
0 5 10 15 20 256
8
10
12
14
16
18
Pérdidas (%)
EN
S (
MW
h/a
ño
)
1
9
10
7
6
5
1
2
3
4
14
13
11
15
16
12
17 8169
24
23
22
19
20
21
25
168
18
60
62
67
66
61
65
63
68
69
64
70
71
167
2627
3040
35
166
28
31
32
33
165
34
29
45
46
39
37
36
38
72
44
43 42 41
73
78
76
47
84
83
82
81
80 79
777574
56
55
54
53
52
51
49
50
48
57
58
59
94
8988
87
8685
90
91
9293
95
96
97
98
99
100
163101102103
105 104106108
109 107110
111
112121
120119
118117
116
115
114
113
124
126
125
123
122
127 128
129130
131
132
133
134
135
136137
138
139164
140141142143144
145
146149
148
147150
151
152
15
31
54
15
5
15
61
57
16
1
162
15
81
59
16
0
Aplicaciones: MO Sistema Real
1.5 2 2.5 3110
115
120
125
130
135
140
145
150
Pérdidas (%)E
NS
(M
Wh
/añ
o)
Tasa de error (TE): Esta métrica mide qué porcentaje de los “n”
vectores del frente de Pareto obtenido (FPo) no pertenece al frente de
Pareto verdadero (FPv).
Número de evaluaciones (NE): Este indicador refleja la cantidad de
individuos que son necesarios evaluar para encontrar el frente de
pareto resultante en cada técnica.
Tiempo de simulación: Aunque este indicador está asociado al
número de evaluaciones realizadas, es posible evidenciar algunas
diferencias producto de los diversos procedimientos evolutivos. Por esta
razón será expresado como tiempo de simulación total (TST) y como
tiempo de simulación por evaluación (TSE).
Indicadores de Comparación
n
e
TE
n
i
i 1
caso otroen 1
),...1( FP i vector el si 0 v niei
Civanlar μGA 2 PESA 2 NSGA 2 SPEA 2
ER 0 0 0 0
NE 58 (43%) 72 (54%) 50 (37%) 67 (50%)
TST (s) 3.9 4.1 2.4 2.1
STE (ms) 67 57 48 31
Baran
ER 0 0 0 0
NE 438 (2.7%) 601 (3.7%) 235 (1.4%) 231 (1.4%)
TST (s) 43 95 20 19
STE (ms) 98 159 85 82
Real
ER 0 0 0 0
NE 2702 2665 1504 1423
TST (min) 74 72 33 21
STE (s) 1.66 1.62 1.32 0.88
Indicadores de Comparación
Total Evaluaciones
Exhaustivo: 134
Total Evaluaciones
Exhaustivo: 16300
Total
Evaluaciones
25.000
Comentarios finales
1. La configuración o reconfiguración, es una herramienta que permite tomar decisiones en etapas de diseño, planificación y operación de la red
2. Las técnicas evolutivas son muy eficientes al momento de resolver problemas combinatoriales de gran envergadura
3. La clave para obtener buenos resultados utilizando técnicas evolutivas es la codificación
4. Una adecuada codificación permite generar operadores genéticos especializados
5. Existe un fuerte desarrollo de técnicas evolutivas para encontrar soluciones eficientes asociadas a la frontera de Pareto de problemas complejos.
6. El desempeño de cada técnica evolutiva depende de la problemática de aplicación
Reconfiguración de redes eléctricas de media tensión utilizando técnicas evolutivas
Dr. Ing. Jorge Mendoza Baeza
Grupo Investigación CORE - PUCV
FACULTAD DE INGENIERIA
ESCUELA DE
INGENIERIA ELECTRICA
