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

A coworker and I are working on a solution for loading freight onto trucks using the various criteria our company requires. I've been working on a Genetic Algorithm solution while he is using a Branch And Bound with aggressive pruning. We are still in the process of implementing this solution but so far, we have been getting good results.

Answer 2

Not homework.

My first job as a professional programmer (1995) was writing a genetic-algorithm based automated trading system for S&P500 futures. The application was written in Visual Basic 3 [!] and I have no idea how I did anything back then, since VB3 didn't even have classes.

The application started with a population of randomly-generated fixed-length strings (the "gene" part), each of which corresponded to a specific shape in the minute-by-minute price data of the S&P500 futures, as well as a specific order (buy or sell) and stop-loss and stop-profit amounts. Each string (or "gene") had its profit performance evaluated by a run through 3 years of historical data; whenever the specified "shape" matched the historical data, I assumed the corresponding buy or sell order and evaluated the trade's result. I added the caveat that each gene started with a fixed amount of money and could thus potentially go broke and be removed from the gene pool entirely.

After each evaluation of a population, the survivors were cross-bred randomly (by just mixing bits from two parents), with the likelihood of a gene being selected as a parent being proportional to the profit it produced. I also added the possibility of point mutations to spice things up a bit. After a few hundred generations of this, I ended up with a population of genes that could turn $5000 into an average of about $10000 with no chance of death/brokeness (on the historical data, of course).

Unfortunately, I never got the chance to use this system live, since my boss lost close to $100,000 in less than 3 months trading the traditional way, and he lost his willingness to continue with the project. In retrospect, I think the system would have made huge profits - not because I was necessarily doing anything right, but because the population of genes that I produced happened to be biased towards buy orders (as opposed to sell orders) by about a 5:1 ratio. And as we know with our 20/20 hindsight, the market went up a bit after 1995.

Answer 3

At work I had the following problem: given M tasks and N DSPs, what was the best way to assign tasks to DSPs? "Best" was defined as "minimizing the load of the most loaded DSP". There were different types of tasks, and various task types had various performance ramifications depending on where they were assigned, so I encoded the set of job-to-DSP assignments as a "DNA string" and then used a genetic algorithm to "breed" the best assignment string I could.

It worked fairly well (much better than my previous method, which was to evaluate every possible combination... on non-trivial problem sizes, it would have taken years to complete!), the only problem was that there was no way to tell if the optimal solution had been reached or not. You could only decide if the current "best effort" was good enough, or let it run longer to see if it could do better.

Answer 4

I used a simple genetic algorithm to optimize the signal to noise ratio of a wave that was represented as a binary string. By flipping the the bits certain ways over several million generations I was able to produce a transform that resulted in a higher signal to noise ratio of that wave. The algorithm could have also been "Simulated Annealing" but was not used in this case. At their core, genetic algorithms are simple, and this was about as simple of a use case that I have seen, so I didn't use a framework for generation creation and selection - only a random seed and the Signal-to-Noise Ratio function at hand.

Answer 5

As part of my undergraduate CompSci degree, we were assigned the problem of finding optimal jvm flags for the Jikes research virtual machine. This was evaluated using the Dicappo benchmark suite which returns a time to the console. I wrote a distributed gentic alogirthm that switched these flags to improve the runtime of the benchmark suite, although it took days to run to compensate for hardware jitter affecting the results. The only problem was I didn't properly learn about the compiler theory (which was the intent of the assignment).

I could have seeded the initial population with the exisiting default flags, but what was interesting was that the algorithm found a very similar configuration to the O3 optimisation level (but was actually faster in many tests).

Edit: Also I wrote my own genetic algorithm framework in Python for the assignment, and just used the popen commands to run the various benchmarks, although if it wasn't an assessed assignment I would have looked at pyEvolve.

Answer 6

I don't know if homework counts...

During my studies we rolled our own program to solve the Traveling Salesman problem.

The idea was to make a comparison on several criteria (difficulty to map the problem, performance, etc) and we also used other techniques such as Simulated annealing.

It worked pretty well, but it took us a while to understand how to do the 'reproduction' phase correctly: modeling the problem at hand into something suitable for Genetic programming really struck me as the hardest part...

It was an interesting course since we also dabbled with neural networks and the like.

I'd like to know if anyone used this kind of programming in 'production' code.