Come for the quick hacks, stay for the epiphanies. PerlMonks

### Re: A Beginning Guide To Evolutionary Algorithms

by AssFace (Pilgrim)
 on Oct 20, 2003 at 16:12 UTC Need Help??

in reply to A Beginning Guide To Evolutionary Algorithms

Also, don't forget the variant on that that is evolutionary programming. An evolutionary algorithm takes a result, usually a string, and manipulates it so that it gets progressively better over time based on some scoring system.

Evolutionary programming does a similar thing, but with the program code itself.
An example of this is in the game GridWars, the team that came in second used a program that was all evolutionarily built. 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.

I haven't yet tried it myself with eval, but I suspect it would be relatively easy to implement in Perl.

The idea is that you have your desired result, and instead of manipulating your string as the desired output - you manipulate the code that generates your output. Usually this means adding if/then statements and adjusting the values that they compare, and perhaps nesting them as well.
I haven't ever written in Lisp, but I have read that it is relatively easy to implement in Lisp.

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.

-------------------------------------------------------------------
There are some odd things afoot now, in the Villa Straylight.
• Comment on Re: A Beginning Guide To Evolutionary Algorithms

Replies are listed 'Best First'.
Re: Re: A Beginning Guide To Evolutionary Algorithms
by 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:

```  data vector         = (x1,..,x5) = (3,5,2,7,2)
comparison operator = greater-than

isac list:
1: (x1, x3, jump, 3) # if (x1 > x3) goto 3;
2: (x5, x3, noop, 1) # if (x5 > x3) noop;
3: (x2, x1, foo,  5) # if (x2 > x1) return "foo";
4: ...
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.

Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://300632]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others contemplating the Monastery: (4)
As of 2024-02-23 06:50 GMT
Voting Booth?
My favourite way to spend a leap day ...

Results (22 votes). Check out past polls.