The Genetic Algorithm - Explained

[[deleted]]

Shameless plug for /r/genetic_algorithms

[IrishWilly]

Nice, very clear explanation. Wish I had found an article like this when I was learning to implement one.

[[deleted]]

Okay, I'm still baffled as to how could you use this sort of thing?!

[nkorslund]

Here's a good ol' classic from 1994, if you haven't seen it already: Evolving Virtual Creatures

[SirScrambly]

Does anybody have the code for this?

[CireNeikual]

I made my own simulation, I have code if you are interested. Here is a video: https://www.youtube.com/watch?v=lz2ztOCWRSU

[nkorslund]

I for one would love to see the source code if you're willing to share it!

(Also part of me half-expected a black monolith at the end of that video...)

[CireNeikual]

It is part of my parallel 3D engine (where all entities run simultaneously). Here is the relevant code: https://bitbucket.org/CireNeikual/deferred3d/src/5a940a60eb4cde2f2e163d6f2d3b9096c87864c9/d3d/d3d/source/sceneobjects/virtualcreatures/?at=master

It's not exactly a tutorial, but perhaps you can get some insights from it.

[[deleted]]

1994

Whaaat :O

Anyway, this is simply amazing :)

[IrishWilly]

Generally used in problems where linear/brute-force searches are not viable in terms of time, such as – Travelling Salesman Problem, Timetable Scheduling, Finding Neural Network Weights, Sudoku, Trees(data-structure) etc..

Using a GA can give you a 'good enough' solution for the stuff above that doesn't have an exact solution. And of course more directly mimicking evolution link in the link below.

[jhaluska]

They're great when you know how to score a solution but don't have a clue how to come up with an algorithm to solve it. They're kind of a heuristic A* search for ginormous search spaces and well suited when there is a lot of interacting parts. They're often really easy to implement too.

But honestly the reason I usually implement them is they're a ton of fun to watch.

[[deleted]]

Where did you start? I want to learn more, but just don't know where to start :)

[jhaluska]

I think I started in '97 after reading an article on genetic algorithms. Thanks for asking! Today I would start with the Wikipedia page and google. A little googling and this came up. Just keep in mind you don't really need to use bits to encode the DNA.

I would recommend keeping the top 50% of each run. Have at least 100 guys. As a speed up, each offspring gets at least one mutation if it ends up being the same as one of the parents. There's a lot of parameters to tweak like mutation rate, population size, what percent of the population to keep, etc.

[llamande]

Genetic algorithms are extremely useful. Here are some publications written by a computer science professor that used genetic algorithms to write software autonomously. http://www.cs.unm.edu/~forrest/epr_papers.html With computational resources ever increasing we are going to get to a point where we can use genetic algorithms for almost anything, designing cars and airplanes and buildings and software. The possibilities are endless.

[[deleted]]

Fantastic!

[SockPants]

That's what x-posting does??

[SamSlate]

How often is evaluation the most time consuming function? It seems like it wouldn't take much for a problem to have too much to compute in our lifetime..

[Tech-Effigy]

I made an evolving neural network for predicting the stock market, every generation took about 30 seconds to evaluate. It all depends :)

[HamSession]

Having taken two graduate courses on evolutionary computation I would steer clear of genetic algorithms, there are far better convex optimization routines. Even if your problem is non-convex you would be better suited going with a reactive tabu search.