What are some common uses for genetic programming?

Question

Today I read this blog post by Roger Alsing on how to draw a replica of Mona Lisa using only 50 translucent polygons.

I am fond of the results for this particular case, so I was interested (and this is my question): how does genetic programming work and what other <strong> problems can be solved by genetic programming?

Answer 1

There is some debate as to whether Roger Mona Lisa's program is Genetic programming in general. This is similar to an evolution strategy (1 + 1) . Both methods are examples of a wider field of evolutionary computing, which also includes genetic algorithms .

Genetic programming (GP) is the process of developing computer programs (usually in the form of trees - often Lisp programs). If you ask specifically about the GP, John Cosa is widely regarded as a leading expert. His site contains many links to additional information. GP, as a rule, is very intensively calculated (for non-trivial problems, a large grid of machines is often used).

If you ask more generally, evolutionary algorithms (EAs) are usually used to provide good approximate solutions to problems that cannot be easily solved using other methods (such as NP-hard problems). Many optimization problems fall into this category. It may be too computationally intensive to find the exact solution, but sometimes the optimal solution is enough. In these situations, evolutionary methods can be effective. Due to their random nature, evolutionary algorithms never guarantee to find the optimal solution for any problem, but they often find a good solution if it exists.

Evolutionary algorithms can also be used to solve problems that people really don’t know how to solve. EA, without any prejudice or prejudice of people, can create amazing solutions that are comparable or better than the best human efforts. It is simply necessary that we can find a good solution if it were presented to us, even if we do not know how to create a good solution. In other words, we should be able to formulate an effective fitness function .

Some examples

• Sales traveler
• Sudoku

EDIT: The freely available book Field Guide to Genetic Programming contains examples of where the GP has led to human-beneficial results.

Answer 2

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

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

I believe that they mimicked the character’s nervous system and then randomized the compounds to some extent. Then they combined the “genes” of models that went further to create more and more “children” in successive generations. Really fun simulation work.

I also saw the genetic algorithms used in path finding machines, with ants looking for food a classic example.

Answer 3

Genetic algorithms can be used to solve most optimization problems. However, in many cases there are more advanced, more direct methods for solving them. He is in the class of metaprogramming algorithms, which means that he is able to adapt to everything that you can throw on him, given that you can create a method for coding a potential solution, combining / mutating decisions and deciding which decisions are better than others. GA has the advantage over other metaprogramming algorithms in that it can handle local maxima better than a clean hill climb algorithm, such as simulated annealing.

Answer 4

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

Answer 5

In my thesis, I used genetic programming to model the evolution of species based on the landscape, but this, of course, is the application of the A-life genetic algorithms.

GA problems are good at hill climbing issues . The problem is that, as a rule, it’s easier to solve most of these problems manually, if only the factors that determine the problem are unknown, in other words, you cannot in any other way achieve this knowledge, say things related to 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.

The fine-tuning situation that I did was to fine-tune several Othello AI players based on the same algorithms giving different styles of play, which made each opponent unique and with its own quirks, and then I decided from the first 16 AI that I used in his game. The advantage was that they were all very good players of more or less equal skill, so it was interesting for a human opponent because they could not guess the AI ​​as easily.

Answer 6

You must ask yourself: "Can I (a priori) define a function to determine how well a particular solution relates to other solutions?"

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

Answer 7

I have several projects using genetic algorithms. GAs are ideal for optimization tasks when you cannot develop a fully consistent, accurate algorithm to solve a problem. For example: what is the best combination of a car that characterizes it faster and at the same time more economical?

I'm currently developing a simple GA for developing playlists. My GA should find the best album / song combinations that are similar (this similarity will be “calculated” with last.fm) and offers playlists for me.

Answer 8

A new field has appeared in robotics called Evolutionary Robotics ( w: Evolutionary Robotics ), in which genetic algorithms (GA) are widely used.

See w: Genetic Algorithm :

Pseudocode of a simple genetic algorithm for generating

• Choose an initial population
• Assess the suitability of each person in a population
• Repeat until the end: (time limit is reached or sufficient suitability)
• Choose the best people to play
• Generation of a new generation through crossover and / or mutation (genetic surgery) and give birth to offspring
• Assess the individual suitability of the offspring.
• Replace the worst part of the population with offspring

The key is the reproduction part, which can occur sexually or erratically using the Crossover and Mutation genetic operators.