News for hackers. Stuff that matters.
Re:To all who Think Themselves a Programmer by DougWebb on Tuesday July 07, 2009 @11:20PM (#693159)
The 'win' that said they'd write a genetic algorithm got me interested, but I'm not looking for a job, so here's what I came up with:

  #!/usr/bin/perl

  use strict;
  use warnings;

  our $POP_SIZE      = 100;
  our @GOAL          = map { ord($_) - 32 } split //, 'hello world';
  our $MUTATION_RATE = 0.05;
  our $GENE_LENGTH   = scalar @GOAL;

  use constant GENE  => 0;
  use constant SCORE => 1;

  my @population = make_initial_population( $POP_SIZE, $GENE_LENGTH );
  my $generation = 1;

  while (1) {
      @population = rank(@population);

      print as_string( $population[0][GENE] ) . "\n";

      last if $population[0][SCORE] == 0;

      @population = mutate( sex(@population) );

      $generation++;
  }

  exit;

  ##################################################

  sub as_string {
      return join( '', map { chr( $_ + 32 ) } @{ $_[0] } );
  }

  ##################################################

  sub rank {
      my @population = @_;

      for ( my $i = 0 ; $i < @population ; $i++ ) {
          $population[$i][SCORE] = score( $population[$i][GENE] );
      }

      @population =
        sort { $a->[SCORE] <=> $b->[SCORE] || $a->[GENE] cmp $b->[GENE] }
        @population;

      return @population;
  }

  ##################################################

  sub score {
      my ($gene) = @_;

      my $value    = 0;
      my $num_diff = 0;

      for ( my $i = 0 ; $i < @$gene ; $i++ ) {
          my $diff = abs( $gene->[$i] - $GOAL[$i] );
          $value += $diff;
          $num_diff++ if $diff > 0;
      }

      return $value * $num_diff;
  }

  ##################################################

  sub sex {
      my @population = @_;

      my $end = $#population / 2;

      for ( my $i = 0 ; $i < $end ; $i++ ) {
          my @mother = @{ $population[$i][GENE] };
          my @father = @{ $population[ $i + 1 ][GENE] };

          my ( $sp1, $sp2 );
          while (1) {
              $sp1 = int( rand($GENE_LENGTH) );
              $sp2 = int( rand($GENE_LENGTH) );
              last
                if $sp1 < $sp2
                    && $sp1 > 0
                    && $sp2 < $GENE_LENGTH - 1;
          }

          $population[ $end + $i ][GENE] = [
              @mother[ 0 .. $sp1 - 1 ],
              @father[ $sp1 .. $sp2 - 1 ],
              @mother[ $sp2 .. $GENE_LENGTH - 1 ]
          ];
          $population[ $end + $i + 1 ][GENE] = [
              @father[ 0 .. $sp1 - 1 ],
              @mother[ $sp1 .. $sp2 - 1 ],
              @father[ $sp2 .. $GENE_LENGTH - 1 ]
          ];
      }

      return @population;
  }

  ##################################################

  sub mutate {
      my @population = @_;

      for ( my $i = 0 ; $i < $#population ; $i++ ) {
          if ( rand() > $MUTATION_RATE ) {
              my $gene           = $population[$i][GENE];
              my $chromosone_num = rand($GENE_LENGTH);
              my $chromosone     = $gene->[$chromosone_num];
              $chromosone += int( rand(5) + 0.5 ) - 2;    # -2, -1, 0, 1, 2
              $chromosone %= ( 128 - 32 );

              $population[$i][GENE][$chromosone_num] = $chromosone;
          }
      }

      return @population;
  }

  ##################################################

  sub make_initial_population {
      my ( $pop_size, $gene_length ) = @_;

      my @population;

      foreach ( 1 .. $pop_size ) {
          my @gene = map { int( rand( 128 - 32 ) ) } ( 1 .. $gene_length );
          push @population, [ \@gene, 0 ];
      }
  
      return @population;
  }

  ##################################################

There are no comments on this comment yet.