Your skill will accomplishwhat the force of many cannot PerlMonks

### Re: A Beginning Guide To Evolutionary Algorithms

by AssFace (Pilgrim)
 on Oct 20, 2003 at 16:12 UTC ( #300632=note: print w/replies, xml ) 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
Node Status?
node history
Node Type: note [id://300632]
help
Chatterbox?
 [LanX]: qwiud you sthink so? [LanX]: zxwqbd good idea! :) LanX embraces his new habit spqopiwjdnq [ambrus]: qQUkZTmHTuKxStGT- BzTIK9gdudif7TkTLI t3mnF144UaAZjkknXY 8nN-QM19wHBsTrp5vB lEYU_Kksa7X1RIBB4x EWLD5X7SW3jGX5ryfN OMn_yL5FTdQxzjhtyX mKN9sjUCzBNHK5Rrp0 S2WMUvIb1i9aZFgjtq VR0GH1bjPMvm1G16iz hBqc1U6toPd4FbJOFj VsOeT745AN1_pO88rD SRAYKtBZwCZedESZmN mvutrOTHiSNwflB- pRfn_k [Eily]: so far it seems to work Your Mother reminds the monks they should be grateful not to share an office, lest they be subjugated to constant inanities like, "Czech please!" [LanX]: what's strange is that the "Cowboy you said this already" message is missing #dqiwd [LanX]: YM: BTW learn to mute your humanity [Your Mother]: Cumin? Now I want tacos...

How do I use this? | Other CB clients
Other Users?
Others studying the Monastery: (14)
As of 2017-03-27 16:55 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Should Pluto Get Its Planethood Back?

Results (320 votes). Check out past polls.