Meta-heuristic and Evolutionary Algorithms for Engineering Optimization
Description
More details
Other editions
Additional editions
Persons
Content
Preface xv
About the Authors xvii
List of Figures xix
1 Overview of Optimization 1
Summary 1
1.1 Optimization 1
1.1.1 Objective Function 2
1.1.2 Decision Variables 2
1.1.3 Solutions of an Optimization Problem 3
1.1.4 Decision Space 3
1.1.5 Constraints or Restrictions 3
1.1.6 State Variables 3
1.1.7 Local and Global Optima 4
1.1.8 Near?-Optimal Solutions 5
1.1.9 Simulation 6
1.2 Examples of the Formulation of Various Engineering Optimization Problems 7
1.2.1 Mechanical Design 7
1.2.2 Structural Design 9
1.2.3 Electrical Engineering Optimization 10
1.2.4 Water Resources Optimization 11
1.2.5 Calibration of Hydrologic Models 13
1.3 Conclusion 15
2 Introduction to Meta?-Heuristic and Evolutionary Algorithms 17
Summary 17
2.1 Searching the Decision Space for Optimal Solutions 17
2.2 Definition of Terms of Meta?-Heuristic and Evolutionary Algorithms 21
2.2.1 Initial State 21
2.2.2 Iterations 21
2.2.3 Final State 21
2.2.4 Initial Data (Information) 21
2.2.5 Decision Variables 22
2.2.6 State Variables 23
2.2.7 Objective Function 23
2.2.8 Simulation Model 24
2.2.9 Constraints 24
2.2.10 Fitness Function 24
2.3 Principles of Meta?-Heuristic and Evolutionary Algorithms 25
2.4 Classification of Meta?-Heuristic and Evolutionary Algorithms 27
2.4.1 Nature?-Inspired and Non?-Nature?-Inspired Algorithms 27
2.4.2 Population?-Based and Single?-Point Search Algorithms 28
2.4.3 Memory?-Based and Memory?-Less Algorithms 28
2.5 Meta?-Heuristic and Evolutionary Algorithms in Discrete or Continuous Domains 28
2.6 Generating Random Values of the Decision Variables 29
2.7 Dealing with Constraints 29
2.7.1 Removal Method 30
2.7.2 Refinement Method 30
2.7.3 Penalty Functions 31
2.8 Fitness Function 33
2.9 Selection of Solutions in Each Iteration 33
2.10 Generating New Solutions 34
2.11 The Best Solution in Each Algorithmic Iteration 35
2.12 Termination Criteria 35
2.13 General Algorithm 36
2.14 Performance Evaluation of Meta?-Heuristic and Evolutionary Algorithms 36
2.15 Search Strategies 39
2.16 Conclusion 41
References 41
3 Pattern Search 43
Summary 43
3.1 Introduction 43
3.2 Pattern Search (PS) Fundamentals 44
3.3 Generating an Initial Solution 47
3.4 Generating Trial Solutions 47
3.4.1 Exploratory Move 47
3.4.2 Pattern Move 49
3.5 Updating the Mesh Size 50
3.6 Termination Criteria 50
3.7 User?-Defined Parameters of the PS 51
3.8 Pseudocode of the PS 51
3.9 Conclusion 52
References 52
4 Genetic Algorithm 53
Summary 53
4.1 Introduction 53
4.2 Mapping the Genetic Algorithm (GA) to Natural Evolution 54
4.3 Creating an Initial Population 56
4.4 Selection of Parents to Create a New Generation 56
4.4.1 Proportionate Selection 57
4.4.2 Ranking Selection 58
4.4.3 Tournament Selection 59
4.5 Population Diversity and Selective Pressure 59
4.6 Reproduction 59
4.6.1 Crossover 60
4.6.2 Mutation 62
4.7 Termination Criteria 63
4.8 User?- Defined Parameters of the GA 63
4.9 Pseudocode of the GA 64
4.10 Conclusion 65
References 65
5 Simulated Annealing 69
Summary 69
5.1 Introduction 69
5.2 Mapping the Simulated Annealing (SA) Algorithm to the Physical Annealing Process 70
5.3 Generating an Initial State 72
5.4 Generating a New State 72
5.5 Acceptance Function 74
5.6 Thermal Equilibrium 75
5.7 Temperature Reduction 75
5.8 Termination Criteria 76
5.9 User?- Defined Parameters of the SA 76
5.10 Pseudocode of the SA 77
5.11 Conclusion 77
References 77
6 Tabu Search 79
Summary 79
6.1 Introduction 79
6.2 Tabu Search (TS) Foundation 80
6.3 Generating an Initial Searching Point 82
6.4 Neighboring Points 82
6.5 Tabu Lists 84
6.6 Updating the Tabu List 84
6.7 Attributive Memory 85
6.7.1 Frequency?-Based Memory 85
6.7.2 Recency?-Based Memory 85
6.8 Aspiration Criteria 87
6.9 Intensification and Diversification Strategies 87
6.10 Termination Criteria 87
6.11 User?- Defined Parameters of the TS 87
6.12 Pseudocode of the TS 88
6.13 Conclusion 89
References 89
7 Ant Colony Optimization 91
Summary 91
7.1 Introduction 91
7.2 Mapping Ant Colony Optimization (ACO) to Ants' Foraging Behavior 92
7.3 Creating an Initial Population 94
7.4 Allocating Pheromone to the Decision Space 96
7.5 Generation of New Solutions 98
7.6 Termination Criteria 99
7.7 User?- Defined Parameters of the ACO 99
7.8 Pseudocode of the ACO 100
7.9 Conclusion 100
References 101
8 Particle Swarm Optimization 103
Summary 103
8.1 Introduction 103
8.2 Mapping Particle Swarm Optimization (PSO) to the Social Behavior of Some Animals 104
8.3 Creating an Initial Population of Particles 107
8.4 The Individual and Global Best Positions 107
8.5 Velocities of Particles 109
8.6 Updating the Positions of Particles 110
8.7 Termination Criteria 110
8.8 User?- Defined Parameters of the PSO 110
8.9 Pseudocode of the PSO 111
8.10 Conclusion 112
References 112
9 Differential Evolution 115
Summary 115
9.1 Introduction 115
9.2 Differential Evolution (DE) Fundamentals 116
9.3 Creating an Initial Population 118
9.4 Generating Trial Solutions 119
9.4.1 Mutation 119
9.4.2 Crossover 119
9.5 Greedy Criteria 120
9.6 Termination Criteria 120
9.7 User?-Defined Parameters of the DE 120
9.8 Pseudocode of the DE 121
9.9 Conclusion 121
References 121
10 Harmony Search 123
Summary 123
10.1 Introduction 123
10.2 Inspiration of the Harmony Search (HS) 124
10.3 Initializing the Harmony Memory 125
10.4 Generating New Harmonies (Solutions) 127
10.4.1 Memory Strategy 127
10.4.2 Random Selection 128
10.4.3 Pitch Adjustment 129
10.5 Updating the Harmony Memory 129
10.6 Termination Criteria 130
10.7 User?- Defined Parameters of the HS 130
10.8 Pseudocode of the HS 130
10.9 Conclusion 131
References 131
11 Shuffled Frog?-Leaping Algorithm 133
Summary 133
11.1 Introduction 133
11.2 Mapping Memetic Evolution of Frogs to the Shuffled Frog Leaping Algorithm (SFLA) 134
11.3 Creating an Initial Population 137
11.4 Classifying Frogs into Memeplexes 137
11.5 Frog Leaping 138
11.6 Shuffling Process 140
11.7 Termination Criteria 141
11.8 User?-Defined Parameters of the SFLA 141
11.9 Pseudocode of the SFLA 141
11.10 Conclusion 142
References 142
12 Honey?-Bee Mating Optimization 145
Summary 145
12.1 Introduction 145
12.2 Mapping Honey?-Bee Mating Optimization (HBMO) to the Honey?- Bee Colony Structure 146
12.3 Creating an Initial Population 148
12.4 The Queen 150
12.5 Drone Selection 150
12.5.1 Mating Flights 151
12.5.2 Trial Solutions 152
12.6 Brood (New Solution) Production 152
12.7 Improving Broods (New Solutions) by Workers 155
12.8 Termination Criteria 156
12.9 User?-Defined Parameters of the HBMO 156
12.10 Pseudocode of the HBMO 156
12.11 Conclusion 158
References 158
13 Invasive Weed Optimization 163
Summary 163
13.1 Introduction 163
13.2 Mapping Invasive Weed Optimization (IWO) to Weeds' Biology 164
13.3 Creating an Initial Population 167
13.4 Reproduction 167
13.5 The Spread of Seeds 168
13.6 Eliminating Weeds with Low Fitness 169
13.7 Termination Criteria 170
13.8 User?- Defined Parameters of the IWO 170
13.9 Pseudocode of the IWO 170
13.10 Conclusion 171
References 171
14 Central Force Optimization 175
Summary 175
14.1 Introduction 175
14.2 Mapping Central Force Optimization (CFO) to Newtons Gravitational Law 176
14.3 Initializing the Position of Probes 177
14.4 Calculation of Accelerations 180
14.5 Movement of Probes 181
14.6 Modification of Deviated Probes 181
14.7 Termination Criteria 182
14.8 User?-Defined Parameters of the CFO 182
14.9 Pseudocode of the CFO 183
14.10 Conclusion 183
References 183
15 Biogeography?-Based Optimization 185
Summary 185
15.1 Introduction 185
15.2 Mapping Biogeography?-Based Optimization (BBO) to Biogeography Concepts 186
15.3 Creating an Initial Population 188
15.4 Migration Process 189
15.5 Mutation 191
15.6 Termination Criteria 192
15.7 User?- Defined Parameters of the BBO 192
15.8 Pseudocode of the BBO 193
15.9 Conclusion 193
References 194
16 Firefly Algorithm 195
Summary 195
16.1 Introduction 195
16.2 Mapping the Firefly Algorithm (FA) to the Flashing Characteristics of Fireflies 196
16.3 Creating an Initial Population 198
16.4 Attractiveness 199
16.5 Distance and Movement 199
16.6 Termination Criteria 200
16.7 User?-Defined Parameters of the FA 200
16.8 Pseudocode of the FA 201
16.9 Conclusion 201
References 201
17 Gravity Search Algorithm 203
Summary 203
17.1 Introduction 203
17.2 Mapping the Gravity Search Algorithm (GSA) to the Law of Gravity 204
17.3 Creating an Initial Population 205
17.4 Evaluation of Particle Masses 207
17.5 UpdatingVelocities and Positions 207
17.6 Updating Newton's Gravitational Factor 208
17.7 Termination Criteria 209
17.8 User?- Defined Parameters of the GSA 209
17.9 Pseudocode of the GSA 209
17.10 Conclusion 210
References 210
18 Bat Algorithm 213
Summary 213
18.1 Introduction 213
18.2 Mapping the Bat Algorithm (BA) to the Behavior of Microbats 214
18.3 Creating an Initial Population 215
18.4 Movement of Virtual Bats 217
18.5 Local Search and Random Flying 218
18.6 Loudness and Pulse Emission 218
18.7 Termination Criteria 219
18.8 User?-Defined Parameters of the BA 219
18.9 Pseudocode of the BA 219
18.10 Conclusion 220
References 220
19 Plant Propagation Algorithm 223
Summary 223
19.1 Introduction 223
19.2 Mapping the Natural Process to the Planet Propagation Algorithm (PPA) 223
19.3 Creating an Initial Population of Plants 226
19.4 Normalizing the Fitness Function 226
19.5 Propagation 227
19.6 Elimination of Extra Solutions 228
19.7 Termination Criteria 228
19.8 User?-Defined Parameters of the PPA 228
19.9 Pseudocode of the PPA 229
19.10 Conclusion 230
References 230
20 Water Cycle Algorithm 231
Summary 231
20.1 Introduction 231
20.2 Mapping the Water Cycle Algorithm (WCA) to the Water Cycle 232
20.3 Creating an Initial Population 233
20.4 Classification of Raindrops 235
20.5 Streams Flowing to the Rivers or Sea 236
20.6 Evaporation 237
20.7 Raining Process 238
20.8 Termination Criteria 239
20.9 User?-Defined Parameters of the WCA 239
20.10 Pseudocode of the WCA 239
20.11 Conclusion 240
References 240
21 Symbiotic Organisms Search 241
Summary 241
21.1 Introduction 241
21.2 Mapping Symbiotic Relations to the Symbiotic Organisms Search (SOS) 241
21.3 Creating an Initial Ecosystem 242
21.4 Mutualism 244
21.5 Commensalism 245
21.6 Parasitism 245
21.7 Termination Criteria 246
21.8 Pseudocode of the SOS 246
21.9 Conclusion 247
References 247
22 Comprehensive Evolutionary Algorithm 249
Summary 249
22.1 Introduction 249
22.2 Fundamentals of the Comprehensive Evolutionary Algorithm (CEA) 250
22.3 Generating an Initial Population of Solutions 253
22.4 Selection 253
22.5 Reproduction 255
22.5.1 Crossover Operators 255
22.5.2 Mutation Operators 261
22.6 Roles of Operators 262
22.7 Input Data to the CEA 263
22.8 Termination Criteria 264
22.9 Pseudocode of the CEA 265
22.10 Conclusion 265
References 266
Wiley Series in Operations Research and Management Science 267
Index 269
List of Figures
Figure 1.1 Decision space of a constrained two-dimensional optimization problem. Figure 1.2 Schematic of global and local optimums in a one-dimensional maximizing optimization problem. Figure 1.3 Different types of decision spaces: (a) maximization problem with single-modal surface and one global optimum; (b) maximization problem with multimodal surface that has one global optimum. Figure 1.4 Demonstration of near optima in a one-dimensional maximizing optimization problem. Figure 1.5 Compound gear train made of four gears. Figure 1.6 Schematic of a two-bar truss. Figure 1.7 Schematic of a hydropower dam. Figure 2.1 Sampling grid on a two-dimensional decision space. Figure 2.2 General schematic of a simple algorithm; K denotes the counter of iterations. Figure 2.3 Diagram depicting the relation between a simulation model and an optimization algorithm. Figure 2.4 The main components of the optimization by meta-heuristic and evolutionary algorithms. Figure 2.5 Different solutions in a two-dimensional decision space. Figure 2.6 Selection probability of a set of solutions 1-10 of a hypothetical maximization problem. Figure 2.7 The flowchart of the general algorithm. Figure 2.8 Convergence history of an optimization algorithm toward the best solution in a minimization problem. Figure 2.9 Convergence of an optimization algorithm in which the best solution is not always transferred to the next iteration during the search in a minimization problem. Figure 2.10 Convergence of different runs of an optimization algorithm toward near-optimal solutions of a minimization problem. Figure 2.11 Convergence of different runs of an optimization algorithm in a minimization problem. Figure 3.1 The flowchart of the PS. Figure 3.2 Meshes generated by the GPS and MADS methods in a two-dimensional decision space. Figure 4.1 The flowchart of the GA. Figure 4.2 Demonstration of a roulette wheel. F = Fitness function value; P = probability of selecting a solution. Figure 4.3 Ranking chromosomes (or solutions) according to the fitness function (F) in a maximizing problem. Figure 4.4 The process of constituting a new generation from the previous generation. Figure 4.5 Different approaches of crossover: (a) one-point crossover, (b) two-point crossover, and (c) uniform crossover. Figure 4.6 An example of the mutation operator.62Figure 5.1The flowchart of the SA. Figure 6.1 The flowchart of the TS. Figure 6.2 The decision space of a two-dimensional optimization problem. Figure 6.3 Illustration of steps based on recency-based memory in a two-dimensional decision space. Figure 7.1 A double-bridge experiment with pathways of unequal length. Figure 7.2 The flowchart of the ACO. Figure 7.3 Representation of a solution in the ACO; there are M such solutions. Figure 8.1 The flowchart of the PSO. Figure 8.2 Concepts of the best individual position in a two-dimensional maximization problem. Figure 8.3 Concept of the global best position in a maximization problem. Figure 9.1 The flowchart of the DE. Figure 10.1 The flowchart of the HS. Figure 10.2 Generating a new solution based on memory strategy. Figure 11.1 The flowchart of the SFLA. Figure 11.2 Sorting frogs according to the fitness function F(X) in a maximizing problem. Figure 11.3 Assigning frogs to different memeplexes; Z = number of memeplexes and Y = number of frogs assigned to each memeplex. Figure 11.4 The representation of a memeplex and a submemeplex within the entire population. Figure 12.1 The flowchart of the HBMO algorithm. Figure 12.2 Determining the queen and trial solutions according to the fitness function F(X). Figure 12.3 Different crossover approaches: (a) one-point crossover, (b) two-point crossover, and (c) uniform crossover. Figure 12.4 Performance of mutation operator. Figure 13.1 The flowchart of the IWO. Figure 13.2 Number of seeds for each weed with respect to the fitness value. Figure 14.1 The flowchart of the CFO. Figure 14.2 Distribution of initial probes in the CFO algorithm. Figure 15.1 Species immigration and emigration pattern in a habitat. Figure 15.2 The flowchart of the BBO. Figure 15.3 Comparison of two solutions for one problem. Figure 15.4 Ranking habitats (solutions) according to their fitness values in a minimization problem. Figure 16.1 The flowchart of the FA. Figure 17.1 Gravity force between different particles; Force1 is the resultant force on Mass1. Figure 17.2 The flowchart of the GSA. Figure 18.1 The flowchart of the BA. Figure 19.1 The flowchart of the PPA. Figure 20.1 The flowchart of the WCA for a minimization problem. Figure 20.2 Classification of raindrops and relations between the sea, rivers, and streams according to their fitness values (F(X)) for a minimization problem where M = 10 and R = 3. Figure 20.3 Schematic of stream flowing toward a river at distance d: X: existing stream; X´: new stream. Figure 21.1 The flowchart of the SOS. Figure 22.1 The flowchart of the CEA. Figure 22.2 Illustration of a roulette wheel. Figure 22.3 Types of one-point cut crossover in the CEA: (a) Type 1 (new solution (1)) and type 2 (new solution (2)), (b) Type 3 (new solution (1)) and type 4 (new solution (2)), (c) Type 5 (new solution (1)) and type 6 (new solution (2)), (d) Type 7 (new solution (1)) and type 8 (new solution (2)), and (e) Type 9 (new solution (1)) and type 10 (new solution (2)). Figure 22.4 Types of two-point cut crossover in the CEA: (a) Type 11 (new solution (1)) and type 12 (new solution (2)), (b) Type 13 (new solution (1)) and type 14 (new solution (2)), (c) Type 15 (new solution (1)) and type 16 (new solution (2)), (d) Type 17 (new solution (1)) and type 18 (new solution (2)), and (e) Type 19 (new solution (1)) and type 20 (new solution (2)). Figure 22.5 Types of...
