An improved binary particle swarm optimization for unit commitment problem

An improved binary particle swarm optimization for unit commitment problemXiaohui Yuan a,*,Hao Nie a ,Anjun Su a ,Liang Wang a ,Yanbin Yuan ba School of Hydropower and Information Engineering,Huazhong University of Science and Technology,Luoyu Road 1037,Wuhan 430074,China bSchool of Resources and Environmental Engineering,Wuhan University of Technology,Wuhan 430070,Chinaa r t i c l e i n f o Keywords:Unit commitment Priority listParticle swarm optimization Heuristic searcha b s t r a c tThis paper proposes a new improved binary PSO (IBPSO)method to solve the unit commitment (UC)problem,which is integrated binary particle swarm optimization (BPSO)with lambda-iteration method.The IBPSO is improved by priority list based on the unit characteristics and heuristic search strategies to repair the spinning reserve and minimum up/down time constraints.To verify the advantages of the IBPSO method,the IBPSO is tested and compared to the other methods on the systems with the number of units in the range of 10–100.Numerical results demonstrate that the IBPSO is superior to other meth-ods reported in the literature in terms of lower production cost and shorter computational time.Ó2008Elsevier Ltd.All rights reserved.1.IntroductionUnit commitment (UC)is a very significant optimization task,which plays an important role in the operation planning of power systems.The unit commitment problem (UCP)in power systems refers to the optimization problem for determining the start-up and shut-down schedule of generating units over a scheduling per-iod so that the total production cost is minimized while satisfying various of constraints.UCP can be considered as two linked optimi-zation decision processes,namely the unit-scheduled problem that determines on/off status of generating units in each time period of planning horizon,and the economic load dispatch problem.Math-ematically,the UCP has commonly been formulated as a complex nonlinear,mixed-integer combinational optimization problem with 0–1variables that represents on/off status and continuous variables that represents unit power,and a series of prevailing equality and inequality constraints.However,the number of com-binations of 0–1variables grows exponentially as being a large-scale problem.Therefore,UCP is known as one of the problems which is the most difficult to be solved in power systems.Many methods have been developed to solve the UCP in the past decades.The major methods include priority list method (PLM)(Senjyu,Miyagi,&Saber,2006),dynamic programming (DP)(Su &Hsu,1991),branch-and-bound methods (BBM)(Cohen &Yoshimura,1983),integer and mixed-integer linear program-ming (MILP)(Khodaverdian,Brameller,&Dunnitt,1986;Samer &John,2000),Langrangian relaxation (LR)(Feng &Liao,2006;Ongsa-kul &Petcharaksm,2004).Among these methods,PLM is simple and fast,but the quality of final solution is not guaranteed.DP isflexible but the disadvantage is the ‘‘curse of dimensionality”,which results it may leads to more mathematical complexity and increase in computation time if the constraints are taken into con-sideration.The shortcoming of BBM is the exponential growth in the execution time with the size of P adopts linear pro-gramming techniques to solve and check for an integer P for solving UCP fail when the number of units increases be-cause they require a large memory and suffer from great computa-tional delay.These methods have only been applied to small UCP and have required major assumptions that limit the solution space.The main problem with the LR is the difficulty encountered in obtaining feasible solutions.Due to the non-convexity of the UCP,optimality of the dual problem does not guarantee feasibility of the primal UCP.Furthermore,solution quality of LR depends on the method to update Lagrange multipliers.Aside from the above methods,meta-heuristic approaches such as artificial neural networks (ANN)(Dieu &Ongsakul,2006),genetic algorithm (GA)(Damousis,Bakirtzis,&Dokopoulos,2004;Kazarlis &Bakirtzis,1996;Senjyu,Yamashiro,&Uezato,2002),evolutionary programming (EP)(Juste,Kita,&Tanaka,1999),memetic algorithm (MA)(Jorge &Smith,2002),Tabu search (TS)(Mantawy,Abdel,&Selim,1998),simulated annealing (SA)(Zhu-ang &Galiana,1990),particle swarm optimization (PSO)(Lee &Chen,2007;Ting,Rao,&Loo,2003)and greedy random adaptive search procedure (GRASP)(Viana,Sausa,&Matos,2003)have also been used to solve UCP since the beginning of the last decade.These meta-heuristic methods optimization methods attract much attention,because of their ability to search not only local optimal solution but also global optimal solution and can easily deal with various difficult nonlinear constraints.However,these meta-heu-ristic methods require a considerable amount of computational time to find the near-global minimum especially for a large-scale UCP.0957-4174/$-see front matter Ó2008Elsevier Ltd.All rights reserved.doi:10.1016/j.eswa.2008.10.047*Corresponding author.E-mail addresses:yxh71@ ,yuanxh71@ (X.Yuan).Expert Systems with Applications 36(2009)8049–8055Contents lists available at ScienceDirectExpert Systems with Applicationsjournal homepag e:/locate/eswaTo reduce the search space in large-scale UCP,hybrid methods combining meta-heuristic approaches and deterministic optimiza-tion methods such as LR and GA(LRGA)(Cheng,Liu,&Liu,2000), LR and MA(LRMA)(Jorge&Smith,2002),and PSO combined with the LR(PSOLR)(Balci&Valenzuela,2004)have been used to solve UCP.They are more efficient than the single methods due to less expensive production cost and a faster computational time.One main difficulty is their sensitivity to the choice of parameters.Thus, improving current optimization techniques and exploring new strategy to solve UCP has great significance.PSO proposed by Kennedy and Eberhart in1995has become a candidate for optimization applications due to itsflexibility and efficiency.In this paper,a new improved PSO(IBPSO)method has been proposed to solve UCP,which is integrated an improved discrete binary particle swarm optimization(BPSO)with the lamb-da-iteration method.The IBPSO is enhanced by priority list based on the unit characteristics and heuristic search strategies to repair the spinning reserve and minimum up/down time constraints.In the proposed IBPSO method,BPSO is used to solve the unit-sched-uling problem and the lambda-iteration method is used to solve the economic load dispatch problem.In solving UCP,the BPSO and lambda-iteration method are run in parallel,adjusting their solutions in search of a better solution.Finally,the proposed IBPSO method is tested on the UCP systems with the number of units in the range of10to100.Simulation results demonstrate the feasibil-ity and effectiveness of the IBPSO method in terms of solution quality and computation time compared with those of other opti-mization methods reported in the literature.This paper is organized as follows.Section2provides the math-ematical formulation of the UCP.Section3briefly introduces the basics of PSO.Section4proposes an improved binary PSO(IBPSO) method for solving UCP.Section5gives the numerical example. Section6outlines the conclusions.Finally,acknowledgements are given.2.Formulation of UCP2.1.Objective functionThe objective of UCP is tofind the generation scheduling over the scheduled time horizon such that the total production cost can be minimized while satisfied all kinds of constraints.The total cost F over the entire scheduling periods is the sum of the operat-ing cost and start-up cost for all of the units.Thus,the objective function of the UC problem ismin F¼X Tt¼1X Nt¼1½f iðP tiÞþST tið1Àu tÀ1iÞ u tið1Þwhere N is number of generators;T is total scheduling period;P tiisgeneration of unit i at time t;u tiis on/off status of unit i at time t(on=1and off=0);ST tiis start-up cost of unit i at time t.Generally,the fuel cost,f iðP tiÞper unit is a function of the gener-ator power output.Most frequently used cost function is in the form off iðP ti Þ¼a iþb i P tiþc iðP tiÞ2ð2Þwhere a i,b i and c i represent the unit cost coefficients.The generator start-up cost depends on the time the unit has been off prior to start-up.In this paper,time-dependent start-up cost is simplified using H offidefined as follows:ST ti ¼S hi if T i;down T ti;offH offiS ci if T ti;off>H offi8><>:ð3ÞH offi ¼T i;downþTcold iwhere S hi is hot start cost of unit i;S ci is cold start cost of unit i;Tcol-d i is cold start time of unit i;T i,down is minimum down time of unit i;T ti;offis continuously off time of unit i up to time t.2.2.Constraints(1)System power balanceX Ni¼1P tiu ti¼P tDð4Þwhere P tDis system load demand at time t.(2)System spinning reserve requirementX Ni¼1u tiP i max!P tDþP tRð5Þwhere P tRis spinning reserve at time t.(3)Generation power limitsP i min P tiP i maxð6Þwhere P i min and P i max are minimum and maximum genera-tion limit of unit i,respectively.(4)Unit minimum up timeA unit must be on for a certain number of hours before it canbe shut down.T ti;on!T i;upð7Þwhere T ti;onis continuously on time of unit i up to time t T i,up isunit i minimum up time.(5)Unit minimum down timeA unit must be off for a certain number of hours before it canbe brought online.T ti;off!T i;downð8Þwhere T ti;offis continuously off time of unit i up to time tT i,down is unit i minimum down time.(6)Unit initial statusThe initial status at the start of the scheduling period mustbe taken into account.3.Overview of particle swarm optimizationParticle swarm optimization(PSO),first introduced by Ken-nedy and Eberhart,is one of the heuristic optimization algo-rithms(Clerc&Kennedy,2002).A classical PSO maintains aswarm of particles that represent the potential solutions to theproblem on hand.The classical PSO model consists of a swarmof particles moving in the D-dimensional space of possible prob-lem solutions.Each particle embeds the relevant informationregarding the D decision variables and is associated with afit-ness that provides an indication of its performance in the objec-tive space.Each particle i has a position X i=(x i,1,x i,2,...,x i,D)andaflight velocity V i=(v i,1,v i,2,...,v i,D).Moreover,a swarm containseach particle i own best position Pbest i=(pbest i,1,pbes-t i,2,...,pbest i,D)found so far and a global best particle positionGbest=(gbest1,gbest2,...,gbest D)found among all the particlesin the swarm so far.In essence,the trajectory of each particle is updated accord-ing to its ownflying experience as well as to that of the bestparticle in the swarm.The standard PSO algorithm can be de-scribed as8050X.Yuan et al./Expert Systems with Applications36(2009)8049–8055v kþ1i;d¼xÁv k i;dþc1Án k1Áðpbest k i;dÀx k i;dÞþc2Án k2Áðgbest k dÀx k i;dÞð9Þx kþ1 i;d ¼x ki;dþv kþ1i;d i¼1;2;...;n;d¼1;2;...;Dð10Þwhere x is a inertia weight factor;c1is a cognition weight fac-tor;c2is a social weight factor;n1and n2are two random num-bers uniformly distributed in the range of[0,1];v k i;d is the d th dimension velocity of particle i at iteration k;x ki;dis the d thdimension position of particle i at iteration k;pbest ki;dis the d th dimension of the own best position of particle i until itera-tion k;gbest kdis the d th dimension of the best particle in the swarm at iteration k.4.Improved binary particle swarm optimization(IBPSO)for UCPThe proposed IBPSO method for solving UCP consists of three stages.In thefirst stage,combination discrete binary particle swarm optimization with priority list is used to commit units to satisfy spinning reserve neglecting the minimum up and down time constraints.In the second stage,a heuristic search algorithm is applied to repair violations of the minimum up and down time constraints as well as decommit excessive spinning reserve units based on the unit schedule from thefirst stage.In the last stage,the equal lambda-iteration method is used to solve the economic load dispatch problem.Finally,the total production costs including operational cost from economic dispatch and start-up costs from UC is calculated.When one generating units combination has the lowest total generation production cost,it will be an optimal solution of UC schedule.4.1.Binary particle swarm optimization for unit-scheduling4.1.1.Binary particle swarm optimizationThe original version of PSO operates on real values.However, the unit-scheduled problem of UCP is a discrete optimization problem with0–1decision variables representing on/off status of units,which determines on/off status of generating units in each time period of planning horizon.So it must extend the real-valued PSO to handle discrete space of the UC schedule.A clever technique for creating a discrete binary version of the PSO introduced by Kennedy and Eberhart(1997)in1997 uses the concept of velocity as a probability that a bit takes on a one or a zero.Binary PSO can be used to solve unit-sched-uled problem of UCP.But a drawback of binary PSO(Kennedy& Eberhart,1997)for solving UCP is that the particle’s position x i,d update equation has a non-standard form.In Kennedy and Eberhart(1997),by comparing the new particle’s velocity v i,d with a random number the new value for x i,d becomes0or1. Another drawback is the non-monotonic shape of the changing probability function of a bit(from0to1or vice versa).The probability function has a concave shape that for some bigger v i,d values the changing probability will decrease.This seems to be an unusual probability function because we expect a higher changing probability as the velocity increases.Moreover, the sigmoid function used to limit the v i,d values between0and 1,makes the problem nonlinear.In order to overcome the shortcomings of the binary PSO for solving UCP,this paper pro-poses a new improved binary PSO method(IBPSO)to solve UCP.An individual in the IBPSO method is a bit string which starts its trip from a random point in the search space and tries to become nearer to the global best position and previous best position of it-self.The process of generating a new position for a selected indi-vidual in the swarm can be represented by the following equations:v kþ1i;d¼x1 ðpbest k i;dÈx k i;dÞþx2 ðgbest k dÈx k i;dÞð11Þx kþ1i;d¼x ki;dÈv kþ1i;d i¼1;2...;n;d¼1;2;...;Dð12ÞwhereÈdenotes‘‘XOR”operator; denotes‘‘AND”operator;+de-notes‘‘OR”operator;x1and x2are two random binary integer numbers uniformly distributed in the range of[0,1].As it is clear from the Eqs.(11)and(12)in IBPSO method,the proposed binary PSO has all major characteristics of the real-val-ued PSO.Only the neighborhood in the IBPSO method contains all particles and inertia weight is zero.4.1.2.Structure of individuals for UCPBefore using the proposed binary PSO to solve UCP,the repre-sentation of a particle must be defined.A particle is also called an individual.Hence,we defined each unit on/off(or1/0)status as a gene,all available unit status at each hour make up a sub-chro-mosome,and there are T sub-chromosomes over the time horizon T comprising an individual.An individual would display the unit commitment schedule over the time horizon T.The on–off sche-dule of the units is stored as an integer-matrix U with dimension NÂT.A matrix representation of an individual in the population is shown as follows:U¼u11u21...u T1u12u22...u T2............u1Nu2N...u TN26666643777775where u tiis unit on/off status of unit i at time t(u ti¼1=0for on/off).4.1.3.Initialization individualsIn the initialization process,a set of individuals is created at random.For the complete M population,the candidate solution of each individual U j(j=1,2,...,M)is randomly initialized.The po-sition u tiof each particle U j is generated using a uniform distributed random function,which generates either0or1and they are equally likely.4.2.Priority list for unit-schedulingPriority list is created according to each unit parameters.Cost per produced unit,of a unit at its maximum output power usually is less than that at other output power levels.So,it is expected to run a unit at its maximum output power.In this paper,priority list is based on fuel cost obtained from the average fuel cost of each unit operating at its maximum output power.The average full-load cost a of a unit is defined as the cost per unit of power($/MW)when the unit is at its full capacity. When the fuel cost of unit is given by Eq.(2),a can be expressed asa i¼f iðP i maxÞi max¼a ii maxþb iþc iÁP i maxð13ÞThe units are ranked by their a in ascending order.Thus,the priority list of units will be formulated based on the order of a i,in which a unit with the lowest a i will have the highest priority to be dispatched.4.3.Spinning reserve constraints repairingThe obtained primary unit-scheduling using BPSO may not sat-isfy the spinning reserve constraints(5).Therefore,the spinning re-serve violations are repaired by heuristic search.The procedure for repairing the spinning reserve violations in primary unit-schedul-ing is as follows:X.Yuan et al./Expert Systems with Applications36(2009)8049–80558051Step1.Set t=1.Step2.For all uncommitted units at hour t,calculate the aver-age full-load cost a i using formula(13).Sort them inascending order of a i to obtain a list SS(a i).Step3.The amount of excessive spinning reserve at each hour is calculated byR t¼X Ni¼1u tiP i maxÀP tDÀP tRð14ÞStep4.If R t P0,go to step6;mit an uncommitted unit in SS(a i)with the lowesta i,one unit at a time until the spinning reserve con-straint is satisfied.Step6.If t<T,t=t+1and return to step2.Otherwise,stop. 4.4.Minimum up and down time constraints repairingSince the obtained unit schedule may not satisfy the minimum up and down time constraints,a heuristic search algorithm is re-quired to repair any violations of these constraints.To check for violations,on and off times of units are determined in advance (Dieu&Ongsakul,2006).The continuously on/off times of the unit i up to hour t are calculated as follows:T t i;on ¼T tÀ1i;onþ1if u ti¼10if u ti¼08><>:;Tti;off¼T tÀ1i;offþ1if u ti¼10if u ti¼08><>:ð15ÞThe procedure to repair violations of the minimum up and down times constraints is as follows:Step1:Calculate the duration on and off times of all units for the whole schedule time horizon using formula(15). Step2:Set t=1.Step3:Set i=1.Step4:If u ti ¼0and u tÀ1i¼1and T tÀ1i;on<T i;up,then set u ti¼1.Step5:If u ti ¼0and u tÀ1i¼1and tþT i;downÀ1T andT tþT i;downÀ1 i;off <T i;down,then set u ti¼1.Step6:If u ti ¼0and u tÀ1i¼1and tþT i;downÀ1>T andP Tj¼t u ji>0,then set u ti¼1.Step7:Update the duration on/off times for the unit i using for-mula(15).Step8:If i<N,i=i+1and return to step4.Step9:If t<T,t=t+1and return to step3.Otherwise,stop.An example of repairing the minimum up and down time is shown in Figs.1and2.4.5.Decommitment of excess unitsRepairing the minimum up and down time constraints can lead to excessive spinning reserves,which is not desirable due to the high operation cost.We use a heuristic search algorithm based on a priority list to decommit the redundant units due to the min-imum up and down time repairing,thereby reducing the operating cost.Starting from the committed units with the lowest priority list(the highest average operating cost),the algorithm determines units that can be decommitted without violating the minimum up and down time and spinning reserve constraints until no unit can be decommitted.So in this process,the spinning reserve and min-imum up and down time constraints must be checked before decommitting a unit.An example is shown in Fig.3.Procedure for decommitment of excessive units is as follows: Step1.Set t=1.Step2.Calculate the average full-load cost a i of each committed unit in hour t and sort the units in the descending orderof a i to obtain a list SS(a i).Let thefirst unit in SS(a i)beCU t.Step3.The amount of excessive spinning reserve at hour t is calculated byR t¼X Ni¼1u tiP i maxÀP tDÀP tRð16ÞStep4.If R t is less than the maximum generation power of CU t, go to step6.Step5.If decommitting CU t does not violate its minimum up/ down time constraint,decommit CU t and update on/offstatus for all units.Step6.Delete CU t from SS(a i).Step7.If SS(a i)is not empty,let CU t be thefirst unit in SS(a i)and return to step3.Step8.If t<T,t=t+1and return to step2.Otherwise,stop. mbda-iteration method for ELD problemWith the feasible UC schedule,classical equal lambda-iteration method(Wood&Wollenberg,1996)is used to solve the ELD prob-lem in this paper.The ELD procedure is stopped when thetoler-Fig.1.Repairing the minimum uptime.Fig.2.Repairing the minimum downtime.Fig.3.Decommitment of excessive units.8052X.Yuan et al./Expert Systems with Applications36(2009)8049–8055ance,which indicates that the sum of all online units output minus the load demand,is less than the value given beforehand.Once the optimal values of P tiare found,the total generation production cost is computed by adding the operating cost of all units over the time horizon T.The total start-up cost is calculated by adding the start-up costs of those units that change their states from0to1.4.7.Gray zone modification for start-up costThe gray zone for start-up cost indicates the change point where changes from the cold start-up cost to the hot start-up cost. As the cold start-up cost is higher than the hot start-up cost.Hence, it is desirable that the unit starts up with the hot start-up cost if possible.The gray zone modification algorithm only checks for the next hour ahead which does not violate unit’s minimum down/up time constraint to modify start-up cost.Meanwhile the algorithm considers the modification of start-up costs from cold to hot if the cost savings from the modification is higher than maintaining cost for the unit during the changed interval.So,the algorithm only checks one hour ahead because two or more hours ahead considered will not lead to cost savings from start-up and may violate minimum down time constraints.Fig.4shows an example for gray zone modification algorithm to reduce the cost. The method shown in Fig.4searches the gray zone for start-up cost and modifies schedule by turning the unit on just one hour ahead.4.8.Implementation of IBPSO for solving UCPThe procedures of the proposed IBPSO method for solving UCP are shown as follows:Step1:Initialization individuals in the swarm as in Section4.1. Step2:Calculate priority list of units according to each unit parameters as in Section4.2.Step3:Modify units’status of individuals in the swarm satisfy-ing spinning reserve constraints as in Section4.3.Step4:Repair each particle in the swarm for minimum up/ down time violations as in Section4.4.Step5:Decommit units of each particle in the swarm to reduce excessive spinning reserve due to minimum up/downtimes repairing as in Section4.5Step6:Solve ELD problem using equal lambda-iteration method as in Section4.6.Step7:Calculate the evaluation value of each particle using the objective function(1)and evaluate each particle in thepare each particle’s evaluation value withits own best position Pbest.The particle who owns thebest evaluation value among Pbest is set to be a globalbest particle position Gbest.Step8:Modify the velocity and position of each particle in the swarm using Eqs.(11)and(12).Step9:If the maximum iteration number is reached,then go to step10.Otherwise,increase iteration number and goback to step3.Step10:Modify gray zone for start-up cost of unit from cold to hot as in Section4.7.If there is any change in the unitschedule,solve ELD problem by equal lambda-iterationmethod.Step11:Stop and the optimal solution of UCP is obtained from the particle that generated the latest Gbest.5.Numerical examplesIn order to verify the feasibility and effectiveness of the pro-posed IBPSO method for solving UCP,the proposed IBPSO method is tested on different system sizes based on a basic system of 10units from the literature(Juste et al.,1999).The scheduling time horizon T is chosen as one day with24intervals of one hour each. The spinning reserve requirement is set to be10%of total load demand.For the systems of20,40,60,80and100units,the basic 10-unit system is duplicated and total load demands are adjusted proportionally to the system size.The proposed IBPSO method is coded in visual C++6.0and implement on a P-IV1.5GHz CPU with RAM128MB personal computer.The demand and generating unit data of the test system are given in the literature(Juste et al.,1999) in details.Parameters are chosen in this paper:population size M=20and maximum number of iteration Gmax=2000,respectively.Under the chosen parameters,we run the proposed IBPSO method to solve UCP for several test system with the number of units ranging from10to100.In the meantime,at each test system we also per-formed IBPSO10trials from different initial populations in succes-sion to examine the variation in their total production costs.Test results are shown in Table1.The best,worst,and average total pro-duction costsfindings of the proposed IBPSO are obtained together with their cost standard deviation.From Table1,the average pro-duction cost of10runs using the IBPSO method generated varia-tion in a small range as well as the standard deviation are small and tolerable.Simultaneously,average production costs are near to the middle position between their maximum and minimum val-ues.So,it is clear that solutions are not biased and they are equally distributed between the best and the worst solutions.It is demon-strated that the IBPSO method has better quality of solution and the robustness for the UCP.To validate the results obtained with the proposed IBPSO meth-od,we compare the performance of the IBPSO to those of other ap-proaches with respect to the best total production cost and CPU execution time.The results were reported in the literature when the same problem were solved using Lagrangian relaxation(LR) (Kazarlis&Bakirtzis,1996),genetic algorithm(GA)(Kazarlis& Bakirtzis,1996),evolutionary programming(EP)(Juste et al., 1999),memetic algorithm(MA)(Jorge&Smith,2002),greedy ran-dom adaptive search procedure(GRASP)(Viana et al.,2003)and particle swarm optimization combined with the Lagrangian relax-ation method(LRPSO)(Balci&Valenzuela,2004).Table2provides comparison of the best total production cost from the IBPSO meth-od to those of other methods.It is clearly shown that the total pro-duction costs by the IBPSO in all test cases are smaller than those of the above methods.The CPU execution times of the IBPSO and other methods in the literatures are shown in Table3.Although they may not be directly comparable due to different computers used,but the trend of com-putational time is shown that IBPSO is able tofind good optimal solutions in much smaller times than other methods.Moreover, Fig.4.Modification of the gray zone from cold to hot start-up.X.Yuan et al./Expert Systems with Applications36(2009)8049–80558053。