Sivanandam / Deepa Introduction to Genetic Algorithms

1. Auflage 2007
ISBN: 978-3-540-73190-0
Verlag: Springer Berlin Heidelberg
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 453 Seiten

This book offers a basic introduction to genetic algorithms. It provides a detailed explanation of genetic algorithm concepts and examines numerous genetic algorithm optimization problems. In addition, the book presents implementation of optimization problems using C and C++ as well as simulated solutions for genetic algorithm problems using MATLAB 7.0. It also includes application case studies on genetic algorithms in emerging fields.

Autoren/Hrsg.

Sivanandam, S. N.

Deepa, S. N.

Inhaltsverzeichnis

1;Preface;5
2;About the Book;7
2.1;1 Organization of the Book;7
2.2;2 Salient Features of the Book;8
3;Acknowledgement;10
4;Contents;11
5;Evolutionary Computation;18
5.1;1.1 Introduction;18
5.2;1.2 The Historical Development of EC;19
5.2.1;1.2.1 Genetic Algorithms;19
5.2.2;1.2.2 Genetic Programming;20
5.2.3;1.2.3 Evolutionary Strategies;21
5.2.4;1.2.4 Evolutionary Programming;22
5.3;1.3 Features of Evolutionary Computation;22
5.3.1;1.3.1 Particulate Genes and Population Genetics;23
5.3.2;1.3.2 The Adaptive Code Book;24
5.3.3;1.3.3 The Genotype/Phenotype Dichotomy;25
5.4;1.4 Advantages of Evolutionary Computation;26
5.4.1;1.4.1 Conceptual Simplicity;27
5.4.2;1.4.2 Broad Applicability;27
5.4.3;1.4.3 Hybridization with Other Methods;28
5.4.4;1.4.4 Parallelism;28
5.4.5;1.4.5 Robust to Dynamic Changes;28
5.4.6;1.4.6 Solves Problems that have no Solutions;29
5.5;1.5 Applications of Evolutionary Computation;29
5.6;1.6 Summary;30
5.7;Review Questions;30
6;Genetic Algorithms;31
6.1;2.1 Introduction;31
6.2;2.2 Biological Background;32
6.2.1;2.2.1 The Cell;32
6.2.2;2.2.2 Chromosomes;32
6.2.3;2.2.3 Genetics;33
6.2.4;2.2.4 Reproduction;33
6.2.5;2.2.5 Natural Selection;35
6.3;2.3 What is Genetic Algorithm?;36
6.3.1;2.3.1 Search Space;36
6.3.2;2.3.2 Genetic Algorithms World;36
6.3.3;2.3.3 Evolution and Optimization;38
6.3.4;2.3.4 Evolution and Genetic Algorithms;39
6.4;2.4 Conventional Optimization and Search Techniques;40
6.4.1;2.4.1 Gradient-Based Local OptimizationMethod;41
6.4.2;2.4.2 Random Search;42
6.4.3;2.4.3 Stochastic Hill Climbing;43
6.4.4;2.4.4 Simulated Annealing;43
6.4.5;2.4.5 Symbolic Artificial Intelligence (AI);45
6.5;2.5 A Simple Genetic Algorithm;45
6.6;2.6 Comparison of Genetic Algorithm with Other Optimization Techniques;49
6.7;2.7 Advantages and Limitations of Genetic Algorithm;50
6.8;2.8 Applications of Genetic Algorithm;51
6.9;2.9 Summary;52
6.10;Review Questions;52
7;Terminologies and Operators of GA;54
7.1;3.1 Introduction;54
7.2;3.2 Key Elements;54
7.3;3.3 Individuals;54
7.4;3.4 Genes;55
7.5;3.5 Fitness;56
7.6;3.6 Populations;56
7.7;3.7 Data Structures;57
7.8;3.8 Search Strategies;58
7.9;3.9 Encoding;58
7.9.1;3.9.1 Binary Encoding;58
7.9.2;3.9.2 Octal Encoding;59
7.9.3;3.9.3 Hexadecimal Encoding;59
7.9.4;3.9.4 Permutation Encoding (Real Number Coding);59
7.9.5;3.9.5 Value Encoding;60
7.9.6;3.9.6 Tree Encoding;60
7.10;3.10 Breeding;61
7.10.1;3.10.1 Selection;61
7.10.2;3.10.2 Crossover (Recombination);65
7.10.3;3.10.3 Mutation;71
7.10.4;3.10.4 Replacement;72
7.11;3.11 Search Termination (Convergence Criteria);74
7.11.1;3.11.1 Best Individual;74
7.11.2;3.11.2 Worst individual;75
7.11.3;3.11.3 Sum of Fitness;75
7.11.4;3.11.4 Median Fitness;75
7.12;3.12 Why do Genetic AlgorithmsWork?;75
7.12.1;3.12.1 Building Block Hypothesis;76
7.12.2;3.12.2 A Macro-Mutation Hypothesis;77
7.12.3;3.12.3 An Adaptive Mutation Hypothesis;77
7.12.4;3.12.4 The Schema Theorem;78
7.12.5;3.12.5 Optimal Allocation of Trials;80
7.12.6;3.12.6 Implicit Parallelism;81
7.12.7;3.12.7 The No Free Lunch Theorem;83
7.13;3.13 Solution Evaluation;83
7.14;3.14 Search Refinement;84
7.15;3.15 Constraints;84
7.16;3.16 Fitness Scaling;85
7.16.1;3.16.1 Linear Scaling;85
7.16.2;3.16.2 Sigma Truncation;86
7.16.3;3.16.3 Power Law Scaling;87
7.17;3.17 Example Problems ;87
7.17.1;3.17.1 Maximizing a Function;87
7.17.2;3.17.2 Traveling Salesman Problem;91
7.18;3.18 Summary;93
7.19;Review Questions;95
7.20;Exercise Problems;96
8;Advanced Operators and Techniques in Genetic Algorithm;97
8.1;4.1 Introduction;97
8.2;4.2 Diploidy, Dominance and Abeyance;97
8.3;4.3 Multiploid;99
8.4;4.4 Inversion and Reordering;100
8.4.1;4.4.1 Partially Matched Crossover (PMX);102
8.4.2;4.4.2 Order Crossover (OX);102
8.4.3;4.4.3 Cycle Crossover (CX);103
8.5;4.5 Niche and Speciation;103
8.5.1;4.5.1 Niche and Speciation in Multimodal Problems;104
8.5.2;4.5.2 Niche and Speciation in Unimodal Problems;107
8.5.3;4.5.3 Restricted Mating;110
8.6;4.6 Few Micro-operators;111
8.6.1;4.6.1 Segregation and Translocation;111
8.6.2;4.6.2 Duplication and Deletion;111
8.6.3;4.6.3 Sexual Determination;112
8.7;4.7 Non-binary Representation;112
8.8;4.8 Multi-Objective Optimization;113
8.9;4.9 Combinatorial Optimizations;114
8.10;4.10 Knowledge Based Techniques;114
8.11;4.11 Summary;116
8.12;Review Questions;117
8.13;Exercise Problems;117
9;Classification of Genetic Algorithm;119
9.1;5.1 Introduction;119
9.2;5.2 Simple Genetic Algorithm (SGA);119
9.3;5.3 Parallel and Distributed Genetic Algorithm (PGA and DGA);120
9.3.1;5.3.1 Master-Slave Parallelization;123
9.3.2;5.3.2 Fine Grained Parallel GAs (Cellular GAs);124
9.3.3;5.3.3 Multiple-Deme Parallel GAs (Distributed GAs or Coarse Grained GAs);125
9.3.4;5.3.4 Hierarchical Parallel Algorithms;127
9.4;5.4 Hybrid Genetic Algorithm (HGA);129
9.4.1;5.4.1 Crossover;130
9.4.2;5.4.2 Initialization Heuristics;131
9.4.3;5.4.3 The RemoveSharp Algorithm;131
9.4.4;5.4.4 The LocalOpt Algorithm;133
9.5;5.5 Adaptive Genetic Algorithm (AGA);133
9.5.1;5.5.1 Initialization;134
9.5.2;5.5.2 Evaluation Function;134
9.5.3;5.5.3 Selection operator;135
9.5.4;5.5.4 Crossover operator;135
9.5.5;5.5.5 Mutation operator;136
9.6;5.6 Fast Messy Genetic Algorithm (FmGA);136
9.6.1;5.6.1 Competitive Template (CT) Generation;137
9.7;5.7 Independent Sampling Genetic Algorithm (ISGA);138
9.7.1;5.7.1 Independent Sampling Phase;139
9.7.2;5.7.2 Breeding Phase;140
9.8;5.8 Summary;141
9.9;Review Questions;142
9.10;Exercise Problems;143
10;Genetic Programming;144
10.1;6.1 Introduction;144
10.2;6.2 Comparison of GP with Other Approaches;144
10.3;6.3 Primitives of Genetic Programming;148
10.3.1;6.3.1 Genetic Operators;149
10.3.2;6.3.2 Generational Genetic Programming;149
10.3.3;6.3.3 Tree Based Genetic Programming;149
10.3.4;6.3.4 Representation of Genetic Programming;150
10.4;6.4 Attributes in Genetic Programming;154
10.5;6.5 Steps of Genetic Programming;156
10.5.1;6.5.1 Preparatory Steps of Genetic Programming;156
10.5.2;6.5.2 Executional Steps of Genetic Programming;159
10.6;6.6 Characteristics of Genetic Programming;162
10.6.1;6.6.1 What We Mean by "Human-Competitive;162
10.6.2;6.6.2 What We Mean by "High-Return";165
10.6.3;6.6.3 What We Mean by "Routine";167
10.6.4;6.6.4 What We Mean by "Machine Intelligence";167
10.7;6.7 Applications of Genetic Programming;169
10.7.1;6.7.1 Applications of Genetic Programming in Civil Engineering;169
10.8;6.8 Haploid Genetic Programming with Dominance;172
10.8.1;6.8.1 Single-Node Dominance Crossover;174
10.8.2;6.8.2 Sub-Tree Dominance Crossover;174
10.9;6.9 Summary;174
10.10;Review Questions;176
10.11;Exercise Problems;176
11;Genetic Algorithm Optimization Problems;177
11.1;7.1 Introduction;177
11.2;7.2 Fuzzy Optimization Problems;177
11.2.1;7.2.1 Fuzzy Multiobjective Optimization;178
11.2.2;7.2.2 Interactive Fuzzy Optimization Method;180
11.2.3;7.2.3 Genetic Fuzzy Systems;180
11.3;7.3 Multiobjective Reliability Design Problem;182
11.3.1;7.3.1 Network Reliability Design;182
11.3.2;7.3.2 Bicriteria Reliability Design;186
11.4;7.4 Combinatorial Optimization Problem;188
11.4.1;7.4.1 Linear Integer Model;190
11.4.2;7.4.2 Applications of Combinatorial Optimization;191
11.4.3;7.4.3 Methods;194
11.5;7.5 Scheduling Problems;199
11.5.1;7.5.1 Genetic Algorithm for Job Shop Scheduling Problems (JSSP);199
11.6;7.6 Transportation Problems;202
11.6.1;7.6.1 Genetic Algorithm in Solving Transportation Location- Allocation Problems with Euclidean Distances;203
11.6.2;7.6.2 Real-Coded Genetic Algorithm (RCGA) for Integer Linear Programming in Production- Transportation Problems with Flexible Transportation Cost;206
11.7;7.7 Network Design and Routing Problems;211
11.7.1;7.7.1 Planning of Passive Optical Networks;211
11.7.2;7.7.2 Planning of Packet Switched Networks;214
11.7.3;7.7.3 Optimal Topological Design of All Terminal Networks;215
11.8;7.8 Summary;220
11.9;Review Questions;220
11.10;Exercise Problems;221
12;Genetic Algorithm Implementation Using Matlab;222
12.1;8.1 Introduction;222
12.2;8.2 Data Structures;222
12.2.1;8.2.1 Chromosomes;223
12.2.2;8.2.2 Phenotypes;223
12.2.3;8.2.3 Objective Function Values;224
12.2.4;8.2.4 Fitness Values;224
12.2.5;8.2.5 Multiple Subpopulations;224
12.3;8.3 Toolbox Functions;225
12.4;8.4 Genetic Algorithm Graphical User Interface Toolbox;230
12.5;8.5 Solved Problems using MATLAB;235
12.6;8.6 Summary;272
12.7;Review Questions;272
12.8;Exercise Problems;273
13;Genetic Algorithm Optimization in C/C++;274
13.1;9.1 Introduction;274
13.2;9.2 Traveling Salesman Problem (TSP);274
13.3;9.3 Word Matching Problem;282
13.4;9.4 PrisonerÌs Dilemma;291
13.5;9.5 Maximize;297
13.6;9.6 Minimization a Sine Function with Constraints;303
13.6.1;9.6.1 Problem Description;304
13.7;9.7 Maximizing the Function;313
13.8;9.8 Quadratic Equation Solving;321
13.9;9.9 Summary;326
13.9.1;9.9.1 Projects;326
14;Applications of Genetic Algorithms;328
14.1;10.1 Introduction;328
14.2;10.2 Mechanical Sector ;328
14.2.1;10.2.1 Optimizing Cyclic-Steam Oil Productionwith Genetic Algorithms;328
14.2.2;10.2.2 Genetic Programming and Genetic Algorithms for Auto- tuning Mobile Robot Motion Control;331
14.3;10.3 Electrical Engineering ;335
14.3.1;10.3.1 Genetic Algorithms in Network Synthesis;335
14.3.2;10.3.2 Genetic Algorithm Tools for Control Systems Engineering;339
14.3.3;10.3.3 Genetic Algorithm Based Fuzzy Controller for Speed Control of Brushless DC Motor;345
14.4;10.4 Machine Learning ;352
14.5;10.4.1 Feature Selection in Machine learning using GA;352
14.6;10.5 Civil Engineering ;356
14.6.1;10.5.1 Genetic Algorithm as Automatic Structural Design Tool;356
14.6.2;10.5.2 Genetic Algorithm for Solving Site Layout Problem;361
14.7;10.6 Image Processing ;363
14.7.1;10.6.1 Designing Texture Filters with Genetic Algorithms;363
14.7.2;10.6.2 Genetic Algorithm Based Knowledge Acquisition on Image Processing;368
14.7.3;10.6.3 Object Localization in Images Using Genetic Algorithm;373
14.7.4;10.6.4 Problem Description;374
14.7.5;10.6.5 Image Preprocessing;375
14.7.6;10.6.6 The Proposed Genetic Algorithm Approach;376
14.8;10.7 Data Mining;378
14.8.1;10.7.1 A Genetic Algorithm for Feature Selection in Data-Mining;378
14.8.2;10.7.2 Genetic Algorithm Based Fuzzy Data Mining to Intrusion Detection;381
14.8.3;10.7.3 Selection and Partitioning of Attributes in Large-Scale Data Mining Problems Using Genetic Algorithm;390
14.9;10.8 Wireless Networks ;397
14.9.1;10.8.1 Genetic Algorithms for Topology Planningin Wireless Networks;397
14.9.2;10.8.2 Genetic Algorithm for Wireless ATM Network;398
14.10;10.9 Very Large Scale Integration (VLSI) ;406
14.10.1;10.9.1 Development of a Genetic Algorithm Techniquefor VLSI Testing;406
14.10.2;10.9.2 VLSI Macro Cell Layout Using Hybrid GA;408
14.10.3;10.9.3 Problem Description;409
14.10.4;10.9.4 Genetic Layout Optimization;410
14.11;10.10 Summary;413
15;Introduction to Particle Swarm Optimization and Ant Colony Optimization;414
15.1;11.1 Introduction;414
15.2;11.2 Particle Swarm Optimization;414
15.2.1;11.2.1 Background of Particle Swarm Optimization;415
15.2.2;11.2.2 Operation of Particle Swarm Optimization;416
15.2.3;11.2.3 Basic Flow of Particle Swarm Optimization;418
15.2.4;11.2.4 Comparison Between PSO and GA;419
15.2.5;11.2.5 Applications of PSO;421
15.3;11.3 Ant Colony Optimization;421
15.3.1;11.3.1 Biological Inspiration;421
15.3.2;11.3.2 Similarities and Differences Between Real Ants and Artificial Ants;425
15.3.3;11.3.3 Characteristics of Ant Colony Optimization;426
15.3.4;11.3.4 Ant Colony Optimization Algorithms;427
15.3.5;11.3.5 Applications of Ant Colony Optimization;433
15.4;11.4 Summary;435
15.5;Review Questions;435
15.6;Exercise Problems;435
15.7;Web Bibliography;451