Genetic Programming

Michael Romanovsky

Genetic programs are a form of a pseudo-intelligent search in the space of computer programs or more generally, combinations of basic functions. (Multi-functions)

Genetic programs are WAY BETTER than Genetic Algorithms because the inherent structure of certain functions are always preserved, allowing one to grow much better results quicker. BUT , on a non-complex problem, they are essentially the same.

Genetic programs rely on the theory and fact of evolution to search through good and bad programs. Bad programs (or multi-functions) die and good programs (or multi-functions) have children..

There are at least 4 things the human programmer must provide in order to implement this successfully:

The fitness (whether a program is good or bad) is determined by a fitness function, which evaluates whether a program has achieved any amount of success in the stated goals.

A genetic program works by mutating and recombining functions (parts) of itself and other genetic programs in various ways. Each functional part that is possible to be created by such a program is set up correctly. That is, the program must know the syntax of the programming language.

A possible problem even in setting up functions is the creation of such things as infinite loops and memory overflows (things that are outside the parameters of the language or the machine). To deal with such problems, all programs must certain limits imposed on them, such as a time counter to deal with infinite loops.

Two very challenging part of creating programs that themselves create programs is the human decision of how and when to apply the mutations or recombinations. A mutation or recombination can have the following bad effects:

The one factor that one must take into consideration of creating a genetic program is the complexity of the problem. This can be divided into several steps:

The ultimate genetic program is one that would allow a user to ask for a certain program or program functionality and, based on the previous gathered knowledge about humans, what they want, and human interfaces, create several good possibilities which the human himself will pick to self-"evolve" what he or she wants. At the same time, the amount of possibilities must be minimal and only aspects that the computer does not know (but the human does) must be requested in the form of multiple solutions, such as the size and shape (scale).

The idea of genetic programming is broadly encompassed in the field of A-life. A-Life examines the effects of simulated organisms. These organisms adopt for mere survival, and sometimes must compete for the available resources with other organisms to survive. Most genetic programs do not compete directly with other genetic programs but instead try to adopt to the definition of success. (the fitness function = food+reproduction). However, sometimes the organisms compete with each other, randomly determining the fitness function based on the success to the goal of two or more organisms, but not the entire ecosystem.

One good and interesting example of genetic programming are the robots created by a computer in Jordan Pollack's lab.The robots evolve to efficiently walk from point A to point B.

Uses of fitness functions:

Genetic programming can enable decades of research to be simulated in a few minutes. Any research that does not rely on very precise implementation and many unrelated abstract concepts falls prey to today's genetic programming techniques. The ideas encompassed in genetic programming are both the future of all science and the also the past of our history, our evolution as a species.

Genetic programming LINKS!!

Koza - Genetic Programming animations.

Koza - 16 Attributes of a System for Automatic Programming.

BREAKTHROUGH GENETIC PROGRAMMING RESEARCH AT BRANDEIS!!!! (1)

BREAKTHROUGH GENETIC PROGRAMMING RESEARCH AT BRANDEIS!!!! (2)

Discusses "what is a genetic program" and how to implement one in C++.

Java "Interface" that gives a set of functions to "easily" create genetic programs.

Genetic Programming.com - Applied Genetic Programming Company

Koza's GA site with way too many links.