User:Pginty13/sandbox/Linear genetic programming

Linear genetic programming (LGP) is a subcategory of genetic programming (GP). Genetic programming is computerized testing and combination of a randomly generated population of computer programs to find a solution to a problem. In LGP, programs are executed in a linear fashion rather than the tree data structure of traditional GP. Linear genetic programs can be written in an imperative programming language such as C rather than a functional programming language like LISP.

Genetic Programming

Genetic programming applies Darwin's principle of natural selection to computer programs, running many combinations of randomly generated programs to get the best result possible (and hopefully solving the problem). LGP compares different programs based on a measure called fitness. Fitness represents how close a program is to solving the problem that the algorithm was intended to solve. Very unfit programs are discarded, while relatively fit programs are modified to find fitter ones (see Variation Operations) until eventually a solution is found.

LGP vs. Traditional GP

Typical genetic programming involves computer programs represented in memory as tree structures. In LGP, however, computer programs are represented as sequences of instructions. This representation of programs lends itself to writing program code in common imperative programming languages like C or Java. Traditional GP program structure, in contrast, lends itself to functional programming languages like LISP. Because of the high level of thinking involved with functional programming combined with the popularity of imperative programming, LGP is open to a wider range of programmers than traditional tree-based GP.

Instructions in LGP

In LGP, the set of operations that can be performed on an individual (program) is composed of arithmetic operations, conditional branches, and function calls. These operations are what LGPs use to attempt to solve the problem.

Instructions are either executed on two variables (operand variables), or on one variable and one integer constant. Below is a table illustrating the types of instructions in LGP.

(**)

Each instruction in LGP is kept in memory as a four-dimensional vector. This vector holds the instruction identifier (instruction type), the indexes of variables to be executed on, and optionally a constant value.

For example; consider the code segment (**). This instruction would be represented as the vector (id(+),i,j,c). The first vector component represents the operation, the second and third represent the indexes of variables to be used, and the fourth component represents a constant c.

Introns

An intron is a part of a program that has no influence on the output. These exist due to the random nature of genetic programming – certain randomly generated instructions will have no effect at all on data inputs. The following is an example of an intron inside a program.

       v[0] = v[0] + 1;
       v[0] = v[0] – 1;

Notice that this code segment will not have any effect on v[0], the variable that is supposed to be changed by the command.

Introns cause a problem in genetic programming because they waste a lot of time by forcing the computer to execute statements that do not affect the output. A major advantage to linear genetic programming over tree-based programming is that program structure allows for efficient removal of introns before they are executed countless times. This speeds up runtimes of LGPs significantly as compared to tree-based GPs.

A good estimate of runtime acceleration by intron removal is given by the following equation. (**) For example, if 40% of code is introns, your program will be about 67% faster if introns are removed at runtime. This is a significant time saver when dealing with a very large and complex LGP.

Variation Operations

A very important aspect of any genetic program is the methods it uses to vary the programs it is working with. Most GPs use a combination of some or all of the following variation operations:

• Reproduction – Copy a program without any changes.

• Recombination – Exchange substructures between two programs.

• Mutation – Exchange a segment of code inside a program at a random position.

These basic operations allow programs to mutate and eventually become improved versions of themselves.

Uses and Applications

In the 1990s, when genetic programming was beginning to gain popularity, GPs were often only used to solve simple tasks due to high computational intensity. With the recent massive gains in computer speeds and memory, however, GPs have been able to produce outstanding results in areas such as quantum computing, electronic design, and game playing.

As GPs in general and LGPs in particular continue to advance technologically, the possibilities for applications of this coding technique advance significantly as well. Computer programs that program themselves is a very powerful technology with an exciting future.