Table of Contents

Chapter 1: Introduction
1.1  Can Machines Think?
1.1.1 Artificial Intelligence
1.1.2 Evolutionary Systems
1.2  Introduction to the Genetic Programming Paradigm
1.3  Machine Learning
1.3.1 Supervised Learning
1.3.2 Unsupervised Learning
1.4  Demonstrating Machine Learning
1.5 A Statement of the Problem

 Chapter 2: Literature Review
2.1 Genetic Algorithms: Precursor to Genetic Programming
2.2 A Closer Look at Genetic Programming
2.3 Tuning
2.4 Genetic Operators
2.4.1 Crossover
2.4.2 Fitness
2.4.3 Selection
2.4.3.1 Stochastic Sampling with Replacement
2.4.3.2 Stochastic Sampling without Replacement
2.4.3.3 Tournament Selection
2.4.3.4 Deterministic Sampling
2.4.4 Fitness Proportionate Reproduction
2.4.5 Demetic Grouping
2.4.6 Mutation
2.4.7 Permutation
2.4.8 Steady State Genetic Programming
2.4.9 Automatic Function Definition
2.5 The Cart-Pole Problem
2.6 Advantages of Genetic Systems
2.7 Applications of Genetic Programming

 Chapter 3: Research Methodology
3.1 Outline
3.2 Experimental Method
3.2.1 Parameter Settings
3.2.2 Populating Generation Zero
3.2.3 Devising a Fitness Function
3.2.3.1 Fitness Scaling
3.2.4 Devising a Function Set and Terminal Set
3.2.4.1 The Function Set
3.2.4.2 The Terminal Set
3.2.5 Criterion for Termination
3.2.6 Selection of Genetic Operators
3.2.7 Simulation of The Cart-Pole Problem
3.2.8 Implementation Language
3.2.9 Performance Specification
3.2.10 Raw Data Output of the Simulation
3.3 Statistical Techniques
3.3.1 De Jong’s Performance Measures
3.3.1.1 On-Line Performance
3.3.1.2 Off-Line Performance
3.3.2 Distribution Analysis Of Performance
3.3.3 The Rate of Learning

Chapter 4: Results
4.1 Introduction
4.2 Limitations
4.3 Performance of Controllers
4.3.1 Specification 1(a): Pole Angle of Controllers
4.3.2 Specification 1(b): Cart Position of Controllers
4.3.3 Specifications 2 and 3: RMS Amplitudes
4.4 Performance of Selection Techniques
4.4.1 On-Line Performance
4.4.2 Off-Line Performance
4.4.3 Distribution of the Observed Means
4.4.4 Distribution of the Observed Best
4.4.5 Performance in Learning Rate
4.4.5.1 Samples of Successful Controllers
4.4.5.2 The Extension of the Median Test
4.4.5.3 Analysis of Variance

Chapter 5: Discussion
5.1 Introduction
5.2 Performance of The Genetic Programming Paradigm
5.3 Performance of Selection Techniques
5.3.1 On-Line Performance
5.3.2 Off-Line Performance
5.3.3 Rate of Learning

 Chapter 6: Conclusion

Chapter 7: Remarks

Glossary of Terms

Bibliography

Appendices

APPENDIX I: THE GENETIC ALGORITHM
APPENDIX II: SELECTION ALGORITHMS
APPENDIX III: CROSSOVER IN GENETIC PROGRAMMING
APPENDIX IV: MINIMUM STANDARD RANDOM NUMBER GENERATOR
APPENDIX V: SOURCE CODE FOR THE GENETIC PROGRAM

List of Tables

TABLE 1: RANDOM CONTROLLERS APPLIED TO THE CART-POLE PROBLEM
TABLE 2: GENETIC PROGRAM TABLEAU
TABLE 3: PROGRAM PARAMETERS
TABLE 4: STANDARD PARAMETERS FOR CART-POLE SIMULATION
TABLE 5: INITIAL CONDITIONS FOR SIMULATION
TABLE 6: THE BEST CONTROLLER FOUND BY ROULETTE WHEEL SELECTION
TABLE 7: THE BEST CONTROLLER FOUND BY TOURNAMENT SELECTION
TABLE 8: THE BEST CONTROLLER FOUND BY EXPECTED VALUE MODEL SELECTION
TABLE 9: RMS AMPLITUDES OF CART POSITION AND POLE ANGLE
TABLE 10: TABULATED DATA FOR THE EXTENSION OF THE MEDIAN TEST
TABLE 11: ANALYSIS OF VARIANCE
TABLE 12: COMPARISON OF CENTRING WITH GENETIC ALGORITHM

List of Equations

EQUATION 1: PROBABILITY OF SELECTION
EQUATION 2: EXPECTED OCCURRENCE IN MATING POOL
EQUATION 3: LINEAR DYNAMIC EQUATION TO SOLVE THE CART-POLE PROBLEM
EQUATION 4: STANDARD FITNESS FUNCTION
EQUATION 5: EXPLICIT CENTRING IN FITNESS FUNCTION
EQUATION 6: SIMULATION OF THE CART-POLE PROBLEM
EQUATION 7: CART POSITION
EQUATION 8: POLE POSITION
EQUATION 9: DE JONG'S ON-LINE PERFORMANCE
EQUATION 10: DE JONG'S OFF-LINE PERFORMANCE
EQUATION 11: CONFIDENCE INTERVAL ESTIMATE FOR PERFORMANCE MEASURES
EQUATION 12: THE EXTENSION OF THE MEDIAN TEST
 
 

List of Figures

FIGURE 1: TWO POINT CROSSOVER OF BINARY STRINGS
FIGURE 2: TOURNAMENT COMPETITION BETWEEN CHROMOSOMES
FIGURE 3: WANDERERS IN DEMETIC GROUPING
FIGURE 4: MUTATION IN BINARY STRINGS
FIGURE 5: MUTATION IN GENETIC PROGRAMMING
FIGURE 6: THE CART-POLE PROBLEM
FIGURE 7: CROSSOVER IN GENETIC PROGRAMMING
 
 

List of Charts

CHART 1: ROULETTE WHEEL - POLE ANGLE V'S TIME
CHART 2: TOURNAMENT - POLE ANGLE V'S TIME
CHART 3: EXPECTED VALUE MODEL - POLE ANGLE V'S TIME
CHART 4: ROULETTE WHEEL - CART POSITION V'S TIME
CHART 5: TOURNAMENT - CART POSITION V'S TIME
CHART 6: EXPECTED VALUE MODEL - CART POSITION V TIME
CHART 7: LOG OF THE OBSERVED LEARNING CURVES OF BEST CONTROLLERS
CHART 8: OBSERVED MEAN FITNESS OF EACH SELECTION TECHNIQUE
CHART 9: AVERAGE OF BEST OBSERVED FITNESS OF EACH SELECTION TECHNIQUE
CHART 10: ON-LINE PERFORMANCE
CHART 11: OFF-LINE PERFORMANCE
CHART 12: DISTRIBUTION OF MEANS - ROULETTE WHEEL AND TOURNAMENT SELECTION
CHART 13: DISTRIBUTION OF MEANS - ROULETTE WHEEL AND EXPECTED VALUE MODEL SELECTION
CHART 14: DISTRIBUTION OF MEANS - EXPECTED VALUE MODEL AND TOURNAMENT SELECTION
CHART 15: DISTRIBUTION OF BEST - ROULETTE WHEEL AND TOURNAMENT SELECTION
CHART 16: DISTRIBUTION OF BEST - ROULETTE AND EXPECTED VALUE MODEL SELECTION
CHART 17: DISTRIBUTION OF BEST - TOURNAMENT AND EXPECTED VALUE MODEL SELECTION
CHART 18: SUCCESSFUL RUNS OF ROULETTE WHEEL SELECTION
CHART 19: SUCCESSFUL RUNS OF TOURNAMENT SELECTION
CHART 20: SUCCESSFUL RUNS OF EXPECTED VALUE MODEL SELECTION
 
 

[Stumptown Brewery]