cool project to use a genetic algorithm for?

Question

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?

Answer 1

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

Answer 2

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

Answer 3

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..

Answer 4

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.

Answer 5

See What problems could be solved using Genetic Programming?

I thought vehicle construction was really cool.

Answer 6

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...

Answer 7

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.

Answer 8

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.

Answer 9

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.

Answer 10

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.

Answer 11

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