Friday, December 24, 2010

Introduction to Genetic Algorithms

Here's a nice little introduction to Genetic Algorithms. Although the problem they solve (generating "hello world") is rather silly, it's a good introduction to the world of Genetic Algorithms. If you are interested in the topic, you should check it out.

This is another good article. Again, this problem (solving N-Queens) isn't the best. A deterministic algorithm can solve the problem much faster.

The best problems for Genetic Algorithms are ones that don't have known optimal solutions. Another important property is that partial solutions can be crossed over to make a better solution. Without this property, your genetic algorithm will essentially degenerate to randomly guessing at the solution. In fact, I'm curious to see how much better some Genetic Algorithms perform when compared to a random algorithm. You can generate a lot of random guesses while a Genetic Algorithm goes through a generation.

It would be cool to make an app that allowed you to encode genetic algorithms without using a traditional programming language. Instead, the user would use a simple, domain specific language to encode the genetic algorithm. Then the program would be able to automatically calculate and display run statistics. Perhaps this should go on my Pet Projects queue.

No comments:

Post a Comment