An introduction to genetic algorithms(theprojectspot.com)
theprojectspot.com
An introduction to genetic algorithms
http://www.theprojectspot.com/tutorial-post/creating-a-genetic-algorithm-for-beginners/3
14 comments
Evolution is not the life's way to solve problem. It is a cold arithmetic where survival is only way.
I like the simplicity of your solution.
Here's a presentation I gave on GE and tic-tac-toe as part of senior sem in college, might be helpful for someone just getting into GA (as I was at the time). https://docs.google.com/present/view?id=df49rshq_117sjxbr2ks
edit: and here's the tutorial I used at the time, which I think would complement your tutorial http://www.puremango.co.uk/2010/12/genetic-algorithm-for-hel...
Here's a presentation I gave on GE and tic-tac-toe as part of senior sem in college, might be helpful for someone just getting into GA (as I was at the time). https://docs.google.com/present/view?id=df49rshq_117sjxbr2ks
edit: and here's the tutorial I used at the time, which I think would complement your tutorial http://www.puremango.co.uk/2010/12/genetic-algorithm-for-hel...
Thanks for the links.
I'm glad you liked it, simplicity was the objective. When you first start learning it's important to make sure you have a firm ground on the basics.
For those who like Lisp, here's a similar article with Clojure as the target language:
http://ethanfast.com/2009/09/ga-framework/
http://ethanfast.com/2009/09/ga-framework/
If you're looking for more doc / research on GAs, be sure to include 'evolutionary computation' in your searches.
The tough parts to using EC/GA on your problem (which this article doesn't discuss at all, unfortunately) are going to be:
a) figuring out a string representation for your candidate solutions (i.e. because strings are easy to 'mate', 'mutate', etc.)
b) writing a fitness function to evaluate one or more candidates
[a] and [b] are intimately related, of course.
One of the nice things about EC/GA is that it's typically very easy to scale up to take advantage of more hardware. If you have an expensive fitness function, e.g. 'fighting' two chess-board evaluators against one another over an extended series of games, you can just farm those simulations out to as many procs/machines as you have available.
The tough parts to using EC/GA on your problem (which this article doesn't discuss at all, unfortunately) are going to be:
a) figuring out a string representation for your candidate solutions (i.e. because strings are easy to 'mate', 'mutate', etc.)
b) writing a fitness function to evaluate one or more candidates
[a] and [b] are intimately related, of course.
One of the nice things about EC/GA is that it's typically very easy to scale up to take advantage of more hardware. If you have an expensive fitness function, e.g. 'fighting' two chess-board evaluators against one another over an extended series of games, you can just farm those simulations out to as many procs/machines as you have available.
One approach to scaling GA I thought was both appropriate and funny was a migrate function that randomly sends a sample to another node. Because you only need to send to a single node occasionally it scales vary well. But what's cool is it's like an infection they either take over the place or get eaten fairly quickly.
This doesn't look like a good framework for GAs. It assumes that the best solution to a given problem is explicitly provided but if it is, then there's no point in running a GA any more. A good framework would only represent the genetic data in the form of a binary string but evaluate the fitness using an external function that actually extracts meaningful information from the string. Shameless plug: here's an example I wrote in Coffee: https://github.com/fawek/distributed-monalisa-evolution/tree.... It also makes it somewhat easy to distribute the evolution to multiple populations which can reside in different processes or machines.
Another problem with GAs that model individuals as arbitrary binary strings is that they unnecessarily create a lot of invalid strings that don't correspond to the solution space of a given problem. Sometimes it's easy to convert the solution space to the entire sequence range of 0 and 1s but sometimes it's not.
Another problem with GAs that model individuals as arbitrary binary strings is that they unnecessarily create a lot of invalid strings that don't correspond to the solution space of a given problem. Sometimes it's easy to convert the solution space to the entire sequence range of 0 and 1s but sometimes it's not.
I agree and thank you for comment, but I wanted to keep it as simple as possible so readers can understand the basic logic and structure behind a GA it.
If I started talking about more complex ways to represent different search spaces while calculating the fitness in a more abstract way it would probably lead to confusion for beginners.
I really wish people would stop calling Java "JAVA".
This nature-inspired and free book also contains some chapters on genetic algorithms: http://www.cleveralgorithms.com/
Allow me to recommend my own free text, which covers most of the field: Essentials of Metaheuristics. http://cs.gmu.edu/~sean/book/metaheuristics/
Thank you, this is excellent stuff!
It feels much more compelling to pay for a book that the writer is having enough confidence to give away for free.
It feels much more compelling to pay for a book that the writer is having enough confidence to give away for free.
A simple implementation in Scala I just did for fun:
https://github.com/Mononofu/Simple-GeneticAlgorithm
Just like the Java one, but less code. Usually converges in 10 - 20 iterations.
https://github.com/Mononofu/Simple-GeneticAlgorithm
Just like the Java one, but less code. Usually converges in 10 - 20 iterations.
For those that like GA's I recommend checking out Cellular evolutionary algorithm ( http://en.wikipedia.org/wiki/Cellular_evolutionary_algorithm ) It is a GA with the addition that you can only mate with those around you. This tweak significantly improves my GA's.