Transcript Evolutionary Program Construction

Deductive and inductive
methods for program
synthesis
Jelena Sanko, Jaan Penjam
Institute of Cybernetics
October 29, 2005
Agenda
•
•
•
•
Program construction
Inductive program construction
Experiments
Conclusions
Program construction
Inductive programming
Set of
behaviours
Requirements
specification
algorithm
program
Deductive programming
x (P (x )  yR (x,y ))
Problem Statement
S : x t
p
x
R1
y
R2
R3
t  p (x )
p  R 6(R 5(R 4(R 3(R 1(x )))))
p  R 1; R 3; R 4; R 5; R 6
composition
R4
t
R6
u
z
R5
v
Scoring of programs
s - measure of fitness
s : 
pi  
pi=R1; R2; R3; R4; R5; ... ;R6
Square root fitness measure of the program p
IN
OUT
x1
t1
x2
t2
…
…
xn
tn
n
2
(
p
(
x
)

t
)

i
i
s ( p )  i 1
n 1
   l (p)
Program synthesis as optimization
z  0,1
s
z0
1
h
P=R2; R3; R5; R6; R2; …; R6
z
Coding of programs
h 0,1  
z = 0,23562…7
h
p=R2; R3; R5; R6; R2; …; R6
Coding of programs (2)
PR
1
,2
M(P) - State
Transition Machine
6
x
3
xy
3
2
1,
xyz
4
computational model
R1
x
R2
R3
R4
y
t
R6
u
z
R5
v
xz
vxyz
4;5
4
vxz
2
1,
5
uvxyz
6
tuvxyz
2
1,
5
4;5
uvxz
Coding of programs (3)
xy
x
xz
4
xyz
4
z = 0.912
1
0
0
0.33
0.66
1
vxz
p=R3; R4; . . . 
uvxz
vxyz
5
p=R3; . . . 
4;5
uvxyz
6
tuvxyz
P=R3;R4;R1;R5;R6
5
4;5
Function to be optimized (f(z))
s
z  0,1
1
z
Optimization technique
-Differential Evolution,
Rainer Storn and Kenneth Price
DE is a method for finding extreme points of real-valued
multi-modal functions
DE is a heuristic method that can be used for optimization of
non-differentiable functions in continuous spaces
The convergence rate of the floating-point encoded DE
is more than 10 times higher than the convergence rate
of the traditional binary encoded GA
Experimental Data
R1
x
R2
R3
R4
y
t
R6
u
z
R5
v
I(R1)=“y:=ln(x)”
I(R2)=“y:=exp(-x)”
I(R3)=“z:=x^3+6x”
I(R4)=“v:=2(x^2+z)”
I(R5)=“(u,z):=(v+6,v/2)”
I(R6)=“v:=0.16yu/7.85^4”
P={(0.75,1.87*10^-07), (0.70, 1.04*10^-07)
(0.65,5.44*10^-08), (0.60,2.61*10^-08)
(0.55,1.17*10^-08),(0.50, 3.40*10^-09)}
P.M. Murphy and D.W. Aha,
Uci repository of machine learning databases
Experimental Data (2)
I(R2)=“y:=exp(-x)”
I(R3)=“z:=x^3+6x”
I(R4)=“v:=2(x^2+z)”
1
,2
I(R1)=“y:=ln(x)”
x
3
xy
3
2
1,
xyz
I(R5)=“(u,z):=(v+6,v/2)”
I(R6)=“v:=0.16yu/7.85^4”
The optimal solutions like 0.37362, 0.40419,
0.795112 correspond to the following sequence
of relations “R2;R3;R4;R5;R4;R5;R4;R5;R6”
4
xz
vxyz
4
vxz
2
1,
5
4;5
uvxyz
5
2
1,
4;5
uvxz
6
tuvxyz
The optimal solution of the problem obtained by the DE method
corresponds to the proposed by Knut Angström functional relation:
E ( )  0.016e t (t 3  3t 2  6t  6) / 7.85 4 ,
where
t  7.85 / 
Conclusions:
• The inductive approach to program construction can
promote control over construction process and take an
appropriate decision when several solutions are available
• IPS uses interpretation of relations and a fitting function
• IPS considers all programs and selects the best
• The research is in progress...
• IPS strategy need to be checked in practice and
extension to high order constraints is required
?