Download generic-function-finder.hqx (156,520 KB)
From: "Aaron Golden"
Subject: Abstract for "Genetic Function Finder.sit.hqx"
Genetic Function Finder by Aaron Golden
Contents
-What is GFF? (Genetic Function Finder)
-How does GFF work?
-How to use GFF
-Limitations
-Random Function Finder
-FAQ (Frequently Asked Questions)
-Comments
What is GFF? (Genetic Function Finder)
Genetic Function Finder is a program that searches for a function that will
produce certain points on a two dimensional coordinate plain. For example,
the function 'y = x' produces the points (1, 1), (2, 2), etc. Genetic
Function Finder uses a survival of the fittest environment, to evolve the
correct function by random mutations. The point of GFF isn't really to find
the correct function, but to demonstrate a kind of evolution.
How does GFF work?
Genetic Function Finder starts by taking three points (given by the user)
and generating ten random arithmetic strings. Then GFF evaluates each
string and finds its value for each point. For example the string 'x+1'
would yield '1' if 'x = 0', '2' if 'x = 1', '3' if 'x = 2'. GFF finds the
difference between the results of each string, and the 'y' values for each
point the user gave it.
Here's an example:
1. The user gives the points: (1, 2) (2, 3) (3, 4)
2. GFF produces a string, S: 'x + x - 2'
If 'x = 1' then 'S = 1 + 1 - 2 = 0'
If 'x = 2' then 'S = 2 + 2 - 2 = 2'
If 'x = 3' then 'S = 3 + 3 - 2 = 4'
3. GFF finds the difference between the results of the random string, and
the real results.
Random string yields: 0, 2, 4.
Real results are: 2, 3, 4.
(2 - 0) + (3 - 2) + (4 - 4) = 3
The total error of this string was '3'.
4. GFF produces nine more strings and finds the total error of each of
them.
5. GFF then erases the strings with the largest five errors. (They die)
6. The best five strings from this generation are duplicated. (They
reproduce)
7. The duplicate strings are mutated randomly to stimulate evolution.
8. The process is repeated, generally getting better and better results each
generation until the correct string appears.
How to use GFF
When GFF first starts up it will ask for three points. These are in the
form of (x, y) coordinates. For GFF to read them properly they should be
written without the parenthesis or commas, but with spaces between the
numbers. For example:
GFF can't read this: (1, 2) (2, 3) (3, 4)
or this: 1, 2, 2, 3, 3, 4
or this: 1 2, 2 3, 3 4
but it can read this: 1 2 2 3 3 4
If the points aren't written in this general format: "x y x y x y" then
there is no telling what GFF will read the points as.
After you enter the points GFF will ask for a "maximum generations" number.
This will be the number of the last generation GFF will allow before
stopping. If GFF finds the correct function before the final generation, it
will stop early. If GFF gets to through the last generation without finding
the correct string, it will ask the user if he/she would like to continue,
using the same points. (For yes/no answers, 1 = yes, 0 = no).
Before GFF starts searching, it will ask if you would like to observe the
evolution of the strings. (1 = yes, 0 = no). If the you type "0", GFF will
give you no information until it has either reached the last generation or
it has found the correct function. If you type "1", GFF will give you
information on every generation as they are produced, including the total,
average, and median error of each generation's population.
When GFF finds the correct function it will print that function in the form
of "y = mx + b" and will ask for different points to work with and the
process will start again.
Limitations
GFF is about demonstrating the process of evolution, not about doing math.
For its purposes, a limited arithmetic is used. The only operators are '+'
and '-' and the only variable is 'x'. Therefore, GFF will not be able to
find non-linear functions (like 'y = x/2', 'y = x*x', etc.). Here's an
interesting thing to try. Give GFF points from a function that it cannot
find. GFF will develop strings that come closer and closer to perfect, but
never quite there. (Of course, if GFF was considering an infinite number of
points, every incorrect string would seem just as unreasonable as any other
string.)
Random Function Finder
An especially observant user might have noticed another program in the
folder with GFF. Random Function Finder works exactly like GFF except that
it searches randomly for the solution, instead of using an evolutionary
process. Try feeding the same numbers into GFF and Random Function Finder.
Except for rare cases, GFF will find the function long before Random
Function Finder will. I included Random Function Finder to show the
difference that an evolutionary process does make.
FAQ (Frequently Asked Questions)
What's the point of GFF?
GFF is designed to demonstrate a kind of evolution in a simple environment
with very basic rules.
Couldn't you find the function faster using "y1 - y = m(x1 - x)"?
Yes. So?
So why use a genetic algorithm?
The evolutionary process is the real purpose, not the math.
I get error messages when the strings get really long. Why?
The strings can only get to about 80 characters in length before problems
will arise. This is because when I wrote the program I arbitrarily chose 80
as the maximum length of a string. If you have a compiler, and you know
what you're doing, you can change it to whatever you'd like.
Is there a Windows/DOS version of GFF?
I don't have a Windoze compiler, but the whole program uses standard
input/output functions, so it shouldn't be very hard to port it to any
operating system.
Have you written any other programs?
Yes. I've written a gravity simulation program called "Orbit" that can be
found at the info-mac archives or on download.com.
Comments
GFF is a free program, written more for my own interest than anything else.
If you have any comments, questions, or cool ideas, email me at:
zerro1@hotmail.com.