Preface	5
	About the Book	6
	Salient Features	6
	Organization of the Book	6
	About the Authors	7
	Acknowledgement	9
	Contents	10
	Introduction to Evolutionary Computation	21
	1.1 Introduction	21
	1.2 Brief History	22
	1.3 Biological and Artificial Evolution	23
	1.3.1 EC Terminology	24
	1.3.2 Natural Evolution – The Inspiration from Biology	24
	1.4 Darwinian Evolution	25
	1.4.1 The Premise	26
	1.4.2 Natural Selection	26
	1.4.3 Slowly but Surely Process	27
	1.4.4 A Theory in Crisis	27
	1.4.5 Darwin’s Theory of Evolution	28
	1.5 Genetics	29
	1.5.1 The Molecular Basis for Inheritance	29
	1.6 Evolutionary Computation	30
	1.7 Important Paradigms in Evolutionary Computation	32
	1.7.1 Genetic Algorithms	32
	1.7.2 Genetic Programming	34
	1.7.3 Evolutionary Programming	35
	1.7.4 Evolution Strategies	37
	1.8 Global Optimization	40
	1.9 Techniques of Global Optimization	41
	1.9.1 Branch and Bound	41
	1.9.2 Clustering Methods	42
	1.9.3 Hybrid Methods	42
	1.9.4 Simulated Annealing	46
	1.9.5 Statistical Global Optimization Algorithms	47
	1.9.6 Tabu Search	47
	1.9.7 Multi Objective Optimization	48
	Summary	50
	Review Questions	50
	Principles of Evolutionary Algorithms	51
	2.1 Introduction	51
	2.2 Structure of Evolutionary Algorithms	52
	2.2.1 Illustration	54
	2.3 Components of Evolutionary Algorithms	56
	2.4 Representation	56
	2.5 Evaluation/Fitness Function	57
	2.6 Population Initialization	57
	2.7 Selection	58
	2.7.1 Rank Based Fitness Assignment	59
	2.7.2 Multi–objective Ranking	61
	2.7.3 Roulette Wheel selection	63
	2.7.4 Stochastic universal sampling	64
	2.7.5 Local Selection	65
	2.7.6 Truncation Selection	67
	2.7.7 Comparison of Selection Properties	69
	2.7.8 MATLAB Code Snippet for Selection	71
	2.8 Recombination	72
	2.8.1 Discrete Recombination	72
	2.8.2 Real Valued Recombination	73
	2.8.3 Binary Valued Recombination (Crossover)	77
	2.9 Mutation	81
	2.9.1 Real Valued Mutation	82
	2.9.2 Binary mutation	83
	2.9.3 Real Valued Mutation with Adaptation of Step Sizes	84
	2.9.4 Advanced Mutation	85
	2.9.5 Other Types of Mutation	86
	2.9.6 MATLAB Code Snippet for Mutation	87
	2.10 Reinsertion	87
	2.10.1 Global Reinsertion	87
	2.10.2 Local Reinsertion	88
	2.11 Reproduction Operator	89
	2.11.1 MATLAB Code Snippet for Reproduction	90
	2.12 Categorization of Parallel Evolutionary Algorithms	90
	2.13 Advantages of Evolutionary Algorithms	92
	2.14 Multi-objective Evolutionary Algorithms	93
	2.15 Critical Issues in Designing an Evolutionary Algorithm	94
	Summary	95
	Review Questions	95
	Genetic Algorithms with Matlab	96
	3.1 Introduction	96
	3.2 History of Genetic Algorithm	99
	3.3 Genetic Algorithm Definition	100
	3.4 Models of Evolution	101
	3.5 Operational Functionality of Genetic Algorithms	102
	3.6 Genetic Algorithms – An Example	103
	3.7 Genetic Representation	105
	3.8 Genetic Algorithm Parameters	105
	3.8.1 Multi-Parameters	105
	3.8.2 Concatenated, Multi-Parameter, Mapped, Fixed- Point Coding	106
	3.8.3 Exploitable Techniques	106
	3.9 Schema Theorem and Theoretical Background	107
	3.9.1 Building Block Hypothesis	108
	3.9.2 Working of Genetic Algorithms	109
	3.9.3 Sets and Subsets	110
	3.9.4 The Dynamics of a Schema	111
	3.9.5 Compensating for Destructive Effects	112
	3.9.6 Mathematical Models	113
	3.9.7 Illustrations based on Schema Theorem	116
	3.10 Solving a Problem: Genotype and Fitness	119
	3.10.1 Non-Conventional Genotypes	121
	3.11 Advanced Operators in GA	123
	3.11.1 Inversion and Reordering	123
	3.11.2 Epistasis	123
	3.11.3 Deception	123
	3.11.4 Mutation and Naive Evolution	124
	3.11.5 Niche and Speciation	124
	3.11.6 Restricted Mating	124
	3.11.7 Diploidy and Dominance	125
	3.12 Important Issues in the Implementation of a GA	125
	3.13 Comparison of GA with Other Methods	126
	3.13.1 Neural Nets	126
	3.13.2 Random Search	126
	3.13.3 Gradient Methods	126
	3.13.4 Iterated Search	127
	3.13.5 Simulated Annealing	127
	3.14 Types of Genetic Algorithm	128
	3.14.1 Sequential GA	128
	3.14.2 Parallel GA	129
	3.14.3 Hybrid GA	131
	3.14.4 Adaptive GA	132
	3.14.5 Integrated Adaptive GA (IAGA)	135
	3.14.6 Messy GA	136
	3.14.7 Generational GA (GGA)	139
	3.14.8 Steady State GA (SSGA)	140
	3.15 Advantages of GA	141
	3.16 Matlab Examples of Genetic Algorithms 3.16.1 Genetic Algorithm Operations Implemented in MATLAB	142
	Reproduction	142
	Selection	142
	Crossover	143
	Fitness Function	144
	Mutation	144
	3.16.2 Illustration 1 – Maximizing the given Function	145
	3.16.3 Illustration 2 – Optimization of a Multidimensional Non- Convex Function	151
	3.16.4 Illustration 3 – Traveling Salesman Problem	155
	3.16.5 Illustration 4 – GA using Float Representation	162
	3.16.6 Illustration 5 – Constrained Problem	177
	3.16.7 Illustration 6 – Maximum of any given Function	180
	Summary	186
	Review Questions	188
	Genetic Programming Concepts	189
	4.1 Introduction	189
	4.2 A Brief History of Genetic Programming	193
	4.3 The Lisp Programming Language	194
	4.4 Operations of Genetic Programming	195
	4.4.1 Creating an Individual	195
	4.4.2 Creating a Random Population	196
	4.4.3 Fitness Test	197
	4.4.4 Functions and Terminals	197
	4.4.5 The Genetic Operations	197
	4.4.6 Selection Functions	198
	4.4.7 Crossover Operation	200
	4.4.8 Mutation	201
	4.4.9 User Decisions	201
	4.5 An Illustration	203
	4.6 The GP Paradigm in Machine Learning	204
	4.7 Preparatory Steps of Genetic Programming	206
	4.7.1 The Terminal Set	206
	4.7.2 The Function Set	207
	4.7.3 The Fitness Function	207
	4.7.4 The Algorithm Control Parameters	207
	4.7.5 The Termination Criterion	208
	–	208
	4.8 Flow – Chart of Genetic Programming	209
	4.9 Type Constraints in Genetic Programming	211
	4.10 Enhanced Versions of Genetic Programming	213
	4.10.1 Meta-genetic Programming	214
	4.10.2 Cartesian Genetic Programming	219
	4.10.3 Strongly Typed Genetic Programming (STGP)	227
	4.11 Advantages of using Genetic Programming	235
	Summary	235
	Review Questions	236
	Parallel Genetic Algorithms	237
	5.1 Introduction	237
	5.2 Parallel and Distributed Computer Architectures: An Overview	238
	5.3 Classification of PGA	241
	5.4 Parallel Population Models for Genetic Algorithms	242
	5.4.1 Classification of Global Population Models	243
	5.4.2 Global Population Models	244
	5.4.3 Regional Population Models	244
	5.4.4 Local Population Models	246
	5.5 Models Based on Distribution of Population	248
	5.5.1 Centralized PGA	248
	5.5.2 Distributed PGA	249
	5.6 PGA Models Based on Implementation	250
	5.6.1 Master–slave/Farming PGA	250
	5.6.2 Island PGA	252
	5.6.3 Cellular PGA	254
	5.7 PGA Models Based on Parallelism	256
	5.7.1 Global with Migration (coarse-grained)	256
	5.7.2 Global with Migration (fine-grained)	256
	5.8 Communication Topologies	258
	5.9 Hierarchical Parallel Algorithms	259
	5.10 Object Orientation (OO) and Parallelization	261
	5.11 Recent Advancements	262
	5.12 Advantages of Parallel Genetic Algorithms	264
	Summary	265
	Review Questions	265
	Applications of Evolutionary Algorithms	267
	6.1 A Fingerprint Recognizer using Fuzzy Evolutionary Programming 6.1.1 Introduction	267
	6.1.2 Fingerprint Characteristics	268
	6.1.3 Fingerprint Recognition using EA	273
	6.1.4 Experimental Results	275
	6.1.5 Conclusion and Future Work	276
	6.2 An Evolutionary Programming Algorithm for Automatic Engineering Design 6.2.1 Introduction	276
	6.2.2 EPSOC: An Evolutionary Programming Algorithm using Self- Organized Criticality	278
	6.2.3 Case Studies	279
	6.2.4 Results of Numerical Experiments	281
	6.2.5 Conclusion	283
	6.3 Evolutionary Computing as a Tool for Grammar Development 6.3.1 Introduction	283
	6.3.2 Natural Language Grammar Development	284
	6.3.3 Grammar Evolution	285
	6.3.4 GRAEL-1: Probabilistic Grammar Optimization	286
	6.3.5 GRAEL-2: Grammar Rule Discovery	290
	6.3.6 GRAEL-3: Unsupervised Grammar Induction	292
	6.3.7 Concluding Remarks	293
	6.4 Waveform Synthesis using Evolutionary Computation 6.4.1 Introduction	294
	6.4.2 Evolutionary Manipulation of Waveforms	294
	Crossover, Mutation and Fitness Evaluation	295
	6.4.3 Conclusion and Results	297
	Appendix: Mathematical Model	298
	6.5 Scheduling Earth Observing Satellites with Evolutionary Algorithms 6.5.1 Introduction	300
	6.5.2 EOS Scheduling by Evolutionary Algorithms and other Optimization Techniques	302
	6.5.3 Results	304
	6.5.4 Future Work	306
	6.6 An Evolutionary Computation Approach to Scenario-based Risk- return Portfolio Optimization for General Risk Measures 6.6.1 Introduction	307
	6.6.2 Portfolio Optimization	307
	6.6.3 Evolutionary Portfolio Optimization	309
	6.6.4 Numerical Results	310
	6.6.5 Results	311
	6.6.6 Conclusion	314
	Applications of Genetic Algorithms	315
	7.1 Assembly and Disassembly Planning by Using Fuzzy Logic & Genetic Algorithms	315
	7.1.1 Research Background	316
	7.1.2 Proposed Approach and Case Studies	321
	7.1.3 Discussion of Results	323
	7.1.4 Concluding Remarks	326
	7.2 Automatic Synthesis of Active Electronic Networks Using Genetic Algorithms	326
	7.2.1 Active Network Synthesis Using GAs	327
	7.2.2 Example of an Automatically-Synthesized Network	329
	7.2.3 Limitations of Automatic Network Synthesis	331
	7.2.4 Concluding Remarks	331
	7.3 A Genetic Algorithm for Mixed Macro and Standard Cell Placement	332
	7.3.1 Genetic Algorithm for Placement	332
	7.3.2 Experimental Results	336
	7.4 Knowledge Acquisition on Image Procssing Based on Genetic Algorithms	337
	7.4.1 Methods	338
	7.4.2 Results and Discussions	343
	7.4.3 Concluding Remarks	345
	7.5 Map Segmentation by Colour Cube Genetic K-Mean Clustering	345
	7.5.1 Genetic Clustering in Image Segmentation	346
	7.5.2 K-Means Clustering Model	347
	7.5.3 Genetic Implementation	347
	7.5.4 Results and Conclusions	348
	7.6 Genetic Algorithm-Based Performance Analysis of Self- Excited Induction Generator	349
	7.6.1 Modelling of SEIG System	350
	7.6.2 Genetic Algorithm Optimization	352
	7.6.3 Results and Discussion	353
	7.6.4 Concluding Remarks	355
	7.7 Feature Selection for Anns Using Genetic Algorithms in Condition Monitoring	356
	7.7.1 Signal Acquisition	358
	7.7.2 Neural Networks	358
	7.7.3 Genetic Algorithms	359
	7.7.4 Training and Simulation	359
	7.7.5 Results	360
	7.7.6 Concluding Remarks	361
	7.8 A Genetic Algorithm Approach to Scheduling Communications for a Class of Parallel Space-Time Adaptive Processing Algorithms	361
	7.8.1 Overview of Parallel STAP	362
	7.8.2 Genetic Algorithm Methodology	363
	7.8.3 Numerical Results	365
	7.8.4 Concluding Remarks	366
	7.9 A Multi-Objective Genetic Algorithm for on-Chip Real-Time Adaptation of a Multi- Carrier Based Telecommunications Receiver	367
	7.9.1 MC-CDMA Receiver	368
	7.9.2 Multi-objective Genetic Algorithm (GA)	368
	7.9.3 Results	371
	7.9.4 Concluding Remarks	373
	7.10 A VLSI Implementation of an Analog Neural Network Suited for Genetic Algorithms	373
	7.10.1 Realization of the Neural Network	375
	7.10.2 Implementation of the Genetic Training Algorithm	380
	7.10.3 Experimental Results	382
	7.10.4 Concluding Remarks	384
	Genetic Programming Applications	385
	8.1 GP-Robocode: Using Genetic Programming to Evolve Robocode Players	385
	8.1.1 Robocode Rules	386
	8.1.2 Evolving Robocode Strategies using Genetic Programming	387
	8.1.3 Results	392
	8.1.4 Concluding Remarks	393
	8.2 Prediction of Biochemical Reactions using Genetic Programming	393
	8.2.1 Method and Results	394
	8.2.2 Discussion	395
	8.3 Application of Genetic Programming to High Energy Physics Event Selection	395
	8.3.1 Genetic Programming	396
	8.3.2 Combining Genetic Programming with High Energy Physics Data	398
	8.3.3 Selecting Genetic Programming Parameters	403
	8.3.4 Testing Genetic Programming on	407
	8.3.5 Concluding Remarks	412
	8.4 Using Genetic Programming to Generate Protocol Adaptors for Interprocess Communication	413
	8.4.1 Prerequisites of Interprocess Communication	415
	8.4.2 Specifying Protocols	415
	8.4.3 Evolving Protocols	418
	8.4.4 The Experiment	421
	8.4.5 Concluding Remarks	423
	8.5 Improving Technical Analysis Predictions: An Application of Genetic Programming	424
	8.5.1 Background	425
	8.5.2 FGP for Predication in DJIA Index	426
	8.5.3 Concluding Remarks	429
	8.6 Genetic Programming within Civil Engineering	430
	8.6.1 Generational Genetic Programming	430
	8.6.2 Applications of Genetic Programming in Civil Engineering	431
	8.6.3 Application of Genetic Programming in Structural Engineering	431
	8.6.4 Structural Encoding	431
	8.6.5 An Example of Structural Optimization	432
	8.6.6 10 Member Planar Truss	433
	8.6.7 Controller-GP Tableau	433
	8.6.8 Model	434
	8.6.9 View-Visualisation	435
	8.6.10 Concluding Remarks	437
	8.7 Chemical Process Controller Design using Genetic Programming	438
	8.7.1 Dynamic Reference Control Problem	438
	8.7.2 ARX Process Description	441
	8.7.3 CSTR (Continuous Stirred Tank Reactor) Process Description	441
	8.7.4 GP Problem Formulation	443
	8.7.5 GP Configuration and Implementation Aspects	444
	8.7.6 Results	446
	8.7.7 Concluding Remarks	448
	8.8 Trading Applications of Genetic Programming	449
	8.8.1 Application: Forecasting or Prediction	451
	8.8.2 Application: Finding Causal Relationships	452
	8.8.3 Application: Building Trading Rules	452
	8.8.4 Concluding Remarks	453
	8.9 Artificial Neural Network Development by Means of Genetic Programming with Graph Codification	453
	8.9.1 State of the Art	453
	8.9.2 Model	456
	8.9.3 Problems to be Solved	459
	8.9.4 Results and Comparison with Other Methods	459
	8.9.5 Concluding Remarks	461
	Applications of Parallel Genetic Algorithm	462
	9.1 Timetabling Problem 9.1.1 Introduction	462
	9.1.2 Applying Genetic Algorithms to Timetabling	463
	9.1.3 A Parallel Algorithm	467
	9.1.4 Results	469
	9.1.5 Conclusion	470
	9.2 Assembling DNA Fragments with a Distributed Genetic Algorithm 9.2.1 Introduction	470
	9.2.2 The DNA Fragment Assembly Problem	471
	9.2.3 DNA Sequencing Process	472
	9.2.4 DNA Fragment Assembly Using the Sequential GA	474
	9.2.5 Implementation Details	475
	9.2.6 DNA Fragment Assembly Problem using the Parallel GA	477
	9.2.7 Experimental Results	479
	Conclusions	485
	9.3 Investigating Parallel Genetic Algorithms on Job Shop Scheduling Problems 9.3.1 Introduction	486
	9.3.2 Job Shop Scheduling Problem	487
	9.3.3 Genetic Representation and Specific Operators	488
	9.3.4 Parallel Genetic Algorithms for JSSP	490
	9.3.5 Computational Results	492
	The Effect of Parallelizing GAs	492
	9.3.6 Comparison of PGA Models	494
	9.4 Parallel Genetic Algorithm for Graph Coloring Problem 9.4.1 Introduction	496
	Migration Model of Parallel Genetic Algorithm	496
	9.4.2 Genetic Operators for GCP	497
	Sum-product Partition Crossover	497
	9.4.3 Experimental Verification	501
	9.4.4 Conclusion	503
	9.5 Robust and Distributed Genetic Algorithm for Ordering Problems 9.5.1 Introduction	503
	9.5.2 Ordering Problems	504
	9.5.3 Traveling Salesman Problem	505
	9.5.4 Distributed Genetic Algorithm	508
	Results for Hamiltonian Cycle TSP	516
	Results for Oliver’s Hamiltonian Cycle TSP	517
	Conclusion	519
	Appendix – A Glossary	520
	A	520
	B	520
	C	521
	D	522
	E	523
	F	525
	G	525
	H	527
	I	527
	L	527
	M	528
	N	528
	O	529
	P	530
	R	530
	S	531
	T	532
	V	533
	Appendix – B Abbreviations	534
	Appendix – C Research Projects	537
	C.1 Evolutionary Simulation-based Validation	537
	C.2 Automatic Generation of Validation Stimuli for Application- specific Processors	537
	C.3 Dynamic Prediction ofWeb Requests	538
	C.4 Analog Genetic Encoding for the Evolution of Circuits and Networks	538
	C.5 An Evolutionary Algorithm for Global Optimization Based on Level- set Evolution and Latin Squares	538
	C.6 Imperfect Evolutionary Systems	539
	C.7 A Runtime Analysis of Evolutionary Algorithms for Constrained Optimization Problems	539
	C.8 Classification with Ant Colony Optimization	540
	C.9 Multiple Choices and Reputation in Multiagent Interactions	540
	C.10 Coarse-grained Dynamics for Generalized Recombination	541
	C.11 An Evolutionary Algorithm-based Approach to Automated Design of Analog and RF Circuits Using Adaptive Normalized Cost Functions	541
	C.12 An Investigation on Noisy Environments in Evolutionary Multi- objective Optimization	542
	C.13 Interactive Evolutionary Computation-based Hearing Aid Fitting	543
	C.14 Evolutionary Development of Hierarchical Learning Structures	543
	C.15 Knowledge Interaction with Genetic Programming in Mechatronic Systems Design Using Bond Graphs	544
	C.16 A Distributed Evolutionary Classifier for Knowledge Discovery in Data Mining	544
	C.17 Evolutionary Feature Synthesis for Object Recognition	544
	C.18 Accelerating Evolutionary Algorithms with Gaussian Process Fitness Function Models	545
	C.19 A Constraint-based Genetic Algorithm Approach for Mining Classification Rules	545
	C.20 An Evolutionary Algorithm for Solving Nonlinear Bilevel Programming Based on a New Constraint- handling Scheme	546
	C.21 Evolutionary Fuzzy Neural Networks for Hybrid Financial Prediction	546
	C.22 Genetic Recurrent Fuzzy System by Coevolutionary Computation with Divide- and- Conquer Technique	547
	C.23 Knowledge-based Fast Evaluation for Evolutionary Learning	547
	C.24 A Comparative Study of Three Evolutionary Algorithms Incorporating Different Amounts of Domain Knowledge for Node Covering Problem	548
	Appendix – D MATLAB Toolboxes	549
	D.1 Genetic Algorithm and Direct Search Toolbox	549
	D.2 Genetic and Evolutionary Algorithm Toolbox	550
	D.3 Genetic Algorithm Toolbox	551
	D.4 Genetic Programming Toolbox for MATLAB	552
	Appendix – E Commercial Software Packages	553
	E.1 ActiveGA	553
	E.2 EnGENEer	553
	E.3 EvoFrame	554
	E.4 REALizer	555
	E.5 Evolver	555
	E.6 FlexTool	555
	E.7 GAME	556
	E.8 GeneHunter	556
	E.9 Generator	556
	E.10 Genetic Server and Genetic Library	557
	E.11 MicroGA	558
	E.12 Omega	558
	E.13 OOGA	558
	E.14 OptiGA	559
	E.15 PC-Beagle	559
	E.16 XpertRule GenAsys	559
	E.17 XYpe	559
	E.18 Evolution Machine	560
	E.19 Evolutionary Objects	560
	E.20 GAC, GAL	560
	E.21 GAGA	560
	E.22 GAGS	561
	E.23 GAlib	561
	E.24 GAWorkbench	561
	E.25 Genesis	561
	E.26 Genie	562
	E.27 XGenetic	562
	Appendix – F GA Source Codes in ‘C’ Language	563
	F.1 A “Hello World” Genetic Algorithm Example	563
	F.2 Test Function Using sin and cos	568
	F.3 Using Matlab to Plot Data Generated by C Language	573
	Appendix – G EC Class/ Code Libraries and Software Kits	575
	G.1 EC Class/Code Libraries	575
	ANNEvolve	575
	daga	576
	dgpf	576
	Ease	576
	EO	576
	FORTRAN GA	577
	GAlib: Matthew’s Genetic Algorithms Library	577
	GALOPPS	577
	GAS	578
	GAUL	578
	GECO	579
	Genetic	579
	GPdata	579
	gpjpp Genetic Programming in Java	579
	jaga	580
	patched lil-gp	580
	Lithos	580
	Open BEAGLE	581
	PGAPack	581
	PIPE	581
	pygene	582
	Sugal	582
	G.2 EC Software Kits/Applications	582
	ADATE	582
	esep & xesep	583
	Corewars	583
	Grany-3	583
	JCASim	584
	JGProg	584
	Bibliography	585