I've been reading quite a lot about genetic algorithms and genetic programming. I find it interesting, to do my final semester thesis, related to these topics. Even though I understand the major difference between them, I do not understand, which one to use, given a situation. Could someone please tell me or point me to any resources that answer a few or all of the following questions?

  1. Apart from the major difference between genetic algorithms and genetic programming are there any other subtle differences? From what I understand, there are subtle mathematical differences between them that dictates which one to use in a given situation.

  2. Is it possible that there are problems that can be solved by one but not the other? And are there any problems that cannot be solved by either of them?

  3. Apart from genetic algorithms and genetic programming are there any other variations in evolutionary computing?

  4. Neural networks benefit from the availability of a large volume of data depending on the problem being solved. Is it true for genetic algorithms or genetic programming as well? If 'yes', how would you combine the use of such a large volume of data with genetic algorithms/programming? Because, all I've seen so far, are simple examples that did not require a large body of data.

At the moment, these are the questions on my mind. Thank you.

asked Dec 30 '10 at 11:36

carpi's gravatar image

carpi
36115

edited Dec 30 '10 at 11:54


5 Answers:

95

  1. As far as I remember, Genetic Programming is used for tree like structures, but is nothing but a special case of genetic algorithms.

  2. If it is not a tree like structure, it might not be solved other way but with GP.

  3. Here there are some variations in Wikipedia

  4. GA principle is to find an optimum for a given problem. So you need : a function to optimize, a good mutation function, and a lot of luck. by principle GA do not requires tremendous amounts of information, since you already know the function to be optimized, the problem with Neural networks is that you are trying to infer that function, so you need lots of data that gives you the best possible approximation to your space.

answered Dec 31 '10 at 01:16

Leon%20Palafox's gravatar image

Leon Palafox ♦
40007093128

edited Dec 31 '10 at 01:23

@Leon Palafox: You said "If its not a tree like structure, it might not be solved other way but with GP". What do you meant by that? Are you saying that any problem can be solved with GP as long as it is represented as a tree like structure?

(Dec 31 '10 at 04:57) carpi

GP is the specific case of GA when a problem has a tree structure, not every problem can be represented like that, and you might get into trouble by doing so.

But essentially yes, a GA is part of a GP, just that when the problem has a tree structure.

(Dec 31 '10 at 05:53) Leon Palafox ♦

A tree is not the only way to store a program. For example, for stack-based languages like Forth, programs can be stored as an array.

(Dec 06 '11 at 13:50) Mathieu Blondel

Genetic algorithms are optimizers. Genetic programming is when genetic algorithms are applied to creating code. That code need not be in tree form. See, for instance, "Genetic Programming, An Introduction", by Banzhaf, Nordin, Keller and Francone.

answered Jan 23 '11 at 05:15

Will%20Dwinnell's gravatar image

Will Dwinnell
312210

1.Generally, GA's are applied to instances of a problem, with the structure of the genome conveying expectations about the form of a solution. GP is usually applied to a get a generic solution to a class of problems, with less guidance towards the desired form of the solution. However, there's a gray area in the middle of very expressive GA, and GP with tight, domain specific operators/functions.

2.Again, speaking in generalities, GA's aren't very good for very unstructured problems or very general problems (you wouldn't evolve an arbitrary robot motion problem with a single GA, although you could use it for solving a single, instantiated motion problem). GP in principal can solve anything a GA could, but in practice the computational cycles needed to find solutions can be prohibitive, so any time you've got an optimization problem (which assignment of n variables is best) you're likely to prefer a GA. Theoretically, any solvable problem could eventually be solved with a properly instantiated GP/GA, but in practice there's a number of properties that make the techniques untenable: poor or misleading discrimination by evaluation functions (e.g., no way to differentiate a poor solution from a so-so solution), high complexity (don't expect GP to evolve a 1M line application), expensive evaluation functions (e.g., humans need to manually evaluate every output).

3.(answered in another answer)

4.You need enough data that a generalization can be obtained. Too little can miss local behaviors of a function, or lead to overfitting. In general, if the complexity of the problem is so great that you need huge quantities of data, you're probably going to have to encode more knowledge into the genome or function set so that less data is needed. Additionally, at least in GP, it's often desirable to have a sparse sampling for the evaluation of each iteration (changing the sampling each iteration to avoid overfitting,etc.): this can be an additional source of randomness that lets novel code that performs well in some small subset of the problem space reproduce, in the hope that mutations/crossover will generalize that contribution, or make use of it for that portion of the problem.

answered Jan 24 '11 at 13:35

Paul%20Barba's gravatar image

Paul Barba
4464916

edited Jan 24 '11 at 13:36

The main difference between genetic programming and genetic algorithm is the representation of the solution. Genetic programming creates computer programs in the lisp or schema computer languages as the solution. Genetic algorithm creat a string of numbers that represent the solution.

answered Dec 04 '11 at 15:32

sangita%20aggarwal's gravatar image

sangita aggarwal
1

The authors of Gene Expression Programming make some pretty amazing claims, compared to GP. It might be fun to test those success stories in a semester project.

answered Dec 06 '11 at 13:13

Art%20Munson's gravatar image

Art Munson
64611316

When I first came across GEP it looked interesting, especially since I have a biological background (I especially like the non-coding regions). As a firm believer that you don't understand an algorithm until you code, I wrote an implementation of GEP. My biggest issue with it is the requirement that you specify the linking-functions, which seems like cheating to me. While there is an extension to GEP that allows you to learn the linking function, when using the extension, I was unable to get it to converge. I went back and used vanilla GP with much better success.

Also, as a side note, I'm on the side of the punctuated equilibrium theorists, and don't believe that cross-over should cause genetic drift, but rather act as a normalization of the population. Thus, the problem GP has with cross-over may really be a non-issue.

(Dec 09 '11 at 17:20) nop
Your answer
toggle preview

powered by OSQA

User submitted content is under Creative Commons: Attribution - Share Alike; Other things copyright (C) 2010, MetaOptimize LLC.