Genetic Algorithms?

I was helping a group with their senior project and they mentioned something about genetic algorithms. I know the generic definition is to basically model different aspects of nature using them, but can anyone elaborate?

 

Log in or Sign up to hide all adverts.

This thread is more suited for the computer science forum, by the way.

Genetic algorithms, and evolutionary algorithms in general, use a simplified simulation of natural selection to evolve solutions. A simplified explanation follows:
We have a black box that returns the value of some function given some input. We don't know what the function is, but we want to find the input that will give us the maximum value (between some bounds, probably).
I randomly initialize a set of possible inputs and call this our population.
I find the 'fitness' of each input by putting it into the box and calling the output the fitness. The higher the fitness the better, since we're trying to optimize.
Depending on the fitness, each possible input has a chance to 'reproduce,' which usually consists of small mutations (perhaps adding or subtracting a small value) and recombinations (if our inputs are represented as binary strings, we can take two inputs and swap portions of them). The child inputs that result from these processes form the new population, and we start all over.

Many many variations on this exist, but the general idea is the same. By biasing by fitness somehow, the population is expected to eventually contain an acceptable solution.

It's not magical...it won't solve everything, and it won't always solve everything as fast as you want. But in a number of cases, it does pretty well.

 

Log in or Sign up to hide all adverts.

Very Deep Knowledge Base . . .

I recommend accessing the Internet for various descriptive sites regarding genetic algorithms. It is a very deep subject in the sense that there are volumes of information. A short post here would really not do the topic justice. I think you'll discover a healthy body of information on genetic algorithms on the Internet while also encountering other topics such as evolutionary algorithms, genetic programming, hill-climbing, and heuristic algorithms.

Happy surfing!

 

Log in or Sign up to hide all adverts.

In my experience most texts on genetic algorithms are overly complex for getting started coding one. The basic algorithm requires only a few pages of code and is fairly simple. A book I recommend for ignoring theory and focusing on applications is Genetic Algorithms in C++. (Read the customer reviews for more info on GAs.)

If you can read C++ (you don’t need to be able to write it) then the book is also a great way to learn about GAs, even if you won’t code one.

In your Google search include “java” to find neat java apps showing off GAs. Also try “traveling salesman”. The classic traveling salesman problem is test of a GA.

 

If you're just looking for an intro to evolutionary computation, then that's probably worthwhile. If you're looking to apply it to something non-trivial or get into it more deeply in some way, I recommend you study some theory as it will allow you to tune your algorithm to perform better (or at all!) for your problem. A particular EA that works well for one class of problems doesn't always work well on a different class. I haven't read that book so I can't comment on it. Here are a couple links that could be helpful as well:

ENCORE
Hitch-Hiker's Guide to Evolutionary Computation

Also, the author of that book has a web site at http://www.coyotegulch.com. Some informative items there, too.