Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What are the differences between genetic algorithms and genetic programming?

I would like to have a simple explanation of the differences between genetic algorithms and genetic programming (without too much programming jargon). Examples would also be appreciated.

Apparently, in genetic programming, solutions are computer programs. On the other hand, genetic algorithms represent a solution as a string of numbers. Any other differences?

like image 775
bjrnt Avatar asked Sep 29 '10 08:09

bjrnt


People also ask

What do you mean by genetic programming?

In artificial intelligence, genetic programming (GP) is a technique of evolving programs, starting from a population of unfit (usually random) programs, fit for a particular task by applying operations analogous to natural genetic processes to the population of programs.

What are the different types of genetic programming?

The various types of Genetic Programming include:Grammatical Evolution. Extended Compact Genetic Programming (ECGP) Cartesian Genetic Programming (CGP) Probabilistic Incremental Program Evolution (PIPE)

What is the difference between genetic algorithm and machine learning?

Genetic algorithms are used in artificial intelligence like other search algorithms are used in artificial intelligence — to search a space of potential solutions to find one which solves the problem. In machine learning we are trying to create solutions to some problem by using data or examples.

What are the main similarities and differences between evolutionary programming and genetic programming?

Evolutionary programming mainly uses mutation. Evolutionary programming is one of the four major evolutionary algorithm paradigms. It is similar to genetic programming, but the structure of the program to be optimized is fixed, while its numerical parameters are allowed to evolve.


2 Answers

Genetic algorithms (GA) are search algorithms that mimic the process of natural evolution, where each individual is a candidate solution: individuals are generally "raw data" (in whatever encoding format has been defined).

Genetic programming (GP) is considered a special case of GA, where each individual is a computer program (not just "raw data"). GP explore the algorithmic search space and evolve computer programs to perform a defined task.

like image 115
JohnIdol Avatar answered Sep 18 '22 03:09

JohnIdol


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
  • Use an explicit structure to avoid operator precedence entirely
like image 33
peterjwest Avatar answered Sep 19 '22 03:09

peterjwest