What are the typical use cases of Genetic Programming?

Asked 10/12, 2008 at 8:58 Answered 14/12, 2008 at 22:38

Today I read this blog entry by Roger Alsing about how to paint a replica of the Mona Lisa using only 50 semi transparent polygons.

I'm fascinated with the results for that particular case, so I was wondering (and this is my question): how does genetic programming work and what other problems could be solved by genetic programming?

Ebro answered 10/12, 2008 at 8:58 Comment(1)

In general, all AI methods are good when you have no idea how to solve a problem. – Gerrald 14/12, 2008 at 22:54

There is some debate as to whether Roger's Mona Lisa program is Genetic Programming at all. It seems to be closer to a (1 + 1) Evolution Strategy. Both techniques are examples of the broader field of Evolutionary Computation, which also includes Genetic Algorithms.

Genetic Programming (GP) is the process of evolving computer programs (usually in the form of trees - often Lisp programs). If you are asking specifically about GP, John Koza is widely regarded as the leading expert. His website includes lots of links to more information. GP is typically very computationally intensive (for non-trivial problems it often involves a large grid of machines).

If you are asking more generally, evolutionary algorithms (EAs) are typically used to provide good approximate solutions to problems that cannot be solved easily using other techniques (such as NP-hard problems). Many optimisation problems fall into this category. It may be too computationally-intensive to find an exact solution but sometimes a near-optimal solution is sufficient. In these situations evolutionary techniques can be effective. Due to their random nature, evolutionary algorithms are never guaranteed to find an optimal solution for any problem, but they will often find a good solution if one exists.

Evolutionary algorithms can also be used to tackle problems that humans don't really know how to solve. An EA, free of any human preconceptions or biases, can generate surprising solutions that are comparable to, or better than, the best human-generated efforts. It is merely necessary that we can recognise a good solution if it were presented to us, even if we don't know how to create a good solution. In other words, we need to be able to formulate an effective fitness function.

Some Examples

EDIT: The freely-available book, A Field Guide to Genetic Programming, contains examples of where GP has produced human-competitive results.

Bellabelladonna answered 10/12, 2008 at 12:21 Comment(2)

The debate is kinda stupid. The definition is clear, and the Mona Lisa code lacks recombination. Besides being the wrong definition, using recombination meaningfully could reduce the iteration count drastically (albeit at the cost of more expensive iterations), potentially improving overall runtime. – Zlatoust 20/12, 2008 at 22:55

Detailed sudoku generator anthony-tresontani.github.com/Python/2012/12/31/… – Luncheon 4/1, 2013 at 6:50

Interestingly enough, the company behind the dynamic character animation used in games like Grand Theft Auto IV and the latest Star Wars game (The Force Unleashed) used genetic programming to develop movement algorithms. The company's website is here and the videos are very impressive:

http://www.naturalmotion.com/euphoria.htm

I believe they simulated the nervous system of the character, then randomised the connections to some extent. They then combined the 'genes' of the models that walked furthest to create more and more able 'children' in successive generations. Really fascinating simulation work.

I've also seen genetic algorithms used in path finding automata, with food-seeking ants being the classic example.

Beaton answered 10/12, 2008 at 12:55 Comment(2)

The ant example you mention isn't a Genetic Algorithm, its what's called an Ant Colony algorithm, they have similar purposes but the algorithms are totally different – Baby 11/12, 2008 at 6:40

@Robert. The ant example he mentioned is actually a classic toy example for GP, it is completely different from the Ant Colony algorithm. – Whitehouse 9/3, 2011 at 7:43

Genetic algorithms can be used to solve most any optimization problem. However, in a lot of cases, there are better, more direct methods to solve them. It is in the class of meta-programming algorithms, which means that it is able to adapt to pretty much anything you can throw at it, given that you can generate a method of encoding a potential solution, combining/mutating solutions, and deciding which solutions are better than others. GA has an advantage over other meta-programming algorithms in that it can handle local maxima better than a pure hill-climbing algorithm, like simulated annealing.

Henderson answered 10/12, 2008 at 9:33 Comment(0)

I used genetic programming in my thesis to simulate evolution of species based on terrain, but that is of course the A-life application of genetic algorithms.

The problems GA are good at are hill-climbing problems. Problem is that normally it's easier to solve most of these problems by hand, unless the factors that define the problem are unknown, in other words you can't achieve that knowledge somehow else, say things related with societies and communities, or in situations where you have a good algorithm but you need to fine tune the parameters, here GA are very useful.

A situation of fine tuning I've done was to fine tune several Othello AI players based on the same algorithms, giving each different play styles, thus making each opponent unique and with its own quirks, then I had them compete to cull out the top 16 AI's that I used in my game. The advantage was they were all very good players of more or less equal skill, so it was interesting for the human opponent because they couldn't guess the AI as easily.

Baby answered 10/12, 2008 at 9:11 Comment(1)

"I used genetic programming in my thesis to simulate evolution of species based on terrain" - something online that one can peek? :P – Winther 11/9, 2012 at 21:31

http://en.wikipedia.org/wiki/Genetic_algorithm#Problem_domains

Bibliomania answered 10/12, 2008 at 9:10 Comment(0)

You should ask yourself : "Can I (a priori) define a function to determine how good a particular solution is relative to other solutions?"

In the mona lisa example, you can easily determine if the new painting looks more like the source image than the previous painting, so Genetic Programming can be "easily" applied.

Curricle answered 10/12, 2008 at 9:30 Comment(0)

I have some projects using Genetic Algorithms. GA are ideal for optimization problems, when you cannot develop a fully sequential, exact algorithm do solve a problem. For example: what's the best combination of a car characteristcs to make it faster and at the same time more economic?

At the moment I'm developing a simple GA to elaborate playlists. My GA has to find the better combinations of albums/songs that are similar (this similarity will be "calculated" with the help of last.fm) and suggests playlists for me.

Zareba answered 10/12, 2008 at 12:59 Comment(1)

Wow, the playlist software sounds like a fun project. I hope you'll share what you learn from it with the public :) – Beaton 10/12, 2008 at 15:31

There's an emerging field in robotics called Evolutionary Robotics (w:Evolutionary Robotics), which uses genetic algorithms (GA) heavily.

See w:Genetic Algorithm:

Simple generational genetic algorithm pseudocode

Choose initial population

Evaluate the fitness of each individual in the population

Repeat until termination: (time limit or sufficient fitness achieved)

Select best-ranking individuals to reproduce

Breed new generation through crossover and/or mutation (genetic operations) and give birth to offspring

Evaluate the individual fitnesses of the offspring

Replace worst ranked part of population with offspring

The key is the reproduction part, which could happen sexually or asexually, using genetic operators Crossover and Mutation.

Sungkiang answered 14/12, 2008 at 22:38 Comment(0)

Simple generational genetic algorithm pseudocode

Recommended topics

Hot tags