« The far Left wants the draft | HomePage | 3.8 Genetic Programming »
Saturday, June 04, 20051117864200
3.8 Genetic Programming
Note: This is an excerpt from a draft of my thesis, A Computer Model of National Behavior. The introduction and table of contents
are also available
3.8 Genetic Programming
Genetic Programming (GP) is a significant extension of GAs. Gibbs states that GA was developed by Dr. John Koza in 1992 “to evolve entire programs of virtually any size and form.” Though all GP programs (GPPs) can be seen as GAs, Dobbs show GPPs are special in two related ways. GPPs deals with populations of variable-length chromosomes, and every member of the population is itself a program. These are important distinctions, because it allows for much more variation.
The difference between GPPS and GAs can best be understood by examples. Consider breeding the following two C programs:
for (x=0;x<10;x++) { printf(“Hello, world!\n”); }
and
int x;
x = 5;
if (x<5) { printf(“X is less than 5.\n”); }
After simplifying them to the pseudocode, they reduce to.
x := 0
while:
if x < 10 then
goto end
end ifprint “Hello world!”
x := x + 1
goto while
end:
and
x := 10
if x < 5 then
print “X is less than 5”
end if
DNA has rules for how genes can be paired. GP can have similar rules, so that no illegal statements are made, so that the system wastes no time attempting to run a program that will not even compile. However, there's still a very large number of possible combinations. To continue the example, the genetic pairing of the two parent programs produced the following child. The child shares most of its structure with the first program, but one of the conditions now comes from the second program.
x := 0
while:
if x < 5 then
print “X is less than 5”
end if
print “Hello world!”
x := x + 1
goto while
end:
Then the GP system would test this program to see if it is more or less fit. If the goal is to maximize text output it succeeds, as it will print out an infinite amount of text. If the goal is to type out the letter X as much as possible it also succeeds, because it will do this five times, more than either parent. If the goal is to minimize program execution time it will fail abysmally. The example GP generated program can never end.
Thus, the selection mode is non-tournament, the data manipulated is code, and the chromosomes are variable lengthened, but otherwise GP is merely a subset of GA.
These seemingly small changes from GAs to GP have a huge effects. Instead of changing some values, we are changing the logic itself. This is very powerful, and GP would bring some advantages to the model. Instead of the nations modeled changing their behavior only under the narrow ranges of their attributes they could possess a complex internal logic. GP also allows the developer of the system to be relatively ignorant of how to implement it, because implementation is taken care of by the system itself.
However, GP is not applicable in this case. Two serious faults prevent it from being implemented in the model. GP would both limit the applicability of the model and make the model unintelligible.
For all of its innovation GP is a limiting tool, especially when compared to GAs. Because GAs modify only values, the effects of small changes will tend to be relatively small. Of course the magnitudes of effects will differ, but wildly unpredictable results would indicate a serious problem. However, this is what can be expected under GP. Discussing a relatively simple attempt to produce satellite guidance systems, Gibbs notes that “when [the GP system] was presented with situations it had never encountered, the program failed, a common problem with evolved software.” Among intelligent creatures, actual failure due to inability to adapt is thankfully rare.
GP programs can be very strange and inscrutable, like DNA. Willihnganz warns that evolved software programs are “often convoluted, bizarrely multiplayed creations, nothing like the software a human might write.” One AI researches discovered that GP correctly programmed the interface to an artificial limb – in one line of incomprehensible code. As it would be impossible to explain why something is happening under a GP approach, the model would not be useful.
Computer Science Thesis Index
00:50 Posted by Dan tdaxp in Thesis | Permalink | Comments (0) | Email this