Using traditional heuristic algorithms on an initial genetic algorithm population applied to the transmission expansion planning problem

Aplicación de algoritmos heurísticos en la construcción de la población inicial de algoritmos genéticos que resuelven el problema de planeamiento de la expansión de la transmisión

This paper analyses the impact of choosing good initial populations for genetic algorithms regarding convergence speed and final solution quality. Test problems were taken from complex electricity distribution network expansion planning. Constructive heuristic algorithms were used to generate good initial populations, particularly those used in resolving transmission network expansion planning. The results were compared to those found by a genetic algorithm with random initial populations. The results showed that an efficiently generated initial population led to better solutions being found in less time when applied to low complexity electricity distribution networks and better quality solutions for highly complex networks when compared to a genetic algorithm using random initial populations.

En este artículo se analiza el impacto de seleccionar poblaciones iníciales de buena calidad para ser usadas en algoritmos genéticos, con el propósito de obtener mayor velocidad de convergencia y mejor calidad en las soluciones alcanzadas cuando se resuelve el problema del planeamiento de la expansión a largo plazo de los sistemas de transmisión de energía eléctrica. Los sistemas de prueba que se analizan corresponden a sistemas de alta complejidad, tradicionalmente usados en la literatura especializada. Para generar soluciones iníciales de buena calidad se utilizan algoritmos heurísticos constructivos, particularmente los más utilizados en problemas de planeamiento de la expansión de sistemas de transmisión. Se comparan los resultados obtenidos con los que entregan los algoritmos genéticos que usan poblaciones iniciales aleatorias. Los resultados muestran que una población inicial generada en forma heurística permite obtener soluciones de mejor o igual calidad y con esfuerzos computacionales menores, cuando se resuelven sistemas eléctricos de gran complejidad.

• HTML (es)
• HTML (en)

Antonio H. Escobar Z.¹, Ramón A. Gallego R.², Rubén A. Romero L.³

¹ Ph.D., Universidad Estadual Paulista, Brasil. Profesor, Universidad Tecnológica de Pereira. aescobar@utp.edu.co

² Ph.D., Universidad Estadu al de Campinas, Brasil. Profesor, Universidad Tecnológica de Pereira. ragr@utp.edu.co

³ M.Sc. y Ph.D., Universidad Estadual de Campinas, Brasil. Profesor, DEE-FEISUNESP. ruben@dee.feis.unesp.br

---

RESUMEN

Palabras clave: planeamiento de redes de transmisión, algoritmos genéticos, algoritmos heurísticos constructivos, metaheurística, población inicial.

ABSTRACT

Keywords: electricity distribution network expansion planning, genetic algorithm, constructive heuristic algorithm, met heuristics, initial population.

---

Recibido: febrero 01 de 2010. Aceptado: febrero 7 de 2011

---

Introducción

Mediante la solución del problema de planeamiento de la expansión de sistemas de transmisión de energía eléctrica se determina dónde, cuándo y cuántos elementos nuevos deben ser adicionados al sistema eléctrico para que éste opere adecuadamente en un horizonte de planeamiento especificado. El planeamiento estático considera únicamente un horizonte y determina el número de elementos que deben adicionarse en cada corredor del sistema de potencia. En los sistemas actuales es necesario en ocasiones tener en cuenta otras consideraciones, lo que conduce a modelos matemáticos de mayor complejidad. Por ejemplo, es posible incorporar un horizonte de planeamiento dividido en etapas, condiciones de seguridad, operación con mercado de electricidad, entre otros. En este artículo únicamente se analiza el caso de planeamiento estático, el cual es la base para el desarrollo de problemas de planeamiento que incorporan nuevos aspectos.

Se utiliza el modelo DC para representar la red eléctrica debido a que únicamente se considera planeamiento de la red para suministro de potencia activa. Este modelo se juzga ideal para planeamiento de largo plazo, y por medio de él se formula el problema de optimización para el planeamiento de la expansión de sistemas de transmisión. El problema resultante es de programación no lineal entero-mixta. Cuando se aplica a problemas de la vida real de gran tamaño, la complejidad del problema se hace evidente por su multimodalidad, a la vez que es común encontrar una gran cantidad de soluciones óptimas locales. Si aumenta el tamaño del sistema el número de soluciones locales crece de manera exponencial.

Para resolver el problema del planeamiento de la transmisión de largo plazo, se han propuesto una gran variedad de técnicas presentes en la literatura especializada. Las referencias (Garver, 1970; Villasana, 1985; Gallego, 1998; Gallego, 2000; Haffner, 2001; Da Silva, 2000) son ejemplos de técnicas de optimización clásica. En Villasana (1985); Monticelli (1982); Pereira (1985), se aplican técnicas heurísticas; y en Gallego (1998a); Gallego (1998b); Gallego, (2000); Dávila (2000); Escobar (2004); Romero (2007) técnicas metaheurísticas. Las técnicas metaheurísticas han sido las más exitosas en cuanto a eficiencia computacional y calidad de las soluciones encontradas cuando se aplican a problemas de gran tamaño y gran complejidad. En Romero (2002); Latorre (2003); Lee (2006), puede encontrarse un análisis más detallado del problema de planeamiento de la expansión de sistemas de transmisión y las técnicas utilizadas en su solución.

Este artículo tiene como propósito analizar un aspecto específico del problema citado: el impacto que produce una población inicial de buena calidad en la velocidad de convergencia y en la calidad de la solución final de un algoritmo genético. Dicho aspecto es probado con la incorporación de poblaciones iniciales de buena calidad a problemas de planeamiento de la transmisión de sistemas de prueba según la literatura especializada. Los resultados obtenidos se comparan con los que entrega un algoritmo genético que utiliza población inicial aleatoria.

El análisis de este aspecto particular surge como resultado de: 1) la necesidad de avanzar en el estudio de la conjetura experimental del caso particular del problema de planeamiento, según la cual poblaciones iniciales de buena calidad producen un rendimiento notable de las técnicas metaheurísticas cuando se aplican a sistemas de gran tamaño y gran complejidad (Gallego, 1998a; Gallego, 1998b); 2) la importancia que ha adquirido este tópico en la literatura, donde se hace referencia a la importancia de seleccionar poblaciones iniciales de buena calidad (Maaranen, 2007); y 3) los nuevos desarrollos en técnicas metaheurísticas que reconocen que buenas poblaciones iniciales son cruciales para su rendimiento (Hansen, 2003).

En la referencia (Maaranen, 2007) se analiza el impacto de diferentes métodos usados para construir poblaciones iniciales en el desempeño de un algoritmo genético general sin ningún conocimiento específico del problema. Las poblaciones iniciales se generan usando cuatro métodos, y los resultados se comparan respecto a la velocidad de convergencia y el valor de la función objetivo final. Las diferencias entre las cuatro formas son pequeñas y las conclusiones más importantes son: 1) la configuración inicial es un factor determinante en la velocidad de convergencia y las diferencias presentes en las primeras generaciones resultan importantes al resolver problemas de la vida real, donde las evaluaciones de la función objetivo requieren mucho tiempo de cálculo y el algoritmo puede activar un criterio de parada prematuramente; 2) la calidad de la población inicial cambia la convergencia de un algoritmo genético; 3) se muestra que una población inicial generada usando algún criterio experto o sensibilidad produce un resultado de alta calidad en el algoritmo genético, y 4) las futuras investigaciones deben incluir formas de generar poblaciones iniciales diversas y de buena calidad para diversos tipos de problemas. Adicionalmente, se observa que el problema de planeamiento en un sistema complejo requiere la solución de cientos o miles de problemas de programación lineal (PL)(Gallego, 2003), para obtener buenas soluciones.

En (Hansen, 2003) se desarrolla un algoritmo de búsqueda con vecindad variable (VNS). El algoritmo VNS explota sistemáticamente la idea de cambio en el vecindario de una solución, tanto en el propósito de descender a un óptimo local (para el problema de minimización) como para escapar de regiones que contienen óptimos locales (Hansen, 2003). También hace énfasis en el hecho de que en muchos problemas de optimización combinatorial los óptimos locales tienden a estar muy cercanos entre sí y situados en una (o en varias) pequeñas regiones del espacio de búsqueda. Una vez encontrada una solución óptima local, ésta contiene implícitamente información de soluciones de mayor calidad o de la solución óptima global. En consecuencia, una solución óptima local frecuentemente suministra información asociada a la solución óptima global. El caso puede ser, por ejemplo, que varias soluciones óptimas locales tengan variables con el mismo valor. Los investigadores han encontrado, en varios casos, relaciones fuertes entre las soluciones óptimas locales de buena calidad y la solución global, de tal forma que en nuevas investigaciones concentran su búsqueda en subespecies, si las soluciones óptimas locales estuvieran muy separadas unas de otras, y uniformemente distribuidas en el espacio de búsqueda, todas las técnicas metaheurísticas deberían ser ineficientes (Hansen, 2003). Si la población inicial de un algoritmo genético se compone de soluciones óptimas locales, cada una representa un punto interesante en una subregión diferente. En una población inicial con estas características es relativamente más fácil encontrar la solución óptima global o soluciones subóptimas de alta calidad.

Este trabajo aplica dichas ideas mediante el uso de varias técnicas heurísticas tradicionales y combinaciones de ellas que llevan a soluciones óptimas locales de alta calidad, con bajos tiempos de procesamiento y moderada robustez. El uso de estas heurísticas, y la inclusión de pequeñas alteraciones en ellas para diseñar algoritmos constructivos, permiten generar una población inicial de buena calidad para el problema de planeamiento de la transmisión. Al utilizar esta población inicial en el algoritmo genético se observa que se obtienen mejores soluciones que las obtenidas sin su uso en sistemas de gran tamaño y gran complejidad. El modelo DC utilizado es el siguiente:

(1)

s.a.

(2)

(3)

(4)

donde representan, respectivamente, el costo de un circuito que puede ser adicionado en el corredor, i-j , la susceptancia de un circuito, el número de circuitos adicionados en el corredor i-j, el número de circuitos en el caso base para el corredor i-j, el flujo de potencia total correspondiente al máximo flujo de potencia por circuito en el corredor i-j; v es la inversión, S es la matriz de incidencia nodo-rama transpuesta, f es un vector con elementos f_ij , g es un vector con elementos g_k (generación en el nodo k) cuyo máximo valor es , es el número máximo de circuitos que pueden existir en el corredor i-j y Ω es el conjunto de corredores del sistema donde se pueden realizar adiciones.

La restricción 2) representa la ley de Kirchhoff de corriente (LKC) en el modelo DC, y la restricción (3) representa la ley de Kirchhoff de tensiones (LKV). Éstas son restricciones no lineales. El problema de expansión de la transmisión formulado es un problema no lineal entero-mixto (PNLEM), problema combinatorial difícil de resolver que produce una explosión combinatorial del número de alternativas a ser consideradas. Sin embargo, si se permiten temporalmente valores continuos para las variables enteras nij el modelo DC se convierte en un problema de programación no lineal (PNL).

A continuación se presentan los modelos simplificados más usados en la solución del problema de planeamiento, así como los algoritmos constructivos implementados para generar las poblaciones iniciales. Finalmente, se presentan los resultados obtenidos en los sistemas de prueba y las comparaciones entre las respuestas.

Modelos simplificados usados en planeamiento de la expansión

El modelo DC es considerado ideal para el planeamiento de la expansión de la transmisión. Se utiliza tanto en la versión completa, como en algunas versiones simplificadas. Se dice que un modelo es simplificado si algunas de sus restricciones son eliminadas o si se permite adicionar un número no entero de circuitos al sistema. En problemas de gran tamaño y complejidad una característica de las técnicas metaheurísticas es que encuentran soluciones de alta calidad sin explorar todo el espacio de soluciones. Estas técnicas exploran de forma simultánea varios subespacios, donde en ocasiones se encuentran soluciones de baja calidad. Las versiones simplificadas del modelo DC son cruciales en el proceso de optimización, ya que ayudan a identificar regiones promisorias en las que se localizan soluciones de alta calidad, suministrando puntos de referencia excelentes para el proceso de búsqueda de las técnicas metaheurísticas.

La eliminación de la condición de entera para las variables permite obtener un espacio de soluciones continuo, lo cual lo convierte en un problema de programación lineal si se asocia esta condición a un algoritmo heurístico constructivo (AHC) que realice propuestas de adición de nuevos elementos. Este procedimiento heurístico permite identificar regiones que contienen soluciones de muy buena calidad, entre las cuales eventualmente se encuentra la solución óptima.

Existen varias propuestas de solución del problema de planeamiento cuando se elimina la condición de entera de las variables o se eliminan restricciones no lineales. A continuación se examinan las propuestas más importantes que utilizan las siguientes versiones simplificadas: (1) el modelo de transportes, y (2) el modelo híbrido.

Modelo de transportes

El modelo de transportes (MT) se obtiene relajando las restricciones no lineales (3) del modelo DC (Garver, 1970; Romero, 2002; Escobar, 2010). El modelo se simplifica al eliminar la característica no lineal del problema de planeamiento. El nuevo modelo es de programación lineal entero-mixta (PLEM) que asume la siguiente forma:

(5)

s.a.

(6)

(7)

Es posible encontrar la solución óptima del MT usando, por ejemplo, un algoritmo Branch y Bound (Haffner, 2001; Gallego, 2007). Sin embargo, este algoritmo no es capaz de encontrar la solución óptima de un problema de planeamiento de gran tamaño y complejidad. Lógicamente, si las variables enteras n_ij pueden asumir valores continuos, el MT se puede resolver por medio de un PL.

Modelo híbrido lineal

El modelo híbrido lineal (MHL) se obtiene relajando las restricciones no lineales (3) para los nuevos circuitos adicionados al sistema. Las restricciones del tipo (3) a los circuitos que existen en la topología actual son lineales. En consecuencia, este modelo es intermedio entre el MT y el DC. El nuevo modelo relajado es de programación lineal entero-mixta (PLEM), que asume la siguiente forma:

(8)

s.a.

(9)

(10)

(11)

(12)

donde S⁰ es la matriz incidencia nodo-rama transpuesta del sistema, construida con las ramas existentes en la topología inicial y los nodos conectados a estas ramas, f0 es el vector de flujos de potencia mediante las ramas de la topología inicial, con elementos f ⁰_ij , S es la matriz incidencia transpuesta del sistema completo, y f es el vector de flujos de potencia a través de los nuevos circuitos adicionados al sistema, Ω es el subconjunto de índices de los circuitos existentes en la topología base.

Es posible obtener la topología base para el MHL usando, por ejemplo, un algoritmo Branch y Bound como en el caso del MT. De nuevo, este tipo de algoritmos no logran resolver problemas de planeamiento de gran tamaño y complejidad. También, en este caso, si se permiten valores continuos a las variables enteras, n_ij el MHL se puede resolver usando PL.

Se puede observar que en la solución óptima del MHL los nuevos circuitos adicionados al sistema no están obligados a cumplir la LKV. En este contexto, los nuevos circuitos pueden conducir flujos de potencia diferentes a los que circulan por circuitos del mismo tipo que se encuentran en paralelo pero que hacen parte de la topología base (las existentes cumplen ambas leyes de Kirchhoff y las nuevas sólo la primera). Es posible formular un modelo híbrido no lineal (MHNL) en el cual los nuevos circuitos también estén obligados a cumplir la segunda ley de Kirchhoff. Sin embargo, esto conduce a un problema de programación no lineal entero-mixta (PNLEM) de una complejidad equivalente a la del modelo DC, modelo que no se analiza aquí. En este artículo se investigan casos donde las regiones promisorias se identifican combinando modelos relajados con AHC.

Algoritmos heurísticos constructivos usados en planeamiento

Un algoritmo heurístico constructivo (AHC) es un procedimiento iterativo que permite encontrar soluciones a un problema complejo usando indicadores de sensibilidad. En el problema de planeamiento de la transmisión, estos AHC casi siempre encuentran la solución óptima de sistemas pequeños. Sin embargo, si el tamaño del problema crece o aumenta su complejidad, la solución encontrada por el AHC se aleja de la solución óptima. A continuación se presentan en forma breve AHC que usan versiones simplificadas del modelo DC.

Algoritmo de Garver

Garver fue el primero en proponer un AHC para el problema de planeamiento (Garver, 1970; Escobar, 2010). Este AHC encuentra soluciones de buena calidad usando el modelo de transporte (MT). Lógicamente, la topología propuesta por el AHC de Garver resulta inadecuada para el sistema cuando se simula la operación de la red usando el modelo DC.

La estructura básica del AHC de Garver ha servido de referencia para otros AHC que han surgido después de la propuesta de Garver. Nuevos AHC difieren del propuesto por Garver en tres aspectos fundamentales: 1) utilizan un modelo diferente, 2) usan factores de sensibilidad diferentes, y 3) emplean optimización local. A continuación se presenta un AHC generalizado de Garver. Un AHC generalizado para el problema de planeamiento sigue el procedimiento presentado a continuación:

1.Asumir la topología base como la actual y seleccionar un modelo matemático para la red (MT, MHL, DC, etcétera).

2.Resolver el problema para la topología actual usando el modelo seleccionado y aplicando PL. Si la solución indica que el sistema opera sin sobrecargas ni racionamiento, entonces se ha encontrado una solución de buena calidad para el problema de planeamiento. En este caso, se va al paso 4; en otro caso, al paso 3.

3.Utilizar un indicador de sensibilidad con la finalidad de identificar los circuitos más atractivos para ser adicionados al sistema. Redefinir la topología actual adicionando uno o varios circuitos identificados por el factor de sensibilidad. Regresar al paso 2.

4.Ordenar los circuitos adicionados en orden descendente de su costo y usar un PL en cada caso para verificar si el circuito adicionado en el proceso iterativo puede ser removido, ya que su retiro no afecta la operación. Repetir este proceso simulando el retiro de todos los circuitos que fueron adicionados, uno a la vez.

El paso 4 es muy necesario en AHC debido a que algunos circuitos adicionados durante el proceso de solución resultan irrelevantes en la solución final.

Todos los AHC pueden construirse a partir del AHC generalizado. Por ejemplo, el AHC de Garver es generalizado con las siguientes particularidades: 1) utiliza el modelo de transportes, 2) el factor de sensibilidad es el flujo de potencia de sobrecarga por medio de los circuitos existentes; para resolver el problema mediante un PL se permite a las variables enteras asumir valores continuos; y 3) no emplear la estrategia de simulación de remoción de circuitos adicionados presentada en el paso 4.

En el AHC de Garver, en el paso 2 se resuelve un PL para el MT considerando únicamente n_ij ≥0 y en el paso 3 se selecciona el corredor con n_ij ≠0 que presenta el mayor flujo de potencia. El flujo de potencia mediante los nuevos circuitos es el indicador de sensibilidad del AHC de Garver.

Algoritmos para el modelo híbrido lineal

Es posible implementar tres AHC para el MHL en el problema de planeamiento, cambiando las condiciones que deben cumplir los nuevos circuitos adicionados al sistema en cada paso del proceso iterativo: 1) todos los circuitos adicionados deben cumplir únicamente la primera ley de Kirchhoff (LKC); 2) los nuevos circuitos adicionados han de cumplir la primera y segunda ley de Kirchhoff (LKC y LKV) si se encuentran conectados en paralelo con circuitos ya existentes en la topología base, y cumplir únicamente la LKC si en su corredor no existen circuitos en la topología base, 3) todos los circuitos cumplen la LKC y LKV. Cada una de estas estrategias conduce a una solución diferente. En todos los casos los circuitos de la topología base cumplen la LKC y la LKV. También en los tres casos puede usarse el factor de sensibilidad usado en el AHC de Garver.

Algoritmo híbrido I

Este AHC se denominará algoritmo heurístico constructivo híbrido I (AHCH-I). En este caso, todos los circuitos adicionados en el proceso iterativo sólo cumplen la LKC y los circuitos de la topología base cumplen la LKC y la LKV. La solución obtenida con este algoritmo generalmente resulta infactible para el modelo DC.

El AHCH-I para el MHL es un AHC generalizado con las siguientes características: 1) utiliza el modelo híbrido lineal (MHL), y 2) emplea el mismo factor de sensibilidad del AHC de Garver. En consecuencia, en el paso 2 el PL aplicado a la topología actual y al MHL se resuelve considerando únicamente n_ij ≥ 0 y en el paso 3 el circuito n_ij ≠0 que tenga asociado el flujo de potencia mayor es seleccionado para adición, esto es, .

La implementación del AHCH-I se efectúa por medio de un PL ligeramente diferente del presentado en las expresiones (8)-(12). En consecuencia, la relación Sf + Sofo + g = d es sustituida por la relación Sf + Sofo+ S′f′ = d, donde S′ es la matriz incidencia nodorama obtenida con los circuitos adicionados durante el proceso iterativo y f′ es el vector de flujos de potencia mediante los circuitos adicionados en el proceso iterativo, con elementos f′_ij .

Se adiciona un nuevo grupo de restricciones de la forma . Puede notarse que el nuevo PL tiene tres vectores de flujo: un vector de flujos para los circuitos existentes en la topología base, un vector de flujos para los circuitos adicionados en el proceso iterativo, y un vector de flujos para los nuevos circuitos de PL sobre la topología actual.

Algoritmo híbrido II

En el algoritmo heurístico constructivo híbrido II (AHCH-II) los nuevos circuitos adicionados deben cumplir la primera y segunda ley de Kirchhoff (LKC y LKV) si se encuentran conectados en paralelo con circuitos ya existentes en la topología base, y cumplir únicamente la LKC si en su corredor no existen circuitos en la topología base. En principio este algoritmo adiciona más circuitos que el AHCH-I al ser más restrictivo, y su solución resulta generalmente infactible para el modelo DC.

Este algoritmo difiere del AHCH-I en el tipo de problema de PL que se resuelve en el paso 2.

Para implementar el AHCH-II se resuelve un PL ligeramente diferente al presentado para el MHL en las expresiones (8)-(12). Se aplican las mismas modificaciones hechas para el AHCH-I. A diferencia del AHCH-I, los circuitos adicionados a la topología base durante el proceso iterativo se van integrando a la topología base y por lo tanto el vector n⁰_ij debe ser actualizado en cada iteración.

Algoritmo híbrido III

En el algoritmo heurístico constructivo híbrido III AHCH-III), todos los circuitos adicionados en el proceso iterativo deben cumplir la primera y segunda ley de Kirchhoff (LKC y LKV). Un aspecto fundamental de este algoritmo es que la topología encontrada al final del proceso iterativo resulta factible para el modelo DC. El proceso finaliza cuando se satisface el balance generación-carga. Este algoritmo fue propuesto por Villasana-Garver-Salon (VGS) (Villasana, 1985).

Para implementar el AHCH-III se resuelve un PL ligeramente diferente al presentado para el MHL en las expresiones (8)-(12). Adicionalmente, el vector n⁰_ij debe ser actualizado con la adición de cada nuevo circuito y el conjunto
0Ω tambien requiere ser actualizado.

Algoritmos para el modelo DC

Existen muchas técnicas heurísticas y AHC que usan el modelo DC y, por lo tanto, encuentran una solución que es simultáneamente factible y de buena calidad para el modelo DC. A continuación se examinan únicamente dos AHC basados en modelo DC. Existen dos versiones ampliamente utilizadas en planeamiento de sistemas de transmisión denominadas criterio de mínimo esfuerzo (CME) y mínimo corte de carga (MCC).

En cada paso del AHC el PL resuelve un problema con los circuitos de la topología base y los circuitos adicionados. Puede notarse que si los valores de n_ij (circuitos adicionados) son conocidos en el modelo DC (expresiones (1)-(4)), el problema resultante es un sistema de ecuaciones e inecuaciones cuya solución puede o no ser factible. Para ayudar al proceso de solución el sistema de ecuaciones e inecuaciones algebraicas ha de ser transformado adicionando nuevas variables denominadas generación artificial, una por cada nodo de carga. En consecuencia, para la topología actual k , el PL resultante para el AHC asume la siguiente forma:

(13)

s.a.

(14)

(15)

Donde n^k_ij representa los circuitos adicionados para llegar a la topología actual k, Ω₀ es el subconjunto de índices de los circuitos existentes en la topología base, r es el vector de generadores artificiales con elementos r_s en cada nodo, Γ es el subconjunto de índices de los nodos de carga, w es una medida de la infactibilidad del problema w = 0 y indica que el sistema opera adecuadamente.

Algoritmo de mínimo esfuerzo (AME)

El algoritmo de mínimo esfuerzo (AME) (Monticelli, 1982; Escobar, 2010) es un AHC generalizado con las siguientes características: 1) utiliza el modelo DC; 2) el factor de sensibilidad identifica el circuito más importante que, una vez adicionado, produce el mayor impacto en la distribución del flujo; 3) usa generadores ficticios para resolver problemas causados por nodos desconectados; y 4) resuelve un PL ligeramente diferente al descrito en (13).

En la solución del PL el AHC que usa el CME permite la sobrecarga de circuitos. En consecuencia, las restricciones de límites de capacidad de los circuitos son eliminadas para las líneas y transformadores en el modelo. La solución de cada PL se obtiene cuando w = 0 ya que los circuitos permiten sobrecarga. El proceso de adición de circuitos finaliza cuando desaparecen las sobrecargas. El criterio usado para la selección de nuevos circuitos es el siguiente:

donde los valores de θ se obtienen mediante la solución del PL y γij es la susceptancia de un circuito en el corredor (i, j). El circuito más atractivo es aquel que tiene el mayor valor absoluto del índice IS_ij. Con el propósito d que el algoritmo siempre finalice con w = 0 y tener en todo momento valores de θ disponibles (para poder calcular IS_ij) , el AHC del CME utiliza una red ficticia con valores de susceptancia adecuados en un número suficiente de circuitos como para garantizar la conectividad de todo el sistema. Los circuitos de la red ficticia solamente se utilizan cuando no hay un camino para la sobrecarga en los circuitos normales.

Algoritmo de mínimo corte de carga

El algoritmo de mínimo corte de carga (AMCC) (Pereira, 1985; Escobar, 2010) es similar al AME y la única diferencia entre ellos es el indicador de sensibilidad utilizado, el cual identifica el circuito que una vez adicionado produce la mayor disminución del corte de carga o demanda no atendida.

En la solución del PL el AHC de MCC no permite sobrecargas en los circuitos y el problema operacional es representado por la demanda no atendida en la topología actual. Si la solución del PL finaliza con w ≠ 0, el sistema no opera adecuadamente y deben adicionarse más circuitos a la topología actual. La adición de circuitos en el AMCC finaliza cuando la solución del PL presenta corte de carga cero. El criterio utilizado para la selección de nuevos circuitos en el AMCC es el siguiente:

Donde ^πj es el multiplicador de Lagrange de la restricción j del grupo de restricciones (14). El circuito más atractivo es aquel que produce el mayor valor de IS_ij. Para poder calcular los valores de IS_ij el AMCC requiere de una red ficticia que garantice la conectividad de la red.

Los dos AHC que usan el modelo DC durante el proceso iterativo adicionan circuitos que conectan nodos aislados al sistema base. Los dos AHC pueden incluir normalización dividiendo el término ISij por c_ij.

Algoritmos heurísticos aplicados al planeamiento de la transmisión

En esta sección se muestra cómo generar una población inicial para un algoritmo genético usando AHC y modelos relajados.

Importancia de generar topologías usando AHC

Las topologías de buena calidad construidas con AHC pueden ser utilizadas de varias formas de acuerdo a la estructura de la meta heurística aplicada. Una topología encontrada usando un AHC puede considerarse buena si presenta una o varias de las siguientes características: 1) tiene una buena función objetivo, y 2) la topología contiene alto porcentaje de circuitos que hacen parte de la solución óptima. Estas dos características no siempre concurren en una misma topología generada por medio de un AHC, para el problema de planeamiento.

Una topología con buena función objetivo puede ser considerada subóptima. Esta topología puede usarse en la población inicial de un algoritmo genético. La topología que contiene un número representativo de circuitos de la solución óptima resulta fundamental para el desempeño de un método como AG.

En las pruebas se puede verificar que un alto número de los circuitos de la solución óptima se encuentran distribuidos en las topologías iniciales construidas usando AHC, en este caso se dice que la población inicial es de alta calidad (Goldberg, 1989).

En el caso de los algoritmos genéticos el método tiene como característica principal su habilidad de reconocer soluciones parciales de alta calidad dispersas en los individuos de la població e integrarlas en una sola solución. Esta función se realiza mediante la operación combinada de los mecanismos de selección y recombinación del AG, que identifica circuitos interesantes y los reúne en una topología subóptima.

El operador de mutación del AG permite adicionar aquellos circuitos de la solución óptima que no aparecen en la población inicial. Este mecanismo resulta fundamental porque es el único capaz de generar alternativas donde están presentes elementos que no están correlacionados con los factores de sensibilidad usados. En el problema de planeamiento de la transmisión de sistemas de gran tamaño, una población inicial generada aleatoriamente contiene, probabilísticamente, un número reducido de circuitos de la solución óptima. En este caso el mecanismo de mutación debe generar todos estos circuitos, incrementando el esfuerzo computacional del AG.

En este artículo se muestra la aplicación de AHC y modelos relajados en la construcción de poblaciones iníciales de AG, con la particularidad de que las soluciones optimas o subóptimas requieren de la adición de un gran número de circuitos, como es el caso del sistema de prueba norte-nordeste brasilero.

Generación de la población inicial

Para cada modelo matemático, y para cada AHC analizado anteriormente, se puede aplicar el siguiente procedimiento con el propósito de generar un grupo de diferentes topologías:

1. Seleccionar un modelo matemático y un AHC, y generar su topología de buena calidad. Suponer que se adicionaron circuitos en k corredores y que usando todas las alternativas de modelos matemáticos y AHC se encontraron p topologías diferentes. Ordenar los k circuitos en cada una de las p topologías en orden descendente de sus costos.

2. Utilizar la información de cada uno de los k circuitos ordenados en el paso anterior para encontrar k nuevas topologías. Cada nueva topología se obtiene repitiendo el paso 1, pero en cada caso se prohíbe la adición de uno de los k circuitos. Este proceso puede implementarse fácilmente, incrementando temporalmente el costo asociado al circuito prohibido para evitar su selección.

La estrategia anterior permite generar k + 1 topologías diferentes para cada modelo matemático y AHC seleccionado. La diversidad entre estas topologías puede incrementarse realizando pequeñas modificaciones en el proceso iterativo, tales como: 1) modificar el factor de sensibilidad si la topología encontrada ya existe en la población, 2) eliminar el paso 4 del AHC generalizado, 3) finalizar el proceso anticipadamente, es decir, antes de que se cumpla el criterio de parada, y 4) prohibir la selección de varios de los k circuitos identificados por el algoritmo básico.

En la primera alternativa, el factor de sensibilidad puede ser modificado alterando ligeramente su lógica de aplicación. Por ejemplo, en el AHC de Garver, en cada paso del proceso iterativo puede adicionarse un circuito en el corredor con mayor valor de n_ij o adicionarse tantos circuitos como parte entera tenga el corredor con mayor valor de n_ij, o adicionarse simultáneamente circuitos en todos los corredores cuyo valor de n_ij es mayor a un cierto valor, por ejemplo, mayor a la unidad. En el caso de los ficados dividiéndolos por el costo del circuito. La segunda alternativa es simple y permite conservar los circuitos adicionados en exceso por el AHC y que pueden resultar interesantes para el modelo DC. La tercera alternativa evita la inclusión de circuitos irrelevantes o de poca importancia, los cuales son adicionados en las fases finales del AHC. En la fase final de un AHC se intentan colocar circuitos nuevos para resolver problemas de pequeñas demandas aún no atendidas, en ocasiones de nodos distantes. La finalización prematura del proceso evita la inclusión de estos circuitos. La última alternativa permite darle más diversidad a la población inicial. La estrategia anterior permite generar un gran número de soluciones iníciales de buena calidad para los AG.

Aplicación al algoritmo genético

A continuación se hace referencia al AG utilizado y a la importancia de tener una buena población inicial para resolver el problema de planeamiento de la transmisión.

El algoritmo genético utilizado es básicamente una versión mejorada del AG presentado en (Gallego, 1998a). La referencia (Glover, 2002; Goldberg, 1989) presenta los aspectos teóricos de los AG y de las metaheurísticas en general, y en las referencias (Gallego, 1998a; Da Silva, 2000) se presenta la aplicación de AG al problema de planeamiento. Se dice que una población inicial es de buena calidad si los genes de la solución óptima están distribuidos entre los individuos que la conforman.

La población inicial generada usando la estrategia descrita en los apartados anteriores se utilizó en 4 sistemas eléctricos: 1) el sistema Garver de 6 nodos, 15 corredores y 760 MW de demanda; 2) el sistema sur brasilero (SB) de 46 nodos, 79 corredores y 7.660 MW de demanda; 3) el sistema colombiano reducido 2012 con 93 nodos, 155 corredores y 14.559 MW de demanda; y 4) el sistema norte-nordeste brasilero en el Plan P1 con 87 nodos, 183 corredores y una demanda de 20.316 MW. Estos 4 sistemas fueron seleccionados debido a que presentan distintos niveles de complejidad. Es importante anotar que la complejidad de un sistema eléctrico no está únicamente asociada a su tamaño.

Un sistema es altamente complejo si presenta un alto nivel de desconexión y requiere de muchas adiciones en la topología óptima. De los 4 sistemas de prueba utilizados, sólo los 2 primeros tienen información para realizar planeamiento con y sin redespacho de generación, y sus soluciones óptimas son conocidas. Para los otros 2 sistemas sólo se han reportado soluciones subóptimas. En el sistema de prueba de Garver todos los circuitos de la solución óptima son identificados por los AHC. Algunos AHC pueden encontrar esta solución óptima. Para el sistema sur brasilero (SB), todos los circuitos de la solución óptima se encuentran distribuidos en la población inicial, pero ningún AHC encuentra la solución óptima. Algunos AHC encuentran soluciones subóptimas que difieren de la óptima en un circuito. En estos dos sistemas utilizar poblaciones iníciales de buena calidad en un AG reduce significativamente el esfuerzo computacional. De otro lado, un AG con población inicial generada en forma aleatoria también encuentra la solución óptima de estos dos sistemas pero con mayor esfuerzo computacional.

Cuando se aplican AHC al sistema colombiano 2012 se encuentra que estos algoritmos identifican 14 de los 17 circuitos de la mejor solución conocida para este sistema. Un aspecto importante es que los AHC identifican con frecuencia la estructura base de la red futura. El sistema colombiano se considera como un sistema de gran tamaño y mediana complejidad.

Para el sistema norte-nordeste brasilero el 87,1% de los circuitos de la mejor solución conocida se encuentra presente en la población inicial. En este sistema es difícil cuantificar la cantidad de circuitos subóptimos presentes en la población inicial debido que este sistema tiene muchas soluciones subóptimas que presentan valores similares en costo de inversión con topologías radicalmente diferentes. El concepto de circuito subóptimo depende de la topología subóptima a la que se haga referencia. Un aspecto interesante es que el 87,1% de los circuitos identificados por los AHC y que se encuentran en la mejor solución conocida para este sistema representan el 97,77% del costo de inversión de esta mejor solución. En otras palabras, los circuitos identificados por los AHC son los más importantes y los más costosos de la mejor solución. La tabla 1 muestra los resultados comparativos de los diferentes sistemas utilizados.

El algoritmo genético debe adicionar los circuitos que no están presentes en la población inicial por medio del operador d mutación. Este operador también requiere reincorporar circuitos interesantes eliminados durante el proceso de selección o recombinación. Es importante tener en cuenta que un AG que usa una población inicial de buena calidad ha de aplicar una baja presión selectiva en las fases iníciales del proceso, con el propósito de preservar genes de alta calidad presentes en topologías iniciales de baja calidad.

Pruebas y resultados

A continuación se presentan en forma ampliada los resultados obtenidos para los sistemas colombiano 2012 y norte-nordeste brasilero plano P1.

Sistema colombiano 2012

La topología y los datos de este sistema se encuentran disponibles en la referencia Escobar (2002). Un AG implementado con una población inicial generada de la forma indicada en este artículo encuentra la mejor solución conocida para este sistema. Si la población inicial es generada aleatoriamente el AG no encuentra esta solución. La mejor solución obtenida presenta un costo de inversión de v = 560 millones de dólares y un corte de carga de w = 0.2. MW. La topología de esta solución es la siguiente:

La mejor solución conocida con w = 0 MW tiene un costo de inversión de v = 562,42 millones de dólares. La tabla 1 muestra la cantidad de circuitos identificados por los AHC que hacen parte de la mejor solución. Para resolver este sistema se requiere resolver en promedio 4.220 problemas de PL.

Sistema norte-nordeste brasilero

Los datos de este sistema se encuentran disponibles en la referencia Escobar (2002). Se muestran los resultados para el caso P1 de este sistema. Este sistema se considera de alta complejidad debido a la alta desconexión que presenta la red inicial y a la cantidad de elementos que deben adicionarse para encontrar soluciones factibles. La solución óptima de este sistema no es conocida. La mejor solución encontrada usando un AG y una población inicial generada con AHC presenta un costo de inversión de v = 1.356.712.000 US $ y un corte de carga de w = 3.3 MW. Esta solución corresponde a la siguiente topología:

Para un corte de carga de w = 0, la solución requiere una inversión de v = 1.360.961.000 US $, y presenta la siguiente configuración:

Las dos soluciones se encuentran en la misma región del espacio de búsqueda ya que son topológicamente similares, con diferencias en sólo 5 corredores. Para encontrar estas configuraciones el AG resuelve en promedio 80.000 PL.

A continuación se muestran los resultados obtenidos al aplicar las estrategias de solución al sistema colombiano y al sistema norte-nordeste brasilero. Se utiliza el mismo algoritmo pero con poblaciones iníciales generadas de forma diferente. Para comparar su desempeño el algoritmo se ejecuta 10 veces. Las pruebas se efectúan usando la modificación que sugiere hacer una finalización prematura de la ejecución de los AHC y realizando ejecuciones con convergencia normal. Para el sistema colombiano la ejecución se detuvo después de 2.000 iteraciones del AHC. En el sistema norte-nordeste brasilero el proceso se detiene después de ejecutados 20.000 PL. El sistema brasilero converge en 80.000 iteraciones. La tabla 2 muestra estos resultados. La cantidad de PL indica el valor medio de los que deben ejecutarse, y v indica el costo de la mejor solución encontrada.

Las poblaciones iniciales se generaron de las siguientes tres formas: 1) totalmente aleatorias (ALE), 2) aleatoria controlada (ALC), y (3) empleando un algoritmo heurístico constructivo (AHC). En la primera estrategia, en cada corredor se adicionan aleatoriamente un número de circuitos entre 0 y un límite superior. En la segunda, sólo se permite adicionar circuitos en un número limitado de corredores (np), similar en cantidad a los que presenta la mejor solución conocida. Para el sistema colombiano se usa un valor de np = 20, y para el sistema brasilero un np = 65. En la tabla 2, C significa sistema colombiano, C-ALE es el caso donde se usa población aleatoria, C-ALC es el caso donde se utiliza población aleatoria controlada y CAHC cuando se emplean AHC. La inversión se refiere en millones de dólares. Los resultados muestran claramente un mejor desempeño en el caso en que se usan AHC. La diferencia es mayor en el sistema brasilero, donde la complejidad es mayor.

Conclusiones

En este trabajo se ha realizado una comparación del desempeño de un AG que utiliza una población inicial generada usando los AHC usados tradicionalmente en el proceso de solución del problema de planeamiento de la transmisión. Se ha comparado el esfuerzo computacional, medido en cantidad de problemas de PL que deben resolverse en cada caso, y la cal idad de la respuesta obtenida. Se concluye que una población inicial generada usando AHC permite que el AG sea más eficiente que un AG similar que utiliza una población generada aleatoriamente. La diferencia resulta significativa en sistemas de alta complejidad. Estos resultados coinciden con observaciones realizadas por otros investigadores sobre el efecto de utilizar una adecuada inicialización en AG. El artículo también muestra cómo potenciar el uso de las técnicas heurísticas, normalmente tratadas como técnicas auxiliares, para mejorar el rendimiento y la eficiencia de una técnica metaheurística (AG) que busca la optimización global. Tomando los resultados encontrados en este trabajo y en otros publicados, se podría replantear de forma significativa la manera de encontrar la solución inicial o un conjunto de soluciones iníciales que permitan inicializar el proceso de optimización con metaheurísticas, especialmente en problemas de ingeniería de gran complejidad matemática.

---

Referencias

Da Silva, E.L., Gil, H.A., Areiza, J.M., Transmission Network Expansion Planning under an Improved Genetic Algorithm., IEEE Transactions on Power Systems, Vol. 15, No. 4, November, 2000, pp 1168-1175.

Escobar, A. H., Planeamiento Dinámico de la Expansión de Sistemas de Transmisión Usando Algoritmos Combinatoriales., Universidad Tecnológica de Pereira, tesis de Maestría, 2002.

Escobar, A. H., Gallego, R. A., Romero, R., Multistage and Coordinated Planning of the Expansion of Transmission Systems., IEEE Transactions on Power Systems vol. 9, no. 2, pp. 1565-1573, November 2004.

Escobar, A., Romero, R., Gallego, R. A., Modelos Usados en el Planeamiento de la expansión a Largo Plazo de Sistemas de Transmisión de Energía Eléctrica., Taller de publicaciones Universidad Tecnológica de Pereira, 2010, pp. 22-76.

Gallego, R.A., Monticelli, A., Romero, R., Transmission System Expansion Planning by Extended Genetic Algorithm., IEE Proceedings - Generation, Transmission and Distribution, Vol. 145(3), May, 1998a, pp.329-335

Gallego, R.A., Monticelli, A., Romero, R., Comparative Studies of Non-Convex Optimization Methods for Transmision Network Expansion Planning., IEEE Transactions on Power Systems, Vol. 13, No. 3, August, 1998b, pp.822-828.

Gallego, R.A., Monticelli, A., Romero, R., Tabu Search Algorithm for Network Synthesis., IEEE Transactions on Power Systems, Vol. 15, No. 2, May, 2000, pp. 490-495.

Gallego, R. A., Escobar, A., Romero, R., Optimización en Sistemas Eléctricos I - Programación Lineal., Taller de publicaciones Universidad Tecnológica de Pereira, 2003, pp. 77-218.

Gallego, R. A., Escobar, A., Romero, R., Programación Lineal Entera., Taller de publicaciones Universidad Tecnológica de Pereira, 2007, pp. 87-191.

Garver, L.L., Transmission Network Estimation Using Linear Programming., IEEE Trans. Power App. Syst., Vol. PAS-89, September-October, 1970, pp. 1688-1697.

Glover, F., Kochenberger, G.A., Handbook of Metaheuristics,Kluwer Academic Publishers., Boston/Dordrecht/LOndon, 2002, pp. 37-184.

Goldberg, D.E., Genetics Algorithms in Search, Optimization and Machine Learning, Addison Wesley, Reading, Massachusetts, 1989.

Haffner, S., Monticelli, A., Garcia, A., Romero, R., Specialized Branch and Bound Algorithm for Transmission Network Expansion Planning., IEE Proceedings -Generation, Transmission and Distribution, Vol. 148(5), September 2001, pp. 482 -488.

Hansen, P., Mladenovic, N., A Tutorial on Variable Neighborhood Search., Les Cathiers du GERAD, G-2003-46, July 2003.

Latorre, G., Cruz, R.D., Areiza, J.M., Villegas, A., Classification of Publications and Models on Transmission Expansion Planning., IEEE Transactions on Power Systems, Vol. 18, No. 2, May 2003, pp 938-946

Lee, C.W., Ng, S.K.K., Zhong, J., Wu, F.F., Transmission Expansion Planning From Past to Future., Power Systems Conference and Exposition, Oct. 29 2006-Nov. 1, PSCE ´06. IEEE PES, Atlanta, GA, USA, 2006, pp. 257 - 265

Maaranen, H., Miettinen, K., Penttinen, A., On Initial Populations of a Genetic Algorithm for Continuos Optimization Problems., Journal of Global Optimization, 37, 2007, pp 405- 436.

Monticelli, A., Santos, Jr. A., Pereira, M.V.F., Cunha, S.H., Parker, B.J., Praga, J.C.G., Interactive Transmission Network Planning Using a Least-Effort Criterion., IEEE Trans. Power App. Systems, Vol. PAS-101, No. 10, 0ctober, 1982, pp. 3919-3925.

Pereira, M.V.F., Pinto, L.M.V.G., Application of Sensitivity Analysis of Load Supplying Capability to Interactive Transmission Expansion Planning., IEEE Transaction on Power Apparatus and Systems, Vol. PAS-104, No. 2, February, 1985, pp. 381 -389.

Romero, R., Monticelli, A., Garcia, A., Haffner, S., Test Systems and Mathematical Models for Transmission Network Expansion Planning., IEE Proceedings - Generation, Transmission and Distribution, Vol. 149(1), 2002, pp. 27-36.

Romero, R., Rider, M.J., Silva, I., A Metaheuristic to Solve the Transmission Expansion Planning., IEEE Transactions on Power Systems, Vol. 22, No. 4, November, 2007, pp. 2289- 2291.

Villasana, R., Garver, L.L., Salon, S.J., Transmission Network Planning Using Linear Programming., IEEE Trans. Power App. Systems, Vol. PAS-104, No. 2, February 1985, pp. 349-356.

---

Antonio H. Escobar Z.¹, Ramón A. Gallego R.², Rubén A. Romero L³.

¹ Ph.D., Universidad Estadual P aulista, Brazil. Professor, Univer sidad Tecnológica de Pereira, Colombia. aescobar@utp.edu.co

² Ph.D., Universidad Est adual de Campinas, Brazil. Professor, Universidad Tecnológica de Pereira, Colombia. ragr@utp.edu.co

³ M.Sc. and Ph.D., Universidad Estadual de Campinas, Brazil. Professor, DEEFEIS-UNESP, Brazil. ruben@dee.feis.unesp.

---

ABSTRACT

Keywords: electricity distribution network expansion planning, genetic algorithm, constructive heuristic algorithm, met heuristics, initial population.

---

Received: Feuary 01th 2010. Accepted: Feuary 7th 2011

---

Introduction

A planning problem’s solution specifies where, how many and when new equipment must be installed in an electricity distribution system so that it operates adequately within a specified planning scenario. Static planning considers only one planning horizon and determines the number of circuits which should be added to each anch of an electricity distribution system. Mathematical models become more complex if different operation modes are taken into account such as multistage planning, security conditions, operation conditions in a competitive market which can be incorporated in a model. Although this paper only deals with static planning, it can be applied to more complex modelling situations.

The DC mode has been used to represent an electricity distribution network, since only transmission network active power planning is considered; it should be said that this is considered ideal for long-term planning. The DC model formulates optimising the planning of transmission system expansion. It is equivalent to a mixed-integer non-linear programming problem. Complexity increases due to the existence of a large number of local optimum solutions. Also, the number of solutions grows exponentially as a system gets larger.

Many techniques have been proposed in the field literature for resolving mathematically modelled planning problems. The following references (Garver, 1970; Villasana,1985; Gallego, 1998; Gallego, 2000; Haffner, 2001; Da Silva, 2000) show techniques corresponding to classical optimisation, whereas(Villasana, 1985; Monticelli, 1982; Pereira, 1985) used heuristic techniques and (Gallego, 1998a; Gallego, 1998b; Gallego, 2000; Davila,2000; Escobar, 2004; Romero, 2007) used met heuristic techniques. Met heuristic techniques have been dominant in relation to efficiency and solution quality when planning involves large size and complexity. A more detailed analysis of transmission system expansion planning and optimisation techniques can be found in (Romero, 2002; Latorre, 2003; Lee, 2006).

This paper specifically analyses the impact of efficient initial populations on convergence speed and solution quality by using a genetic algorithm. Such aspects are tested regarding transmission planning on large-size and highly-complex distribution systems and the results are compared with those obtained by a genetic algorithm with random initial population.

This issue has been explored because of the need for documenting the experimental conjecture that good initial populations have a tremendous impact on met heuristic technique performance in highly complex systems, at least in planning (Gallego, 1998a; Gallego, 1998b). The topic has emerged in the literature (Maaranen, 2007) regarding the relevance of choosing good initial populations and there have been new theoretical developments on met heuristics in which good initial populations have been recognised as crucial (Hansen, 2003).

In (Maaranen, 2007) the impact of different methods for choosing initial populations was determined for a general genetic algorithm, without any knowledge of the specific problem. Initial populations were generated using 4 different methods and results were compared to uniform coverage and genetic diversity in convergence and final objective function value. The four techniques involved slight differences. Initial configuration was a key factor in convergence speed and differences in early generation became important in solving many real-life problems where evaluation of objective functions may have required timeconsuming simulations and the optimisation algorithm may have had to be stopped prematurely. It was made clear (through an example) that the initial population had an effect on genetic algorithm convergence. It was shown that some attention to the initial population may have had an effect on genetic algorithm success and further research and discussion was encouraged. Topics for future research included a different initial population for specific types of problem and it was observed that complex system planning required many linear programming problems to be resolved to obtain the objective function value so the final solution would require resolving hundreds or thousands of linear programming (LP) items (Gallego, 2003).

The theory behind the variable neighbourhood search (VNS) algorithm was developed in (Hansen, 2003).The VNS algorithm systematically exploits the idea of neighbourhood change, both in descent to local minima and escape from the valleys containing them(Hansen, 2003). It also makes the interesting remark that local optimal minima tend to be close to one another in many combinatorial and global optimisation problems and are situated in one (or sometimes several) small parts of the space search. So, once a local optimum has beenreached, it contains implicit information about close better, and perhaps globally optimum, ones. Therefore, a local optimum often provides some information about a global one. The case may be, for instance, that several optimal solutions have variables having the same value. In other words, researchers have found that optimal local solutions are related in many cases and concentrate on a quite limited part of the search space. In fact, if local optima were far apart and uniformly distributed in the search space, all metaheuristic techniques would be inefficient (Hansen,2003). Therefore, the ideal initial population for genetic algorithms should consist of local optima, each representing a different valley. With such initial population it becomes relatively easy to find a global optimal or sub-optimal solution.

This work involves these ideas by combining several traditional heuristics producing good quality local optima in short times and which are moderately robust. A set of good solutions was generated by making small alterations to a constructive algorithm. If this set were used as initial population, a genetic algorithm finds better solutions in highly-complex systems compared to a random initial population. The model consisted of the following DC model:

(1)

s.a.

(2)

(3)

(4)

Where represented, respectively, the cost of one circuit that can be added to right-of-way ij , that circuit´s susceptance, the number of circuits added in right-of-way i-j, the number of circuits in the base case, total power flow and the corresponding maximum power flow by circuit in right-of-way i-j . v was investment, S was the anchnode incidence matrix transpose, f was a vector having elements f_ij , g was a vector having elements g_k (generation in bus k) whose maximum value was was the maximum number of circuits which could be added to right-of-way i–j and Ωwas the set of all rights-of-way.

Constraint (2) modelled Kirchhoff´s current law (KCL) in the equivalent DC distribution network and constraint (3) modelled Kirchhoff´s voltage law (KVL). These constraints were non-linear constraints. The transmission expansion formulated above was an integer non- linear mixed problem (INLMP). It is a difficult combinatorial problem which can lead to the combinatorial explosion of the number of alternatives to be searched. However, continuous values are allowed for variable nij then the DC model becomes a non-linear problem (NLP).

The relaxed models used in transmission expansion planning are shown, as well as constructive heuristics used to generate initial populations. Test results and comparisons for the genetic algorithm in question are shown.

Relaxed models in expansion planning

The DC model is considered ideal for research in transmission planning. This model is used both in its complete version and its relaxed versions. It is relaxed if some of its constraints are eliminated and/or if the number of added elements is non-integer. In large-sized, very complex problems, a feature of met heuristics is that they do not explore complete solution space; instead, they make simultaneous explorations in many subspaces, frequently leading to low quality solutions. The relaxed versions of the DC model are crucial in optimising because they help to identify regions where promising solutions are located, giving excellent reference points for searching in met heuristics.

The relaxation of the DC model makes the solution space continuous which, when solved using LP in association with a constructive heuristic algorithm (CHA), leads to identifying regions containing very good quality solutions where the optimal solution can eventually be found.

There are several solution proposals for transmission expansion planning when some DC model constraints are relaxed. The two most important relaxed versions are the transportation model and the hyid model.

The transportation model

The transportation model (TM) was obtained by relaxing nonlinear constraints (3) in the DC model (Garver, 1970; Romero, 2002; Escobar, 2010). The model was simplified by eliminating non-linear characteristics implicit in planning. The new relaxed model was an integer linear mixed problem (ILMP) taking the following form:

(5)

s.a.

(6)

(7)

An optimal solution for the TM can be found by using, for example, a anch and bound algorithm (Haffner, 2001; Gallego, 2007). However, this algorithm cannot find an optimal solution for a large-sized, complex planning problem. Obviously, if continuous values were allowed for variable nij,then the transport model would become a simple LP.

The hyid linear model

The hyid linear model (HLM) was obtained by relaxing nonlinear constraints (3) for the new circuits added to a system. It should be noted that type (3) constraints for already existing circuits in current topology were linear. Therefore, this model was an intermediate version between TM and DC models. The new relaxed model was an integer linear mixed problem (ILMP) taking the following form:

(8)

s.a.

(9)

(10)

(11)

(12)

Where S⁰ was the node-anch incidence matrix transpose of the system, made up of existent anches in initial topology and the buses connected to those anches, f0was the vector of power flows through the anches of the initial topology, with elements f ⁰_ij , S was the incidence matrix transpose of the complete system, and f was the vector of power flows of new circuits added to the system. Therefore, Ω was the group of indexes of existent circuits in base topology.

An optimal solution for HLM can be obtained by using, for example, a anch and bound algorithm as in the TM case. Again, this type of algorithms can not resolve large sized, great complexity optimisation problems. Also, in this case, if continuous values were allowed for variable n_ij then HLM would become an LP.

It should be observed that new circuits added to the system were not forced to satisfy KV Linan optimal solution for HLM. A new circuit added to the system could carry a different power flow than a circuit in parallel of the same type which was in the base topology (the existent one complies with both Kirchhoff´s laws but the new one only complies with the first). Ahyid non- linear model (HNLM) can be formulated in which all new circuits added to the system in parallel with existent circuits in base topology satisfy both Kirchhoff´s laws. However, this problem is an integer non-linear mixed problem (INLMP) having complexity close to that of the DC model. This type of model was not examined in this paper. Promising regions were identified in this paper by using CHA and relaxed models to generate excellent initial configurations for genetic algorithms.

Constructive heuristic algori thms in expansion planning

A constructive heuristic algorithm (CHA) is an iterative solution providing good solutions to complex problems. The CHA generally finds optimal solutions for small systems in applications like transmission expansion planning. However, as problem complexity increases, the solutions found are farther from being optimal. Different versions of the CHA that use relaxed versions of the DC model are presented next.

Garver´s algorithm

Garver was the first to propose a systematic CHA for planning (Garver, 1970; Escobar, 2010). Garver´s CHA finds good quality TM configurations. Obviously, the topology found by Garver´s CHA is not generally suitable for the DC model.

The basic structure of Garver´s CHA was used for proposing other CHAs for planning. The other CHAs that appeared after Garver´s original proposal differed from it in three aspects: they use a different model, different sensitivity indicator and local optimisation. The basic structure of a CHA for planning is presented here. It turned out to be a generalisation of Garver´s algorithm. A generalised CHA for planning took the following form:

1. Base topology was assumed as current topology and a mathematical model was chosen (TM, HLM, DC model, etc);

2. LP for the chosen mathematical model and for the current onfigurationwas solved. If LP solution indicated that the system operated without problems for current topology, then feasible topology for the chosen model had been found and was good quality for planning(in this case, step 4 would have been nextor, otherwise, step 3);

3. A sensitivity indicator was used to identify the most attractive circuit to be added to a system. Current topology was updatedby adding one or several of the identified circuits(step 2 would have been next); and

4. The added circuits were sorted in descending order by cost and an LP used in each case to verify whether the removal of a circuit would maintain the system in appropriate operating conditions. If the system operated adequately, then such circuit was removed. Removal simulation was repeated with all circuits.

Step 4 was necessary in CHA because some circuits added during solution were irrelevant in the final solution.

The remaining CHAS were obtained by starting generalised CHA. Therefore, Garver´s CHA was a generalised CHA having the following haracteristics: it used TM, the sensitivity indicator was the power flow through the added circuits provided in LP solution for TM and whose relaxation consisted of allowing continuous values for integer variables and it did not use the simulation strategy of removing the added circuits implemented in step 4.

Step 2 in Garver´s CHA solved the LP for TM considering only n_ij ≥0 and step 3 selected circuit n_ij ≠0 having the largest power flow. The power flow through the new circuits(not necessarily integer)was the sensitivity indicator for Garver´s CHA. Obviously, generalised CHA step 4 could be incorporated into Garver´s CHA and another sensitivity indicator could be used, such as the circuit having the largest nij value found in resolving LP in step 2.

Algorithms for the hyid linear model

Three CHAs could be implemented for HLM in planning by simply changing the logic for the behaviour of new circuits added to the system during each step. Three types of behaviour could be selected for each new circuit added to the system. All circuits added to a system only comply with Kirchhoff´s current law (KCL),new circuits added in parallel to other circuits of the same type in base topology should obey both Kirchhoff´s laws (KVL and KCL) but circuits added in new paths should only obey KCL and all circuits added should obey both KL. Each strategy led to different CHAs and different final configurations; in all cases, base topology circuits had to obey both KL. In the three cases, the sensitivity indicator could be that used in Garver´s CHA.

Hyid algorithm I

This algorithm type will be called constructive hyid heuristic algorithm I (CHHA-I). All circuits added had simply to obey KCL and circuits in base topology had to obey both KL. In spite of this, this algorithm added more circuits to the system than Garver´s CHA and the obtained configuration was usually unfeasible for the DC model.

The CHHA-I for HLM was a generalised CHA with the following characteristics: it used the hyid linear model (HLM) and Garver´s sensitivity indicator. The newest and most important circuit was thus that taking the largest power flow in resolving the LP. Therefore, current topology LP for the HLM model was solved in step 2considering only n_ij ≥ 0 and circuit n_ij ≠0 taking the largest power flow was chosen in step 3, i.e. .

An LP slightly different to the HLM presented in (8)-(12) was solved in step 2 above for implementing the CHHA-I. The relationship Sf + Sofo + g = d was thus substituted for relationship Sf + Sofo+ S'f' = d where S' was the node-anch incidence matrix obtained from added circuits and f' was the vector for power flows through the added circuits, with elements f'_ij . A new group of constraints had to be added. It should be noted that the new LP had three flow vectors:a flow vector for existent circuits in base topology, a flow vector for the added circuits and a third flow vector for the new circuits that had to be added to the solution of the LP, based on current topology.

Hyid algorithm II

In the constructive hyid heuristic algorithm II (CHHA-II), the added circuits which were parallel to existent circuits of the same type in base topology had to obey both KL and circuits added to new paths had only to obey the KCL. In principle, this algorithm should have added more circuits to the system than CHHA-I, although it was also generally unfeasible for the DC model.

This algorithm differed from the CHHA-I in the type of LP solved during step 2.

To implement the CHHA-II, a slightly different LP to the HLM presented in (8)-(12) had to be solved in step 2. The same modifications as for CHHA-I were thus applied, i.e. the relationship Sf + Sofo + g = d had to be substituted by the relationship Sf + Sofo+ S'f' = d , although in this case S' was the node-anch incidence matrix formed by the added circuits corresponding to paths in which no circuits were present in base topology and f′ was the vector for power flows through circuits added in new paths, with elements f'_ij. Also, a new group of constraints had to be added for all circuits added in new paths. In addition, whenever a circuit was added in a anch in which there was already at least one circuit in base topology, the n^o_ij vector had to be updated.

Hyid algorithm III

In constructive hyid heuristic algorithm III (CHHA-III), all added circuits satisfied both KLs. The fundamental aspect of this algorithm was that final topology was feasible for the DC model. This important property arose from the fact that all added circuits obeyed both KLs. The iterative process stopped when balance load-generation was satisfied. This algorithm was proposed by Villasana-Garver-Salon (VGS) (Villasana, 1985).

To implement the CHHA-III, a LP slightly different from the HLM presented in (8)-(12) had to be solved in step 2. Thus, continuous values for integer variables nij≥0 had to be allowed. Additionally, in each step of the algorithm, the vector n⁰_ij was updated with the addition of every new circuit and, whenever a circuit corresponding to a new anch was added to the system, set Ω had to be updated also.

Algorithms for the DC model

Many existing heuristic algorithms and CHAs work directly with the DC model and, therefore, find feasible and good quality topology for the DC model. Only the two CHA used in this paper are examined. CHAs have been widely applied in electricity transport planning in versions called least effort criterion (LEC) and least load loss (LLL).

In each CHA step, LP for current topology was solved from the information from base topology and the added circuits. The type of LP that each CHA solved had to be identified. It should be noted that if values for n_ij(added circuits) were known in the DC model (1)-(4), the resulting problem would be a system of equations and inequations whose solution may or may not have be en feasible. To help in the solution, the system of algeaic equations and inequations could be transformed into a new LP having new variables representing the so-called artificial generators, one for each load bus. Therefore, for current topology k, the resulting LP that the CHA solved would have assumed the following form:

(13)

s.a.

(14)

(15)

Where n^k_ij represented the circuits added to find the current topology k, Ω₀ was the group of indexes for the existent circuits in the current topology, r was the vector of artificial generators whose elements were r_s in each load bus, and Γ was the group of indexes for the load buses; w was a measure of the problem´s unfeasibility and w = 0 indicated that the system operated appropriately.

Least effort criterion algorithm

The least effort criterion algorithm (LEC) (Monticelli, 1982; Escobar, 2010) is a generalised CHA having the following characteristics: it uses the DC model, the sensitivity indicator identifies the most important circuit producing the largest distribution of flows once added to current topology, it uses a fictitious network to solve disconnected node problems and solves a slightly different LP from that described in (13).

The CHA of LEC allowed circuit overload in LP solution. Therefore, power limit constraints were eliminated for lines and transformers in the model. The solution of each LP finished with w=0 since the circuits could be overloaded. Circuit addition in the CHA of LEC stopped when there were no overloaded, real or fictitious circuits. The criterion used for selecting new circuits was:

Where θ values were obtained from solution of the LP and γij was the susceptance of a circuit in path (i, j). The most attractive circuit was that having the largest absolute value in IS_ij. The CHA of LEC uses a fictitious network having adequate susceptance values in a sufficient number of paths to have the whole system connected to make the solution of the system always finish with w = 0 and to have values of θ available (for calculating IS_ij). The fictitious network´s circuits were only used when there was no way to overload the normal circuits.

Least load loss algorithm

The least load loss algorithm (LLL) (Pereira, 1985; Escobar, 2010) is similar to the LEC algorithm and the only difference between them is that in the former the sensitivity indicator identifies the most important circuit that produces the largest decrease in load cut once added to current topology.

In the resolving LP, the CHA of LLL did not allow overload in the circuits and operational problems were represented by load shedding in current topology. If the solution of the LP finished with w ≠ 0 , then the system did not operate properly and more circuits had to be added to current topology. Adding circuits to the CHA of LLL stopped when the solution of the LP presented zero load shedding. The criterion used for selecting new circuits in the LLL algorithm was:

Where ^πj was the Lagrange multiplier of constraint j from the group of constraints (14). The most attractive circuit was that having the largest value in ISij. To be able to compute the values of IS_ij, the CHA of LLL required a fictitious network to have the complete system connected.

More than one circuit could be added in the two CHAs using the DC model, generating paths connecting isolated nodes with the rest of the system. The two CHAs could include normalisation by dividing the ISij by c_ij.

Using traditional heuristic algorithms in expansion planning

The importance of generated topologies for CHA

The topologies found using CHA can be used in several ways within metaheuristic structure. A topology found by a CHA can be considered good if it shows one or both of the following characteristics: it has a good objective function (i.e. it represents a quality investment proposal) and the topology has a high percentage of circuits forming part of optimal topology. These two characteristics do not always concur in any one topology regarding planning.

Topology having good objective function can be considered suboptimal. Such topology can be used in a GA´s initial population. Topology having a high number of circuits from optimal topology is fundamental in optimisation methods like GA because it can be transformed into optimal topology by means of appropriate operators. Virtually all topologies found by CHA have a significant number of circuits forming part of the optimal topology.

An initial GA population can be considered high quality if the circuits forming part of optimal topology are distributed in different initial population topologies (Goldberg, 1989).

In this case, the selection and recombination operators can collect all these circuits into a single topology, incorporating them in optimal or suboptimal configurations. If circuits from optimal topology are not present in the initial population, the only way to build optimal topology is by means of the mutation operator, which is considered a secondary operator in the GA.

Initial randomly-generated populations have a reduced number of circuits in optimal configuration for large-size systems in planning. Mutation should thus generate these circuits, increasing the GA´s computational effort. Relaxed models and CHAs were used in this paper in generating the initial population for the GA having characteristics regarding optimal or sub-optimal solutions requiring the addition of a large number of circuits, as in the] case of the Brazilian North-Northeastern test system.

Generating topologies for metaheuristics

The following procedure was used for generating a group of ifferent topologies for each mathematical model and each CHA analysed:

1. The best topology for the mathematical model selected and for the chosen CHA was generated. Supposing that circuits were added in p paths and that k ≤ p different topologies were to be found, p circuits were sorted in descending order regarding cost; and

2. The information for each of the first k circuits sorted in th previous step was used to find k new topologies. Each new topology was obtained by repeating step 1 but, in each case, adding one of the k circuits was forbidden. This process could be easily implemented, temporarily increasing the cost of the circuit analysed to avoid its selection.

The previous strategy generated k + 1 different topologies for the mathematical model and the selected CHA. Topology diversity could be increased through small changes in the iterative process, such as: modifying the sensitivity indicator if alternative proposals existed, eliminating step 4 from the generalised CHA and finishing the process before stopping criterion in generalised CHA was met and forbidding some of the k circuits found by the basic algorithm.

In the first case, the sensitivity indicator could be modified in Garver´s algorithm and the circuit having the largest value n_ij added and/or simultaneously the integer part of all the circuits after resolving the first LP had also been added. These modifications could also be implemented in all the CHAs for the hyid model. Such sensitivity indicator could be normalised in least effort criterion and least load loss algorithms by dividing the factores de sensibilidad de MCC y CME, éstos pueden ser modi original value by circuit cost. The second proposal is simpler and seeks to keep excess circuits added by the CHA and which maybe interesting for the DC model. The third modification seeks to avoid the irrelevant addition of circuits in final CHA phase. A large number of circuits are usually added during the final CHA phase to solve small demand problems in distant buses. Therefore, the process can be stopped prematurely to avoid adding irrelevant circuits. The last property was included to augment initial population variability. This strategy produced a large number of good initial topologies and was used to generate an initial population for the GA.

Applying the genetic algorithm

The topologies found by the CHA can be used in different ways within the structure of metaheuristics. In this paper these topologies were used to generate an initial population in a GA.

The genetic algorithm used was basically an improved version of the GA presented in (Gallego, 1998a). For more details on the theory of genetic algorithms and metaheuristics see (Glover, 2002), and for their application to planning see (Gallego, 1998a; Da Silva, 2000). An initial population was regarded as having excellent quality if optimal topology genes were distributed among the elements constituting it. The initial population generated using the CHA for the different models was applied to 4 electricity distribution systems: (1) the Garver system with 6 buses, 15 anches and 760 MW demand, (2) the Southern Brazilian system (SB) with 46 buses, 79 anches and 7,660 MW demand, (3) the Colombian system in 2012 with 93 buses, 155 anches and 14,559 MW demand and (4) the North-Northeast Brazilian system in Plan P1 with 87 buses, 183 anches and a demand of 20,316 MW. These 4 systems were selected because they present different levels of complexity. It should be noted that a large-sized system does not necessarily present great complexity. A system is regarded as being highly complex during planning if it presents a high level of disconnection and requires many additions to optimal topology. Only the first two systems had enough data to carry out planning both with and without rescheduling generation and had a well-known optimal solution. Only sub-optimal solutions were knownfor the other systems.

The optimal solution was identified for the Garver system by almost all CHA and it therefore formed the initial population. For the Southern Brazilian system (SB), all solution circuits were distributed in the initial population and, although no CHA identified the optimal solution, some CHAs identified solutions differing from the optimal only in one circuit. Anyway, having excellent quality initial configurations for resolving optimisation in the two previous systems, using metaheuristic methods only reduced computing time since, in low complexity systems like these, it is always possible to find the optimal solution even though the initial population has been randomly generated.

When applying the constructive heuristic algorithms described in this paper to the Colombian system in 2012, 14 of the 17 circuits from the best known solution were identified. An important characteristic of the CHA is that they frequently identify future network base structure while circuits from the best solution whose capacity is small are less frequently identified. The Colombian system was considered a large size and medium complexity system.

For the Brazilian North-Northeast system, 87.1% of the circuits from the best solution known were present in the initial population. In this system, it was difficult to quantify the amount of suboptimal circuits present in the initial population since there were many sub-optimal solutions having very similar investment values and radically different topologies. The concept of sub-optimal circuit depended on the sub-optimal topology taken as reference. A more interesting aspect was that the circuits present in the best solution forming the initial population represented 97.77% of investment in the best known solution. In other words, the circuits identified were the most important and the most expensive in the best known solution. Table 1 shows the comparative results for the different systems used.

The genetic algorithm should have found circuits which are not present in the initial population using the mutation operator. Obviously the selection and/or mutation operator can eliminate optimal circuits in the initial population and, in such cases, the mutation operator must reconstruct them. Also, a GA using good quality initial population must use low selective pressure (i.e. the survival of topologies having low quality objective function must be preserved).

Test and results

In this case, only the results obtained for the Colombian and the Brazilian North-Northeast systems are shown.

Colombian system

This system´stopology and data were available in (Escobar, 2002). The GA using an initial population generated in the way presented in this paper found the best solution known for the Colombian system. Thus, the best solution obtained, with an investment of v = 560 million dollars and load cut of w = 0.2 MW had the following topology:

Also, the best solution obtained with w = 0 MW had v = 562,42 investment. Table 1 shows the quantity of anches identified by the CHAs corresponding to the best solutions. To find these configurations, the GA solved around 4,250 LP´s.

Brazilian North North-eastern system

The data for this system was available in (Escobar, 2002). Results for the P1 case are displayed. This was considered a high complexity system because it was highly disconnected and needed many transmission lines to find feasible solutions. Additionally, no optimal solution was known. Using the initial population generated for this paper, a solution having v = 1.356.712.000 US $ investment and w = 3.3 MW load cut was found. It had the following topology:

For w = 0 shedding load, the solution required an investment of v = 1.360.961.000 US $, and had following configuration:

Both solutions corresponded to the same region in the search space because they were topologically similar, having differences in only five paths. The GA solved around 80,000 LPs to find these configurations.

Results for the two solution strategies are shown for the Colombian system and Brazilian North-Northeast System. The same algorithm was used but different initial populations were used.

The algorithm was run ten times to compare their performance. Test were also run in which a premature cut was made, by contrast with runs where normal convergence was allowed. For the Colombian system, execution was stopped after 2,000 LPs and normal convergence was found after 20,000 LPs. For the Brazilian North-Northeast System, the cut was made after 20,000 LPs and convergence happened at 80,000 LPs. Table 2 shows the results, where LP indicates mean LP values for the ten runs and v indicates the best solution found.

Initial populations were generated in the following three ways: totally random (ALE), controlled random (ALC) and using constructive heuristic algorithms (CHA). A number of lines between 0 and the top limit were enerated for each path by the first strategy. For the second, np transmission lines were generated in a random np step process, where np was close to the number of lines in the best topologies for the system being studied. np = 20 values for the Colombian system and np = 65 for the Brazilian system were used. In Table 2, C means the Colombian system, C -ALE is the case using random, C-ALC controlled random and CCHA CHA generated initial population. Investment was measured in millions of US dollars. The results clearly showed superior performance for CHA regarding execution speed and solution quality. The difference was even greater in the Brazilian system because of its high complexity.

Conclusions

A genetic algorithm has been presented which was initialised with constructive heuristic algorithms and it has been shown that it was more efficient than the same algorithm using a random initial population; such difference could be highly significant in complex systems. The results coincided with observations made by other researchers investigating the effect of initialisation on genetic algorithms. The paper has also shown a new use for met heuristic techniques, namely as an auxiliary method for improving overall performance of the globally met heuristic optimisation technique. Based on this paper´s results and those in other publications, our results have indicated how a currently established initial solution can be restated (this would also apply to a set of initial solutions necessary for initialising any met heuristic algorithm). This might be very effective for engineering problems involving high mathematical complexity.

---

References

Da Silva, E.L., Gil, H.A., Areiza, J.M., Transmission Network Expansion Planning under an Improved Genetic Algorithm., IEEE Transactions on Power Systems, Vol. 15, No. 4, November, 2000, pp 1168-1175.

Escobar, A. H., Planeamiento Dinámico de la Expansión de Sistemas de Transmisión Usando Algoritmos Combinatoriales., Universidad Tecnológica de Pereira, tesis de Maestría, 2002.

Escobar, A. H., Gallego, R. A., Romero, R., Multistage and Coordinated Planning of the Expansion of Transmission Systems., IEEE Transactions on Power Systems vol. 9, no. 2, pp. 1565-1573, November 2004.

Escobar, A., Romero, R., Gallego, R. A., Modelos Usados en el Planeamiento de la expansión a Largo Plazo de Sistemas de Transmisión de Energía Eléctrica., Taller de publicaciones Universidad Tecnológica de Pereira, 2010, pp. 22-76.

Gallego, R.A., Monticelli, A., Romero, R., Transmission System Expansion Planning by Extended Genetic Algorithm., IEE Proceedings - Generation, Transmission and Distribution, Vol. 145(3), May, 1998a, pp.329-335

Gallego, R.A., Monticelli, A., Romero, R., Comparative Studies of Non-Convex Optimization Methods for Transmision Network Expansion Planning., IEEE Transactions on Power Systems, Vol. 13, No. 3, August, 1998b, pp.822-828.

Gallego, R.A., Monticelli, A., Romero, R., Tabu Search Algorithm for Network Synthesis., IEEE Transactions on Power Systems, Vol. 15, No. 2, May, 2000, pp. 490-495.

Gallego, R. A., Escobar, A., Romero, R., Optimización en Sistemas Eléctricos I - Programación Lineal., Taller de publicaciones Universidad Tecnológica de Pereira, 2003, pp. 77-218.

Gallego, R. A., Escobar, A., Romero, R., Programación Lineal Entera., Taller de publicaciones Universidad Tecnológica de Pereira, 2007, pp. 87-191.

Garver, L.L., Transmission Network Estimation Using Linear Programming., IEEE Trans. Power App. Syst., Vol. PAS-89, September-October, 1970, pp. 1688-1697.

Glover, F., Kochenberger, G.A., Handbook of Metaheuristics,Kluwer Academic Publishers., Boston/Dordrecht/LOndon, 2002, pp. 37-184.

Goldberg, D.E., Genetics Algorithms in Search, Optimization and Machine Learning, Addison Wesley, Reading, Massachusetts, 1989.

Haffner, S., Monticelli, A., Garcia, A., Romero, R., Specialized Branch and Bound Algorithm for Transmission Network Expansion Planning., IEE Proceedings -Generation, Transmission and Distribution, Vol. 148(5), September 2001, pp. 482 -488.

Hansen, P., Mladenovic, N., A Tutorial on Variable Neighborhood Search., Les Cathiers du GERAD, G-2003-46, July 2003.

Latorre, G., Cruz, R.D., Areiza, J.M., Villegas, A., Classification of Publications and Models on Transmission Expansion Planning., IEEE Transactions on Power Systems, Vol. 18, No. 2, May 2003, pp 938-946

Lee, C.W., Ng, S.K.K., Zhong, J., Wu, F.F., Transmission Expansion Planning From Past to Future., Power Systems Conference and Exposition, Oct. 29 2006-Nov. 1, PSCE ´06. IEEE PES, Atlanta, GA, USA, 2006, pp. 257 - 265

Maaranen, H., Miettinen, K., Penttinen, A., On Initial Populations of a Genetic Algorithm for Continuos Optimization Problems., Journal of Global Optimization, 37, 2007, pp 405- 436.

Monticelli, A., Santos, Jr. A., Pereira, M.V.F., Cunha, S.H., Parker, B.J., Praga, J.C.G., Interactive Transmission Network Planning Using a Least-Effort Criterion., IEEE Trans. Power App. Systems, Vol. PAS-101, No. 10, 0ctober, 1982, pp. 3919-3925.

Pereira, M.V.F., Pinto, L.M.V.G., Application of Sensitivity Analysis of Load Supplying Capability to Interactive Transmission Expansion Planning., IEEE Transaction on Power Apparatus and Systems, Vol. PAS-104, No. 2, Feuary, 1985, pp. 381 -389.

Romero, R., Monticelli, A., Garcia, A., Haffner, S., Test Systems and Mathematical Models for Transmission Network Expansion Planning., IEE Proceedings - Generation, Transmission and Distribution, Vol. 149(1), 2002, pp. 27-36.

Romero, R., Rider, M.J., Silva, I., A Metaheuristic to Solve the Transmission Expansion Planning., IEEE Transactions on Power Systems, Vol. 22, No. 4, November, 2007, pp. 2289- 2291.

Villasana, R., Garver, L.L., Salon, S.J., Transmission Network Planning Using Linear Programming., IEEE Trans. Power App. Systems, Vol. PAS-104, No. 2, Feuary 1985, pp. 349-356.

---