4 ms·
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
by DougWebb 17y ago
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;
}
##################################################