What Is Genetic Programming?
Genetic programming is the process of using one computer program to write another computer program using evolutionary algorithm-based methodology. This process is often compared to linear programming, in which the programmer writes specific instructions for the computer to carry out. LISP and Scheme are the most common programming languages for this type of work due to their high level functionality and flexibility. As a result of its conceptual similarity to biological evolution, genetic programming is often cited as an example of bio-inspired computing.
Genetic programs (GPs) work by generating and running thousands of programs and chooses the most effective to use. For example, a GP might be used to create a program to draw a sketch of a photograph. The first thing that the GP would do is create a set of programs that use various computer drawing functions in random combinations. Then the GP would run each of these programs in order, outputting the results of each to image files.
The next step for the GP is selecting the best of those programs from the set. This process is generally the most difficult part of genetic programming. In the case of the drawing program, the GP would use image comparison software to determine which of the random drawings was most similar to the image the software was attempting to draw. Of the randomly generated programs, the GP would select the top several and discard the rest. The selection process is known as fitness evaluation, and is generally considered to be the most difficult part of genetic programming.
Once the top few programs have been selected, the GP will use them as the basis of a new batch of programs. Each new batch is called a generation. The two ways of creating the new generation are mutation and crossover. Mutation works by taking one of the existing programs and making random changes to it, hopefully for the better. Crossover, also called breeding, works by taking two of the top programs and combining elements of them to create new programs.
After creating a new batch of programs, the GP repeats the process of running and evaluating them, and then repeats the selection, elimination, and generation processes. GPs will frequently run hundreds of generations before finding a single program with a satisfactory result. Despite this limitation, genetic programming is a common way to solve some types of difficult computing problems, including robotic engineering and artificial intelligence problems.
@hamje32: To avoid random events such as the one you are talking about, each proposed solution is generally run several times to reduce the impact of one off lucky coincidences. Some randomness is usually introduced in the selection process as well, so that better programs only tend to be selected more often, but worse programs may be selected every now and then anyway. This is to reduce premature stagnation (where a local optimum is reached, and the fitness stagnates around that optimum).
@hamje32 - I don’t think that the genetic programming example given in the article is meant to be as completely random as you think. The way I understand it, the program draws a sketch using random functions.
That much is true. If the sketch is good, then the program is deemed good. I would think at that point, the program would try to figure out, so to speak, what it did correctly to draw that picture the right way.
The program would “learn” in other words, and subsequent drawing operations would not be so random. That’s how I take it. Genetic programming is supposed to constantly be feeding itself information about how to learn.
Perhaps I don’t understand it completely, but the randomness of the genetic programming model would be misleading. What if a program accidentally won a game of tic-tac-toe?
Does that mean we treat that program as “good” simply because it randomly won the game, and then move it up the evolutionary computing chain? Anyway, it does appear to work so I guess that I will have to just chalk it up to my own ignorance.
I just wish that the genetic programming model could be expanded to perform larger tasks, like write my own programs at the software company where I work.
Post your comments