12
$\begingroup$

What are some real world problems that have been solved using a genetic algorithm? What is the problem? What is the fitness test used to solve this problem?

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ This should be community wiki (assuming that it's on topic). $\endgroup$
    – Shane
    Aug 23, 2010 at 20:15
  • 4
    $\begingroup$ I'm not sure genetic algorithms are within scope. We should discuss it here: meta.cstheory.stackexchange.com/questions/73/… $\endgroup$
    – Suresh Venkat
    Aug 23, 2010 at 20:25
  • 7
    $\begingroup$ This is out of topic. $\endgroup$
    – Marcos Villagra
    Aug 23, 2010 at 22:33
  • 5
    $\begingroup$ An intereresting question might have been: are there any scenarios that admit provable guarantees for GAs. $\endgroup$
    – Suresh Venkat
    Sep 1, 2010 at 17:27
  • 2
    $\begingroup$ But this isn't about an application of theory. It's about an application of practice. $\endgroup$
    – Jeffε
    Sep 3, 2012 at 14:38

12 Answers 12

Reset to default
10
$\begingroup$

The optimizer in relational databases. Examples are PostgreSQL and H2; other databases most likely also use a genetic algorithm. The problem is: selecting the best query plan (the one with the lowest estimated cost) is NP-hard. The fitness test is the estimated cost.

Improve this answer
$\endgroup$
8
$\begingroup$

The Lamarckian Genetic Algorithm is used in chemoinformatics to screen for potential new drug compounds that can bind with a particular receptor.

The computational problem is to search through a chemical database for candidates that can orient correctly (wrt the possible orientations of the molecule containing the receptor), and to combine that with a conformational search (i.e., one that considers the possible rotatable torsions of the molecule, which can strongly affect the reaction).

Previously, it was feasible to perform either an orientation search or a conformation search, but not both. LGA takes advantage of computer speedup, and combines the global search of a genetic algorithm with a local search.

Improve this answer
$\endgroup$
6
$\begingroup$

Nasa created a genetic algorithm for Antenna Design.

The fitness test is as follows:

The fitness function used to evaluate antennas is a function of the voltage standing wave ratio (VSWR) and gain values on the transmit and receive frequencies. VSWR is a way to quantify reflected-wave interference, and thus the amount of impedance mismatch at the junction. VSWR is the ratio between the highest voltage and the lowest voltage in the signal envelope along a transmission line.

Improve this answer
$\endgroup$
6
$\begingroup$

These are often used in finance, especially for portfolio optimization problems. There are many papers on this subject, but see for example Genetic Algorithms in Portfolio Optimization.

Improve this answer
$\endgroup$
6
$\begingroup$

I've used GAs to solve scheduling problems in manufacturing and education. The fitness function in the first case was how much of the requested items were manufactured in the given time frame, while in the second case the fitness was based on penalizing schedules with conflicts.

If you're interested in applications, here's a link to 20K+ papers on citeseerx

Improve this answer
$\endgroup$
6
$\begingroup$

I can't resist but point out Roger Alsing's work:

http://rogeralsing.com/2008/12/07/genetic-programming-evolution-of-mona-lisa/

Represent the image of Mona Lisa using only 50 semi-transparent triangles.

Improve this answer
$\endgroup$
1
  • $\begingroup$ That was a very cool project! And I can't resist pointing out another very cool project tagxedo.com, in case y'all don't know about it. ;-) $\endgroup$
    – Steven A. Lowe
    Oct 4, 2010 at 18:29
4
$\begingroup$

Antenna design has already been mentioned, and it is an extremely rich domain. (It is, very directly, what started my motion from electrical engineering to computer science (in the late 90's) and more specifically to bio-inspired computation and artificial intelligence (in the last five years or so.))

In the same vein, I'll add antenna array optimization, especially for phased array optimization, which is all of the headaches of antenna design, and more. There are opportunities in the entire field of electromagnetic device design, really: Antennas, antenna arrays, microwave filters, optical gratings, metamaterial device design, all off the top of my head. A dated survey is Electromagnetic Optimization by Genetic Algorithms, and a more recent survey is Genetic Algorithms in Electromagnetics. (I should really buy that second one.

I've seen a lot of good papers on non-electromagnetic circuit design as well: GAs coming up with competitive op-amp or other integrated circuit designs, GAs "learning" to take advantage of the analog imperfections in FPGAs to implement analog functions like clocks, etc. Even something as simple as dumb, discrete element filter design can be a target for GAs: I've seen one that factors in q-factors, tolerances, discrete values and soldering parasitic models to get good, manufacturable filters from the parts you have at hand.

These often involve some novel (to me, anyway) circuit representations to get the genetic operators to fit the paradigm, as well as variable size chromosomes.

Improve this answer
$\endgroup$
1
3
$\begingroup$

recently there was a question about using GAs to evolve wind turbine blade designs using fluid dynamics simulations of physical power generated as the fitness function.[1]

This video shows the use of a genetic algorithm to develop VAWT wind turbine blades. One of the resulting blades is quite different and seems to simulate well. The breeding software was written in Perl, the display software Java, and the CFD software was OpenFoam. More than 672 CPU hours went into the making of this video. Note: I have since discovered I used the wrong viscosity for air on this experiment, so the results aren't valid for use on the earth. (Maybe Jupiter.)

[1] "Evolving wind turbine blades" on youtube by "sjh7132". cited by/from the TCS.se question: To what extent is it possible to use genetic algorithms to make wind mill turbine blades more efficient?

Improve this answer
$\endgroup$
3
$\begingroup$

there is some research into using GAs for wine classification. it accurately classifies the variety of wine and the production place ("origin denomination").[1] this is a subset of use of GAs in Agricultural Systems of which there are many applications. [2]

[1] Feature selection algorithms using Chilean wine chromatograms as examples by N.H.Beltran et al

[2] State of Art in Genetic Algorithms for Agricultural Systems by Bolboaca et al

Improve this answer
$\endgroup$
1
$\begingroup$

there are many papers on use of GAs for flight control in the aerospace field. many of these are published or searchable by IEEE explorer. the fitness function generally measures how well/effectively the algorithm controls the flight.

[1] Flight control system design and optimisation with a genetic algorithm by Fantinutto et al

[2] Application of genetic algorithms to hypersonic flight control. Austin, Jacobs.

[3] Multi-core implementation of F-16 flight surface control system using Genetic Algorithm based adaptive control algorithm, Xiaoru Wang

[4] Fuzzy logic control based on genetic algorithm to integrated flight control for hypersonic vehicles. by Wang Jian

Improve this answer
$\endgroup$
1
$\begingroup$

a remarkable, even extraordinary or paradigm shifting use of GAs, highly cited in later surveys, was pioneered by Koza to solve a video game "problem"— namely Pac Man for a proof of principle, but the concept can likely be applied to possibly almost any video game, and the results are definitely far from trivial or "toy".

that is, he evolved algorithms that implement actual behavior to win at playing the game for extended periods of time. results are on the level of performance of amateur or even advanced human players. a fitness function can be either points scored by the algorithm or length of time played (the later will presumably evolve algorithms that survive without scoring points, such as a classic case of "hunting" spaceships in the game Asteroids). the behavior is implemented with "primitives" (eg sense monsters/act by turning etc) and trees that represent the combinations of primitive strategies.

[1] Evolving Diverse Ms. Pac-Man Playing Agents Using Genetic Programming by Atif M. Alhejali and Simon M. Lucas

[2] Learning to Play Pac-Man: An Evolutionary, Rule-based Approach by Gallagher and Ryan

[3] Learning to Play Using Low-Complexity Rule-Based Policies: Illustrations through Ms. Pac-Man by István Szita András L~orincz

Improve this answer
$\endgroup$
2
  • $\begingroup$ TO be very nit-picky, I would draw a distinction between genetic programming, and genetic algorithms. Certainly they're closely related, though. $\endgroup$
    – Novak
    Sep 3, 2012 at 2:00
  • $\begingroup$ @novak agreed & thx for drawing out the distinction that was blurred here. roughly, GP is the use of GAs to discover algorithms, true? yes the behavior found/constructed is basically equivalent to an algorithm.. & of course the technique is probably widely applicable outside of video games although not aware of many examples so far.. its very advanced usage.. (although am reminded of another example of koza's which still uses trees in a clever way! need to post that). $\endgroup$
    – vzn
    Sep 3, 2012 at 2:59
1
$\begingroup$

The annual GECCO conference (pretty much the premier venue for evolutionary computation research) has a `Real World Applications' track.

See also this recent presentation:

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.