Modern Heuristic Optimization Techniques: Theory and Applications to Power Systems

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 T₀ 128

7.3.2 Determination of N_k 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