IEEE PES Tutorial on
Modern Heuristic Optimization Techniques with Application to Power Systems
Several heuristic tools have evolved in the last decade that facilitate solving optimization problems that were previously difficult or impossible to solve. These tools include evolutionary computation, simulated annealing, tabu search, particle swarm, etc. Reports of applications of each of these tools have been widely published. Recently, these new heuristic tools have been combined among themselves and with knowledge elements, as well as with more traditional approaches such as statistical analysis, to solve extremely challenging problems. Developing solutions with these tools offers two major advantages: 1) development time is much shorter than when using more traditional approaches, and, 2) the systems are very robust, being relatively insensitive to noisy and/or missing data
Course Objective:
The objective of this tutorial is to provide participants with basic knowledge of evolutionary computation, and other heuristic optimization techniques, and how they are combined with knowledge elements in computational intelligence systems. Applications to power problems are stressed, and example applications are presented.
Evolutionary Computation:
Natural evolution is a hypothetical population-based optimization process. Simulating this process on a computer results in stochastic optimization techniques that can often out-perform classical methods of optimization when applied to difficult real-world problems. This tutorial will provide a background in the inspiration, history, and application of evolutionary computation and other heuristic optimization methods to system identification, automatic control, gaming, and other combinatorial problems.
The objectives are to provide an overview of how evolutionary computation and other heuristic optimization techniques may be applied to problems within your domain of expertise, to provide a good understanding of the design issues involved in tailoring heuristic algorithms to real-world problems, to compare and judge the efficacy of modern heuristic optimization techniques with other more classic methods of optimization, and to program fundamental evolutionary algorithms and other heuristic optimization routines.
Genetic Algorithms
Genetic Algorithm (GA) is a search algorithm based on the conjecture of natural selection and genetics. The features of genetic algorithm are different from other search techniques in several aspects. First, the algorithm is a multi-path that searches many peaks in parallel, and hence reducing the possibility of local minimum trapping. Secondly, GA works with a coding of parameters instead of the parameters themselves. The coding of parameter will help the genetic operator to evolve the current state into the next state with minimum computations. Thirdly, GA evaluates the fitness of each string to guide its search instead of the optimization function. The genetic algorithm only needs to evaluate objective function (fitness) to guide its search. There is no requirement for derivatives or other auxiliary knowledge. Hence, there is no need for computation of derivatives or other auxiliary functions. Finally, GA explores the search space where the probability of finding improved performance is high.
Evolutionary Strategies (ES) employ real-coded variables and, in its original form, it relied on Mutation as the search operator, and a Population size of one. Since then it has evolved to share many features with GA. The major similarity between these two types of algorithms is that they both maintain populations of potential solutions and use a selection mechanism for choosing the best individuals from the population. The main differences are: ES operate directly on floating point vectors while classical GAs operate on binary strings; GAs rely mainly on recombination to explore the search space, while ES uses mutation as the dominant operator; and ES is an abstraction of evolution at individual behavior level, stressing the behavioral link between an individual and its offspring, while GAs maintain the genetic link.
Evolutionary Programming (EP) is a stochastic
optimization strategy similar to GA, which
places emphasis on the behavioral linkage
between parents and their offspring, rather
than seeking to emulate specific genetic
operators as observed in nature. EP is similar to Evolutionary Strategies,
although the tow approaches developed independently. Like both ES and GAs, EP is a useful method
of optimization when other techniques such
as gradient descent or direct analytical
discovery are not possible. Combinatorial and real-valued function optimization
in which the optimization surface or fitness
landscape is “rugged”, possessing many
locally optimal solutions, are well suited
for Evolutionary Programming.
Particle swarm optimization (PSO) is an exciting new methodology in evolutionary computation that is somewhat similar to a genetic algorithm in that the system is initialized with a population of random solutions. Unlike other algorithms, however, each potential solution (called a particle) is also assigned a randomized velocity and then flown through the problem hyperspace. Particle swarm optimization has been found to be extremely effective in solving a wide range of engineering problems. It is very simple to implement (the algorithm comprises two lines of computer code) and solves problems very quickly!
Tabu Search (TS) is basically a gradient-descent search with memory. The memory preserves a number of previously
visited states along with a number of states
that might be considered unwanted. This information is stored in a Tabu List. The definition of a state, the area around
it and the length of the Tabu list are critical
design parameters. In addition to these Tabu parameters, two
extra parameters are often used: Aspiration
and Diversification. Aspiration is used when all the neighboring
states of the current state are also included
in the Tabu list. In that case, the Tabu obstacle is overridden
by selecting a new state. Diversification adds randomness to this otherwise
deterministic search. If the Tabu search is not converging, the
search is reset randomly.
In statistical mechanics, a physical process called annealing is often performed in order to relax the system to a state with minimum free energy. In the annealing process, a solid in a heat bath is heated up by increasing the temperature of the bath until the solid is melted into liquid, then the temperature is lowered slowly. In the liquid phase all particles of the solid arrange themselves randomly. In the ground state the particles are arranged in a highly structured lattice and the energy of the system is minimum. The ground state of the solid is obtained only if the maximum temperature is sufficiently high and the cooling is done sufficiently slowly. Based on the annealing process in the statistical mechanics, the Simulated Annealing (SA) was introduced for solving complicated combinatorial optimization.
The name ‘simulated annealing’ originates from the analogy with the physical process of solids, and the analogy between physical system and simulated annealing is that the cost function and the solution (configuration) in the optimization process correspond to the energy function and the state of statistical physics, respectively. In a large combinatorial optimization problem, an appropriate perturbation mechanism, cost function, solution space, and cooling schedule are required in order to find an optimal solution with simulated annealing. SA is effective in network reconfiguration problems for large-scale distribution systems, and its search capability becomes more significant as the system size increases. Moreover, the cost function with a smoothing strategy enables the simulated annealing to escape more easily from local minima and to reach rapidly to the vicinity of an optimal solution.
INTENDED AUDIENCE: Engineers, scientists, and managers who need to solve difficult large-scale problems. Some background in computer programming is very useful. Background in stochastic processes and optimization theory is helpful, but not required.
Course Outline
Part 1: Theory of Evolutionary Computation (4 hr lecture)
Chapter 1. Fundamentals of Evolutionary Computation (El-Sharkawi)
1. Review of evolutionary computation theory and concepts
2. Comparison of the efficacy of evolutionary computation with other more classic methods of optimization
Chapter 2. Overview of Applications in Power Systems (Alves da Silva)
1. Overview on applicability of evolutionary computation
2. Design issues involved in tailoring evolutionary algorithms to power system problems
Chapter 3. Fundamentals of Genetic Algorithm (Alves da Silva)
1. Basic computational blocks: evaluation, selection, crossover, mutation
2. Design issues in GA: initial population pool, conversion from phenotype and genotype, conversion of error to fitness, parent selection
Chapter 4. Fundamentals of Evolutionary Programming and Evolutionary Strategy (Miranda & Lee)
1. Basic computational blocks for Evolutionary Strategies
2. Basic computational blocks for Evolutionary Programming
Chapter 5. Fundamentals of Particle Swarm Techniques (Fukuyama)
1. Introduction, background and history of particle swarm optimization
2. Particle swarm implementations
Chapter 6. Fundamentals of Simulated Annealing (Monticelli)
1. Theoretical background
2. Simulated annealing implementations
Chapter 7. Fundamentals of Tabu Search (Monticelli)
1. Theoretical background
2. Tabu search implementations
Chapter 8. Hybrid Systems of Evolutionary Computation (Lambert-Torres)
1. Hybrid of evolutionary computation with neural networks
2. Hybrid of evolutionary computation with fuzzy logic systems
Part 2: Selected Applications of Evolutionary Computation (4 hr lecture)
Chapter 9. Dynamic Security Assessment (El-Sharkawi)
1. Vulnerability/security margin
2. Boundary tracking
3. Visualization
Chapter 10. Generation Planning (Miranda & Lee)
1. Generation expansion planning
2. Reactive power planning
Chapter 11. Network Planning (Monticelli)
1. Transmission planning
2. Distribution planning
Chapter 12. Operational Planning (Alves da Silva)
1. Economic dispatch
2. Unit commitment
Chapter 13. Power System Controls (Fukuyama)
1. Voltage and reactive power control ? Particle swarm technique
2. Distribution system optimization ? Hybrid particle swarm technique
Chapter 14. Power Plant Controls (Lee)
1. Fossil-Fuel units
2. Nuclear Plants
Chapter 15. State Estimation (Monticelli)
1. Tabu search in bad data processing
2. Comparison with Branch-and-Bound method
Chapter 16. Bibliographies (Lee)
Instructors:
Mohamed A. El-Sharkawi (committed)
Dr. El-Sharkawi is a Fellow of IEEE. He is a professor of Electrical Engineering at the University of Washington. He is the Founder of the international conference on the Application of Neural Networks to Power Systems (ANNPS) and the Co-founder of the international conference on Intelligent Systems Applications to Power (ISAP). He is a member of the administrative committee of the IEEE Neural Networks Council representing the Power Engineering Society; Video Tutorial Chair of the IEEE Continuing Education Committee and the neural network council. He is the Founding Chairman of several IEEE task forces and working groups and subcommittees. He is a member of the editorial board and associate editor of several journals. He co-edited an IEEE tutorial book on the applications of neural network to power systems. He organized and taught several international tutorials on intelligent systems applications, power quality and power systems; and organized and chaired numerous panel and special sessions in IEEE and other international conferences. He published over 130 papers and book chapters in these areas, and holds 7 licensed patents. He published recently a textbook entitled “Fundamentals of Electric Drives,” Brooks/Cole Publishing, 2000.
Kwang Y. Lee (committed)
Dr. Lee is a Fellow of IEEE. He is a professor of Electrical Engineering at the Pennsylvania State University. He is Associate Editor of the IEEE Transactions on Neural Networks since 1996, Technical Program Chairman for the 1997 International Conference on Intelligent Systems Applications to Power Systems (ISAP ’97), and Program Co-Chairman of the 1989 U.S.-Korea Joint Seminar on Expert Systems for Power Systems. He is active in the Intelligent Systems Subcommittee and Station Operation, Design and Control Subcommittee of the IEEE Power Engineering Society. He organized and participated several panels and special sessions in IEEE and other international conferences on intelligent control, distributed simulation, combined research and curriculum development, and undergraduate research. He was a tutorial speaker on “IEEE Tutorial on The Applications of Neural Network to Power Systems Artificial Neural Networks”, and edited an “ISAP Tutorial Book on Current Trend and the State of the Art in Intelligent System Applications to Power Systems”. He is the author of over 300 technical publications and proceedings and 14 book chapters.
Alcir J. Monticelli (committed)
Dr. Monticelli is a Fellow of the IEEE and a member of the Brazilian Academy of Sciences. He received his B.S. degree in electronic engineering from the Insituto Tecnologico de Aeronautica (ITA) in 1970, the M.S. degree from Universidade Federal da Paraiba (UFPB) in 1972, and the Ph.D. degree from Universidade Estaduial de Campinas (Unicamp) in 1975, all in Brazil. From 1982 to 1985, he was a visiting professor at the University of California Berkeley, and from 1991 to 1992 he was with Mitsubishi Electric Corporation, Japan. Currently he is a professor of electrical engineering at Unicamp.
Dr. Lambert-Torres is a professor of Electrical Engineering and Dean of Research and Graduate Studies at the Federal Engineering School at Itajuba, Brazil. He is the General Editor of Research Technologic Development Magazine, General Chairman for the first Brazilian Conference on Neural Networks (CBRN’97), General Chairman for the 1999 International Conference on Intelligent Systems Applications to Power Systems (ISAP ’99), Program Co-Chairman of the International Congress of Logic Applied to Technology (LAPTEC’00), and Vice-General Chairman for the 2001 International Conference on Intelligent Systems Applications to Power Systems (ISAP ’01). He is also a Member of the Internal Program Committee for IASTED International Conference on Power and Energy Systems, International Conference in Evolutionary Computing in Computer, Communication, Control and Power, and WSES International Conference on Simulation. He serves on a number of committees related to intelligent systems in IEEE and CIGRE. He also serves as consultant for many Brazilian and South America Power Industries, such as Itaipu Power Plant. He has more than 300 technical papers published in transactions, proceedings, and book chapters.
Alexandre P. Alves da Silva (committed)
Dr. Alves da Silva was born in Rio de Janeiro, Brazil, in 1962. He received the B.Sc., M.Sc. and Ph.D. degrees in Electrical Engineering from the Catholic University of Rio de Janeiro, in 1984 and 1987, and the University of Waterloo, Canada, in 1992, respectively. He worked with the Electric Energy Research Center (CEPEL) from 1987 to 1988. During 1999, he was a Visiting Professor in the Department of Electrical Engineering, University of Washington, USA. Since 1993, he has been with the Federal Engineering School at Itajuba, where he is a Professor in Electrical Engineering. He and his group have developed intelligent forecasting and security assessment systems that are in operation at control centers of Brazilian electric utilities. Professor Alves da Silva was the Technical Program Committee Chairman of the First Brazilian Conference on Neural Networks in 1994, and of the International Conference on Intelligent System Application to Power Systems in 1999. He is the Chairman of the IEEE Neural Network Council Brazilian Regional Interest Group. He has authored and coauthored about 150 papers on intelligent systems application to power systems.
Yoshikazu Fukuyama (committed)
Dr. Fukuyama received the B.S., M.S., and Ph.D. degrees in electrical engineering
in 1985, 1987, and 1997, respectively, from Waseda University, Tokyo, Japan. He has been working at Fuji Electric Co.
R&D, Japan from 1987. He was a visiting scientist at Cornell University
from 1993 to 1994. His research interests include application
of intelligent systems to power systems and
power system analysis. He is also interested in general optimization
problems. He is a member of IEEE and IEE of Japan.
Russell C. Eberhart (committed as an alternate)
Dr. Eberhart is a Fellow of the IEEE. He is the Associate Dean for Research of the Purdue School of Engineering and Technology, Indiana University Purdue University Indianapolis (IUPUI). He is also Acting Chair of the Electrical and Computer Engineering Department, and Professor of Electrical and Computer Engineering. He received his Ph.D. from Kansas State University in electrical engineering. He is co-editor of a book on neural networks, now in its fifth printing, and co-author of Computational Intelligence PC Tools, published in 1996 by Academic Press. He is currently finishing revisions to a book with Jim Kennedy and Yuhui Shi entitled Swarm Intelligence: Collective Adaptation, to be published by Morgan Kaufmann/Academic Press, in April 2001. He is Associate Editor of the IEEE Transactions on Evolutionary Computation. He was recently awarded the IEEE Millenium Medal.
Vladimiro Miranda (committed)
Dr. Miranda is presently a Professor at the University of Porto, Portugal, and he is also a Director of INESC Porto, a private non-for-profit research organization, where for many years he hold the position of Coordinator of the Power Systems area. In 1996 and 1997 he was the Chairman of the Executive Board of INESC Macau (China). He has been responsible for the participation of INESC Porto in a number of projects within the European Union research programs, namely ESPRIT, JOULE, TEMPUS and SYNERGY. He is also the Chairman of ELAB, the Conference in Power Systems for all Portuguese speaking countries. His main interests are related with system planning and operation planning, and in the areas of computational intelligence, with an emphasis to fuzzy set theory, evolutionary programming and neural networks. He also has solid experience in the problems of distributed generation and its integration and in planning and forecasting with GIS (Geographic Information Systems) tools. He has authored or co-authored about 150 publications, among which some that gave him particular pleasure such as in fuzzy modeling of power systems, genetic algorithm applications to expansion planning and fuzzy inference systems applied over GIS environments.