Advances in Genetic Programming - Vol. 3

by Lee Spector, William B. Langdon, Una-May O'Reilly and PeterJ (Eds.)

• ISBN13: 9780262194235
• ISBN10: 0262194236
• Format: Hardcover
• Copyright: 1999-07-16
• Publisher: Bradford Books

Summary

Genetic programming is a form of evolutionary computation that evolves programs and program-like executable structures for developing reliable time- and cost-effective applications. It does this by breeding programs over many generations, using the principles of natural selection, sexual recombination, and mutuation. This third volume of Advances in Genetic Programminghighlights many of the recent technical advances in this increasingly popular field.

Table of Contents

Contributors

Acknowledgments

An Introduction to the Third Volume

A brief overview of genetic programming

Other GP Resources

Public Domain GP Implementations (unsupported)

The work in this volume

Part I: Applications

Part II: Theory

Part III: Extensions

Bibliography

Applications

An Automatic Software Re-Engineering Tool Based on Genetic Programming

Introduction

Software Re-engineering

Parallel Problems

Problems with Data Dependency Analysis

Genetic Structure

Atom Mode

Atom Mode Transformations.

P and S

F and L

Shift

Null/Parnull

Atom Mode Fitness

Directed Analysis for Fpar

Directed Analysis for Lpar

Directed Analysis for Pxx

Directed Analysis

Loop Mode

Loop Fusion

Loop Shrinking

Example Individual

Loop Mode

Resumption of Atom Mode

Directed Data Dependency Analysis

Experimental Results

Scheduling

Conclusion

Bibliography

CAD Surface Reconstruction from Digitized 3D Point Data with a Genetic Programming/Evolution Strategy Hybrid

Introduction

Classic Context

Digitizing and Preprocessing

Gridded Representation and Topological Information

Surreal- a Genetic Programming/Evolution Strategy Hybrid

The Approach

Overview

Algorithmic Structure

Genetic Representation

Constructive Solid Geometry

Terminal and Function Set

Search Space

Quality Measure

Distance Criterion Delta

Angle Criterion Abn

Curvature-type Criterion Ctype

Primitive-number Criterion Prim

Variation

Mutation

Recombination

Creation

Selection for variation

Selection for the next generation

Results

Problem: dowel reconstruction

Parameters

Discussion

Incremental optimization

Fitness progression

Population size and convergence

Interactive evolution

Problem: cross-structure reconstruction

Conclusion and future work

Acknowledgments

Bibliography

A Genetic Programming Approach for Robust Language Interpretation

Introduction

Abstraction on the Problem of Parse Repair

The Basic Problem

Program Induction as a Solution

ROSE's Application of GP

The Partial Parsing Stage

The Combination Stage

Applying Genetic Programming

Fitness Evaluation for the Combination Problem

Why GP?

Evaluation

Challenges

Acknowledgements

Bibliography

Time Series Modeling Using Genetic Programming: An Application to Rainfall-Runoff Models

Introduction

The Genetic Programming System CFG-GP

Rainfall Runoff Modelling

CFG-GP Setup

Catchment Descriptions and Results

The Glan Teifi Catchment

Results

The Namoi River Catchment

Results

Discussion

Conclusion

Acknowledgments

References

Automatic Synthesis, Placement, and Routing of Electrical Circuits by Means of Genetic Programming

Introduction

Automatic Creation of Circuit Topology and Sizing

Method for Automatic Creation of Circuit Topology, Sizing, Placement, and Routing

The Initial Circuit

Circuit-Constructing Functions

Component-Creating Functions

Topology-Modifying Functions

Development-Controlling Functions

The Developmental Process

Statement of the Illustrative Problem

Preparatory Steps

Initial Circuit

Program Architecture

Function and Terminal Sets

Fitness Measure

Control Parameters

Termination Criterion and Results Designation

Implementation on Parallel Computer

Results

Computer Time

Genetic Programming as an Invention Machine

Conclusion

Bibliography

Quantum Computing Applications of Genetic Programming

Quantum Computation

A Virtual Quantum Computer

State Representation and Notation

Quantum Gates

Quantum NOT and SQUARE ROOT OF NOT

Applying quantum gates to multi-qubit systems

Other Quantum Gates

Running a Quantum Algorithm

Example Execution Trace

The Power of Quantum Computation

Evolving Quantum Algorithms

Standard Tree-based Genetic Programming

Stack-Based, Linear Genome Genetic Programming

Stackless Linear Genome Genetic Programming

Fitness Function

Results

Deutsch's Early Promise Problem

The Scaling Majority-On Problem

The Database Search Problem

The And-Or Query Problem

Conclusions

Acknowledgements

Bibliography

Theory

The Evolution of Size and Shape

Introduction

Background

Program Search Spaces

Bloat Inherent in Variable Length Representations

Sextic Polynomial

GP Runs

Non GP Search Strategies

New Tree Mutation Operators

50-150% Fair Mutation Runs

Subtree Fair Mutation Runs

Direct Measurement of Genetic Operators Effects on Performance

Self Crossover

Mutation Operators

Bloat in Discrete Problems

Code Bloat as Protection

Code bloat due to "Removal Bias"

Evolution of Program Shapes

Discussion

Conclusions

Future Work

Acknowledgments

Bibliography

Fitness Distributions: Tools for Designing Efficient Evolutionary Computations

Introduction

Background

Fitness distributions

Evolving computer programs using evolutionary programming

Initialization

Offspring generation through variation

Parent selection

Test problems

Experiments

Results

Discussion

Conclusion

Acknowledgments

Bibliography

Analysis of Single-Node (Building) Blocks in Genetic Programming

Introduction

Current Usages and Definitions

Objectives

Case Study Description

Motivations

Method

Fitness-Centric Experiment

Fitness-Centric Results

Fitness-Centric Discussion

ERC-Centric Experiment

ERC-Centric Results

ERC-Centric Discussion

Implications for Building Blocks

Conclusions

Acknowledgments

Appendix A.10.1 Approaches to Solving f(x)

Appendix A.10.2 Known ERC Strategies

Appendix A.10.3 Alternative Frame for Analyzing GP and ERCs

Bibliography

Rooted-Tree Schemata in Genetic Programming

Introduction

Schema Theory

Schemata in genetic algorithms

Schemata in genetic programming

Portraying Variable Complexity Representations

The rooted-tree schema property

Growth of rooted-tree schemata

The role of variable size during evolution

Adding Parsimony

Selection with a parsimonious fitness function

Growth of rooted-tree schemata with parsimony

Controlling Schema Growth

Experimental Results

Fitness based on pure performance

Parsimonious fitness

Adaptive probability of destruction

Summary of experiments

Solution Acquisition in GP

Related Work

Conclusion

Acknowledgements

Bibliography

Extensions

Efficient Evolution of Machine Code for CISC Architectures Using Instruction Blocks and Homologous Crossover

Introduction

Why Evolve Machine Code?

Advantages of Evolving Machine Code

Why is Binary Manipulation so Fast?

Overview of AIM-GP

Making Machine Code Genetic Programming Work on CISC Processors

The Importance of Extending AIM-GP to CISC Processors

Challenges in Moving AIM-GP to CISC Processors

Instruction Blocks

Instruction Annotations

The Benefits of ''Glue''

Other AIM-GP Innovations

Memory Access and Large Input Sets

Decompilation

Homologous Crossover

Floating Point Arithmetic

Automatically Defined Functions

AIM-GP and Tree-Based GP

Future Work

Summary and Conclusion

Acknowledgments

Bibliography

Sub-machine-code Genetic Programming

Introduction

Background

Sub-machine-code GP

Examples

1-bit and 2-bit Adder Problems

Character Recognition Problem

Discussion

Fast Parallel Evaluation of Fitness Cases

Conclusions

Appendix: Implementation

Description

Code

Acknowledgements

Bibliography

The Internal Reinforcement of Evolving Algorithms

Introduction

Neural Programming

The Neural Programming Representation

Illustrative Examples

Example 1: The Fibonacci Series

Example 2: The Golden Mean

Example 3: Foveation

Internal Reinforcement in NP

Creating a Credit-Blame Map

Accumulation of Explicit Credit Scores

Function Sensitivity Approximation

Refining the Credit-Blame Map

Credit Scoring the NP arcs

Exploration vs. Exploitation Within a Program

Using a Credit-Blame Map

Mutation: Applying a Credit-Blame Map

Crossover: Applying a Credit-Blame Map

The Credit-Blame Map Before/After Refinement

IRNP Discussion

Experimental Results

Experimental Overview

Natural Images

Setting PADO up to Solve the Problem

The Results

Acoustic Signals

Setting PADO up to Solve the Problem

The Results

Acoustic Signals Revisited

Setting PADO up to Solve the Problem

The Results

Related Work

Conclusions

Acknowledgements

Bibliography

Inductive Genetic Programming with Immune Network Dynamics

Introduction

Immune Version of the GP System

Biological Networks

Computational CounterParts in GP

The Dynamic Fitness Function

Micromechanisms of the Inductive GP

Inductive Learning and Regression

Multivariate Trees

Context-Preserving Mutation

Crossover by Cut and Splice

Practical Induction by Immune Dynamics

Traditional and Immune Versions of iGP

Performance Measures

Machine Learning

Time-Series Prediction

Discussion

Relevance to Other Works

Conclusion

Bibliography

A Self-Tuning Mechanism for Depth-Dependent Crossover

Introduction

A Self-Tuning Mechanism for Depth-Dependent Crossover

Experimental Results

The 11MX problem

The ANT problem

The robot problem

Discussion

Conclusion

Acknowledgments

Bibliography

Genetic Recursive Regression for Modeling and Forecasting Real-World Chaotic Time Series

Problem Definition: Data Driven Model Building

Genetic Symbolic Regression and Data Driven Model Building

A New Algorithm Genetic Recursive Regression (GRR)

Recursive Regression

Representation of the Regression Model as a Series Expansion

Parallel Computational Architecture

Adaptive Update of the Numerical Coefficients.

Derived Terminal Set

Implementation Issues

Fitness Assignment

Super Population and Migration between Multiple Populations

Dealing with Absurd Attributes of a Symbolic Form

Division of the Data Set: Training, Validation and Prediction Regions

Termination Conditions

Some Manipulations on the Raw Data

Application to Read World Chaotic Time Series

Benchmarking

Data and Computational Settings

Benchmarking Results and Discussion

Effects of the Adaptive Update of the Numerical Coefficients

Effects of the Parallel Architecture

Effects of the Recursive Model Building

Rend World Chaotic Time Series

Data and Computational Settings

Results and Discussion

Effects of the Derived Terminal Set (DTS)

Comparisons with Earlier Works

ASHRAE and Santa Fe Competitions

Mackey-Glass Equation

Conclusion and Issues Remaining

Acknowledgments

Bibliography

Co-evolutionary Fitness Switching: Learning Complex Collective Behaviors Using Genetic Programming

Introduction

Genetic Programming with Coevolutionary Fitness Switching

Results on Table Transport

Application to Robotic Soccer

Conclusions

Acknowledgements

Bibliography

Evolving Multiple Agents by Genetic Programming

Introduction

Example Tasks

Fitness Assignment and Breeding Strategies

Comparison with Reinforcement Learning

Evolving Agents with Communication

Evolving Controlling Agents

Evolving Negotiating Agents

Discussion

Evolving Other Types of Communicating Agents

Q-learning and Genetic Programming

Related Work

Conclusion

A Multi-agent reinforcement learning

Bibliography

Index

Table of Contents provided by Publisher. All Rights Reserved.