Have you ever used a genetic algorithm in real-world applications?

Question

I was wondering how common it is to find genetic algorithm approaches in commercial code.

It always seemed to me that some kinds of schedulers could benefit from a GA engine, as a supplement to the main algorithm.

Certiorari

Answer 1

Genetic Algorithms have been widely used commercially. Optimizing train routing was an early application. More recently fighter planes have used GAs to optimize wing designs. I have used GAs extensively at work to generate solutions to problems that have an extremely large search space.

Many problems are unlikely to benefit from GAs. I disagree with Thomas that they are too hard to understand. A GA is actually very simple. We found that there is a huge amount of knowledge to be gained from optimizing the GA to a particular problem that might be difficult and as always managing large amounts of parallel computation continue to be a problem for many programmers.

A problem that would benefit from a GA is going to have the following characteristics:

• A good way to encode potential solutions
• A way to compute an a numerical score to evaluate the quality of the solution
• A large multi-dimensional search space where the answer is non-obvious
• A good solution is good enough and a perfect solution is not required

There are many problems that could probably benefit from GAs and in the future they will probably be more widely deployed. I believe that GAs are used in cutting edge engineering more than people think however most people (like my company does) guards those secrets extremely closely. It is only long after the fact that it is revealed that GAs were used.

Most people that deal with "normal" applications probably don't have much use for them though.

Liverish

+1 but I think genetic algorithms are only simple for people who "get" the basic principle of evolution/natural selection. I've never been able to successfully explain GA to people who deny evolution (a large bunch, unfortunately). – Pascale

Answer 2

If you want to find an example, look at Postgres's Query Planner. It uses many techniques, and one just so happens to be genetic.

http://developer.postgresql.org/pgdocs/postgres/geqo-pg-intro.html

Nicolina

This extremely old answer brought my day job closer to my PhD studies. Thank you from the future. – Mocambique

The above link is dead. Updated Link :- postgresql.org/docs/9.1/geqo-pg-intro.html – Brianbriana

Answer 3

I used GA in my Master's thesis, but after that I haven't found anything in my daily work a GA could solve that I couldn't solve faster with some other Algorithm.

Tedra

Thats in the nature of the beast - GA are most useful if you do not know an analytical solution to your problem. An anayltical solution should always be more efficient. – Depalma

Answer 4

I haven't but I've heard of this company (can't remember their name) which uses mutating, genetic algos to calculate placements and lengths of antennas (or something) from a friend of mine. And they're supposed to (according to my friend) have huge success with this. I guess GA is just too complex for "average Joe developer" to become mainstream. Kind of like Map Reduce - spectacularly cool, but WAY too advanced to hit the "mainstream"...

Tamboura

ieeexplore.ieee.org/Xplore/login.jsp?url=/iel5/8/27408/… – Euchology

I dont think it is too complex. The bigger problem is that it is a non-deterministic algorithm and therefor you often cant guarantee a certain quality of the results and so the people prefer other heuristics (where they can). – Reset

It#s not complex: the problem is that it SOUNDS complex - you don't actually need much knowledge of genetics to implement your own GAs. – Pathan

That company is called NASA, and here is a paper on developing antennas with GA: ti.arc.nasa.gov/m/pub-archive/1244h/1244%20(Hornby).pdf – Thumbprint

Answer 5

I don't think it is particularly common to find genetic algorithms in everyday-commercial code. They are more commonly found in academic/research code where the need to find the "best algorithm" is less important than the need to just find a good solution to a problem.

Nonetheless, I have consulted on a couple of commercial projects that do use GAs (chiefly as a result of my involvement with GAUL). I think the most interesting example was at a Biotech company. They used the GA to optimise scoring functions that were used for virtual screening, as part of their drug discovery application.

Earlier this year, with my current company, I added a new feature to one of our products that uses another GA. I think we might be marketing this from next month. Basically, the GA is used to explore molecules that have the potential for binding to a protein, and could therefore be further investigated as drugs targeting that protein. A competing product that also uses a GA is EA inventor.

Centonze

Answer 6

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.

Balas

Answer 7

LibreOffice Calc uses it in its Solver module.

Yarmouth