Finding aproximate functions using genetic algorithms

Image

 

I have undertaken another weekend project, this time I wanted to investigate how well a genetic algorithm could find and approximate a variety of 1d functions.  Approximate functions can be very useful to speed up processing time in many areas where accuracy is not crucial.

In total I have spend around 5 hours on this having programmed everything from scratch.  I had worked with genetic algorithms before so I had a good idea how to approach them, and avoid some common pitfalls.

For this task each gene can contain the follow operators [ +, -, *, /, abs() ].  There are 15 operand nodes, and 16 input leaves, forming a binary tree which propagates the overall evaluation towards the root of the tree.

One of major change over my previous designs was to try an maintain diversity in the gene pool as a high priority.  My early tests showed that each gene in the pool would approach the current best gene with minimal to no change.  I took two approaches to combat this.  The easiest was to periodically call a function to kill inbred genes;  if any genes were too similar then the one with the lowest performance would be entirely randomized.  My second strategy was to allow a newly created and mutated gene to replace one of its parents only when it scores better then them, otherwise it will be dumped entirely.  My old approach was to kept any new gene in the pool if it performed better then the worst in the pool, which leads to the best performing genes dominating the pool with no incentive for variance.

I have observed that a species can easily get stuck in a local maxima and take quite a long time to escape it, which is something that can use improvement in the future.

The overall performance of this project is quite pleasing, and it is already churning out some very unusual approximation functions, for instance:

float aprox_tanh( float x )
{
//  return 6.01180618117f / ( 1.201234f * x + 7.38167675703f / x );
    return 5.00469199271f / ( x + 6.14507810887f / x );
}

 

Image

Image

Advertisements

3 thoughts on “Finding aproximate functions using genetic algorithms

  1. This is pretty cool stuff you’ve got going on here, very impressed!

    Do you constrain the solver to a specific range of floating point numbers? It is much easier to find a converging solution to trig functions in a much smaller range from my experience – just curious to know what you do! 🙂

    • Yep I did train it over a limited range of input values. I presume it would really be dependant on the function its trying to learn, and probably good to focus the training on the important parts of the function.

      I would like to go back to this project and extend it for multiple dimensions and have some smarter breeding algorythms. I’m curious how well it could learn images, and what they would look like.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s