What are good examples of genetic algorithms/genet

Question

Genetic algorithms (GA) and genetic programming (GP) are interesting areas of research.

I'd like to know about specific problems you have solved using GA/GP and what libraries/frameworks you used if you didn't roll your own.

Questions:

• What problems have you used GA/GP to solve?
• What libraries/frameworks did you use?

I'm looking for first-hand experiences, so please do not answer unless you have that.

Answer 1

As well as some of the common problems, like the Travelling Salesman and a variation on Roger Alsing's Mona Lisa program, I've also written an evolutionary Sudoku solver (which required a bit more original thought on my part, rather than just re-implementing somebody else's idea). There are more reliable algorithms for solving Sudokus but the evolutionary approach works fairly well.

In the last few days I've been playing around with an evolutionary program to find "cold decks" for poker after seeing this article on Reddit. It's not quite satisfactory at the moment but I think I can improve it.

I have my own framework that I use for evolutionary algorithms.

Answer 2

I developed a home brew GA for a 3D laser surface profile system my company developed for the freight industry back in 1992. The system relied upon 3 dimensional triangulation and used a custom laser line scanner, a 512x512 camera (with custom capture hw). The distance between the camera and laser was never going to be precise and the focal point of the cameras were not to be found in the 256,256 position that you expected it to be!

It was a nightmare to try and work out the calibration parameters using standard geometry and simulated annealing style equation solving.

The Genetic algorithm was whipped up in an evening and I created a calibration cube to test it on. I knew the cube dimensions to high accuracy and thus the idea was that my GA could evolve a set of custom triangulation parameters for each scanning unit that would overcome production variations.

The trick worked a treat. I was flabbergasted to say the least! Within around 10 generations my 'virtual' cube (generated from the raw scan and recreated from the calibration parameters) actually looked like a cube! After around 50 generations I had the calibration I needed.

Answer 3

Football Tipping. I built a GA system to predict the week to week outcome of games in the AFL (Aussie Rules Football).

A few years ago I got bored of the standard work football pool, everybody was just going online and taking the picks from some pundit in the press. So, I figured it couldn't be too hard to beat a bunch of broadcast journalism majors, right? My first thought was to take the results from Massey Ratings and then reveal at the end of the season my strategy after winning fame and glory. However, for reasons I've never discovered Massey does not track AFL. The cynic in me believes it is because the outcome of each AFL game has basically become random chance, but my complaints of recent rule changes belong in a different forum.

The system basically considered offensive strength, defensive strength, home field advantage, week to week improvement (or lack thereof) and velocity of changes to each of these. This created a set of polynomial equations for each team over the season. The winner and score for each match for a given date could be computed. The goal was to find the set of coefficients that most closely matched the outcome of all past games and use that set to predict the upcoming weeks game.

In practice, the system would find solutions that accurately predicted over 90% of past game outcomes. It would then successfully pick about 60-80% of games for the upcoming week (that is the week not in the training set).

The result: just above middle of the pack. No major cash prize nor a system that I could use to beat Vegas. It was fun though.

I built everything from scratch, no framework used.

Answer 4

in undergrad, we used NERO (a combination of neural network and genetic algorithm) to teach in-game robots to make intelligent decisions. It was pretty cool.

Answer 5

As part of my thesis I wrote a generic java framework for the multi-objective optimisation algorithm mPOEMS (Multiobjective prototype optimization with evolved improvement steps), which is a GA using evolutionary concepts. It is generic in a way that all problem-independent parts have been separated from the problem-dependent parts, and an interface is povided to use the framework with only adding the problem-dependent parts. Thus one who wants to use the algorithm does not have to begin from zero, and it facilitates work a lot.

You can find the code here.

The solutions which you can find with this algorithm have been compared in a scientific work with state-of-the-art algorithms SPEA-2 and NSGA, and it has been proven that the algorithm performes comparable or even better, depending on the metrics you take to measure the performance, and especially depending on the optimization-problem you are looking on.

You can find it here.

Also as part of my thesis and proof of work I applied this framework to the project selection problem found in portfolio management. It is about selecting the projects which add the most value to the company, support most the strategy of the company or support any other arbitrary goal. E.g. selection of a certain number of projects from a specific category, or maximization of project synergies, ...

My thesis which applies this framework to the project selection problem: http://www.ub.tuwien.ac.at/dipl/2008/AC05038968.pdf

After that I worked in a portfolio management department in one of the fortune 500, where they used a commercial software which also applied a GA to the project selection problem / portfolio optimization.

Further resources:

The documentation of the framework: http://thomaskremmel.com/mpoems/mpoems_in_java_documentation.pdf

mPOEMS presentation paper: http://portal.acm.org/citation.cfm?id=1792634.1792653

Actually with a bit of enthusiasm everybody could easily adapt the code of the generic framework to an arbitrary multi-objective optimisation problem.

Answer 6

After reading The Blind Watchmaker, I was interested in the pascal program Dawkins said he had developed to create models of organisms that could evolve over time. I was interested enough to write my own using Swarm. I didn't make all the fancy critter graphics he did, but my 'chromosomes' controlled traits which affected organisms ability to survive. They lived in a simple world and could slug it out against each other and their environment.

Organisms lived or died partly due to chance, but also based on how effectively they adapted to their local environments, how well they consumed nutrients & how successfully they reproduced. It was fun, but also more proof to my wife that I am a geek.