Genetic Programming
Evolutionary Computation
Ying-ping Chen
Dept. of Computer Science, NYCU
Outline
◼ Genetic Programming in Brief
◼ Introductory Example
◼ Representation
◼ Operators
◼ Bloat in Genetic Programming
◼ Example Problem for GP
Evolutionary Computation 2 / 36
A Glance at GP
◼ 1990’s; USA
◼ Early Names
John R. Koza
◼ Genetic Programming. MIT Press 1992.
◼ Genetic Programming II. MIT Press 1994.
◼ Genetic Programming III. Morgan Kaufmann. 1999.
◼ Genetic Programming IV. Kluwer Academic
Publisher. 2003.
Evolutionary Computation 3 / 36
A Glance at GP (cont.)
◼ Typically Applied to Machine Learning
Modeling
Prediction
Classification
Symbolicregression
Programming/control rule generation
Evolutionary Computation 4 / 36
A Glance at GP (cont.)
◼ Attributes
Compete with neural networks and the like
Require lots of individuals → Slow
◼ Features
Tree-like/tree-based representation
Mainlycrossover
Crossover or mutation
Evolutionary Computation 5 / 36
GP: Summary
Representation Tree Structures
Recombination Exchange of Subtrees
Mutation Random Change in Trees
Parent Selection Fitness Proportionate
Survivor Selection Generational Model
Evolutionary Computation 6 / 36
Example: Credit Scoring
◼ Distinguish Good and Bad Customers
◼ Based on the Historical Data
ID No. of Children Salary Marital Status OK?
Id-1 2 45,000 Married 0
Id-2 0 30,000 Single 1
Id-3 1 40,000 Divorced 1
… … … … …
Evolutionary Computation 7 / 36
Example: Credit Scoring (cont.)
◼ The Model Might Be
IF ((NoOfChildren = 2) AND (Salary > 80,000))
◼ THEN good
◼ ELSE bad
◼ In General
IF Rules/Formula THEN Ans1 ELSE Ans2
◼ Try to Find the Rules, Formulae, Models…
Evolutionary Computation 8 / 36
Example: Credit Scoring (cont.)
◼ Search Space
Phenotype: Rules, formulae, programs…
◼ Representation
Genotype
◼ Trees (parse trees)
◼ Instructions (linear genetic programming, LGP)
◼ Graphs
Evolutionary Computation 9 / 36
Example: Credit Scoring (cont.)
◼ Fitness Definition
Correctpercentage
Successful rate
Errors
◼ Supervised vs. Unsupervised Learning
Evolutionary Computation 10 / 36
Example: Credit Scoring (cont.)
◼ The Example Rule Can Be Expressed as
AND
= >
No. of children 2 Salary 80,000
Evolutionary Computation 11 / 36
Representation
◼ Traditionally, Parse Trees; E.g.,
Arithmetic Formula Program
µ ¶
y 1: i = 1;
2 ¢ ¼ + (x + 3) ¡
5+1
2: while i < 20 do
3: i = i + 1
Logical Formula 4: end while
(x ^ true) !
((x _ y) _ (z $ (x ^ y)))
Evolutionary Computation 12 / 36
Representation (cont.)
µ ¶
y
◼ 2 ¢ ¼ + (x + 3) ¡
5+1
Evolutionary Computation 13 / 36
Representation (cont.)
◼ (x ^ true) !
((x _ y) _ (z $ (x ^ y)))
Evolutionary Computation 14 / 36
Representation (cont.)
◼ 1: i = 1;
2: while i < 20 do
3: i = i + 1
4: end while
Evolutionary Computation 15 / 36
Tree-Based Representation
◼ In Other EA Branches
Linear-structured chromosomes
◼ Vectors of bits, integers, real numbers, etc
Fixed size/length chromosomes
◼ Tree-Like Chromosomes
Non-linear structures
Variable size: Depth and width of trees
Evolutionary Computation 16 / 36
Symbolic Expression
◼ Traversal of Parse Trees
Pre-order traversal → Prefix S-expression
◼ +(¢(2; ¼); ¡(+(x; 3); =(y; +(5; 1))))
In-order traversal → Infix S-expression
◼ 2 ¢ ¼ + (x + 3 ¡ (y=(5 + 1)))
Post-order traversal → Postfix S-expression
◼5 1 + y = x 3 + ¡ 2 ¼ ¢ +
Evolutionary Computation 17 / 36
Symbolic Expression (cont.)
◼ Defined by
Terminal set T
Function set F (with defined arities)
◼ Recursive Definition
Terminals are correct expressions
For f in F with arity n and that t1, t2, … tn are
correct, f(t1, t2, …, tn) is correct
No other forms of correct expressions
Evolutionary Computation 18 / 36
LISP Programs
◼ Functional Language
Mathematical ways of thinking
◼ Prefix Notation & Lots of Parentheses
F(x, y, z) → (F x y z)
◼ Untyped/Weakly Typed
Mixture of data and code
Flexibility and versatile
Evolutionary Computation 19 / 36
LISP Programs (cont.)
◼ Lists as Human-Readable Representation
◼ Lists Are Simply Syntactic Sugar
Infix: 1 x 2 x (3 + 4)
LISP: (x 1 2 (+ 3 4))
→
(x . (1 . (2 . (+ . (3 . (4 . NIL))))))
→
Evolutionary Computation 20 / 36
LISP Programs (cont.)
As a tree
Evolutionary Computation 21 / 36
Typical Difference
◼ Creation of Offspring
Usually, GAs / EAs use both crossover AND
mutation with respective probabilities
Originally, GP uses crossover OR mutation in
one child generation event
Evolutionary Computation 22 / 36
Typical Difference (cont.)
GA Loop GP Loop
Evolutionary Computation 23 / 36
Crossover
◼ Most Common Recombination
Exchange two random subtrees of parents
◼ Two Parameters for Crossover in GP
Probability to choose crossover or mutation
Probability to choose the crossover point
◼ Sizes of the Offspring May Vary a Lot
Evolutionary Computation 24 / 36
Crossover (cont.)
µ ¶
y
2 ¢ ¼ + (x + 3) ¡ (a ¢ 3) ¢ (3 + (y + 12))
5+1
Parent 1 Parent 2
Evolutionary Computation 25 / 36
Crossover (cont.)
y
2 ¢ ¼ + ((x + 3) ¡ a ¢ 3) ¢ (3 + (y + 12))
5+1
Child 1 Child 2
Evolutionary Computation 26 / 36
Mutation
◼ Usually, Mutate with Random Subtrees
◼ Also, Two Parameters for Mutation in GP
Probability to choose crossover or mutation
Probability to choose the mutation point
◼ Sizes of the Offspring May Vary a Lot, Too
◼ Growing Emphasis on Mutation
0 (1992, Koza) → 0.05 (1998, Banzhaf et al.)
Evolutionary Computation 27 / 36
Mutation (cont.)
µ ¶
y
2 ¢ ¼ + (x + 3) ¡
5+1
2 ¢ ¼ + ((x + 3) ¡ y)
Parent Child
Evolutionary Computation 28 / 36
Selection
◼ Parent Selection
Typically, fitness proportionate selection
(Very) large populations → Over-selection
◼ Group 1: Top x%; Group 2: Others
◼ Select 80% parents from group 1; 20% from others
◼ Population size and percentage for group 1
(1000, 32%); (2000, 16%); (4000, 8%); (8000, 4%)
◼ Empirically, “rule of thumb”
Evolutionary Computation 29 / 36
Selection (cont.)
◼ Survivor Selection
Typically, generational model w/o elitism
◼ All parents die; whole new populations
1998, Banzhaf et al
◼ Generational model GP and steady-state GP
Current trend
◼ Steady-state scheme for GP might be better
Evolutionary Computation 30 / 36
Initialization
◼ Maximum Tree Depth Dmax
◼ Ramped Half-and-Half
Equal probability
Full method: All the way to Dmax
◼ Depth < Dmax, from F; otherwise, from T
Grow method: Up to Dmax
◼ Depth < Dmax, from F or T; otherwise from T
Evolutionary Computation 31 / 36
Bloat in Genetic Programming
◼ Chromosome of Variable Sizes
Tree sizes increase over generations
Survival of the fattest
Over-fitting individuals prevail?
◼ Still Hot in the Current Research
Why it happens?
Meaningful ways of interpretation?
Evolutionary Computation 32 / 36
Bloat in GP (cont.)
◼ We Need Countermeasures
Maximum tree size for operators
◼ Prevent oversized offspring from being generated
Parsimony pressure
◼ Penalty on fitness to penalize oversized offspring
◼ Occam’s Razor, AIC, MDL ideas
Multiobjective techniques
◼ Add-on objective to minimize tree sizes
Evolutionary Computation 33 / 36
“Physical” Environments
◼ Passive Solutions vs. Active Programs
Models/formulae and executable code
◼ Environments and Solutions
Affect/change each other
◼ Fitness Obtained via Simulation
Expensive and extremely expensive
◼ Example: Robot Controller
Evolutionary Computation 34 / 36
Example: Symbolic Regression
◼ Data Points: (x1; y1); (x2; y2); : : : ; (xn; yn) 2 R2
◼ Find f(x) to “Go through” All Points
◼ Might Use GP to Solve the Problem
Choose the representation
◼ F = f+; ¡; ¢; =; exp; sin; cosg; T = R [ fxg
Minimize the Error
n
X
◼ error(f ) = (f (xi) ¡ yi)2
i=1
Evolutionary Computation 35 / 36
Summary & Conclusions
◼ Genetic Programming in a Nutshell
Representation, operators, & control-flow
◼ Features and Characteristics of GP
◼ Problems for Using GP
◼ Evolving Designs of Circuits
◼ Evolvable Hardware
Evolutionary Computation 36 / 36