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

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.

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

ABSTRACT

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.

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.