INVESTIGATIONS OF ANT COLONY MODELS FOR SOLVING UNIT COMMITMENT PROBLEM

Abstract

This dissertation presents the application of ant colony - based optimization models to unit commitment problem (UCP) ensuring efficient operation of practical power system utilities. Many conventional models have been developed to solve UCP but to obtain an optimal solution for large practical utilities with many generating units has still become a difficult task due to the curse of dimensionalities. Therefore, achieving a global optimum solution has become a challenge in research in a highly nonlinear and computationally difficult combinatorial power system optimization environment such as UCP. Systemic evaluation of a large number of possible decisions is performed in a multi-stage scheduling problem and thereby minimizing the overall cost. The exact solution of the UCP can be obtained by complete enumeration using conventional mathematical optimization techniques namely, dynamic programming (DP) or integer programming (IP) methods. However, the limitation ofthese methods is the enormous computational time, which increases exponentially with the number of units and the large memory requirements which soon reach a level that is practically impossible to compute. Even though several modifications of the basic DP, IP and other conventional techniques have been developed for reducing the computational time, these methods cause difficulties in terms of programming and often generate a suboptimal solution. Also, decisions made involving one or more stages or subsets will thereby exclude the non-optimum paths, which are considered to be infeasible. Sometimes, abandoning these sub-economic paths may cost more and may be disadvantageous when the overall cost minimization is considered. Moreover, when operating constraints are considered, a feasible solution becomes rather scarce. Therefore, it becomes necessary to try some kind of heuristic techniques, which do not violate the complete enumeration search of multi-stage DP approaches, but still provide a solution to near global optimum. Conventional mathematical optimization techniques a) may produce only one solution, b) must satisfy mathematical restrictions for problem formulation, c) require advanced computer algorithms and d) may suffer from numerical problems. However, in recent years, one of the most important and promising research field has been "Heuristics from Nature", an area utilizing analogies with natural or social systems. XVll Heuristics optimization methods a) may find a global optimum, b) can produce a number of alternative solutions, c) need no mathematical restriction on the problem formulation, d) are relatively easy to program and e) are numerically robust. Taking all these facts into account, an attempt has been made to explore ants' intelligence and ants' search, which is also heuristic in nature. Ants' search may be applied in a manner so as to search the complete enumeration space ofUCP and thereby, solve the limitations of multi-stage DP. Ant colony optimization (ACO), aheuristic technique takes inspiration from real ant colonies and is used to solve functions or combinatorial optimization problems. It was first introduced by Marco Dorigo in early nineties as an algorithm called ant system (AS), which was applied to hard combinatorial optimization problems like traveling salesman problem (TSP) and quadratic assignment problem. Ant algorithms simulate the natural behavior of ants' developing mechanisms of cooperation and learning, enabling the exploration ofthe positive feedback between agents as asearch mechanism. Hence, it has become one of the important branches in "Swarm Intelligence". An important and interesting behavior of ant colonies is their foraging behavior and in particular, how ants can find the shortest paths between food sources and their nest. While traveling from food sources to the nest and vice versa, ants deposit on the ground achemical substance called pheromone, thereby, forming apheromone trail. The pheromone trail allows the ants to find their way back to the food by their nest mates. Ants can smell pheromone and when choosing their path, they tend to choose, in probability, paths marked by strong pheromone concentrations. Pheromone mediated indirect communication called "stigmergy" acts as afeedback mechanism, present in these social agents. Models such as simulated annealing, tabu search, genetic algorithm, evolutionary programming etc., are quite successful in the history of solving UCP and have some general similarities with ACO. All these approaches, including ACO, use apopulation of individuals representing problem solutions. They have the knowledge about the problem collected by the population which is used to stochastically generate anew population of individuals. However, in ACO, amemory of past performance is maintained under the form of pheromone trails which is not in the case of other optimization models. xvni Even though evolutionary and hybrid computational models have been applied in solving combinatorial optimization problems, existing literatures prove ACO techniques are found to be competent. It is on this basis that ACO is suitable for UCP, which is also a hard combinatorial problem in nature. Until now, limited research work in the area ofUCP based on ACO has been attempted and the solutions obtained are found to be encouraging. However, they have not been thoroughly tested yet. In- Keun Yu, et al. and N. S. Sisworahardjo, et al. applied ant algorithms to UCP and indicated its applicability in terms of economy for smaller systems of few generating units without incorporating power flow constraints. Shyh-Jier Huang applied ant colony system techniques for the enhancement of hydroelectric generation scheduling in the search space ofthe hydro generation scheduling problem. In the work ofLibao Shi, et al, concept of random perturbation behavior with a magnifying factor and mutation rate is incorporated with the basic ant system model. In all the above approaches, ACO algorithms remain same and similar to the implementation ofwell established TSP using ACO. When solving TSP, during initialization phase, ants are positioned on different towns or cities. They are then allowed to search in the TSP solution space to legally satisfy the TSP constraints. Similarly for UCP, ants are positioned on different nodes or eligible states in the complete enumeration search space called ant search space (ASS). Ants are then allowed to search in ASS and legal generating schedule paths or solutions satisfying the UCP constraints are processed for capturing the optimum solutions. However, in this research work, a new ants' search procedure is adopted which is different from the previous approaches. UCP, a scheduling problem of generating units over a short-term horizon, is a complex, large-scale, mixed-integer non-linear optimization problem. The objective of UCP is to determine the optimum schedule of generating units (i.e. switching on and off of NG generating units over aperiod of time for the electricity load demand forecasted to be served) by minimizing the over all cost ofthe power generation while satisfying a set of system constraints. The scheduling of UCP for a time period of generally 24 hours or one day (i.e., Thourly stages) involves the determination of optimal on/off state of power generating units for each stage consisting of (2N° -1) combination of states. Therefore, the maximum number of possible combinations of schedule paths is (2N° -if. It thus becomes computationally difficult to solve UCP XIX when there is an increase in generating units. Hence, to find an optimal UCPsolution in a reasonable time is very critical since it could mean significant annual financial savings in power generating costs. Therefore, a parallel can be drawn between the ants' finding the shortest path from source (nest) to its destination (food) and in obtaining the minimum cost path for scheduling of thermal generating units between the initial and final hour. The proposed UCP formulation is subjected to power balance equality constraints and generating unit inequality constraints such as minimum up-time and down-time constraints with unit start-up and shut-down costs, unit status, maximum and minimum generation constraints, power flow equality and inequality constraints, spinning reserve constraints and ramping constraints. The UCP, which has been formulated including ramping constraints, is further extended by introducing ramping cost so that the generator may be allowed to generate slightly beyond its allowable ramping limits under competitive power supply markets and emergency conditions of power industry. Ramp rates of generators are generally specified within the elastic range of the strength of the shaft to safeguard the rotor from fatigue. From an economic point of view, studies have been conducted wherein these limits are exceeded irrespective of the risk of reducing the rotor life. The reduction in the life expectancy ofthe rotor can be compensated by incorporating ramping costs, which may provide cost-cutting measures in the longer run. In this dissertation, two novel basic ants' search schemes based on ants' movement in ASS, namely, serial and parallel styles have been modeled and presented for UCP. In serial style, each ant starts from the starting node only after its predecessor has reached the end stage. Whereas in parallel style, each ant starts from the starting node after its predecessor has chosen the next stage. The introduction of the AS model to TSP has evolved many other versions and improved ACO models such as ant quantity, ant density, ant cycle, ant colony system, max-min ant system etc., and in total, fourteen ant colony models based on serial and parallel ants' search scheme are modeled and investigated for UCP. The heuristic function involving pseudo-random probabilistic transition rule of the ACO based TSP approach is modified to suit the UCP during the transition of ants from one eligible state of a particular stage to the eligible state of the next stage. Again the transition rule is modified to suit the serial/parallel implementation scheme ofants' search. Elistic ants XX have been used to enhance the ants' search performance. Here, enhanced transition rules and pheromone updating of few of the successful ACO models is incorporated and applied to UCP. In concise, the entire dissertation work of solving UCP using ant colony models is divided into three parts, viz, a) Construction of ant search space b) Implementation ofant colony optimization models for UCP c) Validation and verification of the proposed antcolony models for UCP against other conventional and intelligent models. The proposed ant colony models for UCP are solved mainly in two stages. The first stage which is termed as ASS or matrix space is totally designed for the ants to explore on a platform. The ASS involves sub-components such as economic dispatch using Lagrange multiplier method, power flow performed using Newton Raphson method and Gaussian load distribution to generate twenty four hours' ahead load demand patterns for test case systems. The sub-components are interlinked to yield an optimal generation dispatch and, hence, ASS or matrix space. The second stage involves ants' search on this platform performing multi-stage intelligent decisions. Tuning of parameter for ant variables is very important for good convergence behavior to obtain an optimal solution. Here, the ant parameters are set according to the total number of non-zero elemental states (nzes) present in the matrix space, which is obtained, in the first stage. Asystematic approach on fixing ant parameters has been analyzed and suggested. The performance and analysis of the proposed ant colony models are validated using a practical ten unit generating system, IEEE 6, 14, 30, 57 and 118 bus systems and have been used in different stages of the work. Later the algorithms have also been applied to a practical Indian utility 75 bus system. The performance evaluation for all these test systems iscarried out for the UCP which iscategorized into four case studies, namely, a) unit commitment problem without power flow constraints, b) unit commitment problem with power flow constraints, c) unit commitment problem with power flow constraints and ramping cost, and d) unit commitment problem with power flow constraints, ramping cost and dynamic loads. A positive and negative white Gaussian noise has been added to each and every bus' steady state loads to obtain approximate relative dynamic load patterns. Since ant algorithms are highly stochastic in nature, Monte Carlo simulation plots XXI are used to compare the performance of the proposed ant colony models. On observing several trial runs for eachof the test systems based on the convergence rate and average total generation cost, two effective models namely, serial ant colony system with elistic ants (SACSEA) and parallel ant colony system with elistic ants (PACSEA) are chosen. Although, the performances of both SACSEA and PACSEA models are found to be efficient, different conclusions are derived based on size and feasibility states ofthe system. The two effective models are compared with well-established approaches such as DP, branch and bound method and other intelligent approaches such as genetic algorithm, fuzzy systems, expert systems and hybrid intelligent models. The effects of all the four case studies onall the test systems are discussed. It hasbeen observed that at least 10% of (2Na -1) NZES are required to be present in each and every column ofthe matrix space to facilitate the ants' movement successfully in finding an optimal solution. In conclusion, SACSEA model is best suited for small and medium test systems (IEEE 6, 14, 30 and 57 bus systems) with higher percentage of NZES present in the total available UCP solution space. PACSEA model is best suited for large test systems (IEEE 118 and Indian utility 75 bus systems) with lower percentage of NZES . However, the only drawback associated with PACSEA model is its solution time, which is slightly higherthan SACSEA. In summary, the present work contributes improved models in the area ofUCP and ACO techniques. The newly developed ant colony models will be ofa great help to the present power industry. Presently in this dissertation, the ant colony models are developed for solving UCP under regulated environment but the models can be extended also to UCP under deregulated environment ofpractical power utilities.