Preface xxi
Contributors xxvii
Part 1 Theory of Modern Heuristic Optimization 1
1 Introduction to Evolutionary Computation 3
David B. Fogel
1.1 Introduction 3
1.2 Advantages of Evolutionary Computation 4
1.2.1 Conceptual Simplicity 4
1.2.2 Broad Applicability 6
1.2.3 Outperform Classic Methods on Real Problems 7
1.2.4 Potential to Use Knowledge and Hybridize with Other Methods 8
1.2.5 Parallelism 8
1.2.6 Robust to Dynamic Changes 9
1.2.7 Capability for Self-Optimization 10
1.2.8 Able to Solve Problems That Have No Known Solutions 11
1.3 Current Developments 12
1.3.1 Review of Some Historical Theory in Evolutionary Computation 12
1.3.2 No Free Lunch Theorem 12
1.3.3 Computational Equivalence of Representations 14
1.3.4 Schema Theorem in the Presence of Random Variation 16
1.3.5 Two-Armed Bandits and the Optimal Allocation of Trials 17
1.4 Conclusions 19
Acknowledgments 20
References 20
2 Fundamentals of Genetic Algorithms 25
Alexandre P. Alves da Silva and Djalma M. Falcao
2.1 Introduction 25
2.2 Modern Heuristic Search Techniques 25
2.3 Introduction to GAs 27
2.4 Encoding 28
2.5 Fitness Function 30
2.5.1 Premature Convergence 32
2.5.2 Slow Finishing 32
2.6 Basic Operators 33
2.6.1 Selection 33
2.6.2 Crossover 36
2.6.3 Mutation 38
2.6.4 Control Parameters Estimation 38
2.7 Niching Methods 38
2.8 Parallel Genetic Algorithms 39
2.9 Final Comments 40
Acknowledgments 41
References 41
3 Fundamentals of Evolution Strategies and Evolutionary Programming 43
Vladimiro Miranda
3.1 Introduction 43
3.2 Evolution Strategies 46
3.2.1 The General (µ, º, », �) Evolution Strategies Scheme 47
3.2.2 Some More Basic Concepts 50
3.2.3 The Early (1 + 1)ES and the 1/5 Rule 51
3.2.4 Focusing on the Optimum 53
3.2.5 The (1, »)ES and �SA Self-Adaptation 54
3.2.6 How to Choose a Value for the Learning Parameter? 56
3.2.7 The (µ, l)ES as an Extension of (1, »)ES 57
3.2.8 Self-Adaptation in (µ, »)ES 58
3.3 Evolutionary Programming 60
3.3.1 The (µ + ») Bridge to ES 60
3.3.2 A Scheme for Evolutionary Programming 61
3.3.3 Other Evolutionary Programming Variants 63
3.4 Common Features 63
3.4.1 Enhancing the Mutation Process 63
3.4.2 Recombination as a Major Factor 65
3.4.3 Handling Constraints 67
3.4.4 Starting Point 67
3.4.5 Fitness Function 67
3.4.6 Computing 68
3.5 Conclusions 68
References 69
4 Fundamentals of Particle Swarm Optimization Techniques 71
Yoshikazu Fukuyama
4.1 Introduction 71
4.2 Basic Particle Swarm Optimization 72
4.2.1 Background of Particle Swarm Optimization 72
4.2.2 Original PSO 72
4.3 Variations of Particle Swarm Optimization 76
4.3.1 Discrete PSO 76
4.3.2 PSO for MINLPs 77
4.3.3 Constriction Factor Approach (CFA) 77
4.3.4 Hybrid PSO (HPSO) 78
4.3.5 Lbest Model 79
4.3.6 Adaptive PSO (APSO) 79
4.3.7 Evolutionary PSO (EPSO) 81
4.4 Research Areas and Applications 82
4.5 Conclusions 83
References 83
5 Fundamentals of Ant Colony Search Algorithms 89
Yong-Hua Song, Haiyan Lu, Kwang Y. Lee, and I. K. Yu
5.1 Introduction 89
5.2 Ant Colony Search Algorithm 90
5.2.1 Behavior of Real Ants 90
5.2.2 Ant Colony Algorithms 91
5.2.3 Major Characteristics of Ant Colony Search Algorithms 98
5.3 Conclusions 99
References 99
6 Fundamentals of Tabu Search 101
Alcir J. Monticelli, Rub©n Romero, and Eduardo Nobuhiro Asada
6.1 Introduction 101
6.1.1 Overview of the Tabu Search Approach 101
6.1.2 Problem Formulation 103
6.1.3 Coding and Representation 104
6.1.4 Neighborhood Structure 105
6.1.5 Characterization of the Neighborhood 108
6.2 Functions and Strategies in Tabu Search 110
6.2.1 Recency-Based Tabu Search 110
6.2.2 Basic Tabu Search Algorithm 112
6.2.3 The Use of Long-Term Memory in Tabu Search 115
6.3 Applications of Tabu Search 119
6.4 Conclusions 120
References 120
7 Fundamentals of Simulated Annealing 123
Alcir J. Monticelli, Rub©n Romero, and Eduardo Nobuhiro Asada
7.1 Introduction 123
7.2 Basic Principles 125
7.2.1 Metropolis Algorithm 125
7.2.2 Simulated Annealing Algorithm 126
7.3 Cooling Schedule 127
7.3.1 Determination of the Initial Temperature T0 128
7.3.2 Determination of Nk 129
7.3.3 Determination of Cooling Rate 130
7.3.4 Stopping Criterion 130
7.4 SA Algorithm for the Traveling Salesman Problem 131
7.4.1 Problem Coding 131
7.4.2 Evaluation of the Cost Function 132
7.4.3 Cooling Schedule 133
7.4.4 Comments on the Results for the TSP 134
7.5 SA for Transmission Network Expansion Problem 134
7.5.1 Problem Coding 136
7.5.2 Determination of the Initial Solution 136
7.5.3 Neighborhood Structure 138
7.5.4 Variation of the Objective Function 139
7.5.5 Cooling Schedule 140
7.6 Parallel Simulated Annealing 140
7.6.1 Division Algorithm 141
7.6.2 Clustering Algorithm 142
7.7 Applications of Simulated Annealing 143
7.8 Conclusions 144
References 144
8 Fuzzy Systems 147
Germano Lambert-Torres
8.1 Motivation and Definitions 147
8.1.1 Introduction 147
8.1.2 Typical Actions in Fuzzy Systems 148
8.2 Integration of Fuzzy Systems with Evolutionary Techniques 150
8.2.1 Integration Types of Hybrid Systems 150
8.2.2 Hybrid Systems in Evolutionary Techniques 151
8.2.3 Evolutionary Algorithms and Fuzzy Logic 152
8.3 An Illustrative Example of a Hybrid System 152
8.3.1 Parking Conditions 153
8.3.2 Creation of the Fuzzy Control 154
8.3.3 First Simulations 156
8.3.4 Problem Presentation 156
8.3.5 Genetic Training Modulus Description 158
8.3.6 The Option to Define the Starting Positions 158
8.3.7 The Option Genetic Training 158
8.3.8 Tests 163
8.4 Conclusions 167
References 168
9 Differential Evolution, an Alternative Approach to Evolutionary Algorithm 171
Kit Po Wong and ZhaoYang Dong
9.1 Introduction 171
9.2 Evolutionary Algorithms 172
9.2.1 Basic EAs 172
9.2.2 Virtual Population-Based Acceleration Techniques 174
9.3 Differential Evolution 176
9.3.1 Function Optimization Formulation 176
9.3.2 DE Fundamentals 177
9.4 Key Operators for Differential Evolution 181
9.4.1 Encoding 181
9.4.2 Mutation 181
9.4.3 Crossover 183
9.4.4 Other Operators 183
9.5 An Optimization Example 184
9.6 Conclusions 186
Acknowledgments 186
References 186
10 Pareto Multiobjective Optimization 189
Patrick N. Ngatchou, Anahita Zarei, Warren L. J. Fox, and Mohamed A. El-Sharkawi
10.1 Introduction 189
10.2 Basic Principles 190
10.2.1 Generic Formulation of MO Problems 191
10.2.2 Pareto Optimality Concepts 191
10.2.3 Objectives of Multiobjective Optimization 193
10.3 Solution Approaches 194
10.3.1 Classic Methods 194
10.3.2 Intelligent Methods 196
10.4 Performance Analysis 202
10.4.1 Objective of Performance Assessment 202
10.4.2 Comparison Methodologies 203
10.5 Conclusions 205
Acknowledgments 205
References 205
11 Trust-Tech Paradigm for Computing High-Quality Optimal Solutions: Method and Theory 209
Hsiao-Dong Chiang and Jaewook Lee
11.1 Introduction 209
11.2 Problem Preliminaries 210
11.3 A Trust-Tech Paradigm 213
11.3.1 Phase I 213
11.3.2 Phase II 214
11.4 Theoretical Analysis of Trust-Tech Method 218
11.5 A Numerical Trust-Tech Method 221
11.5.1 Computing Another Local Optimal Solution 222
11.5.2 Computing Tier-One Local Optimal Solutions 223
11.5.3 Computing Tier-N Solutions 224
11.6 Hybrid Trust-Tech Methods 225
11.7 Numerical Schemes 227
11.8 Numerical Studies 228
11.9 Conclusions Remarks 231
References 232
Part 2 Selected Applications of Modern Heuristic Optimization In Power Systems 235
12 Overview of Applications in Power Systems 237
Alexandre P. Alves da Silva, Djalma M. Falc£o, and Kwang Y. Lee
12.1 Introduction 237
12.2 Optimization 237
12.3 Power System Applications 238
12.4 Model Identification 239
12.4.1 Dynamic Load Modeling 239
12.4.2 Short-Term Load Forecasting 240
12.4.3 Neural Network Training 241
12.5 Control 242
12.5.1 Examples 243
12.6 Distribution System Applications 244
12.6.1 Network Reconfiguration for Loss Reduction 245
12.6.2 Optimal Protection and Switching Devices Placement 246
12.6.3 Prioritizing Investments in Distribution Networks 247
12.7 Conclusions 249
References 250
13 Application of Evolutionary Technique to Power System Vulnerability Assessment 261
Mingoo Kim, Mohamed A. El-Sharkawi, Robert J. Marks, and Ioannis N. Kassabalidis
13.1 Introduction 261
13.2 Vulnerability Assessment and Control 263
13.3 Vulnerability Assessment Challenges 264
13.3.1 Complexity of Power System 264
13.3.2 VA On-line Speed 265
13.3.3 Feature Selection 265
13.3.4 Vulnerability Border 270
13.3.5 Selection of Vulnerability Index 276
13.4 Conclusions 281
References 281
14 Applications to System Planning 285
Eduardo Nobuhiro Asada, Youngjae Jeon, Kwang Y. Lee, Vladimiro Miranda, Alcir J. Monticelli, Koichi Nara, Jong-Bae Park, Rub©n Romero, and Yong-Hua Song
14.1 Introduction 285
14.2 Generation Expansion 286
14.2.1 A Coding Strategy for an Improved GA for the Least-Cost GEP 288
14.2.2 Fitness Function 288
14.2.3 Creation of an Artificial Initial Population 289
14.2.4 Stochastic Crossover Elitism and Mutation 291
14.2.5 Numerical Examples 292
14.2.6 Parameters for GEP and IGA 293
14.2.7 Numerical Results 295
14.3 Transmission Network Expansion 297
14.3.1 Overview of Static Transmission Network Planning 297
14.3.2 Solution Techniques for the Transmission Expansion Planning Problem 300
14.3.3 Coding, Problem Representation, and Test Systems 302
14.3.4 Complexity of the Test Systems 304
14.3.5 Simulated Annealing 306
14.3.6 Genetic Algorithms in Transmission Network Expansion Planning 307
14.3.7 Tabu Search in Transmission Network Expansion Planning 309
14.3.8 Hybrid TS/GA/SA Algorithm in Transmission Network Expansion Planning 310
14.3.9 Comments on the Performance of Meta-heuristic Methods in Transmission Network Expansion Planning 311
14.4 Distribution Network Expansion 311
14.4.1 Dynamic Planning of Distribution System Expansion: A Complete GA Model 312
14.4.2 Dynamic Planning of Distribution System Expansion: An Efficient GA Application 316
14.4.3 Application of TS to the Design of Distribution Networks in FRIENDS 317
14.5 Reactive Power Planning at Generation¢"Transmission Level 320
14.5.1 Benders Decomposition of the Reactive Power Planning Problem 321
14.5.2 Solution Algorithm 323
14.5.3 Results for the IEEE 30-Bus System 324
14.6 Reactive Power Planning at Distribution Level 326
14.6.1 Modeling Chromosome Repair Using an Analytical Model 326
14.6.2 Evolutionary Programming/Evolution Strategies Under Test 327
14.7 Conclusions 330
References 330
15 Applications to Power System Scheduling 337
Koay Chin Aik, Loi Lei Lai, Kwang Y. Lee, Haiyan Lu, Jong-Bae Park, Yong-Hua Song, Dipti Srinivasan, John G. Vlachogiannis, and I. K. Yu
15.1 Introduction 337
15.2 Economic Dispatch 337
15.2.1 Economic Dispatch Problem 337
15.2.2 GA Implementation to ED 339
15.2.3 PSO Implementation to ED 346
15.2.4 Numerical Example 348
15.2.5 Summary 354
15.3 Maintenance Scheduling 354
15.3.1 Maintenance Scheduling Problem 354
15.3.2 GA, PSO, and ES Implementation 355
15.3.3 Simulation Results 365
15.3.4 Summary 366
15.4 Cogeneration Scheduling 366
15.4.1 Cogeneration Scheduling Problem 367
15.4.2 IGA Implementation 370
15.4.3 Case Study 373
15.4.4 Summary 374
15.4.5 Nomenclature 379
15.5 Short-Term Generation Scheduling of Thermal Units 380
15.5.1 Short-Term Generation Scheduling Problem 380
15.5.2 ACSA Implementation 382
15.5.3 Experimental results 385
15.6 Constrained Load Flow Problem 385
15.6.1 Constrained Load Flow Problem 385
15.6.2 Heuristic Ant Colony Search Algorithm Implementation 386
15.6.3 Test Examples 390
15.6.4 Summary 399
References 399
16 Power System Controls 403
Yoshikazu Fukuyama, Hamid Ghezelayagh, Kwang Y. Lee, Chen-Ching Liu, Yong-Hua Song, and Ying Xiao
16.1 Introduction 403
16.2 Power System Controls: Particle Swarm Technique 404
16.2.1 Problem Formulation of VVC 405
16.2.2 Expansion of PSO for MINLP 406
16.2.3 Voltage Security Assessment 407
16.2.4 VVC Using PSO 408
16.2.5 Numerical Examples 409
16.2.6 Summary 416
16.3 Power Plant Controller Design with GA 417
16.3.1 Overview of the GA 417
16.3.2 The Boiler-Turbine Model 419
16.3.3 The GA Control System Design 420
16.3.4 GA Design Results 423
16.4 Evolutionary Programming Optimizer and Application in Intelligent Predictive Control 427
16.4.1 Structure of the Intelligent Predictive Controller 428
16.4.2 Power Plant Model 430
16.4.3 Control Input Optimization 431
16.4.4 Self-Organized Neuro-Fuzzy Identifier 435
16.4.5 Rule Generation and Tuning 438
16.4.6 Controller Implementation 442
16.4.7 Summary 444
16.5 An Interactive Compromise Programming-Based MO Approach to FACTS Control 444
16.5.1 Review of MO Optimization Techniques 446
16.5.2 Formulated MO Optimization Model 449
16.5.3 Power Flow Control Model of FACTS Devices 450
16.5.4 Proposed Interactive DWCP Method 453
16.5.5 Proposed Interactive Procedure with Worst Compromise Displacement 455
16.5.6 Implementation 457
16.5.7 Numerical Results 457
16.5.8 Summary 462
References 464
17 Genetic Algorithms for Solving Optimal Power Flow Problems 471
Loi Lei Lai and Nidul Sinha
17.1 Introduction 471
17.2 Genetic Algorithms 473
17.2.1 Terms Used in GA 473
17.3 Load Flow Problem 478
17.4 Optimal Power Flow Problem 483
17.4.1 Application Examples 485
17.5 OPF with FACTS Devices 488
17.5.1 FACTS Model 492
17.5.2 Problem Formulation 495
17.5.3 Numerical Results 496
17.6 Conclusions 499
References 499
18 An Interactive Compromise Programming-Based Multiobjective Approach to FACTS Control 501
Ying Xiao, Yong-Hua Song, and Chen-Ching Liu
18.1 Introduction 501
18.2 Review of Multiobjective Optimization Techniques 503
18.2.1 Weighting Method 503
18.2.2 Goal Programming 504
18.2.3 1-Constraint Method 504
18.2.4 Compromise Programming 504
18.2.5 Fuzzy Set Theory Applications 505
18.2.6 Genetic Algorithm 505
18.2.7 Interactive Procedure 506
18.3 Formulated MO Optimization Model 506
18.3.1 Formulated MO Optimization Model for FACTS Control 507
18.3.2 Power Flow Control Model of FACTS Devices 508
18.4 Proposed Interactive Displaced Worst Compromise Programming Method 511
18.4.1 Applied Fuzzy CP 511
18.4.2 Operation Cost Minimization 512
18.4.3 Local Power Flow Control 512
18.5 Proposed Interactive Procedure with WC Displacement 513
18.5.1 Phase 1: Model Formulation 513
18.5.2 Phase 2: Noninferior Solution Calculation 514
18.5.3 Phase 3: Scenario Evaluation 514
18.6 Implementation 516
18.7 Numerical Results 516
18.8 Conclusions 521
References 521
19 Hybrid Systems 525
Vladimiro Miranda
19.1 Introduction 525
19.2 Capacitor Sizing and Location and Analytical Sensitivities 527
19.2.1 From Darwin to Lamarck: Three Models 528
19.2.2 Building a Lamarckian Acquisition of Improvements 529
19.2.3 Analysis of a Didactic Example 531
19.3 Unit Commitment Fuzzy Sets and Cleverer Chromosomes 538
19.3.1 The Deceptive Characteristics of Unit Commitment Problems 538
19.3.2 Similarity Between the Capacitor Placement and the Unit Commitment Problems 539
19.3.3 The Need for Cleverer Chromosomes 540
19.3.4 A Biological Touch: The Chromosome as a Program 541
19.3.5 A Real-World Example: The CARE Model in Crete Greece 542
19.3.6 Fitness Evaluation: Reliability (Spinning Reserve as a Fuzzy Constraint) 547
19.3.7 Illustrative Results 547
19.4 Voltage/Var Control and Loss Reduction in Distribution Networks with an Evolutionary Self-Adaptive Particle Swarm Optimization Algorithm: EPSO 550
19.4.1 Justifying a Hybrid Approach 550
19.4.2 The Principles of EPSO: Reproduction and Movement Rule 551
19.4.3 Mutating Strategic Parameters 552
19.4.4 The Merits of EPSO 553
19.4.5 Experiencing with EPSO: Basic EPSO Model 554
19.4.6 EPSO in Test Functions 554
19.4.7 EPSO in Loss Reduction and Voltage/VAR Control: Definition of the Problem 557
19.4.8 Applying EPSO in the Management of Networks with Distributed Generation 558
19.5 Conclusions 559
References 560
Index 563
