Introduction to Evolutionary Algorithms / Edition 1

Introduction to Evolutionary Algorithms / Edition 1

by Xinjie Yu, Mitsuo Gen
     
 

ISBN-10: 184996128X

ISBN-13: 9781849961288

Pub. Date: 06/25/2010

Publisher: Springer London

Evolutionary algorithms are becoming increasingly attractive across various disciplines, such as operations research, computer science, industrial engineering, electrical engineering, social science and economics. Introduction to Evolutionary Algorithms presents an insightful, comprehensive, and up-to-date treatment of evolutionary algorithms. It covers such hot

…  See more details below

Overview

Evolutionary algorithms are becoming increasingly attractive across various disciplines, such as operations research, computer science, industrial engineering, electrical engineering, social science and economics. Introduction to Evolutionary Algorithms presents an insightful, comprehensive, and up-to-date treatment of evolutionary algorithms. It covers such hot topics as:

genetic algorithms

differential evolution

swarm intelligence, and

artificial immune systems

The reader is introduced to a range of applications, as Introduction to Evolutionary Algorithms demonstrates how to model real world problems, how to encode and decode individuals, and how to design effective search operators according to the chromosome structures with examples of constraint optimization, multiobjective optimization, combinatorial optimization, and supervised/unsupervised learning. This emphasis on practical applications will benefit all students, whether they choose to continue their academic career or to enter a particular industry.

Introduction to Evolutionary Algorithms is intended as a textbook or self-study material for both advanced undergraduates and graduate students. Additional features such as recommended further reading and ideas for research projects combine to form an accessible and interesting pedagogical approach to this widely used discipline.

The Decision Engineering series focuses on the foundations and applications of tools and techniques related to decision engineering, and identifies their relevance in 'engineering' decisions. The series provides an aid to practising professionals and applied researchers in the development of tools for informed operational and business decision making, within industry, by utilising distributed organisational knowledge.

Read More

Product Details

ISBN-13:
9781849961288
Publisher:
Springer London
Publication date:
06/25/2010
Series:
Decision Engineering Series
Edition description:
2010
Pages:
422
Product dimensions:
6.40(w) x 9.30(h) x 1.20(d)

Table of Contents

Part I Evolutionary Algorithms

1 Introduction 3

1.1 What Are Evolutionary Algorithms Used For? 3

1.2 What Are Evolutionary Algorithms? 6

Suggestions for Further Reading 8

References 9

2 Simple Evolutionary Algorithms 11

2.1 Introductory Remarks 11

2.2 Simple Genetic Algorithm 14

2.2.1 An Optimization Problem 14

2.2.2 Representation and Evaluation 15

2.2.3 Initialization 17

2.2.4 Selection 18

2.2.5 Variation Operators 20

2.2.6 Simple Genetic Algorithm Infrastructure 22

2.3 Evolution Strategy and Evolutionary Programming 25

2.3.1 Evolution Strategy 25

2.3.2 Evolutionary Programming 27

2.4 Direction-based Search 28

2.4.1 Deterministic Direction-based Search 28

2.4.2 Random Direction-based Search 32

2.5 Summary 35

Suggestions for Further Reading 36

Exercises and Potential Research Projects 37

References 37

3 Advanced Evolutionary Algorithms 39

3.1 Problems We Face 39

3.2 Encoding and Operators 40

3.2.1 Binary Code and Related Operators 42

3.2.2 Real Code and Related Operators 45

3.2.3 Other Topics on Code and Operators 62

3.3 Selection Methods 64

3.3.1 Dilemmas for Selection Methods 64

3.3.2 Proportional Selection 67

3.3.3 Fitness Scaling and Transferral 68

3.3.4 Ranking 72

3.3.5 Tournament Selection 74

3.4 Replacement and Stop Criteria 75

3.4.1 Replacement 75

3.4.2 Stop Criteria 80

3.5 Parameter Control 82

3.5.1 Strategy Parameter Setting 82

3.5.2 Examples of Variation Operator Control 86

3.5.3 Examples of popsize Control 96

3.6 Performance Evaluation of Evolutionary Algorithms 101

3.6.1 General Discussion on Performance Evaluation 101

3.6.2 Performance Evaluation and Comparison 105

3.7 Brief Introduction to Other Topics 116

3.7.1 Coevolution 116

3.7.2 Memetic Algorithms 117

3.7.3 Hyper-heuristics 119

3.7.4 Handling Uncertain Environments 121

3.8 Summary 123

Suggestions for Further Reading 124

Exercises and Potential Research Projects 126

References 127

Part II Dealing with Complicated Problems

4 Constrained Optimization 135

4.1 Introduction 135

4.1.1 Constrained Optimization 135

4.1.2 Constrained Optimization Evolutionary Algorithms 137

4.2 Feasibility Maintenance 138

4.2.1 Genetic Algorithm for Numerical Optimization of Constrained Problems 138

4.2.2 Homomorphous Mappings 140

4.3 Penalty Function 143

4.3.1 Static Penalty Function 144

4.3.2 Dynamic Penalty Function 145

4.3.3 Adaptive Penalty Function 145

4.3.4 Self-adaptive Penalty Function 150

4.4 Separation of Constraint Violation and Objective Value 150

4.4.1 Constrained Optimization Evolutionary Algorithms Based on Rank 151

4.4.2 Simple Multimembered Evolution Strategy 155

4.4.3 α Constrained Method 156

4.5 Performance Evaluation of Constrained Optimization Evolutionary Algorithms 159

4.5.1 Benchmark Problems 159

4.5.2 Performance Indices 160

4.6 Summary 160

Suggestions for Further Reading 161

Exercises and Potential Research Projects 162

References 163

5 Multimodal Optimization 165

5.1 Problems We Face 165

5.1.1 Multimodal Problems 165

5.1.2 Niche, Species, and Speciation 167

5.2 Sequential Niche 169

5.3 Fitness Sharing 171

5.3.1 Standard Fitness Sharing 171

5.3.2 Clearing Procedure 173

5.3.3 Clustering for Speciation 174

5.3.4 Dynamic Niche Sharing 175

5.3.5 Coevolutionary Shared Niching 179

5.4 Crowding 180

5.4.1 Deterministic Crowding 180

5.4.2 Restricted Tournament Selection 181

5.4.3 Species Conserving Genetic Algorithm 182

5.5 Performance Indices for Multimodal Optimization 183

5.6 Application Example 185

5.7 Summary 187

Suggestions for Further Reading 188

Exercises and Potential Research Projects 189

References 190

6 Multiobjective Optimization 193

6.1 Introduction 193

6.1.1 Problems We Face 193

6.1.2 Terminologies 194

6.1.3 Why Are Evolutionary Algorithms Good at Multiobjective Optimization Problems? 196

6.2 Preference-based Approaches 198

6.2.1 Weight Sum Method 198

6.2.2 Compromise Method 200

6.2.3 Goal Programming Method 201

6.3 Vector-evaluated Genetic Algorithm 202

6.4 Considerations for Designing Multiobjective Evolutionary Algorithms 203

6.4.1 Quality 204

6.4.2 Distribution 206

6.5 Classical Multiobjective Evolutionary Algorithms 209

6.5.1 Nondominated Sorting Genetic Algorithm II 209

6.5.2 Strength Pareto Evolutionary Algorithm 2 and Pareto Envelope-based Selection Algorithm 211

6.5.3 Pareto Archived Evolution Strategy 215

6.5.4 Micro-GA for Multiobjective Optimization 216

6.6 Cutting Edges of Multiobjective Evolutionary Algorithms 217

6.6.1 Expanding Single-objective Evolutionary Algorithms into Multiobjective Optimization Problems 217

6.6.2 Archive Maintenance 221

6.6.3 Rebirth from the Ashes 228

6.7 Performance Evaluation of Multiobjective Evolutionary Algorithms 234

6.7.1 Benchmark Problems 234

6.7.2 Performance Indices 236

6.8 Objectives vs. Constraints 247

6.8.1 Handling Constraints in Multiobjective Optimization Problems 247

6.8.2 Multiobjective Evolutionary Algorithms for Constraint Handling 248

6.9 Application Example 253

6.10 Summary 256

Suggestions for Further Reading 256

Exercises and Potential Research Projects 258

References 259

7 Combinatorial Optimization 263

7.1 Introduction 263

7.1.1 Combinatorial Optimization 263

7.1.2 NP-complete and NP-hard Problems 266

7.1.3 Evolutionary Algorithms for Combinatorial Optimization 267

7.2 Knapsack Problem 270

7.2.1 Problem Description 270

7.2.2 Evolutionary Algorithms for Knapsack Problem 271

7.3 Traveling Salesman Problem 276

7.3.1 Problem Description 276

7.3.2 Heuristic Methods for Traveling Salesman Problem 278

7.3.3 Evolutionary Algorithm Code Schemes for Traveling Salesman Problem 281

7.3.4 Variation Operators for Permutation Code 285

7.4 Job-shop Scheduling Problem 299

7.4.1 Problem Description 300

7.4.2 Heuristic Methods for Job-shop Scheduling 305

7.4.3 Evolutionary Algorithm Code Schemes for Job-shop Scheduling 310

7.5 Summary 318

Suggestions for Further Reading 319

Exercises and Potential Research Projects 320

References 321

Part III Brief Introduction to Other Evolutionary Algorithms

8 Swarm Intelligence 327

8.1 Introduction 327

8.2 Ant Colony Optimization 329

8.2.1 Rationale Behind Ant Colony Optimization 329

8.2.2 Discrete Ant Colony Optimization 330

8.2.3 Continuous Ant Colony Optimization 336

8.3 Particle Swarm Optimization 339

8.3.1 Organic Particle Swarm Optimization 340

8.3.2 Neighbor Structure and Related Extensions 342

8.3.3 Extensions from Organic Particle Swarm Optimization 347

8.4 Summary 348

Suggestions for Further Reading 349

Exercises and Potential Research Projects 350

References 351

9 Artificial Immune Systems 355

9.1 Introduction 355

9.2 Artificial Immune System Based on Clonal Selection 357

9.2.1 Clonal Selection 357

9.2.2 Clonal Selection Algorithm 359

9.2.3 Artificial Immune System for Multiobjective Optimization Problems 361

9.3 Artificial Immune System Based on Immune Network 364

9.3.1 Immune Network Theory 364

9.3.2 Continuous Immune Network 366

9.3.3 Discrete Immune Network 368

9.4 Artificial Immune System Based on Negative Selection 370

9.4.1 File Protection by Negative Selection 371

9.4.2 Intrusion Detection by Negative Selection 373

9.5 Summary 375

Suggestions for Further Reading 376

Exercises and Potential Research Projects 377

References 377

10 Genetic Programming 381

10.1 Introduction to Genetic Programming 381

10.1.1 The Difference Between Genetic Programming and Genetic Algorithms 381

10.1.2 Genetic Programming for Curve Fitting 382

10.2 Other Code Methods for Genetic Programming 390

10.2.1 Gene Expression Programming 390

10.2.2 Grammatical Evolution for Solving Differential Equations 392

10.3 Example of Genetic Programming for Knowledge Discovery 395

10.4 Summary 397

Suggestions for Further Reading 398

Exercises and Potential Research Projects 399

References 400

A Benchmark Problems 403

References 409

Index 411

Read More

Customer Reviews

Average Review:

Write a Review

and post it to your social network

     

Most Helpful Customer Reviews

See all customer reviews >