Question

Difference between genetic algorithm and genetic programming

Answer 1

Answer:

Genetic programming and genetic algorithms are very similar. They are both used to evolve the answer to a problem, by comparing the fitness of each candidate in a population of potential candidates over many generations.

Each generation, new candidates are found by randomly changing (mutation) or swapping parts (crossover) of other candidates. The least 'fit' candidates are removed from the population.

Structural differences

The main difference between them is the representation of the algorithm/program.

A genetic algorithm is represented as a list of actions and values, often a string. for example:

1+x*3-5*6

A parser has to be written for this encoding, to understand how to turn this into a function. The resulting function might look like this:

function(x) { return 1 * x * 3 - 5 * 6; }

The parser also needs to know how to deal with invalid states, because mutation and crossover operations don't care about the semantics of the algorithm, for example the following string could be produced: 1+/3-2*. An approach needs to be decided to deal with these invalid states.

A genetic program is represented as a tree structure of actions and values, usually a nested data structure. Here's the same example, illustrated as a tree:

-

/ \

* *

/ \ / \

1 * 5 6

/ \

x 3

A parser also has to be written for this encoding, but genetic programming does not (usually) produce invalid states because mutation and crossover operations work within the structure of the tree.

Practical differences

Genetic algorithms

Inherently have a fixed length, meaning the resulting function has bounded complexity

Often produces invalid states, so these need to be handled non-destructively

Often rely on operator precedence (e.g. in our example multiplication happens before subtraction) which could be seen as a limitation

Genetic programs

Inherently have a variable length, meaning they are more flexible, but often grow in complexity

Rarely produces invalid states, these can usually be discarded