Next:
Contents
Scaling of Program Fitness Spaces
W. B. Langdon
C
OMPUTER
S
CIENCE,
U
NIVERSITY
C
OLLEGE,
L
ONDON
Foundations of Genetic Programming
Chapters 7 and 8
W.Langdon@cs.ucl.ac.uk
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 ...
Bill LANGDON
2001-12-05
All Outputs Equally Likely
Linear Program