|Perl Monk, Perl Meditation
Re: Re: A Beginning Guide To Evolutionary Algorithmsby blokhead (Monsignor)
|on Oct 20, 2003 at 18:52 UTC
In evolutionary programming (also known as genetic programming), you evolve structures that are programs. The most common way to do this is by evolving lists of statements or parse trees / abstract syntax trees.
Interestingly enough, in that particular competition, speed matters very much, and that is one drawback of evolutionary programming - it tends to make bulky code that isn't always as fast as it could be.This is something we studied in my EA class. The reason for this is that evolution tends "pad" its solutions to protect against mutation. The best solutions you find will usually have many sections of dead/unreachable code and/or redundancy, which will increase the probability of a mutation not causing harm to the "real" code. It also increases the change that the important code is not split during a crossover as well. An interesting research topic is how the average percentage of dead code is related to your mutation rate.
I haven't yet tried it myself with eval, but I suspect it would be relatively easy to implement in Perl.You may wish to look at Genetic Programming or breeding Perls, which is a neat exercise. I currently have a few relevant Perl/EA links on my homenode at the moment. And also, for the moment, I have in my scratchpad a reimplementation of Breeding Perls using one of my own EA modules. It uses a fixed-length array of simple Perl statements, and uses eval to score the fitness.
Usually this means adding if/then statements and adjusting the values that they compare, and perhaps nesting them as well.For nesting, conditionals, etc, you would need to evolve an abstract syntax tree instead of just a list of statements (that is, if you want the code to actually be syntactically valid for each individual). But another alternative very similar to what you suggest is called an ISAc list. I forget what it stands for, but it was invented by some guy from a previous semester of the EA class I took. It's very much like modern assembly codes with only jump and no-op instructions. But each instruction has a boolean predicate based on two data values and a comparison operator. I'm a little short on time right now, but I can come back a bit later and explain this in full..
OK, an ISAc list has 4 parts, two offsets into a data vector, an action, and a jump location. The environment defines a data vector, which holds some values. Some values may be constants, some may change each time (like a list of the opponents' last few moves, etc). The environment also defines a comparison operator. To execute each instruction, the two data-vector values are compared, and if the comparison succeeded the action is taken. Otherwise, flow continues to the next statement (looping around at the bottom). This will probably be clearer with an example:
Two actions, "jump" and "noop" are special flow-control actions. Other actions cause a return from the structure, as the program's "final answer." Anyway, the lists seem to evolve well, as crossovers and mutations are quite straight-forward.
This is a good way to let a program design a program for you. Then later on it usually benefits the speed of the program for a human to go over the final result and look for areas that it could be changed to optimize various parts of it.The biggest problem is that computer-evolved programs are notoriously impossible to understand. You don't need to look any farther than the example outputs of Breeding Perls. It may not be possible to do much more with evolved programs than just remove dead/unreachable code, but this is an actively researched field and you may find some interesting papers out there.