Transcript Genetic Programming: The Basics

Genetic Programming
• Using an evolutionary process to design computer programs.
• Automatic Programming where the computer is only told WHAT the
final program should do, not HOW to design it.
– In traditional AI Automatic Programming (AP), the system reasons
through a complex design logic, the HOW (derived from human
software engineers) to generate code that is easy to understand and
modify.
– In GP, the system only knows WHAT the system should do. The
WHAT is the basis for fitness tests, but there is no step-by-step
design logic.
– The GP simply generates whole solutions (as random combinations
of previous solutions) and tests them…just like in nature.
– The resulting programs are often very efficient, but terribly hard to
understand and modify…just like in nature.
Overview
Goal: Give enough background of both general principles and
essential details so that you can begin designing a GP
system.
•
•
•
•
•
Basic GP Design Issues
Multiplexer Example
The closure property for GP function sets.
Genotype Representations
Development and Execution
– Going from genotype to phenotype
– Running the phenotype
Key GP Design Issues
• Phenotype Representation - The general format of solutions.
• Genotype Representation - This defines the size of the search space.
– Primitives: Terminals & Functions
– Form: Linear, Tree, Graph
• Development (Morphogenesis) - How are genotypes converted into
phenotypes?
• Fitness Function - This defines the texture of the search space.
• Fitness Cases - Test set for the phenotypes. The “environment” in
which the individuals must “live”.
• Genetic Operators - How are new genotypes generated from old ones?
– Standard or specialized mutation and crossover.
• Selection Mechanism – How are fitness values converted to areas on
the roulette wheel?
• Phenotype Execution Process– Interpreted or Compiled?
GP Primitives
• GP Terminals - leaf nodes of a GP tree
– Args/params (to the main GP function or “genetic program”)
– Constants
– Zero-argument primitive functions
• GP functions – non-leaf nodes of a GP tree
– Primitive functions (building-blocks) of the genetic program
– Arity = # of arguments (must be pre-defined)
– Many types
•
•
•
•
•
•
•
•
Boolean:
Arithmetic:
Transcendental
Conditional:
Loop
Block
Assignment
Memory access
and, or, not, xor, nand…
+, -, *, % (protected division)
sin, cos, exp, expt, rlog (protected log)
if, case, switch…
while, repeat…
progn2, progn3…
assign (val to var)
mem (retrieves value in a given memory location)
Fitness
Fitness Function: Assesses the performance of a phenotype and outputs a
fitness score.
Raw fitness = basic performance score (e.g., # of correct mappings) of the
phenotype.
Standardized Fitness = scaled fitness so that 0 is always the best value.
Normalized fitness = scaled fitness to range [0 1]
• In practice, raw fitness is often used, without any scaling.
• The fitness function should give a continuous grade of credit, not just
yes/no info.
• It should serve as a heuristic to indicate the closeness of a phenotype to
an optimal phenotype, and thus provide useful information to the
genetic search process.
The Fitness Landscape of the Search Space
• Genotype representation determines the size and density of the search space
• Fitness function determines its texture (rough, smooth, etc.).
• Rough landscapes are harder to search, since the partial information provided by
the fitness function does not have good heuristic value. E.g. A local max gets a
high fitness score though it may be quite distant from the global max.
Fitness
Func
(Testing is performed at this level)
Phenotype
Genotype (Search is performed at this level)
Boolean Multiplexer Problem
• Design a Boolean expression of that takes N = K + M inputs, where
the K bits a(0)…a(K-1) denote an address/index A, and the data bit
d(A) from d(0)…d(M-1) is the desired return value. In other words,
the address bits select a data bit.
• Standard problem sizes: log2(M) + M
• 1+2=3
• 2+4=6
• 3 + 8 = 11
Address
a0-a2
Data
d0-d7
11-bit
Mux
dA
Boolean Multiplexer Solutions
3-bit Mux
(if a0 d1 d0)
6-bit Mux
(if a0
(if a1 d3 d1)
(if a1 d2 d0))
11-bit Mux
(if a0
(if a1
(if a2 d7 d3)
(if a2 d5 d1)
(if a1
(if a2 d6 d2)
(if a2 d4 d0)))
*There are MANY other solutions for the 6-bit and 11-bit cases
Primitives for Mux Design using GP
• Terminals:
– Address bits: a0, a1… and
Data bits: d0,d1…
• Functions:
– GOR(2)
(defun gor (x y) (if (or (> x 0) (> y 0)) 1 -1)
– GAND(2)
(defun gand (x y) (if (and (> x 0) (> y 0)) 1 -1)
– GNOT(1)
(defun gnot(x) (if (> x 0) -1 1))
– GIF(3)
(defmacro gif (condition act1 act2)
`(if (> ,condition 0) ,act1 ,act2))
• Closure: All functions output an integer, and all functions accept
integers for all their arguments.
• Truth value of an integer (I) is T iff I > 0. For this problem, the acts in
gif are any func calls or terminals.
Fitness Testing of GP Multiplexers
• For an n-bit Mux, there are 2n test cases: all possible combinations of
input bits.
• Each case has a correct output: the value of dA, where A is the integer
encoded by the address bits.
• For each individual program in the population
– hits = 0
– For each of the 2n cases:
• Set the values of primitives a0..ak and d0…dm according to
their values in the test case.
• Run the individual program with bindings for ai’s and dj’s from
above.
• Compare the output of the program, O*, to dA.
• If 0* = dA, then hits = hits + 1.
– Fitness(individual) = hits
GP Tableau (Koza, 1992)
Parameters
Objective:
Terminal Set:
Function Set:
Fitness Cases:
Fitness Func:
Population Size:
Crossover Probability:
Mutation Probability:
Selection Mechanism:
Termination Criteria:
Max # Generations:
Max Tree Depth:
Max Init Tree Depth:
… many others possible…
Values
Evolve an 11-bit Multiplexer
a0,a1,a2,d0,d1…d7
Gif, Gor, Gand, Gnot
All 211 input cases
# outputs correctly predicted.
4000
75%
5% (per individual)
Sigma Scaling
None
50
15
6
GP Multiplexer Solutions (Koza, 1992)
Generation 1: Fitness = 1408
(gif a0 (gif a2 d7 d3) d0)
Generation 4: Fitness = 1664
(gif a0 (gif a2 d7 d3)
(gif a2 d4 (gif a1 d2
(gif a2 d7 d0))))
Generation 9: Fitness = 2048 (perfect)
(gif a0 (gif a2 (gif a1 d7 (gif a0 d5 d0))
(gif a0 (gif a1 (gif a2 d7 d3) d1) d0))
(gif a2 (gif a1 d6 d4)
(gif a2 d4 (gif a1 d2 (gif a2 d7 d0)))))
* Population size = 4000!!
The Closure Property of GP Functions
• Genetic programs are randomly generated and combined, so ANY
function could end up with the output of ANY OTHER function (or
itself) or ANY terminal as its input.
• So, EVERY GP primitive function must be capable of accepting the
output of ANY primitive function for ANY of its input arguments.
This is the closure property.
• Protected versions of functions like Division and Log are needed to
handle inputs of 0, or negative numbers, respectively.
• The only constraint that classic GP systems check when generating
trees is function arity: each function call gets exactly the number of
arguments that it requires.
• Once the initial population is generated, recombination of programs
via crossover will never violate the arity constraints, so no extra
checking is necessary.
Closure Tricks
• If mixing booleans and arithmetic funcs, rewrite your booleans to
interpret every number other than 0 as TRUE, and have them output a
0 for FALSE and a 1 for TRUE. Or, view all neg numbers as FALSE,
pos as TRUE, and then output -1 or 1.
– (GAND 8 0) => 0
(GOR 5 -3.2) => 1…
• All action funcs such as Move-Forward, Turn-Left, etc. should return a
number. For example, they can return a number that denotes TRUE if
they succeed, FALSE otherwise.
• Use the MOD (modulo) operator to convert numeric inputs into indices
in collections. For example, if your genetic program includes a
memory buffer of size 4, then a call to (ASSIGN 33 12) could be
interpreted as “Assign the value 12 to MEM(1)”, since 1 = 33 Mod 4.
Or, (COPY 17 15) could be “Assign the value at MEM(1) to
MEM(3)”, since 17 Mod 4 = 1 and 15 Mod 4 = 3. If the inputs are real
numbers, then they’ll need to be rounded first.
• Disadvantage: Using these tricks, any program is legal, and many
genetic programs can represent the exact same procedure (I.e., N-to-1
mapping between representation/search space and solution space.
Hence the search space can be huge!
Strongly-Typed GPs
•
•
•
•
Restrict the set of legal programs by requiring the inputs to each function to be
of specified types => Great reduction in representation/search space.
Each function declaration must include: types for all arguments + output/return
type. Also, each terminal must be typed. A func’s type = type of return value.
E.g., GIFACT(bool, act1, act2) => real - if boolean condition is true, then
perform action 1, else action 2. The return value is a real, denoting, for
example, something about the actions, such as how far the agent moved while
doing act1 or act2.
Type-checking needed during both program generation + crossover.
– E.g. f(bool,act) => dir
g(real) => real
h(dir) => bool
Generation
Crossover
f
f
Must be
bool
Must be
act
True
3
Turn
Left
g
h
7
Left
??
GP Genotype Representations
• It is important to distinguish between the static form of the genotype
and the pattern of interactions that it generates when its corresponding
phenotype is executed.
• Static Forms
– Linear – sequence of operations
– Tree - node-arc rep with all nodes (except the root) having 1
parent. Classic GP!
– Graph – node-arc rep with no restrictions on interconnections
Linear GP Genomes
• Genome
– Linear string of commands (in any language or machine code).
• Execution structure of the Genome:
– Linear: sequence of independent commands.
– Graph: inter-dependent commands due to shared memory (e.g.
registers)
– Tree: Nested sequence of commands with only local interactions the results from one command are available ONLY to the command
that it is a nested argument of . To make it available many places,
you have to recompute it at several points in the tree.
f
(f 6 (g 1 (h 3 4)))
g
6
1
h
3
4
Linear Genomes with Linear & Graph Execution
Linear genome with linear execution
- Each action is independent
Turn left
Go forward
Turn right
Turn right
:
Linear genome with graph execution
- Actions are inter-dependent via shared memory registers.
A:
B:
C:
D:
E:
Memory
B
1: C = A + B
2: D = C + A
3: E = D + D
4: A = E + B
:
C
D
A
E
1
2
4
3
Graph-Based GP
• PADO (Teller & Veloso, 1995)
• Each node must:
– Compute using stack and/or indexed memory
– Decide on the neighbor node to move to.
+
*
12
push/pop
213
55
127
8
Run-time
Stack
• Read/Write work only with indexed memory
• Other nodes pop values from the stack, compute
a function, then push result onto the stack
start
7
end
XY
read
write
0
61
1
32
2
197
3
4
404 88
Indexed Memory
Development & Execution of GP Programs
gtype
ptype
1
Fitness
gtype
Application
Language
gtype
GP-App
interpreter
Devp
Exec
3
ptype
Source
Language
Fitness
2
4
Source
interpreter
compiler
Fitness
ptype*
ptype
cpu
Machine
Language
Executing a Genetic Program
• Interpreting the Genotype
– Hand-coded interpreter reads through the genotype and performs
the appropriate actions during fitness testing.
– Done in Lisp and C++.
– Very slow, but better than compiling when there are not many
fitness cases to run.
• Compiling the Genotype
– Hand-coded wrapper routines for the genotype enable its
compilation to machine code, which then runs during fitness
testing.
– Easy in Lisp.. Hard in C++
• Genotype IS Machine Code
– No compilation necessary.
– Possible with any type of machine code.
– Extremely fast (60 x faster than compiled C++)
– Limited expressibility within a reasonable program size.
Interpreting a GP Genotype
Sample Genotype: (gor (gand A0 D1) D3)
(defun interpret (sexpr)
(cond
((equal sexpr ‘A0) (fetch-input-value 0))
((equal sexpr ‘A1) (fetch-input-value 1))
:
((equal (first sexpr) ‘gnot)
(if (> (interpret (second sexpr)) 0) -1 1))
((equal (first sexpr) ‘gor)
(if (or (> (interpret (second sexpr)) 0)
(> (interpret (third sexpr)) 0))
1 -1))
:
*You can compile the interpreter, but then you still have to interpret the
genotype code for EVERY fitness test case.
*This is easy in C++ too, but you’ll have to deal with the genotype tree
explicitly: C++ doesn’t handle nested lists (I.e. trees) implicitly the
way Lisp does.
Interpreter for Prefix
Linear Prefix of (+ (* (- 3 4) 5) (/ 8 4)) is:
(+ * - 3 4 5 / 8 4)
(defun interp-prefix (symbols)
(labels ((num-args (func) 2)) ;; Local function
(let ((sym (car symbols)) ;; Declare 4 local vars
(evaled-args nil)
evaled-arg remains)
(cond ((and (symbolp sym) (fboundp sym)) ;; symbol is func name
(setf remains (cdr symbols))
(dotimes (i (num-args sym))
(multiple-value-setq (evaled-arg remains)
(interp-prefix remains))
(push evaled-arg evaled-args))
(values (apply sym (reverse evaled-args))
remains))
(t ;; symbol is not a function name
(values sym (cdr symbols)))))))
Interpreter for Postfix
The Postfix of (+ (* (- 3 4) 5) (/ 8 4)) is:
(3 4 - 5 * 8 4 / +)
(defun interp-postfix (symbols)
(let ((stack nil) args) ;; the operand stack
;; 2 Local functions: num-args and interp
(labels ((num-args (func) 2)
(interp (symbols)
;; the main, recursive local func
(cond ((null symbols) (pop stack))
((and (symbolp (car symbols)) ;; func symbol
(fboundp (car symbols)))
(setf args nil)
(dotimes (i (num-args (car symbols)))
(push (pop stack) args))
(push (apply (car symbols) args) stack)
(interp (cdr symbols)))
(t (push (car symbols) stack)
(interp (cdr symbols))))))
;; the main program
(interp symbols))))
Variable Binding in GP
• Assume we convert the genotype into code that is executable in the
application language (e.g. Lisp, C++) without the aid of a specialpurpose GP interpreter. Note that the code may still be interpreted, but
now it’s the general LISP language interpreter that does the job.
• When this code runs, how do we get the proper variable bindings from
a fitness case into the code?
Fitness Case
(gif A0 D1 (gor A1 D2…)
??
• Simple (ugly) solution
– Declare A0,A1…D0, D1… as global variables
– Update them with each new fitness case.
– Use Lisp’s interpreter, EVAL.
• (eval ‘(gif A0 D1 (gor A1 D2….)))
A0:
A1:
D0:
D1:
D2:
D3:
1
0
1
1
0
1
Wrapping with a Lambda
A slightly more elegant solution
? (setf ptype
(eval (append ‘(lambda (A0 A1 D0 D1 D2 D3)) (list genotype))))
This creates an unnamed phenotype function of 6 arguments. The body
code of the phenotype is the genotype s-expression.
E.g. (lambda (A0 A1 D0 D1 D2 D3)
(gif A0 D1 (gor A1 D2….)))
? (apply ptype fitness-case)
This calls the phenotype function with its arguments bound to the
fitness case. No global variables are needed.
(dolist (case fitness-cases)
(let ((res (apply ptype case)))
.. compare res to expected result
.. update error sum … )
Compiling the Genotype in Lisp
(setf ptype
(compile nil (append ‘(lambda (A0 A1 D0 D1 D2 D3))
(list genotype))))
Lisp’s compile function allows us to compile code at run-time! The first
argument to compile (nil in this case) is the name to be given to the
compiled function.
Sometimes, eval will automatically compile its argument too, but only
within the scope of the global environment.
Eval and compile are not recommended for normal Lisp applications, but
GP is special since it must create executable code on the fly (i.e. at run
time).
Run-time compiling is very difficult in C++ and similar languages. GPs
in these other languages normally rely on a hand-written interpreter.
Machine-Code GP
• Cramer (1985), Nordin (1994), Crepeau (1995)
• Genome = Linear sequence of Machine-Code instruction, often in binary.
• Extensive use of machine registers allows storage of intermediate results,
which can be used MANY different places in the code. Hence run-time
structure ressembles a GRAPH (not a tree)
• E.g.
– A=A+ B
• 011 (op code for reg-reg add) 000 (dest reg 0) 000 (src 1 = reg 0) 001 (src 2 = reg 1)
– C=A+5
• 100 (code for reg-const add) 010 (dest reg 2) 000 (src1 = reg 0) 101 (src2 = const 5)
– GOTO 1
• 111 (code for jump) 000000001 (destination address)
• By using the actual machine codes for your machine, the GP creates fullycompiled and assembled programs => 60X faster than C++ GP interpreters.
Maintaining Legal Genomes
• Tree-based GP
– As long as closure holds or if strong-typing is
used, then subtree swapping does not create
illegal programs.
• Linear or Graph-based GP
– Crossover can create invalid programs, so
special care must be taken.
Maintaining Legal Machine Code Programs
Generating:
Once an op-code is (randomly) selected, restrict the operands to legal
ones.
E.g. if it’s a reg-reg add instruction, make sure the operands are legal
register indices (At the machine level, closure tricks like modulo are
not performed!!)
Crossing over:
Swap whole-instruction sub-sequences between individuals: never pick
the crossover point inside of an instruction.
Mutating:
For each operator, define a set of legal mutations.
E.g. Legal mutations for a reg-reg subtract: reg1 = reg2 - reg3
reg1 = reg2 + reg3
reg2 = reg2 - reg3
reg3 = reg2 - reg1
reg1 = reg2 AND reg3 ….
Maintaining Legal Linear Genomes
• For genomes with linear or graph execution modes, the same
techniques as for constrained generation, crossover and mutation of
machine-code genomes are applicable (see below).
• For genomes with tree-type execution structure, there is no standard
instruction length, since each operator has subtree operands of widelyvarying size. Hence, different considerations must be taken within the
genetic operators to preserve program validity, I.e. to insure that the
resulting linear genome represents a well-formed tree.
• Mutation: You cannot just replace an operator or operand with any
other, since:
– Arities may vary among functions, so a 3-argument operator cannot be
replaced by a 2-argument operator .
– Terminals cannot replace operators, or vice versa.
• Crossover: You cannot just swap linear segments unless each
represents a complete sub-tree.
• In short, genetic operators working on linear representations of treestructured programs cannot forget that they are really working with
trees!!
Linear Prefix-Coded Genomes for GP Trees
• Keith & Martin (1994)
• (f 6 (g 1 (h 3 4)))
represented as
f6g1h34
• Given the arity of each function, a recursive interpreter for these
strings is simple to write in any language.
• Preserving program validity
– Generating: randomly choose terminals & functions, but always
check that the new node is the root of a subtree for SOME earlier
node. Also, keep track of current tree depth so as not to exceed the
maximum depth bound. When at maximum depth, use only
terminals.
– Mutating: Only replace function names with the names of samearity functions, and always replace terminals with terminals.
– Crossover: Only swap segments that represent complete subtrees.
– Once found, whole subtrees can be changed to other subtrees as a
form of mutation.
– Key trick: finding the subtrees.
Subtree Detection in Prefix-Coded Genomes
Use arity info, where arity(func) = number of args; arity(terminal) = 0.
Procedure Random Subtree Fetch:
sum = 0
Begin at any random array element, A(j).
k=j
While sum <> -1 and A(j) <> end-of-array Do
sum = sum + (arity(A(k)) - 1).
k=k+1
end while
If sum = -1, then subtree = A(j)…A(k)
Tree
(gor (gand (gnot 2) (gor 5 8)) 1)
Subtree
Linear Genome
[ Gor Gand Gnot 2 Gor 5 8 1 ]
Sum:
1
1
0
1 0 -1