- 72 -

Ingeniería energética Vol. XXXII, No. 1/2011 p 72 – 76 Enero – Marzo ISSN 1815 - 5901

APLICACIÓN DE LA COMPUTACIÓN

Un Algoritmo Genético Especializado en Planeamiento de Redes de Distribución

Parte I. Fundamentos Técnicos del Algoritmo

A specialized Genetic Algorithm in Distribution Network planning. Part I.

Algorithm Base

Raúl Nicolás Carvajal- Pérez

Recibido: junio del 2009

Aprobado: julio del 2009

Resumen/ Abstract

La planificación de redes eléctricas de distribución utilizando técnicas naturales es un tema de actualidad científica.
Se destacan entre estas técnicas los algoritmos genéticos. El problema del planeamiento se representa mediante
modelos matemáticos de gran cantidad de restricciones. Su solución aconseja la utilización de algoritmos genéticos
especializados. Aquí se presenta un algoritmo genético de este tipo elaborado por el autor para realizar estudios de
expansión y reconfiguracion de redes. Se explican los procedimientos elaborados y la magnitud de los parámetros
generales a partir del trabajo experimental.
Palabras clave: redes, planificación, algoritmo genético, redes de distribución

The distribution network planning using natural techniques is an actual scientific thematic; specially Genetic
Algorithms. The representative mathematical model in this case has a lot of restrictions. In this paper is presented a
specialized genetic algorithm to realize distribution network expansion studies. The author explains the basic
procedures and experimental work to determine the general parameters magnitude.
Keywords: networks, planning, genetic algorithm, distribution networks

INTRODUCCIÓN
En sentido general, un algoritmo genético es una técnica de búsqueda del óptimo de una función basado en la teoría
de la evolución natural. El algoritmo genético trata de encontrar la mejor solución factible a un problema. Comienza
con la creación de una población inicial de un grupo de individuos y la evaluación de su “Fitness”. Sigue un proceso
de evolución de la población a partir de la formación de nuevos individuos o hijos que resultan del apareamiento por
dos de los miembros de la población anterior. Este apareamiento aunque es aleatorio, se realiza de forma tal que los
individuos de mejor “Fitness” tengan más posibilidades de ser electos como padres que los de peor “Fitness”. Los
hijos que surjan deben heredar los genes de sus padres y algunos de ellos deben mutar de forma aleatoria alguno
de sus genes. Finalmente, el conjunto de individuos formados por padres e hijos de una población, son sometidos a
un proceso de Selección; de acuerdo a su “Fitness”, para formar con ellos una nueva generación [1 – 4].

Este concepto evolucionista permite fijar los pasos que de forma general debe tener un algoritmo genético [3].
 Raúl Nicolás Carvajal- Pérez
- 73 -
Paso1. Preparación de la base genética y generación aleatoria de una población inicial.
¾ Cada problema tiene que tener definido el cromosoma y los genes característicos.
¾ Se fijan condiciones de factibilidad y se eligen de forma aleatoria N individuos que
las cumplan.

Paso2. Evalué el “Fitness” de cada individuo en la población obtenida antes.

¾ Requiere de la definición previa de cómo medir el “Fitness” en cada problema.

Paso3. Cree una nueva población, desarrollando los siguientes procedimientos:

3.1. Selección aleatoria de dos cromosomas padres de la población anterior dando más posibilidades a los de
mejor “Fitness”.
3.2. Crossover o precombinación. Con cada pareja (de padres) seleccionada, forme nuevos hijos que
enriquecen la población actual y a la vez sean aspirantes a la nueva generación. Cuando una pareja no forme
nuevos hijos diferentes a ellos, tome estos como copias de sus padres.
3.3. Mutación Defina una probabilidad de mutación y si aleatoriamente le corresponde, realice mediante
alguna regla, cambios genéticos al hijo seleccionado ubicando los genes cambiados en su “Locus”.
3.4. Sitúe el nuevo hijo como miembro de la población actual.
3.5. Sobrevivencia. Tome la población actual formada por los padres e hijos y sométala a un proceso de
evaluación y de acuerdo a las reglas del problema, decida cuales formarán parte de la siguiente población
como padres de la misma.
En este análisis se debe tener en cuenta que los individuos mas aptos de la población actual (Élite) deben
pasar a formar parte de la nueva generación para asegurar el avance genético de las nuevas generaciones.
3.6. Reemplazo: Tome la nueva población y colóquela en lugar de la anterior.

Paso4. Test o Chequeo: de condiciones alcanzadas.

Se proponen condiciones respecto a la meta que debe alcanzar la evolución.
4.1. Si las condiciones de optimalidad son alcanzadas. Terminar
4.2. Sino, Regrese al paso 2 con la nueva población.
Operadores Genéticos. Hay conjuntos de operaciones que realizar en cada uno de los pasos del algoritmo
genético. Estas son realizadas por los llamados operadores genéticos.

CODIFICACIÓN DE UN CROMOSOMA

Sirve para simplificar el trabajo matemático del algoritmo. Se recoge la información genética en forma codificada. Hay
varios tipos de código pero el más utilizado es el código binario. Por ejemplo
Suponga que se quieren ubicar 3 bancos de condensadores fijos en 5 postes posibles y se disponen de 2
capacidades de vasos (25 y 30) kVAr. Se requiere la ubicación de un banco. El cromosoma debe contemplar como
base genética.

Poste 1 2 3 4 5
Vasos 25 30 25 30 25 30 25 30 25 30
Locus 1 2 3 4 5 6 7 8 9 10
Cromosoma 0 0 0 1 0 0 1 0 1 0 string de 10 dígitos

El código acordado representa la ubicación de un banco de 30 kVAr por fase en el poste 2, uno de 25 por fase en el
poste 4 y otro de 25 por fase en el poste5.
Esta codificación permite el manejo de string de bits para realizar múltiples operaciones genéticas y finalmente
decodificar los resultados dando los parámetros del problema. También permite que se utilicen procedimientos de
carácter general que independiza la evolución genética de los parámetros físicos del problema trabajando con la
matriz de los cromosomas. Realizar un proceso de codificación adecuada al tipo de problema en estudio es
fundamental para un buen trabajo del AG.

La Selección. El concepto establece que se realiza la selección de forma aleatoria pero brindando mas posibilidades
a los aspirantes a padres de mejor “Fitness”. Aparecen en la literatura varios métodos: regla de la ruleta, Sección de
Boltzman, selección por Ranking, selección de estado estable, etc. La primera es recomendada para este tipo de
problemas.

Regla de la ruleta. Suponga una ruleta de 360 grados; si la población tiene N individuos con Fitness (k); k=1... N. Se
asigna un rango (k) a cada individuo en proporción a su “Fitness” de forma que
N
Ingeniería energética Vol. XXXII, No. 1/2011 p 72 – 76 Enero – Marzo ISSN 1815 - 5901
 Raúl Nicolás Carvajal- Pérez
- 74 -

Σ Rango (k) = 360

k=1

Cada individuo tiene un rango, con inicio y final, en la ruleta que está entre 1 y 360.
Se generan números aleatorios entre 1 y 360. El individuo que tenga asignada una porción (rango) que contenga ese
número es elegido como padre.

EL “CROSSOVER” Y LA MUTACIÓN

Son los dos operadores básicos, sin ellos no hay algoritmo genético. El “crossover”, también llamado recombinación,
crea un nuevo individuo recombinando los genes de sus padres tal y como ocurre con muchas especies naturales.
Hay varios métodos de realizar la precombinación.

Crossover de simple punto: Los hijos heredan aproximado al 50 % de los genes de sus padres pero en dos pedazos
de cromosomas, cada uno toma una parte de un padre y el resto del segundo padre. Por ejemplo, suponga un
cromosoma con base de 8 genes y que cada padre posee.

Base 1 2 3 4 5 6 7 8
Padre1 1 1 0 0 1 0 1 1
Padre2 1 0 1 1 0 1 1 1
Hijo1 1 1 0 0 0 1 1 1
Hijo2 1 0 1 1 1 0 1 1
Note que hubo un solo corte del cromosoma de cada padre (M=1).

Crossover Multipunto. Es el mismo concepto del anterior pero se realizan varios cortes a los padres y los hijos van
tomando alternativamente trozos de cromosomas de los padres hasta cubrir todo el cromosoma. Por ejemplo para
M=3, hay tres cortes y por tanto 4 trozos de cromosomas que se van tomando alternamente de los padres 1 y 2.

Padre1 1 1 0 0 1 0 1 1 0 0 11
Padre2 1 1 0 1 1 1 1 1 1 10 0
Hijo1 1 1 0 1 1 1 1 1 0 1 0 0 . Si se quiere un segundo hijo
Hijo2 1 1 0 0 1 0 1 1 1 0 1 1

En estos casos, los hijos no son copia de sus padres pero puede ocurrir.
Un aspecto muy importante, en el planeamiento de redes, es el relacionado con los puntos de corte. Los cromosomas
están compuestos por genes y estos pueden ocupar varios bits del string. Para que los hijos sean factibles, los
cortes se realizan en puntos tales que ocupen los bits de un gen completo. En el ejemplo anterior, ocurre esto pues
cada gen tiene varios bits en el string. En el planeamiento, la cantidad de bits en cada gen puede ser diferente.

LA MUTACIÓN
También se estudiaron diferentes métodos para efectuar la mutación:
Cambio de orden, Permutación de código, Inversión de bits., Código de valor, etc. Se escogió el de permutación
de código con selección aleatoria del gen donde se realiza la permutación y del bit que permuta para tener en cuenta
las condiciones de factibilidad. Recomendaciones. En la literatura se dan algunas recomendaciones generales; entre
ellas:
• La mutación debe tener una probabilidad de ocurrencia entre 0,5 y 1 % de los individuos de la población; en
los algoritmos especializados en redes eléctricas, hay autores que recomiendan mutar hasta un 10 % de los
hijos y algunos recomiendan que la mutación sea menor en las primeras generaciones y en la medida que
haya tendencia al estatismo, se incremente la cantidad de mutantes.
• Se recomienda que las poblaciones sean siempre superiores a 20 o 30 individuos y en los trabajos
relacionados con redes electricas se dan cifras superiores.
• La mayoría recomienda como método de Selección básica de padres el método de la ruleta y el de selección
por Rankin.
• El elitismo es imprescindible en la evolución. Siempre debe pasar a la siguiente generación, al menos, el
mejor de la generación actual para preservar el avance de la especie.

Ingeniería energética Vol. XXXII, No. 1/2011 p 72 – 76 Enero – Marzo ISSN 1815 - 5901
 Raúl Nicolás Carvajal- Pérez
- 75 -

BASE GENÉTICA DE UNA RED ELÉCTRICA DE DISTRIBUCIÓN

Una red de distribución tiene NR centros de servicio (nodos) caracterizados como puntos de ubicación de la carga
con un nivel de demanda y las condiciones de variación de esta durante el día así como un nivel de tensión de
suministro que le son impuestos a la red. Para prestar el servicio, existen gran cantidad de posibilidades (variantes)
.Las que cumplan los requisitos técnicos serán factible. Por ejemplo, si se tiene una subestación que presta servicio
a 5 cargas.

1
4

2
S 5

Fig.1. Representación de una pequeña red.

La red de la figura1 tiene como base genética un conjunto de planes de alimentación a las cargas. Cada plan
depende de las posibilidades de alimentación a cada nodo o gen; por ejemplo:

Nodo 1 2 3 4 5 Se pueden alimentar desde

S,2 S,1 1,4 3,1,2 S,2,4

Combinando las posibilidades que la base genética o red base, se obtienen redes radiales. Cada plan es un
cromosoma. Una de ellas

Nodo recibo 1 2 3 4 5
Envio S 1 1 1 S
Linea Nr. 1 4 5 6 3

Se pueden formar muchos planes de servicio a partir de los posibles corredores para los enlaces. Cada uno de ellos
tendrá parámetros comunes y diferentes a los demás.
Las cargas se caracterizan por: Demanda Máxima( Dmax), Factor de carga (Fc), Demanda activa (P) y demanda
reactiva (Q). Son comunes a todos los planes de suministro que se generen.
Las líneas de enlace: Se diferencian por el envió, recibo, calibre, Existencia actual, longitud. El calibre a su vez
2
ofrece: Resistencia (R), Reactancia (X), Resistividad del conductor (ρ), Sección en mm (Sec), densidad económica
de corriente (Jec) y el costo.

Las subestaciones son caracterizadas por: Potencia de Suministro, kVA instalados y de ahí se obtienen sus
parámetros: Capacidad nominal Sn, Perdidas de vacío; Po, pérdidas de cobre; Pk, y costo de inversión.

Se establecen algunos conceptos en este algoritmo genético especializado:

• El conjunto formado por un grupo de líneas, subestaciones y nodos de servicio que cumpla las condiciones
fijadas es un individuo que se representara por un cromosoma. Hay elementos comunes para todos los
individuos como la ubicación y parámetros del servicio y otros elementos que diferencian cada individuo
como las subestaciones de alimentación y los enlaces.
• Se puede establecer una similitud entre los elementos que caracterizan cada plan de alimentación con el
valor de los parámetros característicos de los nodos o genes.

Ingeniería energética Vol. XXXII, No. 1/2011 p 72 – 76 Enero – Marzo ISSN 1815 - 5901
 Raúl Nicolás Carvajal- Pérez
- 76 -

• Hay manifestación de algunos parámetros que forman grupos específicos con valores establecidos en
catálogos o tablas (Conductores, transformadores etc.)
• La cualidad de cada individuo esta dada en el cumplimiento de las condiciones de factibilidad (Leyes de
kirchoff, radialidad, conectividad) con la mayor economía posible. Esto define la aptitud de cada individuo.

El cromosoma representando a cada individuo puede ser codificado en un string de longitud igual a la cantidad de
enlaces posibles con un código binario. La cantidad de bits de cada gen (Nodo) será igual a la cantidad de
corredores posibles (líneas) para la entrega de energía al nodo.
• Una población se genera formando una cantidad de cromosomas de forma aleatoria, con solo producir
alteraciones en los bit del cromosoma se alteran sus características (genotipo) y por tanto genera individuos
diferentes al original.
• Es evidente que hay que establecer un tipo de codificación especializada que permita conservar las
características de las redes eléctricas y la descodificación final devuelva, después del proceso evolutivo,
parámetros de redes eléctricas que tengan significado físico para el proyectista.

CONCLUSIONES
Se aprecian dos características particulares en el problema del planeamiento de las redes de distribución: Su modelo
matemático contiene gran cantidad de restricciones y la codificación de los cromosomas tiene una cantidad variable
de bits por cada gen. Estas características aconsejan la utilización de un algoritmo genético especializado para
resolver este problema. Las peculiaridades de este algoritmo serán presentadas en la segunda parte de este
artículo.

REFERENCIAS

1. EDGAR, M.H. “Un Algoritmo Genético aplicado no problema de minimización de perdas activas em redes de
distribuicao de energía”. XIV Congreso Brasilero de Automática. 2002.
2. MIRANDA, V. “Genetic Algorithms in optimal multistage distribution network planning”. INESC. Porto,
Portugal, 2000.
3. MONTAGNO F. “Planificación de la expansión de sistemas de distribución vía algoritmos genéticos”.
Universidad de Santiago de Chile. 1999.
4. PINTO J. L. “Topología optima de redes de distribución utilizando programación evolutiva”. INESC. Porto,
Portugal, 2003.

AUTOR

Raúl Nicolás Carvajal Pérez

Ing. Electricista, Dr. Ciencias Técnicas, Profesor Auxiliar, Centro de Investigaciones y Pruebas
Electro energéticas (CIPEL) Facultad de Eléctrica, CUJAE, La Habana, Cuba.
e-mail: [email protected]

Ingeniería energética Vol. XXXII, No. 1/2011 p 72 – 76 Enero – Marzo ISSN 1815 - 5901