Suchen und Finden
Introduction to Genetic Algorithms
von: S.N. Sivanandam, S. N. Deepa
Springer-Verlag, 2007
ISBN: 9783540731900 , 453 Seiten
Format: PDF, OL
Kopierschutz: Wasserzeichen
Preis: 149,79 EUR
Preface
5
About the Book
7
1 Organization of the Book
7
2 Salient Features of the Book
8
Acknowledgement
10
Contents
11
Evolutionary Computation
18
1.1 Introduction
18
1.2 The Historical Development of EC
19
1.2.1 Genetic Algorithms
19
1.2.2 Genetic Programming
20
1.2.3 Evolutionary Strategies
21
1.2.4 Evolutionary Programming
22
1.3 Features of Evolutionary Computation
22
1.3.1 Particulate Genes and Population Genetics
23
1.3.2 The Adaptive Code Book
24
1.3.3 The Genotype/Phenotype Dichotomy
25
1.4 Advantages of Evolutionary Computation
26
1.4.1 Conceptual Simplicity
27
1.4.2 Broad Applicability
27
1.4.3 Hybridization with Other Methods
28
1.4.4 Parallelism
28
1.4.5 Robust to Dynamic Changes
28
1.4.6 Solves Problems that have no Solutions
29
1.5 Applications of Evolutionary Computation
29
1.6 Summary
30
Review Questions
30
Genetic Algorithms
31
2.1 Introduction
31
2.2 Biological Background
32
2.2.1 The Cell
32
2.2.2 Chromosomes
32
2.2.3 Genetics
33
2.2.4 Reproduction
33
2.2.5 Natural Selection
35
2.3 What is Genetic Algorithm?
36
2.3.1 Search Space
36
2.3.2 Genetic Algorithms World
36
2.3.3 Evolution and Optimization
38
2.3.4 Evolution and Genetic Algorithms
39
2.4 Conventional Optimization and Search Techniques
40
2.4.1 Gradient-Based Local OptimizationMethod
41
2.4.2 Random Search
42
2.4.3 Stochastic Hill Climbing
43
2.4.4 Simulated Annealing
43
2.4.5 Symbolic Artificial Intelligence (AI)
45
2.5 A Simple Genetic Algorithm
45
2.6 Comparison of Genetic Algorithm with Other Optimization Techniques
49
2.7 Advantages and Limitations of Genetic Algorithm
50
2.8 Applications of Genetic Algorithm
51
2.9 Summary
52
Review Questions
52
Terminologies and Operators of GA
54
3.1 Introduction
54
3.2 Key Elements
54
3.3 Individuals
54
3.4 Genes
55
3.5 Fitness
56
3.6 Populations
56
3.7 Data Structures
57
3.8 Search Strategies
58
3.9 Encoding
58
3.9.1 Binary Encoding
58
3.9.2 Octal Encoding
59
3.9.3 Hexadecimal Encoding
59
3.9.4 Permutation Encoding (Real Number Coding)
59
3.9.5 Value Encoding
60
3.9.6 Tree Encoding
60
3.10 Breeding
61
3.10.1 Selection
61
3.10.2 Crossover (Recombination)
65
3.10.3 Mutation
71
3.10.4 Replacement
72
3.11 Search Termination (Convergence Criteria)
74
3.11.1 Best Individual
74
3.11.2 Worst individual
75
3.11.3 Sum of Fitness
75
3.11.4 Median Fitness
75
3.12 Why do Genetic AlgorithmsWork?
75
3.12.1 Building Block Hypothesis
76
3.12.2 A Macro-Mutation Hypothesis
77
3.12.3 An Adaptive Mutation Hypothesis
77
3.12.4 The Schema Theorem
78
3.12.5 Optimal Allocation of Trials
80
3.12.6 Implicit Parallelism
81
3.12.7 The No Free Lunch Theorem
83
3.13 Solution Evaluation
83
3.14 Search Refinement
84
3.15 Constraints
84
3.16 Fitness Scaling
85
3.16.1 Linear Scaling
85
3.16.2 Sigma Truncation
86
3.16.3 Power Law Scaling
87
3.17 Example Problems
87
3.17.1 Maximizing a Function
87
3.17.2 Traveling Salesman Problem
91
3.18 Summary
93
Review Questions
95
Exercise Problems
96
Advanced Operators and Techniques in Genetic Algorithm
97
4.1 Introduction
97
4.2 Diploidy, Dominance and Abeyance
97
4.3 Multiploid
99
4.4 Inversion and Reordering
100
4.4.1 Partially Matched Crossover (PMX)
102
4.4.2 Order Crossover (OX)
102
4.4.3 Cycle Crossover (CX)
103
4.5 Niche and Speciation
103
4.5.1 Niche and Speciation in Multimodal Problems
104
4.5.2 Niche and Speciation in Unimodal Problems
107
4.5.3 Restricted Mating
110
4.6 Few Micro-operators
111
4.6.1 Segregation and Translocation
111
4.6.2 Duplication and Deletion
111
4.6.3 Sexual Determination
112
4.7 Non-binary Representation
112
4.8 Multi-Objective Optimization
113
4.9 Combinatorial Optimizations
114
4.10 Knowledge Based Techniques
114
4.11 Summary
116
Review Questions
117
Exercise Problems
117
Classification of Genetic Algorithm
119
5.1 Introduction
119
5.2 Simple Genetic Algorithm (SGA)
119
5.3 Parallel and Distributed Genetic Algorithm (PGA and DGA)
120
5.3.1 Master-Slave Parallelization
123
5.3.2 Fine Grained Parallel GAs (Cellular GAs)
124
5.3.3 Multiple-Deme Parallel GAs (Distributed GAs or Coarse Grained GAs)
125
5.3.4 Hierarchical Parallel Algorithms
127
5.4 Hybrid Genetic Algorithm (HGA)
129
5.4.1 Crossover
130
5.4.2 Initialization Heuristics
131
5.4.3 The RemoveSharp Algorithm
131
5.4.4 The LocalOpt Algorithm
133
5.5 Adaptive Genetic Algorithm (AGA)
133
5.5.1 Initialization
134
5.5.2 Evaluation Function
134
5.5.3 Selection operator
135
5.5.4 Crossover operator
135
5.5.5 Mutation operator
136
5.6 Fast Messy Genetic Algorithm (FmGA)
136
5.6.1 Competitive Template (CT) Generation
137
5.7 Independent Sampling Genetic Algorithm (ISGA)
138
5.7.1 Independent Sampling Phase
139
5.7.2 Breeding Phase
140
5.8 Summary
141
Review Questions
142
Exercise Problems
143
Genetic Programming
144
6.1 Introduction
144
6.2 Comparison of GP with Other Approaches
144
6.3 Primitives of Genetic Programming
148
6.3.1 Genetic Operators
149
6.3.2 Generational Genetic Programming
149
6.3.3 Tree Based Genetic Programming
149
6.3.4 Representation of Genetic Programming
150
6.4 Attributes in Genetic Programming
154
6.5 Steps of Genetic Programming
156
6.5.1 Preparatory Steps of Genetic Programming
156
6.5.2 Executional Steps of Genetic Programming
159
6.6 Characteristics of Genetic Programming
162
6.6.1 What We Mean by "Human-Competitive
162
6.6.2 What We Mean by "High-Return"
165
6.6.3 What We Mean by "Routine"
167
6.6.4 What We Mean by "Machine Intelligence"
167
6.7 Applications of Genetic Programming
169
6.7.1 Applications of Genetic Programming in Civil Engineering
169
6.8 Haploid Genetic Programming with Dominance
172
6.8.1 Single-Node Dominance Crossover
174
6.8.2 Sub-Tree Dominance Crossover
174
6.9 Summary
174
Review Questions
176
Exercise Problems
176
Genetic Algorithm Optimization Problems
177
7.1 Introduction
177
7.2 Fuzzy Optimization Problems
177
7.2.1 Fuzzy Multiobjective Optimization
178
7.2.2 Interactive Fuzzy Optimization Method
180
7.2.3 Genetic Fuzzy Systems
180
7.3 Multiobjective Reliability Design Problem
182
7.3.1 Network Reliability Design
182
7.3.2 Bicriteria Reliability Design
186
7.4 Combinatorial Optimization Problem
188
7.4.1 Linear Integer Model
190
7.4.2 Applications of Combinatorial Optimization
191
7.4.3 Methods
194
7.5 Scheduling Problems
199
7.5.1 Genetic Algorithm for Job Shop Scheduling Problems (JSSP)
199
7.6 Transportation Problems
202
7.6.1 Genetic Algorithm in Solving Transportation Location- Allocation Problems with Euclidean Distances
203
7.6.2 Real-Coded Genetic Algorithm (RCGA) for Integer Linear Programming in Production- Transportation Problems with Flexible Transportation Cost
206
7.7 Network Design and Routing Problems
211
7.7.1 Planning of Passive Optical Networks
211
7.7.2 Planning of Packet Switched Networks
214
7.7.3 Optimal Topological Design of All Terminal Networks
215
7.8 Summary
220
Review Questions
220
Exercise Problems
221
Genetic Algorithm Implementation Using Matlab
222
8.1 Introduction
222
8.2 Data Structures
222
8.2.1 Chromosomes
223
8.2.2 Phenotypes
223
8.2.3 Objective Function Values
224
8.2.4 Fitness Values
224
8.2.5 Multiple Subpopulations
224
8.3 Toolbox Functions
225
8.4 Genetic Algorithm Graphical User Interface Toolbox
230
8.5 Solved Problems using MATLAB
235
8.6 Summary
272
Review Questions
272
Exercise Problems
273
Genetic Algorithm Optimization in C/C++
274
9.1 Introduction
274
9.2 Traveling Salesman Problem (TSP)
274
9.3 Word Matching Problem
282
9.4 PrisonerÌs Dilemma
291
9.5 Maximize
297
9.6 Minimization a Sine Function with Constraints
303
9.6.1 Problem Description
304
9.7 Maximizing the Function
313
9.8 Quadratic Equation Solving
321
9.9 Summary
326
9.9.1 Projects
326
Applications of Genetic Algorithms
328
10.1 Introduction
328
10.2 Mechanical Sector
328
10.2.1 Optimizing Cyclic-Steam Oil Productionwith Genetic Algorithms
328
10.2.2 Genetic Programming and Genetic Algorithms for Auto- tuning Mobile Robot Motion Control
331
10.3 Electrical Engineering
335
10.3.1 Genetic Algorithms in Network Synthesis
335
10.3.2 Genetic Algorithm Tools for Control Systems Engineering
339
10.3.3 Genetic Algorithm Based Fuzzy Controller for Speed Control of Brushless DC Motor
345
10.4 Machine Learning
352
10.4.1 Feature Selection in Machine learning using GA
352
10.5 Civil Engineering
356
10.5.1 Genetic Algorithm as Automatic Structural Design Tool
356
10.5.2 Genetic Algorithm for Solving Site Layout Problem
361
10.6 Image Processing
363
10.6.1 Designing Texture Filters with Genetic Algorithms
363
10.6.2 Genetic Algorithm Based Knowledge Acquisition on Image Processing
368
10.6.3 Object Localization in Images Using Genetic Algorithm
373
10.6.4 Problem Description
374
10.6.5 Image Preprocessing
375
10.6.6 The Proposed Genetic Algorithm Approach
376
10.7 Data Mining
378
10.7.1 A Genetic Algorithm for Feature Selection in Data-Mining
378
10.7.2 Genetic Algorithm Based Fuzzy Data Mining to Intrusion Detection
381
10.7.3 Selection and Partitioning of Attributes in Large-Scale Data Mining Problems Using Genetic Algorithm
390
10.8 Wireless Networks
397
10.8.1 Genetic Algorithms for Topology Planningin Wireless Networks
397
10.8.2 Genetic Algorithm for Wireless ATM Network
398
10.9 Very Large Scale Integration (VLSI)
406
10.9.1 Development of a Genetic Algorithm Techniquefor VLSI Testing
406
10.9.2 VLSI Macro Cell Layout Using Hybrid GA
408
10.9.3 Problem Description
409
10.9.4 Genetic Layout Optimization
410
10.10 Summary
413
Introduction to Particle Swarm Optimization and Ant Colony Optimization
414
11.1 Introduction
414
11.2 Particle Swarm Optimization
414
11.2.1 Background of Particle Swarm Optimization
415
11.2.2 Operation of Particle Swarm Optimization
416
11.2.3 Basic Flow of Particle Swarm Optimization
418
11.2.4 Comparison Between PSO and GA
419
11.2.5 Applications of PSO
421
11.3 Ant Colony Optimization
421
11.3.1 Biological Inspiration
421
11.3.2 Similarities and Differences Between Real Ants and Artificial Ants
425
11.3.3 Characteristics of Ant Colony Optimization
426
11.3.4 Ant Colony Optimization Algorithms
427
11.3.5 Applications of Ant Colony Optimization
433
11.4 Summary
435
Review Questions
435
Exercise Problems
435
Web Bibliography
451
Alle Preise verstehen sich inklusive der gesetzlichen MwSt.