|
Project Summary:
|
A
genetic algorithm (GA) is a computer search technique involving
concepts from evolutionary biology. Basically, random solutions are
initially generated to represent individuals in a virtual
population. Each solution (individual) is given a fitness rating
based on how well it solves the problem. Through selection of these
solutions (those with the highest fitness), these solutions undergo
reproduction. Crossovers (and mutation) of the surviving solutions
are used to create the next generation of solutions. Thus, every
generation is an evolution towards the final solution. Since their
conception, GA's have been used as adaptive algorithms for solving
practical problems by many scientists, engineers, and software
programmers. Therefore, we wondered how effective it would be to use
a GA to approximate functions (function approximation software often
requires advanced math). Through the project, we pondered questions
such as,
"What is the fewest points necessary for good
approximations?",
"How
fast can the GA be?",
and
"Can it output practical functions?" This project aims to create a computer program that, given
a set of points, can approximate a mathematical function using a GA,
without prior knowledge of what function the data may resemble.
|
|
It was in the summer of 2006 when this, the topic of genetic
algorithms first arose for us out of interest in programming. At
first applying a genetic algorithm to function approximation seemed
like a novel exercise in programming, but research on the idea
produced only abstracts—no code or executables to compare with.
Thus, we set out to find out for ourselves how practical the
approach may be.
Perhaps the
reason such a program did not already exist was because a genetic
algorithm may not be worth the effort as they are known to be slow.
Still, one abstract piqued our interest. It claimed, “Genetic
programming is indeed a powerful tool.”
Research into other function approximation programs and methods led
us to the following questions: What is the minimum number of points
necessary for good approximations? How powerful is genetic
programming? Can a function approximation program output nice/clean
looking functions?
|
|
o
Gold
Medal (at the Greater
Vancouver
Regional Science Fair)
o
Canada-Wide Science Fair 2007 Finalist
o
UBC
Computing Science Award
o
SFU
Computing Science Award
Project Report Download:
A condensed project report can be downloaded
from here:
 Project Report
|
