Meta-heuristic and Evolutionary Algorithms for Engineering Optimization

Omid Bozorg-Haddad, PhD, is Professor in the Department of Irrigation and Reclamation Engineering at the University of Tehran, Iran.Mohammad Solgi, M.Sc., is Teacher Assistant for M.Sc. courses at the University of Tehran, Iran.Hugo A. Loáiciga, PhD, is Professor in the Department of Geography at the University of California, Santa Barbara, United States of America.

• Preface xvAbout the Authors xviiList of Figures xix1 Overview of Optimization 1Summary 11.1 Optimization 11.1.1 Objective Function 21.1.2 Decision Variables 21.1.3 Solutions of an Optimization Problem 31.1.4 Decision Space 31.1.5 Constraints or Restrictions 31.1.6 State Variables 31.1.7 Local and Global Optima 41.1.8 Near-Optimal Solutions 51.1.9 Simulation 61.2 Examples of the Formulation of Various Engineering Optimization Problems 71.2.1 Mechanical Design 71.2.2 Structural Design 91.2.3 Electrical Engineering Optimization 101.2.4 Water Resources Optimization 111.2.5 Calibration of Hydrologic Models 131.3 Conclusion 152 Introduction to Meta-Heuristic and Evolutionary Algorithms 17Summary 172.1 Searching the Decision Space for Optimal Solutions 172.2 Definition of Terms of Meta-Heuristic and Evolutionary Algorithms 212.2.1 Initial State 212.2.2 Iterations 212.2.3 Final State 212.2.4 Initial Data (Information) 212.2.5 Decision Variables 222.2.6 State Variables 232.2.7 Objective Function 232.2.8 Simulation Model 242.2.9 Constraints 242.2.10 Fitness Function 242.3 Principles of Meta-Heuristic and Evolutionary Algorithms 252.4 Classification of Meta-Heuristic and Evolutionary Algorithms 272.4.1 Nature-Inspired and Non-Nature-Inspired Algorithms 272.4.2 Population-Based and Single-Point Search Algorithms 282.4.3 Memory-Based and Memory-Less Algorithms 282.5 Meta-Heuristic and Evolutionary Algorithms in Discrete or Continuous Domains 282.6 Generating Random Values of the Decision Variables 292.7 Dealing with Constraints 292.7.1 Removal Method 302.7.2 Refinement Method 302.7.3 Penalty Functions 312.8 Fitness Function 332.9 Selection of Solutions in Each Iteration 332.10 Generating New Solutions 342.11 The Best Solution in Each Algorithmic Iteration 352.12 Termination Criteria 352.13 General Algorithm 362.14 Performance Evaluation of Meta-Heuristic and Evolutionary Algorithms 362.15 Search Strategies 392.16 Conclusion 41References 413 Pattern Search 43Summary 433.1 Introduction 433.2 Pattern Search (PS) Fundamentals 443.3 Generating an Initial Solution 473.4 Generating Trial Solutions 473.4.1 Exploratory Move 473.4.2 Pattern Move 493.5 Updating the Mesh Size 503.6 Termination Criteria 503.7 User-Defined Parameters of the PS 513.8 Pseudocode of the PS 513.9 Conclusion 52References 524 Genetic Algorithm 53Summary 534.1 Introduction 534.2 Mapping the Genetic Algorithm (GA) to Natural Evolution 544.3 Creating an Initial Population 564.4 Selection of Parents to Create a New Generation 564.4.1 Proportionate Selection 574.4.2 Ranking Selection 584.4.3 Tournament Selection 594.5 Population Diversity and Selective Pressure 594.6 Reproduction 594.6.1 Crossover 604.6.2 Mutation 624.7 Termination Criteria 634.8 User- Defined Parameters of the GA 634.9 Pseudocode of the GA 644.10 Conclusion 65References 655 Simulated Annealing 69Summary 695.1 Introduction 695.2 Mapping the Simulated Annealing (SA) Algorithm to the Physical Annealing Process 705.3 Generating an Initial State 725.4 Generating a New State 725.5 Acceptance Function 745.6 Thermal Equilibrium 755.7 Temperature Reduction 755.8 Termination Criteria 765.9 User- Defined Parameters of the SA 765.10 Pseudocode of the SA 775.11 Conclusion 77References 776 Tabu Search 79Summary 796.1 Introduction 796.2 Tabu Search (TS) Foundation 806.3 Generating an Initial Searching Point 826.4 Neighboring Points 826.5 Tabu Lists 846.6 Updating the Tabu List 846.7 Attributive Memory 856.7.1 Frequency-Based Memory 856.7.2 Recency-Based Memory 856.8 Aspiration Criteria 876.9 Intensification and Diversification Strategies 876.10 Termination Criteria 876.11 User- Defined Parameters of the TS 876.12 Pseudocode of the TS 886.13 Conclusion 89References 897 Ant Colony Optimization 91Summary 917.1 Introduction 917.2 Mapping Ant Colony Optimization (ACO) to Ants’ Foraging Behavior 927.3 Creating an Initial Population 947.4 Allocating Pheromone to the Decision Space 967.5 Generation of New Solutions 987.6 Termination Criteria 997.7 User- Defined Parameters of the ACO 997.8 Pseudocode of the ACO 1007.9 Conclusion 100References 1018 Particle Swarm Optimization 103Summary 1038.1 Introduction 1038.2 Mapping Particle Swarm Optimization (PSO) to the Social Behavior of Some Animals 1048.3 Creating an Initial Population of Particles 1078.4 The Individual and Global Best Positions 1078.5 Velocities of Particles 1098.6 Updating the Positions of Particles 1108.7 Termination Criteria 1108.8 User- Defined Parameters of the PSO 1108.9 Pseudocode of the PSO 1118.10 Conclusion 112References 1129 Differential Evolution 115Summary 1159.1 Introduction 1159.2 Differential Evolution (DE) Fundamentals 1169.3 Creating an Initial Population 1189.4 Generating Trial Solutions 1199.4.1 Mutation 1199.4.2 Crossover 1199.5 Greedy Criteria 1209.6 Termination Criteria 1209.7 User-Defined Parameters of the DE 1209.8 Pseudocode of the DE 1219.9 Conclusion 121References 12110 Harmony Search 123Summary 12310.1 Introduction 12310.2 Inspiration of the Harmony Search (HS) 12410.3 Initializing the Harmony Memory 12510.4 Generating New Harmonies (Solutions) 12710.4.1 Memory Strategy 12710.4.2 Random Selection 12810.4.3 Pitch Adjustment 12910.5 Updating the Harmony Memory 12910.6 Termination Criteria 13010.7 User- Defined Parameters of the HS 13010.8 Pseudocode of the HS 13010.9 Conclusion 131References 13111 Shuffled Frog-Leaping Algorithm 133Summary 13311.1 Introduction 13311.2 Mapping Memetic Evolution of Frogs to the Shuffled Frog Leaping Algorithm (SFLA) 13411.3 Creating an Initial Population 13711.4 Classifying Frogs into Memeplexes 13711.5 Frog Leaping 13811.6 Shuffling Process 14011.7 Termination Criteria 14111.8 User-Defined Parameters of the SFLA 14111.9 Pseudocode of the SFLA 14111.10 Conclusion 142References 14212 Honey-Bee Mating Optimization 145Summary 14512.1 Introduction 14512.2 Mapping Honey-Bee Mating Optimization (HBMO) to the Honey- Bee Colony Structure 14612.3 Creating an Initial Population 14812.4 The Queen 15012.5 Drone Selection 15012.5.1 Mating Flights 15112.5.2 Trial Solutions 15212.6 Brood (New Solution) Production 15212.7 Improving Broods (New Solutions) by Workers 15512.8 Termination Criteria 15612.9 User-Defined Parameters of the HBMO 15612.10 Pseudocode of the HBMO 15612.11 Conclusion 158References 15813 Invasive Weed Optimization 163Summary 16313.1 Introduction 16313.2 Mapping Invasive Weed Optimization (IWO) to Weeds’ Biology 16413.3 Creating an Initial Population 16713.4 Reproduction 16713.5 The Spread of Seeds 16813.6 Eliminating Weeds with Low Fitness 16913.7 Termination Criteria 17013.8 User- Defined Parameters of the IWO 17013.9 Pseudocode of the IWO 17013.10 Conclusion 171References 17114 Central Force Optimization 175Summary 17514.1 Introduction 17514.2 Mapping Central Force Optimization (CFO) to Newtons Gravitational Law 17614.3 Initializing the Position of Probes 17714.4 Calculation of Accelerations 18014.5 Movement of Probes 18114.6 Modification of Deviated Probes 18114.7 Termination Criteria 18214.8 User-Defined Parameters of the CFO 18214.9 Pseudocode of the CFO 18314.10 Conclusion 183References 18315 Biogeography-Based Optimization 185Summary 18515.1 Introduction 18515.2 Mapping Biogeography-Based Optimization (BBO) to Biogeography Concepts 18615.3 Creating an Initial Population 18815.4 Migration Process 18915.5 Mutation 19115.6 Termination Criteria 19215.7 User- Defined Parameters of the BBO 19215.8 Pseudocode of the BBO 19315.9 Conclusion 193References 19416 Firefly Algorithm 195Summary 19516.1 Introduction 19516.2 Mapping the Firefly Algorithm (FA) to the Flashing Characteristics of Fireflies 19616.3 Creating an Initial Population 19816.4 Attractiveness 19916.5 Distance and Movement 19916.6 Termination Criteria 20016.7 User-Defined Parameters of the FA 20016.8 Pseudocode of the FA 20116.9 Conclusion 201References 20117 Gravity Search Algorithm 203Summary 20317.1 Introduction 20317.2 Mapping the Gravity Search Algorithm (GSA) to the Law of Gravity 20417.3 Creating an Initial Population 20517.4 Evaluation of Particle Masses 20717.5 UpdatingVelocities and Positions 20717.6 Updating Newton’s Gravitational Factor 20817.7 Termination Criteria 20917.8 User- Defined Parameters of the GSA 20917.9 Pseudocode of the GSA 20917.10 Conclusion 210References 21018 Bat Algorithm 213Summary 21318.1 Introduction 21318.2 Mapping the Bat Algorithm (BA) to the Behavior of Microbats 21418.3 Creating an Initial Population 21518.4 Movement of Virtual Bats 21718.5 Local Search and Random Flying 21818.6 Loudness and Pulse Emission 21818.7 Termination Criteria 21918.8 User-Defined Parameters of the BA 21918.9 Pseudocode of the BA 21918.10 Conclusion 220References 22019 Plant Propagation Algorithm 223Summary 22319.1 Introduction 22319.2 Mapping the Natural Process to the Planet Propagation Algorithm (PPA) 22319.3 Creating an Initial Population of Plants 22619.4 Normalizing the Fitness Function 22619.5 Propagation 22719.6 Elimination of Extra Solutions 22819.7 Termination Criteria 22819.8 User-Defined Parameters of the PPA 22819.9 Pseudocode of the PPA 22919.10 Conclusion 230References 23020 Water Cycle Algorithm 231Summary 23120.1 Introduction 23120.2 Mapping the Water Cycle Algorithm (WCA) to the Water Cycle 23220.3 Creating an Initial Population 23320.4 Classification of Raindrops 23520.5 Streams Flowing to the Rivers or Sea 23620.6 Evaporation 23720.7 Raining Process 23820.8 Termination Criteria 23920.9 User-Defined Parameters of the WCA 23920.10 Pseudocode of the WCA 23920.11 Conclusion 240References 24021 Symbiotic Organisms Search 241Summary 24121.1 Introduction 24121.2 Mapping Symbiotic Relations to the Symbiotic Organisms Search (SOS) 24121.3 Creating an Initial Ecosystem 24221.4 Mutualism 24421.5 Commensalism 24521.6 Parasitism 24521.7 Termination Criteria 24621.8 Pseudocode of the SOS 24621.9 Conclusion 247References 24722 Comprehensive Evolutionary Algorithm 249Summary 24922.1 Introduction 24922.2 Fundamentals of the Comprehensive Evolutionary Algorithm (CEA) 25022.3 Generating an Initial Population of Solutions 25322.4 Selection 25322.5 Reproduction 25522.5.1 Crossover Operators 25522.5.2 Mutation Operators 26122.6 Roles of Operators 26222.7 Input Data to the CEA 26322.8 Termination Criteria 26422.9 Pseudocode of the CEA 26522.10 Conclusion 265References 266Wiley Series in Operations Research and Management Science 267Index 269