Application of Evolutionary Computation Techniques to the Optimal Short-Term Scheduling of the Electrical Energy Production

Application of Evolutionary Computation Techniques to the Optimal Short-Term Scheduling of the Electrical Energy Production Alicia Troncoso Lora1,Jos´eCrist´obal Riquelme1,Jos´eLu´ıs Mart´ınez Ramos2, Jes´us Manuel Riquelme Santos2, and Antonio G´omez Exp´osito2 1Department of Languages and Systems, University of Sevilla, Spain {ali,riquelme}@lsi.us.es 2Department of Electrical Engineering, University of Sevilla, Spain {camel,jsantos,age}@us.es Abstract. In this paper, an evolutionary technique applied to the optimal short-term scheduling (24 hours) of the electric energy production is presented. The equations that define the problem lead to a nonlinear mixed-integer programming problem with a high number of real and integer variables. Consequently, the resolution of the problem based on combinatorial methods is rather complex. The required heuristics, introduced to assure the feasibility of the constraints, are analyzed, along with a brief description of the proposed genetic algorithm. Finally, results from realistic cases based on the Spanish power system are reported, revealing the good performance of the proposed algorithm, taking into account the complexity and dimension of the problem. Keywords: Genetic algorithms, scheduling, optimization, feasibility. 1 Introduction The optimal short-term scheduling of the electrical energy production [1] aims at determining which generating units should be online and the corresponding optimal generation of thermal and hydro units along the scheduling period, usually 24 hours, in order to minimize the expected total cost satisfying the forecasted system load. The scheduling task leads to a nonlinear mixed-integer programming problem. Moreover, this problem is coupled in time by the maximum speed that generating units, specially thermal units, are able to change the produced energy (known as up and down ramps), and also by the topology of the hydroelectric power plants, with a delay in hours between the water of a reservoir being used and the availability of that water in the reservoirs downstream. A really large number of variables, both real and binary variables, is needed to properly model this problem. Many approaches have been proposed for the resolution of this optimization problem, ranging from Dynamic Programming to Linear Mixed-Integer Programming or Lagrangian Relaxation [2], the latter being the most widely used optimization method in commercial programs. Genetic Algorithms (GA) [3, 4], a general-purpose stochastic search method based on the R. Conejo et al. (Eds.): CAEPIA-TTIA 2003, LNAI 3040, pp. 656–665, 2004. c Springer-Verlag Berlin Heidelberg 2004 Application of Evolutionary Computation Techniques 657 mechanics of natural selection, have also been successfully applied to the Electrical Energy Scheduling problem since the adaptation is quite straightforward due to the combinatorial nature of this problem. In this paper, a GA applied to the optimal short-term (24 hours) electrical energy production scheduling is presented. The paper is organized as follows: Section 2 presents the equations used to model the scheduling problem, leading to a nonlinear mixed-integer programming problem with a large number of both real and integer variables. Section 3 briefly introduces the proposed GA, and several implementation issues that are crucial to obtain feasible solutions are discussed. Finally, Section 4 reports some results obtained from realistic cases based on the Spanish power system, and the main conclusions of the paper are outlined. 2 Formulation of the Problem The objective of the scheduling problem is to determine the on/off state and the energy production of thermal and hydro units on each hour of the scheduling period, in order to minimize the total cost of the system satisfying the forecasted hourly demand and the technical constraints of thermal and hydro power plants. 2.1 Objective Function The total energy production cost of the scheduling period is defined by CT= nt  t=1 ng  i=1 [Ci(Pi,t)+SUi·Ui,t ·(1 −Ui,t−1)+SDi·(1 −Ui,t)·Ui,t−1](1) where ntis the number of hours of the scheduling period, ngis the number of thermal units, each having a quadratic cost function, Ci(Pi,t), of the energy production, Pi,t;SUiand SDiare respectively the start-up and shut-down cost of thermal generator i,andUi,t is a binary variable representing the on/off state of the thermal generator iat hour t. It can be observed that the total production cost is a sum of quadratic functions of the energy of each thermal generator if the state of each generator was previously stated by the GA. This is the case of the proposed technique because the on/off states are managed by the GA. Notice that the production cost is only due to the production of thermal generators Pi,t, i.e., generators that produce energy by burning a fuel or by atomic means. Hydro units provide free-of-charge energy PH h,t that is only subject to the availability of water in the corresponding reservoirs. 2.2 Constraints The minimization of the objective function is subject to technical constraints, water balance in hydroelectric power plants and the associated reservoirs, and to the system energy demand and reserve balances: 658 Alicia Troncoso Lora et al. –Maximum and minimum limits on the hourly energy production of the thermal and hydro generators, Pm i≤Pi,t ≤PM ii=1,...,n gt=1,...,n t(2) PHm h≤PH h,t ≤PHM hh=1,...,n ht=1,...,n t(3) where nhis the number of hydro plants, PH h,t is the energy production of hydro plant hat hour t,andPm i,PM i,PHm hand PHM hare respectively the limits on the hourly energy production of the thermal unit iand hydro plant h. The equation (2) cannot be fulfilled when thermal generators are either starting or stopping, starting and stopping periods begin respectively when the corresponding state changes to ON or OFF. In order to avoid this problem, this equation is modified for thermal units that are either being started-up or shut-down, 0≤Pi,t ≤PM ii=1,...,n gt=1,...,n t(4) Moreover, in order to penalize the power generated by thermal units during periods of shutting-down, energy that is out of the optimal commitment, penalty terms are added to the objective function as follows C T=CT+ nt  t=1 ng  i=1 Cp·Pi,t ·(1 −Ui,t)(5) –Maximum up and down ramps of thermal units. The thermal units can not increase or decrease the production of energy at consecutive hours by more than a given maximum rate, −RBi≤Pi,t −Pi,t−1≤RSii=1,...,n gt=1,...,n t(6) where RSiyRBiare respectively the maximum up and down rates of the thermal generator i, usually known as ramp limits. –Limits on the available water. The hydro units use water to generate electrical energy and water is a limited resource. Thus, the energy produced by a hydro unit is limited by the volumen of available water in the associated reservoir. In consequence, reservoir levels are subject to capacity limits, VH m h≤VH h,t ≤VH M hh=1,...,n ht=1,...,n t(7) where VH h,t is the stored energy of reservoir hat hour t, corresponding to the hydro unit h;VH m hand VH M hare respectively the minimum and maximum limits on the stored energy imposed by the maximum and minimum possible water level of reservoir h. –Hydraulic coupling between reservoirs. Time coupling exits due to cascaded reservoirs, since the water used to produce energy in a hydro unit will be Application of Evolutionary Computation Techniques 659 available later to the next hydraulic unit downstream with a certain delay, obviously when the water has arrived to the corresponding reservoir. VH h,t =VH h,t−1−PH h,t + n(k)=h PH k,t−d(k)+Wh(8) where d(k) is the water delay time in hours between reservoir kand the next reservoir downstream, n(k), that is supposed to be reservoir h,andWhis the natural inflow of reservoir h. –The total hourly energy production must be equal the total energy demand at that hour, Dt, which has been previously forecasted. ng  i=1 Pi,t ·Ui,t + nh  h=1 PH h,t =Dtt=1, ..., nt(9) –The total energy that can be produced on each hour must exceed the forecasted demand by a specified amount, Rt, i.e., the generating capacity in reserve to be used if an unexpected event such as the failure of a plant or a large error on the forecasted demand happened. ng  i=1 PM i·Ui,t + nh  h=1 PHM h≥Dt+Rtt=1, ..., nt(10) –Minimum up and down times of thermal units. The minimum up time, UTi, is the minimum number of hours that the unit imust be functioning after starting. Besides, the minimum down time, DTi, is the minimum number of hours that the unit imust be shut-down after stopping. DTi−1  k=0 (1 −Ui,t+k)≥DTiif unit iis shut-down at hour t(11) UTi−1  k=0 Ui,t+k≥UTiif unit iis started at hour t(12) Start-up and shut-down costs of realistic cases tend to reduce the number of shut-downs and start-ups to a minimum, making the minimum-time constraints useless in most cases. Moreover, the inclusion of hydraulic generation facilitates the fulfillment of the thermal unit constraints because the hydro units are faster in response and produce energy at no cost, i.e., the hydraulic energy will be strategically distributed among the hours of the scheduling horizon in order to avoid the starting of more thermal units than the strictly required. As an example, Table 1 shows the number of constraints, binary and continuous variables of the above problem for a test system comprising 49 thermal units, 2 hydro units and the scheduling horizon embracing 24 hours. 660 Alicia Troncoso Lora et al. Table 1. Dimension of the problem for a test system comprising 49 thermal units, 2 hydro units and 24 hours. Number of Variables Number of Constraints Binary Continuous (2 ·ng+3·nh+2)·nt+2·ngng·nt(ng+2·nh)·nt 2642 1176 1272 3 The Proposed Genetic Algorithm As presented in the previous section, the optimal scheduling of the electric energy production is a nonlinear, non-convex, combinatorial, mixed-integer and very large problem. Hence, there is no technique that would always lead to the optimal solution of the problem for realistic cases. In the last years, techniques based on heuristics, dynamic programming, linear mixed-integer programming and lagrangian relaxation have been applied to this particular problem. Techniques based on heuristics rely on simple rules that depends on the knowledge of power plant operators. Constraints of realistic problems are not properly modeled by dynamic programming approaches, and the number of required states increases exponentially, thus dealing to excessive computation times. Linear programming approaches cannot properly model neither the nonlinear objective function nor the nonlinear constraints, and crude approximations are required. Finally, the use of heuristic techniques is required by lagrangian relaxation approaches to calculate feasible solutions, deteriorating the quality of the obtained solutions. Consequently, new methods are still needed to obtain more optimal solutions to realistic problems. In this paper, a GA [5, 6] has been used to solve the scheduling problem due to its ability to deal with nonlinear functions and integer variables. The proposed GA algorithm is used to compute the optimal on/off states of thermal units, i.e., the binary variables, while the optimal continuous variables, i.e., the hourly energy production of hydro and committed thermal units, are calculated solving a typical quadratic programming problem by a classical optimization algorithm in which the on/off states of thermal units are known. Convergence characteristics of GA depend on several key implementation issues that are discussed in the rest of this section. 3.1 Codification of the Individuals Each individual is represented by the on/off states of thermal generators during the scheduling period. Thus, individuals are represented by 0/1 matrices, with columns corresponding to time scheduling intervals and rows associated with thermal units. If element (i, j) is equal to one, the state of thermal unit iduring time interval jis on. Similarly, if element (i, j) is equal to zero, the state of thermal unit iduring time interval jis off. 3.2 Initial Population Up and down ramp constraints of thermal units, equation (6), are a key factor in the convergence of the GA: if the initial population is strictly randomly selected, Application of Evolutionary Computation Techniques 661 ramp constraints lead to many infeasible individuals in the initial generation, which makes successive generations suffer from poor diversity, and the GA may converge prematurely. To assure that the initial population contains an adequate percentage of feasible individuals, initial on/off schedulings are randomly selected but modified to account for the minimum start-up and shut-down times imposed by ramp constraints. For example, if generator g,withamaximumdownramp equal to 100 MWh, is on at hour 3 producing an energy of 400 MWh, this generator would require 4 hours to shut-down and, consequently, the generator at hours 4, 5 and 6 should be on. The state Ug,3is strictly randomly generated but the states for the following hours, Ug,4,Ug,5and Ug,6,aregivenby Ug,3=1⇒Ug,4=Ug,5=Ug,6= 1 (13) 3.3 Fitness Function The fitness function evaluates the quality of an individual of the population. In this case, the function is the inverse of the total production cost of the individual. The total production cost is obtained solving a quadratic programming problem by using a nonlinear Interior Point method [7–9]. An extra-high-cost fictitious generator is included to satisfy the system demand, equation (9). This fictitious generator generates the necessary energy that the rest of generators cannot produce to satisfy the demand of the customers. A penalty term proportional to the deficit in reserve requirements is added in the cost function aiming at satisfying the reserve constraint. Penalty terms only apply to infeasible individuals, which are consequently eliminated throughout the evolutionary process. 3.4 Selection Operator To produce a new generation, parents are randomly selected using a tournament selection technique that selects the best individuals for reproduction. The probability of a particular individual being selected is in proportion to its fitness function, taking into account that the total generation cost, including possible penalizations, is being minimized. The individuals chosen to be parents are included in the following generation. 3.5 Crossover Operator Children are obtained by adding the binary strings that results from random partitions of each row, as shown in Figure 1a. A column-partitioning procedure may also be applied (Figure 1b). This crossover operator is a particular case of the multipoint crossover operator. As rows are associated with the thermal units, the first approach yields the infeasibility of new individuals in terms of minimum up and down times, equations (11) and (12), while the second approach affects to the constraint of the demand (9) and the reserve (10). The crossover probability has been set to one, i.e., two individuals that have been selected to be parents are always combined to obtain a new individual. 662 Alicia Troncoso Lora et al. 1 2 3 t 1 2 3 t 11 22 33 .. .. .. gg 1 2 3 t 1 2 3 t 11 22 33 .. .. .. gg (a) PARENTS CHILDREN 123 t 123 t 11 22 ... ... gg 123 t 123 t 11 22 ... ... gg (b) CHILDREN PARENTS Fig. 1. Crossover Operator: a) random partitions of rows; b) random partitions of columns. In the final version of the GA, the crossover by rows has been chosen because start-up and shut-down costs of realistic cases, along with the inclusion of hydraulic generation, tend to reduce the number of shut-downs and start-ups to a minimum, making the minimum-time constraints useless in most cases. All rows are always combined to obtain a new individual, though probabilities could have been used to determine which rows should be combined. 3.6 Mutation Operator Following the crossover process, children are mutated to introduce some new genetic material according to a pre-defined mutation probability. The gene to be mutated is represented by a randomly selected generator and time interval, element (i, j) of the matrix representing a particular individual. The mutation implies changing the state on/off of the generator with some probability. 4 Test Results The GA algorithm have been applied to several realistic cases based on the Spanish generation system, comprising 49 thermal units and one equivalent hydraulic generator, the scheduling horizon embracing 24 hours. Hourly system demand corresponds to a working day of 1998. Table 2 shows the main parameters of the implemented GA. Figure 2 shows the evolution of the fittest individual cost and the average cost of the generation throughout the evolutive process, with and without reserve requirements (figures 2a and 2b respectively). Obviously, reserve requirements lead to higher operating costs, both in the best solution (3152.71 and 3109.51 thousands of Euros, respectively) and in the average (3170.90 and 3132.02 thousands of Euros, respectively). Figure 3 presents the optimal thermal and hydraulic generation, along with the evolution of the marginal cost during the scheduling period. The marginal Application of Evolutionary Computation Techniques 663 Table 2. Parameters of the proposed GA. Maximum number Size of the Probability of generations population of crossover 5000 100 1 Number of children Number of mutations Probability by reproduction of the best individual of mutation 2 2 0.1 3 3.25 3.5 3.75 4 4.25 4.5 4.75 5 1 1001 2001 3001 4001 5001 Number of generations (a) Cost (Thousands of Euros) 3 3.25 3.5 3.75 4 4.25 4.5 4.75 5 1 1001 2001 3001 4001 5001 Number of generations (b) Cost (Thousands of Euros) Fig. 2. Evolution of the best individual and average costs: a) reserve requirements considered; b) no reserve requirements considered. cost represents the increment of cost when the system demand increases in one MWh, i.e., the hourly cost of the energy. Ramp constraints are only included in the second case (Figure 3b). Note that, when ramps are considered, a higher cost, fast-response generator is needed at hour 22 to satisfy a small peak of demand. As expected, the total operating cost is higher when ramps are included (3119.1 and 3109.5 thousands of Euros, respectively). Figure 4 shows the optimal scheduling of a thermal generator, ignoring its ramp constraints (Figure 4a) and considering them (Figure 4b). Notice that ramps modify the optimal scheduling when the generator is starting and stopping. The penalty term imposed to the objective function when Ui,t = 0, forces the generator to adjust its output to the least possible value compatible with the ramp constraint (hours 15 and 16). Similar considerations apply when the generation is starting (hours 20 and 21). Finally, Figure 5 shows the solution provided by the proposed GA applied to the optimal scheduling of 49 thermal units and two cascaded reservoirs with a delay of 10 hours and all the energy initially stored in the upstream reservoir. Note that the downstream reservoir 2 cannot start producing until water released by generator 1 arrives. The total available hydraulic energy cannot be used due to the hydraulic constraint and to the maximum power of generators. 664 Alicia Troncoso Lora et al. 0 7000 14000 21000 1 3 5 7 9 11 13 15 17 19 21 23 Hours (a) Energy (MWh) 12 14 16 18 20 22 24 Marginal Cost (Euros/MW) Thermal Energy Hydro Energy Marginal Cost 0 7000 14000 21000 1357911131517192123 Hours (b) Energy (MWh) 12 14 16 18 20 22 24 Marginal Cost (Euros/MW) Thermal Energy Hydro Energy Marginal Cost Fig. 3. Optimal thermal and hydraulic generation: a) no ramp constraints considered; b) ramp constraints considered. 0 20 40 60 80 100 120 140 160 1 3 5 7 9 11131517192123 Hours (a) Energy (MWh) 0.5 1 1.5 Energy State (On/Off) 0 20 40 60 80 100 120 140 160 1357911131517192123 Hours (b) Energy (MWh) 0.5 1 1.5 Energy State (On/Off) Fig. 4. Optimal scheduling of a thermal generator: a) no ramp constraints considered; b) ramp constraints considered. 0 5000 10000 15000 20000 25000 1 3 5 7 9 11 13 15 17 19 21 23 Hours (a) Energy (MWh) 12 12.5 13 13.5 14 14.5 15 Marginal Cost (Euros/MW) Energy of hydro plant 1 Energy of hydro plant 2 Thermal Energy Marginal Cost 0 5000 10000 15000 20000 25000 30000 35000 40000 45000 50000 1357911131517192123 Hours (b) Energy (MWh) 0 5000 10000 15000 20000 25000 Energy (MWh) Energy of reservoir 1 Energy of reservoir 2 Demand Fig. 5. Optimal thermal and hydraulic generation of a case with two cascaded reservoirs and all energy initially stored in the upstream reservoir. 5 Conclusions In this paper an evolutionary technique applied to the optimal short-term (24 hours) electric energy production scheduling has been proposed. The equations defining the model of the problem have been presented leading to a nonlinear