Genesis
Concurrent evolutionary algorithms with Perl 6
JJ Merelo, @jjmerelo
Yep, you've probably seen this before. It's cooler now, and it works, as in actually scaling. I keep doing this, but well, it keeps me in the publish and perish loop, so it's OK.
EAs are optimization methods
Optimize this
sub road-royale ( @χ ) {
@χ.rotor(4).map( {so @_.all + so @_.none}).sum;
}
It can optimize (or search if it can be formulated in terms of distances) any function. This function is often used because it's simple but it's also got some "neutral" changes: it increases fitness only when several things changes at the same time. Also includes junctions, and cool stuff.
Evolutionary algorithms evolve encoded solutions in populations
my @population = ( Bool.pick() xx $length ) xx $population-size;
Chromosomes are simply lists of random Bools, or bits. Other data structures are possible, but this works well for demos and many benchmark functions.
... through evaluation ...
my $evaluated = @population.unique.map( { @$_ => road-royale( @$_ ) } ).Mix;Mixes are immutable, so we're good here, but we need them to be unique or it will add the weights. Here's an interesting thing that I haven't seen in any other language; I'm using elements and its "weight" as score. This is going to be useful later on. Also, I'm using a cache so that I don't evaluate twice the same thing. It's not important at the beginning, but by the end of the simulation lots of values are going to be the same.
... to select the best
my @reproductive-pool = $evaluated.roll( $population-size );Since it's a Mix, just a roll takes care of
selecting with a probability thats related to fitness
... and interchange bits ...
my @pairs = @x Z @y;
my $xover1point = @x.keys.pick;
my $xover2point = ($xover1point^..@x.elems).pick;
my @crossed = gather for @pairs.kv -> $index, @value {
take ( ($xover1point <= $index <= $xover2point) ?? @value.reverse !!
@value );
}
return ([Z] @crossed).Slip;@population.append:
@reproductive-pool.pick( $population-size / 5 ).rotor(2)
.map( { xover( @$_[0], @$_[1] ) } );These are selected randomly from all members in
the population. Since the list is already randomized, we can just pick them by pairs. Also, 1/5 of the population is doing this. There's something called the rule of fifths, which I'm not going to bore you with, but it means that what we're doing is just right. ... which mutate ...
sub mutate ( @x is copy ) {
@x[ (^@x.elems).pick ] ?^= True;
@x;
}@population.append:
@reproductive-pool.pick( $population-size*3/5).map( {mutate(@$_)} );
It's a single bitflip of an element randomly
chosen, which uses xor so that we don't need to store the mutation point in a variable. We again use map to process the population, functional style.
Repeat until solution is found
my $best-so-far = $evaluated.values.max;
@best = $evaluated.grep( *.value == $best-so-far );
if any( $evaluated.values ) == $length/4 {
last;
} We use junctions, so that we don't really have to sort the population. We also filter the best to add it to the next generation. Or until you get tired, whatever happens
first.
We ♥ just the way you are
@population.append: @reproductive-pool.pick( $population-size / 5 );This is just random, so it might include or not the best.
First iteration
Evolving...
This keeps the best for the next generation.
Add Perl6 for instant data-paralellism
my @unique-population = @population.unique;
my @evaluations = @unique-population.race.map( { $^p => $evaluator( $^p ) } );
my MixHash $pop-bag;
for @evaluations -> $pair {
$pop-bag{$pair.key.item} = $pair.value;
}
return $pop-bag.Mix;
}We had to do some shuffling to avoid deadlocks,
but this is equivalent to a normal evaluation, only
faster. You can try and find parts of the code that can be
converted into concurrent this way. hyper, by default,
uses 4 threads, but it can be configured to use more.
Task paralellism: Communicating sequential processes
Stateless process writes to/reads from channels
Stateless ⇒ 1 to 1 mapping input/outputFor all functions.
We need a reactive/functional EA
Mutation, crossover, selection, no problem. But there are problems with...
Let's de-state-ify evolutionary algorithms
Using channels!
By converting them in a set
of pure functions.
Channelize
# Read from $channel-one and repeat...
$population = generation( population => $population,
fitness-of => %fitness-of,
evaluator => &royal-road,
population-size => $population-size);$to-mix.send( frequencies-best($population, 8) );
We are not sending the whole population, but only the per-gene frequency of every element in the population.
Threading threads
$to-mix.send( @pair.pick ); # To avoid getting it hanged up
my @new-population = crossover-frequencies( @pair[0], @pair[1] );
$channel-one.send( @new-population);
This mixes directly the frequencies of genes in the population
Does it scale?
I didn't have the fancy Log::Timeline to check it out. I'll have to look into that.
Concluding
Science
Open!
New algorithms!
