koorio.com

海量文库 文档专家

海量文库 文档专家

- A Solution to the Angel Problem
- A decomposition approach to the two-stage stochastic unit commitment problem
- A solution to the generalized railroad crossing problem in ESTEREL
- Modeling and Solution of the Large-Scale Security-Constrained Unit Commitment
- A Novel Solution to the ATT48 Benchmark Problem
- A solution to the embedding problem for partial idempotent latin squares
- FastSLAM A factored solution to the simultaneous localization and mapping problem
- The steps to write a problem solution essay
- A matrix real-coded genetic algorithm to the unit commitment problem
- A new decomposition approach for the thermal unit commitment problem

IEEE TRANSACTIONS ON POWER SYSTEMS, VOL. 19, NO. 2, MAY 2004

1165

A Solution to the Unit-Commitment Problem Using Integer-Coded Genetic Algorithm

Ioannis G. Damousis, Anastasios G. Bakirtzis, Senior Member, IEEE, and Petros S. Dokopoulos, Member, IEEE

Abstract—This paper presents a new solution to the thermal unit-commitment (UC) problem based on an integer-coded genetic algorithm (GA). The GA chromosome consists of a sequence of alternating sign integer numbers representing the sequence of operation/reservation times of the generating units. The proposed coding achieves significant chromosome size reduction compared to the usual binary coding. As a result, algorithm robustness and execution time are improved. In addition, generating unit minimum up and minimum downtime constraints are directly coded in the chromosome, thus avoiding the use of many penalty functions that usually distort the search space. Test results with systems of up to 100 units and 24-h scheduling horizon are presented. Index Terms—Generation scheduling, genetic algorithm, unit commitment.

RAND

Operating status of unit , hour ( , ). Number of load peaks during the UC horizon. Number of operating cycles for unit . Operating cycle index. Duration of operating cycle for unit (in hours). Integer part of . Closest integer to real number . . Random number generator: RAND(a,b) creates a random number uniformly distributed in the interval [a,b]. I. INTRODUCTION

NOMENCLATURE Number of units. Unit index. Hour index. UC horizon (in hours). Demand during hour (in megawatts). Reserve requirement during hour (in megawatts). Active power output of th unit for hour (in megawatts). Maximum active power output of th unit (in megawatts). Minimum active power output of th unit (in megawatts). Maximum response rate limited active power output of th unit for hour (in megawatts). Minimum response rate limited active power output of th unit for hour (in megawatts). Total production cost for the duration of the UC horizon (in U.S. dollars). th unit cost function (in U.S. dollars per hour). Minimum uptime of unit (in hours). Minimum downtime of unit (in hours). Ramp-up rate of unit (in megawatts per minute). Ramp-down rate of unit (in megawatts per minute). Start-up cost function for unit (in U.S. dollars). Shutdown cost for unit (in U.S. dollars).

Manuscript received June 2, 2003. This work was supported by the European Union Research Project “More Advanced Control Advice for Secure Operation of Isolated Power Systems with Increased Renewable Energy Penetration and Storage (MORE CARE)” under Contract ERK5-CT1999-00019. The authors are with the Electrical Power Systems Laboratory of the Department of Electrical and Computer Engineering in Aristotle University of Thessaloniki, Hellas 54006, Greece. Digital Object Identifier 10.1109/TPWRS.2003.821625

T

HE objective of the unit commitment (UC), in regulated or state monopoly power markets, is to schedule the operation of the generating units in order to serve the load demand at minimum operating cost while observing all plant and system constraints over a given scheduling period, ranging from several hours to days ahead. Some competitive electricity markets, such as the original California market before the 2000–01 energy crisis, leave commitment decisions entirely to participants. In such markets, the system operator (or a power exchange) accepts simple pricequantity offers from the generating companies (gencos), and simply arranges them in merit order hour-by-hour in order to compute the day-ahead market clearing price and the daily generation schedule. It is the gencos’ responsibility to schedule the operation of their resources in response to anticipated next-day electricity prices, and internalize the quasi-fixed costs (start-up and no-load costs) in their price offers. In other competitive electricity markets, however, [1]–[3], the day-ahead generation scheduling is performed by solving a centralized security-constrained UC (SCUC). The centralized SCUC in a competitive power market is very similar to the traditional UC of a regulated utility. The main difference, apart from the inclusion of transmission system security constraints, is the fact that the actual generator operating and start-up costs are replaced by the corresponding offers. Thus, the solution of the traditional, centralized UC problem is important in the competitive power industry. The UC is a large-scale, nonconvex, nonlinear, mixed-integer optimization problem. The optimal solution to the UC problem can be obtained by complete enumeration, which is prohibitive in practice owing to its excessive computational resource requirements [4]. The need for practical, cost-effective UC solutions, led to the development of various UC algorithms that provide suboptimal, but efficient scheduling for real sized power systems comprising hundreds of generators.

0885-8950/04$20.00 ? 2004 IEEE

1166

IEEE TRANSACTIONS ON POWER SYSTEMS, VOL. 19, NO. 2, MAY 2004

Priority list (PL) methods [5], [6] simulate the scheduling practices of system operators. Base load units are committed first and peaking units last in order to meet the load demand. PL methods are fast but highly heuristic and give schedules with relatively high operating costs. Dynamic programming (DP) [7]–[10] has been extensively used for the solution of the UC problem. However, it suffers from the “curse of dimensionality”: the explosion of computational resource requirements with the system size, limit its application to very small-sized systems. Different techniques have been adopted in an effort to reduce the DP resource requirements and make it applicable to real-sized systems. However, these heuristics produce suboptimal solutions, and in certain cases, they may require the relaxation of some constraints in order to produce a solution [8], [9]. Lagrangian Relaxation (LR) methods [11]–[16] separate the UC constraints into (a) “local constraints,” each invoking only one unit, such as unit operating limits, ramp rate, minimum up/down times, and (b) “system constraints,” each invoking many units, such as power balance and reserve requirement. The system constraints are then relaxed through a pricing mechanism: The system constraints augment the objective function multiplied by the associated prices (Lagrange multipliers or dual variables) to form the Lagrangian function. For fixed prices, the minimization of the Lagrangian with respect to the primal variables (unit status and outputs) can be separated to a number of local problems, each invoking one unit only. These problems are solved by DP without any dimensionality problems owing to their small size. The prices are then updated, usually through a subgradient update mechanism, in the direction of the dual function maximization, which, in case of convex primal problem, would imply feasibility of the system constraints. However, owing to the nonconvexity of the UC problem, optimality of the dual does not guarantee feasibility of the primal UC problem and heuristics are employed in order to locate a feasible suboptimal solution in the vicinity of the dual optimum. The “duality gap,” (i.e., the difference of the primal and the dual objective functions), is used to estimate the quality of the suboptimal solution. Branch-and-bound [17] and Bender’s decomposition [18], [19] have also been used for the solution of the UC problem. Recently, simulated annealing [20], expert systems [21], neural networks [22], [23], and genetic algorithms (GAs) [24]–[30] have also been used for the solution of the UC problem. GAs are global optimization techniques inspired by the study of genetics [31]–[33]. They can be easily implemented for the solution of hard optimization problems and they provide great modeling flexibility. Several GA approaches to the UC problem have been reported in the literature [24]–[30]. Most GA approaches use genetic guided search for the primal UC problem variables (unit status) [24]–[29], while others search for the dual variables (prices) within the framework of a LR solution to the UC problem [30]. A disadvantage of the GA solution to the UC problem is the long execution time. Another problem is that owing to the heuristic nature of the algorithms, the solution is not guaranteed to be optimal. The reported GA implementations on the

UC problem are based on the usual binary coding. However, studies [34] have shown that other coding schemes such as integer or floating point can be more efficient when accompanied with suitable GA operators. In this paper, an integer-coded genetic algorithm (ICGA) is developed for the solution of the UC problem. The ICGA chromosome consists of a sequence of alternating sign integer numbers representing the sequence of operation/reservation times of the generating units. The proposed coding achieves significant chromosome size reduction compared to the usual binary coding. As a result, algorithm robustness and execution time are improved. In addition, generating unit minimum up and downtime constraints are directly coded in the chromosome, thus avoiding the use of many penalty functions that distort the search space. Test results with systems of up to 100 units and 24-h scheduling horizon are presented. II. THERMAL UC FORMULATION The objective of the UC problem is the minimization of the total production cost over the scheduling horizon. The total costs consist of: ? fuel costs; ? start-up costs; ? shutdown costs. Fuel costs are calculated using heat rate and fuel price information. Start-up costs are expressed as an exponential (when cooling) or linear (when banking) function of the time since last shut down [4]. Two-valued (hot-start/cold-start) staircase function simplifications of the start-up cost [26] are also modeled. Shutdown costs are modeled as a fixed dollar amount for each unit per shutdown. The constraints (both local and system-wide) that must be satisfied during the optimization process are: ? unit initial operating status; ? unit operating constraints that include upper and lower power output technical limits, minimum up and down times, status (must run, fixed power, unavailable/available), and ramp rates. Owing to the response rate constraints, the operating region of the units is constrained by the following response rate constrained, time-dependent operating limits: (1) (2) is the UC time step; where ? plant crew constraints; ? system power balance (3) ? system spinning reserve (10-min) requirements (4) where is the 10-min response rate constrained maximum active power output of the th unit, and is de-

DAMOUSIS et al.: A SOLUTION TO THE UNIT-COMMITMENT PROBLEM USING INTEGER-CODED GA

1167

fined by (1) with . For simplicity, regulating reserve is not included in the problem formulation. Its incorporation is trivial. III. INTEGER-CODED GENETIC ALGORITHM SOLUTION A. Chromosome Definition The straightforward way to define the GA chromosome for the UC problem is to use a binary alphabet, and assign a binary digit for the ON/OFF operating status of a particular unit during a particular hour. In this case, the GA chromosome consists of [26]. In our solution, the chromosome consists of a sequence of integer numbers, representing the sequence of the ON/OFF cycle durations of each unit during the UC horizon. The length of the chromosome is equal to the number of ON/OFF cycles of all units during the scheduling period. Since the number of ON/OFF cycles of generating units is small in practice (typically 1–5 ON/OFF cycles per day), a significant reduction of the chromosome length is achieved. The dispatchers know the number of the daily ON/OFF cycles of the generating units from their operating history. Fig. 1 illustrates the ON/OFF cycles of a base-load unit (1 cycle) and a cycling unit (5 cycles), along with a daily load profile exhibiting two peaks. Please note that by “ON/OFF cycle” we actually mean a half-cycle, since, strictly speaking, a full-cycle consists of a complete ON-OFF sequence. In the absence of unit operating history data, the maximum number of a unit’s “ON/OFF” cycles during the UC horizon can be determined as a function of 1) the number of load peaks during the UC horizon and 2) the sum of the minimum up and down times of the unit, using the following formula:

Fig. 1.

Base-load and cycling unit operating cycles.

itive integer in the chromosome represents duration of continuous unit operation (ON status), while a negative integer represents duration of continuous reservation (OFF status) of the unit. The part of the chromosome representing the operating schedule of a particular unit during the UC horizon consists of a sequence of alternating sign. The sum of of integers the absolute values of these alternating sign integers must equal the scheduling horizon

(5) The first term in the large parenthesis of (5) limits the maximum number of ON/OFF cycles for the fast responding peaking units, since the minimum up and down times of these units are . For a daily small, resulting in a small sum load profile exhibiting two peaks (typical for the Greek power system), the maximum number of “ON/OFF” cycles for a unit is limited to five, as shown in Fig. 1. On the other hand, base-load units have large minimum up . Thus, and downtimes, resulting in a large sum the maximum number of ON/OFF cycles for the base-load units is limited by the second term in the large parenthesis of (5). In is greater the case of one-shift, base-load units , resulting in a single, ON, daily cycle. than The first term in the large parenthesis of (5) reduces the length of the GA chromosome, based on practical experience with peaking unit operation. However, from a theoretical point of view, it restricts the GA search space and may lead to suboptimal solutions. To address this issue, our GA implementation allows augmentation of the chromosome length to allow selected peaking units to perform more cycles than those dictated by the first term of (5) as described later in this section. The chromosomes consist of concatenated integers that represent the duration of the “ON/OFF” cycles for every unit. A pos-

In the initial population of the GA, the sequence of alternating sign integers that represents the operating schedule of unit is created as follows. is iniThe duration of the first cycle of operation of unit , tialized so that the unit continues the operating mode (ON/OFF) of the last cycle of the previous scheduling day for at least as many hours as required to satisfy the minimum up/down time constraints ( is the duration of the last cycle of the previous scheduling day) if if (6) , the duration of the th cycle of operation of unit , is calculated taking into account the unit’s minimum up and downtime constraints, the UC horizon, and the duration of prior cycles of operation of the unit. the If , cycle represents ON status with duration For if otherwise If (7a) , cycle represents OFF status with duration if otherwise (7b) where represents the scheduling time remaining after cycles (Fig. 2) the allocation of the first

1168

IEEE TRANSACTIONS ON POWER SYSTEMS, VOL. 19, NO. 2, MAY 2004

TABLE I UC SCHEDULE REPRESENTATION IN A CHROMOSOME AND DECODED HOURLY SCHEDULES FOR THE SYSTEM’S UNITS

The start-up/shut-down costs are calculated from

Fig. 2. Calculation of the duration of the c

ON cycle T .

(9) where is the Heavyside (unit step) function. The total thermal system cost during the scheduling horizon is (10) The penalty function consists of two terms. The first term penalizes spinning reserve constraint violations (11). The second term penalizes excessive capacity [i.e., the situation in which the load is less than the sum of the minimum outputs of all committed units at a specific hour (12)]

The duration of the last cycle is determined by the durations of the previous cycles: . If owing to the random generation of the cycle durations, the enoperating tire scheduling period is covered with the first cycles are assigned zero cycles, the remaining duration by filling the last positions of the part of the chromosome that represents the operating schedule of unit with zeros. Note that the unit minimum up and downtime constraints are automatically satisfied by the above described coding, eliminating the need for the addition of corresponding penalty functions in the GA fitness function.

B. Fitness Function Computation The fitness function used for the evaluation of the chromosomes contains two terms. The first term is the total thermal system operating cost over the scheduling horizon, and the second term is a penalty function penalizing the violation of system constraints. The fitness function assigned to a chromosome is calculated as follows. Given a GA chromosome, the unit commitment schedule is completely defined, as shown in Table I. The total thermal system cost consists of the cost of unit start-up and shutdown during the scheduling horizon as well as the production cost to cover the load. The latter is calculated by economically dispatching the load to the committed units at each time interval of the scheduling period, while observing the time-dependent, response-rate-constrained unit operating limits. The resulting response-rate-constrained producis used for tion schedule the computation of the production cost. Quadratic thermal unit production cost functions are used (8) (11)

(12) where is the unit ramp function. The GA fitness function is formed as follows: (13) and is a system-dewhere pendent constant. Constant is used in order to prevent the fitness from obtaining too small values, and its magnitude should be of the order of the system maximum operating cost over the defined as scheduling period

DAMOUSIS et al.: A SOLUTION TO THE UNIT-COMMITMENT PROBLEM USING INTEGER-CODED GA

1169

The penalty weight coefficient in (11) and (12) is a multiple so as to disqualify infeasible solutions. If the solution corresponding to a particular chromosome is infeasible, the total system cost (10), is based on a thermal unit production schedule that satisfies the unit ramp-rate-constrained operating limits, but may not satisfy the system power balance or reserve requirements of one or more time intervals. In this case, the penalty function is the prevailing term in the denominator of (13) and the fitness is assigned a low value, disqualifying such an infeasible solution. of C. GA Evolution The evolution of a GA population is based on the natural selection [31]–[33] and the survival of the fittest. In our implementation, this is achieved using the roulette wheel parent selection [33]: The chance of a chromosome to be selected for reproduction is proportional to its fitness. After the selection of the parent chromosomes, recombination and mutation take place to produce the offspring chromosomes. Owing to the nature of our coding and the use of integers, we cannot use the crossover and mutation operators in their classic form. New operator versions were developed specifically tailored to our coding. 1) Crossover: Crossover produces new solutions by the recombination of the parent chromosomes. The operator in its classic form selects one or more crossing points in the parent chromosomes and swaps the resulting pieces. This is not applicable to our coding since the integers that represent a unit’s daily schedule depend on each other. Our crossover operator selects multiple crossing points that do not “cut” a unit’s schedule in half. This crossover scheme swaps whole unit schedules instead of hourly “ON/OFF” states. In order to control the population’s convergence, varying crossover probability and varying number of crossing points have been used. 2) Mutation: Since we use integer-coded GA, the simple mutation scheme that alters a bit from 0 to 1 and vice-versa cannot be used. Instead, a variation of Michalewicz’s [34] nonuniform mutation operator for real-coded GAs is used. This operator is described below. is a chromoIf some, and unit is selected to be mutated at cycle , the new duration of cycle will be after mutation if if (14)

Fig. 3. Improvement of the GA evolution with the application of the unit swapping/copying operator to a commitment of 20 units.

, , where is a random bit, for . For , the upper and lower limits are or returns a value in the range [0, defined in (6). Function ] such that the probability of the value returned being close to 0 increases with (15) where is a random floating-point number in the interval [0, 1], is the current generation number, is the maximum number of generations, and is a parameter that controls the degree

of dependence on the number of generations. In this way, the operator performs a uniform search in the whole range of the parameter at the early stages of the evolution, and at later stages, the search is restricted around the local area of the parameter, resembling a hill-climbing operator. For our experiments, was chosen equal to 0.2. Since the durations of the operating cycles in our coding depend on each other, the cycles following “ ” are mutated in the same way (14) until the UC horizon is covered. The mutation probability varies in order to control premature convergence of the population. 3) Special Operators: a) Unit swapping/copying operator: This operator is applied to the best chromosome of the population every 20 generations with a 30% probability. It selects randomly two units in the chromosome and performs the following actions: i) copy the schedule of the first unit to the second; ii) copy the schedule of the second unit to the first; iii) swap the schedules of the two units. Each of the above actions takes place only if the units’ minimum up/down times are the same. In this way, violations of these constraints are avoided. At the end of each action, the new UC schedule (chromosome) is evaluated and if it is superior to the original schedule, it replaces it and the action of the operator is terminated; if not, the original schedule is restored and the operator continues to the next action. Fig. 3 demonstrates the improvement in the evolution of the GA from the application of this operator. b) Excessive-reserve elimination operator: The existence of many units operating at minimum power output during certain time intervals in a daily schedule indicates commitment of excessive number of units during these time intervals. Such a commitment schedule may be improved if some of the units operating at minimum are turned off whenever certain conditions are met. The excessive reserve elimination operator explores this possibility. This operator checks whether the new operating cycles, resulting after the shutdown of certain units, operating at minimum power output, satisfy the unit’s operating time constraints (Fig. 4). Subsequently, it checks whether the rest of the online units satisfy the demand and reserve requirements during the time interval that the unit is turned off.

1170

IEEE TRANSACTIONS ON POWER SYSTEMS, VOL. 19, NO. 2, MAY 2004

Fig. 6. Improvement of the GA evolution with the second application of the excessive-reserve elimination operator to a commitment of 20 units. Fig. 4. Operating cycles of unit i before and after the application of the excessive-reserve elimination operator. TABLE II UC RESULTS USING LR [26], BCGA [26], AND ICGA FOR SYSTEMS RANGING FROM 10 TO 100 UNITS

a number of trailing cycles (of 0-h duration) are added to the daily schedule of the specific unit in all other chromosomes of the population.

Fig. 5. Improvement of the GA evolution with the first application of the excessive-reserve elimination operator to a commitment of 20 units.

IV. TEST RESULTS The proposed ICGA unit commitment was evaluated using the generating unit data of [26]. A base set of ten units was initially used, along with a 24-h load curve. For the 20-unit configuration, we duplicated the base set and doubled the load demand. The 40-unit to 100-unit systems were created in the same way. The reserve requirement was 10% of the hourly load in all cases. The ICGA solutions were compared to the solutions of the LR and the binary-coded GA (BCGA) reported in [26]. For each case, an ICGA consisting of 50 chromosomes ran for 300 generations. Because of the stochastic nature of GAs, different GA test runs do not converge to the same solution. In Table II, the BCGA and ICGA operating costs refer to the average of ten trial runs for each case. The results show that the LR method produces better results only for the 10-unit system since, in this particular case, the LR locates the global optimum [26]. In all other cases, the ICGA produces better results that lead to significant cost savings. The fact that the ICGA steadily finds better UC schedules for larger systems seems to show its superiority over LR for practical, large-scale applications. Compared to the binary GA, the ICGA provides, on the average, better solutions for all cases examined. An interesting feature of the proposed ICGA

If the above requirements are satisfied, then the operator turns the unit off for this specific time interval and the new schedule is evaluated. If it is superior to the original, the new solution is encoded back to the chromosome; otherwise, the original solution is retained. The excessive reserve elimination operator is applied to all chromosomes in two phases. Initially, it is applied in every generation to a randomly chosen unit in each chromosome. Fig. 5 demonstrates the improvement in the evolution of the GA from the application of this operator. Then, the operator is applied every ten generations to all units in every chromosome. The effect of this application is illustrated in Fig. 6. The GA now converges very fast to the LR solution and locates a significantly better solution. c) Chromosome length augmentation: The excessive reserve elimination operator breaks an operating cycle of a unit into several cycles of smaller duration. Thus, the maximum number of cycles assigned to such a unit at initialization (5) is not sufficient. To overcome this problem, the chromosomes in our implementation have the ability to increase their length so as to include the necessary new cycles. In order for all of the chromosomes of the same population to have the same length,

DAMOUSIS et al.: A SOLUTION TO THE UNIT-COMMITMENT PROBLEM USING INTEGER-CODED GA

1171

TABLE III NUMBER OF GENERATIONS AND RESPECTIVE EXECUTION TIMES NEEDED BY THE BINARY AND INTEGER-CODED GAS IN ORDER TO CONVERGE

REFERENCES

[1] A. I. Cohen, V. Brandwajn, and S. K. Chang, “Security constrained unit commitment for open markets,” in Proc. 21st Power Ind. Comput. Applicat., 1999, pp. 39–41. [2] PJM Manual for Scheduling Operations (2002). http://www.pjm.com [Online] [3] NYISO Day Ahead Scheduling (2001). http://www.nyiso.com [Online] [4] A. J. Wood and B. F. Wollenberg, Power Generation Operation and Control. New York: Wiley, 1984. [5] H. H. Happ, R. C. Johnson, and W. J. Wright, “Large scale hydro-thermal unit commitment-method and results,” IEEE Trans Power App. Syst., vol. PAS-90, pp. 1373–1383, May/June 1971. [6] C. J. Baldwin, K. M. Dale, and R. F. Dittrich, “A study of economic shutdown of generating units in daily dispatch,” IEEE Trans. Power App. Syst., vol. PAS-78, pp. 1272–1284, 1960. [7] C. K. Pang and H. C. Chen, “Optimal short-term thermal unit commitment,” IEEE Trans. Power App. Syst., vol. PAS-95, pp. 1336–1346, July/Aug. 1976. [8] C. K. Pang, G. B. Sheble, and F. Albuyeh, “Evaluation of dynamic programming based methods and multiple area representation for thermal unit commitments,” IEEE Trans. Power App. Syst., vol. PAS-100, pp. 1212–1218, Mar. 1981. [9] W. L. Snyder, H. D. Powell Jr., and J. C. Rayburn, “Dynamic programming approach to unit commitment,” IEEE Trans. Power Syst., vol. PWRS-2, pp. 339–350, May 1987. [10] W. J. Hobbs, G. Hermon, S. Warner, and G. B. Sheble, “An enhanced dynamic programming approach for unit commitment,” IEEE Trans. Power Syst., vol. 3, pp. 1201–1205, Aug. 1988. [11] G. S. Lauer, D. P. Bertsekas, N. R. Sandell Jr., and T. A. Posbergh, “Solution of large-scale optimal unit commitment problems,” IEEE Trans. Power App. Syst., vol. PAS-101, pp. 79–86, Jan. 1982. [12] A. Merlin and P. Sandrin, “A new method for unit commitment at Electricite de France,” IEEE Trans. Power App. Syst., vol. PAS-102, pp. 1218–1225, May 1983. [13] A. I. Cohen and S. H. Wan, “A method for solving the fuel constrained unit commitment problem,” IEEE Trans. Power Syst., vol. PWRS-2, pp. 608–614, Aug. 1987. [14] F. Zhuang and F. D. Galiana, “Toward a more rigorous and practical unit commitment by Lagrangian relaxation,” IEEE Trans. Power Syst., vol. 3, pp. 763–770, May 1988. [15] F. N. Lee, “A fuel-contrained unit commitment method,” IEEE Trans. Power Syst., vol. 4, pp. 691–698, Aug. 1989. [16] S. Virmani, C. Adrian, K. Imhof, and S. Mukherjee, “Implementation of a Lagrangian relaxation based unit commitment problem,” IEEE Trans. Power Syst., vol. 4, pp. 1373–1380, Oct. 1989. [17] A. I. Cohen and M. Yoshimura, “A branch-and-bound algorithm for unit commitment,” IEEE Trans. Power App. Syst., vol. PAS-102, pp. 444–451, Feb. 1983. [18] L. F. B. Baptistella and J. C. Geromel, “A decomposition approach to problem of unit commitment schedule for hydrothermal systems,” Proc. IEEE, pt. D, vol. 127, p. 250, Nov. 1980. [19] N. Alguacil and A. J. Conejo, “Multiperiod optimal power flow using Bender’s decomposition,” IEEE Trans. Power Syst., vol. 15, pp. 196–201, Feb. 2000. [20] F. Zhuang and F. D. Galiana, “Unit commitment by simulated annealing,” IEEE Trans. Power Syst., vol. 5, pp. 311–318, Feb. 1990. [21] C. Wang and S. M. Shahidehpour, “A decomposition approach to nonlinear multi-area generation scheduling with tie-line constraints using expert systems,” IEEE Trans. Power Syst., vol. 7, pp. 1409–1418, Nov. 1992. [22] Z. Ouyang and S. M. Shahidehpour, “A multi-stage intelligence system for unit commitment,” IEEE Trans. Power Syst., vol. 7, pp. 639–646, May 1992. [23] H. Sasaki, M. Watanabe, and R. Yokoyama, “A solution method of unit commitment by artificial neural networks,” IEEE Trans. Power Syst., vol. 7, pp. 974–981, Aug. 1992. [24] G. B. Sheble and T. T. Maifeld, “Unit commitment by genetic algorithm and expert-system,” Elect. Power Syst. Res., vol. 30, no. 2, pp. 115–121, July/Aug. 1994. [25] X. Ma, A. A. El-keib, R. E. Smith, and H. Ma, “A genetic algorithm based approach to thermal unit commitment,” Elect. Power Syst. Res., vol. 34, pp. 29–36, 1995. [26] S. A. Kazarlis, A. G. Bakirtzis, and V. Petridis, “A genetic algorithm solution to the unit commitment problem,” IEEE Trans. Power Syst., vol. 11, pp. 83–92, Feb. 1996.

Fig. 7.

BCGA versus ICGA execution time.

is that it does not require additional generations in order to converge as the system size increases from 10 to 100 units. This fact demonstrates the robustness of the new algorithm, since it is not necessary to test many GA configurations (regarding population size and maximum number of generations) in order to achieve a high-quality solution. Table III reports the execution time [on an Intel Pentium IV 1.60-GHz and 512-Mb random-access memory (RAM)] and the number of generations needed by the BCGA of [26] and the ICGA, in order to converge to the solutions reported in Table II. Fig. 7 gives the scaling of the execution time with the system size for both the BCGA of [26] and the ICGA. As illustrated from the results presented in Table III and Fig. 7, the ICGA is faster than BCGA for large systems, owing to the fact that the number of generations needed for convergence of the ICGA does not increase with system size. V. CONCLUSION In this paper, we presented a new GA for the solution of the UC problem. The use of integer coding and the use of new genetic operators differentiates the new GA from previous, binary GA implementations. In addition, two new problem-specific operators that drastically improve the performance of the algorithm are introduced. The result is a GA that produced better results than the popular LR method that was used as a benchmark, while the execution time is reduced compared to binary GA implementations. Finally, the new algorithm showed remarkable robustness since it did not require heuristic changes to the population size or the number of generations in order to converge, regardless of the system’s size.

1172

IEEE TRANSACTIONS ON POWER SYSTEMS, VOL. 19, NO. 2, MAY 2004

[27] A. Rudolf and R. Bayrleithner, “A genetic algorithm for solving the unit commitment problem of a hydro-thermal power system,” IEEE Trans. Power Syst., vol. 14, pp. 1460–1468, Nov. 1999. [28] W. G. Xing and F. F. Wu, “Genetic algorithm based unit commitment with energy contracts,” Int. J. Elect. Power, vol. 24, no. 5, pp. 329–336, June 2002. [29] J. M. Arroyo and A. J. Conejo, “A parallel repair genetic algorithm to solve the unit commitment problem,” IEEE Trans. Power Syst., vol. 17, pp. 1216–1224, Nov. 2002. [30] C. P. Cheng, C. W. Liu, and G. C. Liu, “Unit commitment by Lagrangian relaxation and genetic algorithms,” IEEE Trans. Power Syst., vol. 15, pp. 707–714, May 2000. [31] J. H. Holland, “Outline for a logical theory of adaptive systems,” J. Assoc. Comput. Mach. 3, 1962. , Adaptation in Natural and Artificial Systems. Ann Arbor, MI: [32] Mich. Univ. Press, 1975. [33] D. E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning. Reading, MA: Addison-Wesley, 1989. [34] Z. Michalewicz, Genetic Algorithms + Data Structures = Evolution Programs. New York: Springer-Verlag, 1996.

Anastasios G. Bakirtzis (S’77–M’79–SM’95) was born in Serres, Greece, in February 1956. He received the Dipl. Eng. degree from the Department of Electrical Engineering at the National Technical University, Athens, Greece, in 1979, and the M.S.E.E. and Ph.D. degrees from the Georgia Institute of Technology, Atlanta, in 1981 and 1984, respectively. Currently, he is a Full Professor with the Electrical Engineering Department at the Aristotle University of Thessaloniki, Hellas, Greece, where he has been since 1986. In 1984, he was a Consultant to Southern Company, Atlanta, GA. His research interests include power system operation and control, reliability analysis, and alternative energy sources.

Ioannis G. Damousis was born in Thessaloniki, Greece, in April 1974. He received the Dipl. Eng. and Ph.D. degrees from the Department of Electrical and Computer Engineering at the Aristotle University of Thessaloniki, Hellas, Greece, in 1997 and 2003, respectively. His research interests include neural network, fuzzy logic, and genetic-algorithm (GA) applications in power systems. Dr. Damousis is a member of the Society of Professional Engineers of Greece.

Petros S. Dokopoulos (M’77) was born in Athens, Greece, in September 1939. He received the Dipl. Eng. degree from the Technical University of Athens, Athens, Greece, in 1962 and the Ph.D. degree from the University of Brunswick, Brunswick, Germany, in 1967. Currently, he is Full Professor with the Department of Electrical Engineering at the Aristotle University of Thessaloniki, Hellas, Greece, where he has been since 1978. From 1962 to 1967, he was with the Laboratory for High Voltage and Transmission at the University of Brunswick. He was also with the Nuclear Research Center, Julich, Germany, from 1967 to 1974. From 1974 to 1978, he was with the Joint European Torus. He was a Consultant to Brown Boveri and Cie, Mannheim, Germany; Siemens, Erlagen, Germany; Public Power Corporation of Greece; and to National Telecommunication Organization of Greece and construction companies in Greece. His research interests include dielectric, power switches, power generation (conventional and fusion), transmission, distribution, and control in power systems.