cool concept and the implementation looks well done.
i need to study it more in order to make any detailed
or deep comments.

extremely minor nitpiks and some questions.

1)  someone already covered the map in void context.
2)  my $min = ${$fitnesses}[0];
    for ($i = 0; $i < $size; ++$i) {
    #  set $i = 1 since you used 0th index to load $min.
    #  same thing for the $max value in a diff routine later.
      $min = ${$fitnesses}[$i] if (${$fitnesses}[$i] < $min);
    }

3)  sub random_gene {
      my $self = shift;
      return ${$self->{GENES}}[rand(@{$self->{GENES}})];

why do you allow perl to truncate the above, which provides 
a fair distribution for the 0th index, but you handle
explicitly below, which never includes the 0th index?  there
may be a good reason, but i couldn't figure out what it was.

    if (rand(1.0) < 0.005) {
      my $mutate = 1 + int(rand(@{$self->{NEW_GENES}} - 1));

4)  if (rand(1.0) > 0.5) {
        my $cut = 1 + int(rand(@genes1 - 1));
# i understand it here - since replacing the entire gene
from beginning might not make sense

5)  i factored out the following from the code so I could stick
everything on the top and play:
my $Genes = ['$x+=1 ;', '$x=$y ;',  '$y=$x ;', '$x|=$y ;', '$x+=$y ;',
+ ' ;'];
my $IndivGeneLen = 32;
my $PopSize = 1999;
my $Target = 10512;
my $NumGenerations = 100;

next thought - this can be generalized into a module.
very cool, thanks!
[download]