European Journal of Operational Research 179 (2007) 677–691

www.elsevier.com/locate/ejor

Solving the short-term electrical generation

scheduling problem by an adaptive evolutionary approach
Jorge Maturana, Marı́a-Cristina Riff *,1

Department of Computer Science, Universidad Técnica Federico Santa Marı́a, Valparaı́so, Chile

Received 7 April 2004; accepted 23 March 2005

Available online 3 February 2006

Abstract

In this paper, we introduce an adaptive evolutionary approach to solve the short-term electrical generation sched-
uling problem (STEGS). The STEGS is a hard constraint satisfaction optimization problem. The algorithm includes
various strategies proposed in the literature to tackle hard problems with constraints such as: the representation used
a non-binary coding scheme that drastically reduces the search space compared with the traditional evolutionary
approaches. Specialized operators are especially designed for this problem and for this kind of representation, which
also includes a local search procedure. Furthermore, the algorithm is guided by an adaptive parameter control strategy.
We used some very well known benchmarks for STEGS to evaluate our approach. The results are very encouraging and
we have obtained new better values for all the systems tested. Our aim here is to show that evolutionary approaches can
be considered as good techniques to be used to solve real-world highly constrained problems.
2005 Elsevier B.V. All rights reserved.

Keywords: Evolutionary computations; Short-term electrical generation scheduling; Real-world problems

1. Introduction [16] as penalization, specialized representations,

specialized operators, hybrid repairing operators
Designing evolutionary algorithms to tackle and many others. Short-term electrical generation
hard constrained problems is a time consuming scheduling problem (STEGS) is a well known
task. In the literature, some strategies to be consid- hard constraint satisfaction optimization problem
ered in designing evolutionary algorithms have which requires many constraints to be satisfied.
been proposed to solve problems with constraints, Many techniques have been applied to solve
STEGS, including heuristics and priority lists
*
Corresponding author.
[14,20], Lagrangian relaxation [17,9,6] and simu-
E-mail address: mcriff@inf.utfsm.cl (M.-C. Riff). lated annealing [26]. In the evolutionary com-
1
Partially supported by FONDECYT Project 1040364. munity, we can find some approaches to solve

0377-2217/$ - see front matter 2005 Elsevier B.V. All rights reserved.
doi:10.1016/j.ejor.2005.03.074
678 J. Maturana, M.-C. Riff / European Journal of Operational Research 179 (2007) 677–691

STEGS, [19,4,18,24,13,23]. Hybrid evolutionary solutions. Many other methods have been applied,
algorithms that include Lagrangian relaxation, such as simulated annealing [26], unit decommit-
report the best results obtained for the classical ment [21], Fuzzy Logic [10] and Benders decompo-
benchmarks from [13]. However, these algorithms sition [11]. In the next section, we define the
are very time consuming. Our goal in this paper is problem to be tackled in this paper. This definition
to improve the performance of evolutionary algo- is the most studied one in the community, however
rithms applied to STEGS. it is important to remark that it is not the only
This paper is organized as follows, in the next existing model for STEGS. For instance, Bard in
section we present the short-term electrical sched- [2] and Turgeon in [22] consider the start-up cost
uling problem, in Section 3 we introduce our evo- as an exponential function. More recently, Hansen
lutionary approach; in Section 4 we discuss in et al., [12] propose a dynamic approach when the
detail the aspects related to the parameters of the transmission losses are represented by a quadratic
algorithm and we present the adaptive parameter formula.
control strategy, the test systems and the results
are analyzed in Section 5. Finally, in Section 6 2.1. Mathematical model
we give some conclusions and further issues.
The mathematical model, adopted from Kazar-
lis work [13], is presented in this section.
2. Short-term electrical scheduling (1) Parameters
General
Short-term electrical generation scheduling N number of generators
problem (STEGS) is, given an electrical generation T number of time windows in the horizon of
system composed of a set of electric generators, to time
determine the operation conditions of each gener- Dt power demand for time window t
ator for a certain horizon of time. This time can Rt spinning reserve
divided into time windows. Operation conditions
include to define the power level and state on/off. For each generator i:
Some market and technical constraints must be Pmini, Pmaxi bounds for power level
satisfied. STEGS is commonly divided in two Ai, Bi, Ci constants to calculate the fuel cost
sub-problems: Unit Commitment Problem Temini minimum interval of operation time
(UCP), which is to determine which generators will Tamini minimum interval of inoperating time
be operating for each time window, and Economic Tcoldi time it takes to get cold
Dispatch Problem (EDP), which is to determine Sci set-up cost when it is cold
the power level that each generator must provide. Shi set-up cost when it is hot
STEGS is a NP hard problem. Ei amount of time that it has been on
Several approaches have been used to solve this
problem. The first one uses priority lists and heu- (2) Variables
ristics [14,20], where a priority list of generators The variables of the model are the following:
is established based on their performance. One of
the most popular approaches is based on Lagrang- 1 if generator i is turned on at time window t;
xi;t ¼
ian Relaxation [17,2,5], where some hard con- 0 if not,
straints are relaxed by including them in a i ¼ 1. . .N ; t ¼ 1 .. .T .
penalization of the objective function. Thus, the
problem can be divided into smaller problems, Pi,t: power produced by generator i at time t, when
one for each generator, that can be solved sepa- it is switched on i = 1. . .N, t = 1. . .T.
rately. Another widely-used method has been (3) Objective function
based on evolutionary computation [19,4,18,24, Objective function is given by the following
13,23], where a set of individuals codify candidate formula:
J. Maturana, M.-C. Riff / European Journal of Operational Research 179 (2007) 677–691 679

N X
X T 3. Evolutionary approach
min xi;t CCðP i;t Þ þ CS i;t ; ð1Þ
i¼1 t¼1
The algorithm includes various strategies pro-
where CC(Pi,t) is the fuel cost and CSi,t is the set- posed in the literature to tackle hard problems
up cost. Fuel cost CC(Pi,t) is given by the amount with constraints such as: the representation used
of fuel that generator i spends to produce the is a non-binary coding scheme that drastically
power Pi,t. This cost is quadratic, and can be com- reduces the search space compared with the tradi-
puted by the following expression: tional evolutionary approaches. Specialized opera-
tors are especially designed for this problem and
CCðP i;t Þ ¼ Ai P 2i;t þ Bi P i;t þ Ci. ð2Þ for this kind of representation, which also includes
local search procedures. Furthermore, the algo-
Set-up cost CSi,t is included when a generator be- rithm is guided by an adaptive parameter control
gins to work. Its value depends on whether the strategy. In our approach, the constraints are con-
generator is hot or cold. To be cold the amount sidered by different components of the algorithm.
of time that the generator has been off, must be Thus, the algorithm charges the representation to
greater than Tcoldi. For each generator i, control the satisfaction of the minimum off-time
i = 1. . .N, at the time window t, t = 1. . .T, the constraints. A penalization in the fitness function
set-up cost will be calculated by considers the soft constraints related to the power
demand, and the other hard constraints are under-
Shi if generator i is hot,
CS i;t ¼ ð3Þ taken by the operators. We describe in detail all
Sci if generator i is cold.
the components of the algorithm in the following
(4) Constraints sections.
Constraints are related to market and technical
operation conditions, and are the following: 3.1. Representation
The power demand must be satisfied:
X
N The typical representations used by evolution-
xi;t P i;t ¼ Dt t ¼ 1...T. ð4Þ ary algorithms to solve STEGS are binary, which
i¼1 is a natural choice given the mathematical model
presented above. However, this coding is highly
Generators must have a security margin that make superfluous. Another drawback of this representa-
them able to produce extra power if something tion is that it is not able to deal with any con-
fails. This range is specified by the spinning reserve straint: thus, some easy constraints are violated
parameter: and a repair algorithm is required. Repairing algo-
X
N rithms usually requires an important computa-
xi;t ðPmaxi P i;t Þ P Rt t ¼ 1...T. ð5Þ tional effort, spending, in some cases, 90% of the
i¼1 total execution time [1].
We propose a representation that uses the idea
The power delivered by each generator must be-
of operation blocks.
long to its technical bounds:
Pmini 6 P i;t 6 Pmaxi i ¼ 1 . . . N; t ¼ 1 . . . T . ð6Þ Definition 1. Given a generator i, and its mini-
mum interval of inoperating time, Tamini. We
The generators must also not operate less than define one operation blocki of generator i by a pair
Temini consecutive time windows, and they must (anchor, long), that indicates that generator i is
not be turned off less than Tamini consecutive turned on at time window anchor and works for
time windows. These constraints also involve long-Tamini time windows.
the initial state. In the following section, we
introduce our evolutionary approach for this Remark 2. An individual is a sequence of opera-
problem. tion blocks, one for each generator.
680 J. Maturana, M.-C. Riff / European Journal of Operational Research 179 (2007) 677–691

Fig. 1. Representations comparison: Binary coding v/s operation blocks.

Fig. 1 shows a scheduling for 24 time windows, 3.2. Initial population

with Tamin1 = 2 and Tamin2 = 3, and 1 means the
generator is on and 0 off. We consider only two We consider that the population is only com-
generators. In the figure, each of them is repre- posed of individuals that satisfy the minimum time
sented using both kinds of representations: the tra- constraints. In the beginning of the algorithm it is
ditional binary coding and its equivalent operation important to have a diverse population. To accom-
blocks. The associated blocks for the individual plish both requirements we have designed the algo-
will be (0, 20) (because it is turned on at time win- rithm in Fig. 2.
dow 0 and works for 20 2 = 18 time windows),
and (0, 13)(15, 11) (turned on at 0 and 15, and
works for 13 3 = 10 and 11 3 = 9 time win-
dows respectively). The individual representation
in our algorithm only uses operation blocks.
The variables anchor and long must satisfy some
constraints. These constraints are the following:

• anchor P 0: a generator must be turned on

within the scheduling time.
• long P Temin + Tamin: a generator must be
turned on at least Temin time windows and
turned off after time windows Tamin.
• anchor must be at least equal to anchor + long
of the previous operation block, i.e. the blocks
must not overlap.

We make some remarks here about the advan-

tages of using this representation:

• Our representation just contains information

about when each generator is turned on.
• Reduction of the search space from N2 for bin-
ary representation to N for the problems con-
sidered in this paper.
• The representation controls the satisfaction of
the constraints related to the minimum times.
Thus, the algorithm does not require repairing
procedures for these constraints.
• This coding is easily understandable and
readable. Fig. 2. Initial population.
J. Maturana, M.-C. Riff / European Journal of Operational Research 179 (2007) 677–691 681

We consider here three states for the generators: In this case, it is changed to the following
on, off and not assigned. In the beginning, all gen- block.
erators are not assigned. The algorithm randomly In the smart version, the survivals are the lower
selects a generator and an hour. It analyzes if the cost individuals among the parents and their chil-
generator can be switched on according to both dren.
the power deficit and the hours required by Tamin. In its naive version, the two survivals are
Otherwise, the generator is switched off. selected randomly among the parents and their
children.
3.3. Specialized genetic operators
3.3.2. Asexual operators
Genetic operators use our representation to We include four asexual operators, especially
generate only feasible individuals. Thus, the other designed to act on specific parts of the operation
constraints which are not controlled by the repre- blocks:
sentation, are managed by the operators.
Anchor-mutation: It modifies the value of anchor
3.3.1. Recombination operators variable producing a displacement of the opera-
We designed two recombination operators. tion block. Only feasible displacements are
Each operator has two versions: a smart one, to considered.
choose the better option, and a naive one, which Long-mutation: It modifies the value of long
uses a random selection. The smart versions guide variables, producing the enlargement or shrink-
the algorithm to do more exploitation, and the age of the block. Analogously, only feasible
naive versions allow the algorithm to do explora- modifications are taken into account.
tion of the search space. Both recombination oper- Destroy-mutation: It kills a block, i.e., it turns
ators, take two parents to generate two offsprings, off the generator for the time windows specified
cutting the parents at one-point. The first operator on the block.
cuts the individuals looking at the generators and Create-mutation: It inserts a new block.
the second one cuts the parents looking at the time
windows. These operators have both, a smart and a naive
version. The smart versions are hill-climbing pro-
(Generator-crossover). It interchanges the gener- cedures which use the best improvement strategy.
ator scheduling after the cut point. In the The naive versions of these operators help the
smart version, the algorithm selects the cut point algorithm to do exploration of the search space.
in order to obtain an offspring with a lower cost. All of them are included in the algorithm.
It selects the two individuals among the parents
and their children with the best fitness evalua- 3.3.3. Specific operator
tions for the next population. In its naive We also designed a specialized operator that is
version, the choice of the cut point is random. stricter in terms of the reduction of the costs,
(Time-crossover). It is focused on the time win- denominated gener-swap. The main idea of
dows. It interchanges the time schedules after gener-swap is to replace inefficient generators by
the cut point. This cut point is randomly gener- efficient ones. Thus, we need to define a measure
ated, but it must be a feasible cut point for each that relates to both the performance and the utili-
block. Thus, we must respect the following zation degree of each generator.
rules:
• If the cut point does not belong to any block, Definition 3. Given SGETS we define the measure
the cut point is changed to the nearest block. of performance and utilization of generator i, URi
• If the cut point belongs to a block, the cut as
point is moved to the beginning of the block
in case it is not close to the end of the block. URi ¼ time windows used Costmax =Powermax . ð7Þ
682 J. Maturana, M.-C. Riff / European Journal of Operational Research 179 (2007) 677–691

A high value of UR will indicate an over-used inef- require evaluation, we define a new light evalua-
ficient generator, while a low value of UR will tion. This is an approximation of the heavy evalu-
mean a sub-used efficient generator. ation but it is roughly six times faster. Light
evaluation computes the cost considering that the
To make the replacement, gener-swap operator
generators are operating in their higher power lev-
makes a systematic elimination of the schedules of
els, thus it is the maximum cost expected. Light
generators with extreme values of UR. Then the
evaluation does not perform EDP computation,
scheduling is reconstructed using a heuristic based
but is a good approximation to establish a ranking
procedure, beginning with the most efficient gener-
of individual’s costs. Our main idea is to use heavy
ators, giving them first priority to cover the power
evaluation only for the better individuals. The rest
demand.
of the population is evaluated using the light eval-
Definition 4. Given a generator i, at time t, we uation, because it is usually composed of individu-
define a supply condition. It values TRUE if at least als that are not satisfying the power demand level.
Temin
2 hours within {t, t + Temin} have an unsatis- Thus, if we calculate their fitness evaluations using
fied power demand and are FALSE in another the heavy evaluation, we obtain very similar values
case. because of penalization. Heavy evaluation is
applied on about 14 of the population, during the
The procedure is shown in Fig. 3.
first 95% of the generations. In the last 5%, only
heavy evaluation is used, in order to do a fine
3.4. Evaluation
exploitation of the search space. The penalty coef-
ficients change at each generation according to the
Most of the problem constraints are undertaken
cost ratio between the production of megawatt and
by both the representation and the operators.
the power generation cost. A rank-based evalua-
However, since the constraints of the power sup-
tion was adopted due to the enormous differences
ply demand are considered as soft constraints, we
in the cost of the individuals [16], because of penal-
include them by a penalization in the fitness func-
ization of some of them, this makes the effect of
tion. Thus, the fitness function is composed of:
applying heavy evaluation over all the individuals
despicable.
• A set-up cost, when a generator changes from
Once all the individuals are evaluated, they are
off to an on state.
selected by roulette-wheel, considering also the
• The fuel cost, corresponding to the cost of fuel
individuals of the previous generation in order to
consumed when the generator is operating.
keep low-cost individuals in the population.
• A penalization when the power demand is not
supplied.
3.4.1. Heavy evaluation solving EDP
The set-up cost depends on the size of the time In order to make the paper self content we
window when the generator has been switched off. briefly describe the algorithm used to compute
To obtain the fuel cost, the algorithm uses a EDP.
local optimization procedure to determine the Given kðP Þ ¼ dFCdPi ðP Þ, the incremental fuel cost in
optimal level of power to be generated by each function of power delivered, where FCi(P) corre-
generator in every time window. This process sponds to the fuel cost of generator i when it deliv-
involves EDP computation with high computa- ers power P. The goal is to determine the power
tional cost. EDP adjusts power levels of generators level delivery for every committed generator, such
to produce the exact amount of power required at that the fuel cost of the whole generator cluster is
the minimum cost as appears in Wood and Wol- minimized. This is done by:
lemberg [25], we call this heavy evaluation. Because
all genetic operators in their smart versions often • supplying the charge required, and
J. Maturana, M.-C. Riff / European Journal of Operational Research 179 (2007) 677–691 683

Fig. 3. Gener-swap operator.

• when is possible, setting all committed genera- The algorithm is shown in Fig. 4, where THR
tors to produce the amount of power that corresponds to the smaller difference between
makes ki = k for all generators i, [25] (it is not Pi(k) and the charge required (power demand) to
possible when k is out of bound for generator i). accept a solution (acceptance threshold).
684 J. Maturana, M.-C. Riff / European Journal of Operational Research 179 (2007) 677–691

Fig. 4. EDP procedure.

4. Parameters the algorithm. It specifies the number of gener-

ations while the algorithm only uses light evalu-
Many parameters determine the performance ations. After this amount of generations, the
of the algorithm. The problem gives both the algorithm continues by evaluating EDP.
number of generators and the horizon planning. • Bound of EDP: it represents a cost value. All
Among the classical parameters for an evolution- individuals having a cost lower than this bound
ary algorithm are the population size and the are evaluated including full EDP.
number of generations. We include other para- • EDP Tolerance: to calculate EDP we use an
meters that are associated to the fitness function, iterative process that depends at each iteration
which are relevant to both, to find a good solution on the parameter k, thus the procedure finds a
and to reduce the execution time. near-optimal value. EDP Tolerance indicates
the maximum difference accepted between the
• Penalization: this value is associated to the supplied and requested amounts.
number of required megawatts that are not sup-
plied. The penalization value is for 1 MW not 4.1. Adaptive parameter control
supplied. This value is bigger than the cost to
supply 1 MW using the most expensive The parameters associated to the operators
generator. require special attention. Due to the complex rela-
• Bound of light evaluation: the goal of this tionship between the operators, it is hard to know
parameter is to improve the performance of in advance the best set of parameter values [7]. At
J. Maturana, M.-C. Riff / European Journal of Operational Research 179 (2007) 677–691 685

the beginning of the implementation of our algo- 5. Results

rithm, we have tried to determine the parameter
values by tuning. However, we cannot obtain the 5.1. Test system
optimal set of values, because they are strongly
interdependent. The first results obtained were Although there is a huge bibliography related to
really not encouraging. Using the set of parameter STEGS, there are few standard test systems to
values, found by tuning, the algorithm was only compare performances of different algorithms.
able to solve around 30% of the problems tested. The most widely used system is that proposed by
Thus, we include a parameter control strategy, Kazarlis et al. [13], with 10–100 generators with
which allows the algorithm to modify its parame- a horizon of scheduling of one day and time win-
ter values according to the state of the search. dows of one hour.
An adaptive parameter control was introduced in The spinning reserve is assumed as 10% of the
Riff and Bonnaire [15]. The operator’s probabili- demand for each hour. The base case contains 10
ties change during the execution, depending on generators and the larger cases are derived by mul-
the performance of the related operators. At the tiplying the base case for 2, 4, 6, 8 and 10 genera-
beginning, all operators have the same probability tors and power demand for each hour. The
value however, in the following generations they specifications for generators and power demand
are modified according to the next equation: appear in Tables 1 and 2, respectively.
The program was coded in C/C++, compiled
Probi;t ¼ ð1 aÞ Ri;t þ a Probi;t1 ð8Þ
with g++ in Red Hat Linux 8.0 and executed in
where Probi,t is the probability of application of a 2 GHz Pentium 4 processor machine, with
operator i at generation t, Ri,t is the reward (ex- 512 MB of RAM. The population size ranged
pressed as probability) for the operator i at gener- from 20 to 40 individuals, over 1000 generations.
ation t and a is a momentum parameter, to avoid
the abrupt changes caused by operators’s occa- 5.2. Evaluation of adaptive parameter control
sional successes, smoothing probability modifica- strategy
tions. As it was suggested in [15] we consider
here a equal to 0.2 for mutations and equal to Fig. 5 shows the variation of the mutation
0.3 for crossovers. probability of the four mutation operators. The
We also need to balance between smart and most successful operator is the long-mutation
naive versions. This equilibrium is controlled by followed by the create-blocks. The adaptive
a parameter that we determine by tuning. The parameter control strategy produces competition
results of this strategy are presented in the follow- among the operators. It increases the probability of
ing section. the operator that helped to find better individuals.

Table 1
Generators specification, Kazarlis96 system
Pmin Pmax A B C Temin Tamin Sh Sc Tcold E
150 455 0.00048 16.19 1000 8 8 4500 9000 5 8
150 455 0.00031 17.26 970 8 8 5000 10000 5 8
20 130 0.00200 16.60 700 5 5 550 1100 4 5
20 130 0.00211 16.50 680 5 5 560 1120 4 5
25 162 0.00398 19.70 450 6 6 900 1800 4 6
20 80 0.00712 22.26 370 3 3 170 340 2 3
25 85 0.00079 27.74 480 3 3 260 520 2 3
10 55 0.00413 25.92 660 1 1 30 60 0 1
10 55 0.00222 27.27 665 1 1 30 60 0 1
10 55 0.00173 27.79 670 1 1 30 60 0 1
686 J. Maturana, M.-C. Riff / European Journal of Operational Research 179 (2007) 677–691

Table 2
Power demand for every hour, Kazarlis96 system
Time 1 2 3 4 5 6 7 8
Power 700 750 850 950 1000 1100 1150 1200
Time 9 10 11 12 13 14 15 16
Power 1300 1400 1450 1500 1400 1300 1200 1050
Time 17 18 19 20 21 22 23 24
Power 1000 1100 1200 1400 1300 1100 900 800

Fig. 5. Variation of the mutations probabilities.

Thus, the algorithm can regulate the power of able for time-crossover to obtain children which
each operator according to the search. In the do not completely supply the power demand. In
case of crossover operators the competition is this case, penalization is applied and the smart
between generator-crossover and time-crossover. version of the operator selects one of the parents
We can observe in Fig. 6 that generator-cross- instead of a new child. However, when the
over increases its probability value very quickly. demand is satisfied this operator shows a good
We can explain this result because it is quite prob- performance.

Fig. 6. Variation of the crossovers probabilities.

J. Maturana, M.-C. Riff / European Journal of Operational Research 179 (2007) 677–691 687

5.3. Comparisons The algorithm identified as LRV is a Lagrang-

ian relaxation implementation, the same as LRC.
Kazarlis96 system results are shown in Table 3. GAV is a standard genetic algorithm, and MAV
These results are based on 10 runs. Blank spaces is a memetic algorithm. LRsV is a Lagrangian
mean unavailable data in the corresponding relaxation algorithm executed for a few iterations
publication. just to seed LRMAV, which is also a memetic

Table 3
Results comparison, Kazarlis96 system
Algorithm Issue Number of generators
10 20 40 60 80 100
LRV Best 566107 1128362 2250223 3374994 4496729 5620305
Average 566493 1128395 2250223 3374994 4496729 5620305
Worst 566817 1128444 2250223 3374994 4496729 5620305
GAV Best 565866 1128876 2252909 3377393 4507692 5626362
Average 567329 1130160 2262585 3394044 4525204 5669362
Worst 571336 1131565 2269282 3401847 4552982 5690086
MAV Best 565827 1127254 2252937 3388676 4501449 5640543
Average 566453 1128824 2262477 3394830 4527779 5665803
Worst 566861 1130916 2270361 3408275 4545305 5698039
LRsV Best 567663 1129663 2250223 3374994 4496729 5621796
Average
Worst
LRMAV Best 566686 1128192 2249589 3370595 4494214 5616314
Average 566787 1128213 2249589 3370820 4494378 5616699
Worst 567022 1128403 2249589 3371272 4494439 5616900
EAM Best 557110 1116240 2228070 3363220 4473210 5597470
Average 562018 1120010 2246736 3367000 4484988 5605562
Worst 565162 1122440 2255740 3370890 4492410 5612260
GAK Best 565825 1126243 2251911 3376625 4504933 5627437
Average
Worst 570032 1132059 2259706 3384252 4510129 5637914
GAG Best 565169 1128075 2252201
Average 566045 1129328 2254329
Worst 567117 1130899 2260114
LRC Best 565825 1130660 2258503 3394066 4526022 5657277
Average
Worst
GAC Best 565825 1126243 2251911 3376625 4504933 5627437
Average
Worst
LRGAC Best 564800 1122622 2242178 3371079 4501844 5613127
Average
Worst
DPV Best 565827
Average
Worst
688 J. Maturana, M.-C. Riff / European Journal of Operational Research 179 (2007) 677–691

algorithm. GAK, GAG and GAC are genetic algo- A graphical comparison of the above data is
rithms with specialized operators and representa- presented in the following charts.
tions. LRGAC is a coupled of LRC and GAC. Fig. 7 shows the best, the average and the worst
DPV is a dynamic programming algorithm and cost obtained over 10 executions. Fig. 7a shows the
EAM is the evolutive algorithm presented in this results for the 10-generator system. We report a
work. All algorithm names ending with letter new best solution of $557.110 here. Fig. 7b corre-
‘‘V’’ has been developed by Valenzuela and Smith sponds to a 20-generator system. In all the execu-
[23], with ‘‘C’’ are from Chen et al. [3], ‘‘K’’ is from tions the final cost is always lower than any
Kazarlis, Bakirtzis and Petridis [13], ‘‘G’’ is from minimum cost previously obtained with previous
Gil [8], and ‘‘M’’ is the one proposed in this paper. systems. Our algorithm found a new best solution

Fig. 7. Comparison 10, 20 and 40-generator systems.

J. Maturana, M.-C. Riff / European Journal of Operational Research 179 (2007) 677–691 689

of $1.116.240. Fig. 7c shows the 40-generator case, Finally, Fig. 8c shows the 100-generator case.
with a new best solution of $2.228.070. The same as in the 20-generator and 80-generator
Fig. 8a shows the system with 60 generators. In case, all the solutions are better than any previous
this case the best and average solutions are better solution found in other studies. We report a new
than the best value obtained in previous studies. best solution of $5.597.470.
The algorithm found a new best solution of The gap between the best known solutions and
$3.363.220. Fig. 8b shows the results for the 80- our results vary from 2% to 20% improvement.
generator system. All the solutions obtained in this The execution times were absolutely acceptable,
study are better than any solution previously from 7 seconds for the 10-generator system to less
found. A new best solution of $4.473.210 is set. than 5 minutes for the 100-generator system.

Fig. 8. Comparison 60, 80 and 100-generator systems.

690 J. Maturana, M.-C. Riff / European Journal of Operational Research 179 (2007) 677–691

6. Conclusions power systems, which is a crucial source of energy

in our country.
An evolutionary algorithm was proposed to
solve the STEGS problem.
Various aspects have been considered, mainly Acknowledgements
the coding and evaluation, in order to obtain good
quality solutions with high-performance We would like to thank Prof. Claudio Moraga
algorithms. for his discussions and suggestions. Thanks are
Good results were obtained in acceptable CPU also owed to the anonymous referees whose com-
times, setting new best solutions for all the systems ments have led to a significant improvement of
tested. the paper.
The central elements used to achieve the results
presented above are the following:
References
• A new coding scheme, that has produced a con-
[1] J. Arroyo, Modelos y algoritmos para la explotación
siderable reduction in the search space. This rep- óptima de la generación en sistemas eléctricos centraliza-
resentation can be used by other metaheuristics. dos y competitivos mediante algoritmos genéticos y pro-
• The specialized operators of mutation and gramación lineal entera-mixta. PhD thesis, Departamento
crossover, which work coherently with the cod- de Ingenierı́a Eléctrica, Electrónica y Automática, Uni-
ing, generating feasible individuals. versidad de Castilla, La Mancha, 2000.
[2] J. Bard, Short-term scheduling of thermal-electric genera-
• The existence of both smart and naive opera- tors using Lagrangian relaxation, Operations Research 36
tors, which allow control exploration and (5) (1988).
exploitation of the search space in the same [3] C. Cheng, C. Liu, C. Liu, Unit commitment by Lagrangian
algorithm. relaxation and genetic algorithms, IEEE Transactions on
• The gener-swap operator, an economic and Power Systems 15 (2) (2000).
[4] D. Dasgupta, Unit commitment in thermal power gener-
powerful mechanism that improves the conver- ation using genetic algorithms, in: Proceedings of Sixth
gence of the algorithm. International Conference on Industrial & Engineering
• The rank-based evaluation allows a quick com- Applications of Artificial Intelligence and Expert Systems
parison between individuals. (IEA/AIE-93), 1993, pp. 374–383.
[5] D. Dentcheva, R. Gollmer, A. Möller, W. Römisch, R.
Shultz, Solving the unit commitment problem in power
We have shown that evolutionary approaches generation by primal and dual methods, in: Progress in
can be considered as good techniques to be used Industrial Mathematics at ECMI 96, 1997, pp. 332–339.
to solve real-world highly constrained problems. [6] E. Dotzauer, An introduction to short-term scheduling of
There are several aspects that could increase the power and cogeneration systems, PhD thesis, Department
performance of the algorithm. of Mathematics, Linköping University, Sweden, 2001.
[7] A. Eiben, R. Hinterding, Z. Michalewicz, Parameter
The inclusion of more information about the control in evolutionary algorithms, IEEE Transaction on
domain can filter the search space even more. Evolutionary Computation 3 (2) (1999) 124–141.
For example, there are hours during which all [8] E. Gil, Programación de la generación de corto plazo en
generators must be necessarily switched on. An sistemas hidrotérmicos usando algortimos genéticos, Mas-
interesting contribution from the electrical engi- ter’s thesis, Departamento de Electricidad, Universidad
Técnica Federico Santa Marı́a, 2001.
neering field could be the definition of bench- [9] R. Gollmer, M. Nowak, W. Römisch, R. Shultz, Primal
marks that include different types of generators and dual methods for unit commitment in a hydro-thermal
(thermoelectric, hydroelectric, nuclear, eolic, power system, in: Proceedings 13th Power Systems Com-
etc.), different problem sizes, and various schedul- putation Conference, Norway, vol. 2, 1999, pp. 724–730.
ing horizons. This would clearly help to do better [10] X. Guan, P. Luh, B. Prasannan, Power system scheduling
with fuzzy reserve requirements, IEEE Transactions on
comparisons among diverse methods and algo- Power Systems 11 (2) (1996) 864–869.
rithms. We are going towards applying this [11] H. Habibollahzadeh, J. Bubenko, Application of decom-
approach to the real problem of hydroelectrical position techniques to short-term operation planning of
J. Maturana, M.-C. Riff / European Journal of Operational Research 179 (2007) 677–691 691

hydrothermal power system, IEEE Transactions on Power [19] D. Srinivasan, A. Tettamanzi, An integrated framework
Systems (1986). for devising optimum generation schedules, in: Proceedings
[12] P. Hansen, N. Mcadevović, A separable approximation of the 1995 IEEE International Conference on Evolution-
dynamic programming algorithm for economic dispatch ary Computing (ICEC’95), vol. 1, 1995, pp. 1–4.
with transmission losses, Yugoslav Journal of Operations [20] S. Tong, S. Shahidehpour, Z. Ouyang, A heuristic short-
Research 2 (2002) 157–166. term unit commitment, IEEE Transactions on Power
[13] S. Kazarlis, A. Bakirtzis, V. Petridis, A genetic algorithm Systems 6 (3) (1991) 1210–1216.
solution to the unit commitment problem, IEEE Transac- [21] C. Tseng, C. Li, S. Oren, Solving unit commitment by a
tions on Power Systems 11 (1) (1996) 83–92. unit decommitment method, Journal of Optimization
[14] E. Khodaverdia, A. Bramellar, R. Dunenet, Semi-rigorous Theory and Applications 105 (3) (2000) 707–730.
thermal unit commitment for large scale electrical power [22] K. Turgeon, Optimal scheduling of thermal generating
systems, in: IEEE Proceedings in Generation, Transmis- units, IEEE Transactions on Automatic Control 23 (1978)
sion and Distribution, 1986. 100–105.
[15] M.C. Riff, X. Bonnaire, Inheriting parents operators: A [23] J. Valenzuela, A. Smith, A seeded memetic algorithm for
new dynamic strategy for improving evolutionary algo- large unit commitment problems, Journal of Heuristics 8
rithms, in: Foundations of Intelligent Systems, ISMIS (2) (2002) 173–195.
2002, 2002, pp. 333–341. [24] K. Wong, Y. Wong, Thermal generator scheduling using
[16] Z. Michalewicz, Genetic Algorithms + Data Struc- hybrid genetic/simulated annealing approach, IEE Pro-
tures = Evolution Programs, Springer-Verlag, 1996. ceedings C, Generation, Transmission, and Distribution
[17] J. Muckstadt, S. Koenig, An application of Lagrangian 142 (4) (1995) 372–380.
relaxation to scheduling in power-generation systems, [25] A. Wood, B. Wollemberg, Power Generation, Operation,
Operations Research (25) (1977) 387–403. and Control, John Wiley & Sons, 1984.
[18] S. Orero, M. Irving, A genetic algorithm for generator [26] F. Zhuang, F. Galiana, Unit commitment by simulated
scheduling in power systems, International Journal of annealing, IEEE Transactions on Power Systems 5 (1)
Electrical Power & Energy Systems 18 (1) (1996) 19–26. (1990) 311–317.