Genetic Programming On the Programming of Computers by Means of Natural Selection

Complex Adaptive Systems
John H. Holland, Christopher Langton, and Stewart W. Wilson, advisors
Adaptation in Natural and Artificial Systems: An Introductory Analysis with
Applications to Biology, Control, and Artificial Intelligence, MIT Press edition
John H. Holland
Toward a Practice of Autonomous Systems: Proceedings of the First European
Conference on Artificial Life
edited by Francisco J. Varela and Paul Bourgine
Genetic Programming: On the Programming of Computers by
Means of Natural Selection
John R. Koza

Contents
Preface ix
Acknowledgments xiii
Introduction and Overview
Pervasiveness of the Problem of Program Induction
Introduction to Genetic Algorithms
The Representation Problem for Genetic Algorithms
Overview of Genetic Programming
Detailed Description of Genetic Programming
Four Introductory Examples of Genetic Programming
Amount of Processing Required to Solve a Problem
Nonrandomness of Genetic Programming
Symbolic Regression—Error-Driven Evolution
11 Control—Cost-Driven Evolution
12 Evolution of Emergent Behavior 329
13 Evolution of Subsumption 357
14 Entropy-Driven Evolution 395
15 Evolution of Strategy 419
16 Co-Evolution 429
17 Evolution of Classification 439
18 Iteration, Recursion, and Setting 459
19 Evolution of Constrained Syntactic Structures 479
20 Evolution of Building Blocks 527
21 Evolution of Hierarchies of Building Blocks 553
22 Parallelization of Genetic Programming 563
23 Ruggedness of Genetic Programming 569
24 Extraneous Variables and Functions 583
25 Operational Issues 597
26 Review of Genetic Programming 619
27 Comparison with Other Paradigms 633
28 Spontaneous Emergence of Self-Replicating and Evolutionarily Self-Improving
Computer Programs 643
29 Conclusions 695
Appendix A: Computer Implementation 699
Appendix B: Problem-Specific Part of Simple LISP Code 705
Appendix C: Kernel of the Simple LISP Code 735
Appendix D: Embellishments to the Simple LISP Code 757
Appendix E: Streamlined Version of EVAL 765
Appendix F: Editor for Simplifying S-Expressions 771
Appendix G: Testing the Simple LISP Code 777
Appendix H: Time-Saving Techniques 783
Appendix I: List of Special Symbols 787
Appendix J: List of Special Functions 789
Bibliography 791
Index 805

Introduction to Genetic Algorithms
Practical Genetic Algorithms
Genetic algorithm - Wikipedia, the free encyclopedia
Intro to Genetic Algorithms
Other Genetic Algorithm Books
Download

Genetic Programming Theory And Practice II

Edited by
Una-May O’Reilly
Massachusetts Institute of Technology
Tina Yu
Chevron Texaco Information Technology Group
Rick Riolo
University of Michigan
Bill Worzel
Genetics Squared, Inc.

Contents
Contributing Authors
Preface
Foreword
1
Genetic Programming: Theory and Practice
Una-May O’Reilly, Tina Yu, Rick Riolo and Bill Worzel
2
Discovering Financial Technical Trading Rules Using Genetic Program-
ming with Lambda Abstraction
Tina Yu, Shu-Heng Chen and Tzu-Wen Kuo
3
Using Genetic Programming in Industrial Statistical Model Building
Flor Castillo, Arthur Kordon, Jeff Sweeney and Wayne Zirk
4
Population Sizing for Genetic Programming Based On Decision-Making
Kumara Sastry, Una-May O ’Reilly and David E. Goldberg
5
Considering the Roles of Structure in Problem Solving by Computer
Jason Daida
6
Lessons Learned using Genetic Programming in a Stock Picking Context
Michael Caplan and Ying Becker
7
Favourable Biasing of Function Sets
Conor Ryan, Maarten Keijzer, and Mike Cattolico
Toward Automated Design of Industrial-Strength Analog Circuits by Means
of Genetic Programming
J. R. Koza, L. W. Jones, M. A. Keane, M. J. Streeter and S. H. Al-Sakran
9
Topological Synthesis of Robust Dynamic Systems by Sustainable Ge-
netic Programming
Jianjun Hu and Erik Goodman
10
Does Genetic Programming Inherently Adopt Structured Design Techniques?
John M. Hall and Terence Soule
11
Genetic Programming of an Algorithmic Chemistry
W. Banzhaf and C. Lasarczyk
12
ACGP: Adaptable Constrained Genetic Programming
Cezary Z. Janikow
13
Using Genetic Programming to Search for Supply Chain Reordering
Policies
Scott A. Moore and Kurt DeMaagd
14
Cartesian Genetic Programming and the Post Docking Filtering Problem
A. Beatriz Garmendia-Doval, Julian F. Miller, and S. David Morley
15
Listening to Data: Tuning a Genetic Programming System
Duncan MacLean, Eric A. Wollesen and Bill Worzel
16
Incident Detection on Highways
Daniel Howard and Simon C. Roberts
17
Pareto-Front Exploitation in Symbolic Regression
Guido F. Smits and Mark Kotanchek
18
An Evolved Antenna for Deployment on NASA’s Space Technology 5
Mission
Jason D. Lohn, Gregory S. Hornby, and Derek S. Linden
Index


Introduction to Genetic Algorithms
Practical Genetic Algorithms
Genetic algorithm - Wikipedia, the free encyclopedia
Intro to Genetic Algorithms
Other Genetic Algorithm Books
Download

Facts, Conjectures, and Improvements for Simulated Annealing

Peter Salamon
San Diego State University
San Diego, California
Paolo Sibani
University of Southern Denmark
Odense, Denmark
Richard Frost
San Diego State University
San Diego, California
Society for Industrial and Applied Mathematics
Philadelphia
SIAM

Contents
List of Figures ix
Preface xi
Acknowledgments xiii
I Overview 1
1 The Place of Simulated Annealing in the Arsenal of Global Optimization 3
2 Six Simulated Annealing Problems 7
2.1 Problem Definitions 7
2.2 Move Classes 14
3 Nomenclature 17
4 Bare-Bones Simulated Annealing 19
II Facts 23
5 Equilibrium Statistical Mechanics 25
5.1 The Number of States That Realize a Distribution 26
5.2 Derivation of the Boltzmann Distribution 29
5.3 Averages and Fluctuations 33
6 Relaxation Dynamics—Finite Markov Chains 35
6.1 Finite Markov Chains 36
6.2 Reversibility and Stationary Distributions 40
6.3 Relaxation to the Stationary Distribution 41
6.4 Equilibrium Fluctuations 43
6.4.1 The Correlation Function 44
6.4.2 Linear Response and the Decay of the Correlation Function 45
6.5 Standard Examples of the Relaxation Paradigm 47
6.5.1 Two-State System 47
6.5.2 A Folk Theorem—Arrhenius' or Kramers' Law 49
6.6 Glassy Systems 51
III Improvements and Conjectures 53
7 Ensembles 55
8 The Brick Wall Effect and Optimal Ensemble Size 57
9 The Objective Function 63
9.1 Imperfectly Known Objective 63
9.2 Implications of Noise 64
9.3 Deforming the Energy 65
9.4 Eventually Monotonic Deformations 65
10 Move Classes and Their Implementations 67
10.1 What Makes a Move Class Good? 67
10.1.1 Natural Scales 67
10.1.2 Correlation Length and Correlation Time 68
10.1.3 Relaxation Time at Finite T 69
10.1.4 Combinatorial Work 70
10.2 More Refined Move Schemes 70
10.2.1 Basin Hopping 70
10.2.2 Fast Annealing 71
10.2.3 Rejectionless Monte Carlo 72
11 Acceptance Rules 75
11.1 Tsallis Acceptance Probabilities 76
11.2 Threshold Accepting 76
11.3 Optimality of Threshold Accepting 76
12 Thermodynamic Portraits 79
12.1 Equilibrium Information 79
12.1.1 Histogram Method 81
12.2 Dynamic Information 84
12.2.1 Transition Matrix Method 84
12.3 Time-Resolved Information 86
12.A Appendix: Why Lumping Preserves the Stationary Distribution . . . . 87
13 Selecting the Schedule 89
13.1 Start and Stop Temperatures 90
13.2 Simple Schedules 90
13.2.1 The Sure-to-Get-You-There Schedule 90
13.2.2 The Exponential Schedule 91
13.2.3 Other Simple Schedules 91
13.3 Adaptive Cooling 92
13.3.1 Using the System's Scale of Time 92
13.3.2 Using the System's Scale of Energy 93
13.3.3 Using Both Energy and Time Scales 93
13.4 Nonmonotonic Schedules 96
13.5 Conclusions Regarding Schedules 97
14 Estimating the Global Minimum Energy 99
IV Toward Structure Theory and Real Understanding 103
15 Structure Theory of Complex Systems 105
15.1 The Coarse Structure of the Landscape 106
15.2 Exploring the State Space Structure: Tools and Concepts 107
15.3 The Structure of a Basin 110
15.4 Examples 111
15.A Appendix: Entropic Barriers 114
15.A.1 The Master Equation 115
15.A.2 Random Walks on Flat Landscapes 115
15.A.3 Bounds on Relaxation Times for General Graphs 116
16 What Makes Annealing Tick? 119
16.1 The Dynamics of Draining a Basin 119
16.2 Putting It Together 120
16.3 Conclusions 121
V Resources 123
17 Supplementary Materials 125
17.1 Software 125
17.1.1 Simulated Annealing from the Web 125
17.1.2 The Methods of This Book 126
17.1.3 Software Libraries 126
17.2 Energy Landscapes Database 127
Bibliography 129
Index 139

Genetic algorithm - Wikipedia, the free encyclopedia
Main page - Introduction to Genetic Algorithms

Practical Genetic Algorithms
Introduction to Genetic Algorithms
Other Genetic Algorithm Books
Download

An Introduction to Genetic Algorithms

An Introduction to Genetic Algorithms............................................................................................................1
Mitchell Melanie......................................................................................................................................1
Chapter 1: Genetic Algorithms: An Overview.................................................................................................2
Overview..................................................................................................................................................2
1.1 A BRIEF HISTORY OF EVOLUTIONARY COMPUTATION.....................................................2
1.2 THE APPEAL OF EVOLUTION.....................................................................................................4
1.3 BIOLOGICAL TERMINOLOGY.....................................................................................................5
1.4 SEARCH SPACES AND FITNESS LANDSCAPES.......................................................................6
1.5 ELEMENTS OF GENETIC ALGORITHMS...................................................................................7
Examples of Fitness Functions...................................................................................................7
GA Operators..............................................................................................................................8
1.6 A SIMPLE GENETIC ALGORITHM..............................................................................................8
1.7 GENETIC ALGORITHMS AND TRADITIONAL SEARCH METHODS..................................10
1.9 TWO BRIEF EXAMPLES..............................................................................................................12
Using GAs to Evolve Strategies for the Prisoner's Dilemma...................................................13
Hosts and Parasites: Using GAs to Evolve Sorting Networks..................................................16
1.10 HOW DO GENETIC ALGORITHMS WORK?...........................................................................21
THOUGHT EXERCISES......................................................................................................................23
COMPUTER EXERCISES...................................................................................................................24
Chapter 2: Genetic Algorithms in Problem Solving......................................................................................27
Overview................................................................................................................................................27
2.1 EVOLVING COMPUTER PROGRAMS.......................................................................................27
Evolving Lisp Programs...........................................................................................................27
Evolving Cellular Automata.....................................................................................................34
2.2 DATA ANALYSIS AND PREDICTION.......................................................................................42
Predicting Dynamical Systems.................................................................................................42
Predicting Protein Structure......................................................................................................47
2.3 EVOLVING NEURAL NETWORKS............................................................................................49
Evolving Weights in a Fixed Network.....................................................................................50
Evolving Network Architectures..............................................................................................53
Direct Encoding........................................................................................................................54
Grammatical Encoding.............................................................................................................55
Evolving a Learning Rule.........................................................................................................58
THOUGHT EXERCISES......................................................................................................................60
COMPUTER EXERCISES...................................................................................................................62
Chapter 3: Genetic Algorithms in Scientific Models.....................................................................................65
Overview................................................................................................................................................65
3.1 MODELING INTERACTIONS BETWEEN LEARNING AND EVOLUTION...........................66
The Baldwin Effect...................................................................................................................66
A Simple Model of the Baldwin Effect....................................................................................68
Evolutionary Reinforcement Learning.....................................................................................72
3.2 MODELING SEXUAL SELECTION.............................................................................................75
Simulation and Elaboration of a Mathematical Model for Sexual Selection...........................76
3.3 MODELING ECOSYSTEMS.........................................................................................................78
3.4 MEASURING EVOLUTIONARY ACTIVITY.............................................................................81
Thought Exercises..................................................................................................................................84
Computer Exercises...............................................................................................................................85
Chapter 4: Theoretical Foundations of Genetic Algorithms........................................................................87
Overview................................................................................................................................................87
4.1 SCHEMAS AND THE TWO−ARMED BANDIT PROBLEM.....................................................87
The Two−Armed Bandit Problem............................................................................................88
Sketch of a Solution..................................................................................................................89
Interpretation of the Solution....................................................................................................91
Implications for GA Performance.............................................................................................92
Deceiving a Genetic Algorithm................................................................................................93
Limitations of "Static" Schema Analysis..................................................................................93
4.2 ROYAL ROADS.............................................................................................................................94
Royal Road Functions...............................................................................................................94
Experimental Results................................................................................................................95
Steepest−ascent hill climbing (SAHC).....................................................................................96
Next−ascent hill climbing (NAHC)..........................................................................................96
Random−mutation hill climbing (RMHC)...............................................................................96
Analysis of Random−Mutation Hill Climbing.........................................................................97
Hitchhiking in the Genetic Algorithm......................................................................................98
An Idealized Genetic Algorithm...............................................................................................99
4.3 EXACT MATHEMATICAL MODELS OF SIMPLE GENETIC ALGORITHMS.....................103
Formalization of GAs.............................................................................................................103
Results of the Formalization...................................................................................................108
A Finite−Population Model....................................................................................................108
4.4 STATISTICAL−MECHANICS APPROACHES.........................................................................112
THOUGHT EXERCISES....................................................................................................................114
COMPUTER EXERCISES.................................................................................................................116
5.1 WHEN SHOULD A GENETIC ALGORITHM BE USED?........................................................116
5.2 ENCODING A PROBLEM FOR A GENETIC ALGORITHM...................................................117
Binary Encodings....................................................................................................................117
Many−Character and Real−Valued Encodings......................................................................118
Tree Encodings.......................................................................................................................118
5.3 ADAPTING THE ENCODING....................................................................................................118
Inversion.................................................................................................................................119
Evolving Crossover "Hot Spots"............................................................................................120
Messy Gas...............................................................................................................................121
5.4 SELECTION METHODS.............................................................................................................124
Fitness−Proportionate Selection with "Roulette Wheel" and "Stochastic Universal"
Sampling................................................................................................................................124
Sigma Scaling.........................................................................................................................125
Elitism.....................................................................................................................................126
Boltzmann Selection...............................................................................................................126
Rank Selection........................................................................................................................127
Tournament Selection.............................................................................................................127
Steady−State Selection...........................................................................................................128
5.5 GENETIC OPERATORS..............................................................................................................128
Crossover................................................................................................................................128
Mutation..................................................................................................................................129
Other Operators and Mating Strategies..................................................................................130
5.6 PARAMETERS FOR GENETIC ALGORITHMS.......................................................................130
THOUGHT EXERCISES....................................................................................................................132
COMPUTER EXERCISES.................................................................................................................133
Chapter 6: Conclusions and Future Directions............................................................................................135
Overview..............................................................................................................................................135
Incorporating Ecological Interactions..................................................................................................136
Incorporating New Ideas from Genetics..............................................................................................136
Incorporating Development and Learning...........................................................................................137
Adapting Encodings and Using Encodings That Permit Hierarchy and Open−Endedness.................137
Adapting Parameters............................................................................................................................137
Connections with the Mathematical Genetics Literature.....................................................................138
Extension of Statistical Mechanics Approaches..................................................................................138
Identifying and Overcoming Impediments to the Success of GAs......................................................138
Understanding the Role of Schemas in GAs........................................................................................138
Understanding the Role of Crossover..................................................................................................139
Theory of GAs With Endogenous Fitness...........................................................................................139
Appendix A: Selected General References...................................................................................................140
Appendix B: Other Resources.......................................................................................................................141
SELECTED JOURNALS PUBLISHING WORK ON GENETIC ALGORITHMS..........................141
SELECTED ANNUAL OR BIANNUAL CONFERENCES INCLUDING WORK ON
GENETIC ALGORITHMS................................................................................................................141
INTERNET MAILING LISTS, WORLD WIDE WEB SITES, AND NEWS GROUPS WITH
INFORMATION AND DISCUSSIONS ON GENETIC ALGORITHMS........................................142
Bibliography........................................................................................................................................143

Another Genetic Algorithm Books
Download

Cost Optimization of Structures

Contents
Preface xi
Acknowledgments xiii
About the Authors xv
1 Introduction 1
1.1 The Case for Cost Optimization 1
1.2 Cost Optimization of Concrete Structures 2
1.2.1 Concrete Beams and Slabs 3
1.2.2 Concrete Columns 11
1.2.3 Concrete Frame Structures 12
1.2.4 Bridge Structures 14
1.2.5 Water Tanks 16
1.2.6 Folded Plates and Shear Walls 17
1.2.7 Concrete Pipes 17
1.2.8 Concrete Tensile Members 17
1.2.9 Cost Optimization Using the Reliability Theory 18
1.2.10 Concluding Comments 20
1.3 Cost Optimization of Steel Structures 20
1.3.1 Deterministic Cost Optimization 20
1.3.2 Cost Optimization Using the Reliability Theory 31
1.3.3 Fuzzy Optimization 33
1.3.4 Concluding Comments 35
2 Evolutionary Computing and the Genetic Algorithm 37
2.1 Overview and Basic Operations 37
2.2 Coding and Decoding 39viii Contents
2.3 Basic Operations in Genetic Algorithms 40
2.4 GA with the Penalty Function Method 43
2.4.1 Problem Formulation for Axial Force (Truss)
Structures 43
2.4.2 Genetic Algorithm with the Penalty Function
Method 45
2.5 Augmented Lagrangian Method 47
2.6 GA with the Augmented Lagrangian Method 48
2.6.1 Problem Formulation for Axial Force (Truss)
Structures 48
2.6.2 Genetic Algorithm with the Augmented Lagrangian
Method 49
3 Cost Optimization of Composite Floors 53
3.1 Introduction 53
3.2 Minimum Cost Design of Composite Beams 54
3.2.1 Cost Function 54
3.2.2 Constraints 55
3.2.3 Problem Formulation as a Mixed Integer–Discrete
Nonlinear Programming Problem 61
3.3 Solution by the Floating-Point Genetic Algorithm 62
3.3.1 Binary Versus Floating-Point GA 62
3.3.2 Crossover Operation for the Floating-Point GA 62
3.3.3 Mutation Operation for the Floating-Point GA 63
3.3.4 Floating-Point GA for Cost Optimization
of Composite Floors 63
3.4 Solution by the Neural Dynamics Method 65
3.5 Counter Propagation Neural (CPN) Network for Function
Approximations 68
3.6 Examples 71
3.6.1 Example 1 71
3.6.2 Example 2 72
4 Fuzzy Genetic Algorithm for Optimization of Steel Structures 77
4.1 Introduction 77
4.2 Fuzzy Set Theory and Structural Optimization 79
4.3 Minimum Weight Design of Axially Loaded Space
Structures 82
4.4 Fuzzy Membership Functions 85
4.5 Fuzzy Augmented Lagrangian Genetic Algorithm 87Contents ix
4.6 Implementation and Examples 92
4.6.1 Example 1 93
4.6.2 Example 2 93
4.7 Conclusion 98
5 Fuzzy Discrete Multi-criteria Cost Optimization of Steel
Structures 101
5.1 Cost of a Steel Structure 101
5.2 Primary Contributing Factors to the Cost of a Steel
Structure 102
5.3 Fuzzy Discrete Multi-criteria Cost Optimization 105
5.4 Membership Functions 110
5.4.1 Membership Function for Minimum Cost 110
5.4.2 Membership Function for Minimum Weight 110
5.4.3 Membership Function for Minimum Number of
Section Types 110
5.5 Fuzzy Membership Functions for Criteria with Unequal
Imortance 112
5.6 Pareto Optimality 112
5.7 Selection of Commercially Available Discrete Shapes 114
5.8 Implementation and a Parametric Study 117
5.9 Application to High-Rise Steel Structures 118
5.9.1 Example 1 118
5.9.2 Example 2 119
5.10 Concluding Comments 123
6 Parallel Computing 125
6.1 Multiprocessor Computing Environment 125
6.2 Parallel Processing Implementation Environment 128
6.2.1 OpenMP Data Parallel Application Programming
Interface (API) 128
6.2.2 Message Passing Interface (MPI) 130
6.3 Performance Optimization of Parallel Programs 130
7 Parallel Fuzzy Genetic Algorithms for Cost Optimization of
Large Steel Structures 133
7.1 Genetic Algorithm and Parallel Processing 133
7.2 Cost Optimization of Moment-Resisting Steel Space
Structures 135
7.3 Data Parallel Fuzzy Genetic Algorithm for Optimization
of Steel Structures Using OpenMP 136
7.4 Distributed Parallel Fuzzy Genetic Algorithm for
Optimization of Steel Structures Using MPI 138
7.4.1 Processor Farming Scheme 138
7.4.2 Migration Scheme 140
7.5 Bilevel Parallel Fuzzy GA for Optimization of Steel
Structures Using OpenMP and MPI 142
7.5.1 Bilevel Parallel Fuzzy GA with the Processor
Farming Scheme 145
7.5.2 Bilevel Parallel Fuzzy GA with the Migration Scheme 146
7.6 Application to High-Rise Building Steel Structures 147
7.6.1 Example 1 147
7.6.2 Example 2 149
7.7 Parallel Processing Performance Evaluation 155
7.7.1 Data Parallel Fuzzy GA Using OpenMP 155
7.7.2 Distributed Parallel Fuzzy GA Using MPI 157
7.7.3 Bilevel Parallel Fuzzy GA Using OpenMP and MPI 160
7.8 Concluding Comments 164
8 Life-Cycle Cost Optimization of Steel Structures 165
8.1 Introduction 165
8.2 Life-Cycle Cost of a Steel Structure and the Primary
Contributing Factors 167
8.3 Formulation of the Total Life-Cycle Cost 170
8.4 Fuzzy Discrete Multi-criteria Life-Cycle Cost Optimization 171
8.5 Application to a High-Rise Building Steel Structure 174
Appendix A 177
Appendix B 181
References 185
Index 201


Another Fuzzy Logic Books
Another Genetic Algorithm Books
Another Parallel Programming Books
Download

Fusion of Neural Networks, Fuzzy Systems and Genetic Algorithms: Industrial Applications

Preface
Chapter 1—Introduction to Neural Networks, Fuzzy Systems, Genetic
Algorithms, and their Fusion
1. Knowledge-Based Information Systems
2. Artificial Neural Networks
3. Evolutionary Computing
4. Fuzzy Logic
5. Fusion
6. Summary
References
Chapter 2—A New Fuzzy-Neural Controller
1. Introduction
2. RBF Based Fuzzy System with Unsupervised Learning
2.1 Fuzzy System Based on RBF
2.2 Coding
2.3 Selection
2.4 Crossover Operator
2.5 Mutation Operator
3. Hierarchical Fuzzy-Neuro Controller Based on Skill Knowledge Database
4. Fuzzy-Neuro Controller for Cart-Pole System
5. Conclusions
References
Chapter 3—Expert Knowledge-Based Direct Frequency Converter Using
Fuzzy Logic Control
1. Introduction
2. XDFC Topology and Operation
3. Space Vector Model of the DFC
4. Expert Knowledge-Based SVM
5. XDFC Control
5.1 XDFC Control Strategy and Operation
5.2 Fuzzy Logic Controller
5.3 Load’s Line Current Control
5.4 Input’s Line Current Control
6. Results
7. Evaluation
8. Conclusion
References
Chapter 4—Design of an Electro-Hydraulic System Using Neuro-Fuzzy
Techniques
1. Introduction
2. The Fuzzy Logic System
2.1 Fuzzification
2.2 Inference Mechanism
2.3 Defuzzification
3. Fuzzy Modeling
4. The Learning Mechanism
4.1 Model Initialization
4.2 The Cluster-Based Algorithm
4.3 Illustrative Example
4.4 The Neuro-Fuzzy Algorithm
5. The Experimental System
5.1 Training Data Generation
6. Neuro-Fuzzy Modeling of the Electro-Hydraulic Actuator
7. The Neuro-Fuzzy Control System
7.1 Experimental Results
8. Conclusion
References
Chapter 5—Neural Fuzzy Based Intelligent Systems and Applications
1. Introduction
2. Advantages and Disadvantages of Fuzzy Logic and Neural Nets
2.1 Advantages of Fuzzy Logic
2.2 Disadvantages of Fuzzy Logic
2.3 Advantages of Neural Nets2.4 Disadvantages of Neural Nets
3. Capabilities of Neural Fuzzy Systems (NFS)
4. Types of Neural Fuzzy Systems
5. Descriptions of a Few Neural Fuzzy Systems
5.1 NeuFuz
5.1.1 Brief Overview
5.1.2 NeuFuz Architecture
5.1.3 Fuzzy Logic Processing
5.2 Recurrent Neural Fuzzy System (RNFS)
5.2.1 Recurrent Neural Net
5.2.2 Temporal Information and Weight Update
5.2.3 Recurrent Fuzzy Logic
5.2.4 Determining the Number of Time Delays
6. Representative Applications
6.1 Motor Control
6.1.1 Choosing the Inputs and Outputs
6.1.2 Data Collection and Training
6.1.3 Rule Evaluation and Optimization
6.1.4 Results and Comparison with the PID Approach
6.2 Toaster Control
6.3 Speech Recognition using RNFS
6.3.1 Small Vocabulary Word Recognition
6.3.2 Training and Testing
7. Conclusion
References
Chapter 6—Vehicle Routing through Simulation of Natural Processes
1. Introduction
2. Vehicle Routing Problems
3. Neural Networks
3.1 Self-Organizing Maps
3.1.1 Vehicle Routing Applications
3.1.2 The Hierarchical Deformable Net
3.2 Feedforward Models
3.2.1 Dynamic vehicle routing and dispatching
3.2.2 Feedforward Neural Network Model with Backpropagation
3.2.3 An Application for a Courier Service
4. Genetic Algorithms
4.1 Genetic clustering
4.1.1 Genetic Sectoring (GenSect)
4.1.2 Genetic Clustering with Geometric Shapes (GenClust)
4.1.3 Real-World Applications
4.2 Decoders4.3 A Nonstandard GA
5. Conclusion
Acknowledgments
References
Chapter 7—Fuzzy Logic and Neural Networks in Fault Detection
1. Introduction
2. Fault Diagnosis
2.1 Concept of Fault Diagnosis
2.2 Different Approaches for Residual Generation and Residual Evaluation
3. Fuzzy Logic in Fault Detection
3.1 A Fuzzy Filter for Residual Evaluation
3.1.1 Structure of the Fuzzy Filter
3.1.2 Supporting Algorithm for the Design of the Fuzzy Filter
3.2 Application of the Fuzzy Filter to a Wastewater Plant
3.2.1 Description of the Process
3.2.2 Design of the Fuzzy Filter for Residual Evaluation
3.2.3 Simulation Results
4. Neural Networks in Fault Detection
4.1 Neural Networks for Residual Generation
4.1.1 Radial-Basis-Function(RBF) Neural Networks
4.1.2 Recurrent Neural Networks (RNN)
4.2 Neural Networks for Residual Evaluation
4.2.1 Restricted-Coulomb-Energy (RCE) Neural Networks
4.3 Application to the Industrial Actuator Benchmark Test
4.3.1 Simulation Results for Residual Generation
4.3.2 Simulation Results for Residual Evaluation
5. Conclusions
References
Chapter 8—Application of the Neural Network and Fuzzy Logic to the
Rotating Machine Diagnosis
1. Introduction
2. Rotating Machine Diagnosis
2.1 Fault Diagnosis Technique for Rotating Machines
3. Application of Neural Networks and Fuzzy Logic for Rotating Machine Diagnosis
3.1 Fault Diagnosis Using a Neural Network
3.2 Fault Diagnosis Using Fuzzy Logic
4. Conclusion
References
Chapter 9—Fuzzy Expert Systems in ATM Networks
1. Introduction

Another Neural Network Books
Another Fuzzy Logic Books
Another Genetic Algorithm Books
Download

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

Network Models and Optimization Multiobjective Genetic Algorithm Approach

Contents
1 Multiobjective Genetic Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.1 General Structure of a Genetic Algorithm . . . . . . . . . . . . . . . . 2
1.1.2 Exploitation and Exploration . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.3 Population-based Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.4 Major Advantages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Implementation of Genetic Algorithms. . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.1 GA Vocabulary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.2 Encoding Issue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.3 Fitness Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2.4 Genetic Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2.5 Handling Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.3 Hybrid Genetic Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.3.1 Genetic Local Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.3.2 Parameter Adaptation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.4 Multiobjective Genetic Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.4.1 Basic Concepts of Multiobjective Optimizations . . . . . . . . . . 26
1.4.2 Features and Implementation of Multiobjective GA . . . . . . . . 29
1.4.3 Fitness Assignment Mechanism . . . . . . . . . . . . . . . . . . . . . . . . 30
1.4.4 Performance Measures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2 Basic Network Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
2.1.1 Shortest Path Model: Node Selection and Sequencing . . . . . . 50
2.1.2 Spanning Tree Model: Arc Selection . . . . . . . . . . . . . . . . . . . . 51
2.1.3 Maximum Flow Model: Arc Selection and Flow Assignment 52
2.1.4 Representing Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
2.1.5 Algorithms and Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
2.1.6 NP-Complete . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
2.1.7 List of NP-complete Problems in Network Design . . . . . . . . . 56
2.2 Shortest Path Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
2.2.1 Mathematical Formulation of the SPP Models . . . . . . . . . . . . 58
2.2.2 Priority-based GA for SPP Models . . . . . . . . . . . . . . . . . . . . . . 60
2.2.3 Computational Experiments and Discussions . . . . . . . . . . . . . 72
2.3 Minimum Spanning Tree Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
2.3.1 Mathematical Formulation of the MST Models . . . . . . . . . . . 83
2.3.2 PrimPred-based GA for MST Models . . . . . . . . . . . . . . . . . . . 85
2.3.3 Computational Experiments and Discussions . . . . . . . . . . . . . 96
2.4 Maximum Flow Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
2.4.1 Mathematical Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
2.4.2 Priority-based GA for MXF Model . . . . . . . . . . . . . . . . . . . . . 100
2.4.3 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
2.5 Minimum Cost Flow Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
2.5.1 Mathematical Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
2.5.2 Priority-based GA for MCF Model . . . . . . . . . . . . . . . . . . . . . 110
2.5.3 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
2.6 Bicriteria MXF/MCF Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
2.6.1 Mathematical Formulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
2.6.2 Priority-based GA for bMXF/MCF Model . . . . . . . . . . . . . . . 119
2.6.3 i-awGA for bMXF/MCF Model . . . . . . . . . . . . . . . . . . . . . . . . 123
2.6.4 Experiments and Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
2.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
3 Logistics Network Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
3.2 Basic Logistics Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
3.2.1 Mathematical Formulation of the Logistics Models . . . . . . . . 139
3.2.2 Pr¨ufer Number-based GA for the Logistics Models . . . . . . . . 146
3.2.3 Numerical Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
3.3 Location Allocation Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
3.3.1 Mathematical Formulation of the Logistics Models . . . . . . . . 156
3.3.2 Location-based GA for the Location Allocation Models . . . . 159
3.3.3 Numerical Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
3.4 Multi-stage Logistics Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
3.4.1 Mathematical Formulation of the Multi-stage Logistics . . . . 176
3.4.2 Priority-based GA for the Multi-stage Logistics . . . . . . . . . . . 185
3.4.3 Numerical Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
3.5 Flexible Logistics Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
3.5.1 Mathematical Formulation of the Flexible Logistics Model . 196
3.5.2 Direct Path-based GA for the Flexible Logistics Model . . . . 202
3.5.3 Numerical Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206
3.6 Integrated Logistics Model with Multi-time Period and Inventory . . 208
3.6.1 Mathematical Formulation of the Integrated Logistics
Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
3.6.2 Extended Priority-based GA for the Integrated Logistics
Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
3.6.3 Local Search Technique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218
3.6.4 Numerical Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221
3.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
4 Communication Network Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229
4.2 Centralized Network Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234
4.2.1 Capacitated Multipoint Network Models . . . . . . . . . . . . . . . . . 235
4.2.2 Capacitated QoS Network Model . . . . . . . . . . . . . . . . . . . . . . . 242
4.3 Backbone Network Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246
4.3.1 Pierre and Legault’s Approach . . . . . . . . . . . . . . . . . . . . . . . . . 248
4.3.2 Numerical Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252
4.3.3 Konak and Smith’s Approach . . . . . . . . . . . . . . . . . . . . . . . . . . 253
4.3.4 Numerical Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257
4.4 Reliable Network Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257
4.4.1 Reliable Backbone Network Model . . . . . . . . . . . . . . . . . . . . . 259
4.4.2 Reliable Backbone Network Model with Multiple Goals . . . 269
4.4.3 Bicriteria Reliable Network Model of LAN . . . . . . . . . . . . . . 274
4.4.4 Bi-level Network Design Model . . . . . . . . . . . . . . . . . . . . . . . . 283
4.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291
5 Advanced Planning and Scheduling Models . . . . . . . . . . . . . . . . . . . . . . . 297
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297
5.2 Job-shop Scheduling Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303
5.2.1 Mathematical Formulation of JSP . . . . . . . . . . . . . . . . . . . . . . 304
5.2.2 Conventional Heuristics for JSP . . . . . . . . . . . . . . . . . . . . . . . . 305
5.2.3 Genetic Representations for JSP . . . . . . . . . . . . . . . . . . . . . . . . 316
5.2.4 Gen-Tsujimura-Kubota’s Approach . . . . . . . . . . . . . . . . . . . . . 325
5.2.5 Cheng-Gen-Tsujimura’s Approach . . . . . . . . . . . . . . . . . . . . . . 326
5.2.6 Gonc¸alves-Magalhacs-Resende’s Approach . . . . . . . . . . . . . . 330
5.2.7 Experiment on Benchmark Problems . . . . . . . . . . . . . . . . . . . . 335
5.3 Flexible Job-shop Scheduling Model . . . . . . . . . . . . . . . . . . . . . . . . . . 337
5.3.1 Mathematical Formulation of fJSP . . . . . . . . . . . . . . . . . . . . . . 338
5.3.2 Genetic Representations for fJSP . . . . . . . . . . . . . . . . . . . . . . . 340
5.3.3 Multistage Operation-based GA for fJSP . . . . . . . . . . . . . . . . 344
5.3.4 Experiment on Benchmark Problems . . . . . . . . . . . . . . . . . . . . 353
5.4 Integrated Operation Sequence and Resource Selection Model . . . . . 355
5.4.1 Mathematical Formulation of iOS/RS . . . . . . . . . . . . . . . . . . . 358
5.4.2 Multistage Operation-based GA for iOS/RS . . . . . . . . . . . . . . 363
5.4.3 Experiment and Discussions . . . . . . . . . . . . . . . . . . . . . . . . . . . 372
5.5 Integrated Scheduling Model with Multi-plant . . . . . . . . . . . . . . . . . . 376
5.5.1 Integrated Data Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379
5.5.2 Mathematical Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381
5.5.3 Multistage Operation-based GA . . . . . . . . . . . . . . . . . . . . . . . . 383
5.5.4 Numerical Experiment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 389
5.6 Manufacturing and Logistics Model with Pickup and Delivery . . . . . 395
5.6.1 Mathematical Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395
5.6.2 Multiobjective Hybrid Genetic Algorithm . . . . . . . . . . . . . . . . 399
5.6.3 Numerical Experiment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407
5.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 412
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 412
6 Project Scheduling Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 419
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 419
6.2 Resource-constrained Project Scheduling Model . . . . . . . . . . . . . . . . . 421
6.2.1 Mathematical Formulation of rc-PSP Models . . . . . . . . . . . . . 422
6.2.2 Hybrid GA for rc-PSP Models . . . . . . . . . . . . . . . . . . . . . . . . . 426
6.2.3 Computational Experiments and Discussions . . . . . . . . . . . . . 434
6.3 Resource-constrained Multiple Project Scheduling Model . . . . . . . . . 438
6.3.1 Mathematical Formulation of rc-mPSP Models . . . . . . . . . . . 440
6.3.2 Hybrid GA for rc-mPSP Models . . . . . . . . . . . . . . . . . . . . . . . . 444
6.3.3 Computational Experiments and Discussions . . . . . . . . . . . . . 451
6.4 Resource-constrained Project Scheduling Model with Multiple
Modes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457
6.4.1 Mathematical Formulation of rc-PSP/mM Models . . . . . . . . . 457
6.4.2 Adaptive Hybrid GA for rc-PSP/mM Models . . . . . . . . . . . . . 461
6.4.3 Numerical Experiment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 470
6.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 472
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 472
7 Assembly Line Balancing Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 477
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 477
7.2 Simple Assembly Line Balancing Model . . . . . . . . . . . . . . . . . . . . . . . 480
7.2.1 Mathematical Formulation of sALB Models . . . . . . . . . . . . . . 480
7.2.2 Priority-based GA for sALB Models . . . . . . . . . . . . . . . . . . . . 484
7.2.3 Computational Experiments and Discussions . . . . . . . . . . . . . 492
7.3 U-shaped Assembly Line Balancing Model . . . . . . . . . . . . . . . . . . . . . 493
7.3.1 Mathematical Formulation of uALB Models . . . . . . . . . . . . . 495
7.3.2 Priority-based GA for uALB Models . . . . . . . . . . . . . . . . . . . . 499
7.3.3 Computational Experiments and Discussions . . . . . . . . . . . . . 505
7.4 Robotic Assembly Line Balancing Model . . . . . . . . . . . . . . . . . . . . . . 505
7.4.1 Mathematical Formulation of rALB Models . . . . . . . . . . . . . . 509
7.4.2 Hybrid GA for rALB Models . . . . . . . . . . . . . . . . . . . . . . . . . . 512
7.4.3 Computational Experiments and Discussions . . . . . . . . . . . . . 523
7.5 Mixed-model Assembly Line Balancing Model . . . . . . . . . . . . . . . . . 526
7.5.2 Hybrid GA for mALB Models . . . . . . . . . . . . . . . . . . . . . . . . . 532
7.5.3 Rekiek and Delchambre’s Approach . . . . . . . . . . . . . . . . . . . . 542
7.5.4 Ozmehmet Tasan and Tunali’s Approach . . . . . . . . . . . . . . . . 543
7.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 546
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 546
8 Tasks Scheduling Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 551
8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 551
8.1.1 Hard Real-time Task Scheduling . . . . . . . . . . . . . . . . . . . . . . . 553
8.1.2 Soft Real-time Task Scheduling . . . . . . . . . . . . . . . . . . . . . . . . 557
8.2 Continuous Task Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 562
8.2.1 Continuous Task Scheduling Model on Uniprocessor
8.2.2 Continuous Task Scheduling Model on Multiprocessor
System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 575
8.3 Real-time Task Scheduling in Homogeneous Multiprocessor . . . . . . 583
8.3.1 Soft Real-time Task Scheduling Problem (sr-TSP) and
Mathematical Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 584
8.3.2 Multiobjective GA for srTSP . . . . . . . . . . . . . . . . . . . . . . . . . . 586
8.3.3 Numerical Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 592
8.4 Real-time Task Scheduling in Heterogeneous Multiprocessor
8.4.1 Soft Real-time Task Scheduling Problem (sr-TSP) and
Mathematical Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 595
8.4.2 SA-based Hybrid GA Approach . . . . . . . . . . . . . . . . . . . . . . . . 597
8.4.3 Numerical Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 601
8.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 602
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 604
9 Advanced Network Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 607
9.1 Airline Fleet Assignment Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 607
9.1.1 Fleet Assignment Model with Connection Network . . . . . . . . 613
9.1.2 Fleet Assignment Model with Time-space Network . . . . . . . . 624
9.2 Container Terminal Network Model . . . . . . . . . . . . . . . . . . . . . . . . . . . 636
9.2.1 Berth Allocation Planning Model . . . . . . . . . . . . . . . . . . . . . . . 639
9.2.2 Multi-stage Decision-based GA . . . . . . . . . . . . . . . . . . . . . . . . 643
9.2.3 Numerical Experiment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 646
9.3 AGV Dispatching Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 651
9.3.1 Network Modeling and Mathematical Formulation . . . . . . . . 652
9.3.2 Random Key-based GA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 658
9.3.3 Numerical Experiment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 664
9.4 Car Navigation Routing Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 666
9.4.1 Data Analyzing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 667
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 682
Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 687
9.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 681
9.4.2 Mathematical Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 670
9.4.3 Improved Fixed Length-based GA . . . . . . . . . . . . . . . . . . . . . . 672
9.4.4 Numerical Experiment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 677


Another Genetic Algorithm Books
Download