Annealed Demon Algorithms Solving the Environmental / Economic Dispatch Problem
Department of Informatics, Univercity of
Emails: Aris532003@yahoo.gr, v_tsanos@yahoo.com
^{* }Corresponding author: Phone: +30 6937 480 570
Abstract
This paper presents an efficient and reliable Annealed Demon (AD) algorithm for the Environmental/Economic Dispatch (EEB) problem. The EED problem is a multiobjective nonlinear optimization problem with constraints. This problem is one of the fundamentals issues in power system operation. The system of generation associates thermal generators and emissions which involves sulphur oxides (SO_{2}) and nitrogen oxides (NO_{x}). The aim is to minimize total fuel cost of the system and control emission. The proposed AD algorithm is applied for EED of a simple power system.
Keywords
Environmental/Economic Dispatch (EED) Problem; Simulated Annealing (SA) Algorithm; Demon Algorithm.
Introduction
In electric power plants, Economic Dispatch (ED) is used to minimize fuel costs while satisfying all thermal generators and System equality and inequality constraints [1].
The generation of electricity from the fossil fuel releases contaminants, mainly sulphur oxides (SO_{2}) and nitrogen oxides (NO_{x}), into the atmosphere. As a result, EED problem has been proposed in the area of generation dispatch, which simultaneously minimizes both fuel cost and pollutant emissions [2,3].
Different techniques and heuristic methods have been proposed to handle this problem including particle swarm optimization (PSO) [46], evolutionary algorithms [7,8], fuzzy satisfactionmaximizing decision approach [9], genetic algorithm (GA) [10], artificial immune system [11] and hybrid methods [1214].
In this paper, Annealed Demon (AD) [15] method is proposed for solving the EED problem in power system.
Simulated Annealing (SA) Algorithm
The basis of SA algorithm has built on the manner in which metals recrystallise in the process of annealing. It begins at a high temperature where a metal is slowly cooled, so that the system is in thermal equilibrium at every stage. At high temperature the metal is in liquid phase. By gradually cooling of the metal, the system freezes into a minimum energy crystalline structure that is reaching a globally minimum value [16].
Suppose a state of the metal with energy E_{i} and subsequent energy state E_{j}. If ΔΕ=EjEi<=0, then state j is accepted as current state, otherwise it is accepted with probability
_{} 
(1) 
where T is the current temperature and K_{Β }is Boltzann’s constant.
The SA algorithm starts with an initial solution S_{i}. A neighborhood, s_{j}, of the solution is generated and the change in cost Δf(S_{i},S_{j}) is calculated. If a reduction in cost is found, the current solution is replaced by the neighboring solution otherwise the neighboring solution is accepted with a certain probability.
The probability of accepting a new solution is given [16]:
_{} 
(2) 
where T is the control parameter that corresponds in the analogy with annealing process.
For the solution of an optimization problem with SA algorithm the following steps are required:
§ Step 1: Find, randomly, an initial solution, which is assigned as the current solution xi .
§ Step 2: Determine the initial value of the control parameter of temperature T(O) = T_{init}
§ Step 3: Find a neighboring solution x_{j}, being i.e. a heuristic strategy and calculate the new value of the objective function f(x_{j})
§ Step 4: if f(x_{j})<=f(x_{i}), accept the trial solution, otherwise if f(x_{j})>f(x_{i}) calculate the difference of the objective function Δf = f(x_{j})f(x_{i}) and accept the new solution according to the probability _{} otherwise go to step 6
§ Step 5: Set x_{i }= x_{j} and f(x_{i})=f(x_{j}) and calculate the current simulated temperature with coefficient α (0<α<1) and decrease the simulated temperature gradually at every iteration, so that at (k+1) iteration: T(k+1) = aTk , where k is the iteration index.
§ Step 6: If the current simulated temperature is low, according to a cooling schedule, accept the current solution as being optimum, otherwise go to step 3.
Demon Algorithm
The Demon algorithm is an improved generalization of the SA algorithm [17]. The need of finding such an algorithm derived from the analysis of stochastic heuristic algorithms, where we must find the minimum number of evaluations of the objective function of a problem. This is a necessity in order for the system to move from a small number of conditions to another. The sum of these conditions derives from a distribution which defines the probability of finding a specific solution into that group.
The main purpose of this stochastic search algorithm is the change of the conditions group which is achieved through a Boltzmann distribution sequence with continued lower temperatures [18].
In general, the demon algorithm replaces the check of the acceptance probability with a variable named “Demon”. When the algorithm accepts a new solution of better cost it adds the cost difference to the demon variable. When the algorithm accepts a worse solution it subtracts the cost difference from the demon variable. While Demon has a value that can “afford” worse solutions it continues accepting them.
For the application of the demon algorithm we must consider the following
1. States of the system: they correspond to the acceptable solutions of a problem.
2. Energy : it corresponds to the cost of the objective function
3. Demon : it corresponds to a parameter that controls the acceptance probability of a solution
4. Cooling condition: Optimal solution of the algorithm.
The steps of the Demon Algorithm are [16]:
Step 1. Choose an initial state S_{i}
Step 2. Choose an initial demon energy D=D > 0
Step 3. Repeat
a) choose a new state S_{j}
b) let ΔΕ=E(S_{j})E(S_{i})
c) if ΔΕ<=D accept new state and update Demon, i.e. S_{j}=S_{i}, D=DΔΕ
d) else reject new state
Step 4. Until Stop_Condition
Annealed Demon (AD) Algorithm
The best form of the demon algorithm is the annealed demon. Annealed demon combines the benefits of the classic demon algorithm along with those from simulated annealing algorithm. In particular it exploits the calculation speed of the demon algorithm and it also gives solutions of high quality. In order to do that the Annealed demon algorithm reduces the demon variable in a manner similar to the reduction of the temperature in the simulation annealing. The steps of the Annealed demon algorithm are :
1. Choose initial state S_{i}
2. Choose an initial demon energy D=Do>0
3. repeat
(i) choose a new state S_{j}
(ii) let ΔΕ = E(S_{j})E(S_{i})
(iii) if ΔΕ<D accept new state and update demon, i.e. S_{j}=S_{i} , D=DΔΕ
(iv) else reject new state
(v) if equilibrium reached, reduce Demon according to schedule, i.e. D=a*D
4. until stop condition
Problem Formulation
The EED problem is to minimize simultaneously two conflicting objectives i.e. fuel cost and emission, while satisfying several equality and inequality constraints. The problem is formulated as follows.
Objective Functions
Minimize of Fuel Costs
The problem of an economic load dispatch (ELD) is to find the optimal combination of power generation which minimizes the fuel cost, under some constraints [19]. The ELD problem can be mathematically formulated as the following optimization problem:
Minimize
_{} 
(3) 
where: Fc = the total fuel cost ($/hr); α_{i},b_{i},c_{i} = the fuel cost coefficients of generator i^{th}; PG_{i} = the power generated by generator i^{th} (MW); n = the number of generators;
The emission dispatch problem including the SO_{2} and NO_{x} emission objectives, can be modeled using second order polynomial functions [20]:
Minimize
_{} 
(4) 
Minimize
_{} 
(5) 
Units of ESO_{2} and ENO_{x} are ton/h.
Problem Constraints
Power Balance Constraints
The total power generation must cover the total demand, P_{D}(MW) and the real power loss, P_{L}(MW) in transmition lines. Hence
_{} 
(6) 
The transmission losses are given by:
_{} 
(7) 
where P_{L} = Power loss, B_{ij} = transmition losses coefficients, PG_{i}=Power generated by i^{th} generator, PG_{j} = Power generated by j^{th }generator.
Generation Capacity Constraints
The power output of each generator should lie between it’s minimum and maximum limits.
_{} 
(8) 
where: PG_{i}min = minimum power generated, and PG_{i}max = maximum power generated.
Implementation of Annealed Demon (AD) Algorithm in Environmental/Economic Dispatch (EED) Problem
The steps of the algorithm (AD) in order to solve the EED problem are :
· Step 1. Initialization of the demon value and definition of the termination criterion (number of repetitions). Selection of an initial random solution state, which derives from the calculation of the total cost (objective function) in order to meet the criteria from restrictive conditions (6) and (8).
· Step 2. Find a neighboring solution through a random perturbation of the counter one in respect to the restrictive conditions (6) and (8)
· Step 3. Calculate the new total cost of the objective function (F_{c})
· Step 4. If the new solution is better then we accept it and we add the Energy Difference (ΔΕ) to the demon variable. If the new solution is worse then we accept it and we subtract the energy difference (ΔΕ) to the demon variable. Worst Solutions are accepted only if the demon variable has enough big value to “pay” for the (ΔΕ) of the worst solution.
· Step 5. We decrease the demon variable by a factor α* EΔ = α*ΕΔ
· Step 6. If we don’t meet termination criteria then go to Step 2
Case Study
The annealed demon (AD) algorithm was applied to a 3 generator test system [19] whose data are given below. The system demand is 850 MW.
_{ }
Table 1. Fuel Cost Coefficients
Unit i 
a_{i} 
b_{i} 
c_{i} 
PG_{i} min 
PG_{i} max 
1 
561.0 
7.92 
0.001562 
150.0 
600.0 
2 
310.0 
7.85 
0.00194 
100.0 
400.0 
3 
78.0 
7.97 
0.00482 
50.0 
200.0 
α_{i},b_{i},c_{i} = the fuel cost coefficients of generator i^{th}; PG_{i} min = minimum power of generator i^{th} PG_{i} max = maximum power of generator i^{th} 
The transmition losses are calculated using a simplified loss expression:
P_{L} = 0.00003PG_{1}^{2} + 0.00009PG_{2}^{2} + 0.00012PG_{3}^{2}
SO_{2} and NO_{x }emission coefficients are taken from [20] and are shown in tables 2 and 3 respectively
Table 2. SO_{2} Emission coefficients
Unit i 
a_{is} 
b_{is} 
c_{is} 
1 
1.6103e6 
0.00816466 
0.5783298 
2 
2.1999e6 
0.00891174 
0.3515338 
3 
5.4658e6 
0.00903782 
0.0884504 
a_{iS},b_{iS},c_{iS} = coefficients of SO_{2} emissions (see eq.4) 
Table 3. NO_{x} Emission coefficients
Unit i 
a_{iN} 
b_{iN} 
c_{iN} 
1 
1.4721848e7 
9.4868099e5 
0.04373254 
2 
3.0207577e7 
9.7252878e5 
0.055821713 
3 
1.9338531e6 
3.5373734e4 
0.027731524 
a_{iN},b_{iN},c_{iN} = coefficients of NO_{x} emissions (see eq.5) 
Simulation of the (AD) Algorithm
In table 4 we present the results for the (AD) algorithm. In our simulations
the demon value is 100, temperature is 100, alpha factor is 0.9 and repetitions
we choose 1000. All the simulations made in a Core 2 Duo at 1.8 GHz with 2GB
RAM. The programming language we used is
Table 4. Minimum values of individual objectives
Number of execution 
Fuel Cost 
Emissions of SO_{2} 
Emissions of NO_{x} 
1 
8.344.593 
8.990 
0.096 
2 
8.362.288 
8.968 
0.097 
3 
8.387.265 
8.966 
0.1 
4 
8.357.183 
9.020 
0.098 
5 
8.359.827 
9.000 
0.098 
6 
8.376.034 
8.966 
0.096 
7 
8.377.415 
9.019 
0.114 
8 
8.344.593 
8.971 
0.096 
9 
8.388.149 
9.014 
0.098 
10 
8.344.725 
8.968 
0.096 
Final Solution  Convergence Solution  Compromise Solution
From the above results we have now 3 optimum solutions for the 3 objective functions which define
· Best Fuel Cost
· Best SO_{2} Emissions
· Best NO_{x} Emissions
There are many theories for finding the best compromise solutions like the fuzzy logic theory. One of them is the simple average. In order to apply the simple average to our results we must take the best results we have come up with. Then we must calculate the average of the two power generators. The third power generator value will derive after we solve a second degree equation. Then we will simply replace the PG1, PG2 and PG3 to our initial equations and we will have the final compromise solution.
Table 5. Best Solutions so far

Best Fuel Cost 
Best SO_{2} Emission 
Best NO_{x} emission 
PG_{1} 
435.237 
552.187 
473.696 
PG_{2} 
300.088 
219.466 
285.204 
PG_{3} 
130.507 
92.864 
106.514 
Losses 
15.832 
14.517 
15.414 
Fuel Cost 
8.344.593 
8.396.533 
8.351.418 
SO_{2} Em. 
9.022 
8.966 
8.992 
NO_{x} Em. 
0.099 
0.097 
0.096 
Initially we find the average of PG_{1} and PG_{2}.
PG_{1} = (435.237 + 552.187 + 473.696) / 3 = 487.040
PG_{2} = (300.088 + 219.466 + 285.204) / 3 = 268.253
In order to find PG_{3} we must solve the following equation: ΣP_{i} – P_{D} – P_{L} = 0 which will end up to a second degree polynomial with PG_{3} as the unknown value. We solve and we come up with PG_{3} = 109.745
Since we have the PG_{1}, PG_{2}, PG_{3} values we put them to the initial equations. The following table shows the best compromise solution.
Table 6. Best compromise solution
PG_{1} 
487.040 
PG_{2} 
268.253 
PG_{3} 
109.745 
Losses 
15.038 
Fuel Cost 
8.354.982 
SO_{2} Em. 
8.983 
NO_{x} Em. 
0.096 
Conclusions
An annealed Demon (AD) algorithm has been used for solving the environmental/economic dispatch problem. In general an optimization problem is considered where simulation results on a 3generator test system considering fuel cost, SO_{2} emission and NO_{x} emission have been presented. The system demand is 850 MW in all simulations. We considered 3 different objective functions and through them we founded best fuel cost, best SO_{2} emission, and best NO_{x} emission
For the final compromise solution we used the simple average method.
References
1. Lee K. Y., Yome A. S., Park J. H., Adoptive Hopfied neural networks for economic load dispatch, IEE Transactions on Power Systems, 1998, 13(2), p. 519526.
2. Petrovic R., Kralj B., Economic and environmental power dispatch, European Journal of Operation Research, 1993, 61(1), p. 211.
3. Talaq J. H., EIHawary F., EIHawary M. E., A Summary of environmental/economic dispatch algorithms, IEEE Transactions on Power Systems, 1994, 9(3), p. 15081516.
4. Wang L.F., Singh C., Environmental / Economic Dispatch using a fuzzified multiobjective particle swarm optimization algorithm, Electric Power System Research, 2007, 77(12), p. 16541664.
5. Papiya D., Sinha A.K., Environmental economic dispatch constrained by voltage stability using PSO, In: Proceedings of IEEE International Conference on Industrial Technology, 2006, p. 18791884.
6. Jayabarathi T., Sadasivarm G., Ramachandran V., Evolutionary programming based multiarea economic dispatch with tie line constraints, Electric Machines and Power Systems, 2000, 28, p. 11651176.
7. King R. T. F. A., Rughooputy H. C. S., Deb K., Stochastic evolutionary multiobjective environmental/economic dispatch, In: Proceedings of IEEE congress on Evolutionary computation, 2006, p. 946953.
8. Abido M. A., Environmental /Economic Power Dispatch using multiobjective evolutionary algorithms, IEEE Transactions on Power Systems, 2003, 18(4), p. 15291537.
9. Huang C. M., Yang H. T., Huang C. L., Biobjective power dispatch using fuzzy satisfactionmaximizing decision approach, IEEE Transaction on Power Systems, 1997, 12, p. 17151721.
10.
Abido M. A., A new multiobjective evolutionary algorithm for
environmental/economic power dispatch, IEEE Summer Meeting,
11. Chen S.L., Tsay M.T., Gow H.J., Scheduling of cogeneration plants considering electricity wheeling using enhanced immune algorithm, International Journal of Electrical Power and Energy Systems, 2005, 27(1), p. 3138.
12.
Song Y. H., Wang G. S., Wang P. Y., Johns A. T., Environmental /
Economic dispatch using fuzzy logic controlled genetic algorithms,
13. Chaturvedi K. T., Pandit M., Srivastava L., Modified neofuzzy neuron based approach for economic and environmental optimal power dispatch, Applied Soft Computing, 2008, 8(4), p. 14281438.
14. Das D. B., Patvardhav C., New multiobjective stochastic search technique for economic load dispatch, IEE ProceedingsGeneration, Transmission and Distribution, 1998, 145(6), p. 747752.
15.
Wood I.,
16. Kirkpatcick S., Gelatt C. D., Vecchi M. P., Optimization by Simulated Annealing, Science, 1983, 220, p. 671680.
17. Zimmermann T., Salamon P., The demon algorithm, Futern. J. Computer Math., 1992, 42, p. 2131.
18. Salamon P., Hoffman K. H., Harland J., Nulton J.D., An information theoretic bound on the performance of simulated annealing algorithms, SDSU IRC report, 1988, 881.
19. Wood A. J., Wollenberg B. F., Power generation, operation and control, John Wiley and sons; IMC, 1984.
20. FoaSepulveda C. A., SalazarNova E. R., GraciaCaroca E., Knight U. G., Coonic A., Environmental Economic Dispatch via Hopfield Neural Network and Taboo Search, UPEC’96 Universities power engineering conference, Crete, Greece, 1820 September 1996, p. 10011004.