Inte rnatio nal Jo urnal o f Sc ie ntific & Eng inee ring Re se arc h Vo lume 3, Issue 3 , Marc h -2012 1

ISSN 2229-5518

Effective Genetic Algorithms & Implementation on Economic Load Dispatch

Varun Kumar Vala, Srikanth Reddy Yanala, Maheswarapu Sydulu

**Abstract**—This paper deals w ith some proposals to Conventional Genetic Algorithms to improve the perf ormance (number of iterations needed to achieve convergence, time of execution). The advantages and disadvantages of each proposal have been noted. The disadvantage of a proposal is eliminated in the next proposal to the maximum extent. Thus, w e f inally landed up in a propos al w ith least time of execution and also less number of iterations f or convergence. All the proposals made are tested by implementing on test f unction sine(x) and basic *hand calculations*. Later it has been imple mented on Economic Load Dispatch w ith Pmin and Pmax constraints. The results of all the above have been highly satisf actory and a f ew are

reported

Inde x Te rms— Best Random GA w ith termination, Best Random w ithout termination, Conventional GA , Economic Load Dispatch, Fixed

Threshold, Genetic Algorithms(GA), Optional Crossover and Mutation.

—————————— ——————————

oncisely stated, a Genetic Algorithm (GA) is an evoluti o- nary programming technique that mimics biological evo- lution as a problem-solving strategy. Given a specific optimi- zation problem to solve, the input to the GA is a set of poten- tial solutions to that problem, encoded in some fashion (mos t- ly binary coded), and a metric called a *fitness function *that al- lows each candidate to be quantitatively evaluated based on

its binary coded chromosome.

The variable x in f(x) is Xactual. The decoded Xdec is calculated value for each chromosome. Xmax and Xmin are the limits of the variable. In case of sine(x), the limits taken are [0 to 180]. The equation governing is equation 1.

These candidates are generated at random for the first itera-

tion. For the later iterations, the *operators *such as elitism, cross- over and mutation come into picture. The size of population is taken as 40 and chromosomes are 8 bit binary coded. An elitism of 20% has been followed. Roulette wheel technique is consi- dered for parent selection. Uniform cross -over is performed and probability of cross-over is taken as 0.7. The probability of mu- tation is considered as 0.005.

These operators modify the present generation and the

chromosomes thus obtained are taken into next generation. This

process is thus carried until a state of convergence is achieved. Convergence is the solution (for almost all problems pertaining to GA) where all the chromosomes will have their fitness fun c- tion value as the maximum fit value of the fun ction. Hence, the fitsum will be equal to sum of all fit va lues and that would be (maximum fit)*(population size).

However the following factors are found to affect the con- vergence and time of execution:

1) Dependence on the nature of randomly picked initial

population,

2) The negative effects of the medieval operators such as

*Srikanth Reddy Yanala is currently working as an Engineer in Corporate*

R&D,BHEL, India, PH-09985154522. E-mail:srikanth.yanala@gmail.com

*Maheswarapu Sydulu is currently working as aProfessor in National Inst i- tute of Technology, Warangal, India.)*

cross-over and mutation.

These two fundamental issues enabled us to go for mod- ified and highly effective proposals to Genetic Algorithms which emphasize more on these drawbacks of conventional GA.

In conventional GA approach, initial population (say 40 chro- mosomes) is generated randomly. If all the 40 chromosomes are having relatively good fit values, GA converges fast or else it takes more number of iterations. Hence, the quality of the initial population plays a very significant role. This motivated us for the following proposals.

Here, a random chromosome is generated and its fitness fun c- tion value is calculated. The next chromosome is again picked up similarly from the search space and its fitness value is also calculated. However, this chromosome is considered only if its fitness value is greater than or equal to the fit value of the pre- vious chromosome. Else it is discarded. The best fit value is updated. This process is carried till the required number of chromosomes (=40) had been generated.

In other words, the search space has been reduced drasti-

cally to *potential search space *by addition of a potential chromo-

some into the random generation. By this, the quality of the initial population is made better.

Advantages: The convergence was found to occur very soon

compared to the conventional GA. For example, this technique when applied to sine(x) yielded convergence within 2 itera- tions while the conventional GA took about 25 iterations.

There was no need to use dynamic elitism to achieve con- vergence.

Disadvantages: The number of chromosomes discarded near to

sag end of population size was relatively high and thus sizable time has been spent in generating a good initial population.

IJSER © 2012

Inte rnatio nal Jo urnal o f Sc ie ntific & Eng inee ring Re se arc h Vo lume 3, Issue 3 , Marc h -2012 2

ISSN 2229-5518

Best Random with termination: This is just a special case of the above proposal. This case arises when one of the chromo- somes generated randomly in above manner has its fitness value as the “maximum fit value of the function”. This is poss- ible only if the maximum value of the fitness function is known in advance to the operator (say sine(x) =1=maximum fit value). The algorithm is terminated at this instant itself be- cause “the maximum fitness value gives us the characteristics of that chromosome, and thus it is not necessary to go for fu r- ther search.” Hence this approach works very fast.

Results: Here is the implementation to test function

f(x)=sine(x). Table-1 shows the random generation obtained.

The so called convergence is achieved at 8 th chromosome of the random generation itself. Hence the process is terminated at this point itself.

Advantages: The basic operators such as the static elitism, cross-over and mutation are found to have no impact on this solution and hence this approach converges very fast. The s o- lution is obtained even before the random initial population is completely generated.

Disadvantages: The operator should know the maximum possi-

ble value of fitness function well in advance.

Fixed Threshold approach: The previous proposals were found to search the sample space a lot for the selection of a chromo- some. Here, we assign a cutoff/threshold value (typically 20-

50%) of maximum fitness value and all new chromosomes

with fit value greater or equal to this are added to the next generation or else discarded. The operators like elitism, cross - over and mutation are then carried as usual. Usually, Roulette wheel technique is used for parent selection. But, we propose a new approach to pick up a parent with reas onably better fit as given by equation 2.

Advantages: The potential search space is separated from the general search space by assigning a threshold value. Disadvantages: In spite of getting a good parent generation by the threshold setting, the number of iterations required has gone up to 6 to 10 iterations.

Inferences: As the iterations were carried, the fitsum was found

to increase for a few iterations an d decrease for some itera- tions, as per Fig-1. The reason for the decrease in fitsum was the production of low fitness function value chromosomes by relatively better parent chromosomes. This must be avoided to get convergence fast.

Table-2 gives comparison between the four techniques con-

ventional GA, Best random with and without termination and

Fixed threshold of 85% for f(x)=sine(x).

In case of conventional GA the convergence was found to

occur at the 39th generation. This clearly shows us that, though better fitsum has been achieved in some generations, it could not be carried forward due to the misguiding operation of cross-over and mutation. Hence the following proposal has been made to improve the convergence property:

Optional Cross-Over & Mutation: This technique follows the

principle of evolution strategy. The disadvantage of the above proposals is that even after obtaining a good parent generation the number of iterations required for convergence has been quite large. Also, if the graph between fitsum and iterations is plotted, it is found that the graph is not a set of straight lines with positive slopes, but rather it is a set of lines with some negative slopes too (can be observed from the fitsum values in the above table-2). This is because the operators like cross-over and mutation gave rise to low fit chromosomes in spite of good fit parent chromosomes. Hence, we have provided an option here, by which the better of the parent and child is ta k- en into the next generation. This means the parent 1 and child

1 fit values are calculated and then compared and the best is

sent to next generation. Similar is the case of parent 2 and

child 2.

In conventional GA, fit values of child 1 and child 2 are not

calculated before they are sent to next generation. Child 1 and

child 2 are simply copied into next population. But, in the proposed approach, the fit values of child 1 and child 2 are calculated and compared with the fit values of respective pa r- ents. The parent or child with the best fit is copied onto next generation with appropriate fit value. Thus, it needs no extra computational burden as fit values of new chromosomes are already known.

Illustrative example:

In the Table-3, the cases where in the parent fit is better

than the corresponding child are given (for a particular itera-

tion). As mentioned earlier, the parent is taken into the next generation as the new child as per this proposed technique. *Advantages*: The generation child(i+1) is always better than its generation by traditional approach. Hence, fast convergence is promised.

This approach would yield “fitsum vs iterations” graph

with positive slopes, as shown in Fig-2.

The convergence condition can be thought of a horizontal

straight line and the fitsum of each generation goes on increas-

ing to reach this value, as shown in Fig-2.

Thus the convergence would occur at a very fast rate.

Disadvantages: This proposal has no disadvantages yet and can

be employed in any problem be it maximization or minimiza- tion. This proposed approach can yield promised c onverged results without extra computational burden.

In the Table-4, a comparison between the Roulette Wheel technique and new parent selection approach is made. The function taken is f(x)=sine(x). The conventional GA is cons i- dered. Optional crossover and mutation is also applied to achieve convergence very fast.

Inferences: The number of iterations required has reduced dras-

tically by optional cross-over and mutation approach.

The new parent selection scheme is much better than the

Roulette wheel technique.

The Economic Load Dispatch (ELD) problems are one of the major areas of applications of Genetic Algorithms. The ELD problem is about minimizing the fuel cost of generating units for a specific period of operation s o as to accomplish optimal generation dispatch among operating units and in

IJSER © 2012

Inte rnatio nal Jo urnal o f Sc ie ntific & Eng inee ring Re se arc h Vo lume 3, Issue 3 , Marc h -2012 3

ISSN 2229-5518

return satisfying the system load demand, generator operation constraints like Pmin and Pmax.

Thus, the objective is to minimize the nonlinear function which is the total fuel cos t of thermal generating units. The objective function for the entire power system can be written

as the sum of the quadratic cost model for each generator as per the equation 4.

The economic load dispatch problem is made simpler by

neglecting the transmission losses and the constraints on bus voltages. The only constraints are on the real power outputs of the generation units. The difference between the demand on load side and total power generation, Pg (=sum of all real power outputs) is called the error function, er[i]. The fitness function is taken as equation 5.

Typical values of k in the above formula are 1, 2, 5 and 10. Thus, the load dispatch problem has turned into maximization problem of f(i).

Illustrative example:

A ten unit system is considered & is solved using the above

proposed methods. At convergence, the incremental fuel cost,

λ=1207.92 Rs/Mwhr. Real Power Demand is 2608 MW.

The economic load dispatch problem is solved by the above

proposed methods and with conventional GA. A comparison

between these has been made in the following Table-6.

The value of k is taken as 1. The probability of cross -over is

taken as 0.7. The probability of mutation is taken as 0.005 .

Inferences: The conventional GA has taken more number of iterations and needs more time of execution compared to the proposed methods.

The method “Best random with termination” is found to give the best results of all.The fixed threshold approach along with the “best random without termination” method, has been proved to be much better than the conventional GA.

In the Table-7, a comparison between the Roulette Wheel

technique and new parent selection approach is made. The

conventional GA & proposed methods are implemented on

Economic Load Dispatch.

Inferences: The above table clearly shows that the fixed thre-

shold approach for parent selection is much better than the

Roulette Wheel technique.

Fig-2: Without proposed Optional Cross -Over and Mutation

Final convergence fitsum

Xactual=Xmin +Xdec(Xmax-Xmin). E q. (1)

The decoded Xdec is calculated value for each chromosome. Xmax and Xmin are the limits of the variable. In case of sine(x), the limits taken are [0 to 180].

j=0.5*f(i)*i*(N/fitsum) Eq. (2)

where f(i) is the fitvalue of the ith chromosome and N its popu- lation size, fitsum is the sum of the fitvalues of their chromo- somes arranged in descending order of their fit and j is the chromosome to be taken as parent.

W her e *f *(Pi) =aiPi2 +b iPi+Ci , i=1, 2, 3, ...,ng...,n.

f[i]=(1/1+(k*|er[i]|)) Eq.(4)

Chromosome | Fitness | Number | of |

chromosomes | |||

discarded | |||

00000000 | 0 | 0 | |

10010000 | 0.980741 | 0 | |

01111010 | 0.997305 | 3 | |

10000011 | 0.999315 | 7 | |

01111101 | 0.999330 | 82 | |

10000001 | 0.999922 | 2 | |

10000001 | 0.999922 | 19 | |

10000000 | 1 | 34 | |

Search process completed in 0.050s |

Table-1:“Best Random with termination” implemented on sine(x).

fitsum

iterations

Fig-2: With proposed Optional Cross-Over and Mutation

Fitsum final convergence fitsum

Table-2: *Comparison between proposed methods implemented on sine(x); population size=40*

IJSER © 2012

Inte rnatio nal Jo urnal o f Sc ie ntific & Eng inee ring Re se arc h Vo lume 3, Issue 3 , Marc h -2012 4

ISSN 2229-5518

Child-fit | P are nt -fi t C hi l d(i ) P are nt (i ) C hi l d(i + 1) | |||

0.90923 | 0.998105 | 01011101 | 10000101 | 10000101 |

0.914105 | 0.997305 | 10100010 | 01111010 | 01111010 |

0.313334 | 0.995164 | 11100110 | 10001000 | 10001000 |

0.302044 | 0.993928 | 00011001 | 01110111 | 01110111 |

0.963712 | 0.992503 | 10010110 | 01110110 | 01110110 |

0.963821 | 0.992453 | 01101010 | 10001010 | 10001010 |

0.975651 | 0.980741 | 10010010 | 10010000 | 10010000 |

Table-3: *Cases where parent fit is better than the child fit.*

Table-7: *Comparison between Roulette wheel technique and Op- tional Cross-Over & Mutation, Fixed threshold approach.*

Table-4: *Comparison between Roulette wheel technique and new par- ent selection approach.*

unit | a[i] | b[i] | c[i] | Pmin [i] | Pmax [i] | Power output, P[i] |

1 | 0.3133 | 796.9 | 64782 | 220 | 550 | 550 |

2 | 0.3127 | 795.5 | 64670 | 200 | 500 | 500 |

3 | 0.7075 | 915.7 | 172832 | 114 | 500 | 413 |

4 | 0.4211 | 1250.1 | 91340 | 110 | 500 | 110 |

5 | 2.5881 | 238.1 | 190928 | 65 | 315 | 315 |

6 | 0.4921 | 696.1 | 39197 | 120 | 272 | 272 |

7 | 0.3572 | 803.2 | 28770 | 110 | 260 | 260 |

8 | 9.693 | 655.9 | 13518 | 20 | 38 | 38 |

9 | 23.915 | 1633.9 | 83224 | 25 | 60 | 25 |

10 | 1.1421 | 805.4 | 22233 | 60 | 125 | 125 |

Table-5: *Power Outputs of various units for ELD*

Proposal | It er at i ons required for convergence | Time of execution(secs) |

Conventional GA | 4 | 1.5 82 |

Bes t Random without termination | 1 | 0.8 99 |

Bes t Random with termination | 0(convergence at 7th chromos ome of firs t generation) | 0.0 57 |

Fixed thres hold(with thres hold of 0.20) | 2 | 1.0 00 |

Table-6: *Comparison between the proposed methods, for ELD*

Initially, the conventional GA has been studied in detail. The various factors affecting the nature of convergence of con- ventional GA have been explored. Taking these factors as mo- tivation, a few effective methods such as “Best Random with Termination”, Best Random without termination”, “Fixed Threshold approach along with new parent selection a p- proach” & “Optional cross -over and mutation” have been proposed. The proposed methods have been tested on the test function sine(x) and later implemented on Economic Load Dispatch. It has been observed that the proposed methods would offer convergence very fast as compared to the con- ventional GA. Especially, the “Best Random with termina- tion” was observed to be giving the best results. These pro- posed algorithms can be treated as a basic contribution in the area of Genetic Algorithms.

[1] Maheswarapu Sy dulu, A ve ry fast and e ffec tive no n-ite rativ e “λ log ic base d” eco no mic lo ad dispatc h o f the rmal uni ts,1999,IEEE TENCON.

[2] Thee rthamalai, Adhinaray an, Maheswarapu Sy dulu, Direc tio nal Se arc h Ge ne tic Algo rithm Applic atio ns to Eco no mic Dispatc h o f the rmal uni ts, Vo lume 9,No 4, July 2008,pp.211 -216(6).

[3] C.Achy uthay an, Ge ne tic Algo rithm Applic atio n to Eco no mic Lo ad Dispatc h, Maste r The sis Re po rt in Asian Institute o f Tec hno logy, Thailand,1997.

[4] S inha N, Chakrabarthi R, Chatto padhy ay.P.K, Evolutio nary Pro- g ramming Tec hniques fo r eco no mic lo ad dispatc h,IEEE Trans Evol. Co mput. v 7il. 83 -94

[5] Ge re ld B.S he ble , Kristin Brittig , Re fine d Ge ne tic Algo rithms: Ec o-

no mic lo ad dispatc h e xample ,IEEE Trans Po we r Syste ms 10 1 (1995)

[6] A.Bakirtiz, V.Pe tridis and S.A.Kazarlis, Ge ne tic Algorithm solution to eco- no mic lo ad dispatch proble m, IEEE Proc C 1414 (1994)

[7] K.Y.Lee, ”Fuel cost minimization for real and reactive power dis-

patches,” IEEE Proc. C,Gener. Trsns & distr., 131,(3),pp.83-94,1984

BOOKS: Melanie Mitchell, Introduction to Genetic Algorithms.

IJSER © 2012