Both are specific types of a broad class of what are now usually called Evolutionary Algorithms. There's no single definition of what makes an Evolutionary Algorithm, but it's generally construed to be very broad. A rough description might be any search method that starts with a population of one or more stochastically generated candidate solutions to a problem, applies operators to those solutions to produce new solutions, and applies some form of selection to guide the process towards better solutions over time.
Note: This implies some encoding mechanism for solutions, which might be as simple as just recording the parameters to the problem as numbers directly, or may be more complex, binary coded, represented as finite state machines, represented as program code, or any other representation that can be decoded and evaluated in a programmable way.
Also note: This definition can encompass all sorts of things we wouldn't necessarily call "GAs" -- things like random hill climbers, simulated annealing, etc. Most of what we actually call evolutionary methods are a bit more restricted. They typically use a population much larger than one, the operators are generally some form of binary crossover and unary mutation, and a handful of well known selection mechanisms are used.
With that in mind, we can sketch out an abstract form of an evolutionary algorithm:
Generate initial population of size N;
while(offspring population not full)
insert offspring into offspring population;
select survivors for next generation;
While this is obviously highly abstracted version, both "Genetic Algorithms" and "Genetic Programming" match this template. The differences are almost entirely in how solutions are encoded and how they are evaluated.
The canonical "Genetic Algorithm" uses a binary encoding of all parameters, but aside from historical references, we don't really consider that to be a requirement anymore. For solving the traveling salesman problem, for instance, the standard representation would be a permutation of the city labels. In any case, for a GA, we have program code that evaluates how good a particular solution is for solving our problem, and we simply feed it evolved parameters. Imagine you're optimizing the design of a wind turbine. For a GA, you'd have code that took as parameters, all the important properties of a turbine, and that code would spit out a number, efficiency or whatever you're trying to optimize. We can encode those properties as real numbers, binary encoded numbers, gray-coded, whatever, but we always decode them into the form required by the fitness function.
Genetic programming is different. Rather than evolving parameters, we're evolving executable code itself. So the representation generally isn't something like binary-coded decimal numbers, but rather abstract syntax trees, often expressed in syntactically regular languages like Lisp. It's easiest to see this with an example, and the "Hello world" of GP is undoubtedly symbolic regression.
Imagine you have some set of variables
(x1, x2, x3), and for each, you know the value
y = f(x1, x2, x3). The symbolic regression problem is to find an expression that most accurately matches the unknown function f. In classical regression analysis, we would first select a model -- we make an assumption that f is linear, quadratic, whatever. For the sake of simplicity, let's assume a linear model. This means that
f(x1, x2, x3) = ax1 + bx2 + cx3 + d. We simply minimize an error term over the training examples to find the values of
a, b, c, and
dthat give us the "correct" model. One major problem with this approach is that the assumptions required are very strong. If you guess the wrong model for f, you're going to get poor results.
With GP, you relax the assumptions somewhat. Rather than say "f must be linear", we say something like, "f must be expressed using only arithmetic operators, trigonometric functions, exponentials, and numeric constants". We can then generate a bunch of random expressions as candidates for our unknown f. We might start with
x1^2 + 4.2*(x2-2) - x1 + 2*x3*s2. This expression is our representation (probably suitably encoded as a Lisp expression because this makes it much easier to perform the genetic operators). We can recombine and mutate the expressions themselves to generate new expressions. To evaluate the fitness of an expression, we can compute the error across our training data. Other than the encoding and the evaluation method, the standard evolutionary framework applies.
I've mentioned Lisp a few times. The earliest GP work was almost exclusively done in Lisp because it makes it easy to cut and splice programs together. A Lisp expression is a straightforward translation of the parse tree, so cutting a branch off of the parse tree and swapping it with a branch from another parse tree can be done easily. Trying to do similar things with, say, C or Java, can be done, but is much more difficult to do without generating syntax errors. In more recent times, GP approaches have broadened a bit, and there are now methods using concatenative languages and other choices, but Lisp and Lisp-family languages (e.g., Clojure) are still popular as well.
There are a few other minor differences that pop up. Practitioners found that the normal EA parameters that work well for GAs often don't work well for GP. Things like the population size can differ dramatically, with 100 or so being very common in GAs, while GP might use 500 or 1000 individuals in a population. GP approaches typically require some additional methods to control things like bloat, where the GP system may evolve expressions like
2 + 2 - 1 + x + 4 - 2 * x instead of the equivalent
3x+7 or evolve the same sub-expressions over and over again.
Because of these differences, GA and GP researchers tend to work in fairly different ways. Most people are specialized in one camp or the other, where each knows mostly what the others are doing, but don't delve much into the specifics.