Unidad Azcapotzalco

División de Ciencias Básicas e Ingeniería

económico con funciones de costo no convexas y zonas muertas de unidades térmicas”

Maestro en Ciencias de la Computación

Benjamín Carpio Flores

Asesor: Dr. Javier Ramírez Rodríguez

Departamento de Sistemas UAM Azcapotzalco

México, Octubre-2007

“Métodos heurísticos aplicados al despacho

Tesis que para obtener el grado de

Presenta:

Dedicatorias

A mi niña

A miA mis hermanos Tino, Hugo, Jaz,

A Dios, por los regalos que me ha dado.

Agradecimientos:

mi asesor, Ing. Javier Ramírez Rodríguez. Gracias por su amistad y dedicación.

todos mis profesores de la UAM, por el tiempo y conocimiento brindados.

Al MC Anselmo Sánchez Sánchez, por la disposición y atención a mis dudas.

Alma Teresa, tus sonrisas son mi mayor felicidad. A mi esposa Alma, gracias por tu amor y consejos.

s padres, Justino, Epi y Tomasa , por sus sacrificios, amor y enseñanzas. David y Tomi, ya no me quieran tanto☺.

A A

INDICE Pág.

Lista de tablas y figuras ………………………………………………………… i

Nomenclatura …………………………………………………………………… iv

Resumen …………………………………………………………………………. v

Abstract…………………………………………………………………………... vii

Introducción …………………………………………………………………….. viii

Antecedentes …………………………………………………………………….. xiii

Justificación ……………………………………………………………………... xvii

Objetivos ………………………………………………………………………… xix

Contenido de la tesis…………………………………………………………….. xx

CAPÍTULO 1. DESPACHO ECONÓMICO.

1.1 Introducción…………………………………………………………. 1

1.2 Despacho Económico Sin Pérdidas…………………………………. 1

1.3 Otros problemas de Despacho Económico…………………………. 4

1.4 Técnicas clásicas de solución………………………………………... 5

1.5 Casos de Estudio……………………………………………………... 6 1.5.1 Caso de estudio 1, 7 Us (función de costo no convexa de un PIE y zona muerta) ………………………………………………………………... 6 1.5.2 Caso de estudio 2, 36 Us (problema de mayor tamaño) …………………. 10

1.5.3 Caso de estudio 3, 3 Us (funciones no convexas en las tres unidades que consideran puntos de válvula) ……………………………………….. 12

CAPÍTULO 2. MÉTODOS HEURÍSTICOS.

2.1 Introducción ………………………………………………………… 14

2.2 Algoritmos Genéticos ……………………………………………….. 14

2.3 Búsqueda local ………………………………………………………. 16

2.4 Algoritmo de Recocido Simulado ………………………………….. 18

2.5 GRASP ………………………………………………………………. 19

2.6 Satisfacción de Restricciones ……………………………………….. 22

2.7 Algoritmos Híbridos ………………………………………………… 23

CAPÍTULO 3. IMPLEMENTACIÓN DEL ALGORTIMO GENÉTICO.

3.1 Introducción ………………………………………………………… 24

3.2 Descripción del programa ………………………………………….. 25

3.3 Población inicial y codificación …………………………………….. 26 3.3.1 Codificación ………………………………………………………………… 26 3.3.2 Representación de los límites de potencia del generador ………………... 27 3.3.3 Decodificación ………………………………………………………………. 27 3.3.4 Codificación de la zona muerta …………………………………………… 27

3.4 Evaluación …………………………………………………………… 29 3.4.1 Aptitud de los individuos …………………………………………………... 29 3.4.2 Funciones de costo ………………………………………………………….. 29 3.5 Selección ……………………………………………………………... 31 3.5.1 Selección por torneo ………………………………………………………... 31

3.6 Nuevas Generaciones ……………………………………………….. 31 3.6.1 Mutación y Cruza …………………………………………………………... 31 3.6.1.1 Zona muerta ………………………………………………………... 34 3.7 Ajuste de parámetros particulares del AG al problema de DE ….. 34 3.7.1 Tamaño de la población ……………………………………………………. 35 3.7.2 Elitismo ……………………………………………………………………... 37 3.7.3 Factor de penalización por incumplimiento del balance de potencia …... 38 3.8 Resumen de resultados del AG (DE con funciones convexas) …… 42 3.9 Algoritmo Genético Híbrido ………………………………………. 43 3.9.1 Población inicial a partir de algoritmo de SR …………………………….. 43 3.9.2 Población inicial a partir de fc_GRASP ………………………………….. 45 3.9.3 Adición de búsqueda local al AG ………………………………………….. 46 3.10 Resumen de resultados del AGH (DE con funciones convexas) ... 51

CAPÍTULO 4. IMPLEMENTACIÓN DEL ALGORITMO DE RECOCIDO SIMULADO.

4.1 Introducción ………………………………………………………… 52

4.2 Descripción del programa ………………………………………….. 53

4.3 Solución inicial ………………………………………………………. 53 4.3.1 Zona muerta ………………………………………………………………... 53

4.4 Vecindades …………………………………………………………... 54 4.4.1 Zona muerta ………………………………………………………………... 55

4.5 Ajuste de los parámetros de ARS ………………………………….. 55 4.5.1 Temperatura ………………………………………………………………... 56 4.5.2 Ajuste de k0 en la búsqueda local …………………………………………. 59 4.6 Resumen de resultados del ARS (DE con funciones convexas) ...... 60 CAPÍTULO 5. IMPLEMENTACIÓN DEL GRASP. 5.1 Introducción ………………………………………………………... 61

5.2 Descripción del programa …………………………………………. 62

5.3 Fase Constructora ………………………………………………….. 62

5.4 Fase de Búsqueda Local ……………………………………………. 68

5.5 Zona muerta ………………………………………………………... 68

5.6 Ajuste de parámetros, Nitr, α ……………………………………... 68

5.7 Resumen de resultados del GRASP (DE con funciones convexas) 74

CAPÍTULO 6. RESULTADOS FINALES.

6.1 Introducción ………………………………………………………… 75

6.2 Resultados para el caso de estudio 1, 7 unidades ………………… 76

6.3 Resultados para el caso de estudio 2, 36 unidades ……………….. 86

6.4 Resultados para el caso de estudio 3, 3 unidades ………………… 87

CONCLUSIONES ………………………………………………………………. 89

REFERENCIAS ………………………………………………………………… 91

APENDICE I Solución analítica al caso de estudio 1 (7 Us) por el método

del lagrangiano.

APENDICE II Código fuente de los programas en lenguaje C

Lista de tablas y figuras Tablas Tabla 1.1 Limites de potencia y coeficientes abc de las unidades del caso 1. Tabla 1.2 Solución óptima del caso 1 con funciones de costo de segundo grado convexas. Tabla 1.3 Datos de las 36 unidades del caso 2. Tabla 1.4 Solución óptima del caso 2 con funciones de costo de segundo grado convexas Tabla 1.5 Datos de las 3 unidades del caso 3. Tabla 1.6 Solución óptima del caso 3. Tabla 2.1 Algoritmo Genético simple. Tabla 2.2 Algoritmo de búsqueda local. Tabla 2.3 Algoritmo de Recocido Simulado. Tabla 2.4 Algoritmo GRASP simple. Tabla 2.5 Algoritmo de fase de construcción del GRASP basado en valor. Tabla 2.6 Algoritmo de fase de construcción del GRASP basado en cardinalidad. Tabla 2.7 Algoritmo de búsqueda local del GRASP. Tabla 3.1 Estructura de datos generador. Tabla 3.2 Límites de potencia usados en la decodificación del valor entero Pcod según el valor de bit_zm. Tabla 3.3 Factores de escalamiento de aptitud para cada caso de estudio. Tabla 3.4 Tipos de funciones de costo de los casos de estudio. Tabla 3.5 Unidades de los coeficientes abcef de la función general de costo. Tabla 3.6 Tabla de costos del PIE CC Mexicali. Tabla 3.7 Parámetros utilizados por defecto para el AG. Tabla 3.8 Parámetros a determinar para el AG. Tabla 3.9 Resultados del AG para distintos valores del FP_IBP y solución óptima del caso 1. Tabla 3.10 Ajustes del FP_IBP y número de generaciones para cada caso de estudio. Tabla 3.11Resultados del AG para los casos de estudio 1, 2 y 3 (con funciones de costo convexas). Tabla 3.12 Datos para el ejemplo de SR. Tabla 3.13 Algoritmo para crear una solución factible por SR. Tabla 3.14 Soluciones creadas con a) SR b) fc_GRASP. Tabla 3.15 Comparativo del costo de las soluciones creadas por SR y fc_GRASP. Tabla 3.16 Algoritmo Genético Híbrido (AGH). Tabla 3.17 Generaciones iniciales n del AGH para cada caso de estudio. Tabla 3.18 Comparativo de aptitudes después de 75 y 150 generaciones, para el AG con diferentes tipos de población inicial, caso 1. Tabla 3.19 Ajuste del parámetro k0 para el caso 1 (7 U’s). Tabla 3.20 Ajuste del parámetro k0 para el caso 2 (36 U’s). Tabla 3.21 Ajuste del parámetro k0 para el caso 3 (3 U’s). Tabla 3.22Resultados del AGH para los casos de estudio 1, 2 y 3 (con funciones de costo convexas). Tabla 4.1 Datos del ejemplo para el cálculo de una solución vecina. Tabla 4.2 Rangos permisibles de movimiento a partir de la solución inicial del ejemplo 4.1. Tabla 4.3 Parámetros utilizados por defecto para el ARS. Tabla 4.4 Criterio de Metrópolis para aceptación de una solución. Tabla 4.5 Máxima diferencia en costo mdc para el caso 1 con funciones convexas. Tabla 4.6 Valores de mdc y criterios de paro para los casos de estudio 1,2 y 3. Tabla 4.7 Resultados para diferentes valores de T. Resaltados los valores de referencia para el cálculo de los porcentajes. El valor mínimo y el valor promedio son de diez pruebas. Tabla 4.8 Parámetros del ARS para cada caso de estudio.

i

Tabla 4.9 Ajuste de la búsqueda local a través del parámetro k0 para caso 1 (7 U’s). Tabla 4.10 Ajuste de la búsqueda local a través del parámetro k0 para caso 2 (36 U’s). Tabla 4.11 Ajuste de la búsqueda local a través de parámetro k0 para caso 3 (3 U’s). Tabla 4.12 Resultados del ARS para los casos de estudio 1, 2 y 3 (con funciones de costo convexas). Tabla 5.1 Algoritmo general GRASP para el DE. Tabla 5.2 Algoritmo GRASP (fase constructora) para el DE. Tabla 5.3 Datos del ejemplo 5.1. Aplicación del GRASP. Tabla 5.4 Resultados del GRASP al caso 1, con k0 = 100 y distintos valores de alfa (0.0, 1.0 y 0.5). Tabla 5.5 Resultados del GRASP al caso 1, con diferentes combinaciones de N_itr y k0. Tabla 5.6 Ajuste de k0 para el caso 1 (7 U’s). Tabla 5.7 Resultados del GRASP para el DE del caso 2, con diferentes combinaciones de N_itr y k0. Tabla 5.8 Ajuste de k0 para el caso 2 (36 U’s). Tabla 5.9 Resultados del GRASP para el DE del caso 3, con diferentes combinaciones de N_itr y k0. Tabla 5.10 Ajuste de k0 para el caso 3 (3 U’s). Tabla 5.11 Parámetros del GRASP determinados para cada caso de estudio. Tabla 5.12 Resultados del GRASP para los casos de estudio 1, 2 y 3 (con funciones de costo convexas). Tabla 6.1 Ajustes de los parámetros de las heurísticas, caso 1 (7 U’s). Tabla 6.2 Caso 1. Aplicación del AG. Número de generaciones = 300, FP_IBP = 2500, probabilidad de cruza = 0.8, probabilidad de mutación = 0.01. a) todas las unidades con funciones de costo convexas, b) unidad 7 con función de costo no convexa y zona muerta. Tabla 6.3 Caso 1. Aplicación del AGH. Número de generaciones = 75, K0 = 500, FP_IBP = 2500, probabilidad de cruza = 0.8, probabilidad de mutación = 0.01. a) todas las unidades con funciones de costo convexas, b) unidad 7 con función de costo no convexa y zona muerta. Tabla 6.4 Caso 1. Aplicación del Algoritmo de Recocido Simulado. T= 500 000, k0 = 50, a) todas las unidades con funciones de costo convexas, b) unidad 7 con función de costo no convexa y zona muerta. Tabla 6.5 Caso 1. Aplicación del GRASP. Nitr = 300, k0 = 400, a) todas las unidades con funciones de costo convexas, b) unidad 7 con función de costo no convexa y zona muerta. Tabla 6.6 Resumen de la aplicación de los métodos heurísticos al caso 1 con funciones de costo convexas. Tabla 6.7 Resumen de la aplicación de los métodos heurísticos al caso 1, con zona muerta y función de costo no convexa para unidad 7. Tabla 6.8 Resultados del ARS con zona muerta y función no convexa en U7, k0 = 100. Tabla 6.9 Evaluación de funciones de costo, caso 1 (7Us) sin zona muerta. Demanda = 870 MW Tabla 6.10 Resultados de las heurísticas para el caso 1. U7 con función de costo real. Demanda = 870 MW. Tabla 6.11 Evaluación de funciones de costo, caso 1 (7Us). Demanda = 700 MW. Tabla 6.12 Resultados de las heurísticas para el caso 1. U7 con función de costo real. Demanda = 700 MW. Tabla 6.13 Evaluación de funciones de costo, caso 1 (7 Us). Demanda = 1 050 MW. Tabla 6.14 Resultados de las heurísticas para el caso 1. U7 con función de costo real. Demanda = 1 050 MW. Tabla 6.15 Ajustes de los parámetros de las heurísticas, caso 2 (36 U’s). Tabla 6.16 Resumen de la aplicación de los métodos heurísticos al caso 2 con funciones de costo convexas. Tabla 6.17 Resumen de la aplicación de los métodos heurísticos al caso 2, con zona muerta y función no convexa para la unidad 36. Tabla 6.18 Ajustes de los parámetros de las heurísticas, caso 3 (3 U’s). Tabla 6.19 Resumen de la aplicación de los métodos heurísticos al caso 3 (3 Us). Tabla 6.20 Resultados del DE para el caso 3 (3 Us).

ii

Figuras Figura a) Semana típica de verano del Sistema Interconectado Nacional en México. Figura b) Curva de entrada-salida de la U3 de la central Mérida II. Figura c) Curva de consumo específico o régimen térmico de U3 Mérida tg. Figura d) Modelado del punto de válvula en unidades térmicas. Figura e) Planta de ciclo combinado. Figura f) Curva de entrada-salida de un ciclo combinado. Figura g) Curva de consumo específico basada en tres puntos del PIE CC Mexicali. Figura 2.1 Funciones de costo o curvas de entrada-salida de las unidades del caso 1. Figura 2.2 Régimen térmico en $/MWh del CC Mexicali (U7). Figura 2.3 Costos incrementales de las unidades del caso 1. Figura 2.4 Costos incrementales de los dos modelos utilizados para la unidad 7. Figura 2.5 Costos incrementales de las unidades del caso 2. Figura 2.6 Funciones de a) costo y b) costos incrementales de las unidades del caso 3. Figura 3.1 Cadena, individuo o cromosoma. Figura 3.2 Subcadena de 11 bits. Figura 3.3 Representación de diferentes valores de potencia a través del bit_zm para una unidad con zona muerta. Figura 3.4 Cruza de 2 individuos a nivel de bits, con pcruza = 14. Figura 3.5 Modificación del valor de potencia por operador de cruza, pcruza = 16. Figura 3.6 Operador de cruza a nivel de unidades con dos puntos de cruza, pcruza1 = 2, pcruza2=5. Figura 3.7 Operador de mutación modificó bit 23 en una cadena de longitud 33. Figura 3.8 a) aptitud mejor individuo b) aptitud promedio de cada generación c) balance de potencia BP, para poblaciones de 40 y 100 individuos, caso 1. Figura 3.9 a) aptitud mejor individuo b) aptitud promedio de cada generación c) balance de potencia BP, para poblaciones de 40 y 100 individuos, caso 2. Figura 3.10 Comparación de la convergencia del AG con y sin elitismo, a) aptitud del mejor individuo, b) BP, caso 1. Figura 3.11 Comparación de la convergencia del AG con y sin elitismo, caso 2. Figura 3.12 Curvas de las unidades con mayor costo incremental del caso1. Figura 3.13 Convergencia en aptitud y en BP del AG, con valores de FP_IBP de 2000, 2500 y 3000, caso 1. Figura 3.14 Curvas de las unidades con mayor costo incremental del caso 2. Figura 3.15. Convergencia en aptitud y en BP del AG aplicado al caso 2, con distintos valores de FP_IBP. Figura 3.16. Convergencia en aptitud y en BP del AG aplicado al caso 3, con distintos valores de FP_IBP. Figura 3.17 Convergencia del AGH con diferentes poblaciones iniciales, caso 1. Figura 3.18 Desempeño del AG con población inicial de soluciones factibles y no factibles para el caso 3 (DEPV de 3 unidades). Fig. 4.1 Evaluación de la función de Boltzman con valores de T referidos a la mdc del caso 1. Fig. 4.2 Desempeño del ARS para diferentes valores de T, caso 1 (7 U’s). Fig. 4.3 Desempeño del ARS para diferentes valores de T, caso 2 (36 U’s). Fig. 4.4 Desempeño del ARS para diferentes valores de T, caso 3 (3 U’s). Figura 5.1 Costo de las soluciones mejoradas de cada iteración, fase de construcción con α=0.5, caso 1 (7 U’s). Figura 5.2 Costo de las soluciones mejoradas de cada iteración, fase de construcción con α=1, caso 1 (7 U’s). Figura 5.3 Costo de las soluciones mejoradas de cada iteración, fase de construcción con α=0, caso 1 (7 U’s). Figura 6.1 Punto de operación de la unidad 7 (306 MW), caso 1 con 870 MW de demanda. Figura 6.2 Funciones de costo del caso 3 (3 Us).

iii

Nomenclatura AG Algoritmo Genético AGH Algoritmo Genético Híbrido ARS Algoritmo de Recocido Simulado ASR Algoritmo de Satisfacción de Restricciones BP Balance de Potencia CC Ciclo Combinado CENACE Centro Nacional de Control de Energía DE Despacho Económico DEPV DE con Punto de Válvula F Función de costo FP_IBP Factor de Penalización por Incumplimiento de Balance de Potencia GRASP “Greedy Randomized Adaptive Search Procedure” K0 Parámetro de ajuste de la intensidad de la búsqueda local kcal kilocaloría kWh Kilowatt-hora MWh Megawatt-hora Nitr Número de iteraciones del GRASP PDE Problema de despacho económico PIE Productor Independiente de Energía Pmin Potencia mínima Pmax Potencia máxima T Temperatura tam_pob Tamaño de la población Us Unidades V Vapor tg Turbogás

iv

Resumen En México, el Centro Nacional de Control de Energía (CENACE) de la Comisión Federal de Electricidad (CFE) realiza diariamente el despacho económico de generación. El problema de despacho económico (PDE) consiste en determinar la potencia que cada unidad generadora debe suministrar para cubrir la demanda pronosticada de un Sistema Eléctrico de Potencia al menor costo posible. La función de costo que se utiliza para la optimización del PDE es la curva de entrada-salida de las unidades térmicas y representa la cantidad o costo de combustible que la unidad consume por hora para la potencia generada. Para simplificar el problema, esta relación se representa por una función de segundo grado, convexa y continua, y entonces se utilizan técnicas de programación lineal para optimizar el problema. En realidad, las funciones de costo de las unidades térmicas son discontinuas y no convexas debido al cierre y apertura de válvulas en el sistema de la caldera para el control de la potencia del generador eléctrico. Por otra parte, funciones no convexas son derivadas de los modelos contractuales de algunos Productores Independientes de Energía, quienes adicionalmente declaran zonas muertas o prohibidas en las transiciones por las diferentes configuraciones del ciclo combinado. En este trabajo se muestra la aplicación de cuatro métodos heurísticos al PDE, donde se consideran funciones de costo no convexas y zonas muertas de unidades térmicas, para evaluar los costos de las simplificaciones que se realizan por las restricciones que impone el método clásico de solución. Los métodos heurísticos utilizados son el Algoritmo Genético (AG), Algoritmo Genético Hibrido (AGH), Algoritmo de Recocido Simulado (ARS) y el GRASP (greedy randomized adaptive search procedure). Se describen los ajustes de parámetros y procedimientos particulares al PDE, como son el factor de penalización por incumplimiento del balance de potencia FP_IBP (AG), parámetro de temperatura T (ARS), función miope (GRASP), el algoritmo de generación de vecindades para la búsqueda local (ARS, AGH, GRASP) y el algoritmo de satisfacción de restricciones para generar soluciones factibles (ARS, AGH). Para los algoritmos genéticos, la zona muerta zm es restringida desde la propia codificación, agregando un bit adicional bit_zm a la subcadena que representa a cada unidad. Para el GRASP y ARS, la zm se evita desde la generación aleatoria de la solución inicial. Los resultados muestran que con la evaluación de las funciones no convexas, a través de métodos heurísticos, se obtiene un mejor despacho de generación, con excepción del AG que requirió ser mejorado (AGH). En la comparación de los desempeños, el GRASP presentó la mejor calidad en las soluciones referidas a

v

costo y a variabilidad. Cualquier mejora en el despacho de generación resulta en ahorros importantes si consideramos los costos de producción por combustibles y costos variables que se tienen en el Sistema Interconectado Nacional que, por ejemplo, en el año 2006 totalizaron 86 mil millones de pesos. Palabras clave: Despacho Económico, Métodos Heurísticos, Algoritmo Genético, Algoritmo de Recocido Simulado, GRASP.

vi

Abstract In Mexico, the National Energy Control Center (CENACE) accomplishes the diary Economic Dispatch of generation (ED). The ED problem consists in determining the electric power outputs of thermal units to supply the forecast load on the system at minimum operating cost. In the traditional ED problem, convex quadratic functions are used to approximately represent the variable operation costs, which mostly depend on fuel. Then, the DE problem can be optimized using mathematical programming such as linear programming techniques. In fact, fuel cost functions of thermal units are discontinuous and non-convex due to the closing and opening of valves in the steam boiler system. Besides, non-convex functions are derived from the contractual models of some Independent Energy Generators, which additionally declare dead or prohibited zones in the transitions by the different configurations from the combined cycle technology. In this work, the application of four heuristic methods to the ED problem is presented, where non-convex cost functions and dead zones of thermal units are considered to evaluate the costs of the simplifications that are made by the restrictions that the classic method of solution imposes. The used heuristic methods are Genetic Algorithm (AG), Hybrid Genetic Algorithm (AGH), Simulated Annealing Algorithm (ARS) and the GRASP (greedy randomized adaptive search procedure). Adjustments of parameters and procedures particular to the PDE are described, such as power misbalance penalty factor (AG), temperature parameter T (ARS), myopic function (GRASP), the neighborhood algorithm for local search (ARS, AGH, GRASP) and the constraint satisfaction algorithm to generate feasible solutions (ARS, AGH). For the genetic algorithms, the dead zone zm is restricted from the own codification, having added an additional bit bit_zm to the sub-chain that represents each unit. For GRASP and ARS, the dead zone is avoided from the random generation of the initial solution. The results show that the fact of evaluating the non-convex functions with the heuristic methods approaches a better generation dispatch, with exception of the AG that required to be improved (AGH). In the comparison of the performances, the GRASP presented the best quality in the solutions referred to cost and variability. Any improvement in the generation dispatch is in important savings, if we considered the operating variable costs in the Interconnected National System of México that totalized, for example in year 2006, 86 billion pesos,. Keywords: Economic Dispatch, GRASP, Simulated Annealing, Genetic Algorithm, Heuristic methods.

vii

Introducción

El patrón de demanda de energía eléctrica de los consumidores es completamente irregular, con tendencias de mayor demanda por las tardes y noches que por las madrugadas. También los patrones son diferentes para los días de descanso y para días festivos. En la figura a) se muestra la demanda de energía de una semana típica del Sistema Interconectado Nacional de México, normalizada respecto a la demanda máxima anual.

0.5

0.6

0.7

0.8

0.9

1.0

1 5 9 13 17 21horas

Dem

anda

en

pu

Sábado Domingo Lun-Vie

Figura a) Semana típica de verano del Sistema Interconectado Nacional en México. Con estos comportamientos irregulares de las demandas, algunas unidades de generación deben entrar y salir del sistema, mientras que otras sólo necesitan cambiar su aportación en potencia siguiendo el perfil de la demanda. Al problema de decidir qué unidades deben participar para cubrir la demanda se llama Asignación de Unidades y al problema de asignar el nivel de potencia de cada generador en cada hora, se le conoce como Despacho de Generación. El Despacho Económico de generación (DE) consiste en determinar la potencia eléctrica que debe suministrar cada generador térmico para satisfacer la demanda de energía pronosticada al menor costo posible. Para ello se consideran principalmente los costos de generación termoeléctrica, que son variables debido a que las unidades generadoras convierten combustible en energía eléctrica con diferentes eficiencias. La función de costo que se utiliza para la optimización del problema de DE (PDE) es la curva de entrada-salida de cada unidad térmica. Esta curva representa la cantidad o el costo de combustible que una unidad consume por hora para la potencia a la que la unidad está generando. Esta relación se representa generalmente por un polinomio de segundo grado. Los datos de esta curva se

viii

obtienen de pruebas de consumo específico de las unidades o por cálculos de diseño. La figura b) muestra una curva de entrada-salida de una unidad turbogas de la central termoeléctrica Mérida II en México.

90,000

100,000

30,000

40,000

50,000

60,000

70,000

80,000

5 10 15 20 25 30 35 40

MW

$ / h

Figura b) Curva de entrada-salida de la U3 de la central Mérida II.

La curva de consumo específico o de régimen térmico representa el costo por

egawatt-hora (MWh) que tiene la unidad para una determinada potencia de salida. Este tipo de curva muestra la eficiencia de la unidad térmica. Obsérvese en la figura c que para valores mínimos de generación los costos por MWh son altos y la máxima eficiencia se presenta aproximadamente al 85% de la potencia máxima. La eficiencia máxima de esta unidad se alcanza cuando opera a 31 MW. La curva de régimen térmico se determina durante el periodo de pruebas de un generador nuevo o después de un mantenimiento mayor y se construye generalmente a partir de por lo menos tres puntos de operación, que corresponden al 50%, 75% y 100% de la potencia máxima.

m

6,000

6,500

2,000

2,500

3,000

3,500

4,000

4,500

5 10 15 20 25 30 35 40

$/M

Wh

5,000

5,500

MW

Figura a tg.

debido a que presentan brincos por el cierre y apertura de válvulas que se

c) Curva de consumo específico o régimen térmico de U3 Mérid En realidad las funciones de costo de las unidades térmicas son discontinuas,

ix

realizan en el sistema de la caldera para el control de la potencia del generador [12]. A este efecto se le conoce como punto de válvula y las curvas

presentativas son no convexas, como se aprecia en la figura d. re

0

1,000

2,000

3,000

4,000

5,000

6,000

7,000

8,000

50 150 250 350 450 550 650

MW

$/h

U1

U2

U3

Figura d) Modelado del punto de válvula en unidades térmicas.

Otro tipo de discontinuid s tipo ciclo combinado.

ste tipo de centrales es ades los presentan las unidadetán formadas por varias unidades turbogás donde losE

vapores a la salida de sus turbinas son reutilizados a través de un recuperador de calor que alimenta a la caldera de una unidad de vapor, ver figura e.

Figura e) Planta de ciclo combinado. Las curvas de entrada-salida y consumo específico de la unidad de ciclo combinado se obtienen para cada combinación de turbinas de gas con la unidad de vapor, lo cuál es útil cuando una o más unidades turbogás no están disponibles por falla o mantenimiento. En la figura f se muestran curvas características de entrada-salida de un ciclo combinado.

x

Figura f) Curva de entrada-salida de un ciclo combinado En el caso de las plantas de ciclo combinado de CFE, para el DE sólo se utiliza la curva correspondiente a la configuración disponible y generalmente corresponde al ciclo completo. Esto no sucede para algunos Productores Independientes de

nergía (PIE´s), quienes son empresas particulares a quienes se les permite la

o complementario. Además, estos IE´s han declarado zonas prohibidas de operación conocidas como “zonas

sí poder evaluar el impacto de las simplificaciones que se realizan.

os métodos heurísticos son herramientas eficientes de búsqueda de soluciones a roblemas complejos para los cuales no existe un algoritmo que los resuelva, o a roblemas con dominios tan grandes que no existe un algoritmo eficiente de olución. Las reglas y operaciones matemáticas que definen el funcionamiento de s métodos heurísticos son fáciles de entender e implementar. Entre los métodos eurísticos más populares utilizados para problemas de optimización se

Egeneración de energía eléctrica para venta exclusiva a CFE. Estos permisionarios declararon un rango de operación que incluye el paso por todas las configuraciones posibles. Las funciones de costo que se derivan de su régimen térmico contractual corresponden a una curva no convexa en el primer rango de operación y a una curva convexa en el rangPmuertas” por las dificultades técnicas y altos costos de parar o arrancar una unidad turbogás en las transiciones de cada configuración. Una de las metodologías más utilizadas en la solución del PDE es conocida como la técnica del Lagrangiano, que lo reduce a un problema de programación lineal donde las restricciones son incorporadas a la función objetivo a través de multiplicadores de Lagrange, uno por cada restricción; luego se aplica el método simplex para minimizar la función objetivo. Sin embargo, esta técnica requiere de estricta convexidad de la función objetivo y no se puede aplicar para evaluar funciones de costo no convexas ni discontinuidades. Por lo tanto, se deben buscar otras metodologías que permitan considerar estas situaciones operativas especiales y a Lppsloh

xi

encuentran el Algoritmo Genético (AG) y el Algoritmo de Recocido Simulado RS).

l AG toma los conceptos de la teoría de la evolución de Darwin para crear uevos individuos (soluciones) a través de operadores de cruza y mutación, que an sobreviviendo de generación en generación por su mejor aptitud. La base órica de estos algoritmos fue introducida por su creador John Holland en 1975 y s conocida como teoría de los esquemas [3].

l ARS imita un proceso de recocido en metalurgia, una técnica que incluye alentar y luego enfriar controladamente un material para aumentar el tamaño de us cristales y reducir sus defectos. El calor causa que los átomos se salgan de us posiciones iniciales (un mínimo local de energía) y se muevan de forma leatoria. El enfriamiento lento les da mayores probabilidades de encontrar onfiguraciones con menor energía que la inicial. En la analogía con el método de ptimización, las soluciones corresponden a estados del sistema físico. El costo

de la solución corresponde a la energía del estado. Se introduce un parámetro de onde a la temperatura. Si se baja la temperatura lo

o se puede alcanzar el equilibrio térmico en cada nivel de mperatura. Esto se hace mediante la generación de varias transiciones en cada

(A Envtee Ecssaco

control que correspuficientemente lents

tetemperatura.

xii

Antecedentes En el problema del despacho económico, las restricciones impuestas por los

étodos matemáticos clásicos en las cmg

urvas de costo de las unidades en

cos dcostos de potede l f Los édifemodelade aen suncion

s casos donde estas últimas tienen aplicación, para revisar la

n y puntos de válvula.

nsidera puntos de válvula y la solución del AG es superior

•

eradoras han impedido la utilización de mejores modelos de las funciones de to e las unidades térmicas que permitan reducciones adicionales en los

de generación. Si se considera el costo total de generación de un sistema ncia real, resulta evidente que evitar cualquier restricción en el modelado

as unciones de costo se traducirá en un ahorro significativo.

todos heurísticos son utilizados como herramientam s de optimización que, a rencia de los métodos matemáticos clásicos, no imponen restricciones en el

do de los elementos implícitos en el problema, ya que tienen la habilidad ptarse a las no-linealidadeda s y discontinuidades comúnmente encontradas

lo sistemas físicos, además muestran buenas características de amiento en problemas con espacio de solución multimodal. f

El AG ha mostrado buenos resultados en problemas de DE donde los métodos clásicos de solución no tienen aplicación. Un problema típico es el DE con punto de válvula, en donde se utiliza una mejor aproximación de las curvas de entrada-salida de las unidades térmicas al considerar curvas no convexas. Los resultados de los métodos heurísticos se han comparado con los de las técnicas de solución clásicas en loproximidad de sus soluciones. F. Li [5], por ejemplo, prueba la robustez del AG sobre cuatro problemas de DE y compara su desempeño contra tres técnicas clásicas de solución, que son la tabla de mérito, la lambda iterativa y la técnica del gradiente. El sistema es de sólo tres unidades y aumenta la complejidad de cada problema con la consideración de pérdidas de transmisió

• Para el problema más sencillo, que es el caso sin pérdidas y funciones convexas de segundo grado, todas las técnicas ofrecen solución y la del AG es superior en 0.006% respecto a la del método exacto de la lambda iterativa.

• Para el segundo caso, donde se consideran pérdidas de transmisión, el costo de la solución del AG es superior en 0.6%.

• El tercer caso coen 3.7% sobre el método de la tabla de mérito (los otros métodos no tienen aplicación en este caso). Finalmente, para el caso más complejo donde se consideran puntos de válvula y pérdidas de transmisión, el AG es el único que ofrece solución.

xiii

El A ttipo no tales [11]. Las emisiones de dióx o funciones de seg d r. Estas rest cpenaliz El AG es tdeterminó que el tamaño óptimo para una cen función exponenc n, aunque posteriormente sugirió que un valor

gran escala (17 unidades), que era un

• • mejor individuo de cada generación)

o orden.

G ambién ha sido utilizado para problemas de despacho con restricciones de lineal, por ejemplo, restricciones ambien

id de azufre y óxidos de nitrógeno son representadas porun o grado en función de la potencia de salida de cada generadoric iones son incorporadas a la función objetivo mediante un factor de

ación.

tiene muchos parámetros de control que deben ser ajustados, uno de ellos el amaño de la población. David Goldberg, un estudiante de John Holland,

odificación binaria de longitud n estaba ial de

adecuado era de 100 individuos. Otros resultados empíricos sugieren poblaciones de 30 individuos [9]. Olachea A. [7] analiza la aplicación del AG al PDE con diferentes restricciones (sin pérdidas, con punto de válvula y con restricción de flujo máximo en líneas) en un istema de tres máquinas y para uno des

sistema aislado del Sistema Eléctrico Nacional. Olachea reporta una gran variedad de pruebas para diferentes parámetros del AG, coincidiendo sus ajustes con algunos ya ampliamente recomendados en la literatura. Estos son algunos resultados que obtuvo:

• utilizar poblaciones iniciales lo más grande posible para obtener una rápida convergencia debido a que se explota con mayor eficacia el recurso de búsqueda en paralelo. Obtiene sus mejores resultados con poblaciones de 100 individuos

• menores desviaciones de potencia utilizando puntos de cruza uniforme, respecto al punto de cruza en un solo punto probabilidades de cruza alta (0.8) y de mutación bajas (0.1) uso de elitismo (conservar al

• las funciones de evaluación estructuradas en forma de sumatorias facilitan el proceso de sintonización del algoritmo

• conveniencia del uso de factores de prioridad y penalización en la función de evaluación cuando se incluyen restricciones adicionales

• utilizar una función de evaluación de tipo exponencial para el caso del DE con punto de válvula.

También compara los resultados codificando por una parte, las potencias de los generadores y por otra, valores de costo incremental λ, siguiendo el criterio de que el óptimo se logra cuando todas las unidades operan a un mismo valor de λ. En ambos casos logra convergencia con un número similar de iteraciones y desviaciones de costo del mism

xiv

El desempeño de las heurísticas también ha sido mejorado mediante la hibridación para tratar de compensar algunas deficiencias. Por ejemplo, se sabe que los AG’s son imperfectos en cuanto a la exactitud de la solución encontrada, y las mejoras siguen en general dos líneas:

• La primera es mejorar los procedimientos genéticos: la representación o codificación de los individuos, el tamaño y calidad de la población inicial, diferentes funciones de evaluación, operadores genéticos avanzados y

rgencia y viceversa. No es osible que ambas cosas se mejoren al mismo tiempo. El AGH propuesto consta

del 0.36% respecto al AG para empos iguales de ejecución; y una mejora en tiempo de ejecución del 52.9% para

costos iguales de generación. Ongsakul W. [8] utilizó métodos basados en tablas de mérito para el despacho de unidades tipo ciclo combinado, para resolver una limitación del programa de despacho económico en tiempo real de la compañía Electricity Generating Authority of Thailand. Esta aplicación sólo consideraba funciones de costo incremental monótonas crecientes y los modelos que se querían utilizar eran funciones lineales decrecientes y de tipo escalón (correspondientes a curvas de entrada-salida de segundo y primer orden, respectivamente). El autor utilizó los costos incrementales de las unidades generando a su máxima potencia como criterio para despachar los ciclos combinados y obtuvo mejores resultados que los obtenidos con el método de Newton. Las desviaciones promedio fueron del 0.43 % respecto de la solución óptima. El caso de estudio referido estaba formado por 4 ciclos combinados con curvas de costos incrementales lineales decrecientes y 1 ciclo combinado con curva de costo incremental de tipo escalera decreciente. Sin embargo, el autor no comenta nada acerca de las variaciones derivadas de utilizar modelos aproximados (curvas de costo incremental lineales y de escalera decrecientes).

auto-adaptables, y selección óptima de los parámetros del algoritmo. • La segunda línea va en el sentido de usar híbridos, combinando el AG con

técnicas de búsqueda local para acelerar el proceso y mejorar la calidad de la solución.

Como ejemplo de esta segunda línea de mejora, F. Li et al [6] proponen un algoritmo genético híbrido (AGH) usando el AG combinado con la técnica del gradiente para el PDE. Comentan que el AG balancea la exploración y explotación del espacio de búsqueda, lo que significa que un incremento en la exactitud de la solución sólo se logra sacrificando la rapidez de convepde un AG encargado de dirigir la búsqueda hacia regiones prometedoras, y de la técnica del gradiente de primer orden para hacer el trabajo fino. La efectividad de su algoritmo fue probada en un sistema real de 25 unidades generadoras. En sus resultados, el AGH presenta una mejora en costoti

xv

El AG es el método heurístico más popular aplicado al PDE. Los últimos trabajos

más a resolver el problema de asignación de unidades, en donde l PDE implícito se resuelve con las técnicas clásicas de solución que consideran

se han enfocado efunciones de costo convexas de segundo grado.

xvi

Justificación

lusiva a la Comisión Federal de Electricidad (CFE). A la fecha, operan 21 IE’s en distintas zonas del país y utilizan la tecnología de ciclo combinado. Los

ene una zona muerta de 260 a 320 MW, que es un rango de peración donde no se desea operar debido a las dificultades técnicas y altos

costos que implica desplazarse en ese rango de operación, pues se debe arrancar o parar una unidad turbogás. .

Con la reciente modificación en México a la Ley del Servicio Público de Energía Eléctrica1, se ha permitido la generación de energía eléctrica por particulares. Uno de los permisos es el de producción independiente de energía eléctrica, que autoriza a los Productores Independientes de Energía (PIE) la generación para venta excPPIE’s actualizan periódicamente al CENACE el régimen térmico para su participación en el despacho de generación, y es referido a los consumos específicos en kcal/kWh de al menos tres puntos de operación. En algunos permisionarios, como es el caso del PIE CC Mexicali, los primeros dos puntos dan origen a una curva de entrada-salida no convexa, (ver figura g). Adicionalmente, este permisionario tio

1,780

1,800

1,820

1,840

1,860

1,880

25 50 100

% Capacidad

kcal

/ kW

h

zona muerta

Figura g) Curva de consumo específico basada en tres puntos del PIE CC Mexicali.

Las funciones de costo de las plantas térmicas de CFE, incluyendo los ciclos combinados, son representadas con curvas convexas de segundo grado, como lo exige la aplicación que se utiliza para ejecutar el Despacho de Económico de Generación. Los modelos con regiones no convexas que proporcionan algunos PIE’s, son ajustados a una curva convexa de segundo orden y cuando los

1 Diario Oficial de la Federación, 27 diciembre de 1993

xvii

resultados del despacho indican una operación del PIE en una zona muerta, éstos trasladan su punto de operación al límite más cercano de la zona muerta.

s necesario contar con una herramienta que permita la evaluación de las regiones no convexas y las zonas muertas que se presentan en las unidades

es posible hacerlo con los métodos clásicos de solución. Se de DE sin pérdidas de transmisión con la única finalidad de

En este trabajo de tesis, se muestra la aplicación de heurísticas aplicadas a la E sin pérdidas, considerando las funciones de costo no

térmicas para evaluar el costo de las

E

térmicas, ya que noutiliza el problema poder comparar los resultados de las heurísticas con la solución de un método clásico.

solución del problema de Donvexas y las zonas muertas de unidades c

consideraciones que se realizan por las restricciones que impone el método clásico de solución.

xviii

Objetivos

Objetivo General: Aplicar métodos heurísticos al problema de despacho económico sin pérdidas, considerando las funciones de costo no convexas y zonas muertas de unidades térmicas.

Objetivos particulares: - Resolver el problema planteado con los métodos heurísticos siguientes:

Algoritmo Genético, Algoritmo Genético Hibrido, Algoritmo de Recocido Simulado y GRASP.

- Determinar los mejores ajustes de los parámetros de cada heurística. - Comparar el desempeño de los cuatro métodos heurísticos utilizados - Evaluar el efecto en los costos de operación del despacho económico al

considerar las zonas muertas y las curvas no convexas de las unidades térmicas.

xix

Contenido de la tesis

n el capítulo primero se describen los métodos heurísticos que se aplican al lican de forma general los algoritmos utilizados para resolver el

roblema: el AG, AGH, ARS y GRASP. Se describen también la técnica de ar soluciones iniciales factibles y la

reación de vecindades para la búsqueda local utilizadas en los algoritmos. Se en la literatura de los parámetros de

ada heurística.

blema de DE, su formulación matemática, y la técnica de solución clásica. Se describen también otros roblemas de DE según el tipo de restricción. Al final del capítulo se muestran los

los que se probarán los métodos heurísticos.

n los capítulos 3, 4 y 5 se presenta la implementación de los métodos heurísticos

lamente aquellos parámetros que son articulares del PDE. Los ajustes de estos parámetros se hacen sobre problemas

rísticas utilizadas.

gundo grado mediante la técnica del grangiano. El segundo apéndice contiene el código fuente de los programas

elaborados para cada método heurístico.

EPDE. Se exppsatisfacción de restricciones (SR) para genercmencionan los valores típicos recomendados c En el capítulo segundo se describe el pro

pcasos de estudio con Eal problema de DE. Los valores típicos de los parámetros generales de cada método heurístico son utilizados, como son las probabilidades de cruza y de mutación para el AG, o el coeficiente de enfriamiento alfa del ARS y el coeficiente de miopía alfa del GRASP. Se ajustan soppara los cuáles se puede obtener la solución analítica, para utilizarlos posteriormente en los problemas con funciones de costo no convexas y zonas muertas. En el capítulo 6 se muestran los resultados comparativos de cada heurística, referidos a tiempos de ejecución, mejores soluciones obtenidas, variabilidad de resultados y porcentajes de error respecto a la mejor solución encontrada. De acuerdo con estos resultados, se comentan las conclusiones sobre la aplicación de las heu Finalmente se muestran las conclusiones de este trabajo y dos apéndices. El primer apéndice muestra paso a paso obtención de la solución al caso de estudio 1 con funciones de costo convexas de sela

xx

Capítulo 1. Despacho Económico

n general, el problema tiene que ser dividido para el análisis de restricciones que dan origen a diferentes problemas de DE. Las diferentes soluciones son iteradas hasta que no se viola ninguna restricción.

a de DE sin pérdidas, que es ampliamente

ente fácil de resolver, cuando se hacen consideraciones dicionales como utilizar funciones de costo convexas de segundo orden, que lo onvierte en un problema de programación lineal. La única dificultad mayor,

viéndolo de esta forma, sería con el número de unidades del sistema a tratar, pero ún así, con los recursos de cómputo y programas de software actuales, no

representan más dificultades que el de tener que esperar unos minutos para su solución.

1.1 Introducción

uede hacer tan sencillo o complicado como se quiera. Pero El problema de DE se pe

En este capítulo se describe el problemutilizado para mostrar la naturaleza y un buen entendimiento del problema. Este problema es relativamac

a

En el capítulo se describen brevemente algunos otros problemas de DE con el único fin de mostrar las restricciones más estudiadas y al final se presentan los sistemas utilizados como casos de estudio.

1.2 Despacho Económico sin pérdidas El problema más sencillo de despacho es que se plantea para un sólo intervalo de empo donde la demanda es constante y generalmente se asume que las curvas ti

de entrada-salida son suaves y convexas, las cuales pueden ser representadas por funciones lineales o cuadráticas. Un caso simple es el DE sin pérdidas de

1

transmisión, en donde las únicas restricciones son el balance de potencia (BP) y los límites de potencia de cada generador. La formulación [1] es la siguiente :

inimizar : Pi)

sujeto a:

Pmini ≤ Pi ≤ Pmaxionde:

mini :Pmaxi Se uti etivo las restricFunción la

uego, la condición necesaria para el mínimo es cuando el gradiente de la función

∑=

n

iiF

1(m

∑=

=n

ii demandaP

1

Dn: número de unidades generadoras Fi : Función de costo del generador i PP

i : Potencia del generador i Potencia mínima que puede suministrar el generador i

rador i : Potencia máxima que puede suministrar el gene

lizan multiplicadores de Lagrange para incorporar a la función objciones de igualdad (balance generación-demanda).

grangeana:

Llagrangeana es cero:

nidPdF

PL

i

i

i

,...,1;0 ==+=∂∂ λ

;01

=−=∂∂ ∑

=

demandaPL n

iiλ

Al término λ = -

i

i

dPdF , se le conoce como costo incremental del generador i, y

do a un incremento en la potencia generada. Se observa de las condiciones de optimalidad, que para lograr el

a un mismo costo incremental λ.

⎟⎜ −+= ∑∑ demandaPPF )() λλ⎠⎝ == i

ii

ii11

⎞⎛ nn

PL ,(

representa el incremento de costo debi

óptimo, todas las unidades deben operar

2

El problema consiste en la solución de un sistema de ecuaciones simultáneas, el cual se puede resolver por el método simplex o con el método de Newton, según ea el grado de las funciones de costo de los generadores.

alores de potencia que

iolan los límites de los generadores, es necesario aplicar algún criterio para

s

Si al resolver el sistema de ecuaciones se encuentran vvdecidir cuál generador se fija en su límite máximo, o cuál en su límite mínimo. Para esto se aplican las condiciones de optimalidad de Kuhn-Tucker:

ii PPiPparadPidFi maxmin <<= λ

iPPiparadFi max=≤ λ dPi

iPPiparadPidFi min=≥ λ

donde es el costo incremental del sistema, obtenido de la solución del sistema de ecuaciones. Se sigue entonces el siguiente procedimiento:

1.- Fijar a los generadores fuera de límites en su límite alcanzado. 2.- Solucionar nuevamente el sistema de ecuaciones.

n integrarse en un nuevo conjunto de generadores para realizar un nuevo despacho.

6.- Ejecutar un nuevo despacho (solucionar nuevamente el sistema de ecuaciones).

7.- Verificar límites. Si todos los generadores cumplen con los límites, entonces termina el problema; de lo contrario, regresar al paso 1.

Otra forma de considerar los límites de generación es agregando nuevos multiplicadores de Lagrange a la función objetivo, dos por cada unidad. La función Lagrangeana es ahora:

∑ ∑∑∑= ===

−+−+⎟⎠

⎞⎜⎝

⎛−+=

n

i

n

iiiii

n

ii

n

iii PPiPPidemandaPPFPL

1 1

minminmaxmax

11)()()(),( µµλλ

3.- Calcular los costos incrementales λi para los generadores del paso 1. 4.- Verificar las condiciones de optimalidad 5.- Para los generadores que cumplen con las condiciones de optimalidad, fijar sus

generaciones en el límite; mientras que los que no cumplen debe

3

nidPP ii∂

dFLii

i ,...,1;0minmax ==+++= µµλ ∂

;01

=−=∂ ∑∂

=

n

especto a la exactitud deseada y relevancia del problema considerado se han

es térmicas randes, los niveles de potencia se van escalando a través de la apertura de

de energía entre las nidades asignadas, pero tomando en cuenta la demanda actual y futura

nergía entre las unidades asignadas minimizando costos por uso de

demandaPLi

iλ

Como se observa, la cantidad de términos es considerable al incorporar los límites perativos de las unidades, lo cuál requiere de más recursos de cómputo. o

1.3 Otros problemas de Despacho Económico Rderivado otros problemas de DE, como por ejemplo: 1.- DE con punto de válvula.- el cual considera la no linealidad de las funciones de costo, con el fin de tener mayores ahorros en el costo. En unidadgválvulas, en forma escalonada, lo cual origina que la función de costo pueda ser no convexa y con discontinuidades. 2.- DE dinámico.- su objetivo es satisfacer la demanda upronosticada, minimizando costos dentro de un periodo corto de tiempo, y tomando en consideración restricciones como rampas de carga y reserva rodante. 3.- DE con consideraciones Ambientales.- su objetivo es satisfacer la demanda de ecombustibles y las emisiones de contaminantes que generan las unidades de generación. 4.- Flujos óptimos.- el objetivo es minimizar el costo sujeto a restricciones de seguridad, y las potencias activa y reactiva de cada generador se sujetan a los niveles seguros de voltaje y ángulos de fase en los buses del sistema.

4

1.4 Técnicas clásicas de solución Convencionalmente, se aplican diferentes técnicas para atacar los diferentes tipos de problemas del despacho. Sin embargo, cualquier cambio en la formulación del problema, puede requerir una alteración parcial o el reemplazo total de la técnica utilizada. El tiempo y esfuerzo que se requiere para adecuar la técnica son inadecuados para muchas aplicaciones prácticas.

lgunas de las técnicas utilizadas para solucionar los problemas de DE son la

e gradiente. Todas ellas utilizan reglas deterministas transitorias para btener estrategias de solución.

alor de λ inicial y se termina hasta que s potencias de las unidades se ajustan a la demanda. Este método requiere

atemática útil en la toma de una erie de decisiones interrelacionadas. Proporciona un procedimiento sistemático

para dete práctica el espac de búsqued e tan grande q e sim leme letarla. 4.- Técnica del gradiente. Es un método iterativo muy eficiente cuando se parte de una buena solución inicial, ya que busca c En contraste a las técn nale os oritm ené xhibido robustez d trar tim glob en l de los problem e DE d e comple dad. a a estos algoritmos es que son computacionalmentla búsqueda de óptimos globales del problema de DE, estos algoritmos permiten utilizar de igual maner line eales, de ahí que se

Atabla de mérito, el método de la lambda iterativa, la programación dinámica y el método do 1.- Tabla de mérito. La idea es que la unidad más eficiente opere a su máxima capacidad, luego la segunda más eficiente, y así sucesivamente hasta satisfacer la demanda de energía. Este método es muy simple y eficiente, pero no permite considerar un gran número de restricciones y da resultados costosos. 2.- Método de la lambda iterativa. Está basado en el principio de costos incrementales iguales. Se empieza por un vlaestricta convexidad y continuidad de las funciones objetivo. 3.- Programación Dinámica. Es una técnica ms

rminar la combinación óptima de decisiones. Sin embargo, en laio a s u p nte no es posible comp

óptimos lo ales.

icas convencio s, l Alg os G ticos han e en la habili ad para encon óp os ales la so ución as d e diferent ji L mayor tracción de

e simples, pero bastante poderosos en . En el caa funcion

soes de costo al o no lin

an una buena opción para resolver el DEPV.

5

1.5 Casos de Estudio. Se utilizaron tres casos de estudio para evaluar el desempeño de los métodos h urís y se nalizstá formado por 3 unidades y se utilizó para analizar funciones de costo no onvexas que consideran los puntos de válvula de las unidades. El caso 2 consta e 36 unidades y se utilizó para probar el desempeño de los métodos heurísticas

con un problema de mayor dimensión. 1.5.1 Caso de estudio 1, 7 Us (función de costo no convexa de un PIE y zona muerta). Estas unidades fueron tomadas del sistema aislado de Baja California. En este sistema la unidad 7 corresponde a un PIE y se modela de dos formas. La primera corresponde al modelo actual que se utiliza en CENACE y que es un ajuste a una función de costo de segundo orden a partir de los tres puntos del régimen térmico que proporciona el PIE (ver figura 1.2). El segundo modelo utiliza una función de costo no convex convexa para l rango complementario (245 a 489 MW). Además, se considera la zona muerta onde no opera el PIE (de 160 a 320 MW).

e ticos aplicados al DE. El primer caso está formado por 7 unidades a la función de costo no convexa del CC Mexicali y la zona muerta. El caso 3 a

ecd

a para el primer rango (122 a 245 MW) y una curvaed La tabla 1.1 muestra las potencias máximas y mínimas de cada unidad, el tipo de tecnología y los coeficientes abc de las curvas de entrada-salida que, como ya se ha explicado, son de segundo orden convexas.

Tabla 1.1 Límites de potencia y coeficientes abc de la unidades del caso 1.

Coeficientes de la function de

costo F

Pmin Pmax a b c

central tipo [MW] [MW] [$/MWh2] [$/MWh] [$]

Presidente Juárez U1 vapor 40 160 1.2800 368.0 22770

Presidente Juárez U2 ciclo combinado 248 0.5635 158.5 33830 62

Presidente 5 33830 Juárez U3 ciclo combinado 62 248 0.5635 158.

Ciprés U4 turbogás 7 27 24.9200 1154.0 13330

Mexicali U5 turbogás 7 26 19.4500 1204.0 16680

Tijuana U6 turbogás 8 30 21.1600 1190.0 16660

CC Mexicali 1) U7 ciclo combinado 122 489 0.0291 467.7 6957

Total 308 1,228 1) Coeficientes abc de la curva ajustada a los tres puntos del régimen térmico

6

La figura 1.1 muestra las curvas de entrada-salida o funciones de costo F de las 7 unidades. La curva F7a es la función ajustada de segundo orden convexa del PIE CC Mexicali. La curva F7b es la función de costo no convexa.

0

50,000

100,000

150,000

200,000

250,000

0 50 100 150 200 250 300 350 400 450 500

MW

$/h

F1 F2 F3 F4 F5 F6 F7 a F7 b

Figura 1.1 Funciones de costo o curvas de entrada-salida de las unidades del caso 1.

Curva de regimen termico (Heat Rate)

MW [$/MWh]

122 494.5

245 500.1

CC Mexicali505

489 480.9

47550 75 100

% Capacidad

480

485

500

$ /

490 MW

495

h

Figura 1.2 Régimen térmico en $/MWh del CC Mexicali (U7).

7

La función de costo incremental es la derivada de la función de costo y cada punto presenta el costo de generar el siguiente megawatt. El criterio de optimalidad del

aratas) de las demás unidades. La figura 1.3 muestra los CI’s de las 7 nidades. Las unidades 4, 5 y 6 no son coordinables con las demás unidades.

rePDE establece el óptimo cuando todas las unidades operan a un mismo costo incremental. Algunas unidades no son coordinables porque su rango de potencia tiene costos incrementales que están por encima (son más caras) o por debajo (son más bu

0

500

1,000

1,500

2,000

2,500

0 100 200 3 500

$/M

Wh

00 400

MW

CI 1 CI 2 CI 3 CI 4 CI 5 CI 6 CI 7a

ra 1.3 stos i me un el c En la figura 1.4 ob la d nc los c incr s de los dos modelos utilizados para n 7. CI 7 m la figura 1.3, sólo que la pen te s má an esca zada. La zona muerta de la unidad 7 es 0 a MW

Figu Co ncre ntales de las idades d aso 1.

se serva ifere ia entre ostos ementale la u idad La curva a es la isma de

dien e ve s gr de por la la utilide 16 320 .

8

470

475

480

485$/M

W

490

495

500

505

h

0 100 200 300 400 500

MW

CI 7a

CI 7b

zona muerta

emanda: 870 MW

Solución analítica con funciones de o o c vexas y sin zona muerta. La solución óptima se muestra en la tabla 1 Las ion osto de todas las unidades son curvas e se o g on as, zon ta para la unidad 7.

Tabla 1.2 Solución óptima d cio de co e rado convexas. Solución an a

Figura 1.4 Costos incrementales de los dos modelos utilizados para la unidad 7. D

segund grad on

.2. func es de c d gund rado c vex sin a muer

el caso 1 con fun nes sto d segundo galític

P6 P7 P1 P2 P3 P4 P5 demanda [MW]: 0.0 .9 .0 8.0 306.187 45 248.0 248 7.0 7.0costo óptimo [$]: 8 8 107,796 22,629 7,534 152,845487,01 42,35 107,796 26,061 2

La solución analítica se obtuvo con la técnica del lagrangiano. El desarrollo completo se explica el A O

en NEX 1.

9

1.5.2 Caso de estudio 2, 36 Us (problema de mayor tamaño). Estas unidades fueron tomadas del Sistema Interconectado Nacional. Se omiten los nombres por brevedad simplemente. La tabla 1.3 contiene los datos de las 36 nidades. Todas son unidades de vapor con funciones de costo de segundo grado u

convexas.

Tabla 1.3 Datos de las 36 unidades del caso 2. Pmin Pmax a b c [MW] [MW] [$/MW2h] [$/MWh] [$/h]

U1 220 300 0.037132 201.24 3550.7 U2 220 300 0.041288 199.26 3948.2 U3 260 350 0.026299 224.54 3423.0 U4 3593.7 260 350 0.027610 226.70U5 225 350 0.105430 188.96 13722.0 U6 225 350 0.106470 196.73 13857.0 U7 25 01 202.0 13270.0 2 350 0.1 950 9U8 22 3 9689 25.86 070.4 5 50 0.06 2 9U9 225 350 84 5.0 0.0794 219.15 1034U10 22 3 7196 21.33 048.0 5 50 0.07 2 10U11 140 2 2280 48.18 483.9 27 0.16 3 9U12 180 240 0.504030 186.40 33471.0 U13 122 184 0.676600 233.93 25139.0 U14 150 225 0.248010 381.11 13352.0 U15 225 350 0.156080 408.54 20314.0 U16 225 350 0.155620 411.79 20254.0 U17 55 70 1.438000 127.75 23277.0 U18 90 122 0.427510 347.77 13513.0 U19 90 129 0.335730 367.52 13534.0 U20 50 62 1.608000 131.94 22128.0 U21 64 138 0.880550 115.52 44688.0 U22 50 63 2.061700 45.90 27971.0 U23 249 498 0.272490 291.24 44357.0 U24 518 1036 0.118610 261.78 135260.0 U25 125 250 0.341910 341.77 22705.0 U26 291.3 500 0.000096 522.55 25.7 U27 470 580 0.032259 485.21 1.0 1153U28 124 247.5 0.540800 226.62 98.0 351U29 600 983 0.019976 464.50 20509.0 U30 162 489 0.025944 480.16 6591.4 U31 160 258 0.543030 173.30 38405.0 U32 280 449 0.025059 446.95 2881.2 U33 242 484 0.264990 203.06 65955.0 U34 350 495 0.007721 465.96 2010.1 U35 248 495 0.005007 476.31 1303.3 U36 120 252.4 0.384100 283.63 25998.0

10

En la fig. 1.5 se muestran las curvas de costo incremental de las 36 unidades.

CI1 CI2CI21200

CI3CI4

CI5CI6

CI7CI8

CI9CI10

CI11 CI12CI13

CI14

CI15CI16

CI17

CI18

CI19

CI20

CI22

CI23

CI24

CI25CI26 CI27

CI28

CI29CI30

CI31

CI32

CI33

CI34CI35

CI36

250

300

350

400

450

500

550

600

50 150 250 350 450 550 650 750 850 950

MW

$/M

Wh

CI1 CI2 CI3 CI4 CI5 CI6 CI7 CI8 CI9 CI10

CI11 CI12 CI13 CI14 CI15 CI16 CI17 CI18 CI19 CI20

CI21 CI22 CI23 CI24 CI25 CI26 CI27 CI28 CI29 CI30

CI31 CI32 CI33 CI34 CI35 CI36

cel 2003 de Microsoft.

Figura 1.5 Costos incrementales de las unidades del caso 2. Demanda: 10 500 MW Zona muerta: no Solución analítica para funciones de segundo grado convexas y sin zona muerta. Esta solución se encontró usando la función “solver” de Ex

11

Tabla 1.4 Solución óptima del caso 2 con funciones de costo de segundo grado convexas. Unidad Potencia

[MW] Costo

[$] Unidad Potencia [MW]

Costo[$]

1 300 67,265 19 129 66,531 2 300 67,442 20 62 36,489 3 350 85,234 21 138 77,399 4 350 86,321 22 63 39,046 5 350 92,773 23 332 170,993 6 350 95,755 24 886 460,539 7 350 96,490 25 191 100,270 8 350 96,658 26 291 152,253 9 350 96,784 27 470 246,706 10 350 96,970 28 227 114,482 11 227 96,883 29 600 306,400 12 240 107,239 30 162 85,058 13 176 87,265 31 258 119,263 14 183 91,570 32 449 208,614 15 225 120,137 33 484 226,312 16 225 120,785 34 396 187,822 17 70 39,266 35 248 119,736 18 122 62,304 36 245 118,696

demanda 10,500 MW costo 4,443,749 $

la).

= aP + bP + c + e sen(f * (Pmin-P))

Tabla 1.5 Datos de las 3 unidades del caso 3.

a b c e f

Funciones de costo no convexas, zonas muertas y punto de válvula. Para observar el desempeño con diferentes tipos de funciones de costo y zona muerta. Incluye 33 unidades del caso 2, una de las cuáles se modela con una función de costo no convexa y zona muerta; 3 unidades del caso 3, que modelan los puntos de válvula. 1.5.3 Caso de estudio 3, 3 Us (evaluación de puntos de válvu Este caso se tomó de Walters [13] y consta de 3 unidades con funciones de costo que modelan los puntos de válvula. La tabla 2.5 contiene los datos de las 3 unidades. La función de costo de cada unidad térmica es de la forma:

2F

Pmin Pmax [$/h] [MW] [MW] [$/MW2h] [$/MWh] [$/h]

U1 100 700 0.001570 7.92 571.0 300 0.0315U2 100 400 0.001940 7.85 310.0 200 0.042U3 50 200 0.004820 7.97 78.0 150 0.073

12

En la figura 1.6 se grafican las funciones de costo y las curvas de costo incremental.

0

1,000

2,000

3,000

50 150 250 350 450 550 650

MW

4,000

5,000

6,000

$/h

7,000

8,000

U1

U2

U3

24

4

8

12

50 100 150 200 250 300 350 400 450 500 550 600 650 700

$/

16

20

MW

MW

h U1U2U3

a) b)

Figura 1.6 Funciones de a) costo y b) costos incrementales de las unidades del caso 3. Demanda: 850 MW La tabla 1.6 presenta la mejor solución encontrada por Walters y según reporta, coincide con la solución óptima obtenida por el método de programación dinámica.

Tabla 1.6 Solución óptima del caso 3. P1

[MW] P2

[MW] P3

[MW] demanda

[MW] Costo

[$] 300.0 400.0 150.0 850.0 8,237.6

13

Capítulo 2. Métodos Heurísticos

tandard Dictionary of lectrical and Electronics Terms), una heurística se refiere a aquellos métodos o

as en problemas en los que la complejidad de la olución algorítmica disponible es función exponencial de algún parámetro;

r de éste crece, el problema se vuelve rápidamente inabordable. as técnicas heurísticas no aseguran soluciones óptimas sino solamente

n este capítulo se hace una breve descripción de los métodos heurísticos que se ron para el PDE (AG, AGH, ARS, GRASP) , y de métodos heurísticos

Un AG puede considerarse un algoritmo de búsqueda probabilística inteligente que puede aplicarse a varios problemas de optimización combinatoria. Las bases

2.1 Introducción El término heurística proviene del griego heuriskein que significa encontrar o descubrir. De acuerdo con ANSI/IEEE Std 100-1984 (SEalgoritmos exploratorios para la resolución de problemas en los que las soluciones se descubren por la evaluación del progreso logrado en la búsqueda de un resultado final. Se trata de métodos en los que, aunque la exploración se realiza de manera algorítmica, el progreso se logra por la evaluación puramente empírica del resultado. Se gana eficacia, sobre todo en términos de eficiencia computacional, a costa de la precisión. Las técnicas heurísticas son usadscuando el valoLsoluciones válidas, aproximadas, y frecuentemente no es posible justificar en términos estrictamente lógicos la validez del resultado. Eimplementaque sirvieron de soporte para la implementación del AGH, como son la búsqueda en vecindades y un algoritmo de satisfacción de restricciones.

2.2 Algoritmo Genético

14

teóricas de los algoritmos genéticos fueron deaños setenta; la idea está basada en el proceso evolutivo de

sarrolladas por John Holland en los los organismos

iológicos en la naturaleza, donde las poblaciones evolucionan de acuerdo a los

de búsqueda sin necesidad de imponer ic

individuos menos aptos (enfoque de estado uniforme). Este iclo de evaluación-selección-reproducción se repite hasta encontrar una solución

esumir en la siguiente tabla:

ritmo Genético simple.

damente las soluciones del Problema n individuos o soluciones del Problema

los individuos de la población haya satisfecho el criterio de parada)

res para obtener dos hijos

los padres elegidos, por sus hijos on probabilidad Pm algunas características de cada individuo

e los individuos de la población eccionar individuos que sobreviven en la siguiente generación

nddo

bprincipios de la selección natural en que sobreviven y se reproducen los más aptos. Los algoritmos genéticos intentan imitar matemáticamente algunos procesos adaptativos del fenómeno biológico, considerando una población inicial de individuos y aplicando operadores genéticos en cada reproducción. Con dichos operadores se define un mecanismo restr ciones matemáticas adicionales. En términos de optimización, cada individuo de una población es codificado en una cadena o cromosoma que representa una posible solución de un problema dado. La aptitud de un individuo es evaluado con respecto a una función objetivo propuesta. A los individuos mejor adaptados, o mejores soluciones, se les permite reproducirse intercambiando algunos elementos de su información genética en un proceso de cruce con otros individuos también muy aptos, lo cuál produce nuevas soluciones que comparten algunas características tomadas de sus padres. Frecuentemente se aplica la mutación después del cruce, alterando algunos genes en las cadenas con el fin dar mayor variedad en las soluciones. Los descendientes pueden reemplazar a la población total (enfoque generacional), o reemplazar a loscsatisfactoria. Un AG simple se puede r Tabla 2.1 Algoinicio Representar adecua Generar población inicial co Definir una función de aptitud de do while (NO se Elegir pares de individuos como pad Cruzar con probabilidad Pc a los padres elegidos Reemplazar Mutar c Evaluar la aptitud d Sel efin

15

Los algoritmos genéticos manejan simultáneamente un conjunto de soluciindividuos) en cada etapa (la generación). Las características de cada solución

ones

eben ser codificadas adecuadamente (el cromosoma) de forma que al combinar

ión, resultados empíricos de varios autores sugieren ental de J.T.

string ue representa a un individuo. A. Olachea [7] trabajó con poblaciones de 40 y 100

valor para los problemas de DE que estudió. Para tros generales del AG se puede consultar [3].

a local

a bús en el método de optimización más antiguo, que es el n simple y natural que sorprende como puede

tados para problemas difíciles de optimización mo general se puede describir como sigue: dada una

problema de optimización, dónde F es un conjunto de c es la función de costo, se escoge una vecindad N: F 2F

a un punto t ∈ F de mejora a través de la subrutina:

ejorar""

)()()(lg)(

eda local.

(ddos soluciones para producir una nueva solución, parte de estas características (los genes) se transmitan a ésta. Los parámetros del AG han sido ampliamente estudiados y se recomiendan valores altos para la probabilidad de cruza Pc, siendo un valor típico 0.8. La probabilidad de mutación Pm se recomienda sea de valor muy bajo y un valor típico es de 0.001. En otros trabajos se reportan algoritmos genéticos modificados o refinados con operadores especiales de cruza [2] y probabilidades de cruza y mutación que se van adaptando al nivel de progreso en la solución. Respecto al amaño de la poblactpoblaciones tan pequeñas como 30 individuos. Un trabajo experim

lander sugiere valores entre n y 2n [9], siendo n el tamaño de la cadena o Aqindividuos y sugirió este últimoun mayor análisis de los paráme

2.3 Búsqued L queda local se basade prueba y error. La idea es taofrecer tan buenos resulc natoria. El algoritombiinstancia (F,c) de unsoluciones factibles y , donde se busc

⎩⎨⎧ <∈

=nosinoexistestalsitcsccontNsúna

tm

Tabla 2.2 Algoritmo de búsqu

rocedure búsqueda local pbegin t:= un punto de inicio en F; while mejorar(t) ≠ ‘no’ do t:= mejorar(t); return t end

16

El seudocódigo se muestra en la tabla 2.2, se inicia a partir de una solución inicial factible t∈ F y usa la subrutina mejorar para buscar una mejor solución en su vecindad. Mientras ésta exista, se adopta como la mejor solución y se repite la búsqueda en la vecindad de la nueva solución. El algoritmo termina cuando se haya encontrado el óptimo local [9]. Para aplicarlo a un problema en particular se deben hacer algunas selecciones.

ner una solución inicial factible. Es recomendable, chas ocasiones, correr el algoritmo a partir de distintos puntos de inicio y

ltado. En tales casos, se debe decidir cuántas les utilizar y cómo deben estar distribuidas.

uego ena vecindad y tener un método de búsqueda dentro lar. Esta selección se tiene que hacer

ue existe poco respaldo teórico para btene eneral. Respecto al tamaño de la vecindad, se debe evaluar la

año que podría proporcionar un mejor l, pero que requeriría de más tiempo de búsqueda. La otra alternativa

una vecindad pequeña, pero con la posibilidad de obtener más oluciones en un tiempo similar.

ecindades

Primero que nada, se debe obteen muentonces escoger el mejor resusoluciones inicia L , se debe definir una bude esa vecindad para el problema en particuprácticamente de manera intuitiva, ya qo r una guía gconveniencia de utilizar una de gran tamóptimo locaes la de tener s V Dado un punto o solución factible f∈ F en un problema particular, es útil en muchos casos definir un conjunto de vecindades N(f) de puntos que son “cercanos” en alguna forma a f. Definición. Dado un problema de optimización con instancias (F,c), una vecindad es un mapeo N : F 2F, definido para cada instancia. Si F = Rn, el conjunto de puntos dentro de una distancia euclidiana x, define una vecindad de forma muy natural. En muchos problemas de optimización combinatoria, la selección de N puede depender críticamente de la estructura de F [9].

17

2.4 Algoritmo de Recocido Simulado El concepto de recocido simulado en optimización combinatoria fue introducido por Kirkpatrick, Gellat y Vecchi en 1983 y en forma independiente por C erný en 1985. Usando una analogía entre estos problemas y el recocido de sólidos que es un proces nde y después se enfría lentamente con el fin de obtener estructuras de cristal perfectas las cuales pueden modelarse como un es o d blemas de optimización combi Sea s ad de s que contiene soluciones alterna s’ ∈ N(s) y se calcula la diferencia D = f(s de f(s) es el valor de la función objetivo en s. Si D < 0, entonces ’ se a como la nueva solución, lo que quiere decir que soluciones ejores se aceptan siempre. Si D > 0 y e-D/cT > r, donde r es un número aleatorio

temperatura se hace descender constante de enfriamientoα, durante el proceso de e la probabilidad de aceptar peores soluciones decrece

if f(s’) < f(s) then s s’

atorio n en [0,1] ((f(s) – f(s’))/ c T) > n) then s s’

d if

o físico en el cual un sólido se fu

tad e mínima energía. La idea es resolver prona por un proceso análogo. toria

la solución actual y N(s) una vecindlecciona de forma aleatoria tivas. Se se

don’) – f(s), seleccions

mgenerado de una distribución uniforme, entonces s’ se acepta como nueva solución, lo que significa que también pueden aceptarse soluciones peores que la actual. T es un parámetro de control llamado temperatura y c es la constante de

oltzman (1.38054x10-3). Como ya se dijo, la Blentamente, mediante unaúsqueda de tal manera qub

constantemente. En cada temperatura el proceso continúa hasta que se cumple el criterio de parada. Tabla 2.3 Algoritmo de Recocido Simulado. Inicio inicializa (sini, T, K0) k 0 s sini do while (T> temperatura mínima (criterio de paro) for k=1 to K0 do

genera s’ ∈ N(s)) else genera_ale if (exp en end for T α T , α∈ (0,1) end do fin

18

2.5 GRASP (greedy randomized adaptive search procedures)

e return x*

GRASP es un método iterativo multi-arranque diseñado para resolver problemas difíciles de optimización combinatoria. Una característica importante de GRASP es la facilidad para implementarse. En su forma más simple sólo hay que determinar el número de iteraciones y el tamaño de la lista de candidatos. Cada iteración consiste de dos fases: una de construcción, en la cuál se produce una solución factible buena, y una de mejora, que es una búsqueda local en la que se examinan vecindades de la solución producida en la fase anterior. La mejor solución encontrada en cada fase se va almacenando hasta concluir el proceso con un criterio de terminación. Se muestra a continuación el seudocódigo de un GRASP básico [9]. Tabla 2.4 Algoritmo GRASP simple. procedure GRASP (f(.), g(.), imax) Require: imáx

f* ← ∞ for i ≤ imáx do construct(g(.), α,x)

x ← GreedyRandomized() x ← local_search(x)

i f f(x) < f* then f* ← f(x)

x* ← x nd if e

nd for

truye en forma iterativa una solución factible, se incorpora un lemento a la vez. En cada iteración, la elección del siguiente elemento se

cambios resultantes por la selección del elemento revio. La componente probabilística del GRASP es caracterizado por elegir de

Fase de construcción En esta fase se consedetermina ordenando a todos los candidatos de una lista C con respecto a una función glotona o miope g:C ⇒ R. Esta función mide el beneficio local de seleccionar cada elemento. La heurística es adaptativa porque los beneficios asociados con cada elemento son actualizados en cada iteración de la fase de construcción para reflejar los p

19

forma aleatoria uno de los mejores candidatos en la lista, y no necesariamente al mejor de ellos. La lista de los mejores candidatos es llamada lista restringida de candidatos (RCL, restricted candidate list). Esta técnica de selección permite obtener diferentes soluciones en cada iteración del GRASP. La tabla 2.5 muestra un algoritmo para la fase de construcción. Tabla 2.5 Algoritmo de fase de construcción del GRASP basado en valor.

x = 0; icializar lista de candidatos C;

while C ≠ 0 do

procedure construct(g(.), α, x)

In

s = mín{ g(t) | t ∈ C }; f- = máx{ g(t) | t ∈ C }; RCL = { s ∈ C | g(s) ≤ s + α( f- – s) }; Selección aleatoria de s de la RCL; x = x ∪ {s}; actualizar la lista de candidatos C; end while end construct; El parámetro alfa controla el grado de miopía y aleatoriedad en el algoritmo. Un valor de α = 0 corresponde a un procedimiento de construcción puramente miope, mientras que con α = 1, uno aleatorio. Aunque los algoritmos miopes pueden producir buenas soluciones razonables, su principal desventaja como generador de soluciones iniciales para búsquedas locales es su falta de diversidad. Aplicando repetidamente un algoritmo miope, una sola o muy pocas soluciones pueden generarse. Un algoritmo totalmente aleatorio produce una gran cantidad de soluciones diversas, pero la calidad de éstas es generalmente muy pobre, y al usarlas como soluciones iniciales para búsquedas locales, generalmente conducen a una convergencia muy lenta. Así entonces, para beneficiarse de la onvergencia rápida del algoritmo miope y la gran diversidad de soluciones del

muestra un algoritmo de construcción on RCL basada en cardinalidad [10], donde la lista está formada por un número jo de elementos con las mejores evaluaciones de la función miope.

calgoritmo aleatorio, se recomienda usar valores de α estrictamente contenido dentro del rango [0,1] El algoritmo de construcción de la tabla 2.5 utiliza una RCL basada en el valor, donde los elementos que la forman cumplen con un valor de la función miope dentro de un rango dado. En la tabla 2.6 secfi

20

Tabla 2.6 Algoritmo de fase de construcción del GRASP basado en cardinalidad. rocedure Construcción-C

equire: k, E, c(.) x ← 0 C ← E Calcular costo miope c(e), ∀ e ∈ C while C ≠ 0 do RCL ← { k elementos e ∈ C con el menor c(e) } Seleccionar un elemento s de RCL al azar x ← x ∪ {s} Actualizar el conjunto candidato C Calcular el costo miope c(e), ∀ e ∈ C end while return x

P R

Existen diferentes variantes del algoritmo de construcción (construcción aleatoria espués miope, construcción con perturbaciones, RCL basada en valores con

da Local

as soluciones generadas en la fase de construcción del GRASP no garantizan

iones simples de vecindades. Por lo cuál una búsqueda local para intentar mejorar cada solución

onstruida. Un algoritmo de búsqueda local explora repetidamente la vecindad de

ile x no es localmente óptimo con respecto a N(x) do Sea y ∈ N(x) | f(y) < f(x)

dsesgo) que pueden ser revisadas en [10].

Fase de búsque

Lser localmente óptimas respecto a definices benéfico aplicar cuna solución en busca de una mejor solución. Cuando no se encuentra una solución que mejora la actual, se dice que la solución es localmente óptima. La clave de éxito de los algoritmos de búsqueda local depende de una elección apropiada de la estructura de vecindades, de técnicas eficientes de búsqueda en vecindades y de la solución inicial. En la tabla 2.7 se muestra un algoritmo sencillo de búsqueda local para el GRASP [10]. Tabla 2.7 Algoritmo de búsqueda local del GRASP. Procedure BúsquedaLocal Require : x0, N(.), f(.) x ← x0

wh x ← y end while return x

21

2.6 Satisfacción de Restricciones

ente resolución de restricciones.

rea cada subconjunto. Dependiendo si los

n estado del problema es a algunas o a todas las variables, {Xi que no viola ninguna restricción se llama consi . Una asignación completa es una en la que cada var a solución a un PSR es una asignación completa que satisface a todas las restricciones. La resolución de un PSR consta de dos fases:

i. Modelar el proble isfacción de restricciones. La modelación expresa conjunto de variables, dominios y restricciones del PS

ii. Procesar el problem ciones resultante, para lo que hay dos formas.

1. Técnicas de co e resolución de PSR basadas en la eliminación de valores inconsistentes de los dominios de las variables.

renciales permite deducir información del

La programación de restricciones puede dividirse en dos ramas claramdiferenciadas: la satisfacción de restricciones y la Ambas comparten la misma terminología pero sus orígenes y técnicas de resolución son diferentes. Un problema de satisfacción de restricciones (PSR) está definido por un conjunto de variables X1, X2,…, Xn, y un conjunto de restricciones r1, r2,…,rm. Cada variable Xi tiene un dominio Di de posibles valores. Cada

stricción ri comprende algún subconjunto de variables y especifica las combinaciones de valores permisibles pardominios de las variables son discretos o continuos, finitos o infinitos, se pueden distinguir distintos tipos de PSRs. U está definido por una asignación de valor

= a asignación vi, Xj = vj,…}. Unstente o asignación válidaiable e a; uns mencionad

ma como uno de satel problema mediante un R.

a de satisfacción de restric

n cia. Son técnisisten cas d

2. Algoritmos de búsqueda. Se basan en la exploración sistemática del espacio de soluciones hasta encontrar una solución, o probar que no existe alguna.

as técnicas de consistencia o infeL

problema, niveles de consistencia, valores posibles de variables, dominios mínimos, etc., aunque en general se combinan con las técnicas de búsqueda, ya que reducen el espacio de soluciones y los algoritmos de búsqueda exploran dicho spacio resultante. e

Una forma de hacer mejor uso de las restricciones durante la búsqueda se llama inspección hacia delante. Siempre que una variable X es asignada, el proceso de inspección hacia delante mira a cada variable Y no asignada que está conectada a X por una restricción y borra del dominio de Y cualquier valor que es inconsistente para el valor escogido para X.

22

El conjunto formado por todas las posibles asignaciones de un PSR, también conocido como espacio de estados, se representa mediante un árbol de búsqueda. En cada nivel se asigna un valor a una variable, y los sucesores de un odo son todos los valores de la variable asociada a este nivel. Cada camino del

nodo raíz a un nodo terminal representa una asignación completa. Los algoritmos e búsqueda a la hora de encontrar

oluciones: búsqueda onflicto, etc.

ritmos Híbridos En algunos casos, la efectividad de un algoritmo puede ser mejorada al combi o y se puede aplicar Por ejemplo, para el AG se puede aplicar una

a específica para crear la población inicial de tal manera que cada individbúsque

os consisten en la combinación de algoritmos, ya sea que

codificación del problema. Sin embargo, concluye que esto es preferible i se desea una buena solución para un problema en específico, más que la

evaluación del d e o A a i r s En el caso de r o i im d , s n entido de mejorar la solución a la a a m d e proporciona una buena solución al ARS en lugar de una srecomienda empezar el algoritmo a temperaturas bajas, para no correr el riesgo de destruir la c n e l s r asolución encontrada sea un mínimo local.

n

se diferencian en cómo recorren el árbol dshacia atrás, salta hacia atrás, salta hacia atrás directo a c

2.7 Algo

narlo con otro algoritmo, a lo que se le conoce com hibridación de diferentes maneras.

heurísticuo sea una solución factible. El AG se puede combinar con algoritmos de da local para mejorar la calidad de la solución.

Los algoritmos híbridformen parte de otro algoritmo o que sirvan para mejorar la entrada o salida de un algoritmo principal. Esto con el fin de mejorar el desempeño del algoritmo y la calidad de la solución. Sin embargo, esto requiere de un conocimiento más específico del problema. A veces estas modificaciones rompen con los paradigmas de cada algoritmo. Por ejemplo, Reeves [10 ] comenta que el incorporar heurísticas específicas al AG rompe con una de sus principales ventajas, que es la de encontrar soluciones para cualquier tipo de problema, sin tener un conocimiento detallado de éste y su funcionamiento depende de una adecuadas

esemp ñ del G p ra d ferentes p oblema .

ec c do s ula o la combinaciones son e el s entrad o a la s lida del algorit o. Cuan o s

olución generada de forma aleatoria, se

solu ió n a p imer s etapas. El problema pudiera ser que la

23

Capítulo 3. IMPLEMENTACIÓN DEL ALGORITMO

ENÉTICO

.1 Introducción

l AG es quizá el método heurístico más utilizado para el PDE debido a su fácil

es que se aplica a cada nueva eneración. Esto debido a que aún cuando la población inicial esté conformada or soluciones factibles, los operadores de cruza y mutación se encargan de que

las nuevas combinaciones de potencias resultantes no cumplan con el balance de potencia BP.

ios para conformar los dividuos de la población inicial y poneolución.

la implementación de un AG al problema

G

3 Erepresentación en código binario. Para resolver el PDE, algunos autores hacen uso de un algoritmo de reparación de soluciongp

Sin embargo, el AG no requiere más que una apropiada codificación y el establecimiento adecuado de la función objetivo. No se requiere conocer más del problema en cuestión. Basta con generar números aleatorin r en marcha el AG para encontrar una s En el desarrollo del capítulo se muestrade DE. Se utiliza una codificación binaria para representar el nivel de potencia de cada generador. Un cromosoma está formado por las potencias codificadas de las unidades.

24

3.2 Descripción del programa El programa principal Despacho_AG que implementa el AG tiene 4 módulos: - Pob_ini: Crea la población inicial de forma aleatoria. - Evaluación: Evalúa la función objetivo.

Selección: Selecciona por "torneo" a los mejores individuos de acuerdo a su

ue aplicados a los individuos seleccionados por el módulo de selección, dan paso a una nueva

a estructura de datos utilizada en el programa para representar una unidad eneradora es la siguiente:

Tabla 3.1 Estructura de datos generador. tr e

oat coef_a; oat coef_b; oat coef_c;

float coef_e;

bool hay_zm; float ini_zm; float fin_zm; }

- evaluación

- Hijos. Implementa los operadores de cruza y mutación y q

población. Lg

s

uct gfl

nerador {

flfl

float coef_f; float Pmin; float Pmax; int L;

Las primeras 5 variables de la estructura de datos generador corresponden a los coeficientes abcef de la función general de costo F, que es de la forma: F = aP2 + bP + c + e sen(f * (Pmin-P)) Esta es la función general que modela los puntos de válvula. Si los coeficientes e y f son cero, entonces la función de costo no modela el punto de válvula y se transforma en una función de segundo grado. Pmín y Pmáx son variables de punto flotante que almacenan los límites de potencia de la unidad. L es una variable de tipo entero que almacena el tamaño de la subcadena que representa a una unidad. hay_zm es una variable de tipo booleana que toma el valor 1 si está definida una zona muerta o 0 sino lo está.

25

ini_zm y fin_zm sonicio y fin de la zona muerta. Si

variables de punto flotante que almacenan las potencias de hay_zm = 0, entonces estas variables deben ser

cación

ntrada:

tamaño de la población: tam_pob

ubcadena: Lialida:

población de tam_pob individuos. Cada individuo tiene Us enteros ria. Las soluciones no son factibles.

omas se representaron por una cadena binaria. Cada cadena binaria está formada por subcadenas de 2 bytes (fig. 3.1) que representan la potencia de una unidad. El problema del DE no requiere mucha precisión en el nivel de generación asignado, normalmente se utilizan cifras enteras tanto para las otencias como para la demanda pronosticada. Sin embargo, si se quiere usar

tes se puede disponer de un rango de 216/10 = 6553.6, suficiente para representar la potencia de una unidad generadora (en México las unidades de la CN Laguna Verde son las de mayor potencia: 682.4

W c/u)

U1

iniguales al valor de Pmín.

3.3 Población inicial y codifi La población inicial se crea a través del módulo Pob_ini. Módulo Pob_ini. Crea la población inicial de forma aleatoria. E

número de unidades: Us

límites de potencia de generadores: Pmini, Pmaxi 1 ≤ i ≤ Us longitud de s

S

generados de forma aleato 3.3.1 Codificación. Los individuos o cromos

puna precisión de 1 decimal, con 2 by

M

7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0

7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0

U2 . . s u b c a d e n a

UUs

. 2 b y t e s 7 6 5 4 3 1 0 7 6 5 1 0 2 4 3 2

Figura na, individuo o cromosoma. 3.1 Cade

26

3.3.2 Representación de los límites de potencia del generador.

del rango de peración de la unidad y la precisión que se desea utilizar. Por ejemplo, si el

rango de opera a precisión de se requiere de a

con 11 bits:

ara esta L de la subcadena es 11:

entero de 2 bytes

La representación de los límites de potencia está en funcióno

ción de la unidad es de 35 a 210 MW y se desea unun decimal, entonces diferentes, lo cuál se log

l menos (210-35)*10 = 1750 números ra

10 < 1750 < 2112

211=2048 210=1024 P unidad sólo se utilizarían 11 de los 16 bits, y la longitud

7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0

sin uso

Figura 3.2 Subcadena de 11 bits. 3.3.3 Decodificación Para convertir una s a 3, 1, b0) al valor entero correspondiente, se utiliz iguie ua

2011 −=⎜⎝

⎛⋅= ∑

.

ubcaden b (binariante ec

L-1,..., b b2, ba la s ción:

1,...,0;10)...(10⎠

1

0=⎟ va⎞−

=− Lenterolorbbb

L

k

kt

El valor entero representa un valor de potencia entre los límites de generación especificados, que se decodifica co uient u

kbk

n la sig e ec ación:

12)( minmaxmin

−−

+= Li

iiProvPPi

3.3.4 Codificación de la zo muea zona muerta es un rango de operación donde no se puede operar una unidad

por razones técnicas y/o económicas. Estas regiones se pueden restringir desde la

Pentealori

na rta. L

27

propia codificación operación en zona muerta. Para tomar

o mediante la penalización de aquellas soluciones que incluyan en cuenta la zona muerta desde la

la unidad opera arriba de la zona muerta, el valor entero codificado n 2L unidades.

i la unidad opera en zona generador).

para decodificar el valor m, son como se muestran en la tabla 3.2.

lacodificación de la potencia, se agregó un bit adicional bit_zm a la subcadena para indicar la operación arriba (bit_zm = 1) o debajo (bit_zm = 0) de la zona muerta.

uandoCaumenta e

ro, se debe revisar sCuando se decodifica el valor enteuerta (variable hay_zm de la estructura de datos m

Los límites de potencia que se usan en la expresión entero según el valor de bit_z Tabla 3.2 Límites de potencia usados en la decodificación del valor entero Pcod según el valor de bit_zm.

bit_zm Pmín PmáxExpresión para decodificar valor entero

Pcod 1 Pzmfin Pmáx0 Pmín Pzmini 12

)minmax(min−

−+= Li

iPiPPcodiPPi

Por ejemplo, para representar el rango de 122 a 489 se requieren 12 bits, L=12.

extremos de la codificación de una unidad con m = 260, fin_zm = 320 MW; y con límites de

otencia Pmín=122 MW y Pmáx= 489 MW.

La figura 3.7 muestra los valores zona muerta definida en el rango ini_zp

(decimal) (entero) bitP Pcod zm

15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 01 1 1 1 1 1 1 1

12 11 10 9 8 7 6 5 4 3 2 1 01 1 1 1 1 1 1 1 1 1

3 2 1 00 0 0

14 13 12 11 10 9 8 7 6 5 4 3 2 1 00 0 0 0 0 0 0 0 0 0 0 0 0

[MW]489.0 8191 1 1 1 1 1

15 14 13260.0 4095 0 1 1

15 14 13 12 11 10 9 8 7 6 5 4320.0 4096 1 0 0 0 0 0 0 0 0 0

15122.0 0

Figura 3.3 Representación de diferentes valores de potencia a través del bit_zm para una unidad con zona muerta.

28

3.4 Evaluación Este módulo calcula la aptitud de cada individuo. Entrada: Tamaño de la población: tam_pob Archivo con tam_pob individuos Coeficientes de funciones de costo: coeficientes aibicieifi, modelo de 3 puntos (MW, kcal/MWh) de PIE. Factores de penalización por incumplimiento de BP: FP_IBP Incio y fin de zona muerta: ini_zmi, fin_zmi 1 ≤ i ≤ Us Salida: Archivo con aptitudes de los individuos de la población Para evaluar la función es necesario decodificar cada uno de los valores enteros de cada individuo. 3.4.1 Aptitud de los individuos La función objetivo del problema de DE fue utilizada directamente para evaluar la aptitud de los individuos:

e utilizaron divisores para escalar la aptitud de los individuos de tal forma que quedara representada con 3 dígitos. El FP_IBP también fue atenuado con el mismo d re ia a su alor ori

ZMPdemandaPIBPFPPFaptitudn

ii

n

iii __)(

11+⎟

⎠

⎞⎜⎝

⎛−+= ∑∑

==

La función objetivo incluye los costos de generación de cada unidad, la penalización por incumplimiento de balance de potencia FP_IBP y la penalización por operar en zona muerta P_ZM.

∑=

=i

ii PFZMP1

)(1.0_n

S

ivisor en los algoritmos, pero en los resultados se hace ferencginal para no causar confusión. v

Tabla 3.3 Factores de escalamiento de aptitud para cada caso de estudio.

divisor caso 1 1000caso 2 10000caso 3 10

29

3.4.2 Función de costo. En los casos de estudio se evalúan 3 tipos de funciones de costo:

Tabla 3.4 Tipos de funciones de costo de los casos de estudio. Tipo función de costo Descripción

Convexa de segundo grado Funciones de costo clásicas, coeficientes abc No convexa de segundo grado Modelo especial de PIE. No convexa: de segundo grado + senoidal Para modelar punto de válvula Para los dos primeros casos se evalúa directamente la función de costo. Los o l c

Deficientes abcef tienen las unidades apropiadas para obtener el costo en $/h. E

E se realiza para un periodo determinado y en los casos de estudio es de 1h.

Tabla 3.5 Unidades de los coeficientes abcef de la función general de costo. a b c e f

[$/MW2h] [$/MWh] [$/h] [$/h] adimensional Para el tercer tipo, el PIE proporciona 3 puntos de operación de una curva de onsumo específico o régimen térmico, con unidades kcal / kWh. Los precios de

de peración.

Tabla 3.6 Tabla de costos del PIE CC Mexicali.

Potencia Consumo específico costo

clos combustibles se actualizan diariamente. Los valores en $/MWh mostrados en la fig. 2.2 fueron convertidos con un precio de 267.4 $/gcal. Para obtener el costo de valores de potencia entre estos tres puntos, se utilizó el método de interpolación lineal. La tabla 3.6 muestra en negrita los tres puntos proporcionados por el PIE, y los demás son costos interpolados para diferentes puntoso

[MW] [kcal / kWh] [$/MWh] [$/h]

49 1,837.0 491 24,02098 1,845.3 493 48,257

122 1,849.4 495 60,456147 1,853.5 496 72,710196 1,861.8 498 97,380245 1,870.1 500 122,266260 1,865.5 499 129,700293 1,855.7 496 145,592320 1,847.9 494 158,124342 1,841.4 492 168,543367 1,834.2 490 179,878391 1,827.0 489 191,119440 1,812.7 485 213,319489 1,798.3 481 235,143

30

3.5 Selección Este módulo selecciona por torneo a los mejores individuos de acuerdo con su aptitud. Entrada: Archivo con aptitudes de los individuos de la población. Tamaño de la población: tam_pob

individuos ción menor

uando el problema es de maximizar, el ganador es el que tiene una evaluación

toriamente), y el que tiene la peor evaluación mayor nunca asa a la siguiente generación. Este tipo de selección es muy fácil de implementar tiene la ventaja sobre otros métodos porque no necesita ordenar a los individuos.

3.6 Nuev El módulo s operadores de c tación, que aplicados a

idu ulo de s dan paso a una nueva eneración.

chivo con tam_pob individuos de una nueva generación

3.6.1 Mut

e utilizó una probabilidad de cruza Pc= 0.8 y una probabilidad de mutación m=0.01 durante todo el proceso evolutivo. Se pueden usar uno o dos puntos de

n una probabilidad Pc. Después cada bit del cromosoma es

Salida: Archivo con individuos seleccionados por torneo.

3.5.1 Selección por torneo Se escogen a los ganadores de una competencia entre dosseleccionados aleatoriamente. El ganador es el que tenga una evalua(cmayor). El individuo más apto es seleccionado tantas veces como haya sido puesto a competir (aleapy

as generaciones.

Hijos implementa lo ruza y mulos indivg

os seleccionados por el mód elección

Entrada: Archivo con tam_pob individuos seleccionados Probabilidad de cruza: PcProbabilidad de mutación: Pm. Longitud de subcadena: Li 1 ≤ i ≤ Us Salida: Ar

ación y cruza.

SPcruza pcruza y su valor se elige de forma aleatoria para cada par de padres. Un par de padres genera un par de hijos. Los padres se leen de forma secuencial de un archivo y se cruzan co

31

revisado con el operador de mutación. En la figura 3.4 se muestra la operación de ruza a nivel de bits con un punto de cruza pcruza = 14 en una cadena de 33 bits c

que representa a 3 unidades. El valor de pcruza se escoge entre 1 y 33. Padre 1 Padre 2

7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 Pcod 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 Pcod1 1 0 0 0 1 0 0 0 1 0 1570 U1 0 1 0 0 0 1 1 0 0 1 0 5621 2 3 4 5 6 7 8 9 10 11 1 2 3 4 5 6 7 8 9 10 11

7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 Pcod 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 Pcod1 1 1 0 1 1 0 0 1 1 1 1895 U2 1 1 1 0 0 0 0 0 0 1 0 1712 13 14 15 16 17 18 19 20 21 22 12 13 14 15 16 17 18 19 20 21 22

94

7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 Pcod 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 Pcod0 1 1 0 1 1 0 0 0 0 1 865 U3 0 0 1 0 1 1 0 1 0 0 1 361

23 24 25 26 27 28 29 30 31 32 33 23 24 25 26 27 28 29 30 31 32 33

Hijo 1 Hijo 27 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 Pcod 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 Pcod

1 1 0 0 0 1 0 0 0 1 0 1570 U1 0 1 0 0 0 1 1 0 0 1 0 5621 2 3 4 5 6 7 8 9 10 11 1 2 3 4 5 6 7 8 9 10 11

7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 Pcod 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 Pcod1 1 1 0 1 1 0 0 1 1 1 1794 U2 1 1 1 0 1 1 0 0 1 1 1 189512 13 14 15 16 17 18 19 20 21 22 12 13 14 15 16 17 18 19 20 21 22

7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 Pcod 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 Pcod0 1 1 0 1 1 0 0 0 0 1 361 0 1 1 0 1 1 0 0 0 0 1 865U3

23 24 25 26 27 28 29 30 31 32 33 23 24 25 26 27 28 29 30 31 32 33

Figura 3.4 Cruza de 2 individuos a nivel de bits, con pcruza = 14.

or debido a que l punto de cruza cayó en un punto en donde los bits más significativos de las

unidades 2 son iguales. Con pcruza = 16, los bits más significativos de las unidades 2 en los padres ya no son iguales y el valor codificado de las unidades 2 en los hijos son diferentes, como se observa en la figura 3.5.

En el ejemplo anterior, con el operador de cruza se intercambiaron las unidades 2 y 3 de los padres a los hijos, pero ninguna unidad modificó su vale

7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 Pcod 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 Pcod1 1 1 0 1 0 0 0 0 1 0 1858 U2 1 1 1 0 0 1 0 0 1 1 1 183112 13 14 15 16 17 18 19 20 21 22 12 13 14 15 16 17 18 19 20 21 22

Figura 3.5 Modificación del valor de potencia por operador de cruza, pcruza = 16.

Se implementó también un operador de cruza a nivel de unidades y se refiere al intercambio de los valores de potencia asignados a las unidades. En este caso, no es necesario el proceso de codificación-decodificación. En la figura 3.6 se muestra un ejemplo de este operador con dos puntos de cruza. Se muestran los valores

32

decodificados para revisar el valor de potencia que suministran, pero como se dijo antes, no es necesaria la decodificación de los valores enteros. En este caso los puntos de cruza se escogen de forma aleatoria entre 1 y el número total de unidades. Varios puntos de cruza son recomendados cuando el tamaño de la cadena es grande.

PadresTotal P1 P2 P3 P4 P5 P6 P7 Total P1 P2 P3 P4 P5 P6 P7803.7 134.1 226.6 174.7 21.5 7.7 13.9 225.2 803.7 70.6 235.9 113.2 21.0 21.3 27.9 313.9

HijosTotal P1 P2 P3 P4 P5 P6 P7 Total P1 P2 P3 P4 P5 P6 P7755.2 134.1 226.6 113.2 21.0 21.3 13.9 225.2 852.2 70.6 235.9 174.7 21.5 7.7 27.9 313.9

Figura 3.6 Operador de cruza a nivel de unidades con dos puntos de cruza, pcruza1 = 2, pcruza2=5

Se observa como se pierde la factibilidad de la solución con el operador de cruza. La demanda que cubrían los padres era de 803.7 unidades y los hijos ya no cumplen con ese valor de demanda. Se p de agregar un algoritmo reparador de la solución que aumente o disminuya la potencia de una o varias unidades para cumplir con el BP. Sin embargo, se ostrará más ad lante que el AG va mejorando el BP en cada generación. El operador de mutación revisa bit a bit todo el cromosoma y con una probabilidad muy baja cambia el valor de alguno de ellos. Aún así, si la cadena es larga, la probabilidad de que exista un cambio en algún bit es alta. En la figura 3.7 se muestra como cambia el valor del hijo 1 por el operador de mutación que tuvo efecto en el bit 23 y cambió el valor de potencia de la unidad 3 de 159 a 254.

Figura. 3.7 Operador de mutación modificó bit 23 en una cadena de longitud 33.

ue

m e

Hijo1, Mutación en el bit 23 del cromosoma Hijo 2, sin mutación

hijo 1 hijo 20 562

P11 2 3 4 5 6 7 8 9 10 11 1 2 3 4 5 6 7 8 9 10 11 83

antes 169 antes 8315 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 1858 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 1831

antes 159 P1+P2+P3 = antes 205antes antes635 593

0 593

15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 1570 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

1 1 0 0 0 1 0 0 0 1 0 P1 0 1 0 0 0 1 1 0 0 1 0169

1 1 1 0 1 0 0 0 0 1 0 P2 1 1 1 0 0 1 0 0 1 1 1 P212 13 14 15 16 17 18 19 20 21 22 307 12 13 14 15 16 17 18 19 20 21 22 304

antes 307 antes 30415 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 1385 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 865

1 0 1 0 1 1 0 1 0 0 1 P3 0 1 1 0 1 1 0 0 0 0 1 P323 24 25 26 27 28 29 30 31 32 33 254 23 24 25 26 27 28 29 30 31 32 33 205

P1+P2+P3 = 73

33

3.6.1.1 Zona muerta r de cruza a nivel de bits, las zonas de operación por arriba o por

ebajo de la zona muerta se pueden modificar de los padres a los hijos cuando el

te generación.

3.7 Ajuste de los parámetros particulares del AG al PDE Los parámetros utilizados por defecto, en todos los casos de DE que se plantean, son los de la tabla 3.7.

Tabla 3.7 Parámetros utilizados por defecto para el AG. Parámetro valor

Con el operadodpunto de cruza es tal que divide al padre justo en el bit_zm, y si además el bit_zm de la unidad del otro padre es de valor opuesto. Con el operador de cruza a nivel de unidades, cada unidad conserva su zona de operación. El operador de mutación también opera en el bit_zm para cambiar la zona de operación en una unidad con zona muerta. De esta forma se proporciona más variedad en las soluciones para la siguien

Probabilidad de cruza (Pc) 0.80 Probabilidad de mutación (Pm) 0.01 Punto de cruza: 2 puntos aleatorios Método de selección: Por torneo Tamaño de la población (tam_pob) 40 , 100

Como se explicó en el marco teórico, los valores anteriores han mostrado buenos resultados en muchos problemas y son ampliamente utilizados. No es el propósito de ésta tesis un análisis exhaustivo de todos los parámetros del AG, y sólo se detallan aquellos parámetros que son particulares del problema del DE. Para el caso del tamaño de la población, se realizaron pruebas para valores de 40 y 100 individuos. Los parámetros de la tabla 3.8 son los particulares al PDE que se va a resolver.

Tabla 3.8 Parámetros a determinar para el AG Parámetro Factor de penalización por incumplimiento del balance de potencia (FP_IBP) Factor de penalización por zona muerta (FP_ZM)

Las gráficas, en general, fueron generadas con cinco valores de semillas aleatorias diferentes (100, 200, 300, 400 y 500). Cada curva es el promedio de estas cinco pruebas.

34

3.7.1 Tamaño de la población. Al incrementar el tamaño de la población, se evalúan en paralelo un mayor número de individuos en el espacio de solución y es más probable encontrar mejores soluciones; sin embargo, éste no debe ser muy grande porque el proceso sería semejante a una búsqueda aleatoria. La figura 3.8 muestra la convergencia del AG aplicado al caso 1, con poblaciones de 40 y 100 individuos. Los resultados fueron ligeramente mejores con 100 individuos. Después de 150 generaciones, la aptitud del mejor individuo mejoró en 0.86% y la aptitud promedio de cada generación sólo lo hizo en 0.8%. Respecto al BP la convergencia fue muy similar.

490500

0 10 20 30 40 50 60 70 80 90 100

110

120

130

140

150

núm. generaciones

ap

510

580590600

tio

520530540550560570

tud

del m

ejor

indi

vidu

Pob 40 Pob 100

950

1,000

750800

850

900

pro

med

io

600

650

700

aptit

ud

500

550

0 10 20 30 40 50 60 70 80 90 100

110

120

130

140

150

núm. generaciones

Pob 40 Pob 100 a) b)

c)

0

10

20

30

0 10 20 30 40 50 60 70 80 90 100

110

120

130

140

150

núm. generaciones

Bal

ance

de

Pote

ncia

40

, BP

[M

50

W]

Pob 40 Pob 100 Figura 3.8 a) aptitud mejor individuo b) aptitud promedio de cada generación c) balance de potencia BP, para poblaciones de 40 y 100 individuos, caso 1. FP_IBP = 2 500

35

El efecto del tamaño de la población para el caso 2 de 36 unidades se muestra en la figura 3.9. La aptitud del mejor individuo mejoró sólo un 0.12%; la aptitud romedio de cada generación mejoró en promedio 0.1 % y la convergencia del BP p

fue muy similar. Se utilizó un FP_IBP = 563.

445

450

0 50 100

150

200

250

300

núm. generaciones

aptit

ud d

el m

ejo

455

460

indi

vidu

or

Pob 40 Pob 100

445

450

455

0 50 100

150

200

250

300

núm. generaciones

aptit

ud p

r

460

ome

465

470

dio

Pob 40 Pob 100 a) b)

c)

0

50

100

150

0 50 100

150

200

250

300

núm. generaciones

Bal

ance

de

pote

ncia

, BP

[MW

]

Pob 40 Pob 100 Figura 3.9 a) aptitud mejor individuo b) aptitud promedio de cada generación c) balance de potencia BP, para poblaciones de 40 y 100 individuos, caso 2. Al incrementar el tamaño de la poblacequeñas misma

ión en un 150 % se observan mejorías muy en el desempeño del AG mientras que se incrementa en lap

proporción el número de operaciones. Debido a esto será utilizado el tamaño de población de 40 individuos para las pruebas finales del AG, cuyos mejores resultados serán comparables con las heurísticas que se presentan en los capítulos 4 y 5.

36

3.7.2 Elitismo El elitismo consiste en conservar al mejor individuo generado durante todo el proceso del AG. En cada generación se escoge al individuo con mejor aptitud y se pasa automáticamente a la siguiente generación, sin ningún cambio. De esta forma se evita que un individuo con excelente aptitud, producido en las primeras generaciones, se pierda por las operaciones de cruza y mutación subsecuentes. En la figura 3.10 se muestra el desempeño promedio de 5 pruebas del AG con y sin elitismo, aplicado al caso de estudio 1 de 7 unidades, con semillas de 100 a 0 y FP_IBP = 2500. Después de 500 generaciones, se obtuvo una mejora de 5 0

1.03% en la aptitud del mejor individuo.

490

510

530

550

570

590

610

aptit

ud d

el m

ejor

indi

vidu

o

630

0

100

200

300

400

500

núm. generaciones

sin elitismo con elitismo

0

5

10

15

20

25

30

35

40

45

alan

ce d

e Po

tenc

ia, B

P [M

W]

50

0

100

200

300

400

500

núm. generaciones

B

sin elitismo con elitismo

igura 3.10 Comparación de la convergencia del AG con y sin elitismo, a) aptitud del mejor dividuo, b) balance de potencia, caso 1.

Puede parecer extraño que la curva de aptitud del mejor individuo del caso “sin elitismo” esté por debajo del caso “con elitismo” en algunas zonas. La explicación es porque los individuos de sus poblaciones son diferentes. Cuando no se usó elitismo, se generaron mejores individuos en algunas generaciones. Aunque se usaron las mismas semillas aleatorias, es muy probable que desde la primera generación las poblaciones de ambos casos hayan sido distintas en al menos un individuo. Se dice que es muy probable porque la probabilidad de cruza es alta (0.8) y la probabilidad de mutación es muy baja (0.01) y no se descarta el hecho de que el individuo más apto haya pasado a la siguiente generación sin cambios,

a generación pudo haber sido la misma en ambos casos, pero lo más

robable es que en algún punto de las primeras generaciones, las poblaciones de

a) b) Fin

por no haber sido afectado por los operadores generacionales. La población de lprimera plos dos casos fueron diferentes en al menos un individuo. La figura 3.11 corresponde a la aplicación del AG al caso 2. Se usó elitismo y un FP_IBP=563. La mejora al final de 500 generaciones fue de 0.43% respecto al mejor individuo obtenido con el AG sin elitismo. La mejora más notable fue en el BP.

37

445

450

455

4600

100

200

300

400

500

núm. generaciones

aptit

ud d

el m

ejor

indi

vidu

o

sin elitismo con elitismo

0

20

40

60

80

100

120

0

100

200

300

400

500

núm. generaciones

Bal

ance

de

Pote

ncia

, B

P [M

W]

sin elitismo con elitismo Figura 3.11 Comparación de la convergencia del AG con y sin elitismo, caso 2.

Para el caso 2, que es un problema mucho más grande respecto al caso 1, se

a final fuera factible.

or último, se observa en las gráficas anteriores la rápida convergencia que se

vislumbra entonces la posibilidad de utilizar un algoritmo de úsqueda local para mejorar la solución después de la generación número 75 para

el cas 3.7.3 Factor de penalización por incu iento del b e de potencia (FP_IBP).

l factor de penalización FP_IBP castiga a las soluciones que no cumplen con el P, modificando en forma negativa su aptitud. Este factor debe ser ajustado

a soluciones que cumplen on el BP, pero resultan en costos superiores al óptimo. En la tabla 3.9 se

mue Se escogieron algunos valores extremos resultado f

Tabla 3.9 Resultados del A s valo o 1.

P2 [MW] [MW] [MW]

6 ]

P7 [MW]

b) ización

por IBP

Aptitud (a+b)

error r en [%]

3 62.0 62.3 7.0 8.0 122.0 56,173 328,093 .578 200.8 235.3 7.0 8.1 326.1 155 493,737 028 143.1 243.7 13.8 7 392.1 -424 517,645 .00

8 45.9 248.0 248.0 7.0 7. 8.0 306.1 48 solución óptim

observó la dificultad en la convergencia en BP, y el uso de elitismo hizo que lsolución Ptuvo en las primeras generaciones, después de las cuales el AG perdió efectividad. Se b

o 1, y después de la generación 150 para el caso 2.

mplim alanc

EBadecuadamente para cada instancia del problema. Valores pequeños hacen que la solución converja a un costo menor al óptimo a expensas de un BP negativo, lo cuál significa que la suma de las potencias asignadas sea menor a la demanda. Por el contrario, valores grandes de FP_IBP conducenc

stran los resultados de tres valores del FP_IBP aplicados al caso 1. para acentuar el inal.

G para distintosolución AG

res del FP_IBP y s

a) Cos

lución óptima del caso

Demanda [MW] FP_IBP

P1 [MW]

P3 P4 P5 P[MW] [MW

to de operación [$] Penal costo

erroBP

[%]-44.2 -6408.3 100 40.0 7.0 271,920

69.8 1000 85.252.4

7.410.

493,58251

1.3 -0.6.70.0 10000 1 14. 8,069 3 0

70.0 0 7,018 a

38

Con un valor pequeño de FP_IBP (100) se obtuvo un menor costo de operación ue grande y no se cubrió ni la mitad de la

emanda. Con un FP_IBP grande (10000) no hubo error en BP, pero el costo fue 6.3% superior al óptimo. Un valor de FP_IBP de 1000 proporcionó mejores resultados, tanto en costo como en BP. Los valores más adecuados se obtuvieron bajo el siguiente razonamiento: un error de 1 MW en el BP debe ser comparable con el costo más grande que tiene una unidad al aumentar o disminuir esa misma potencia unitaria, para que el error sea debidamente penalizado. El costo por aumentar o disminuir un MW en cada unidad a partir de un punto de operación se denomina costo incremental CI y se obtiene de derivar la función de costo F. Por ejemplo, supóngase que se tienen 50 unidades baratas operando con un CI= 1 $/MW, y una unidad cara operando con CI = 50 $/MW. Resulta en el mismo costo que las 50 unidades aumenten 1 MW, con un total de 50 MW de incremento, que si lo hace en 1 MW la unidad cara. La penalización por una diferencia de 1 MW en el BP debe ser similar al costo de aumentar 1 MW en la unidad con CI más alto. Entonces el valor de FP_IBP puede establecerse en un valor similar al CI más alto de todas las unidades.

respecto al óptimo, pero el error en BP fd

(27, 2500)

1,250

1,500

1,750

2,000

2,250

2,500

2,750

0 5 10 15 20 25 30 35 40

MW

$/M

Wh

CI 4 CI 5 CI 6

Figura 3.12 Curvas de las unidades con mayor costo incremental del caso1.

En la fig. 3.12 se muestra el costo incremental más alto (2500 $/MWh) de las unidades del caso 1 y corresponde a la unidad 4 en su límite de potencia de 27 MW. En la figura 3.13 se muestra el desempeño del AG con valores de FP_IBP de 2000, 2500 y 3000. Los resultados para los dos primeros valores fueron muy similares y se podrían utilizar indistintamente.

39

495

505

515

525

535

aptit

ud d

el m

ejor

i

545

0

ndiv

555

565

iduo

50 100

150

200

250

300

núm. generaciones

2000 2500 3000

0

8

10

P [M

W]

3

5

Bal

ance

de

pote

ncia

0 50 100

150

200

250

300

núm. generaciones

, B

2000 2500 3000

Convergencia en aptFigura 3.13 itud y en BP del AG, con valores de FP_IBP de 2000, 2500 y 3000, c

ara el ca cremental más alto es de 563 $/MWh y corresponde a la

aso 1.

so 2, el costo inPunidad 23, en su límite de potencia de 498 MW, ver fig. 3.14. En la figura 3.15 se muestra el desempeño del AG con valores de FP_IBP cercanos a 563. Se obtuvieron mejores aptitudes con FP_IBP = 500, pero también se tuvo la peor curva en cuanto a BP. La curva correspondiente a FP_IBP = 563 presentó el mejor balance entre aptitud y BP.

(498, 563)560

580

CI16 CI27500

520

$/M

Wh

CI23

CI25

CI26

480

540

400

420

440

460

50 150 250 350 450 550 650

MW

CI16 CI23 CI25 CI26 CI27

Figura 3.14 Curvas de las unidades con mayor costo incremental del caso 2.

40

446

0

100

200

300

400

500

448

450

núm. generaciones

apti

452

454

456

458

460tu

d de

l mej

or in

divi

duo

500 563 700

0

0

100

40

80

200

300

400

500

núm. generaciones

Bal

ance

de

Po

120

160

200

tenc

ia, B

P [M

W]

500 563 700

5. Convergencia en aptitud y en BP del AG aplicado al caso 2, con distintos valores de

(DEPV) se revisaron los costos incrementales y el más alto fue de rrespondiente a la unidad 3 a una potencia de 179 MW. Se hicieron

valores de FP_IBP de 15, 20 y 25 usando elitismo. En la figura 3.16 la convergencia en aptitud y BP. El mejor valor de FP_IBP fue el de

que da una buena convergencia tanto en BP como en aptitud. Los valores y 50 dan buena convergencia en cuanto a costo, pero no

al en cuanto a BP.

Figura 3.1FP_IBP.

Para el caso 3co20.6 $/MW,

aprueb s constranse mue

5, ya2superiores como 30 sucede igu

8300

8400aptit

8500

8600

ud m

vidu

o

8700

0

100

200

300

400

500

núm. generaciones

ejor

indi 15

20

25

0

5

10

15

20

25

30

0

100

200

300

400

500

núm. generaciones

Bal

ance

de

Pote

ncia

, BP

[MW

]

152025

tintos valores de

para cada caso de estudio. FP_IBP Generaciones

Figura 3.16. Convergencia en aptitud y en BP del AG aplicado al caso 3, con disP_IBP. F

Los mejores valores de FP_IBP que se determinaron para cada caso se muestran en la tabla 3.10.

Tabla 3.10 Ajustes del FP_IBP y número de generaciones

Caso 1 2 500 300 Caso 2 563 500 Caso 3 25 400

41

3.8 Resumen de resultados del AG (DE con funciones convexas).

a tabla 3.11 muestra los resultados de la aplicación del AG a cada uno de los

abilidad de cruza = 0.8, robabilidad de mutación = 0.01, selección por torneo.

Lcasos de estudio, donde se utilizaron los siguientes parámetros: tamaño de la población = 40, elitismo, 2 puntos de cruza aleatorio, probp

Tabla 3.11Resultados del AG para los casos de estudio 1, 2 y 3 (con funciones de costo convexas).

Caso1 (7 unidades)

Generaciones = 300

Caso 2 (36 unidades)

Generaciones = 500

Caso 3 (3 unidades con pv) Generaciones = 400

Costo mínimo 490,719 4,449,024 8 241.1Costo máximo 503,999 4,455,664 8 500.2Costo promedio 496,491 4,452,219 8 327.4desv. Est. 3,915 2,454 89.4%error 1) 0.76 0.16 0.085%error_prom 1) 1.95 0.23 1.133tiempo usuario 0.45 3.1 0.26

1) Respecto al costo de la solución optima.

42

3.9 ALGOR O E T O H BR O El AGH se i a G co lgu s r as que son agregadas a la entrada y sa e la en n d mejorar la rapidez de convergencia y la calidad de la solución final. Estas heurísticas son:

- Algoritmo de Satisfacción de Restricciones (SR) para crear población inic

- Alg on uc n G SP G para crear pobla

- Algoritmo de BL para mejorar calidad de la solución y la rapidez de convergencia.

L valores que puede tomar cada u se cumpla en lo más mínimo con el BP. Se ha vi o que el AG uce rá men r en BP, pero luego emplea demasiadas iteraciones para llegar a un valor aceptable. En este capítulo se revisa el efecto r el po s in les factibles creadas a partir de algoritmos fc_G . Co egura que

s soluciones creadas cumplan con el BP, pero no se tiene en cuenta el costo de stas soluciones. Con fc_GRASP las soluciones cumplen con el BP y además se

s posibles de potencia para una unidad se consideran, en un rincipio, sus límites de potencia (dominio inicial). Pero aplicando SR se modifica ste dominio inicial al verificar que el valor de potencia, asignado de forma

Tabla 3.12 Datos para el ejemplo de SR. Pmín Pmáx demanda

ITM G NÉ IC Í ID

ntegr con el A y n a na heu ísticlida d l AG con int ció e

ial oritmo de fase de c str ció del RA (fc_ RASP)

ción inicial la

a población inicial con soluciones no factibles da una mayor diversidad en losnidad, a red

unque no pidast te el erro

de inicia AG con blacione iciade SR y RASP n el algoritmo de SR se as

laetoma en cuenta el costos de generación a través de una función miope.

3.9.1 Población inicial factible a partir de un algoritmo de satisfacción de restricciones. Como valorepealeatoria, permita seleccionar valores posteriores a las demás unidades. En el PDE las unidades participantes han sido seleccionadas previamente y deben despacharse con algún valor de potencia, por lo menos en su límite mínimo de potencia. Para entender mejor porque se deben restringir los valores de potencia en el proceso de asignación aleatoria de potencia, se muestra el siguiente ejemplo:

U1 35 210 U2 130 325 U3 125 315

400

43

Según los datos de la tabla 3.12, no es posible elegir un valor de potencia de 150 imera unidad, ya que la mínima potencia que podrían suministrar las

unidades sería de 255, dando un total de 455 y no se cumpliría con la tabla 3.13 se muestra el algoritmo de SR que permite

inio (i, dr)

1 . hasta i=n 0. Pn ← dr 1. fin

Piii

imax

NPsiNP

NPi

iii min

minminmin

em - demanda - número de unidades

para la protras 2demanda de 400. En la generar soluciones factibles. Tabla 3.13 Algoritmo para crear una solución factible por SR. 1. inicio 2. dr ← dem 3. i=1 4. Haz

ND uev5. i = n o_dom6. Pi ← aleat(NDi)

r - P7. dr ← d. i ← i +

i

8911 Nuevo_dominio(i, dr) 5a inicio 5b NPmaxi ← dr - Suma(Pmink), k>i 5c NPmini ← dr - Suma(Pmaxk), k>i 5d fin

PNPsiNP maxmaxmax

⎩⎨⎧ <

=NPcasootroimax

⎩⎨⎧ >

=casootroP

P imin

dnPi - potencia asignada a la unidad i, 1 <= i < n Di - dominio de la unidad i, determinado por los límites de potencia de cada unidad, Di = [Pmini, Pmaxi], 1 <= i < n dr - demanda restante NDi – Nuevo dominio de la unidad i por SR, NDi = [NPmini, NPmaxi], 1 <= i < n Siguiendo este algoritmo se tiene que (2) se asigna a dr el valor de la demanda, dr= 400. (3,5) Se calcula el nuevo dominio de la unidad 1. (5b) se obtiene el valor máximo NPmax que se puede asignar a la unidad 1: NPmax1 = dr – Pmin2 - Pmin3 = 400 – 130 – 125 = 145

44

(5c) el valor mínimo NPmin1 se determina como sigue: NPmin1 = dr – Pmax2 - Pmax3 = 400 – 325 – 315 = - 240 Como el valor NPmin1 es menor que el límite de potencia Pmin1, entonces este límite no se modifica, y los nuevos límites para la U1 son: Pmin1 ≤ P1 ≤ NPmax1 o sea, 35 ≤ P1 ≤ 145 (ND1) (6) ahora se puede escoger un valor permisible de potencia P1, entre 145 y 240

W. (7) epite el roceso para las siguientes unidades. (10) Finalmente, a la última unidad U3, se

or en un

s creadas con a) SR b) fc_GRASP. MW P1 P2 P3 P4 P5 P6 P7 aptitud costo [$]

Mp

Se modifica el valor de la demanda restante dr = 400 – P1, y se r

le asigna el valor de la demanda que falta por cubrir P = dr = Demanda – P1 – P2. De esta forma, se escoge un valor aleatorio para cada unidad que permite elegir valores de potencia para las unidades restantes.

3.9.2 Población inicial generada por fase de construcción del GRASP La fase de construcción del GRASP ofrece la ventaja de que en la formación de las soluciones factibles se considera también el costo de generación a través de una función miope, que revisa la conveniencia inmediata de agregar un elemento a la solución. El funcionamiento a detalle de este algoritmo se explica en el capítulo 5. La tabla 3.14 muestra poblaciones de 10 individuos creados por SR y fc_GRASP para el caso 1. En la tabla 3.15 se muestra un resumen de estos datos.

l costo promedio de las soluciones creadas por el fc_GRASP resultó mejE2.1% respecto el costo promedio de las soluciones del SR, pero la mejor solución del fc_GRASP lo fue en un 6.7%. Cuando se usa elitismo en el AG, esta mejora resulta de mayor importancia.

Tabla 3.14 Solucione

870 129 231 190 20 7 15 277 528 527,547 870 118 75 228 15 15 17 401 551 550,350 870 113 141 581 580,221 109 2614 26 441870 132 2 8 9,602 13 24 15 11 347 550 54 13 870 128 18 9 10 25 25 7 2,97 13 35 563 56 83 870 148 193 96 567 566,697 19 24 12 379870 149 70 13 16 12 552 551,113 210 399870 124 16 88 16 25 11 7 56 562,258 9 43 3870 73 19 34 11 8 26 8 5 537,407 0 1 42 38870 141 21 65 22 25 29 5 60 606,271 2 37 7

promedio 560 559,446 a)

45

P P6 P7 p to MW P1 2 P3 P4 P5 a titud cos [$] 870 79 231 138 7 7 14 394 509 508,108 870 158 22 92 27 23 22 3 579 578,255 5 1 22870 143 242 27 24 19 57 571,061 181 235 2870 160 20 48 27 26 30 4 59 594,139 7 2 17 5870 158 16 40 11 24 11 8 5 540,5688 2 25 41 870 141 204 10 24 9 5 530,107 214 268 31 870 50 138 191 21 12 23 436 548 547,794 870 40 216 189 8 7 8 401 495 494,590 870 102 136 188 21 11 20 390 549 548,069 870 136 150 225 18 15 30 296 566 564,824

promedio 549 547,752 b)

Tabla 3.15 Comparativo del costo de las soluciones creadas por SR y fc_GRASP. Caso 1 (7 Us).

SR [$]

fc_GRASP [$] % mejora

minimo 527,547 494,590 6.7 máximo 606,271 594,139 2.0 promedio 559,446 547,752 2.1

3.9.3 Adición de Búsqueda local al AG

igir la búsqueda hacia zonas prometedoras donde el lgoritmo de BL agiliza la convergencia hacia una solución de mejor calidad. El lgoritmo de BL se basa en la generación de vecindades que se describió en la

e la aptitud de los individuos, entonces se busca una solución con rror pequeño en BP, según la precisión que se requiera. En caso de no encontrar

un individuo en l tiva el AG para producir una generación s, has cumpl

o a el s ódi AG

El AG se encarga de diraasección 2.3. Después de un número de generaciones iniciales (AGini) el AG ha reducido de forma notable

a población que cumpla con este criterio, se ac má ta ir con el criterio de BP. El error en BP

es asignad a una de las unid des U con capacidad suficiente. En la tabla 3.16 selse m

uestra eudoc go del H.

46

Tabla 3.16 Algoritmo Genético Híbrido (AGH). BEGIN AGH Generar población inicial n = AGini DO FOR i = 1 TO n DO Evaluar población Seleccionar padres para nueva población

Cruzar padres para generar hijos Mutar END FOR n =

PU mo de H

hijos (se tiene una nueva población)

Buscar individuo con menor DP 1

ILE (DP > 0.1) WH PUsel sel + DP Algorit BL END AG En la tabla 3.17 se muestran los valores de AGini para cada caso de estudio a

del AG respecto a la aptitud de las soluciones disminuye a partir de la eneración 150; respecto al BP, se estabiliza hasta la generación 450. Por eso ara este caso se i.

Tabla 3 io ia l AGH para a tudio.

AG

partir del cuál se puede empezar la búsqueda local. Estos valores se obtuvieron de las gráficas 3.10, 3.11 y 3.16. Para el caso 2 de 36 unidades se observa que el desempeñogp probaron valores de 150, 300 y 500 para el AGin

.17 Generac nes inic les n de cada c so de es ini

caso 1 75 caso 2 , 3 150 00, 500c 150 aso 3

La figura 3.17 muestra el desempeño del AGH aplicado al caso 1 con poblaciones

iales generadas aleato con el fc_GRASP.. Las ráficas muestran el promedio de 5 pruebas, no se usó elitismo para poder bservar la mejora de los individuos en cada generación. Después de la

inicg

riamente, con el algoritmo SR y

ogeneración 75 se muestran las soluciones finales aplicando BL, con k0 (vecindades generadas) = 100.

47

485

495

505

515

525

535

20 25 30 BL

núm. generaciones

aptit

ud d

el m

ejor

indi

vi

545

555du

o

0 5 10 15 35 40 45 50 55 60 65 70 75

no factibles factibles (SR) factibles (fc_grasp)

8.0

9.0

]

0.0

0 5 0

B 1.0

2.0

3.0

4.0

5.0

e po

tenc

i

6.0

7.0

1 35 40 7

neraciones

alan

ce d

a, B

P [M

W

15 20 25 30

núm. ge

45 50 55 60 65 70 5

no factibles factibles (SR) factibles (fc_grasp)

Figura 3.17 Convergenc con diferentes

n las gráficas anteriores que con el algoritmo de BL las soluciones del AGH son independientes de la calidad de los individuos de la población inicial. También se observa que el desempeño del AG fue menor cuando se utilizaron soluciones de buena calidad al inicio, porque el porcentaje de mejora fue mucho menor que cuando se utilizaron soluciones no factibles. La tabla 3.18 registra los porcentajes de mejora de la aptitud de los individuos al inicio y después de 75 y 150 generaciones. Las soluciones proporcionadas por el fc_GRASP fueron de tan buena calidad que el AG difícilmente las pudo mejorar, después de 150 generaciones la mejora del mejor individuo fue de sólo 0.1%. Sin embargo, el trabajo del AG se puede observar si se revisan las aptitudes promedio de cada generación, en este caso se tuvo un 5.5% de mejora. Se puede decir que la secuencias (fc_GRASP + AG + BL) da resultados similares a una secuencia (fc_GRASP + BL = GRASP). El AG tuvo el mejor desempeño cuando se utilizó en su forma más simple, sin la adición de operaciones que depuren las soluciones aleatorias para asegurar la factibilidad. Los porcentajes de mejoría fueron de 8.5% para el mejor individuo y de 38.6% para toda la generación. Tabla 3.18 Comparativo de aptitudes después de 75 y 150 generaciones, para el AG con diferentes

tipos de población inicial, caso 1.

Mejor individuo aptitud inicial

a) aptitud después de

75 generaciones

b) aptitud después de

150 generaciones

a) mejora aptitud [%]

b) mejora aptitud [%]

ia del AGH poblaciones iniciales, caso 1. Se observa e

Soluciones factibles por SR 521 510 503 1.9 3.4 Soluciones factibles por fc_GRASP 498 499 498 -0.2 0.1 Soluciones no factibles 547 500 500 8.5 8.6

48

Promedio generación aptitud inicial

a) aptitud después de

75 generaciones

b) aptitud después de

150 generaciones

a) mejora aptitud [%]

b) mejora aptitud [%]

Soluciones factibles por SR 557 541 531 2.8 4.7

Soluciones factibles por fc_GRASP 553 522 523 5.7 5.5

Soluciones no factibles 847 520 520 38.6 38.6 La figura 3.18 muestra el desempeño del AG (sin BL) para el caso 3 con población

icial factible y no factible. El resultado fue similar a lo observado para el caso 1: o hay dependencia en la convergencia por la calidad de las soluciones de la oblación inicial, por lo tanto se usará el AGH en su forma simple, con población

ial compuesta por soluciones no factibles, generadas de forma aleatoria.

innpinic

8,200

8,300

8,400

8,500

8,600

el m

ejor

indi

vidu

o

8,700

1 59 117

175

233

291

349

407

465

523

581

639

697

755

813

871

929

987

aptit

ud d

generaciones

factibles no factibles

Figura 3.18 Desempeño del AG con población inicial de soluciones factibles y no factibles para el caso 3 (DEPV de 3 unidades). La intensidad de la búsqueda local se controla con el parámetro k0. Se hicieron pruebas con diferentes valores de este parámetro para obtener un valor mínimo aceptable para los casos 1, 2 y 3. En la tabla 3.19, 3.20 y 3.21 se muestran los

sultados de estas pruebare s. Para el caso 1 los mejores resultados se obtuvieron con k0=500.

Tabla 3.19 Ajuste del parámetro k0 para el caso 1 (7 U’s). AGini= 75, k0= 100 200 300 400 500 750

Costo mínimo 487,101.360 487,030.999 487,027.493 487,027.493 487,027.493 487,027.493 Costo máximo 490,405 487,717 487,166 487,105 487,073 487,290 Costo promedio 488,052 487,182 487,079 487,064 487,061 487,086 desv. Est. 1,195 213 45 20 15 73 %error 1) 0.017 0.003 0.002 0.002 0.002 0.002 %error prom 1) 0.21 0.03 0.01 0.01 0.01 0.01 tiempo usuario 0.09 0.11 0.11 0.11 0.09 0.09

1) Respecto al costo de la solución óptima

49

Para el caso 2 se probaron diferentes valores de AGini debido a que en las pruebas del AG se alcanzó el máximo desempeño en aptitud a partir de la generación 150, pero fue un poco inestable en cuanto a BP, estabilizándose hasta la generación 450. Los mejores resultados se obtuvieron con AGini = 500 y k0= 50. Aunque con k0 = 500 se tuvieron resultados similares a k0=500, se prefirió el

n del costo promedio y la desviación estándar de s resultados.

arámetro k0 para el caso 2 (36 U’s). 300 500 750

7primero por la mejor combinaciólo

Tabla 3.20 Ajuste del pAGini = 150

k0 = 500 750 500 750 500 750 500 750 Costo mínimo 4,448,120 4,446,023 4,445,094 4,444,916 4,443,826 4,443,442 4,443,979 4,443,751Costo máximo 4,455,488 4,454,994 4,452,809 4,452,706 4,447,857 4,447,401 4,452,644 4,452,312Costo promedio 4,451,212 4,450,385 4,448,034 4,447,578 4,446,233 4,445,964 4,446,640 4,446,053desv. Est. 2,042 2,358 2,446 2,413 1,240 1,284 2,809 2,476%error 1) 0.137 0.090 0.069 0.065 0.040 0.032 0.044 0.039%error prom 1) 0.21 0.19 0.14 0.12 0.09 0.09 0.10 0.09tiempo usuario 1.12 1.03 2.06 2.13 3.37 3.19 4.76 4.75

1) Respecto al costo de la solución óptima Los mejores resultados para el caso 3 fueron con k0=500, según se observa en la tabla 3.21 por la mejor combinación de menor costo promedio y desviación

stándar.

o k0 para el caso 3 (3 U’s). 0 300 400 500

e

Tabla 3.21 Ajuste del parámetrk = 100 200

Costo mínimo 8,234.4 8,234.4 8,234.4 8,234.3 8,234.1 Costo máximo 8,356.0 8,356.0 8,355.6 8,252.3 8,252.3 Costoprome

dio 8,265.6 8,256.7 8,253.3 8,240.4 8,239.6

desv. Est. 35.8 36.2 36.7 7.0 7.3 %error 1) 0.004 0.004 0.004 0.002 0.000 %error prom 1) 0.38 0.28 0.23 0.08 0.07 tiempo usuario 0.10 0.10 0.10 0.10 0.10

1) Respecto al costo de la mejor solución encontrada

La tabla 3.22 muestra los resultados de la aplicación del AGH a cada uno de los casos de estudio, donde se utilizaron los siguientes parámetros: tamaño de la población = 40, elitismo, dos puntos de cruza aleatorio, probabilidad de cruza = 0.8, probabilidad de mutación = 0.01, selección por torneo y los valores de AGini y k0 obtenidos en párrafos anteriores.

50

3.10 Resumen de resultados del AGH (DE con funciones convexas).

H para los casos de estudio 1, 2 y 3 (con funciones de costo convexas).

so 3 s con pv)

AGini = 150, k0 = 500

Tabla 3.22 Resultados del AG

(7 unidades)

AGini = 75, k

Caso1 Caso 2 dad

Ca(3 unidade

0 = 500 (36 uni es)

AGini = 500, k0 = 750 Costo mínimo 487, 027 4, 443, 442 8, 234Costo máximo 487, 073 4, 447, 401 8, 252Costo promedio 487, 061 4, 445, 964 8, 240desv. Est. 15.2 1, 284.2 7.3%error 0.002 0.03 0.00%error_prom 0.01 0.09 0.07tiempo usuario 0.11 3.2 0.10

51

ECOCIDO SIMULADO

.1 Introducción

ceptación de soluciones está gobernada por un parámetro denominado oluciones que mejoran el costo actual siempre son aceptadas

aquellas que lo empeoran también pueden ser aceptadas con cierta a

es eores también disminuye. Hacia el final de la ejecución sólo las mejores oluciones son aceptadas.

encilla, prácticamente sólo se debe

abajar con el algoritmo que genera la solución inicial factible, que debe cumplir ncias asignadas a los generadores deben ara la consideración de zonas muertas, el

rador de soluciones factibles y el algoritmo de búsqueda en eatorios que estén en la región

ones discontinuas no tienen entación de una función que

Capítulo 4. IMPLEMENTACIÓN DEL ALGORITMO DER

4 El ARS es un algoritmo de búsqueda de la mejor solución y se basa en la analogía del comportamiento de sistemas termodinámicos simples. En el ARS, la a“Temperatura''. Las syprobabilidad, que será alta al inicio de la búsqueda. A medida que la búsquedprogresa la temperatura disminuye y la probabilidad de aceptación de solucionps

La implementación de este algoritmo es muy strcon el BP y con el hecho de que las potestar dentro de sus límites operativos. Pe

algoritmo genevecindades deberán desechar los números alprohibida. Las funciones no convexas y las funci

la implemninguna consideración especial, basta convalué cada solución generada. e

52

El programa de recocido simulado aplicado al PDE consta de tres módulos, el primero desp ncia propia del ARS, el segundo a la solución inici l t vecindades, implementa la búsqued .2 Descripción del programa

0, P20, …, Pn0)

ímites de potDemanda Salida: solución mejorada (P1 , P2 , …, Pn ) Despacho_RS es el p dulos sol_ini y vecindades ara implementar el ARS.

Módulos:

4.3 So

Módulo Sol_inEntrada: Us, U _mu a m P xi em nd 1 Salida: Solución inicial S0 = P10 + P30 = Demanda

acho_RS es el programa principal con la secue sol_ini, gener al y e ercero, a local.

4 Entrada:

olución inicial (P1SNúmero de unidades, Us Unidades que operan en zona muerta Uzmi

ango de zona muerta, ini_zm, fin_zm RL encia, Pmini, Pmaxi,

s s s

rograma principal y utiliza los móp

- Despacho_RS: Implementa el ARS, integrado los módulos anteriores. - Sol_ini: Genera solución inicial factible S0 = P10 + P20 +… Pn0 = Demanda - Vecindades: Genera soluciones vecinas.

lución inicial

i. zmi, zona ert i, P ini, ma , D a a ≤ i ≤ Us

+ P20 El algoritmo utilizado es el de SR que se describió en la sección 3.7.1. 4.3.1 Zona muerta Antes de asignar las potencias de cada unidad, se decide en forma aleatoria si la unidad con zona muerta operará abajo o arriba de esta zona. La decisión es simple, se genera un valor aleatorio entre 0 y 1. Si el valor está entre 0 y 0.5, entonces la unidad opera por debajo de la zona muerta y se modifica temporalmente su potencia máxima Pmax, igualándose al inicio de la zona muerta, Pmax = Pzmini, En caso contrario, la unidad opera arriba de la zona muerta y el parámetro que se redefine temporalmente es la potencia mínima: Pmin = Pzmfin.

53

4.4 Vecindades

Módulo busqueda_local. n i i i i

<xsiajax es una va La cantidad de mueve d ria y limitada por las potencias máximas y idades. El movimiento de la unidad seleccionada en forma aleatoria debe bier las dem nidades de tal manera que no se modifique el valor d anda inistrad movimiento de todas las unidad leatorio a excepción de la última unidad, la cuál tendrá que absorber la difer ue falte por cubri

Tabla 4.1 Datos del ejemplo para el cálculo de una solución vecina.

trada: Us, Uzm , zona_muerta , Pmin , Pmax , Demanda 1 ≤ i ≤ Us ESalida: Solución vecina Sv = P1v + P2v +…+ PUsv = Demanda Las vecindades a una solución dada, se determinan al incrementar o disminuir la potencia de una unidad seleccionada aleatoriamente. El movimiento hacia arriba o hacia abajo también es aleatorio:

5.0≥xsisube

b 5.0riable aleatoria entre 0 y 1.

MW que se la unida es aleato está mínimas de las un

ser cu to por ás ue dem sum o. El

es es aencia q r.

Ejemplo 4.1:

Pmin Pmax P1 35 210 P2 130 325 P3 125 315

Demanda = 400

Solución inicial: P1= 40 P2= 160 P3=200

Movimiento seleccionado: subir (aleatorio) Unidad seleccionada: 2 (aleatorio) Los rangos permisibles de movimiento para cada unidad se muestran en la tabla 4.2.

54

Tabla 4.2 Rangos permisibles de movimiento a partir de la solución inicial del ejemplo 4.1. baja (máx) sube (máx) P1 5 170 P2 30 165 P3 75 115

MW a mover: 25 (aleatorio) Para P1 se selecciona un número aleatorio entre 0 y 5 (rango permisible hacia abajo), digamos 3, P1= 40-3= 37 demanda restante : 25-3=22 La demanda restante es proporcionado por la unidad 3: P3=200-22= 178 P2=160+25= 185 Ede pote solución inicial: 0, 16

185)

m nto sible porque a los s de ncia, e s so o de imient

d.

eración d unidad luc

l movimiento es exitoso porque se cumple con la demanda y con los rangos disponibles ncia de cada unidad.

(4 0,200) solución vecina: (37,178, Cuando un ovimie no es permi rebas límite pote ntoncees no exitoso y se sigue un proce aleatori mov os que sean permisibles para encontrar la vecinda 4.4.1 Zona muerta Cuando existe zona muerta en una unidad, la solución vecina respeta la zona de op e la en la so ión actual, arriba o debajo de la zona muerta.

4.4 Ajuste de los parámetros de ARS Los parámetros de control del ARS son: T: temperatura k0: número de aceptaciones por cada nivel de T criterio de paro (un valor suficientemente bajo de T) alfa: factor de disminución de temperatura

55

Los parámetros utilizados por defecto son los de la tabla 4.3.

Tabla 4.3 Parámetros utilizados por defecto para el ARS. Parám

etro valor Criterio de paro T = 10 Factor ucióntempera

, de dismin por 0.9tura, alfa

0.95

.5.1 Temperatura

a

4

l criterio de Metrópolis del ARS utiliza la función de distribución de Boltzman parEaceptar una nueva solución. La tabla 4.4 muestra los elementos de la función.

Tabla 4.4 Criterio de Metrópolis para aceptación de una solución.

si r< TjFiF

e)()(( −

se acepta la solución j, que tiene un costo mayor al de la solución actual i

Fc(i): Función de costo de la mejor solución

r es un número alea n el intervalo [0,1

Fc(j): Función de costo de la solución actual torio e ]

El valor de T d ta t ia arable con r cuyo rango es El v tend a 1 btie and funciones de costo de las s om das igua l va se o e cuando T ∞. Una buena opción es establecer el valor de T de acuerdo con la máxima diferencia en costo mdc dentro del espacio de soluciones. Este valor se obtiene de la dife . La tabla 4.5 muestra la máxima diferencia en costo m ara e so 1 unidades.

Tab a ia e o e s.

1 3 U $

érmino eebe ser l que el xponenc l pueda se comp

[0, 1]. alor iente se o ne cu o lasoluciones c para son les. E lor 0 btien

rencia en costo de las unidades operando a potencia máxima y mínimadc p l ca de 7

la 4.5 Máxim diferenc en costo mdc para l caso 1 c n funcion s convexa U U2 U U4 5 U6 U7 F [ ] Pmáx [MW 248 26 48 7,816] 160 248 27 30 9 76 Pmín [MW] 40 62 7 122 71,858 62 7 8 2 mdc: 495,958

En la figur ión de la función de Boltzman para valores de T e del rango [0,1] y la posibilid e que ace so andes diferencias en costo es menor respecto a las otras c d na solución con una diferencia de 300 mil p l e ual, sería aceptada con una probabilidad con d c a bilidad de 0.74 con T=mdc*2. El número total de vecindades que se generan depende sólo de la temperatura inicial T, si el factor de disminución de temperatura alfa, el número de aceptaciones k0 y el criterio de paro son fijos. Al disminuir T, se revisa un número

a 4.1 se muestra la evaluacreferidos a la mdc del caso 1. Con T= mdc/4 se cubre la mayor part

ad d se pten luciones con grasigna iones e T. U

pesos, res ecto a costo d la solución actde 0.1 T= m c/4, y on un proba

56

menor de soluciones e er m s variedad en ellas. Por lo tanto, se ebe buscar un balance adecuado con el valor de T que permita variedad en las

, además d ten enodsoluciones y generar un número suficiente de soluciones.

0.0

1.0

0.1

0.2

0.6

0.7

0.9

0 50 100 150 200 250 300 350 400 450 500

diferencia en costo [miles $]

0.3

0.4

0.5

0.8

T= mdc*2T= mdcT= mdc/2T= mdc/4

Figura 4.1 Evaluación de la función de Boltzman con valores de T referidos a la mdc del caso 1

Se hicieron pruebas con diferentes asignaciones de T para los casos 1,2 y 3. Los valores de mdc fueron ajustados a cifras cerradas para su mejor presentación. En la tabla 4.6 se muestran los ajustes de mdc y los valores utilizados para cada caso. También se muestran los criterios de paro utilizados y que se refieren a un valor de temperatura de 10 unidades, que se consideró adecuado para el caso 1. Se utilizó un divisor de costo para su mejor presentación en las gráficas. Los valores afectados por el divisor de costo aparecen subrayados.

Tabla 4.6 Valores de mdc y criterios de paro para los casos de estudio 1,2 y 3. caso 1 caso 2 caso 3 Costo máximo 767,816 5,478,376 12,521 Costo mínimo 271,858 3,450,115 2,972 mdc 500,000 2,000,000 10,000 divisor costo 1,000 10,000 100 mdc 500 200 100 mdc *2 1000 400 500 mdc /2 250 100 50 mdc / 4 125 50 25 criterio de paro, T> 10/1000) 10/10000) 10/10)

En las figuras 4.2, 4.3 y 4.4 se muestra el desempeño del ARS aplicado a los casos 1,2 y 3, con los valores de T de la tabla 4.6. En las primeras fases de enfriamiento se explora un espacio de solución más amplio, donde se permiten

57

peores soluciones con mayor probabilidad. En las últimas fases casi no se ermiten soluciones de calidad inferior a la solución en curso. p

485

505

525

545

565

585

605

0

1000

2000

3000

4000

5000

6000

7000

8000

9000

1000

0

número solución aceptada

cost

o

T=mdc T=mdc*2 T=mdc/2 T=mdc/4

Fig. 4.2 Desempeño del ARS para diferentes valores de T, caso 1 (7 U’s).

447

449

465

451

453

455457

459461

cost

o

463

1 1

número solución aceptada

0

1000

2000

3000

4000

5000

6000

7000

8000

9000

0000

1000

T=mdc*2 T=mdc T=mdc/2 T=mdc/4 Fig. 4.3 Desempeño del ARS para diferentes valores de T, caso 2 (36 U’s).

820

0

500

1000

1500

2000

2500

3000

3500

4000

4500

830

840

850

860

870

880

aceptada

cost

o

número solución

T=mdc*2 T=mdc T=mdc/2 T=mdc/4 Fig. 4.4 Desempeño del ARS para diferentes valores de T, caso 3 (3 U’s).

58

Tabla 4.7 Resultados para diferentes valores de T. Resaltados los valores de referencia para el cálculo de los porcentajes. El valor mínimo y el valor promedio son de 10 pruebas.

T mínimo promed

io desv. Est. soluciones

% incremento soluciones

% mejora (mínimo)

% mejora (promedio)

caso1 mdc*2 487.024 487.063 0.020 11000 22.2 0.000 0.006 mdc 487.024 487.036 0.015 10300 14.4 mdc/2 487.028 487.042 0.018 9700 7.8 0.001 0.001 mdc/4 487.024 487.047 0.020 9000 0.000 0.002 caso 2 mdc*2 446.477 447.243 0.390 25200 19.4 0.050 0.086 mdc 447 1. 04 447.510 0.355 23800 12.8 0.191 0.146 mdc/2 446.252 447.288 0.566 22500 6.6 0.096 mdc/4 446.433 446.859 0.326 21100 0.041 caso 3 mdc*2 823.430 824.585 0.680 5100 64.5 0.002 0.066 mdc 823.412 824.335 0.911 4400 41.9 0.036 mdc/2 824.215 824.690 0.609 3800 22.6 0.098 0.079 mdc/4 823.447 824.039 0.754 3100 0.004

u o diferentes el uso de

ualquiera de los valores propuestos de T

En la tabla 4.7 se muestran los resultados de diez pr ebas usandalores de T, referidos al mdc. Para el caso 1 parece indiferentev

c , respecto de la solución final. Aunque se bservan pequeñas ventajas al utilizar To =mdc (500) por tener menor variabilidad

sos 2 y 3 el costo mínimo, el mejor promedio y la queña no coinciden para un mismo valor de T. Sin

es deseable escoger el valor de T donde se tenga la mejor combinación ará T

en los costos. Para los cadesviación estándar más peembargo, de costo promedio y variabilidad. Así que para el caso 2 se utiliz =mdc/4 (50) y para el caso 3, T=mdc/4 (25). En la tabla 4.8 se resumen los parámetros del ARS para cada caso de estudio.

Tabla 4.8 Parámetros del ARS para cada caso de estudio.

T T alfa caso 1 (7 U’s) mdc = 500 000 500 0.90

caso 3 (3 U’s) mdc / 4 = 2 500 25 0.90

.2 A local.

as p uebas realizadas ita va res de k0 con los

ore resu ejor costo promedio y su menor desviación

caso 2 (36 U’s) mdc / 4 = 500 000 50 0.95

4.5 juste de k0 en la búsqueda Las tablas 4.9, 4.10 y 4.11 muestran los resultados de l rpara diferentes valores de k0. Se destacan en negr los lomej s ltados, referentes a el mestándar.

59

Tabla 4.9 Ajuste de la búsqueda local a través del parámetro k0 para caso 1 (7 U’s). 25 50 75 100 200 k0

Costo mínimo 487,022.3 487,026.2 487,022.2 487,024.7 487,027.2 Costo máximo 487,072.4 487,082 487,101.5 487,077 487,095.0

Costopromed

io 487,050.6 487,044.3 487,055.3 487,047.1 487,060.0

desv. Est. 21.8 18.2 27.1 20.5 22.9 %error 1) 0.001 0.002 0.001 0.001 0.002

%error prom 2) 0.007 0.005 0.008 0.006 0.009 tiempo usuario 0.01 0.03 0.05 0.12 0.14

T búsqueda local a través del parámetro k0 para caso 2 (36 U’s).

500 600 700 800 abla 4.10 Ajuste de la

k0 100 200 Costo mínimo 4,461,458 4,458,141 4,456,795 4,455,173 4,456,227 4,456,305 Costo máximo 4,473,159 4,463,719 4,459,826 4,459,448 4,461,707 4,458,577

Costo promedio 4,466,278 4,461,620 4,458,160 4,457,871 4,458,139 4,457,151 desv. Est. 3,916 1,620 899 1,252 1,644 780 %error 0.44 0.36 0.33 0.30 0.32 0.32 %error prom 0.55 0.44 0.36 0.36 0.36 0.34

tiempo usuario 0.5 1.0 2.5 3.0 3.5 4.0

Tabla 4.11 Ajuste de la búsqueda local a través de parámetro k0 para caso 3 (3 U’s).

k0 = 50 100 150 200 Costo mínimo 8,234.6 8,234.1 8,234.1 8,234.3 Costo máximo 8,286.1 8,257.0 8,275.4 8,250.4

Costo promedio 8,250.2 8,243.7 8,247.2 8,242.3 desv. Est. 18.0 6.9 12.8 3.9 %error 1) 0.006 0.001 0.000 0.003

%error prom 1) 0.20 0.12 0.16 0.10 tiempo usuario 0.00 0.01 0.02 0.03

4.6 Resumen de resultados del ARS (DE con funciones convexas). Finalmente, la tabla 4.12 muestra una tabla resumen con los resultados para cada caso de acuerdo con el valor elegido de k0.

Tabla 4.12 Resultados del ARS para los casos de estudio 1, 2 y 3 (con funciones de costo convexas).

Caso1 (7 U’s)

T= 500 000, k0 = 50

Caso 2 (36 U’s)

T= 500 000, k0 = 800

Caso 3 (3 U’s con pv)

T= 2 500, k0 = 200 Costo mínimo 487,026.2 4,456,305 8,234.3Costo máximo 487,082 4,458,577 8,250.4Costo promedio 487,044.3 4,457,151 8,242.3desv. Est. 18.2 780 3.9%error 0.002 0.32 0.003%error_prom 0.005 0.34 0.10tiempo usuario 0.03 4.0 0.03

60

L GRASP

La uy natural, debido a que la fase constructora guía la forma de construir una solución factible, y asegura que

t diver d e cada jecución. La fase de búsqueda local fue ácticame ada d RS

El método GLa fase consde búsqueda local y la mejor solución es guardada dentro del proceso iterativo. El algorit

Tabla 5.1 Algoritmo general GRASP para el DE. f* for máx c uctora(g ,x) bú ueda loc x) < then f* )

x* x end if

or regresar

onde

x* es la mejor solució ontr α es un factor [0,1], q tabl el gra e ale toriedad o miope o

Capítulo 5. IMPLEMENTACIÓN DE

5.1 Introducción

implementación del GRASP para el DE queda m

és a pued tenera sida n epr nte tom el A .

RASP consta de una fase constructora y una fase de búsqueda local. tructora crea una solución factible, que es mejorada por el algoritmo

mo utilizado se muestra en la tabla 5.1.

← ∞ i ≤ i do

fase onstr (.), α x ← sq al(x)

if f( f* ← f(x←

end f

x* d

imáx es el número máximo de iteraciones. g(.) es la función miope que evalúa la incorporación de cada elemento x es el conjunto solución, que contiene las potencias asignadas a las N unidades f(x) es el costo de la solución x f* es el c a me soluci encontrada osto de l jor

n enón adac

ue es ece do d a s del alg ritmo

61

5.2 Descripción del programa

l cho_g sp es l y utiliza losse de co ión y e ú ed cal.

Entrada: Número de it

úmero de un s que operan en zona muerta, Uzmi an e zona muerta, ini_zm, fin_zm

Límites d pote P axi DemandFactor de aleatoriedad-miopía, α 0 ≤ α ≤ 1 Salida: solución (P1s, P2s, …, PUss), P1s + P2s+ …+ PUss = demanda

.3 Fase co tructor

ntrada: Datos de unidades, Us, Uzmi, ini_zm, fin_zm, Pmini, Pmaxi Demanda

Sal x ∈P P representa el espacio de soluciones factibles La solución en la fase constructora se genera bajo el siguiente algoritmo:

Tabla 5.2 Algoritmo GRASP (fase constru a) p el D inici x =

. m_resto ← Demanda icializa e tos C

4. mi tras 1 do5. calcula Nuevos límites NPmini, NPmaxi | i∈ C 6. pi ← io(NPmini, NPmaxi) | i ∈ C 7. calcula fmiop ∈ C 8. f

E programa despa ra el programa principasqu

módulos de la fa nstrucc l de b a lo

eraciones, Nitr nidades, Us N

U idadego dR

e ncia, mini, Pma

5 ns a E

Número de vecindades k0ida: Una solución factible

ctor ara E. 0. o 12

. {}; deIn3. r lista d

|C| ≠ candida en

aleator

e(pi) | i ← ín{ fmio | i ∈ C }

9. f+ ← áx{ fm i) | i ∈ C } 10. RCL { p ∈ C iope(pi) ≤ f

m pe(pi) m iope(p← | fm + α( f+ – f) }

62

11. selección aleatoria de p de RCL 12. x ← x ∪ {p}

. C ← C – {p}

. d _resto ← _resto – p

. end mientras 6. p {C} ← dem_resto

. fin

on datos solución factible to en la lista de candidatos

1314 em dem15117 D de

cubrir todas las unidades Demanda: es la demanda que deben C: lista de candidatos

RCL: lista restrictiva de candix: conjunto solución pi: elemento i de la

p {c} : ultimo elemen

Descripción del algoritmo.

El algoritmo forma una soluci n factible x = {p1, p2, … pi, …,pn}. Al principio, el conjunto solución x está vacío (1), la variable dem_resto inicia con el valor de demanda que deben cubrir las N unidades y reduce su valor conforme se asignan potencias a cada elemento de la solución. La lista de candidatos inicial C está integrada por todas las unidades C = { U1, U2, …, Ui, …, Un}. Posteriormente, a cada unidad se le asigna una potencia aleatoria (6) dentro de los dominios restringidos,

lculados (5) por un algoritmo de satisfacción de restricciones.

aplicación de este algoritmo permite asig s a una unidad para que ego, en eta s poste s, sea posible ción de potencias a las nidades restantes. La función miope (7) es la función de costo de generación que alúa a cada generador de acuerdo con su potencia asignada de forma aleatoria. lista restri tiva RCL ontend á a la unida es con menor costo que estén

entro del rango determinado en 10. El elemento que se agrega a la solución se scoge, de forma aleatoria, de la lista RCL (11). Luego se actualizan el conjunto

sol cada cicl hasta que la lista de candidatos contenga un sólo elemento. A esta última unidad se le asigna la demanda restante dem_resto.

je inuac , se lica el algo o G ASP ra aso de estudio de 7 uni térmica ra ncon r un oluc fac le.

ó

ca

La na ela a a

r valorlu pa riore signuevLa c c r s dde

ución (12), la lista de candidatos (13) y la demanda por cubrir (14). Eno se agrega un elemento a la solución

E mplo 5. A cont1 ións,

ap e

ritm R pa el c2, dades pa tra a s ión tib

63

Tabla 5.3 Datos del ejemplo 5.1. Aplicación del GRASP. demanda 804 MW U1 U2 U3 U4 U5 U6 U7 Pmax [MW] 248 248 27 26 30 489 Pmin [MW] 40 62 62 7 7 8 122 coef. A 1.28 0.56 0.56 24.92 19.45 21.16 0.029 coef 3 158.5 158.5 1154 1204 1190 467.7 coef. 2 33830 33830 13330 16680 16660 6957

na so fac ible es cual ier asignación de potencias a las N unidades, que m el BP y con los límites de generación de cada una de ellas. El costo de n tot l no es precisamente el más bara

plicación del algoritmo de la fase constructora: 1. x = {} 2. dem_resto = 804 3. se inicializa conjunto C, P6, P7} 4. |C| = 7

30 489 62 62 7 7 8 122

n, NPmax, son iguales a los originales, esto quiere decir er asignación de potencias dentro de los límites originales, hace posible ón de potencias de las demás unidades para cubrir la demanda.

2 oef. b (P) + c . c) / $/ M

eat W]

fmiope [$/MW]

P1 130 710 P2 95 3

2 2,351 2 2,392 2

8, 9

En RCL

f-= 435 fmiope(P) ≤ f+= 2,859 1,647

. Se observa c el valo ermina el grado d leatoriedad, ya que un valor de 0, hará al algo totalmente dependiente de la evaluaci a función miope, y se la RCL

stará integrada sol mente por el elemento con la mejor evaluación. Por otra parte con α=1, se rmite que inte RCL todos lo n s de C

CL = { 1 2 3 7 130 95 247 247

160

. B 68.0 C 2770

Ucu

lución t qupla coneraciónge a to.

A

C = {P1, P2, P3, P4, P5,

5. Nuevos límites U6 U7 U1 U2 U3 U4 U5

160 248 248 27 26NPmáx NPmín 40

Los nuevos límites NPmique cualquiuna asignaci

6, 7. fmiope(P) = (coef. a (P) + c oef P [ W]

P al[M

568 435

2,859PP

247 9 4

P5 6 P6 4 P7 47 503

10 omo r de α det e miopía o aα= ritmo

aón de l

epe gren a la , s eleme to . R P P P P }

64

11 Se selecciona de forma aleatoria un elemento de RCL, digamos el elemento 2 {(P2 = 95)}, C = {P1, P3, P4, P5, P6, P7}, dem-resto = 804 – 95 = 709

Siguiente ciclo, |C| = 6

. Nuevos límites U1 U2 U3 U4 U5 U6 U7 NPmáx 160 248 27 26 30 489 NPmín 40 62 7 7 8 218

El límite inferior de U7 ha sido modificado. Una asignación de potencia inferior a rmitiría cubrir la demanda restante de 709, aún asignando a U1,

U3, U4, U5, U6 con sus valores máximos

leat

[MW] fmiope [$/MW]

P1 104 720

P4 20 2,319

2,570 1,535

05 Siguiente ciclo, |C| = 5 5. Nuevos límites

U4 U5 U6 U7 27 26 30 489

NPmín 62 7 7 8 274

12, 13, 14. x=

5

218 para U7, no pe

6, 7.

P a

P2 P3 64 723

P5 21 2,407 P6 16 2,570 P7 295 500

8, 9, 10.

En RCL f-= 500 fmiope(P) ≤ f+=

RCL = { P1 P3 P7 } 104 64 295

11 Se selecciona de forma aleatoria un elemento de RCL, digamos el elemento 1 12. x= {(P2 = 95), (P1 = 104)} 13. C = {P3, P4, P5, P6, P7} 14. dem_resto = 709 – 104 = 6

U1 U2 U3 NPmáx 248

6, 7.

P aleat [MW]

fmiope [$/MW]

P1 P2 P3 99 556 P4 19 2,329 P5 24 2,366 P6 15 2,618 P7 287 500

65

8, 9, 10.

En RCL f-= 500 fmiope(P) ≤

f+= 2,618 1,559

11 Se selecciona de forma aleatoria un elemento de RCL, digamos el elemento 1

14. dem_resto = 605 – 99 = 506 Siguiente ciclo, | 5. Nuevos límites

U NPmáx 2 30 484 NPmín 423

6, 7.

P aleat [MW

P1 P2 P3

13. C = {P4, P5, P6} 14. dem_resto = 506 – 471 = 35

Siguiente ciclo, |C| = 3 5. Nuevos límites

U1 U2 U3 U4 U5 U6 U7 NPmáx 20 20 21 NPmín 7 7 8

RCL = { P3 P7 } 99 287

12. x= {(P2 = 95), (P1 = 104), (P3 = 99)} 13. C = {P4, P5, P6, P7}

C| = 4

U1 U2

U3 U4

2756

U6 U7

7 7 8

] fmiope [$/MW]

P4 21 2,312 P5 19 2,451 P6 27 2,378 P7 471 496

8, 9, 10.

En RCL f-= 496 fmiope(P) ≤ f+= 2,451 1,474 RCL = { P7 } 471

11 Se selecciona de forma aleatoria un elemento de RCL, no queda más opción que 1 12. x= {(P2 = 95), (P1 = 104), (P3 = 99), (P7 = 471)}

66

6, 7.

P aleat [MW]

fmiope [$/MW]

P1 P2 P3 P4 20 2,319 P5 9 3,232 P6 19 2,469 P7

8, 9, 10.

En RCL f-= 2,319 fmiope(P) ≤

RCL = { P4 P6 }

P aleat fmiope

P1 P2 P3 P4 8 3,020

9

,02 fmiope(P) ≤ 3

{ P }

11 Se selecciona de forma aleatoria un elemento de RCL, sólo hay una opción, elemento 1

f+= 3,232 2,776

20 19

11 Se selecciona de forma aleatoria un elemento de RCL, sea el elemento 2 12. x= {(P2 = 95), (P1 = 104), (P3 = 99), (P7 = 471), (P6 = 19)} 13. C = {P4, P5} 14. dem_resto = 35 – 19 = 16 Siguiente ciclo, |C| = 2 5. Nuevos límites

U1 U2 U3 U4 U5 U6 U7 NPmáx 9 9 NPmín 7 7

6, 7.

[MW] [$/MW]

P5

3,232 P6

P7

8, 9, 10.

En RCL

f-= 3 0 f+= 3,232 ,126

RCL = 4 8

67

12. x= {(P2 = 95), (P1 = 104), (P3 = 99), (P7 = 471), (P6 = 19), (P4 = 8)}

16. P5 = 8 FIN Solución: x = {104, 9 19,

costo de l 6 costo solu 8 desviación

5.4 Fase búsqueda local Entrada: solución factible, x = (P1o, P2o, …, PUso) Salida: solución mejorada, s = (P1s, P2s, …, PUss) El algoritmo utilizado es el mismo que se utilizó en para el ARS, y se describe en la sección 4.3. EL parámetro k0 determina cuantas soluciones vecinas se generan. 5.5 Zona muerta

En la solución inicial (fase constructora) y en la generación de vecindades (BL), se decide de forma aleatoria y antes de asignar las potencias a cada unidad, en que zona operarán las unidades con zona muerta. Si en la solución inicial la unidad opera arriba de la zona muerta, en la búsqueda local se buscan soluciones arriba de la zona muerta también.

5.6 Ajuste de parámetros, Nitr, α El algoritmo GRASP es de los algoritmos más sencillos en cuanto a parámetros de control. Una vez definidos los algoritmos de las fases constructora y de búsqueda local, basta con ajustar elmiopía de la fase constructora (α). Como se describió anteriormente, un valor de α= 1, permite escoger de forma aleatoria cualquier elemento candidato para formar parte de la solución. Con α= 0, se escoge al mejor elemento evaluado por una función miope para ser agregado a la solución. Un término medio de α= 0.5, permite formar una lista restringida de candidatos integrada por los mejores elementos, de donde se elege, de forma aleatoria, al siguiente elemento que

13. C = {P5} 14. dem_resto = 16 – 8 = 8

Se detiene el ciclo, |C| = 1

5, 99 , 8, , 8 471}

a solución: 51 138. ción óptima: 4 7 018. : 6%

número de iteraciones (N_itr) y el grado de aletoriedad-

68

formara parte de la solución. Con N_itr= 5000 y un número de vecinos k0= 100 que genera la fase de búsqueda local, se revisan 5x105 soluciones, que es una cifra pequeña si se compara con el espacio de solución del caso de estudio 1 de 7 unidades, que es de 1.27 x 1014. La tabla 5.4 muestra los resultados del programa GRASP aplicado al caso 1, usando valores extremos y un valor intermedio para α. Se hicieron 10 pruebas para cada valor de α.

Tabla 5.4 Resultados del GRASP al caso 1, con k0 = 100 y distintos valores de α (0.0, 1.0 y 0.5). Numero de iteraciones= 5000 α =0.5 α=0.0 α = 1.0 costo mejor solucion 487,022 487,023 487,023 solución costo promedio 487,025 487,025 487,026 óptima error mejor solución [%] 0.001 0.001 0.001 487,018 error costo promedio [%] 0.001 0.001 0.002

mejor solución α =0.5 α =0.0 α = 1.0 iteración promedio 1873 3338 2873

mejores tres soluciones α=0.5 α =0.0 α = 1.0

iteración mín* 1498 1556 1333 iteración máx 3580 3732 3763

El desempeño de este algoritmo para el caso de estudio 1 de 7 unidades fue excelente. El error de la mejor solución fue muy pequeño para los tres valores de α utilizados. Se prefirió un valor de α= 0.5 porque la mejor solución se encontró, en promedio, en un número de iteraciones menor (1873), y también encontró a las tres mejores soluciones en un rango menor (1498 a 3580). En las figuras 5.1 a 5.3 se muestra el desempeño del algoritmo GRASP. Se observó que cuando α= 0, las variaciones en el costo de las soluciones mejoradas es menor porque no se permite elegir a elementos que aumenten el costo de la solución. Con alfa = 1.0, la elección de los elementos que se incorporan a la solución es totalmente aleatorio y la solución es generalmente más costosa. Por eso se observaron soluciones con costos más altos que con α= 0.0. Con α= 0.5 se balancea la aleatoriedad y miopía en la generación de las soluciones.

69

α = 0.5

485490495500505510515520

0

250

500

750

1000

1250

1500

iteración

cost

o m

ejor

sol

ució

n

Figura 5.1 Costo de las soluciones de cada iteración, fase de construcción con α=0.5, caso 1 (7

U’s). α = 1.0

485490495500505510515520

0

250

500

750

1000

1250

1500

iteración

cost

o m

ejor

sol

ució

n

Figura 5.2 Costo de las soluciones de cada iteración, fase de construcción con α=1, caso 1 (7 U’s).

α = 0.0

485490495500505510515520

0

250

500

750

1000

1250

1500

iteración

cost

o m

ejor

sol

ució

n

Figura 5.3 Costo de las soluciones mejoradas de cada iteración, fase de construcción con α=0, caso 1 (7 U’s).

70

Se probaron otras combinaciones de N_itr y k0 con el fin de tener una referencia mínima de estos valores. En las columnas a y b de la tabla 5.5b se muestran mejores resultados con la intensificación de la búsqueda local a la vez que se redujo el número de iteraciones, conservando así el número total de soluciones generadas. La mejor solución en la columna b se encontró en promedio en la iteración 329, lo cuál nos indica que no es necesario generar tantas como 500 soluciones iniciales. Por lo tanto se realizaron pruebas con N_itr = 400 y N_itr=300, y se probaron diferentes valores de k0 en la búsqueda local. Los resultados mostrados en las columnas f y g muestran un deterioro en la calidad de las soluciones. Los mejores resultados se obtuvieron con Nitr = 500 y Nitr = 300.

Tabla 5.5 Resultados del GRASP al caso 1, con diferentes combinaciones de N_itr y k0. a b c d e f g N_itr 5000 500 400 300 300 300 200 solución k0 100 1000 750 500 400 300 400 óptima costo mejor solucion 487,022 487,018 487,019 487,019 487,019 487,018 487,020 487,018costo promedio 487,025 487,020 487,021 487,021 487,021 487,022 487,022 desv. Est. 1.90 1.06 1.39 1.65 0.96 2.96 1.98 error mejor solución [%] 0.001 0.000 0.000 0.000 0.000 0.000 0.000 error costo promedio [%] 0.001 0.000 0.001 0.001 0.001 0.001 0.001

mejor solución iteración promedio 1873 329 175 162 147 144 162

mejores tres soluciones

iteración mín* 1498 220 90 91 75 73 57 iteración máx 3580 427 305 227 216 226 162

En la tabla 5.6 se muestran los resultados para un ajuste mas detallado de k0 con los mejores valores de Nitr de la tabla 5.5. Aunque el mejor caso se observa con Nitr=500 y k0 = 500, se prefirió la combinación Nitr=300 y k0 = 400 porque emplea la mitad del tiempo con resultados muy similares.

Tabla 5.6 Ajuste de k0 para el caso 1 (7 U’s). Nitr 500 500 500 300 300 300 k0 = 1000 750 500 500 400 300

Costo mínimo 487,018.4 487,018.7 487,018.5 487,018.5 487,019.4 487,019.4 Costo máximo 487,022.3 487,022.7 487,021.1 487,023.6 487,022.2 487,025.2 Costo promedio 487,020.1 487,020.0 487,020.2 487,020.8 487,020.7 487,022.2 desv. Est. 1.3 1.2 0.7 1.4 1.0 1.7 %error 1) 0.000 0.000 0.000 0.000 0.000 0.000 %error prom 1) 0.000 0.000 0.000 0.001 0.001 0.001 tiempo usuario 3.85 2.88 1.88 1.13 0.89 0.66

71

Para el caso 2 de 36 unidades se utilizó un valor de α= 0.5. Las pruebas realizadas consideraron 5 combinaciones diferentes de los parámetros N_itr y k0. Recuérdese que con N_itr se ajusta el número de soluciones factibles que genera la fase de construcción, y con k0 se controla la cantidad de vecindades que se revisan en la búsqueda local. Las combinaciones de N_itr y k0 consideradas dan como máximo la generación de 2x106 soluciones en las dos fases del GRASP. El espacio de solución es de 1.76x1073, así que el número de soluciones revisadas es insignificante. Reduciendo el valor de N_itr se pretendió generar un menor número de soluciones y hacer más intensa la búsqueda local para mejorar la calidad de la solución final. En la tabla 5.7 se muestran los resultados de aplicar el GRASP al DE del caso de estudio 2. Se observa el mejor desempeño del GRASP con Nitr=1000 donde la mejor solución tuvo un error de 0.05% y el costo promedio de 0.09% respecto de la solución óptima.

Tabla 5.7 Resultados del GRASP para el DE del caso 2, con diferentes combinaciones de N_itr y k0.

N_itr 5000 2500 1250 500 1000 k0 100 200 400 2000 1000 soluciones 500 000 500 000 500 000 1 000 000 1 000 000 costo mejor solucion 4,449,397 4,446,597 4,447,128 4,445,020 4,444,244 solución costo promedio 4,451,485 4,449,132 4,448,376 4,445,910 4,446,048 óptima error mejor solución [%] 0.17 0.10 0.11 0.07 0.05 4,442,037error costo promedio [%] 0.21 0.16 0.14 0.09 0.09

mejor solución iteración * 2930 1303 700 260 440

mejores tres soluciones

iteración mín * 1866 590 306 132 287 iteración máx* 3968 1807 995 344 726 promedio de las10 pruebas

Los resultados para Nitr= 1000 y k0 = 1000 muestran que, en promedio, la mejor solución se obtuvo en las primeras 500 iteraciones, por lo que se utilizaron valores semejantes de Nitr para hacer un mejor ajuste del parámetro k0 respecto al tiempo de ejecución, ver tabla 5.8. La mejor solución se obtuvo con k0 = 1000, y valores grandes de Nitr. Si no se tienen limitantes de tiempo, se pueden utilizar valores tan grandes como se desee, pero las mejoras en la calidad de la solución son mínimas. La combinación Nitr = 500 y k0 = 1000 proporciona casi los mismos resultados que la combinación de valores más grande (Nitr=800 y k0 = 1000) en un tiempo de 60% menos. Para este caso, en donde los tiempos de ejecución son significativos, se usó regresión lineal para poder estimar los tiempos de ejecución respecto del número de soluciones generadas por el grasp (Ts = Nitr x k0) : t = 0.1427 Ts + 2.461x 10 -5.

Tabla 5.8 Ajuste de k0 para el caso 2 (36 U’s).

72

Nitr 800 600 500 k0 1000 750 500 1000 750 500 1000 750 500

Costo mínimo 4,444,245 4,445,224 4,445,971 4,444,245 4,445,224 4,445,971 4,444,245 4,446,688 4,447,301Costo máximo 4,447,653 4,448,801 4,449,765 4,448,312 4,448,801 4,450,183 4,448,312 4,449,563 4,449,564Costo promedio 4,446,193 4,447,183 4,448,036 4,446,259 4,447,226 4,448,448 4,446,539 4,447,686 4,448,719desv. Est. 1,126 1,031 1,009 1,235 1,035 1,207 1,115 994 972%error 0.05 0.07 0.09 0.05 0.07 0.09 0.05 0.10 0.12%error prom 0.094 0.116 0.135 0.095 0.117 0.144 0.101 0.127 0.150tiempo 19.8 15.0 10.0 14.9 11.2 7.5 12.4 9.4 6.3

Por último, en las tablas 5.9 y 5.10 se muestran los resultados para el caso 3. Los ajustes de de N_itr y k0 del caso 1 son muy grandes para este caso y se probaron valores más bajos. Con N_itr = 100 y k0=100 fue suficiente para obtener buenas soluciones.

Tabla 5.9 Resultados del GRASP para el DE del caso 3, con diferentes combinaciones de N_itr y k0.

N_itr 1250 700 100 k0 400 400 100 Mejor soluciones GRASP/espacio solución [%] 2.2 1.2 0.04 Solución costo mejor solucion 8,234.07 8,234.07 8,234.10 8,234.07costo promedio 8,234.07 8,234.07 8,234.11 error mejor solución [%] 0.00 0.00 0.00 error costo promedio [%] 0.00 0.00 0.00

mejor solución iteración * 658 497 40

rango mejores tres soluciones

mín* 313 143 34 máx* 723 562 71

Tabla 5.10 Ajuste de k0 para el caso 3 (3 U’s). Nitr 100 80 125 k0 = 100 125 80

Costo mínimo 8,234.078 8,234.072 8,234.085Costo máximo 8,234.2 8,234.2 8,234.3Costo promedio 8,234.1 8,234.1 8,234.1desv. Est. 0.02 0.04 0.06%error 1) 0.000 0.00 0.000%error prom 1) 0.000 0.000 0.001 tiempo usuario 0.04 0.04 0.04

73

En la tabla 5.11 se resumen los mejores ajustes de los parámetros del GRASP para cada caso de estudio.

Tabla 5.11 Parámetros del GRASP determinados para cada caso de estudio. N_itr k0 alfa caso 1 300 400 0.5 caso 2 500 1000 0.5 caso 3 100 100 0.5

5.7 Resumen de resultados del GRASP (DE con funciones convexas). En la tabla 5.12 se muestra un resumen de los resultados para cada caso de estudio, donde se usaron los ajustes obtenidos para Nitr y k0 y funciones de costo convexas.

Tabla 5.12 Resultados del GRASP para los casos de estudio 1, 2 y 3 (con funciones de costo convexas).

Caso1 Caso 2 Caso 3 (7 U’s) (36 U’s) (3 U’s con pv)

Nitr= 300, k0 = 400 Nitr= 500, k0 = 1000 Nitr= 100, k0 = 100

Costo mínimo 487,019.4 4,444,245 8,234.1 Costo máximo 487,022.2 4,448,312 8,234.2 Costo promedio 487,020.7 4,446,539 8,234.1 desv. Est. 1.0 1115.1 0.02 %error 0.000 0.050 0.000 %error_prom 0.001 0.101 0.000 tiempo usuario 0.89 12.38 0.04

74

Capítulo 6. RESULTADOS FINALES 6.1 Introducción. En este capítulo se muestran los resultados finales de la aplicación de cada heurística a cada caso de estudio. Primeramente se presenta una tabla resumen con los ajustes de los parámetros obtenidos en las secciones anteriores. Las tablas de resultados se obtuvieron a partir de diez pruebas donde se utilizaron semillas aleatorias fijas con valores de 100, 200, 300, … , 900 y 1000. Con el fin de ser breve en la exposición de resultados, sólo se presenta el detalle de los valores de potencia de las unidades para el caso 1 (de 7 U’s) y para los demás casos sólo se presentan tablas con estadísticas de las 10 pruebas realizadas. Para cada caso se muestran resultados del DE con funciones de costo convexas y con funciones de costo no convexas y zona muerta. Se muestran también los resultados comparativos de los casos 1 y 3 al utilizar funciones de costo ajustadas, de segundo grado convexas, y las funciones reales no convexas. No se considera la zona muerta con el propósito de evaluar solamente los costos adicionales que se tienen por utilizar las curvas ajustadas de segundo grado. Para el caso 2 de 36 unidades, se muestran resultados con la combinación de funciones de costo: 32 unidades con funciones de costo convexas de segundo grado, 3 unidades con punto de válvula y una unidad con el modelo del PIE CC Mexicali.

75

6.2. Resultados para el caso de estudio, 7 U’s. Los ajustes de los parámetros de cada heurística que se obtuvieron en las secciones anteriores se resumen en la tabla 6.1.

Tabla 6.1 Ajustes de los parámetros de las heurísticas, caso 1 (7 U’s). Generaciones Nitr FP_IBP K0 alfa Temperatura AG 300 - 2 500 - - AGH 75 - 2 500 500 - ARS - - 50 0.9 500 000 GRASP - 300 400 0.5 -

Detalle de resultados del AG. Los resultados del AG tuvieron mucha variabilidad y en ninguna prueba se obtuvo la asignación de potencia de la solución óptima para el caso de funciones de costo convexas (ver tabla 6.2a). Aún en la prueba 9, que es la de menor costo, los valores de potencia despachados a las unidades 1, 2, 3 y 7 son muy diferentes. El valor de potencia de la unidad 7 en la solución óptima es de 306.1 MW, que en la realidad no sería tomado como punto de operación por estar dentro de la zona muerta (260 a 320 MW). La unidad 7 sería operada en 320 MW que es el límite más cercano fuera de la zona muerta y la diferencia en el BP sería de 13.9 MW. Esta diferencia tendría que ser contrarestado por las demás unidades. Esto indica que habría que resolver otro problema de DE, en donde se determinaría la forma más económica de reducir esos 13.9 MW entre las 6 unidades restantes. En la tabla 6.2b se observa el cumplimiento de la restricción de la zona muerta de la unidad 7 en todas las pruebas, ya que fue tratada desde la codificación. El costo más barato fue el de la prueba 1 ($487,876) y es más caro que cuando no se considera la restricción de la zona muerta ($487,018), aunque hay que resaltar que las funciones de costo con que se evaluó la unidad 7 son distintas. El AG implementado no tiene un algoritmo de reparación de soluciones, por lo que la aptitud difiere de la función de costo total por el escalamiento (1000) y la penalización por el incumplimiento del balance de potencia.

76

Tabla 6.2 Caso 1. Aplicación del AG. Número de generaciones = 300, FP_IBP = 2500, probabilidad de cruza = 0.8, probabilidad de mutación = 0.01. a) todas las unidades con funciones de costo convexas, b) unidad 7 con función de costo no convexa y zona muerta.

MW $ Pt P1 P2 P3 P4 P5 P6 P7 Ft P_IBP Aptitud 1 870.0 90.6 248.0 155.0 7.2 7.0 8.1 354.2 499,190 0.0 499.2 2 870.0 103.7 224.7 155.0 8.4 7.2 8.1 362.8 503,874 0.1 504.0 3 870.0 81.2 201.5 201.5 7.3 7.7 8.0 362.8 496,544 0.1 496.6 4 870.0 64.9 177.9 194.2 7.0 7.0 8.0 411.0 498,094 0.0 498.1 5 870.0 98.3 224.7 230.6 7.0 7.0 8.0 294.4 492,941 0.0 493.0 6 869.9 73.1 148.0 224.6 7.0 7.0 8.0 402.4 500,050 0.0 500.1 7 870.0 66.8 212.2 195.7 7.0 7.0 8.0 373.3 494,168 0.0 494.2 8 870.0 65.9 230.3 178.2 7.0 7.0 8.0 373.7 494,742 0.0 494.8 9 870.0 74.3 224.3 227.6 7.0 7.0 8.0 321.8 490,697 0.0 490.7

10 869.9 95.0 200.8 236.3 7.0 7.0 8.0 315.9 494,257 0.0 494.3

1) 870.0 45.9 248.0 248.0 7.0 7.0 8.0 306.1 487,018 0.0 487.0 1) solución óptima

a)

MW $ Pt P1 P2 P3 P4 P5 P6 P7 Ft FP_IBP aptitud 1 870.0 59.4 221.7 236.4 7.0 7.0 8.0 330.5 487,876 0.0 487.9 2 870.0 60.6 108.4 223.7 7.0 7.0 8.0 455.2 501,272 0.0 501.3 3 870.0 54.9 155.0 248.0 7.5 12.7 8.5 383.3 500,944 0.0 501.0 4 870.0 56.7 227.6 201.5 7.2 7.0 8.0 362.0 489,671 0.0 489.7 5 870.0 67.6 153.5 206.6 7.0 7.0 8.0 420.3 496,182 0.0 496.2 6 870.0 50.7 192.0 152.0 7.0 7.0 8.1 453.2 496,270 0.0 496.3 7 870.0 122.5 203.0 201.2 7.0 7.0 8.0 321.2 499,795 0.0 499.8 8 870.0 47.0 213.1 241.5 7.0 7.0 8.1 346.4 487,842 0.0 487.8 9 870.0 53.3 208.1 186.9 7.0 7.0 8.0 399.7 491,619 0.0 491.6

10 870.0 112.2 207.0 198.6 7.0 7.0 8.0 330.2 497,617 0.0 497.6 b)

77

Detalle de resultados del AGH. A diferencia del AG, con el AGH los resultados son más homogéneos. Los valores de potencia de cada unidad en todas las pruebas son muy similares y por lo tanto también los costos totales. Cuando se considera la zona muerta (tabla 6,3b) se observa que la unidad 7 es llevada al límite inferior de su zona muerta e incluso el costo de generación es inferior al mostrado en la tabla 6.3a para la solución óptima. Esto es debido a que han sido evaluadas con diferentes funciones de costo. Tabla 6.3 Caso 1. Aplicación del AG Híbrido. AGini = 75, K0 = 500, FP_IBP = 2500, probabilidad de cruza = 0.8, probabilidad de mutación = 0.01. a) todas las unidades con funciones de costo convexas, b) unidad 7 con función de costo no convexa y zona muerta.

MW $ Pt P1 P2 P3 P4 P5 P6 P7 Ft 1 870.0 40.0 247.9 247.9 7.0 7.0 8.0 312.1 487,070 2 870.0 41.1 248.0 247.9 7.0 7.0 8.0 310.9 487,050 3 870.0 40.0 247.9 247.9 7.0 7.0 8.0 312.2 487,073 4 870.0 40.0 247.9 247.9 7.0 7.0 8.0 312.2 487,073 5 870.0 43.7 247.9 248.0 7.0 7.0 8.0 308.3 487,027 6 870.0 40.0 248.0 247.9 7.0 7.0 8.0 312.1 487,069 7 870.0 40.0 248.0 248.0 7.0 7.0 8.0 312.1 487,067 8 870.0 40.0 248.0 247.9 7.0 7.0 8.0 312.1 487,068 9 870.0 41.7 248.0 247.9 7.0 7.0 8.0 310.4 487,044

10 870.0 40.0 247.9 248.0 7.0 7.0 8.0 312.1 487,068

1) 870.0 45.9 248.0 248.0 7.0 7.0 8.0 306.1 487,018 1) solución óptima

a)

MW $ Pt P1 P2 P3 P4 P5 P6 P7 Ft 1 870.0 40.0 243.9 244.1 7.0 7.0 8.0 320.0 486,003 2 870.0 40.0 243.8 244.2 7.0 7.0 8.0 320.0 486,003 3 870.0 40.0 242.9 245.1 7.0 7.0 8.0 320.0 486,004 4 870.0 40.0 242.4 245.6 7.0 7.0 8.0 320.0 486,006 5 870.0 40.0 242.8 245.2 7.0 7.0 8.0 320.0 486,004 6 870.0 40.0 243.5 244.4 7.0 7.0 8.0 320.0 486,003 7 870.0 40.0 244.5 243.4 7.0 7.0 8.0 320.0 486,010 8 870.0 40.0 243.7 244.3 7.0 7.0 8.0 320.0 486,003 9 870.0 40.0 247.6 240.4 7.0 7.0 8.0 320.0 486,018

10 870.0 40.0 241.4 246.6 7.0 7.0 8.0 320.0 486,014 b)

78

Detalle de resultados del ARS. Los resultados del ARS fueron muy similares al AGH cuando se usaron funciones convexas. La variabilidad en el costo total fue de 19 contra 15 del AGH. En este algoritmo las soluciones generadas son factibles y no hay penalización por incumplimiento de BP. Cuando se utilizó la función no convexa en la unidad 7, la mitad de las soluciones llevaron a la unidad 7 a una operación en el límite inferior y la otra mitad al límite superior de la zona muerta, siendo estos últimos de menor costo. Los resultados del AGH fueron en general mejores que los del ARS, ya que en todos ellos la unidad 7 se asignó en el límite superior de la zona muerta. Tabla 6.4 Caso 1. Aplicación del Algoritmo de Recocido Simulado. T= 500 000, k0 = 50, a) todas las unidades con funciones de costo convexas, b) unidad 7 con función de costo no convexa y zona muerta.

MW $ Pt P1 P2 P3 P4 P5 P6 P7 Ft 1 870.0 43.8 248.0 248.0 7.0 7.0 8.0 308.2 487,043 2 870.0 42.9 248.0 247.9 7.0 7.0 8.0 309.2 487,036 3 870.0 44.3 248.0 247.9 7.0 7.0 8.0 307.8 487,025 4 870.0 40.0 248.0 247.9 7.0 7.0 8.0 312.1 487,069 5 870.0 42.0 248.0 247.9 7.0 7.0 8.0 310.0 487,047 6 870.0 42.5 248.0 248.0 7.0 7.0 8.0 309.5 487,041 7 870.0 47.0 248.0 247.9 7.0 7.0 8.0 305.2 487,029 8 870.0 40.0 248.0 248.0 7.0 7.0 8.0 312.0 487,082 9 870.0 43.2 247.9 248.0 7.0 7.0 8.0 308.9 487,032

10 870.0 47.5 247.9 247.9 7.0 7.0 8.0 304.6 487.030 1) 870.0 45.9 248.0 248.0 7.0 7.0 8.0 306.1 487,018

1) solución óptima a)

MW $ Pt P1 P2 P3 P4 P5 P6 P7 Ft 1 870.0 40.0 240.1 247.9 7.0 7.0 8.0 320.0 486,020 2 870.0 92.0 248.0 248.0 7.0 7.0 8.0 260.0 488,993 3 870.0 40.0 247.8 240.2 7.0 7.0 8.0 320.0 486,031 4 870.0 92.2 248.0 248.0 7.0 7.0 8.0 259.9 489,011 5 870.0 40.0 245.0 243.0 7.0 7.0 8.0 320.0 486,025 6 870.0 40.0 248.0 240.0 7.0 7.0 8.0 320.0 486,029 7 870.0 40.0 242.9 245.1 7.0 7.0 8.0 320.0 486,004 8 870.0 92.1 248.0 248.0 7.0 7.0 8.0 260.0 488,999 9 870.0 92.2 248.0 247.9 7.0 7.0 8.0 259.9 489,014

10 870.0 92.2 248.0 247.9 7.0 7.0 8.0 259.9 489,018 b)

79

Detalle de resultados del GRASP. Los resultados del GRASP mostraron poca variabilidad (desv. est. = 1) y es que, a diferencia de los algoritmos AG y ARS, éste no da opción de aceptar peores soluciones. Véase en la tabla 6.5 la homogeneidad de los resultados en todas las pruebas. El inconveniente es que es el GRASP requiere de mayor tiempo de ejecución. Los tiempos de ejecución de cada algoritmo se muestran en la siguiente sección. Tabla 6.5 Caso 1. Aplicación del GRASP. Nitr = 300, k0 = 400, a) todas las unidades con funciones de costo convexas, b) unidad 7 con función de costo no convexa y zona muerta.

MW $ Pt P1 P2 P3 P4 P5 P6 P7 Ft 1 870.0 44.8 248.0 248.0 7.0 7.0 8.0 307.3 487,022 2 870.0 45.4 248.0 248.0 7.0 7.0 8.0 306.6 487,020 3 870.0 44.9 248.0 248.0 7.0 7.0 8.0 307.1 487,020 4 870.0 46.3 247.9 248.0 7.0 7.0 8.0 305.8 487,022 5 870.0 46.2 248.0 248.0 7.0 7.0 8.0 305.9 487,020 6 870.0 45.3 248.0 248.0 7.0 7.0 8.0 306.7 487,020 7 870.0 45.2 248.0 247.9 7.0 7.0 8.0 306.9 487,022 8 870.0 46.1 248.0 248.0 7.0 7.0 8.0 305.9 487,019 9 870.0 45.2 248.0 248.0 7.0 7.0 8.0 306.8 487,021

10 870.0 46.5 248.0 247.9 7.0 7.0 8.0 305.6 487,022 1) 870.0 45.9 248.0 248.0 7.0 7.0 8.0 306.1 487,018

1) solución óptima a)

MW $ Pt P1 P2 P3 P4 P5 P6 P7 Ft 1 870.0 40.0 244.0 244.0 7.0 7.0 8.0 320.0 486,003 2 870.0 40.0 243.9 244.1 7.0 7.0 8.0 320.0 486,003 3 870.0 40.0 243.9 244.1 7.0 7.0 8.0 320.0 486,003 4 870.0 40.0 244.0 244.0 7.0 7.0 8.0 320.0 486,003 5 870.0 40.0 243.9 244.1 7.0 7.0 8.0 320.0 486,003 6 870.0 40.0 243.9 244.1 7.0 7.0 8.0 320.0 486,003 7 870.0 40.0 244.0 244.0 7.0 7.0 8.0 320.0 486,003 8 870.0 40.0 244.0 244.0 7.0 7.0 8.0 320.0 486,003 9 870.0 40.0 243.9 244.1 7.0 7.0 8.0 320.0 486,003

10 870.0 40.0 243.8 244.2 7.0 7.0 8.0 320.0 486,003 b)

RESUMEN CASO 1, 7 U’s. En los resultados del AG las soluciones tienen mucha variabilidad (3,915) y el error promedio con respecto al costo de la solución óptima (487,018) fue de 1.95%.

80

En la tabla 6.6 se observa que la calidad de las soluciones es buena para el AG y excelente para los algoritmos AGH, ARS y GRASP. El algoritmo más estable es el GRASP con una desviación estándar de 1, aunque requirió más de 10 veces el tiempo reportado para el AGH y el ARS. Como ya se ha comentado, el AG mejora rápidamente las soluciones iniciales, pero la calidad de la solución final es pobre y muy variable. Las estadísticas del AG que se muestran son muy similares desde la generación número 100, pero se muestra el resultado de 300 generaciones para mostrar que la calidad de la solución ya no mejora significativamente. El algoritmo que mejor se desempeñó fue el ARS, por la calidad de sus soluciones en un menor tiempo de ejecución.

Tabla 6.6 Resumen de la aplicación de los métodos heurísticos al caso 1 con funciones de costo convexas.

AG AGH ARS GRASP

Generaciones =300 AGini = 75 T = 500 000 Nitr=300 k0=500 k0=50 K0=400

Costo mínimo 490,719 487,027 487,025 487,019 Costo máximo 503, 999 487,073 487,082 487,022 Costo promedio 496,491 487,061 487,043 487,021 desv. Est. 3,915 15 19 1 %error 1) 0.76 0.002 0.001 0.000 %error prom 2) 1.95 0.01 0.01 0.00 tiempo usuario 0.45 0.09 0.03 0.89

1 costo mínimo respecto al costo de la solución óptima 2 costo promedio respecto al costo de la solución óptima

Los resultados para el caso 1 cuando se considera la zona muerta y la función no convexa en la U7 se muestran en la tabla 6.7.

Tabla 6.7 Resumen de la aplicación de los métodos heurísticos al caso 1, con zona muerta y función de costo no convexa para unidad 7.

AG AGH ARS GRASP

Generaciones=300 AGini=75 T = 500 000 Nitr=300 k0=500 k0=50 k0=400

Costo mínimo 487,843 486,003 486,004 486,003 Costo máximo 501,288 486,018 489,018 486,003 Costo promedio 494,925 486,007 487,514 486,003 desv. Est. 5 271.2 5.2 1 573 0.03 %error 1 0.379 0.000 0.000 %error prom 2 1.84 0.00 0.31 tiempo usuario 0.44 0.09 0.05 1.52

1 costo mínimo respecto al mejor costo obtenido (GRASP) 2 costo promedio respecto al mejor costo obtenido (GRASP)

81

En este caso, la solución óptima no es conocida, por las restricciones impuestas a la unidad 7. Las mejores soluciones las proporcionó nuevamente el GRASP y las soluciones en todas las pruebas fueron prácticamente las mismas. El AGH mostró ahora mejor desempeño que el ARS y aún cuando se incrementó k0 para que en cuestión de tiempo de ejecución fuera comparable con el AGH, los resultados no mejoraron, ver tabla 6.8.

Tabla 6.8 Resultados del ARS con zona muerta y función no convexa en U7, k0 = 100.

ARS

T = 500 000 k0=100 Costo mínimo 486,016Costo máximo 489,022Costo promedio 487,516desv. est. 1,572%error 1 0.003%error prom 2 0.31tiempo usuario 0.14

Se comparó el DE con los dos tipos de funciones, convexa y no convexa, para la unidad 7 del PIE CC Mexicali. A la primera se hará referencia como la función de costo ajustada y a la segunda, como la función de costo real, pues es la que proporciona el permisionario para la facturación de la energía entregada. Los resultados en la tabla 6.9(1) son los que se obtienen con el método simplex, utilizando funciones de costo de segundo grado convexas; en 6.9(2) se evalúa a la unidad 7 con la función de costo real; en 6.9(3), la mejor solución obtenida de los cuatro métodos heurísticos, que la proporcionó el GRASP.

Tabla 6.9 Evaluación de funciones de costo, caso 1 (7Us) sin zona muerta. Demanda = 870 MW potencia Costo Pt P1 P2 P3 P4 P5 P6 P7 P1 P2 P3 P4 P5 P6 P7 total 1 870.0 45.9 248.0 248.0 7.0 7.0 8.0 306.1 42,358 107,796 107,796 22,629 26,061 27,534 152,845 487,0182 870.0 45.9 248.0 248.0 7.0 7.0 8.0 306.1 42,358 107,796 107,796 22,629 26,061 27,534 151,601 485,7743 870.0 40.1 248.0 248.0 7.0 7.0 8.0 311.9 39,569 107,796 107,796 22,629 26,061 27,534 154,347 485,732

1) solución óptima, U7 evaluada con función de costo ajustada de segundo grado convexa. 2) solución óptima, U7 evaluada con función de costo no convexa. 3) mejor solución GRASP, usando función de costo no convexa para U7.

82

La tabla 6.10 muestra la comparación de resultados de las heurísticas. Con excepción del AG, todas las heurísticas obtuvieron costos menores a los obtenidos con el simplex, tanto en costo mínimo como en costo promedio.

Tabla 6.10 Resultados de las heurísticas para el caso 1. U7 con función de costo real. Demanda = 870 MW. AG AGH RS GRASP SIMPLEX1

demanda 870

300 AGini=75 T = 500 000 Nitr=300 generaciones k0=500 k0=50 k0=400 Costo mínimo 487,830 485,733 485,734 485,732 485,774 Costo máximo 499,938 485,806 485,744 485,732 Costo promedio 494,006 485,745 485,739 485,732 desv. Est. 4,216 23 4 0 %error 2 0.42 -0.01 -0.01 -0.01 %error prom 2 1.69 -0.01 -0.01 -0.01 1 costo de la unidad 7 evaluado con función real, no convexa 2 respecto de la solución del simplex

La mejor solución que se obtuvo con el GRASP en diez pruebas tuvo un costo total de 485 732, que es menor en $42 al que se obtendría indirectamente con el simplex 6.9 (2). Tomando en cuenta que los métodos heurísticos no garantizan la obtención de una solución óptima, se puede decir que para una demanda de 870 el DE que se obtuvo utilizando la función ajustada tuvo un error de al menos $42 y representa el 0.01% del costo total de generación. La diferencia en costo de la U7 evaluada con los dos tipos de funciones es de $1 244 (6.9 1,2) y, como se aprecia en la figura 6.1, en este punto de operación de 306 MW, ambas funciones son muy cercanas.

Función de costo

1500

51500

101500

151500

201500

251500

301500

120 160 200 240 280 320 360 400 440 480

MW

$/h real

ajustada

3 0 6

Figura 6.1 Punto de operación de la unidad 7 (306 MW), caso 1 con 870 MW de demanda.

83

Se resolvió el DE con otros valores de demanda para exponer los resultados cuando la U7 opera en regiones donde las curvas están más alejadas, por ejemplo de 122 A 160 MW ó de 420 a 489 MW. En la tabla 6.10 se muestran los resultados para una demanda de 700 MW en donde el despacho de la U7, con la función de costo ajustada, es de 139.9 MW. La diferencia en costo de las dos curvas es de $3 660 (tabla 6.11 1,2). Los resultados del GRASP, utilizando la función real de costo para la U7, la despachan en 130.3 MW. Entonces el error por usar la función de costo ajustada fue de al menos $125 (0.03%). Tabla 6.11 Evaluación de funciones de costo, caso 1 (7Us). Demanda = 700 MW. potencia Costo Pt P1 P2 P3 P4 P5 P6 P7 P1 P2 P3 P4 P5 P6 P7 total 1 700.0 42.1 248.0 248.0 7.0 7.0 8.0 139.9 40,542 107,796 107,796 22,629 26,061 27,534 72,946 405,3042 700.0 42.1 248.0 248.0 7.0 7.0 8.0 139.9 40,542 107,796 107,796 22,629 26,061 27,534 69,286 401,644

3 700.0 51.7 248.0 248.0 7.0 7.0 8.0 130.3 45,220 107,796 107,792 22,629 26,061 27,534 64,486 401,5181) solución óptima, U7 evaluada con función de costo ajustada 2) solución óptima, U7 evaluada con función de costo real 3) mejor solución GRASP, usando función de costo real en la U7 La tabla 6.12 muestra la comparación de resultados de las heurísticas. De igual manera, se obtienen mejores costos con las heurísticas, con excepción del AG.

Tabla 6.12 Resultados de las heurísticas para el caso 1. U7 con función de costo real. Demanda = 700 MW. AG AGH RS GRASP SIMPLEX1

demanda 700

300 AGini=75 T = 500 000 Nitr=300 generaciones k0=500 k0=50 k0=400 Costo mínimo 402,072 401,582 401,526 401,518 401,644 Costo máximo 416,216 401,773 401,614 401,526 Costo promedio 409,245 401,663 401,557 401,522 desv. Est. 5,187 61 29 2 %error 2 0.11 -0.02 -0.03 -0.03 %error prom 2 1.89 0.00 -0.02 -0.03 1 costo de la unidad 7 evaluado con función real, no convexa 2 respecto de la solución SIMPLEX

En la tabla 6.13 se muestran los resultados para una demanda de 1 050 MW. El despacho de la U7 con la función de costo ajustada es de 482.1 MW y la diferencia en costo de las dos curvas es de $7 089 (6.13 1,2). Al compararse con

84

los resultados del GRASP, la U7 se despacha en 489.0 MW y el error por usar la función de costo ajustada fue de al menos $302 (0.05%).

Tabla 6.13 Evaluación de funciones de costo, caso 1 (7 Us). Demanda = 1 050 MW. potencia Costo Pt P1 P2 P3 P4 P5 P6 P7 P1 P2 P3 P4 P5 P6 P7 total 1 1050.0 49.9 248.0 248.0 7.0 7.0 8.0 482.1 44,319 107,796 107,796 22,629 26,061 27,534 239,195 575,3302 1050.0 49.9 248.0 248.0 7.0 7.0 8.0 482.1 44,319 107,796 107,796 22,629 26,061 27,534 232,106 568,241

3 1050.0 43.0 248.0 248.0 7.0 7.0 8.0 489.0 40,971 107,791 107,792 22,629 26,061 27,534 235,161 567,9391) solución óptima, U7 evaluada con función de costo ajustada 2) solución óptima, U7 evaluada con función de costo real 3) mejor solución GRASP, usando función de costo real en la U7

La tabla 6.14 muestra la comparación de resultados de las heurísticas. De igual manera, se obtienen mejores costos con las heurísticas, con excepción del AG y el AGH en el costo promedio. Tabla 6.14 Resultados de las heurísticas para el caso 1. U7 con función de costo real. Demanda = 1 050 MW.

AG AGH RS GRASP SIMPLEX1

demanda 1 050

300 AGini=75 T = 500 000 Nitr=300 generaciones k0=500 k0=50 k0=400 Costo mínimo 570,777 567,942 567,941 567,939 568,241 Costo máximo 584,783 567,963 568,112 567,941 Costo promedio 578,826 567,949 567,966 567,940 desv. Est. 4,380 6 52 1 %error 2 0.45 -0.05 -0.05 -0.05 %error prom 2 1.86 -0.05 -0.05 -0.05 1 costo de la unidad 7 evaluado con función real, no convexa 2 respecto de la solución SIMPLEX

85

6.3 Resultados para el caso de estudio 2, 36 Unidades. Los ajustes de los parámetros de cada heurística se resumen en la tabla 6.15.

Tabla 6.15 Ajustes de los parámetros de las heurísticas, caso 2 (36 U’s). Generaciones Nitr FP_IBP K0 alfa Temperatura AG 500 - 563 - - AGH 500 - 563 750 - ARS - - 800 0.95 500 000 GRASP - 500 1000 0.5 -

RESUMEN CASO 2, 36 U’s. La tabla 6.16 muestra el mejor desempeño del AGH al tener el menor costo y el mejor costo promedio con una variabilidad aceptable respecto a las demás heurísticas. El GRASP presentó resultados similares al AGH pero con un tiempo que es cuatro veces superior. Tabla 6.16 Resumen de la aplicación de los métodos heurísticos al caso 2 con funciones de costo convexas.

AG AGH ARS GRASP Generaciones=500 AGini=500 T=500 000 Nitr=500 k0= 750 k0= 800 k0= 1000 Costo mínimo 4,449,024 4,443,442 4,456,305 4,444,245 Costo máximo 4,455,664 4,447,401 4,458,577 4,448,312 Costo promedio 4,452,219 4,445,964 4,457,366 4,446,539 desv. Est. 2,454 1,284.2 719 1,115 %error1 0.16 0.03 0.32 0.05 %error prom1 0.23 0.09 0.35 0.10 tiempo usuario 3.1 3.2 4.0 12.4

1 respecto al costo de la solución óptima En la tabla 6.17 se observa que la variabilidad de las soluciones se incrementa para las heurísticas AG, AGH y ARS. Esto es porque al considerar la zona muerta de la unidad 36, las soluciones presentan brincos en la potencia de la unidad 36, alrededor de los límites de la zona muerta.

Tabla 6.17 Resumen de la aplicación de los métodos heurísticos al caso 2, con zona muerta y función no convexa para la unidad 36.

AG AGH ARS GRASP Generaciones=500 AGini=500 T=500 000 Nitr=500 k0=750 k0=800 k0=1000 Costo mínimo 3,850,923 3,843,912 3,850,720 3,845,360 Costo máximo 3,863,661 3,853,344 3,870,634 3,847,561 Costo promedio 3,856,027 3,848,348 3,857,610 3,846,342 desv. Est. 4,725 3,860 7,593 831 %error 1 0.14 -0.04 0.14 0.000 %error_prom 1 0.28 0.08 0.32 0.03 tiempo usuario 3.1 3.3 4.1 16.4

1 respecto al mejor costo obtenido (AGH)

86

6.4 Resultados para el caso de estudio 3, 3 Unidades. Los ajustes de los parámetros de cada heurística para el caso 3 se resumen en la tabla 6.18.

Tabla 6.18 Ajustes de los parámetros de las heurísticas, caso 3 (3 U’s). Generaciones Nitr FP_IBP k0 Alfa Temperatura AG 400 - 25 - - AGH 150 - 25 500 - ARS - - 200 0.9 2 500 GRASP - 100 100 0.5 -

RESUMEN CASO 3, 3 U’s. La tabla 6.19 muestra el desempeño de las heurísticas para el caso 3. En este caso todas las heurísticas proporcionaron soluciones bastante aceptables, destacando el ARS por la calidad de las soluciones en cuanto a variabilidad y tiempo de ejecución.

Tabla 6.19 Resumen de la aplicación de los métodos heurísticos al caso 3 (3 Us). AG AGH ARS GRASP mdc/4 Gen =400 AG = 150 T =2 500 Nitr=100 k0=500 k0=200 k0=100

Costo mínimo 8,241.1 8,234.2 8,234.1 8,234.08 Costo máximo 8,500.2 8,254.1 8,252.0 8,234.2 Costo promedio 8,327.4 8,241.7 8,241.81 8,234.11 desv. Est. 89.4 7.4 5.1 0.02 %error 1) 0.085 0.001 0.000 0.000 %error prom 1) 1.133 0.093 0.094 0.000 tiempo usuario 0.26 0.10 0.03 0.04 1 respecto al mejor costo obtenido (GRASP)

La figura 6.2 muestra las funciones de costo que se analizan en este caso. Se recuerda que las funciones en color más grueso representan un comportamiento más aproximado del costo del combustible por la apertura y cierre de válvulas en el control de potencia de la unidad. Los métodos heurísticos pueden evaluar este tipo de funciones en el problema de DE y los resultados comparativos con las soluciones del método clásico que utiliza las funciones de segundo grado se muestran en la tabla 6.20.

87

0

1,000

2,000

3,000

4,000

5,000

6,000

7,000

8,000

50 150 250 350 450 550 650

MW

$/h

U1 U2 U3

Figura 6.2 Funciones de costo del caso 3 (3 Us).

Tabla 6.20 Resultados del DE para el caso 3 (3 Us). potencia [MW] Costo [$] Pt U1 U2 U3 U1 U2 U3 total 1 850.0 392.1 335.4 122.5 3,984 3,250 1,252 8,486 diferencia [$] error [%] 2 850.0 300.3 400.0 149.7 3,087 3,767 1,380 8,234 252 3.1

1) solución óptima, con funciones de costo de segundo grado convexas 2) mejor solución GRASP, con funciones de costo que consideran los puntos de válvula

En este caso el empleo de las heurísticas para evaluar el punto de válvula de las unidades térmicas muestra un mejor despacho con un ahorro del 3.1% en el costo total de generación

88

CONCLUSIONES Al comparar los desempeños de las heurísticas utilizadas, el GRASP presentó la mejor calidad en las soluciones en cuanto a costo y a variabilidad; aunque requirió de mayor tiempo de ejecución para las instancias de 7 y 36 unidades. Al reducir el tiempo de ejecución del GRASP a los tiempos en los que el AGH y el ARS dieron buenos resultados, el GRASP mostró desventajas porque las soluciones fueron de menor calidad. Por otra parte, aumentando los tiempos de ejecución del AGH y el ARS a los tiempos del GRASP, éste continuó siendo mejor, pues los otros ya no mejoraron la calidad de sus soluciones. Sin embargo, los resultados que se obtuvieron para la solución del DE fueron bastante satisfactorios y las cuatro heurísticas presentadas mostraron consistencia en la obtención de buenos soluciones con la consideración de funciones de costo no convexas y las discontinuidades que representan las zonas muertas. La mejor solución del GRASP para el caso de 7 unidades, evidenció la ventaja de evaluar la función no convexa al obtener menores costos en el despacho, del orden de 0.01% al 0.05%, dependiendo de la separación de las curvas analizadas en el punto de operación de la unidad. Para el caso de 3 unidades, donde se evaluó el punto de válvula, la mejor solución del GRASP resultó en un costo de generación menor en un 3.1%. Las ventajas del GRASP son evidentes en este problema y aunque los tiempos de ejecución son superiores a los de las demás heurísticas, éstos no son de consideración para su aplicación. Sin embargo, la adición de restricciones es una desventaja para este algoritmo, al igual que lo es para el ARS, por la dificultad de crear una solución inicial. Es más fácil para el AG considerar más restricciones debido a que sólo es necesario incorporar factores de penalización a la función objetivo y además se tiene la posibilidad de poder considerarlas desde la codificación, aunque esto último requiere de mayor habilidad. Por otra parte, se carece en el CENACE de modelos que consideren los puntos de válvula, u otro tipo de curvas más aproximadas que se obtendrían de medir el régimen térmico en un mayor número de puntos y que actualmente se limitan a la medición de tres puntos, que son los suficientes para ajustar una función de segundo grado.

89

Actualmente, no se han explorado nuevos modelos por las limitaciones que impone el programa computacional que obtiene el despacho económico. La incorporación de métodos heurísticos a las rutinas de solución del despacho económico permitiría utilizar cualquier tipo de curva o serie de puntos que mejor modelaran el régimen térmico de las unidades, con el fin de lograr reducciones, por mínimas que sean, en el despacho de generación. Cualquier mejora en el despacho de generación resulta en ahorros importantes si consideramos los costos de producción por combustibles y costos variables que se tienen en el Sistema Interconectado Nacional, que por ejemplo en el año 2006, totalizaron 86 mil millones de pesos. Una disminución mínima del costo de generación, por ejemplo del 0.01 por ciento representa ahorros de 8.6 millones de pesos anuales. La disminución en el costo de generación que se puede obtener al utilizar métodos heurísticos para considerar curvas de cualquier tipo, como las aquí tratadas, dependerá del mayor número de unidades que las consideren y de la diferencia entre las curvas en los modelos utilizados. Para el caso de 7 unidades, se evaluó la restricción en una de siete unidades. En el Sistema Interconectado Nacional, existen diez PIE’s que utilizan curvas no convexas en su régimen térmico, dentro de un promedio de 250 unidades despachadas económicamente. Como se comentó al inicio de este trabajo, el despacho económico es un subproblema del problema de asignación de unidades. El despacho económico es un problema puntual, donde el espacio de tiempo es generalmente de una hora. En el problema de asignación de unidades se amplía el horizonte de tiempo y se incorporan un mayor número de restricciones que acoplan al despacho actual con los despachos de horas anteriores, por ejemplo tiempos mínimos de arranque y paro, rampas de carga, disponibilidad de combustibles, etc. La metodología actual utiliza la programación lineal para resolver el PDE y programación dinámica para el de asignación de unidades. Para trabajos futuros se recomienda la incorporación de métodos heurísticos al programa computacional que resuelve el despacho económico, o incluso para resolver el problema de asignación de unidades, pues para estos trabajos existen un gran número de trabajos publicados que han mostrado excelentes resultados.

90

REFERENCIAS

[1] Aboytes, F., Guerrero, J.J.: Despacho económico, flujos óptimos y control de generación. Curso de Capacitación en Sistemas de Potencia, CENACE. México, D.F., 2001.

[2] Cai, X., Lo, K.: Unit Commitment by a genetic algorithm. Nonlinear Analysis, Theory, Methods & Applications, Vol. 30, No. 7, pp. 4289-4299, 1997.

[3] Goldberg, D. E., Genetic Algorithms in Search, Optimization, and Machina Learning, The University of Alabama, Adison-Wesley publishing Company, 1989

[4] Gutiérrez A. M. A. “La técnica de Recocido Simulado y sus aplicaciones”, Tesis

para obtener el grado de Doctor en Ingeniería. UNAM, México, 1991

[5] Li, F.: A comparison of genetic algorithms with conventional techniques on a spectrum of power economic dispatch problems. Expert Systems with Applications 15, 133-142, 1998.

[6] Li, F., Morgan, R., Williams, D.: Hybrid genetic to ramping rate constrained dynamic economic dispatch. Electric Power Systems Research 43, 97-103, 1997.

[7] Olachea, A.: Aplicación de la técnica de algoritmos genéticos al problema de despacho económico. Tesis para obtener el grado de MC en Ing. Eléctrica. Universidad Autónoma de Nuevo León, 2003.

[8] Ongsakul, W.: Real-time economic dispatch using merit order loading for linear decreasing and staircase incremental cost functions. Electric Power Systems Research 51, 167-173, 1999.

[9] Reeves, R.: Modern Heuristic Techniques for Combinatorial Problems. Edited by Colin R. Reeves, Mc Graw Hill, 1995

[10] Resende, M.: Greedy Randomized adaptive search procedure (GRASP), AT&T Labs Research Technical Report: 98.41.1. December 22, 1998.

91

[11] Sudhakaran, M., Slochanal, S.M.R., Sreeram, R., Chandrasekhar, N.: Application of refined genetic algorithm to combined economic and emission dispatch. IE (I) Journal-EL. Vol. 85, September 2004.

[12] Wood & Wollenberg: Power generation operation and control. Ed. John Wiley and Sons Inc.,1984.

[13] Walters, D., Sheble, G.: Genetic algorithm solution of economic dispatch with

valve point loading. IIE Transactions on Power Systems, Vol. 8, No. 3, 1993 [14] Barr,S. R., Golden, L. B., Kelly, J. P., Resende, M., Stewart, W.: Designing

and Reporting on Computational Heuristic Methods. Journal of Heuristics, I: 9-32, 1995.

92

APENDICE I

Solución analítica al caso de estudio 1 (7 Us) por el método del lagrangiano.

AI-1

APENDICE I. Solución analítica al caso de estudio 1 (7 Us) por el método del lagrangiano. La formulación del problema de DE sin pérdidas es la siguiente:

minimizar : Pi)

sujeto a:

Pmini ≤ Pi ≤ PmaxiDonde: n: número de unidades generadoras Fi : Función de costo del generador i Pi : Potencia del generador i Pmini : Potencia mínima que puede suministrar el generador i Pmaxi : Potencia máxima que puede suministrar el generador i Se utiliza un multiplicador de Lagrange para incorporar a la función objetivo la restriccion de igualdad (balance generación-demanda). Función lagrangeana:

dando lugar a las siguientes condic

∑=

n

iiF

1(

∑=

=n

ii demandaP

1

El mínimo de la función se obtiene a partir del gradiente, iones de optimalidad:

nidPdF

PL

i

i

i

,...,1;0 ==+=∂∂ λ

;01

=−=∂∂ ∑

=

demandaPL n

iiλ

Datos del caso de estudio:

⎟⎠

⎞⎜⎝

⎛−+= ∑∑

==

n

ii

n

iii demandaPPFPL

11)(),( λλ

AI-2

Demanda: 804 MW coeficientes

Pmin Pmax a b c

central tipo [MW] [MW] [$/MWhP

2P] [$/MWh] [$]

Presidente Juárez U1 vapor convencional 40 160 1.28000 368.0 22770

Presidente Juárez U2 ciclo combinado 62 248 0.56350 158.5 33830

Presidente Juárez U3 ciclo combinado 62 248 0.56350 158.5 33830

Ciprés U4 turbogás 7 27 24.92000 1154.0 13330

Mexicali U5 turbogás 7 26 19.45000 1204.0 16680

Tijuana U6 turbogás 8 30 21.16000 1190.0 16660

CC Mexicali 1) U7 ciclo combinado 122 489 0.02908 467.7 6957

Total 308 1,228 1) Coeficientes abc de la curva ajustada a los tres puntos del consumo específico proporcionado por el Productor Independiente

Sustituyendo los coeficientes abc en las ecuaciones de optimalidad:

;0)2277036828.1(

1

12

1 =+++ λ

dPPPd

;0)338305.1585635.0(

2

22

2 =+++ λ

dPPPd

;0)338305.1585635.0(

3

32

3 =+++ λ

dPPPd

;0)13330115492.24(

4

42

4 =+++ λ

dPPPd

;0)16680120445.19(

5

52

5 =+++ λ

dPPPd

;0)16660119016.21(

6

62

6 =+++

λdP

PPd

;0)69577.4670291.0(

7

72

7 =+++

λdP

PPd

8047654321 =++++++ PPPPPPP

AI-3

Estas derivadas generan el siguiente sistema de ecuaciones lineales: A p = B

Matriz A Matriz p

Matriz B

UB1B UB2B UB3B UB4B UB5B UB6B UB7B λ

2.560 0 0 0 0 0 0 1 P1 -368 0 1.127 0 0 0 0 0 1 P2 -158.5 0 0 1.127 0 0 0 0 1 P3 -158.5

0 0 0 49.840 0 0 0 1 P4 = -1154 0 0 0 0 38.900 0 0 1 P5 -1204 0 0 0 0 0 42.320 0 1 P6 -1190 0 0 0 0 0 0 0.058 1 P7 -467.7 1 1 1 1 1 1 1 0 λ 804

p = A P

-1P B

A P

-1P B p revisión límites

UB1B UB2B UB3B UB4B UB5B UB6B UB7B λ min max

0.3828 -0.0178 -0.0178 -0.0004 -0.0005 -0.0005 -0.3457 0.0201 -368 44.3 40 160-0.0178 0.8468 -0.0405 -0.0009 -0.0012 -0.0011 -0.7853 0.0457 -158.5 286.5 Sup 62 248-0.0178 -0.0405 0.8468 -0.0009 -0.0012 -0.0011 -0.7853 0.0457 -158.5 286.5 Sup 62 248

-0.0004 -0.0009 -0.0009 0.0200 0.0000 0.0000 -0.0178 0.0010 -1154 = -13.5 Inf 7 27-0.0005 -0.0012 -0.0012 0.0000 0.0257 0.0000 -0.0228 0.0013 -1204 -18.6 Inf 7 26-0.0005 -0.0011 -0.0011 0.0000 0.0000 0.0236 -0.0209 0.0012 -1190 -16.7 Inf 8 30-0.3457 -0.7853 -0.7853 -0.0178 -0.0228 -0.0209 1.9776 0.8850 -467.7 235.5 122 4890.0201 0.0457 0.0457 0.0010 0.0013 0.0012 0.8850 -0.0515 804 -481.4

El resultado muestra que se han violado los límites de potencia de 5 unidades generadoras. Para encontrar una solución, se sustituyen los valores fuera de límite por los límites que violaron, mínimo o máximo, y se resuelve nuevamente el sistema de ecuaciones. A p = B

Matriz A Matriz p

Matriz B

UB1B UB2B UB3B UB4B UB5B UB6B UB7B λ

2.560 0 0 0 0 0 0 1 P1 -368 0 1.127 0 0 0 0 0 1 P2 -158.5 0 0 1.127 0 0 0 0 1 P3 -158.5

0 0 0 49.840 0 0 0 1 P4 = -1154 0 0 0 0 38.900 0 0 1 P5 -1204 0 0 0 0 0 42.320 0 1 P6 -1190 0 0 0 0 0 0 0.058 1 P7 -467.7 1 1 1 1 1 1 1 0 λ 804

AI-4

A P

-1P B p revisión límites

UB1B UB2B UB3B UB4B UB5B UB6B UB7B λ min max

0.3819 -0.0222 -0.0222 -0.0222 -0.0222 -0.0222 -0.3819 0.0222 -368 44.4 40 1600.0000 1.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 -248 248.0 62 2480.0000 0.0000 1.0000 0.0000 0.0000 0.0000 0.0000 0.0000 -248 248.0 62 248

0.0000 0.0000 0.0000 1.0000 0.0000 0.0000 0.0000 0.0000 -7 = 7.0

7 270.0000 0.0000 0.0000 0.0000 1.0000 0.0000 0.0000 0.0000 -7 7.0 7 260.0000 0.0000 0.0000 0.0000 0.0000 1.0000 0.0000 0.0000 -8 8.0 8 30

-0.3819 -0.9778 -0.9778 -0.9778 -0.9778 -0.9778 0.3819 0.9778 -467.7 241.6 122 4890.0222 0.0569 0.0569 0.0569 0.0569 0.0569 0.9778 -0.0569 804 -481.7

El costo incremental del sistema es λ=481.7. Se calculan los costos incrementales de las unidades fuera de límites y se revisan las condiciones de optimalidad de Kuhn-Tucker:

ii PPiPparadPidFi maxmin <<= λ

iPPiparadPidFi max=≤ λ

iPPiparadPidFi min=≥ λ

PB2B = PmaxB2B λB2B = 1.127 (248) + 158.5 = 438.0 λB2B < λ cumple PB3B = PmaxB3B λB3B = 1.127 (248) + 158.5 = 438.0 λB3B < λ cumple PB4B = Pmin B4B λB4B = 49.84 (7) + 1 154.0 = 1 502.9 λB4B > λ cumple PB5B = Pmin B5B λB5B = 38.90 (7) + 1 204.0 = 1 476.3 λB5B > λ cumple PB6B = Pmin B6B λB6B = 42.32 (8) + 1 190.0 = 1 528.6 λB6B > λ cumple La solución encontrada cumple con todos los límites de potencia, con las condiciones de optimalidad de Kuhn-Tucker y con el BP. En la Tabla 6.1 se muestra la evaluación del costo de esta solución óptima.

CostoP1 P2 P3 P4 P5 P6 P7 Σ (P1..P7) Fc(P1) Fc(P2) Fc(P3) Fc(P4) Fc(P5) Fc(P6) Fc(P7) Σ (Fc) Fcr(7) R=Σ (Fcr)

44.4 248.0 248.0 7.0 7.0 8.0 241.6 804.0 41,649 107,796 107,796 22,629 26,061 27,534 121,635 455,099 120,767 454,231

Fc(P) = aP 2 + bP + c Costo real

Tabla 6.1 Solución analítica, con funciones de costo cuadráticas; y evaluación con la función de costo real de la U7.

APENDICE II.

Código fuente de los programas en

lenguaje C.

Programas Principales Algoritmo Genético. “AG2.c”. #include "ag.h" int main(int argc,char **argv) { short poblacion_ini[Tam_pob][Us], ganador[Tam_pob],nueva_poblacion[Tam_pob][Us]; real aptitudes[Tam_pob][2]; real P_cruza,P_mutacion; int i,j,k, semilla; Unidad unidades []= { { 1.28, 368.0, 22770.0, 0.0, 0.0, 40.0, 160.0, 11, 0, 40.0, 40.0}, { 0.5635, 158.5,33830.0, 0.0, 0.0, 62.0, 248.0, 11, 0, 62.0, 62.0}, { 0.5635, 158.5,33830.0, 0.0, 0.0, 62.0, 248.0, 11, 0, 62.0, 62.0}, { 24.92, 1154.0,13330.0, 0.0, 0.0, 7.0, 27.0, 8, 0, 7.0, 7.0}, { 19.45, 1204.0,16680.0, 0.0, 0.0, 7.0, 26.0, 8, 0, 7.0, 7.0}, { 21.16, 1190.0,16660.0, 0.0, 0.0, 8.0, 30.0, 8, 0, 8.0, 8.0}, { 0.02908, 467.7,6957.0, 0.0, 0.0, 122.0, 489.0, 12, 0,260.0, 320.0} }; real modelo_cc[][5]= { {0.04528,489.0,-0.07852, 519.3, 245.0} }; P_cruza = 0.8; P_mutacion=0.01; if (argc > 1) {semilla = strtoul(argv[1],NULL,10); srand(semilla);} else { srand(time(NULL));} pob_ini2(poblacion_ini, unidades, Tam_pob, AG); evaluacion2(poblacion_ini, aptitudes, unidades, modelo_cc); for (i=1; i<=300; i++) { selec_torneo2(poblacion_ini, aptitudes, ganador); hijos2(poblacion_ini,ganador,nueva_poblacion,unidades,P_cruza, P_mutacion); evaluacion2(nueva_poblacion, aptitudes, unidades, modelo_cc); for (j=0; j<Tam_pob;j++) { for (k=0; k< Us; k++) { poblacion_ini[j][k]=nueva_poblacion[j][k]; nueva_poblacion[j][k]=0;} } } for (j=0; j<Tam_pob;j++) {for (k=0; k< Us; k++) printf("%d ",poblacion_ini[j][k]); printf("\n");} salir(); return (0); } Algoritmo Genético Híbrido (AGH). “AGH.c”. #include "ag.h"

AII-1

int main(int argc,char **argv) { short poblacion_ini[Tam_pob][Us], ganador[Tam_pob],nueva_poblacion[Tam_pob][Us]; real aptitudes[Tam_pob][2]; real P_cruza, P_mutacion,*P_sol,costo; int i,j,k,lineas,veces,iteraciones,iteraciones_ini; int semilla; short estado; Unidad unidades []= { { 1.28, 368.0, 22770.0, 0.0, 0.0, 40.0, 160.0, 11, 0, 40.0, 40.0}, { 0.5635, 158.5,33830.0, 0.0, 0.0, 62.0, 248.0, 11, 0, 62.0, 62.0}, { 0.5635, 158.5,33830.0, 0.0, 0.0, 62.0, 248.0, 11, 0, 62.0, 62.0}, { 24.92, 1154.0,13330.0, 0.0, 0.0, 7.0, 27.0, 8, 0, 7.0, 7.0}, { 19.45, 1204.0,16680.0, 0.0, 0.0, 7.0, 26.0, 8, 0, 7.0, 7.0}, { 21.16, 1190.0,16660.0, 0.0, 0.0, 8.0, 30.0, 8, 0, 8.0, 8.0}, { 0.02908, 467.7,6957.0, 0.0, 0.0, 122.0, 489.0, 12, 0,260.0, 320.0} }; real modelo_cc[][5]= { {0.04528,489.0,-0.07852, 519.3, 245.0} }; P_cruza=0.8; P_mutacion=0.01; estado=0; despedidas(); if (argc > 1) {semilla = strtoul(argv[1],NULL,10); srand(semilla);} else { srand(time(NULL));} P_sol=crea_vector_real(Us); iteraciones_ini=75; iteraciones=iteraciones_ini; veces=-1; pob_ini2(poblacion_ini, unidades, Tam_pob, AG); evaluacion2(poblacion_ini, aptitudes, unidades, modelo_cc); do { for (i=1; i<=iteraciones; i++) { selec_torneo2(poblacion_ini, aptitudes, ganador); hijos2(poblacion_ini,ganador,nueva_poblacion,unidades,P_cruza, P_mutacion); evaluacion2(nueva_poblacion, aptitudes, unidades, modelo_cc); for (j=0; j<Tam_pob;j++) { for (k=0; k< Us; k++) { poblacion_ini[j][k]=nueva_poblacion[j][k]; nueva_poblacion[j][k]=0;} } } estado=busqueda_local(poblacion_ini, aptitudes, unidades, modelo_cc,P_sol); iteraciones=1; veces++; } while(estado==0); for (i=0;i<Us;i++) printf("P%d: %f\n",i,P_sol[i]); printf(" %u generaciones\n",iteraciones_ini+veces*iteraciones); salir(); return (0); } Algoritmo de Recocido Simulado (ARS). “sa.c”. #include "ag.h" int main(int argc,char **argv) {

AII-2

Unidad unidades []= { { 1.28, 368.0, 22770.0, 0.0, 0.0, 40.0, 160.0, 11, 0, 40.0, 40.0}, { 0.5635, 158.5,33830.0, 0.0, 0.0, 62.0, 248.0, 11, 0, 62.0, 62.0}, { 0.5635, 158.5,33830.0, 0.0, 0.0, 62.0, 248.0, 11, 0, 62.0, 62.0}, { 24.92, 1154.0,13330.0, 0.0, 0.0, 7.0, 27.0, 8, 0, 7.0, 7.0}, { 19.45, 1204.0,16680.0, 0.0, 0.0, 7.0, 26.0, 8, 0, 7.0, 7.0}, { 21.16, 1190.0,16660.0, 0.0, 0.0, 8.0, 30.0, 8, 0, 8.0, 8.0}, { 0.02908, 467.7,6957.0, 0.0, 0.0, 122.0, 489.0, 12, 0,260.0, 320.0} }; real modelo_cc[][5]= { {0.04528,489.0,-0.07852, 519.3, 245.0} }; int i,j,k,desplazamiento, U_selec,tam,Pi_cod[Us]; real adonde,*vecino,costo_mejor, costo_vecino, Pmin_aux[Us], Pmax_aux[Us], P[Us]; int sol_mej, semilla; real Tot_pot_min, *fitness, movimiento_max, dif_costo,max_baja,max_sube,alfa_RS; double aleatorio, T,boltzman; char sol_ini[60]; FILE *desc_r; if (argc > 1) {semilla = strtoul(argv[1],NULL,10); srand(semilla);} else { srand(time(NULL));} strcpy(sol_ini,"/home/benjamin/tesis/bin/sol_ini.dat"); pob_ini(sol_ini, unidades, 1, RS); /*pob_ini_fc(sol_ini, unidades, modelo_cc, 1, RS);/*arreglar para que escriba reales*/ if ((desc_r=fopen(sol_ini,"r"))==NULL) abort(); for (j=0;j<Us;j++){ /*fscanf(desc_r,"%u", &Pi_cod[j]); P[j]=decodifica(Pi_cod[j], &unidades[j]);}*/ fscanf(desc_r,"%f", &P[j]);} i=0; sol_mej=0; T=500.0; /*mdc=500 Para caso 7 unidades, divisor 1000*/ /*T=50;/*mdc/4=50 para caso 36 unidades, divisor 10000;*/ /*T=50; /*mdc=25,50 divisor 10 para caso 3 Us Punto valvula*/ alfa_RS=0.9;/*0.95 para caso 36 Us; 0.9 para 7u y 3u*/ vecino=crea_vector_real(Us); U_selec=rand_int(0,Us-1); for (i=0; i< Us;i++){ Pmin_aux[i] = unidades[i].Pmin; Pmax_aux[i] = unidades[i].Pmax; if (unidades[i].hay_zm){/* si tiene zona muerta, decide en que region operara */ if (P[i]>unidades[i].ini_zm) /*arriba zona muerta */ Pmin_aux[i] = unidades[i].fin_zm; else /*abajo zona muerta */ Pmax_aux[i]=unidades[i].ini_zm; } } costo_mejor=costo_tot(P, unidades,modelo_cc); adonde=baja; U_selec=rand_int(0,Us-1); movimiento_max=(P[U_selec]-Pmin_aux[U_selec]); k=0; while (T>10.0/pot_uni) { while (k<K0)/*K0: nùmero de iteraciones o transiciones generadas por el algoritmo de generacion)*/ { vecino=vecindad(P,Pmin_aux,Pmax_aux,movimiento_max,U_selec,adonde);/*solucion vecina*/ costo_vecino=costo_tot(vecino, unidades,modelo_cc); dif_costo=costo_mejor-costo_vecino; if (dif_costo>0.0) {

AII-3

copia_vector_real(P,vecino,Us); costo_mejor=costo_vecino; sol_mej++;} else { aleatorio=(double)rand_real(); boltzman=exp(1.0*(double)dif_costo/T); if (aleatorio< boltzman){ copia_vector_real(P,vecino,Us); costo_mejor=costo_vecino;} } /*printf("%f\n",costo_mejor);*/ k=k+1; U_selec=rand_int(0,Us-1); if (rand_real()>0.5) {adonde=sube; movimiento_max=(Pmax_aux[U_selec]-P[U_selec]);} else {adonde=baja; movimiento_max=(P[U_selec]-Pmin_aux[U_selec]);} } T=alfa_RS*T; k=0; } printf("# soluciones vecinas mejores: %u\n",sol_mej); for (i=0;i<Us;i++) printf("P%d: %f\n",i,P[i]); corta_vector_real(vecino); return(0); } Algoritmo GRASP . grasp.c #include "ag.h" int main(int argc,char **argv) { int Nmax_itr,mejores,i, semilla; real *Psol, *Pmejor,Pmin_aux[Us], Pmax_aux[Us]; real fcosto_mejor, fcosto; Unidad unidades []= { { 1.28, 368.0, 22770.0, 0.0, 0.0, 40.0, 160.0, 11, 0, 40.0, 40.0}, { 0.5635, 158.5,33830.0, 0.0, 0.0, 62.0, 248.0, 11, 0, 62.0, 62.0}, { 0.5635, 158.5,33830.0, 0.0, 0.0, 62.0, 248.0, 11, 0, 62.0, 62.0}, { 24.92, 1154.0,13330.0, 0.0, 0.0, 7.0, 27.0, 8, 0, 7.0, 7.0}, { 19.45, 1204.0,16680.0, 0.0, 0.0, 7.0, 26.0, 8, 0, 7.0, 7.0}, { 21.16, 1190.0,16660.0, 0.0, 0.0, 8.0, 30.0, 8, 0, 8.0, 8.0}, { 0.02908, 467.7,6957.0, 0.0, 0.0, 122.0, 489.0, 12, 0,260.0, 320.0} }; real modelo_cc[][5]= { {0.04528,489.0,-0.07852, 519.3, 245.0} }; Nmax_itr=300; mejores=0; fcosto_mejor=9999999.; Psol=crea_vector_real(Us); Pmejor=crea_vector_real(Us); if (argc > 1) {semilla = strtoul(argv[1],NULL,10); srand(semilla);} else { srand(time(NULL));} for (i=0;i<=Nmax_itr;i++){ fase_constructora(unidades, modelo_cc, Psol, Pmin_aux, Pmax_aux); fase_BL(unidades, modelo_cc, Psol, Pmin_aux, Pmax_aux);

AII-4

fcosto=costo_tot(Psol, unidades, modelo_cc); /*printf("%f\n",fcosto);*/ if (fcosto<fcosto_mejor){ fcosto_mejor=fcosto; copia_vector_real(Pmejor,Psol,Us); mejores++; } } for (i=0;i<Us;i++) printf("V%d: %f\n",i,Pmejor[i]); printf("# soluciones mejores: %u\n",mejores); corta_vector_real(Psol); corta_vector_real(Pmejor); salir(); return (0); } Algoritmo de búsqueda local . “BL.c”. #include "ag.h" /*Busca mejor solucion del AG y hace una busqueda en sus vecindades */ short busqueda_local(short poblacion[][Us],real evaluaciones[][2],Unidad *unidades,real modelo_cc[][5], real *P_sol) { int i,k, U_selec,*indices; real *P,adonde,*vecino, costo_mejor, costo_vecino, Pmin_aux[Us], Pmax_aux[Us]; short sol_mej,mejor; real movimiento_max, dif_costo,dp[Tam_pob]; indices=crea_vector_int(Tam_pob); P=crea_vector_real(Us); for (i=0;i<Tam_pob;i++) { dp[i]= evaluaciones[i][1]; indices[i]=i; } ordena(indices,dp,1,Tam_pob);/*ordena dp, indices guarda las posiciones originales;*/ /*mejor=0; while ((mejor<Tam_pob)&&(dp[mejor]>=0.1)) { mejor++;}*/ if (dp[0]>=0.1) return(0); else { /*printf("Encontre uno\n");*/ for (i=0;i<Us;i++) { P[i]=decodifica(poblacion[indices[0]][i],&unidades[i]); /*printf("V%d: %f\n",i,P[i]);*/} k=0; sol_mej=0; vecino=crea_vector_real(Us); for (i=0; i< Us;i++){ Pmin_aux[i] = unidades[i].Pmin; Pmax_aux[i] = unidades[i].Pmax; if (unidades[i].hay_zm){/* si tiene zona muerta, decide en que region operara */ if (P[i]>unidades[i].ini_zm) /*arriba zona muerta */ Pmin_aux[i] = unidades[i].fin_zm; else /*abajo zona muerta */ Pmax_aux[i]=unidades[i].ini_zm; } } costo_mejor=costo_tot(P, unidades,modelo_cc); adonde=baja; U_selec=rand_int(0,Us-1); movimiento_max=(P[U_selec]-Pmin_aux[U_selec]); P[Us-1]=P[Us-1]+ DP_NA(P); while (k<K0)/*K0: numero de transiciones del algoritmo de generacion)*/

AII-5

{ vecino=vecindad(P,Pmin_aux,Pmax_aux,movimiento_max,U_selec,adonde);/*solucion vecina*/ costo_vecino=costo_tot(vecino, unidades,modelo_cc); dif_costo=costo_mejor-costo_vecino; if (dif_costo>0.0){ copia_vector_real(P,vecino,Us); costo_mejor=costo_vecino; /*for (i=0;i<Us;i++) printf("V%d: %f\n",i,vecino[i]); printf("costoV: %f\n",costo_vecino);*/ sol_mej++;} k=k+1; U_selec=rand_int(0,Us-1); if (rand_real()>0.5) {adonde=sube; movimiento_max=(Pmax_aux[U_selec]-P[U_selec]);} /*max_sube*/ else {adonde=baja; movimiento_max=(P[U_selec]-Pmin_aux[U_selec]);} /*max_baja*/ } copia_vector_real(P_sol,P,Us); /*printf("# soluciones vecinas mejores: %u\n",sol_mej);*/ /*corta_vector_real(vecino); corta_vector_real(P); corta_vector_short(indices);*/ return(1); } } “pob_ini_nf2.c”. /************************************************************************************ * Programa pob_ini_nf2: Genera aleatoriamente una poblacion inicial con soluciones * * no factibles. Cada cromosoma consta de N enteros cortos, que representan la * * potencia de cada unidad generadora * ************************************************************************************/ #include "ag.h" void pob_ini2(short poblacion[][Us], Unidad *unidades, int Total,bool algortimo) { short i,j; for (j=0;j<Total;j++) { for (i=0;i<Us;i++) { poblacion[j][i] = (short)rand_int(0,(int)pow(2.0,unidades[i].L)-1); if (unidades[i].hay_zm){/* si tiene zona muerta, decide en que region operara */ if (rand_real()>0.5) /*arriba zona muerta */ poblacion[j][i] = poblacion[j][i]+ (short)pow(2.0,unidades[i].L); } } } } “pob_ini_fc.c”. /************************************************************************************ * Programa pob_ini_fc: Genera poblacion inicial con soluciones factibles a partir * * de la fase constructora del GRASP * ************************************************************************************/ #include "ag.h" void pob_ini_fc(char *archivo, Unidad *unidades, real modelo_cc[][5], int Total, bool algoritmo_G) { short i,j;

AII-6

short P_cod; FILE *desc; real P_sol[Us],Pmin_aux[Us], Pmax_aux[Us]; desc=fopen(archivo,"w"); for (j=0;j<Total;j++) { fase_constructora(unidades, modelo_cc, P_sol, Pmin_aux, Pmax_aux); for (i=0;i<Us;i++) { if (!algoritmo_G) {fprintf(desc,"%f ",P_sol[i]);} else {P_cod = codifica(P_sol[i], &unidades[i]); fprintf(desc,"%u ",P_cod);} } fprintf(desc,"\n"); } fclose(desc); } “pob_ini.c”. /************************************************************************************ * Programa pob_ini: Genera poblacion inicial con soluciones factibles por algoritmo * * de satisfaccion de restricciones. * ************************************************************************************/ #include "ag.h" void nuevos_limites(int , real *, real *, real *, real *, real); void pob_ini(char *archivo, Unidad *unidades, int Total, bool algoritmo) { short i,j; short P_cod; FILE *desc; real dr,P_real,NPmin,NPmax; real Paux_min [Us], Paux_max[Us]; desc=fopen(archivo,"w"); for (j=0;j<Total;j++) { dr= Demanda; for (i=0; i< Us;i++){ Paux_min[i] = unidades[i].Pmin; Paux_max[i] = unidades[i].Pmax; if (unidades[i].hay_zm){/* si tiene zona muerta, decide en que region operara */ if (rand_real()>0.5) /*arriba zona muerta */ Paux_min[i] = unidades[i].fin_zm; else /*abajo zona muerta */ Paux_max[i]=unidades[i].ini_zm; } } for (i=0;i<Us-1;i++) { nuevos_limites(i, Paux_min, Paux_max, &NPmin, &NPmax, dr); P_real = NPmin+rand_real()*(NPmax-NPmin); if (algoritmo) {P_cod = codifica(P_real, &unidades[i]); fprintf(desc,"%u ",P_cod);} else {fprintf(desc,"%f ",P_real);} dr = dr-P_real; } if (algoritmo) {P_cod = codifica(dr, &unidades[i]); fprintf(desc,"%u ",P_cod);} else {fprintf(desc,"%f ",dr);}

AII-7

fprintf(desc,"\n"); } fclose(desc); } /* Calcula los nuevos limites de una unidad, de acuerdo con las asignaciones de potencia */ void nuevos_limites(int unidad, real *Pmin,real *Pmax, real *NLmin,real *NLmax ,real dem) { real suma_min, suma_max; int j; suma_min= 0.0; suma_max= 0.0; for (j=unidad+1; j< Us;j++) { suma_min = suma_min + Pmin[j]; suma_max = suma_max + Pmax[j]; } *NLmax = dem - suma_min; *NLmin = dem - suma_max; if (*NLmax>Pmax[unidad]) *NLmax=Pmax[unidad]; if (*NLmin<Pmin[unidad]) *NLmin=Pmin[unidad]; } “evaluacion2.c”. #include "ag.h" void evaluacion2(short poblacion[][Us], real aptitudes[][2], Unidad *unidades, real modelo_cc[][5]) { int i,j; int Pi_cod; real P_ini[Us], fc[Tam_pob], desbalance[Tam_pob]; real fct, fitness, mejor_fitness,suma_fitness,desbalance_mf,PF_zm[Tam_pob]; bool u_zm[]= {0,0,0,0,0,0,1}; /*bool u_zm[]= {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};*/ /* cuando se codifica zona muerta, poner u_zm en ceros y unidades.hay_zm = 1 en U's con zm */ /* cuando se trata por penalizacion, poner u_zm=1 y unidades.hay_zm = 0 en U's con zm */ for (i=0;i<Tam_pob;i++) { PF_zm[i]=0.0; for (j=0;j<Us;j++) { P_ini[j]=decodifica((short)poblacion[i][j], &unidades[j]); if (u_zm[j]){ if ((P_ini[j] > unidades[j].ini_zm) && (P_ini[j] < unidades[j].fin_zm)) PF_zm[i]=0.1; } } fc[i]=costo_tot(P_ini, unidades, modelo_cc); desbalance[i]=DP(P_ini); } mejor_fitness=9999999999.; suma_fitness=0.; for (i=0;i<Tam_pob;i++) { fitness=fc[i]+PF*desbalance[i]+PF_zm[i]*fc[i]; if (fitness<mejor_fitness) { mejor_fitness=fitness; desbalance_mf=desbalance[i];} suma_fitness=suma_fitness+fitness; aptitudes[i][0]=fitness; aptitudes[i][1]=desbalance[i]; }

AII-8

printf("%f %f %f\n",mejor_fitness, suma_fitness/(real)Tam_pob,desbalance_mf); } “selec_torneo2.c”. /******************************************************************************* * Crea una poblacion de padres para la siguiente generacion. * * Escoge de forma aleatoria a 2 individuos de la poblacion y selecciona al de * * mejor aptitud * *******************************************************************************/ #include "ag.h" void selec_torneo2(short poblacion[][Us], real aptitudes[][2], short *ganador) { int *indices, tam, competidor1, competidor2,torneos; real fitness[Tam_pob]; int i,j; indices=crea_vector_int(Tam_pob); /* guarda la posicion original de los individuos */ torneos=Tam_pob; for (i=0;i<Tam_pob;i++) /*lee aptitudes e inicializa indices*/ { fitness[i]=aptitudes[i][0]; indices[i]=i;} /*elitismo*/ if (elitismo) torneos=torneos-1; /*elige aleatoriamente elementos a competir y selecciona a los ganadores*/ for (i=0;i<torneos;i++)/* -1 por elitismo */ { competidor1=rand_int(0,Tam_pob-1); competidor2=rand_int(0,Tam_pob-1); if (fitness[competidor1]<fitness[competidor2]) ganador[i]=competidor1; else ganador[i]= competidor2; } /*Elitismo, escribe al final al mejor individuo*/ if (elitismo) { ordena(indices,fitness,1,Tam_pob); ganador[i]=indices[0]; } } “hijos2.c”. /**************************************************************************************** * Crea a la siguiente generacion a partir de la poblacion de padres. A esta les aplica * * los operadores de cruza y mutacion * ***************************************************************************************** #include "ag.h" void hijos2(short poblacion[][Us],short ganador[], short nueva_poblacion[][Us], Unidad *unidades, real Pcruza, real Pmuta) { int i,j,tot_hijos,long_cadena; short **ap_pob, **ap_nuevapob; long_cadena=0; /*for (i=0;i<Us;i++) long_cadena= long_cadena+unidades[i].L+unidades[i].hay_zm;*/ tot_hijos=Tam_pob; /*elitismo*/ if (elitismo)

AII-9

tot_hijos=tot_hijos-2; for (i=0;i<tot_hijos;i=i+2) { cruza_1(&poblacion[ganador[i]][0], &poblacion[ganador[i+1]][0], &nueva_poblacion[i][0], &nueva_poblacion[i+1][0], Pcruza); for (j=0;j<Us;j++) { nueva_poblacion[i][j] = mutacion(nueva_poblacion[i][j],unidades[j].L,unidades[j].hay_zm,Pmuta); nueva_poblacion[i+1][j] = mutacion(nueva_poblacion[i+1][j],unidades[j].L,unidades[j].hay_zm,Pmuta); } } /*ELITISMO, pasan a la siguiente generacion 2 ultimos individuos, el ultimo es el mejor individuo*/ if (elitismo){ for (i=0;i<Us;i++){ nueva_poblacion[tot_hijos][i]=poblacion[ganador[tot_hijos]][i]; nueva_poblacion[tot_hijos+1][i]=poblacion[ganador[tot_hijos+1]][i];} } } Encabezados “ag.h” /****************************************************************************** * Contiene los encabezados de los procedimientos, tipos de datos, * * definicion de valores de parametros * ******************************************************************************/ /* headers requeridos */ #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <math.h> #include <fcntl.h> #include "aleatorio.h" #include "salir.h" /*Parametros generales*/ #define Demanda 700.0 #define Us 7 #define Nterm 6 #define Ncc 1 #define AG 1 #define RS 0 #define pot_uni 1000.0 /*RS: 1000 7u*/ /*10000.0 36u*/ /* 100.0 para 3u pv*/ /*Parametros AG */ #define Tam_pob 40 /*numero par*/ #define PF 2.500 /*7u (2.5), 36u (.0563), 25 (3upv) */ #define elitismo 1 /*Parametros BL*/ #define K0 500 #define sube 1.0 #define baja -1.0 /*Parametros GRASP*/ #define alfa 0.5 struct generador { real coef_a; real coef_b; real coef_c; real coef_e; real coef_f; real Pmin; real Pmax; int L;

AII-10

bool hay_zm; real ini_zm; real fin_zm; /*bool es_CC;*/ }; struct RT_CC { real puntos [10][2]; }; typedef struct generador Unidad; typedef struct RT_CC Reg_term_CC; /* Prototipos de las funciones */ void pob_ini(char *, Unidad *, int, bool); void pob_ini2(short [Tam_pob][Us], Unidad *, int, bool); void pob_ini_fc(char *, Unidad *, real [][5], int ,bool ); void evaluacion(char *, char *, Unidad *, real [][5]); void evaluacion2(short [Tam_pob][Us], real [Tam_pob][2], Unidad *, real [][5]); void selec_torneo(char *, char *, char *); void selec_torneo2(short [][Us], real [][2], short *); void hijos(char *, char *, Unidad *, real , real ); void hijos2(short [][Us],short *, short [][Us], Unidad *, real, real); short busqueda_local(short [][Us],real [][2],Unidad *,real [][5], real *); real *vecindad(real *,real *, real *,real , int , real ); void fase_constructora(const Unidad *, real [][5], real *, real *, real *); void fase_BL(const Unidad *, real [][5], real *, real *, real *); void ruleta(int *, real *,int *); void error1(void); void errorn(void); void error_opcion(void); int cuad(int); short complemento(short); short vector_bits_a_short(short *,int); short *short_a_vector_bits(short,int); short mutacion(short, int, bool, real); void cruza(short *, short *, short *, short *, const Unidad *, int , real ); void cruza_1(short *, short *, short *, short *, real ); void copia_normal(short *, short *, short *, short *, int , int ); void copia_cruzado(short *, short *, short *, short *, int , int ); real decodifica(short , const Unidad *); short codifica(real , const Unidad *); real fx(real *,real [][3]); void f_recta(real ,real ,real ,real , real *, real *); real DP(real *); real DP_NA(real *); real costo_tot(real *, const Unidad *, real [][5]); int subir(real *, int , real , real *, real *, short *); int bajar(real *, int , real , real *, real *, short *); real fitnessK(real *,const Unidad *, real [][5]); void estandariza(real *); int particion_vector(int *, real *, short, short); void ordena(int *, real *, int , int); void N_lim(real *, real *, real *, real * , real ,int *, int ); Utilerias “Util.c” #include "ag.h" /********** Calcula el cuadrado de un numero entero **************/ int cuad(int x) { return (x^2);

AII-11

} real fx(real *P,real modelo_term[][3]) { real Fct; int i; Fct= 0; for (i=0;i<Nterm;i++) { Fct=Fct+modelo_term[i][0]*P[i]*P[i]+modelo_term[i][1]*P[i]+modelo_term[i][2]; } return (Fct); } real DP(real *P) { int i; real suma_P, desbalance; suma_P=0; for (i=0;i<Us;i++) { suma_P=suma_P+P[i]; } desbalance=absol(Demanda-suma_P); return (desbalance); } real DP_NA(real *P) { int i; real suma_P, desbalance; suma_P=0; for (i=0;i<Us;i++) { suma_P=suma_P+P[i]; } desbalance=Demanda-suma_P; return (desbalance); } void f_recta(real x1,real y1,real x2,real y2, real *m, real *b) { *m = (y2-y1)/(x2-x1); *b = y1-*m*x1; } real costo_tot(real *P, const Unidad *unidades, real modelo_cc[][5]) { /*El arreglo model_cc tiene los parametros de las 2 rectas m,b, y el punto P2 */ /* P2 es el punto donde cambia la pendiente o punto comun a las dos rectas)*/ /* modelo_cc[i,j] = {m1,b1,m2,b2,P2}*/ real costo_cc,costo_term,costo; int i; costo_cc=0.; costo_term= 0.; costo=0.; for (i=0;i< Nterm;i++) { /*costo_term=costo_term+(unidades[i].coef_a*P[i]*P[i]+unidades[i].coef_b*P[i]+unidades[i].coef_c)/pot_uni;*/ costo_term=costo_term+(unidades[i].coef_a*P[i]*P[i]+unidades[i].coef_b*P[i]+unidades[i].coef_c+absol(unidades[i].coef_e*sin(unidades[i].coef_f*(unidades[i].Pmin-P[i]))))/pot_uni; }

AII-12

for (i=0;i < Ncc; i++) { if (P[Nterm+i]<=modelo_cc[i][4]) /*P > P2*/ costo_cc= costo_cc+(P[Nterm+i]*(modelo_cc[i][0]*P[Nterm+i]+modelo_cc[i][1]))/pot_uni; /* P(m1 P + b1) */ else costo_cc= costo_cc+(P[Nterm+i]*(modelo_cc[i][2]*P[Nterm+i]+modelo_cc[i][3]))/pot_uni; /* P(m2 P + b2) */ } costo=costo_term+costo_cc; return costo; } int subir(real *Pot, int U, real cantidad, real *max_baja, real *max_sube,short *idx) { int i; real desp_x,x; /*if (cantidad>max_sube[U]) x=max_sube[U]; else x=cantidad;*/ x=cantidad; if (x>0.1) { desp_x=rand_real() * x; x=desp_x; /*printf("U%d sube:%f MW\n",U,desp_x);*/ Pot[idx[0]]=Pot[idx[0]]+sube*desp_x; for (i=1;i<Us-1;i++) { desp_x=rand_real() * x; if (desp_x>max_baja[idx[i]]) desp_x=max_baja[idx[i]]; Pot[idx[i]]=Pot[idx[i]]+baja*desp_x; x=x-desp_x; if (x<0.01) break; } if (x>max_baja[idx[Us-1]]) return 0; else { Pot[idx[Us-1]]=Pot[idx[Us-1]]+baja*x; return 1;} } return 0; } int bajar(real *Pot, int U, real cantidad, real *max_baja, real *max_sube, short *idx) { int i; real desp_x, x; /*if (cantidad>max_baja[U]) x=max_baja[U]; else*/ x=cantidad; if (x>0.01) /*basta conque x<>0), se supone que no puede tomar valores negativos)*/ { desp_x=rand_real() * x; x=desp_x; /*printf("U%d baja:%f MW\n",U,desp_x);*/ Pot[idx[0]]=Pot[idx[0]]+baja*desp_x; for (i=1;i<Us-1;i++){ desp_x=rand_real() * x; if (desp_x>max_sube[idx[i]]) desp_x=max_sube[idx[i]]; Pot[idx[i]]=Pot[idx[i]]+sube*desp_x; x=x-desp_x; if (x<0.01) break; }

AII-13

if (x>max_sube[idx[Us-1]]) return 0; else {Pot[idx[Us-1]]=Pot[idx[Us-1]]+sube*x; return 1;} } return 0; } real fitnessK(real *P_sol,const Unidad *unidades, real modelo_cc[][5]) { real fitness,costo_FPK; int i; real suma_P; fitness= 0.; suma_P=0; for (i=1;i<=Us;i++) { suma_P=suma_P+P_sol[i]; } costo_FPK=absol(PF*(suma_P-Demanda)); /*PF factor de penalizacion K*/ fitness=costo_tot(P_sol,unidades,modelo_cc)+costo_FPK; return (fitness); } real *vecindad(real *Psol,real *Pmin, real *Pmax,real tam_mov, int U_selec, real adonde) { int i,exito,contador; real *P, *incr_max,*decr_max; short *indice ; P=crea_vector_real(Us); incr_max=crea_vector_real(Us); decr_max=crea_vector_real(Us); copia_vector_real(P,Psol,Us); indice=crea_vector_short(Us); contador=0; do { for (i=0;i<Us;i++) { indice[i]=i; incr_max[i]=Pmax[i]-P[i]; decr_max[i]=P[i]-Pmin[i]; } indice[0]=U_selec; indice[U_selec]=0; if (adonde==sube) exito=subir(P, U_selec, tam_mov, decr_max, incr_max, indice); else exito=bajar(P, U_selec, tam_mov, decr_max, incr_max, indice); if (exito==0) {copia_vector_real(P,Psol,Us); contador++;} }while ((exito==0) && (contador<10)); corta_vector_short(indice); corta_vector_real(incr_max); corta_vector_real(decr_max); return (P); } void ruleta(int *indices, real *fitness, int *lista_seleccion) { int i,j; real ref_aleat, *fitness_acum, suma, min, max; /*fitness normalizado y acumulado */

AII-14

fitness_acum=crea_vector_real(Tam_pob); min=min_vector(fitness,Tam_pob); max=max_vector(fitness,Tam_pob); /*Seleccion por jerarquìa, habilitar si fitness bajo es mejor y deshabilitar (a) */ /*for (i=0;i<Tam_pob;i++) fitness_acum[i]=min+((max-min)*(real)(Tam_pob-i))/(real)(Tam_pob-1);*/ copia_vector_real(fitness_acum,fitness,Tam_pob); /* (a) */ suma=suma_vector(fitness_acum,Tam_pob); for (i=0;i<Tam_pob;i++) fitness_acum[i]=fitness_acum[i]/suma; for (i=1;i<Tam_pob;i++) fitness_acum[i]=fitness_acum[i]+fitness_acum[i-1]; /*seleccion por ruleta*/ srand( (int)suma ); for (j=0;j<Tam_pob;j++) { ref_aleat=rand_real(); if (j==0) printf("random: %f\n",ref_aleat); for (i=0;i<Tam_pob;i++) { if (fitness_acum[i]>ref_aleat) { lista_seleccion[j]=indices[i]; break;} } } corta_vector_real(fitness_acum); } short complemento(short bit) { if (bit==0) return 1; else return 0; } /* convierte un vector de bits en un numero entero*/ short vector_bits_a_short(short *bits, int l) { int i; short numero; numero=bits[l-1]; for(i=l-2;i>=0;i--) { numero=numero<<1; numero=numero|bits[i]; } return (numero); } /* guarda cada bit de un entero corto en un vector*/ short *short_a_vector_bits(short numero, int l_subcadena) { int i; short *bits; bits=crea_vector_short(l_subcadena); for (i=0;i<l_subcadena;i++) { bits[i]=numero&1; numero=numero>>1; } return (bits); } short mutacion(short cromosoma, int l_subcadena, bool hay_zm,real P_mutacion)

AII-15

{ short aux,*bits; int i; short prueba; /*l_subcadena no incluye bit de zona muerta */ bits=short_a_vector_bits(cromosoma, l_subcadena+hay_zm);/*tambien puede mutar bit_zm*/ for(i=0;i<l_subcadena;i++){ if (rand_real()<P_mutacion) bits[i]=complemento(bits[i]);} aux=vector_bits_a_short(bits,l_subcadena+hay_zm); corta_vector_short(bits); return aux; } /* cruza 2 individuos para generar 2 hijos; punto_cruza:aleatorio*/ /* el punto de cruza es a nivel de bits de la cadena completa*/ /* */ void cruza(short *P1, short *P2, short *h1, short *h2, const Unidad *unidades, int l_tot, real Pcruza) { short *upper, *lower, copiador_alto, copiador_bajo; int i, punto_cruza, unidad, modulo,bits; real aleatorio; unidad=-1; bits=0; aleatorio=rand_real(); if (aleatorio<Pcruza) { punto_cruza=rand_int(1,l_tot); do { unidad = unidad + 1; bits=bits+unidades[unidad].L+unidades[unidad].hay_zm; }while (bits<punto_cruza); modulo=bits-punto_cruza; /*crea copiadores de bits de acuerdo a punto de cruza*/ upper=crea_vector_short(unidades[unidad].L+unidades[unidad].hay_zm); lower=crea_vector_short(unidades[unidad].L+unidades[unidad].hay_zm); for (i=0;i<modulo;i++){ upper[i]=0; lower[i]=1;} for (i=modulo;i<(unidades[unidad].L+unidades[unidad].hay_zm);i++){ upper[i]=1; lower[i]=0;} copiador_alto=vector_bits_a_short(upper,unidades[unidad].L+unidades[unidad].hay_zm); copiador_bajo=vector_bits_a_short(lower,unidades[unidad].L+unidades[unidad].hay_zm); for (i=0;i<unidad;i++) /*unidad-1*/ {h1[i]=P1[i]; h2[i]=P2[i];} h1[unidad]=P1[unidad]&copiador_alto|P2[unidad]&copiador_bajo; h2[unidad]=P2[unidad]&copiador_alto|P1[unidad]&copiador_bajo; for (i=unidad+1;i<Us;i++)/*unidad*/ {h1[i]=P2[i]; h2[i]=P1[i];} corta_vector_short(upper); corta_vector_short(lower); } else { copia_vector_short(h1,P1,Us); copia_vector_short(h2,P2,Us); } } /* cruza 2 individuos para generar 2 hijos; 2 puntos de cruza aleatorios*/ /* se combinan unidades */ /* zona muerta se pasa de padre a hijo */ void cruza_1(short *P1, short *P2, short *h1, short *h2, real Pcruza) { real aleatorio; int pc_1, pc_2, aux;

AII-16

aleatorio=rand_real(); if (aleatorio<Pcruza) { pc_1=rand_int(0,Us-1); pc_2=rand_int(0,Us-1); if (pc_2<pc_1){ aux=pc_1; pc_1=pc_2; pc_2=aux;} copia_normal(P1, P2, h1, h2, 0, pc_1); copia_cruzado(P1, P2, h1, h2, pc_1+1, pc_2); copia_normal(P1, P2, h1, h2, pc_2+1, Us-1); } else { copia_vector_short(h1,P1,Us); copia_vector_short(h2,P2,Us); } } void copia_normal(short *P1, short *P2, short *h1, short *h2, int desde, int hasta) { int i; for (i=desde;i<=hasta;i++){ h1[i]=P1[i]; h2[i]=P2[i];} } void copia_cruzado(short *P1, short *P2, short *h1, short *h2, int desde, int hasta) { int i; for (i=desde;i<=hasta;i++){ h1[i]=P2[i]; h2[i]=P1[i];} } /****decodifica: decodifica valor entero corto a valor real de Potencia **************/ real decodifica(short x, const Unidad *unidades) { real valor, Pmin_aux, Pmax_aux; short suma, bit_1; suma=0; Pmin_aux= unidades->Pmin; Pmax_aux= unidades->Pmax; bit_1 = (short)(pow(2.0,(double)unidades->L)); if (unidades->hay_zm) {/*revisa si hay zona muerta*/ if (x >= bit_1){ Pmin_aux = unidades->fin_zm;/* arriba zona muerta */ suma =bit_1;} else {Pmax_aux = unidades->ini_zm;} /* valor abajo de zona muerta */ } x=x-suma; valor=Pmin_aux+((real)x*(Pmax_aux-Pmin_aux))/((pow(2.0,(double)unidades->L)-1.0)); return (valor); } /****codifica: codifica valor real de Potencia a entero corto **************/ short codifica(real valor, const Unidad *unidades) { short x,suma; real Pmin_aux, Pmax_aux; suma=0; Pmin_aux= unidades->Pmin;

AII-17

Pmax_aux= unidades->Pmax; if (unidades->hay_zm) {/*revisa si hay zona muerta*/ if (valor >= unidades->fin_zm){ Pmin_aux = unidades->fin_zm; suma =(short)(pow(2.0,(double)unidades->L));}/*indicara zona muerta */ else {Pmax_aux = unidades->ini_zm;} } x = (short)((valor-Pmin_aux)*(pow(2.0,(double)unidades->L)-1.0)/(Pmax_aux-Pmin_aux)); x= x+suma;/* si hay zona muerta, pone bit L en 1, con el valor de suma */ return (x); } void estandariza(real *fi) { int i,negativo; real suma, suma_abs, promedio_abs, min_abs; /* l=long_vector(fi);*/ negativo=0; /*falso */ /* verifica si hay un numero negativo*/ for (i=0;i<Tam_pob;i++) { if (fi[i]<0.0) { negativo=1; /*verdadero*/ break; } } /*estandariza el vector si hay valores negativos */ if (negativo==1) { suma_abs=suma_abs_vector(fi,Tam_pob); promedio_abs=suma_abs/(real)Tam_pob; min_abs=minimo_abs_vector(fi,Tam_pob); for (i=0;i<Tam_pob;i++) fi[i]=fi[i]+promedio_abs+min_abs; } } int particion_vector(int *subindices,real *subvector, short pos_ini, short pos_fin) { short i, menores , mayores, tam, val_ind, *aux_ind ; short pos_pivote; real *vector_aux, val_pivote; menores=0; mayores=0; tam=pos_fin-pos_ini+1;/* indice de subvector: 0..tam*/ vector_aux=crea_vector_real(tam); aux_ind=crea_vector_short(tam);/** añadido*/ pos_pivote=pos_ini-1;/*-1 porque indice del vector comienza en 0 */ val_pivote=subvector[pos_pivote]; /* se toma como pivote al primer elemento */ val_ind=subindices[pos_pivote];/** añadido*/ for (i=pos_ini;i<pos_fin;i++) { if (subvector[i]<val_pivote) { vector_aux[menores]=subvector[i]; aux_ind[menores] =subindices[i];/** añadido*/ menores++; } else { vector_aux[pos_fin-pos_ini-mayores]=subvector[i]; aux_ind[pos_fin-pos_ini-mayores]=subindices[i];/** añadido*/

AII-18

mayores++; } } /* se copia vector_aux en subvector con particion de acuerdo a pivote*/ pos_pivote=pos_ini+menores; vector_aux[menores]=val_pivote; aux_ind[menores]=val_ind;/** añadido*/ for (i=pos_ini-1;i<pos_fin;i++) {subvector[i]=vector_aux[i-pos_ini+1]; subindices[i]=aux_ind[i-pos_ini+1];/** añadido*/} corta_vector_real(vector_aux); corta_vector_short(aux_ind); return pos_pivote; } void ordena(int *indices, real *vector, int pos_ini, int pos_fin) { int pivote; if (pos_fin>pos_ini) { pivote=particion_vector(indices,vector, pos_ini, pos_fin); ordena(indices,vector, pos_ini, pivote-1); ordena(indices,vector, pivote+1, pos_fin); } } void N_lim(real *Lmin, real *Lmax, real *NLmin, real *NLmax , real dem,int *Id, int n) { real suma_min, suma_max; int i,j; suma_min= 0.0; suma_max= 0.0; for (i=0; i<n; i++) { suma_min = suma_min + Lmin[Id[i]]; suma_max = suma_max + Lmax[Id[i]]; } for (j=0; j< n;j++) { NLmax[Id[j]]= dem - suma_min + Lmin[Id[j]]; NLmin[Id[j]]= dem - suma_max + Lmax[Id[j]]; if (NLmax[Id[j]] > Lmax[Id[j]]) NLmax[Id[j]] = Lmax[Id[j]]; if (NLmin[Id[j]] < Lmin[Id[j]]) NLmin[Id[j]] = Lmin[Id[j]]; } } void fase_constructora(const Unidad *unidades,real modelo_cc[][5],real *Psol, real *Paux_min, real *Paux_max) { int *C,*RCL; int N,tam_RCL,i,j,k,Pos_RCL_selec; real *Paleat,*fmiope,*NLmax,*NLmin; /*real Paux_min [Us], Paux_max[Us]; */ real smin,smax, criterioRCL,dem_resto; C=crea_vector_int(Us); RCL=crea_vector_int(Us); NLmax=crea_vector_real(Us); NLmin=crea_vector_real(Us); Paleat=crea_vector_real(Us); fmiope=crea_vector_real(Us); N=Us; dem_resto=Demanda;

AII-19

/*Inicializa conjunto candidato C*/ for (i=0;i<N;i++) C[i]=i; for (i=0; i< Us;i++){ Paux_min[i] = unidades[i].Pmin; Paux_max[i] = unidades[i].Pmax; if (unidades[i].hay_zm){/* si tiene zona muerta, decide en que region operara */ if (rand_real()>0.5) /*arriba zona muerta */ Paux_min[i] = unidades[i].fin_zm; else /*abajo zona muerta */ Paux_max[i]=unidades[i].ini_zm; } } for (k=0;k<Us-1;k++) {/*forma solucion, elemento por elemento*/ smin=9999999.9; smax=0; j=0; N_lim(Paux_min, Paux_max, NLmin, NLmax , dem_resto, C, N); for (i=0;i<N;i++) {/*Potencia aleatoria a conjunto C y funcion miope */ Paleat[C[i]]=rr2(NLmin[C[i]],NLmax[C[i]]); fmiope[C[i]]=(unidades[C[i]].coef_a*Paleat[C[i]]*Paleat[C[i]]+unidades[C[i]].coef_b*Paleat[C[i]]+unidades[C[i]].coef_c+absol(unidades[C[i]].coef_e*sin(unidades[C[i]].coef_f*(unidades[C[i]].Pmin-Paleat[C[i]]))))/Paleat[C[i]]; if (fmiope[C[i]]<smin) smin=fmiope[C[i]]; if (fmiope[C[i]]>smax) smax=fmiope[C[i]]; } criterioRCL=smin+alfa*(smax-smin); for (i=0;i<N;i++) {/*Crea conjunto RCL Restricted Candidate List*/ if (fmiope[C[i]]<=criterioRCL) { RCL[j]=C[i]; j++;} } tam_RCL=j; Pos_RCL_selec=rand_int(0,tam_RCL-1);/* seleccion aleatoria de RCL */ Psol[RCL[Pos_RCL_selec]]=Paleat[RCL[Pos_RCL_selec]]; dem_resto=dem_resto-Paleat[RCL[Pos_RCL_selec]]; elimina_int_vector(C ,RCL[Pos_RCL_selec],&N);/*actualiza conjunto candidato C */ inicia_vector_int(RCL,tam_RCL); /*inicializa conjunto RCL */ } Psol[C[0]]=dem_resto;/* potencia asignada a ultimo elemento de conjunto C */ } void fase_BL(const Unidad *unidades, real modelo_cc[][5], real *P, real *Pmin_aux, real *Pmax_aux) { real adonde,*vecino, costo_mejor, costo_vecino; int i,k, U_selec; short sol_mej; real Tot_pot_min, Tot_pot_max,movimiento_max, dif_costo,max_baja,max_sube; k=0; sol_mej=0; vecino=crea_vector_real(Us); /* Tot_pot_min=0; Tot_pot_max=0; for (i=0; i< Us; i++){ Tot_pot_min=Tot_pot_min + unidades[i].Pmin; Tot_pot_max=Tot_pot_max + unidades[i].Pmax;} max_baja=Demanda-Tot_pot_min; max_sube=Tot_pot_max-Demanda;*/ costo_mejor=costo_tot(P, unidades,modelo_cc); adonde=baja; U_selec=rand_int(0,Us-1); movimiento_max=(P[U_selec]-Pmin_aux[U_selec]); while (k<K0)/*K0: numero de iteraciones max del algoritmo de generacion)*/ { vecino=vecindad(P,Pmin_aux,Pmax_aux,movimiento_max,U_selec,adonde);/*solucion vecina*/ costo_vecino=costo_tot(vecino, unidades,modelo_cc);

AII-20

dif_costo=costo_mejor-costo_vecino; if (dif_costo>0.0){ copia_vector_real(P,vecino,Us); costo_mejor=costo_vecino; sol_mej++;} k=k+1; U_selec=rand_int(0,Us-1); if (rand_real()>0.5) {adonde=sube; movimiento_max=(Pmax_aux[U_selec]-P[U_selec]);} /*max_sube*/ else {adonde=baja; movimiento_max=(P[U_selec]-Pmin_aux[U_selec]);} /*max_baja*/ } /* copia_vector_real(P_sol,P,Us);/* No es necesario, revisar al unificar con busqueda_local */ /* printf("# soluciones vecinas mejores: %u\n",sol_mej);*/ corta_vector_real(vecino); } /************** Rutinas de manejo de errores.**********************/ void error1(void) { perror("\a Faltan argumentos \n"); abortar(); } void errorn(void) { perror("\a Demasiados argumentos \n"); abortar(); } void error_opcion(void) { perror("\a Opción invalida\n"); abortar(); } Archivos de descripción “make_AG” #************************************************************************ #* Compila el programa de Algortimo Genetico con poblacion inicial * #* de soluciones no factibles generadas de forma aleatoria * #************************************************************************ COMPILADOR=gcc FUENTE= $(HOME)/tesis/fuente/util/util.c $(HOME)/tesis/fuente/pob_ini/pob_ini_nf2.c $(HOME)/tesis/fuente/evaluacion/evaluacion2.c $(HOME)/tesis/fuente/seleccion/selec_torneo2.c $(HOME)/tesis/fuente/hijos/hijos2.c AG2.c OBJS=$(FUENTE:.c=.o) HEADER= ag.h LIB=GA PROG=AG2 CC: $(OBJS) $(COMPILADOR) $(OBJS) -L$(HOME)/tesis/lib -l$(LIB) -lm -o $(HOME)/tesis/bin/$(PROG) @- echo "Compilación terminada" LIMPIA: @- rm -f $(OBJS) @- echo "Borrado de objetos terminado"

AII-21

BORRA: @- rm -f $(OBJS) $(PROG) @- echo "Borrado de archivos terminado" .c.o: $(COMPILADOR) -g -I$(HOME)/tesis/fuente/incl/ -c $*.c -o $*.o $(OBJS): $(HOME)/tesis/fuente/incl/$(HEADER) $(HOME)/tesis/lib/lib$(LIB).a “make_AGH” #********************************************************************************* #* Compila el programa de Algoritmo Genetico Hibrido con poblacion inicial * #* de soluciones no factibles generadas de forma aleatoria. * #********************************************************************************* COMPILADOR=gcc FUENTE= $(HOME)/tesis/fuente/util/util.c $(HOME)/tesis/fuente/pob_ini/pob_ini_nf2.c $(HOME)/tesis/fuente/evaluacion/evaluacion2.c $(HOME)/tesis/fuente/seleccion/selec_torneo2.c $(HOME)/tesis/fuente/hijos/hijos2.c $(HOME)/tesis/fuente/BL/busqueda_local.c AGH.c OBJS=$(FUENTE:.c=.o) HEADER= ag.h LIB=GA PROG=AGH CC: $(OBJS) $(COMPILADOR) $(OBJS) -L$(HOME)/tesis/lib -l$(LIB) -lm -o $(HOME)/tesis/bin/$(PROG) @- echo "Compilación terminada" LIMPIA: @- rm -f $(OBJS) @- echo "Borrado de objetos terminado" BORRA: @- rm -f $(OBJS) $(PROG) @- echo "Borrado de archivos terminado" .c.o: $(COMPILADOR) -g -I$(HOME)/tesis/fuente/incl/ -c $*.c -o $*.o $(OBJS): $(HOME)/tesis/fuente/incl/$(HEADER) $(HOME)/tesis/lib/lib$(LIB).a “make_AGH_FC” #********************************************************************************* #* Compila el programa de Algoritmo Genetico Hibrido con poblacion inicial * #* de soluciones factibles generadas por fase constructora del GRASP * #********************************************************************************* COMPILADOR=gcc FUENTE= $(HOME)/tesis/fuente/util/util.c $(HOME)/tesis/fuente/pob_ini/pob_ini_fc.c $(HOME)/tesis/fuente/evaluacion/evaluacion.c $(HOME)/tesis/fuente/seleccion/selec_torneo.c $(HOME)/tesis/fuente/hijos/hijos.c $(HOME)/tesis/fuente/BL/busqueda_local.c AGH.c OBJS=$(FUENTE:.c=.o) HEADER= ag.h LIB=GA PROG=AGH_FCgrasp CC: $(OBJS) $(COMPILADOR) $(OBJS) -L$(HOME)/tesis/lib -l$(LIB) -lm -o $(HOME)/tesis/bin/$(PROG) @- echo "Compilación terminada" LIMPIA: @- rm -f $(OBJS) @- echo "Borrado de objetos terminado" BORRA:

AII-22

@- rm -f $(OBJS) $(PROG) @- echo "Borrado de archivos terminado" .c.o: $(COMPILADOR) -g -I$(HOME)/tesis/fuente/incl/ -c $*.c -o $*.o $(OBJS): $(HOME)/tesis/fuente/incl/$(HEADER) $(HOME)/tesis/lib/lib$(LIB).a “make_AGH_SR” #************************************************************************ #* Compila el programa de Algortimo Genetico con poblacion inicial * #* de soluciones factibles generadas por algoritmo SR * #************************************************************************ COMPILADOR=gcc FUENTE= $(HOME)/tesis/fuente/util/util.c $(HOME)/tesis/fuente/pob_ini/pob_ini.c $(HOME)/tesis/fuente/evaluacion/evaluacion.c $(HOME)/tesis/fuente/seleccion/selec_torneo.c $(HOME)/tesis/fuente/hijos/hijos.c $(HOME)/tesis/fuente/BL/busqueda_local.c AGH.c OBJS=$(FUENTE:.c=.o) HEADER= ag.h LIB=GA PROG=AGH_SR CC: $(OBJS) $(COMPILADOR) $(OBJS) -L$(HOME)/tesis/lib -l$(LIB) -lm -o $(HOME)/tesis/bin/$(PROG) @- echo "Compilación terminada" LIMPIA: @- rm -f $(OBJS) @- echo "Borrado de objetos terminado" BORRA: @- rm -f $(OBJS) $(PROG) @- echo "Borrado de archivos terminado" .c.o: $(COMPILADOR) -g -I$(HOME)/tesis/fuente/incl/ -c $*.c -o $*.o $(OBJS): $(HOME)/tesis/fuente/incl/$(HEADER) $(HOME)/tesis/lib/lib$(LIB).a “make_RS” #************************************************************************ #* Compila el programa de Recocido Simulado * #************************************************************************ COMPILADOR=gcc FUENTE= $(HOME)/tesis/fuente/util/util.c $(HOME)/tesis/fuente/pob_ini/pob_ini.c sa.c OBJS=$(FUENTE:.c=.o) HEADER= ag.h LIB=GA PROG=RS CC: $(OBJS) $(COMPILADOR) $(OBJS) -L$(HOME)/tesis/lib -l$(LIB) -lm -o $(HOME)/tesis/bin/$(PROG) @- echo "Compilación terminada" LIMPIA: @- rm -f $(OBJS) @- echo "Borrado de objetos terminado" BORRA: @- rm -f $(OBJS) $(PROG) @- echo "Borrado de archivos terminado" .c.o: $(COMPILADOR) -g -I$(HOME)/tesis/fuente/incl/ -c $*.c -o $*.o

AII-23

$(OBJS): $(HOME)/tesis/fuente/incl/$(HEADER) $(HOME)/tesis/lib/lib$(LIB).a “make_GRASP” #************************************************************************ #* Compila el programa GRASP * #************************************************************************ COMPILADOR=gcc FUENTE= $(HOME)/tesis/fuente/util/util.c grasp.c OBJS=$(FUENTE:.c=.o) HEADER= ag.h LIB=GA PROG=grasp CC: $(OBJS) $(COMPILADOR) $(OBJS) -L$(HOME)/tesis/lib -l$(LIB) -lm -o $(PROG) @- echo "Compilación terminada" LIMPIA: @- rm -f $(OBJS) @- echo "Borrado de objetos terminado" BORRA: @- rm -f $(OBJS) $(PROG) @- echo "Borrado de archivos terminado" .c.o: $(COMPILADOR) -g -I$(HOME)/tesis/fuente/incl/ -c $*.c -o $*.o $(OBJS): $(HOME)/tesis/fuente/incl/$(HEADER) $(HOME)/tesis/lib/lib$(LIB).a Nota: Los archivos evaluacion.c, selec_torneo.c, hijos.c (no incluídos) son similares a los archivos evaluacion2.c, selec_torneo2.c, hijos2.c, respectivamente, con la diferencia que los primeros escriben los datos de salida en un archivo.

AII-24