Introduction to Genetic Algorithms

Contents
1 Evolutionary Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 The Historical Development of EC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.1 Genetic Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.2 Genetic Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.3 Evolutionary Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.4 Evolutionary Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Features of Evolutionary Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3.1 Particulate Genes and Population Genetics . . . . . . . . . . . . . . . . . . 6
1.3.2 The Adaptive Code Book . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3.3 The Genotype/Phenotype Dichotomy . . . . . . . . . . . . . . . . . . . . . . . 8
1.4 Advantages of Evolutionary Computation . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.4.1 Conceptual Simplicity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.4.2 Broad Applicability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.4.3 Hybridization with Other Methods . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.4.4 Parallelism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.4.5 Robust to Dynamic Changes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.4.6 Solves Problems that have no Solutions . . . . . . . . . . . . . . . . . . . . . 12
1.5 Applications of Evolutionary Computation . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2 Genetic Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2 Biological Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2.1 The Cell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2.2 Chromosomes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2.3 Genetics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2.4 Reproduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2.5 Natural Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3 What is Genetic Algorithm? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.3.1 Search Space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.3.2 Genetic Algorithms World . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.3.3 Evolution and Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3.4 Evolution and Genetic Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.4 Conventional Optimization and Search Techniques . . . . . . . . . . . . . . . . . . 24
2.4.1 Gradient-Based Local Optimization Method . . . . . . . . . . . . . . . . . 25
2.4.2 Random Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.4.3 Stochastic Hill Climbing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.4.4 Simulated Annealing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.4.5 Symbolic Artificial Intelligence (AI) . . . . . . . . . . . . . . . . . . . . . . . 29
2.5 A Simple Genetic Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.6 Comparison of Genetic Algorithm with Other
Optimization Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.7 Advantages and Limitations of Genetic Algorithm . . . . . . . . . . . . . . . . . . 34
2.8 Applications of Genetic Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3 Terminologies and Operators of GA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.2 Key Elements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.3 Individuals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.4 Genes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.5 Fitness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.6 Populations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.7 Data Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.8 Search Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.9 Encoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.9.1 Binary Encoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.9.2 Octal Encoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.9.3 Hexadecimal Encoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.9.4 Permutation Encoding (Real Number Coding) . . . . . . . . . . . . . . . 44
3.9.5 Value Encoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.9.6 Tree Encoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.10 Breeding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.10.1 Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.10.2 Crossover (Recombination) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.10.3 Mutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.10.4 Replacement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.11 Search Termination (Convergence Criteria) . . . . . . . . . . . . . . . . . . . . . . . . 59
3.11.1 Best Individual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.11.2 Worst individual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.11.3 Sum of Fitness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.11.4 Median Fitness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.12 Why do Genetic Algorithms Work? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.12.1 Building Block Hypothesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.12.2 A Macro-Mutation Hypothesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
3.12.3 An Adaptive Mutation Hypothesis . . . . . . . . . . . . . . . . . . . . . . . . . 62
3.12.4 The Schema Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.12.5 Optimal Allocation of Trials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
3.12.6 Implicit Parallelism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
3.12.7 The No Free Lunch Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
3.13 Solution Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
3.14 Search Refinement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
3.15 Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
3.16 Fitness Scaling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
3.16.1 Linear Scaling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
3.16.2 Sigma Truncation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
3.16.3 Power Law Scaling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
3.17 Example Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
3.17.1 Maximizing a Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
3.17.2 Traveling Salesman Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
3.18 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
Exercise Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
4 Advanced Operators and Techniques in Genetic Algorithm . . . . . . . . . . 83
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
4.2 Diploidy, Dominance and Abeyance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
4.3 Multiploid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
4.4 Inversion and Reordering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
4.4.1 Partially Matched Crossover (PMX) . . . . . . . . . . . . . . . . . . . . . . . . 88
4.4.2 Order Crossover (OX) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
4.4.3 Cycle Crossover (CX) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
4.5 Niche and Speciation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
4.5.1 Niche and Speciation in Multimodal Problems . . . . . . . . . . . . . . . 90
4.5.2 Niche and Speciation in Unimodal Problems. . . . . . . . . . . . . . . . . 93
4.5.3 Restricted Mating . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
4.6 Few Micro-operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
4.6.1 Segregation and Translocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
4.6.2 Duplication and Deletion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
4.6.3 Sexual Determination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
4.7 Non-binary Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
4.8 Multi-Objective Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
4.9 Combinatorial Optimizations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
4.10 Knowledge Based Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
4.11 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
Exercise Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
5 Classification of Genetic Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
5.2 Simple Genetic Algorithm (SGA) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
5.3 Parallel and Distributed Genetic Algorithm (PGA and DGA) . . . . . . . . . 106
5.3.1 Master-Slave Parallelization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
5.3.2 Fine Grained Parallel GAs (Cellular GAs) . . . . . . . . . . . . . . . . . . . 110
5.3.3 Multiple-Deme Parallel GAs (Distributed GAs or Coarse
Grained GAs) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
5.3.4 Hierarchical Parallel Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
5.4 Hybrid Genetic Algorithm (HGA) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
5.4.1 Crossover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
5.4.2 Initialization Heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
5.4.3 The RemoveSharp Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
5.4.4 The LocalOpt Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
5.5 Adaptive Genetic Algorithm (AGA) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
5.5.1 Initialization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
5.5.2 Evaluation Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
5.5.3 Selection operator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
5.5.4 Crossover operator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
5.5.5 Mutation operator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
5.6 Fast Messy Genetic Algorithm (FmGA) . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
5.6.1 Competitive Template (CT) Generation . . . . . . . . . . . . . . . . . . . . . 123
5.7 Independent Sampling Genetic Algorithm (ISGA) . . . . . . . . . . . . . . . . . . 124
5.7.1 Independent Sampling Phase . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
5.7.2 Breeding Phase . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
5.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
Exercise Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
6 Genetic Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
6.2 Comparison of GP with Other Approaches . . . . . . . . . . . . . . . . . . . . . . . . . 131
6.3 Primitives of Genetic Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
6.3.1 Genetic Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
6.3.2 Generational Genetic Programming . . . . . . . . . . . . . . . . . . . . . . . . 136
6.3.3 Tree Based Genetic Programming . . . . . . . . . . . . . . . . . . . . . . . . . . 136
6.3.4 Representation of Genetic Programming . . . . . . . . . . . . . . . . . . . . 137
6.4 Attributes in Genetic Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
6.5 Steps of Genetic Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
6.5.1 Preparatory Steps of Genetic Programming . . . . . . . . . . . . . . . . . . 143
6.5.2 Executional Steps of Genetic Programming . . . . . . . . . . . . . . . . . . 146
6.6 Characteristics of Genetic Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
6.6.1 What We Mean by “Human-Competitive” . . . . . . . . . . . . . . . . . . . 149
6.6.2 What We Mean by “High-Return” . . . . . . . . . . . . . . . . . . . . . . . . . 152
6.6.3 What We Mean by “Routine” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
6.6.4 What We Mean by “Machine Intelligence” . . . . . . . . . . . . . . . . . . 154
6.7 Applications of Genetic Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
6.7.1 Applications of Genetic Programming
in Civil Engineering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
6.8 Haploid Genetic Programming with Dominance . . . . . . . . . . . . . . . . . . . . 159
6.8.1 Single-Node Dominance Crossover . . . . . . . . . . . . . . . . . . . . . . . . 161
6.8.2 Sub-Tree Dominance Crossover . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
6.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
Exercise Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
7 Genetic Algorithm Optimization Problems . . . . . . . . . . . . . . . . . . . . . . . . . 165
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
7.2 Fuzzy Optimization Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
7.2.1 Fuzzy Multiobjective Optimization . . . . . . . . . . . . . . . . . . . . . . . . . 166
7.2.2 Interactive Fuzzy Optimization Method . . . . . . . . . . . . . . . . . . . . . 168
7.2.3 Genetic Fuzzy Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
7.3 Multiobjective Reliability Design Problem . . . . . . . . . . . . . . . . . . . . . . . . . 170
7.3.1 Network Reliability Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
7.3.2 Bicriteria Reliability Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
7.4 Combinatorial Optimization Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
7.4.1 Linear Integer Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
7.4.2 Applications of Combinatorial Optimization . . . . . . . . . . . . . . . . . 179
7.4.3 Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
7.5 Scheduling Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
7.5.1 Genetic Algorithm for Job Shop Scheduling Problems (JSSP) . . 187
7.6 Transportation Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
7.6.1 Genetic Algorithm in Solving Transportation
Location-Allocation Problems with Euclidean Distances . . . . . . . 191
7.6.2 Real-Coded Genetic Algorithm (RCGA) for Integer Linear
Programming in Production-Transportation Problems
with Flexible Transportation Cost . . . . . . . . . . . . . . . . . . . . . . . . . . 194
7.7 Network Design and Routing Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
7.7.1 Planning of Passive Optical Networks . . . . . . . . . . . . . . . . . . . . . . 199
7.7.2 Planning of Packet Switched Networks . . . . . . . . . . . . . . . . . . . . . 202
7.7.3 Optimal Topological Design of All Terminal Networks . . . . . . . . 203
7.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
Exercise Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
8 Genetic Algorithm Implementation Using Matlab . . . . . . . . . . . . . . . . . . . 211
8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
8.2 Data Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
8.2.1 Chromosomes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212
8.2.2 Phenotypes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212
8.2.3 Objective Function Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
8.2.4 Fitness Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
8.2.5 Multiple Subpopulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
8.3 Toolbox Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
8.4 Genetic Algorithm Graphical User Interface Toolbox . . . . . . . . . . . . . . . . 219
8.5 Solved Problems using MATLAB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224
8.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260
Review Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261
Exercise Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261
9 Genetic Algorithm Optimization in C/C++ . . . . . . . . . . . . . . . . . . . . . . . . . 263
9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
9.2 Traveling Salesman Problem (TSP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
9.3 Word Matching Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271
9.4 Prisoner’s Dilemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280
9.5 Maximize f ( x ) = x
2
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286
9.6 Minimization a Sine Function with Constraints . . . . . . . . . . . . . . . . . . . . . 292
9.6.1 Problem Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293
9.7 Maximizing the Function f ( x ) = x
∗
sin ( 10
∗Π∗
x ) + 10 . . . . . . . . . . . . . . . 302
9.8 Quadratic Equation Solving . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310
9.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315
9.9.1 Projects. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315
10 Applications of Genetic Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317
10.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317
10.2 Mechanical Sector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317
10.2.1 Optimizing Cyclic-Steam Oil Production
with Genetic Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317
10.2.2 Genetic Programming and Genetic Algorithms
for Auto-tuning Mobile Robot Motion Control . . . . . . . . . . . . . . . 320
10.3 Electrical Engineering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324
10.3.1 Genetic Algorithms in Network Synthesis . . . . . . . . . . . . . . . . . . . 324
10.3.2 Genetic Algorithm Tools for Control Systems Engineering . . . . . 328
10.3.3 Genetic Algorithm Based Fuzzy Controller for Speed Control
of Brushless DC Motor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334
10.4 Machine Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 341
10.4.1 Feature Selection in Machine learning using GA . . . . . . . . . . . . . 341
10.5 Civil Engineering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345
10.5.1 Genetic Algorithm as Automatic Structural Design Tool . . . . . . . 345
10.5.2 Genetic Algorithm for Solving Site Layout Problem . . . . . . . . . . 350
10.6 Image Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352
10.6.1 Designing Texture Filters with Genetic Algorithms . . . . . . . . . . . 352
10.6.2 Genetic Algorithm Based Knowledge Acquisition
on Image Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357
10.6.3 Object Localization in Images Using Genetic Algorithm . . . . . . . 362
10.6.4 Problem Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363
10.6.5 Image Preprocessing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364
10.6.6 The Proposed Genetic Algorithm Approach . . . . . . . . . . . . . . . . . 365
10.7 Data Mining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 367
10.7.1 A Genetic Algorithm for Feature Selection in Data-Mining . . . . 367
10.7.2 Genetic Algorithm Based Fuzzy Data Mining
to Intrusion Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 370
10.7.3 Selection and Partitioning of Attributes in Large-Scale Data
Mining Problems Using Genetic Algorithm . . . . . . . . . . . . . . . . . 379
10.8 Wireless Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 386
10.8.1 Genetic Algorithms for Topology Planning
in Wireless Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 386
10.8.2 Genetic Algorithm for Wireless ATM Network . . . . . . . . . . . . . . . 387
10.9 Very Large Scale Integration (VLSI) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395
10.9.1 Development of a Genetic Algorithm Technique
for VLSI Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395
10.9.2 VLSI Macro Cell Layout Using Hybrid GA . . . . . . . . . . . . . . . . . 397
10.9.3 Problem Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 398
10.9.4 Genetic Layout Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 399
10.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 402
11 Introduction to Particle Swarm Optimization and Ant Colony
Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403
11.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403
11.2 Particle Swarm Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403
11.2.1 Background of Particle Swarm Optimization . . . . . . . . . . . . . . . . 404
11.2.2 Operation of Particle Swarm Optimization . . . . . . . . . . . . . . . . . . 405
11.2.3 Basic Flow of Particle Swarm Optimization . . . . . . . . . . . . . . . . . 407
11.2.4 Comparison Between PSO and GA . . . . . . . . . . . . . . . . . . . . . . . . 408
11.2.5 Applications of PSO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 410
11.3 Ant Colony Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 410
11.3.1 Biological Inspiration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 410
11.3.2 Similarities and Differences Between Real Ants
and Artificial Ants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414
11.3.3 Characteristics of Ant Colony Optimization . . . . . . . . . . . . . . . . . 415
11.3.4 Ant Colony Optimization Algorithms . . . . . . . . . . . . . . . . . . . . . . . 416
11.3.5 Applications of Ant Colony Optimization . . . . . . . . . . . . . . . . . . . 422
11.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 424
Exercise Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 424
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 425

Another Genetic Algorithm Books
Download