Transcript mstreeter_gecco_2001..

Automated Discovery of Numerical Approximation
Formulae via Genetic Programming
Matthew Streeter
Lee A. Becker
Worcester Polytechnic Institute
Motivations
•
Approximations have value in formal mathematics and
industrial settings
•
Discovery of approximation formulae requires human
insight or numerical analysis technique (f.e. Taylor series,
Padé approximations)
•
Genetic programming provides general automated
technique with potential improvement over existing
methods
Evaluating Approximations
•
Given cost and error, utility function assigns value to an
approximation
•
Reasonable utility function assigns higher value to
approximations with lower error and cost
•
Pareto front represents set of approximations which are
best under some reasonable utility function
Experimental Approach
•
Calculated cost of each expression by assigning fixed
cost associated to each primitive operator
•
GP system returns Pareto front with respect to cost and
error as result of a run
•
Used parameter settings from (Koza 1992) including
populations size of 500, but with generation limit of 100
•
Took combined Pareto front for population histories 50
independent runs
Rediscovery of Harmonic Number Approximations
•
Hn  Sigma(i=1,n,1/i)
•
Asymptotic expansion: Hn =  + ln(n) + 1/(2n) - 1/(12n2)
+ 1/(120n4) - . . . (  0.57722)
•
Function set: {+, *, RCP, RLOG, SQRT, COS}
•
Fitness cases taken as first 50 points of Hn series
•
Candidate approximations simplified through Maple
EVOLVED EXPRESSION
1. ln(x)+.5766598187+1/(sqrt(ln(x)+.5766598187+1/(1/x+2*x
+.6426220121)+x^2)+x)
2. ln(x)+.5766598187+1/(2*x+1/(1.219281831+ ln(1/(ln(x)
+.5766598187))+x))
3. ln(x)+.5766598187+1/(2*x+1/(1.285244024+ ln(1.734124639
+2*x)))
4. ln(x)+.5766598187+1/(2*x+1/(2.584025920+ ln(x)+
1/(3.007188263+x)))
5. ln(x)+.5766598187+1/(2*x+1/(.5766598187 + 1/x+x))
6. ln(x)+.5766598187+1/(2*x+.3592711879)
7. ln(x)+.5766598187+1/(2*x+.3497550998)
8. ln(x+.5022291180)+.5779513609
9. ln(x+.4890238595)+.5779513609
10. 0.5965804779+ln(x)
11. 3.953265289-4.348430001/x
12. 3.815981083
ERROR
0.0215204
COST
39.1
RUN
22
GEN.
32
0.0229032
35.8
22
35
0.0264468
26.9
22
37
0.0278816
25.9
22
49
0.0286254
0.0293595
0.0297425
0.0546846
0.0653603
1.44089
20.2786
31.0297
15.7
13.4
11.4
10.3
10.2
10.1
2.2
0
22
22
22
40
40
49
3
10
36
37
42
28
21
49
1
4
Evolved Harmonic Number Approximations
•
Candidate solutions 8-10 are
variations on first two terms of
asymptotic expansion
TERMS
1
2
3
4
EXPRESSION
0.57722
0.57722 + ln(n)
0.57722 + ln(n) + 1/(2n)
0.57722 + ln(n) + 1/(2n)
- 1/(12n^2)
ERROR
150.56
2.1209
1.2866e-1
6.8393e-3
Terms of Asymptotic Expansion
•
Candidate solutions 2-7 are variations on first 3 terms
•
Euler’s constant discovered as: (RCP(SQRT(*
RLOG(1.90146))))
4.67956
Rational Polynomial Approximations to
Functions of a Single Variable
•
Function set: {*,+,/,-}
•
Evolved approximations to 5 common functions: ln(x),
sqrt(x), arcsinh(x), exp(-x), tanh(x)
•
Re-evaluated Pareto front through Maple cost and error
procedures
•
Approximated over large interval to give evolutionary
technique the advantage
Pareto fronts for approximations to ln(x)
f(x) = sqrt(x)
f(x) = arcsinh(x)
f(x) = exp(-x)
f(x) = tanh(x)
Approximations of Functions of Multiple Variables
•
Possible to use single-variable techniques by combining and
nesting approximations
•
This cannot be done for all functions, f.e. f(x,y) = x^y
•
Genetic programming used to evolve approximating surface
for f(x,y) = x^y over area 0 <= x <= 1, 0 <= y <= 1
Target function: f(x,y) = x^y
Evolved expression: f(x,y) = x/(y2+x-xy3)
Evolutionary Refinement of Approximations
•
New fitness formula: 1/(1+[error multiplier]*[error])
•
Refined approximations evolved to sin(x) over interval
[0, /2]
•
Refined 3 approximations whose error function looked
simple
•
Original Pareto front contains 7 approximations; first 4
are refined
EVOLVED APPROXIMATION
1. [x-x^2*(x-.06687879829)/(4.91791+x)] + [-.2932035419*
x/(151.1461467*x+ 191.8603473)]
2. [x-x^2*(x-.06687879829)/(4.91791+x)] + [-.8756705834e-3*x]
3. [x-x^2*(x-.06687879829)/(4.91791+x)] + [-.5786124498e-3]
4. [x-.137486*x^2*(.137486+x)] + [.3290962388e-3]
5. -.3508427242*(-3.37336+x)*x
6. .0840785+.739616*x
7. x-.0758385
COST
7
ERROR
.3095090765e-3
5
4
3
2
1
0
.3462600904e-3
.4676456530e-3
.002416170399
.02458904516
.08566001170
.2023284751
Refined Approximations to sin(x) over [0, /2]
Summary and Conclusions
•
Rediscovered terms of asymptotic expansion for
Harmonic numbers
•
For common mathematical functions approximated over
a large interval, evolved solutions are superior to Padé
approximations under some reasonable utility function
•
Evolved approximations can be refined
•
Evolved approximations for functions of multiple
variables to which Padé approximation cannot be applied
Future Work
•
Iterative refinement, refinement of evolved
approximations using numerical analysis technique &
vice versa
•
Larger population size
•
Use of seed individuals corresponding to existing Padé
approximations, Taylor series (see late-breaking paper,
“Toward a Better Sine Wave”)
•
More recent GP features: automatically defined
functions, architecture-altering operations
•
Ideal application would be to discover a genuinely new
approximation formula