Finding f(x) with Genetic Algorithms
You are here:

Team Information

         Project Info Program Acknowledgements Team Info               

Team Members:

Jordan Chin (JordanChin89@gmail.com)

Robert Young (Robert.gxYoung@shaw.ca)

Grade Category:

10 – 12

Team Size:

2

Subject Area:

Engineering/Computer Science

Project Type:

Experiment

Language:

English

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.

 

 

Software Tools Used:

 

o     Adobe Photoshop CS2

o     Adobe Illustrator CS2

o     Macromedia Flash MX

o     Microsoft Expression Web

o     Microsoft Word

o     Microsoft Powerpoint

o     Microsoft Visual Studio

o     FireFTP FireFox Extension

Hardware Tools Used:

 

o     Computers

o     Small supercomputing cluster

 

Source of Idea:

 

            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?

 

Special Skills Used:

 

o     C/C++

o     Java

o     JavaScript

o     HTML

 

Awards Won:

 

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:

 

    PDF Project Report