Genetic and Evolutionary Computation - GECCO 2003: Genetic and Evolutionary Computation Conference, Chicago, IL, USA, July 12-16, 2003, Proceedings, Part I (Lecture Notes in Computer Science, 2723)

Genetic and Evolutionary Computation GECCO 2003
Preface
Organization
Table of Contents
Swarms in Dynamic Environments
	1   Introduction
	2   Background
	3   The General Dynamic Search Problem
	4   PSO and CPSO Algorithms
	5   Experiment Design
	6   Results and Analysis
	7   Conclusions
	References
The Effect of Natural Selection on Phylogeny Reconstruction Algorithms
	1   Introduction
	2   Methods
		2.1   The Avida Platform [5]
		2.2   Natural Selection and Avida
		2.3   Determining Correctness of a Phylogeny Reconstruction: The Four Taxa Case
		2.4   Generation of Avida Data
		2.5   Generation of Random Data
		2.6   Two Phylogeny Reconstruction Techniques (NJ, MP)
		2.7    Data Collection
	3   Results and Discussions
		3.1.   Natural Selection and Its Effect on Genome Sequences
		3.2   Natural Selection and Its Effect on Phylogeny Reconstruction
		3.3   Natural Selection via Location Probability Distributions
	4   Future Work
AntClust: Ant Clustering and Web Usage Mining
	Introduction
	The AntClust Algorithm
		Principles of the Chemical Recognition System of Ants
		The Artificial Ants Model
	AntClust Parameters Settings
		Performance Measure
		How Many Meetings?
		How Many Iterations to Learn the Template?
		The Nest Deletion Method
	Experiments and Results
		K-Means and AntClass
		Data Sets and Experimental Protocol
		Results with Artificial and Real Data Sets
	AntClust for Web Usage Mining
		Web Session Data
		Results
	Conclusion and Perspectives
A Non-dominated Sorting Particle Swarm Optimizer for Multiobjective Optimization
	Introduction
	Modifying PSO for Better Dominance Comparison
	Non-dominated Sorting PSO
		Selection Pressure towards $P^*$
		Parameter-Free Niching Methods to Maintain a Diverse $Q$
		NSPSO Algorithm
	Performance Metrics
	Experiments
	Results and Discussion
	Conclusion
The Influence of Run-Time Limits on Choosing Ant System Parameters
	Introduction
	Example Problem
	Algorithm Description
	Influence of Local Search
		Experimental Results
		Probabilistic Local Search
	ACO Specific Parameters
	Conclusions and Future Work
		Future Work
Emergence of Collective Behavior in Evolving Populations of Flying Agents
	Introduction
	{sc SwarmEvolve 1.0}
	Emergence of Collective Behavior in {sc SwarmEvolve 1.0}
	{sc SwarmEvolve 2.0}
	Emergence of Collective Behavior in {sc SwarmEvolve 2.0}
	Conclusions and Future Work
On Role of Implicit Interaction and Explicit Communications in Emergence of Social Behavior Continuous Predators-Prey Pursuit Problem
	1   Introduction
	2   The Problem and the Agents Architecture
		2.1   Instance of Predator Prey Pursuit Problem
		2.2   Architecture of the Agents
		3   Algorithmic Paradigm Employed to Evolve Predator Agents
		3.1   Strongly-Typed Genetic Programming with Exception Handling
		3.2   Main Attributes of STGPE
	4    Empirical Results
	Conclusion
	References
Demonstrating the Evolution of Complex Genetic Representations: An Evolution of Artificial Plants
	1 Introduction
	2 A Genotype Model and 2nd-T ype Mutations
	3 Evolving Plants
	4 Conclusions
Sexual Selection of Co-operation
	1 Introduction and Background
	2 Experimental Setup
	3 Results and Analysis
	4 Conclusion
Optimization Using Particle Swarms with Near Neighbor Interactions
	1 Introduction
	2 FDR-PSO Algorithm
	3 Experimental Settings and Benchmark Problems
	4 Results and Discussion
	5 Conclusions
Revisiting Elitism in Ant Colony Optimization
	Introduction
	Ant System (AS)
		Algorithm
		Discussion
	Ant System Local Best Tour (AS-LBT)
		Algorithm
		Experimentation and Results
			Parameters and Settings
			Results
	Analysis
	Discussion and Future Work
	Conclusions
	References
A New Approach to Improve Particle Swarm Optimization
	1   Introduction
	2   The Ways to Determine the Inertia Weight
	3   Experimental Studies
	4   Results and Discussions
	5   Conclusions
	References
Clustering and Dynamic Data Visualization with Artificial Flying Insect
	Introduction
	Principle
	Conclusion
Ant Colony Programming for Approximation Problems*
	Introduction
	Ant Colony Programming for Approximation Problems
	Test Results
	Conclusions
Long-Term Competition for Light in Plant Simulation
	1   Introduction
	2   Plant Modeling
	3   Conclusion
	References
Using Ants to Attack a Classical Cipher
	Introduction
	Cryptanalysis of Transposition Ciphers
	Ants for Cryptanalysis
Comparison of Genetic Algorithm and Particle Swarm Optimizer When Evolving a Recurrent Neural Network
	Background
	Experiment and Results
	Conclusions and Future Work
Adaptation and Ruggedness in an Evolvability Landscape
Study Diploid System by a Hamiltonian Cycle Problem Algorithm
	Acknowledgments. The authors are very grateful to Prof. John Holland for invaluable encouragement and discussions.
A Possible Mechanism of Repressing Cheating Mutants in Myxobacteria
Tour Jeté, Pirouette: Dance Choreographing by Computers
	1   Introduction
Multiobjective Optimization Using Ideas from the Clonal Selection Principle
	Introduction
	The Immune System
	Previous Work
	The Proposed Approach
		Secondary Memory
	Experiments
	Conclusions and Future Work
A Hybrid Immune Algorithm with Information Gain for the Graph Coloring Problem
	Introduction
	Immune Algorithms
		Termination Condition by Information Gain
		Local Search
	Parameters Tuning by Information Gain
		B Cell\'s Mean Life, $tau _B$
		Duplication Parameter Dup
		Dup and $tau _B$
		Neighborhood\'s Radius R, d and Dup
	Results
	Conclusions
MILA – Multilevel Immune Learning Algorithm
	1   Introduction
	2   Multilevel Immune Learning Algorithm (MILA)
	Application of MILA to Anomaly Detection Problems
	4   Experiments
		4.1   Data Sets
		4.2   Performance Measures
		4.3   Experimental Results
	5   New Features of MILA
	6   Conclusions
	Acknowledgement. This work is supported by the Defense Advanced Research Projects Agency (no. F30602-00-2-0514). The authors would like to thank the source of the datasets: Keogh, E. & Folias, T. (2002). The UCR Time Series Data Mining Archive [http://www.cs.ucr.edu/~eamonn/TSDMA/index.html]. Riverside CA. Univer-sity of California ΠComputer Science & Engineering Department.
	References
The Effect of Binary Matching Rules in Negative Selection
	Introduction
	The Negative Selection Algorithm
		Binary Matching Rules in Negative Selection Algorithm
	Analyzing the Shape of Binary Matching Rules
	Comparing the Performance of Binary Matching Rules
		Experiments with the First Data Set
		Experiments with the Second Data Set
	Conclusions
Immune Inspired Somatic Contiguous Hypermutation for Function Optimisation
	Introduction
	Hybrid Genetic Algorithms
	Artificial Immune Systems
		An Immune Algorithm for Optimisation
	The B-Cell Algorithm
	Results
		Overview of Results
		Why Does the BCA Have Fewer Evaluations?
		Differences between HGA, BCA, and CLONALG
	Conclusions and Future Work
A Scalable Artificial Immune System Model for Dynamic Unsupervised Learning
	Introduction
	Artificial Immune System Models
	Proposed Artificial Immune System Model
		A Dynamic Artificial B-Cell Model Based on Robust Weights: The D-W-B-Cell Model
		Dynamic Stimulation and Suppression
		Organization and Compression of the Immune Network
		Effect of the Network Compression on Interaction Terms
		Cloning in the Dynamic Immune System
		Learning New Antigens and Relation to Outlier Detection
		Proposed Scalable Immune Learning Algorithm for Clustering Evolving Data
		Comparison to Other Immune Based Clustering Techniques
	Experimental Results
	Conclusion
Developing an Immunity to Spam
	Introduction
	The Immune System
		The Acquired Immune System
	Spam as the Common Cold
	Building a Defence
		Layers Revisited
		Regular Expressions as Antibodies
		Weights as Memory
		Mutations?
	Prototype Implementation
		Generation
		Application
		Culling
	Results
		Initial Parameters and Data
		Output
	Conclusions
		Future Work
A Novel Immune Anomaly Detection Technique Based on Negative Selection
	Introduction
	AIS Architecture
	Experimental Results
	onclusions
	References
Visualization of Topic Distribution Based on Immune Network Model
	Introduction
	Examples of Extracted Topic Stream
	Conclusion
Spatial Formal Immune Network
	References
Focusing versus Intransitivity Geometrical Aspects of Co-evolution
	Introduction
	Orders and Co-evolution
		Poset Decomposition
		Applications to Co-evolution
		Discussion
	Experiments
		The Numbers Game
		Algorithms and Setup
		Results
	Conclusion
Representation Development from Pareto-Coevolution
	Introduction
	Structural versus Functional Modularity
	Coevolution of Modules and Assemblies
	Module Evaluation: Assemblies Provide Objectives
		Objectives from Pareto-Coevolution
		Correspondence between Pareto-Coevolution and Functional Modularity
		Practical Issues in Module Evaluation
	The DevRep Algorithm
	Test Problems
		Hierarchical Test Problems
		Pattern Generation
	Experimental Results
	Discussion
	Conclusions
Learning the Ideal Evaluation Function
	Evaluation in Coevolution
		An Ideal Evaluation Function
		Coevolution: Interactions as a Basis for Evaluation
	Principled Evaluation in Coevolution
		Approximating the Complete Evaluation Set
	An Algorithm for Pareto-Coevolution
	Test Problems and Experimental Setup
	Experimental Results
	Conclusions
A Game-Theoretic Memory Mechanism for Coevolution
	Introduction
	Game Theory Fundamentals
	Additional Concepts
	Memory Methods and Solution Concepts
	Construction and Operation of Nash Memory
		Genreal Framework and Instantiation
		Initialization and First Update
		Testing N
		Updating N and M
	Intransitive Number GameDefinition
		Definition
		Game Properties
	Experiments
		Methods
		Results: Nash Memory
		Results: Best of Generation and Dominance Tournament
		Results: Bootstrapping with the Nash Memory
	Conclusion
The Paradox of the Plankton: Oscillations and Chaos in Multispecies Evolution
	Introduction and Background
		Resource Sharing
	Oscillations in Traditional Models of Resource Sharing
		Two-Species Oscillations
		Non-monotonic Convergence with Three Species
	Phytoplankton Models of Resource Sharing
		Differential Competition
		The Law of the Minimum
		Five Species and Chaos
		Discussion
	Conclusions and Future Work
Exploring the Explorative Advantage of the Cooperative Coevolutionary (1+1) EA
	Introduction
	Definitions and Framework
	Linear Functions
	A Function Class with Tunable Advantage for the CC (1+1) EA
	Conclusion
PalmPrints: A Novel Co-evolutionary Algorithm for Clustering Finger Images
	1 Introduction
	2 Feature Extraction
		2.1 Geometric Features
		2.2 Statistical Features
	3 Co-evolution in Dynamic Clustering and Feature Selection
		3.1 Chromosomal Representation
		3.2 Crossover and Mutation, Generally
		3.3 Selection and Generation of Future Generations
		3.4 Fitness Function
		3.5 Convergence Testing
		3.6 Implementation Results
	4 Conclusions
	References
Coevolution and Linear Genetic Programming for Visual Learning
	1   Introduction
	2   Related Work and Contributions
	3   Coevolutionary Construction of Feature Extraction Procedures
	4   Representation of Feature Extraction Procedures
	5   Architecture of the Recognition System
	6   Experimental Results
	7   Conclusions
	Acknowledgements. This research was supported by the grant F33615-99-C-1440. The contents of the information do not necessarily reflect the position or policy of the U. S. Government. The first author is supported by the Polish State Committee for Scientific Research, research grant no. 8T11F 006 19. We would like to thank the authors of software packages: ECJ [7] and WEKA [16] for making their software publicly available.
	References
Finite Population Models of Co-evolution and their Application to Haploidy versus Diploidy
	Introduction
	Models and Methods
		Haploid and Diploid Reproduction Schemes
		Simple Genetic Algorithms
		Co-evolution of Finite Population Models
		Limit Behavior
		Expected Performance
	Application
		Competitive Game: Matching Pennies
		Haploid versus Diploid
		Limit Behavior and Mean Fitness
		Source of High Variance
	Discussion
Evolving Keepaway Soccer Players through Task Decomposition
	Introduction
	Background
		Keepaway
		Neuro-evolution
	Method
		Tabula Rasa Learning
		Learning with Task Decomposition
	Empirical Results
	Discussion
	Conclusion and Future Work
A New Method of Multilayer Perceptron Encoding
	Evolving Neural Networks
	Network Representation and Encoding Schemes
	Experimentation
	Conclusion
An Incremental and Non-generational Coevolutionary Algorithm
Coevolutionary Convergence to Global Optima
Generalized Extremal Optimization for Solving Complex Optimal Design Problems
Coevolving Communication and Cooperation for Lattice Formation Tasks
	Introduction
	Results and Discussion
Efficiency and Reliability of DNA-Based Memories
	1   Introduction
	2   Experimental Design
		2.1   Virtual Test Tubes
		2.2   Libraries and Queries
		2.3   Test Libraries and Experimental Conditions
	3   Analysis of Results
		3.1   Retrieval Efficiency
		3.2   Optimal Concentrations
		3.3   DNA-Based Memory Capacity
	4   Summary and Conclusions
	References
Evolving Hogg’s Quantum Algorithm Using Linear-Tree GP
	Introduction
	Quantum Computing Basics
	Previous Work in Automatic Quantum Circuit Design
	The Linear-Tree GP Scheme
	Evolving Quantum Circuits for 1-SAT
	Conclusions
Hybrid Networks of Evolutionary Processors
	Introduction
	Preliminaries
	Computational Power of HNEP as Language Generating Devices
	Solving Problems with HNEPs
	Concluding Remarks and Future Work
DNA-Like Genomes for Evolution in silico
	1 Introduction
	2 Experimental Design
		2.1 Virtual Test Tubes
		2.2 Fitness Functions
		2.3 Test Graphs and Experimental Conditions
	3 Analysis of Results
	4 Summary and Conclusions
	References
String Binding-Blocking Automata*
On Setting the Parameters of QEA for Practical Applications: Some Guidelines Based on Emperical Evidence
	Introduction
	Some Guidelines for Setting the Parameters of QEA
Evolutionary Two-Dimensional DNA Sequence Alignment
	Introduction
	The Model
	Experiments and Results
	Conclusions and Future Work
Active Control of Thermoacoustic Instability in a Model Combustor with Neuromorphic Evolvable Hardware
	Introduction
	The Model Combustor
	CTRNN-EH
	CTRNN-EH Control Experiments
	Conclusions and Discussion
Hardware Evolution of Analog Speed Controllers for a DC Motor
	1 Introduction
	2 Approach
	3 Conventional Analog Controller
		3.1 Design
		3.2 Performance
	4 Evolved Controllers
		4.1 Case 1
		4.2 Case 2
	5 Summary
An Examination of Hypermutation and Random Immigrant Variants of mrCGA for Dynamic Environments
	Introduction
	Dynamic Optimization Variants of mrCGA
	Testing and Results
	Conclusions
Inherent Fault Tolerance in Evolved Sorting Networks
	Discussion
	References
Co-evolving Task-Dependent Visual Morphologies in Predator-Prey Experiments
	1   Introduction
	2   Experiments
		2.1   Experimental Setup
		2.2   Results
			Experiment A: Evolving the Vision Module
			Experiment B: Adding Constraints
	3   Summary and Conclusions
	References
Integration of Genetic Programming and Reinforcement Learning for Real Robots
	Introduction
	Task Definition
	Proposed Technique
		RL Part Conducted on the Real Robot
		GP Part Conducted on the Simulated Robot
		Integration of GP and RL
	Experimental Results with AIBO
	Discussion
		Comparison with Q-Learning in Both Simulator and Real Robot
		Related Works
		Future Researches
	Conclusion
Multi-objectivity as a Tool for Constructing Hierarchical Complexity
	Introduction
	Embodied Cognition and Organisms
	Complexity in the Eyes of the Beholder
		Assumptions
	Methods
		The Virtual Robots and Simulation Environment
		Experimental Setup
	Results and Discussion
		Morphological Complexity
		Behavioral Complexity
	Conclusion and Future Work
Learning Biped Locomotion from First Principles on a Simulated Humanoid Robot Using Linear Genetic Programming
	Introduction
	Background and Motivation
		Robot Platform
		Gait Control Method
		Evolutionary Gait Optimization Experiment
		Observations
	Evolution of Control Programs
		Dynamic Physics Simulation
		Virtual Register Machine
		Linear Genome Representation
		Evolutionary Algorithm
	Results
	Summary and Conclusions
An Evolutionary Approach to Automatic Construction of the Structure in Hierarchical Reinforcement Learning
	Introduction
	Proposed Method
	Task and Experimental Results
	Conclusion
Fractional Order Dynamical Phenomena in a GA
	The GA Trajectory Planning Scheme
	Fractional-Order Dynamics
	Conclusions
Dimension-Independent Convergence Rate for Non-isotropic (1, λ) − ES
	Introduction
	Notations and Algorithm
	Convergence Results the $(1,lambda )$-ES
		The Sphere Function -- Again
		Convergence of the $(1,lambda )$-ES with $H(x)=|x|$
		Convergence of the $(1,lambda )$-ES with $H(x)=|f\'(x)|$
		Results in Higher Dimensions
	Discussion
	Numerical Experiments
		Computation of the Constants
		Optimality of the Constants
	Conclusions and Perspectives
The Steady State Behavior of (μ/μI, λ)-ES on Ellipsoidal Fitness Models Disturbed by Noise*
	Introduction
	The Steady State Condition of $(mu /mu _I, lambda )$-ES on Noisy Quadratic Functions
		The General Quadratic Fitness Noise Model
		Determining the Steady State Condition
		Estimating the Expected Stationary Fitness Error
		ES-Dynamics and Comparison with Experiments
	Conclusions and Outlook
Theoretical Analysis of Simple Evolution Strategies in Quickly Changing Environments
	Introduction
	Related Work
	Comparing $(1,2)$ and $(1+1)$ on an Environment Changing {em between} Generations
		Optimal Mutation Rate
		Convergence Plots
	Change {em within} a Generation
		Two-Step Mutation
		Using Two-Step Mutation to Model Change within a Generation
		Comparisons
	Conclusion and Future Work
Evolutionary Computing as a Tool for Grammar Development
	Introduction
	Natural Language Grammar Development
	Grammar Evolution
	GRAEL-1: Probabilistic Grammar Optimization
		Experimental Setup
		Results
	GRAEL-2: Grammar Rule Discovery
	GRAEL-3: Unsupervised Grammar Induction
	Concluding Remarks
Solving Distributed Asymmetric Constraint Satisfaction Problems Using an Evolutionary Society of Hill-Climbers
	Introduction
	CSPs, Asymmetric Constraints, and the Phase Transition
		Asymmetric Constraints
		Predicting the Phase Transition
	Society of Hill-Climbers
		The mDBA
		The Simple and Evolutionary SoHCs
	Results
		Experiment I
		Experiment II
		Discussion
	Conclusions and Future Work
Use of Multiobjective Optimization Concepts to Handle Constraints in Single-Objective Optimization
	Introduction
	Problem Statement
	Basic Concepts
		Pareto Optimality
	Related Work
	Description of IS-PAES
		Inverted ``Ownership\'\'
		Shrinking the Objective Space
	Comparison of Results
	Conclusions and Future Work
Evolution Strategies with Exclusion-Based Selection Operators and a Fourier Series Auxiliary Function
	Introduction
	Exclusion-Based Selection Operators
	A Fourier Series Auxiliary Function
	EFES: The Evolution Strategies with Exclusion-Based Selection Operators and a Fourier Series Auxiliary Function
	Simulations and Comparisons
	Conclusion
Ruin and Recreate Principle Based Approach for the Quadratic Assignment Problem
	1   Introduction
	2   Preliminaries
	3   Ruin and Recreate Principle
	4   Ruin and Recreate Principle Based Algorithm for the QAP
		4.1   Initial Solution Generation
		4.2   Local Search
		4.3   Mutation
		4.4   Candidate Acceptance
	5   Computational Experiments and Results
	6   Conclusions
	References
Model-Assisted Steady-State Evolution Strategies
On the Optimization of Monotone Polynomials by the (1+1) EA and Randomized Local Search
	Introduction
	The Optimization of Monomials
	On the Analysis of Random Local Search
	Royal Roads as a Worst-Case Example
	On the Analysis of RLSensuremath {_{p}}
	On the Analysis of the textup {(1+1)} EAfuturelet next
	Some Results on Markov Chains
A Forest Representation for Evolutionary Algorithms Applied to Network Design
	The Proposed Representation
	Final Considerations
Solving Three-Objective Optimization Problems Using Evolutionary Dynamic Weighted Aggregation: Results and Analysis
The Principle of Maximum Entropy-Based Two-Phase Optimization of Fuzzy Controller by Evolutionary Programming
	Two-Phase Evolutionary Optimization
	Simulation Results
A Simple Evolution Strategy to Solve Constrained Optimization Problems
	Our Approach
Effective Search of the Energy Landscape for Protein Folding
A Clustering Based Niching Method for Evolutionary Algorithms
	Clustering Based Niching
	Results and Conclusions
A Hybrid Genetic Algorithm for the Capacitated Vehicle Routing Problem
	1   Introduction
	2   Hybrid Genetic Approach
		2.1  General Description
		2.2 Selection
		2.3 Genetic Operators
	3   Computational Results
	4   Conclusion
	References
An Evolutionary Approach to Capacitated Resource Distribution by a Multiple-Agent Team
	1   Introduction
	2   Problem Formulation
		2.1 	Multi-vehicle Resource Distribution with One Source/Depot
		2.2 	Multi-vehicle Capacitated Resource Distribution with Multiple Sources
		3   The Evolutionary Algorithm: Genetic Structure
		3.1   Recombination and Mutation Operators
		3.2	2-Opt Edge Exchange Local Improvement Heuristic
		3.3	Back Stepping Heuristic for Improved Reload Point Assignment
	4   Discussion of the Results
	5   Conclusions and Future Work
	References
A Hybrid Genetic Algorithm Based on Complete Graph Representation for the Sequential Ordering Problem
	Introduction
	Background
	Genetic Operators
		Voronoi Quantized Crossover
		Genic Distance Assignment
		Heterogeneous Mating
		Properties of VQX
	Experimental Results
	Conclusions
An Optimization Solution for Packet Scheduling: A Pipeline-Based Genetic Algorithm Accelerator
	Introduction
	General Genetic Algorithms Packet Scheduler (G-GAPS)
		Definition
		The Fitness Function
		Implementation of the Genetic Algorithms
	Hyper-generation GAs Packet Scheduler (HG-GAPS)
		Hardware Block Diagram of the HG-GAPS
	Simulation Model and Results
		Simulation Model
		Simulation Results
	Conclusions
Generation and Optimization of Train Timetables Using Coevolution
Chromosome Reuse in Genetic Algorithms
	Introduction
	Statistical Reasoning on the Chromosome Reuse Strategy
	GAs with Chromosome Reuse Strategy
	Two Case Studies
		Performance of Chromosome Reuse Strategy in Numerical Optimization
		Performance of Chromosome Reuse Strategy in Combinatorial Optimization
	Conclusions and Future Work
Real-Parameter Genetic Algorithms for Finding Multiple Optimal Solutions in Multi-modal Optimization
	Introduction
	GAs in Multi-modal Optimisation
	Real-Parameter GAs
		Selection Schemes
		Crossover Schemes
		Replacement Schemes
	Experimental Setup
	Results
	Conclusions
An Adaptive Penalty Scheme for Steady-State Genetic Algorithms
	Introduction
	Penalty Methods
		Related Methods in the Literature
	The Proposed Method
	Numerical Experiments
	Conclusions
Asynchronous Genetic Algorithms for Heterogeneous Networks Using Coarse-Grained Dataflow
	Introduction
	Dataflow Principles
	Using Dataflow for Asynchrony
	Analysis and Results
		Homogeneous System of Processors
		Heterogeneous System of Processors
		0/1 Knapsack Problem
		Air Quality Optimization
	Final Remarks
A Generalized Feedforward Neural Network Architecture and Its Training Using Two Stochastic Search Methods
	Introduction
	The Generalized Feedforward Neural Network Architecture
		Generalized Shunting Inhibitory Neuron
		The Network Architecture
	Training Methods
		Random Optimization Method (ROM)
		Genetic Algorithms (GAs)
	Experimental Results
		The XOR and 3-Bit Parity Problems
		Diabetes Problem
		Heart Disease Problem
	Conclusions and Future Work
Ant-Based Crossover for Permutation Problems
	Introduction
	Related Work
		Permutation Crossover
		Ant Colony Optimization
		Hybrids
	Ant-Based Crossover
	Empirical Evaluation
		Test Setup
		Basic EA Parameters
		Parameters for Ant-Based Crossover
		Comparison of ABX with ERX, and ACO
	Conclusion and Future Work
Selection in the Presence of Noise
	Introduction
	Related Work
	Stochastic Tournament Selection
	Selection Based on a Fixed Sample Size
		Basic Notations
		Standard Stochastic Tournament Selection
		A Simple Correction
		Bootstrapping
	Resampling
	Conclusion
Effective Use of Directional Information in Multi-objective Evolutionary Computation
	Introduction
	Directional Multi-objective Optimization
		Single-Objective Half-Spaces
		Directional Cones and Multi-objective Search
		Test for Local Pareto Optimality
		Multi-objective Steepest Descent
		Dimensionality Analysis
	Directional Evolutionary Computation
		Population-Based Estimation of the Multi-objective Gradient
		Population-Based Pareto Optimality
	Example
	Conclusions and Further Work
	References
Pruning Neural Networks with Distribution Estimation Algorithms
	Introduction
	Neural Network Pruning
	Methods
		Algorithms
		Data Sets
		Evaluation Method
	Experiments
	Conclusions
Are Multiple Runs of Genetic Algorithms Better than One?
	Introduction
	Related Work
	The Gambler\'s Ruin Model
	Multiple Small Runs
		Solution Quality
		Models of Convergence Time
		Random Search
	Experiments
	Multiple Short Runs
	Summary and Conclusions
Constrained Multi-objective Optimization Using Steady State Genetic Algorithms
	1	Introduction
	2	Methods for Multi-objective Optimization Using Steady State GAs
		2.2	Objective Switching Genetic Algorithm for Design Optimization (OSGADO)
	3	Experimental Results
		3.1	Test Problems
		3.2	Parameter Settings
		3.3	Results
	4	Conclusion and Future Work
		Acknowledgement. This research is sponsored by the US National Science Foundation under grant CTS-0121058. The program managers are Drs. Frederica Darema, C. F. Chen and Michael Plesniak.
		References
An Analysis of a Reordering Operator with Tournament Selection on a GA-Hard Problem
	Introduction
	The Framework
		Minimal Deceptive Problem
		Assumptions
		Reordering and Linkage Learning
		Previous Results
	IRO with Tournament Selection
		Separating Selection and Crossover
		Pairwise Tournament Selection
		Using IRO
		$S$-ary Tournament Selection
		Probabilistic Tournament Selection
	Conclusions
Tightness Time for the Linkage Learning Genetic Algorithm
	Introduction
	Brief Review of Competent GAs and the LLGA
		Chromosome Representation
		Exchange Crossover
		Mechanisms Making the LLGA Work
	Linkage Learning Mechanisms
		Quantifying Linkage
		Linkage Skew
		Linkage Shift
	Experimental Results
		Parameter Settings
		Linkage Skew
		Linkage Shift
	Tightness Time
		The Model
		Verification
	Conclusions
A Hybrid Genetic Algorithm for the Hexagonal Tortoise Problem
	Introduction
	Hexagonal Tortoise Problem
	Local Optimization Heuristic
		Consecutive Exchange
		Further Optimization Using Tabu Search
	The Hybrid Genetic Algorithm for the Hexagonal Tortoise Problem
		Nearby Search
		Aging
		Performance Improvement by Nearby Search and Aging
	Experimental Results
	Conclusion
Normalization in Genetic Algorithms
	Introduction
	Drawbacks of Redundant Encoding
	Normalization and Space Reduction
	Normalization Examples
		Graph Partitioning Problem
		Sorting Network Problem
	Conclusion
Coarse-Graining in Genetic Algorithms: Some Issues and Examples
	Introduction
	Coarse-Grained Dynamics
	Exact and Approximate Invariance under a Coarse-Graining
	Crossover and Schemata Coarse Graining
	Mutation and the Genotype-Phenotype Coarse-Graining
	Linkage-Disequilibrium
	Conclusion
Building a GA from Design Principles for Learning Bayesian Networks
	Introduction
	Related Work
	Design Considerations
	The GA
		Generation of the Skeleton Graph
		The GA
	Results
	Conclusions
A Method for Handling Numerical Attributes in GA-Based Inductive Concept Learners
	Introduction
	Handling Numerical Attributes Using Constraints
		Clustering Attribute Values
		Operators
	ECL: A GA Based Inductive Concept Learner
		Clu-Con: ECL Plus Local Discretization
		Ent_MDL: ECL Plus Global Discretization
	Experiments
	Conclusions and Future Work
Analysis of the (1+1) EA for a Dynamically Bitwise Changing OneMax
	Introduction
	The {(1+1)tmspace +thinmuskip {.1667em}tmspace +thinmuskip {.1667em}EA}/ and a Dynamic text {sc OneMax}
	A Super-Polynomial Lower Bound for Large Movement Rates
	A Polynomial Upper Bound for Small Movement Rates
	Conclusions
Performance Evaluation and Population Reduction for a Self Adaptive Hybrid Genetic Algorithm (SAHGA)
	1	Introduction
	2	SAHGA and NAHGA Algorithms
		2.1	Non-adaptive Hybrid Genetic Algorithm (NAHGA)
		2.2	Self-Adaptive Hybrid Genetic Algorithm (SAHGA)
	3	Test Functions
	4	Evaluation of HGA Performance
		4.1	Local Search Algorithm
		Population Size for Genetic Algorithm
		4.3 	Standard Deviation Reduction: Local Search Effect on Population Size
		4.4 	Population Size for Hybrid Algorithms
		4.5 	HGA Performance
	5	Recommendations and Conclusions
	References
Schema Analysis of Average Fitness in Multiplicative Landscape
	Introduction
	Mathematical Model
		Model
		Walsh Transformation
		Evolution Equation
	Schema Theorem
	Multiplicative Landscape
		Schema Analysis
		Schema Representation of Average Fitness
	Experiments
	Conclusion
On the Treewidth of NK Landscapes
	Introduction
	NK Landscape Models
	The Treewidth of the NK Landscape Models
	Conclusions and Future Work
Selection Intensity in Asynchronous Cellular Evolutionary Algorithms
	Introduction
	Asynchronous cEAs
	Takeover Times
	Modelling Individual Growth
		Statistical Results on Information Propagation
		Fitting the Selection Pressure Curves
		An Improved Model
	Conclusions
A Case for Codons in Evolutionary Algorithms
	1.1   Genotypic and Phenotypic Data Representation in Evolutionary Algorithms
	1.2   Genotypic and Phenotypic Data Representation in Biological Systems.
	2.3  Test Problems
	2.3.2  Indecisive
	4   Conclusions
	References
Natural Coding: A More Efficient Representation for Evolutionary Learning*
	Introduction
	Algorithm
	Hybrid Coding
	Natural Coding
	Results
	Conclusions
Hybridization of Estimation of Distribution Algorithms with a Repair Method for Solving Constraint Satisfaction Problems
	Introduction
	Constraint Satisfaction Problems
		Formulation
		Min-Conflict Hill Climbing
	Brief Introduction of the Estimation of Distribution Algorithms
		General Framework of EDAs
		UMDA
		MIMIC
		EBNA
	The Proposed Method
	Experimental Results
	Conclusions
Efficient Linkage Discovery by Limited Probing
	Introduction
	Notation
	Walsh Analysis and Embedded Landscapes
	Probes
	The Linkage Graph and Hypergraph
	Computing the Walsh Coefficients Using the Kargupta-Park Top-Down Algorithm
	Detecting Linkage and Computing the Walsh Coefficients
	Empirical Results
	Conclusions
Distributed Probabilistic Model-Building Genetic Algorithm
	Introduction
	Distributed Probabilistic Model-Building Genetic Algorithm
		Flow of DPMBGA
		Sampling Individuals for Probabilistic Model
		Sampling Individuals for PCA
		PCA Transformation
		Generation of New Individuals
		Restoring Correlation and Substitution of Old Individuals with New Individuals
		Mutation
		Preservation and Recovering of Elite Individuals
	Test Functions and Used Parameters for Numerical Experiments
	Discussion on Effectiveness of PCA and Distributed Environment Scheme
	Comparison of DPMBGA with UNDX + MGG
	Discussion on Case Where PCA Does Not Work Effectively
	Discussion on Search Capability of DPMBGA for Functions Whose Optimum Is Located Near the Boundary
	Conclusions
HEMO: A Sustainable Multi-objective Evolutionary Optimization Framework
	1	Introduction
	2	Convergence, Diversity, and Premature Convergence in EMO
		2.1   Performance Comparison of Modern MOGAs
		2.2   Premature Convergence and the Issue of Exploitation vs. Exploration
		2.3   Combining Ideas in SPEA, PESA, and the Improved NSGA-II
	3	HEMO: Hierarchical Evolutionary Multiobjective Optimization
	4	Experiments and Results
	5	Conclusions and Future Work
	References
Using an Immune System Model to Explore Mate Selection in Genetic Algorithms
	Introduction
	Relevant Work in Prior GA Research
		Fitness Sharing
		Binary Immune System Model
		Mate Selection Schemes
	Experimental Results
		Effects of Mate Selection on Maintaining Subpopulations
		Effects of Mate Selection on the Discovery of Peaks
	Conclusions and Future Work
Designing a Hybrid Genetic Algorithm for the Linear Ordering Problem
	Introduction
	Hybrid Genetic Algorithm
		Genetic Algorithm
		Local Search
	Preliminary Experiments
		Combination of Crossover Operators and Mutation Operators
		Tuning of Parameter {tt mutation_rate}
		Tuning of Parameter {tt crossover_rate}
		Tuning of Parameter {tt population_size}
		Summary: Effect of Genetic Algorithm and Local Search
	Computational Results
		LOLIB Instances
		Random Instances Set A
		Random Instances Set B
	Conclusion
A Similarity-Based Mating Scheme for Evolutionary Multiobjective Optimization
	1 Introduction
	2 Proposed Mating Scheme
	3 Computational Experiments
		3.1 Test Problem and Parameter Specifications
		3.2 Performance Measures
		3.3 Experimental Results
	4 Concluding Remarks
	References
Evolutionary Multiobjective Optimization for Generating an Ensemble of Fuzzy Rule-Based Classifiers
	1 Introduction
	2 Fuzzy Rule-Based Classifiers
	3 Heuristic Rule Extraction and Genetic Rule Selection
		3.1 Heuristic Rule Extraction
		3.2 Genetic Rule Selection
	4 Computational Experiments
		4.1 Data Sets
		4.2 Experimental Conditions
		4.3 Experimental Results
	5 Concluding Remarks
	References
Voronoi Diagrams Based Function Identification
	Introduction
	Domain Partition
	Approximation
		The Non-continuous Combination
		The Continuous Combination
	The Evolutionary Algorithm
		The Representation
		The Operators
	Numerical Results
	Conclusions
New Usage of SOM for Genetic Algorithms
	Introduction
	Preliminaries
		Network Architecture
		Topological Ordering Property of SOM
		Gene Reordering
	Transforming into Isomorphic Structures
		SOM-Based Transformation
	GA for Optimizing the Neural Network
		The GA Structure
		Problem Encoding
		Geographic 2D Crossover
	Experimental Results
		Database
		Experimental Results
	Concluding Remarks
Problem-Independent Schema Synthesis for Genetic Algorithms
	Introduction
	Preliminaries
		Graph Bisection
		Linear Arrangement
		Traveling Salesman Problem (TSP)
	A Hybrid Genetic Algorithm
	Problem-Independent Gene Rearrangement
	Experimental Results
		Graph Bisection
		Linear Arrangement
		Traveling Salesman Problem
	Conclusions
Investigation of the Fitness Landscapes and Multi-parent Crossover for Graph Bipartitioning
	Introduction
	Preliminaries
		Graph Bipartitioning
		Fiduccia-Mattheyses Algorithm (FM)
		Test Beds
	Investigation of the Problem Space
		Cost-Distance Correlation
		Approximate Central Point
	Exploiting Approximate Central Points
		A Pseudo-GA That Exploits the Central Areas
		Experimental Results
	Conclusions
New Usage of Sammon’s Mapping for Genetic Visualization
	Introduction
	Preliminaries
		Graph Partitioning
		Sammon\'s Mapping
	Fitness Landscapes
		Cost-Distance Correlation
		Distribution of Local Optima
		Visualization by Sammon\'s Mapping
	Visualization of a Steady-State Genetic Search
		Previous Studies
		Extended Experiments
	Schema Traces
	Conclusions
Exploring a Two-Population Genetic Algorithm
	Introduction
	Results
		Group 1
		Group 2
		Group 2 with a Two-Population GA
		Summary and Comments on Results
	Discussion
Adaptive Elitist-Population Based Genetic Algorithm for Multimodal Function Optimization
	Introduction
	Related Work
		Elitism
		Evolving Parallel Subpopulations by Niching
		Clonal Selection Principle
	Adaptive Elitist-Population Search Technique
		The Principle of the Individuals\' Dissimilarity
		Adaptive Elitist-Population Search
		The AEGA
	Experimental Results
	Conclusion and Future Work
Wise Breeding GA via Machine Learning Techniques for Function Optimization
	Introduction
	Background
		Population Based Incremental Learning (PBIL)
		Induction of Decision Trees (ID3)
	Statistical Learning + Inductive Learning = SI3E
		Knowledge Extraction from a Population Using ID3
		Can PBIL Ideas Help?
		Fixed Loci and Example Set Formation
		Everything in Place: SI3E Algorithms and Their Tuning
	Experiments
	Conclusions
Facts and Fallacies in Using Genetic Algorithms for Learning Clauses in First-Order Logic
	Introduction
	Preliminaries
		Inductive Logic Programming (ILP)
		Inverse Entailment
	The Binary Representation Approach: Facts and Fallacies
		Fallacy 1 --- Fact 1
		Fallacy 2 --- Fact 2
		Fallacy 3 --- Fact 3
	Potential Solutions
	Conclusions
Comparing Evolutionary Computation Techniques via Their Representation
	Introduction
	Special Evolutionary Algorithms
	The Binary Embedding Theorem
	Characterizing the Morphisms from a Given Heuristic $3$-Tuple into a Genetic Heuristic $3$-Tuple in Terms of Radcliffe\'s Forma
	Conclusions
Dispersion-Based Population Initialization
	Introduction
	Problem Description
	Discrepancy Measurement
		Population Placement Basis
	Heuristic Rules
		Population Placement in Very High-Dimensional Search Spaces
		Population Placement in Complex Search Spaces
	Experimental Verification
	Analysis
	Summary
A Parallel Genetic Algorithm Based on Linkage Identification
	Introduction
	Parallel GAs
	Linkage Identification
	A Parallel GA Based on Linkage Identification
	Empirical Results
	Conclusions
Generalization of Dominance Relation-Based Replacement Rules for Memetic EMO Algorithms
Author Index