W. B. Langdon
*
Foundations of Genetic Programming
*
Chapters 7 and 8
W.Langdon@cs.ucl.ac.uk

COMPUTER SCIENCE, UNIVERSITY COLLEGE, LONDON

- Contents
- Number of programs v. size, various problems
- Distribution of Binary Trees by size and height
- Distribution of Binary Trees by size and height
- Gradient in Distribution of Binary Trees
- Proportion of NAND trees: 2 input logic function
- Proportion of NAND trees: 3-equivalence class
- Proportion of NAND trees: 4-equivalence class
- 3-equivalence class {AND, OR, NAND and NOR}
- {AND, OR, NAND, NOR and XOR}
- Ones 6-input {AND, OR, NAND and NOR}
- Even-6 {AND, OR, NAND and NOR}
- Even-6 parity {AND, OR, NAND, NOR and XOR}
- Even-6 full tree {AND, OR, NAND and NOR}
- Fitness Sextic Polynomial
- Artificial Ant
- Artificial Ant
- Proof Linear: Model of Computer
- Proof Linear: Execution of computer program
- Instructions as Transformation Matrices
- All Programs
- Symmetric All Outputs Equally Likely
- The Chance of Finding a Solution
- An Illustrative Example
- An Illustrative Example: Instruction Set
- An Illustrative Example: Limiting Probabilities
- How big do programs have to be?
- Probability of Long Solution if Asymmetric
- Long Linear Random Programs Don't Generalise
- Large Random Binary Trees
- Proof Trees
- Longest path Linear Program
- Proof Trees
- Consider all programs
- Propergate Up Tree
- Propergate Up Tree: Average Level 2
- Propergate Up Tree: Level 3
- Convergence of

Average Function Transition Matrix - Short Side Branches
- Example: One bit AND, NAND, OR and NOR
- Proof Trees: Function Implemented
- Example 2:
*n*=2 bit AND, NAND, OR and NOR - Example 2:
*n*=2 bit AND, NAND, OR and NOR - Even-6 Parity (EQ) convergence to theory
- Faction of Parity Solutions, Order 2-13
- Automatically Defined Functions
- Memory
- Turing Compete: recursion or iteration
- So what?
- Summary: Long Random Linear Programs
- Summary: Big Random Tree Programs
- Conclusions
- About this document ...