views:

2205

answers:

12

I'm looking for a practical application to use a genetic algorithm for. Some things that have thought of are:

  • Website interface optimization
  • Vehicle optimization with a physics simulator
  • Genetic programming
  • Automatic test case generation

But none have really popped out at me. So if you had some free time (a few months) to spend on a genetic algorithms project, what would you choose to tackle?

+5  A: 

You might be interested in something like Roger Alsing's Mona Lisa

Stephen Denne
Sidenote: there's argumentation around whether or not the Mona Lisa algorithm truly is a genetic algorithm, or not.
Henrik Paul
It seemed like Simulated annealing to me
Robert Gould
It's a great ideas generator though... e.g. creating genetic algorithms for image compression.
Stephen Denne
I created a Java version of the Mona Lisa program that is a proper GA with a population size >1. So you don't have to do it exactly as Roger did, which was more a 1+1 evolution strategy.
Dan Dyer
+6  A: 
mdorseif
+1  A: 

I believe I saw mention of a project to use one to try and find out with the optimal keyboard layout would be--to "beat Dvorak," as it were. :D

J Cooper
A: 

I had fun playing with Conway's Game of Life and Genetic Algorithms,
trying to evolve advanced lifeforms.. Not sure if it'll keep you busy for
several months though..

Tim
Kept me busy through my thesis ;)
Robert Gould
+2  A: 

Perhaps finding a traveling salesman tour. I recently tried to find a walking tour around some 66 locations in Paris and I found coding all of these things very fun. I thought my excitement stemmed from two sources: the fact that I could draw the tours (also one good thing about the Mona Lisa idea, or if engineering's your thing, the Lego structures) and the fact that there are so many approaches that you can compare:

  • You can use simple heuristics, like "start somewhere and always go to the closest, unvisited location".
  • You can use more complex heuristics, like "keep adding edges (anywhere) in order by increasing cost, except when it would cause three edges out of one vertex or a smaller cycle".
  • You can use approximation algorithms, such as an easy one based on minimum spanning trees if your costs satisfy the triangle inequality. As a bonus, you can code up minimum spanning trees (maybe you could even use GAs there, despite the availability of fast-and-easy exact algorithms). If you're feeling confident, you can code up the harder (3/2)-approximation algorithm based on minimum spanning trees and perfect matchings.
  • If you have any traveling salesman tour and it crosses itself, you can improve it by "uncrossing it". Again, this assumes some conditions on the cost function.
  • You can even try to find a tour yourself and see if you can beat your computer.
  • Last but not least, genetic algorithms! The problem is very well suited to GAs because there's a very clear fitness function and a very easy way of doing recombination.
A. Rex
+2  A: 

See What problems could be solved using Genetic Programming?

I thought vehicle construction was really cool.

eed3si9n
Its cool but overdone by now :(
Robert Gould
+2  A: 

It has been used in complex synthesizers to generate sound patches (e.g. the Clavia Nord Modular G2) I'd try it for other machines as well, the Yamaha DX7 comes to mind but I guess there are quite a few software alternatives out there. Or image generation.

Read up on the theory behind the patch algorithms in a paper by Palle Dahlstedt. It seems to be down at the moment though...

Niklas Winde
A: 

Back in college I did multidimensional function minimization.. lets say you have a f(x) which takes parameters x1,x2,x3,...,xn and generates a value Y.. you need to find the parameters x1,..,xn such that Y=Y1.. not so difficult.. interesting way to learn nevertheless. Although Nedlermead is way more efficient.. this is not prone to getting stuck in local minimas.

Sridhar Iyer
+7  A: 

One topic with lots of possibilities is to use evolutionary algorithms to evolve strategies for game playing. People have used evolution to generate strategies for poker, checkers/draughts, Go and many other games. The J-GAP people have used genetic programming to evolve bots for Robocode.

I recently posted an introductory article about evolutionary computation. It includes details of some of the things evolutionary algorithms have been used for. Adam Marczyk has also written an excellent article with lots of examples. The Genetic Argonaut blog contains dozens of links to interesting evolutionary projects.

A less common type of evolutionary algorithm is the learning classifier system. This evolves a set of rules for classifying inputs. It can be applied to the same kind of problems that neural networks are used for. It could be interesting to develop an LCS for a particular problem, such as attempting to predict sports results based on form.

Dan Dyer
I evolved a family of competent othello players, which was fun and very interesting, because I had never played othello before. Thus I solved a problem I didn't even understand. That's the true power of GAs.
Robert Gould
+1  A: 

Genetic Algorithms are well suited for optimization and scheduling. An example would be scheduling a set of machines, having parts and operators over time to complete a set of tasks. While probably not the most exciting project, it would have real world applications.

aekeus
+2  A: 

Hey.
I have read about something similar to proposed in question to Automatic test case generation. Actually it was quite opposite. You specify test cases, and than let algorithm (genetic programming) to create code that will pass. This way you provide specification and you breed your program. If you google a bit for it you can find some studies on it.
I find this to be very intriguing idea. Of course now no one would create any app like this, but that is great study area.

yoosiba
+1  A: 

Generate music compositions! Read about David Cope and his program Emily Howell.

freedrull