[Icfp04-discuss] Evolutionary Ants

[Joseph Gentle]

Carlos Scheidegger wrote:

>>1. STarting off with an extremely simple ant (~10 lines)
>>2. Randomly either:
>> - Changing states
>> - Deleting states
>> - Adding states
>> - Merge states
>>3. Change/delete/add would affect a random number of states from 1 to 4
>>4. Merge operations would merge random chunks from two ants. This needed
>>a lot of work and is where a higher level language would be far more
>>effective.
>>    
>>
>Did you use relative addressing or something? Crossover operations are
>the really important parts of a GA, because they are the ones that
>eventually recombine the good features of two different good
>individuals. Without relative addressing, I can't see crossover doing
>that at all.
>
>  
>
We merged in strands of operations and then readdressed them I think - 
you're right; i don't think it was all that effective.

>>5 Only 12 ants competed in each generation.  3 survived. For some reason
>>this seemed to produce smart ants *MUCH* faster than generation sizes
>>~100 (which is what I used at first).
>>    
>>
>Hmm. I'd hazard a guess that this was happening because most of the GA
>operations were generating worse ants than original. Have you tried to
>check whether the population converges to one of the ants at the first
>generations? I think this may be happening, and then you end up with
>pretty much just a randomized search. Which sort of works, but you
>should just use population size = 1 then :)
>  
>
Heh - probably worth a look. It was very interesting - I ran the 
simulation on 3 processors and they all reached very different mean and 
maximum scores (in terms of food collected) in each generation. Watching 
the actual simulations however the ants definitely *did* get smarter. 
Some started following ant trails left behind by ants in front. Some 
started travelling vast distances before changing direction. Others just 
didn't work at all.

If I were to do the problem again (strongly considering this once my uni 
holidays start) I'd use/write a compiler to a higher level language then 
use that for merging.

>I'd try to do the crossover by analyzing control flow of the assembly
>language and switching a contiguous block for another. Mutations would
>include changing the sense condition and direction, among other
>things. Another interesting thing would be to inject NOP operations in
>the population, to allow for variation without directly affecting ant
>individuals. Note that for that to work you'll either need to disable
>optimizers, or use higher-level languages. What this tries to do is to
>create "introns" - pieces of the genotype that are not expressed in
>the individuals. There's lots of evidence from the GP community that
>fitness is directly related to the amount of introns in the genotype -
>they serve to prevent hazardous crossovers, among other things.
>I remember reading this in Peter Bentley's "Evolutionary Design..."
>book, but I'm too lazy to pick the accurate reference right now :)
>
>  
>
Heh i really should learn this stuff properly. This was the first GA 
I've written and I don't know most of the theory (just read a few 
websites a few years ago and talked to people about it... never properly 
learnt it).

Interesting stuff! I'll have to read up on it all :]

-J

>-carlos
>
>  
>