| 1 | 1 | ▶ | use strict; #-*-cperl-*- |
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||
| 2 | 1 | ▶ | use warnings; |
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||
| 3 | |||
| 4 | 1 | ▶ | use lib qw(../../.. ../.. ); #Emacs does not allow me to save!!! |
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||
| 5 | |||
| 6 | =head1 NAME | ||
| 7 | |||
| 8 | Algorithm::Evolutionary::Run - Class for setting up an experiment with algorithms and population | ||
| 9 | |||
| 10 | =head1 SYNOPSIS | ||
| 11 | |||
| 12 | use Algorithm::Evolutionary::Run; | ||
| 13 | |||
| 14 | my $algorithm = new Algorithm::Evolutionary::Run 'conf.yaml'; | ||
| 15 | #or | ||
| 16 | my $conf = { | ||
| 17 | 'fitness' => { | ||
| 18 | 'class' => 'MMDP' | ||
| 19 | }, | ||
| 20 | 'crossover' => { | ||
| 21 | 'priority' => '3', | ||
| 22 | 'points' => '2' | ||
| 23 | }, | ||
| 24 | 'max_generations' => '1000', | ||
| 25 | 'mutation' => { | ||
| 26 | 'priority' => '2', | ||
| 27 | 'rate' => '0.1' | ||
| 28 | }, | ||
| 29 | 'length' => '120', | ||
| 30 | 'max_fitness' => '20', | ||
| 31 | 'pop_size' => '1024', | ||
| 32 | 'selection_rate' => '0.1' | ||
| 33 | }; | ||
| 34 | |||
| 35 | my $algorithm = new Algorithm::Evolutionary::Run $conf; | ||
| 36 | |||
| 37 | #Run it to the end | ||
| 38 | $algorithm->run(); | ||
| 39 | |||
| 40 | #Print results | ||
| 41 | $algorithm->results(); | ||
| 42 | |||
| 43 | #A single step | ||
| 44 | $algorithm->step(); | ||
| 45 | |||
| 46 | =head1 DESCRIPTION | ||
| 47 | |||
| 48 | This is a no-fuss class to have everything needed to run an algorithm | ||
| 49 | in a single place, although for the time being it's reduced to | ||
| 50 | fitness functions in the A::E::F namespace, and binary | ||
| 51 | strings. Mostly for demo purposes, but can be an example of class | ||
| 52 | for other stuff. | ||
| 53 | |||
| 54 | =cut | ||
| 55 | |||
| 56 | =head1 METHODS | ||
| 57 | |||
| 58 | =cut | ||
| 59 | |||
| 60 | package Algorithm::Evolutionary::Run; | ||
| 61 | |||
| 62 | 1 | ▶ | use Algorithm::Evolutionary qw(Individual::BitString Op::Easy Op::CanonicalGA |
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||
| 63 | Op::Bitflip Op::Crossover | ||
| 64 | 1 | Op::Gene_Boundary_Crossover); | |
| 65 | |||
| 66 | use Algorithm::Evolutionary::Utils qw(hamming); | ||
| 67 | |||
| 68 | our $VERSION = '3.2' ; | ||
| 69 | |||
| 70 | use Carp; | ||
| 71 | use YAML qw(LoadFile); | ||
| 72 | use Time::HiRes qw( gettimeofday tv_interval); | ||
| 73 | |||
| 74 | =head2 new( $algorithm_description ) | ||
| 75 | |||
| 76 | Creates the whole stuff needed to run an algorithm. Can be called from a hash with t | ||
| 77 | options, as per the example. All of them are compulsory. See also the C<examples> subdir for examples of the YAML conf file. | ||
| 78 | |||
| 79 | =cut | ||
| 80 | |||
| 81 | sub new { | ||
| 82 | my $class = shift; | ||
| 83 | |||
| 84 | my $param = shift; | ||
| 85 | my $fitness_object = shift; # Can be undef | ||
| 86 | my $self; | ||
| 87 | if ( ! ref $param ) { #scalar => read yaml file | ||
| 88 | $self = LoadFile( $param ) || carp "Can't load $param: is it a file?\n"; | ||
| 89 | } else { #It's a hashref | ||
| 90 | $self = $param; | ||
| 91 | } | ||
| 92 | |||
| 93 | #----------------------------------------------------------# | ||
| 94 | # Variation operators | ||
| 95 | my $m = new Algorithm::Evolutionary::Op::Bitflip( 1, $self->{'mutation'}->{'priority'} ); | ||
| 96 | my $c; | ||
| 97 | #Big hack here | ||
| 98 | if ( $self->{'crossover'} ) { | ||
| 99 | $c = new Algorithm::Evolutionary::Op::Crossover($self->{'crossover'}->{'points'}, $self->{'crossover'}->{'priority'} ); | ||
| 100 | } elsif ($self->{'gene_boundary_crossover'}) { | ||
| 101 | $c = new Algorithm::Evolutionary::Op::Gene_Boundary_Crossover($self->{'gene_boundary_crossover'}->{'points'}, | ||
| 102 | $self->{'gene_boundary_crossover'}->{'gene_size'} , | ||
| 103 | $self->{'gene_boundary_crossover'}->{'priority'} ); | ||
| 104 | } elsif ($self->{'quad_xover'} ) { | ||
| 105 | $c = new Algorithm::Evolutionary::Op::QuadXOver($self->{'crossover'}->{'points'}, $self->{'crossover'}->{'priority'} ); | ||
| 106 | } | ||
| 107 | |||
| 108 | # Fitness function | ||
| 109 | if ( !$fitness_object ) { | ||
| 110 | my $fitness_class = "Algorithm::Evolutionary::Fitness::".$self->{'fitness'}->{'class'}; | ||
| 111 | eval "require $fitness_class" || die "Can't load $fitness_class: $@\n"; | ||
| 112 | my @params = $self->{'fitness'}->{'params'}? @{$self->{'fitness'}->{'params'}} : (); | ||
| 113 | $fitness_object = eval $fitness_class."->new( \@params )" || die "Can't instantiate $fitness_class: $@\n"; | ||
| 114 | } | ||
| 115 | $self->{'_fitness'} = $fitness_object; | ||
| 116 | |||
| 117 | #----------------------------------------------------------# | ||
| 118 | #Usamos estos operadores para definir una generación del algoritmo. Lo cual | ||
| 119 | # no es realmente necesario ya que este algoritmo define ambos operadores por | ||
| 120 | # defecto. Los parámetros son la función de fitness, la tasa de selección y los | ||
| 121 | # operadores de variación. | ||
| 122 | my $algorithm_class = "Algorithm::Evolutionary::Op::".($self->{'algorithm'}?$self->{'algorithm'}:'Easy'); | ||
| 123 | my $generation = eval $algorithm_class."->new( \$fitness_object , \$self->{'selection_rate'} , [\$m, \$c] )" | ||
| 124 | || die "Can't instantiate $algorithm_class: $@\n";; | ||
| 125 | |||
| 126 | #Time | ||
| 127 | my $inicioTiempo = [gettimeofday()]; | ||
| 128 | |||
| 129 | #----------------------------------------------------------# | ||
| 130 | bless $self, $class; | ||
| 131 | $self->reset_population; | ||
| 132 | for ( @{$self->{'_population'}} ) { | ||
| 133 | if ( !defined $_->Fitness() ) { | ||
| 134 | $_->evaluate( $fitness_object ); | ||
| 135 | } | ||
| 136 | } | ||
| 137 | |||
| 138 | $self->{'_generation'} = $generation; | ||
| 139 | $self->{'_start_time'} = $inicioTiempo; | ||
| 140 | return $self; | ||
| 141 | } | ||
| 142 | |||
| 143 | =head2 population_size( $new_size ) | ||
| 144 | |||
| 145 | Resets the population size to the C<$new_size>. It does not do | ||
| 146 | anything to the actual population, just resests the number. You should | ||
| 147 | do a C<reset_population> afterwards. | ||
| 148 | |||
| 149 | =cut | ||
| 150 | |||
| 151 | sub population_size { | ||
| 152 | my $self = shift; | ||
| 153 | my $new_size = shift || croak "Too small!"; | ||
| 154 | $self->{'pop_size'} = $new_size; | ||
| 155 | } | ||
| 156 | |||
| 157 | |||
| 158 | =head2 reset_population() | ||
| 159 | |||
| 160 | Resets population, creating a new one; resets fitness counter to 0 | ||
| 161 | |||
| 162 | =cut | ||
| 163 | |||
| 164 | sub reset_population { | ||
| 165 | my $self = shift; | ||
| 166 | #Initial population | ||
| 167 | my @pop; | ||
| 168 | |||
| 169 | #Creamos $popSize individuos | ||
| 170 | my $bits = $self->{'length'}; | ||
| 171 | for ( 1..$self->{'pop_size'} ) { | ||
| 172 | my $indi = Algorithm::Evolutionary::Individual::BitString->new( $bits ); | ||
| 173 | $indi->evaluate( $self->{'_fitness'} ); | ||
| 174 | push( @pop, $indi ); | ||
| 175 | } | ||
| 176 | $self->{'_population'} = \@pop; | ||
| 177 | $self->{'_fitness'}->reset_evaluations; | ||
| 178 | } | ||
| 179 | |||
| 180 | =head2 step() | ||
| 181 | |||
| 182 | Runs a single step of the algorithm, that is, a single generation | ||
| 183 | |||
| 184 | =cut | ||
| 185 | |||
| 186 | sub step { | ||
| 187 | my $self = shift; | ||
| 188 | $self->{'_generation'}->apply( $self->{'_population'} ); | ||
| 189 | $self->{'_counter'}++; | ||
| 190 | } | ||
| 191 | |||
| 192 | =head2 run() | ||
| 193 | |||
| 194 | Applies the different operators in the order that they appear; returns the population | ||
| 195 | as a ref-to-array. | ||
| 196 | |||
| 197 | =cut | ||
| 198 | |||
| 199 | sub run { | ||
| 200 | my $self = shift; | ||
| 201 | $self->{'_counter'} = 0; | ||
| 202 | do { | ||
| 203 | $self->step(); | ||
| 204 | |||
| 205 | } while( ($self->{'_counter'} < $self->{'max_generations'}) | ||
| 206 | && ($self->{'_population'}->[0]->Fitness() < $self->{'max_fitness'})); | ||
| 207 | |||
| 208 | } | ||
| 209 | |||
| 210 | =head2 random_member() | ||
| 211 | |||
| 212 | Returns a random guy from the population | ||
| 213 | |||
| 214 | =cut | ||
| 215 | |||
| 216 | sub random_member { | ||
| 217 | my $self = shift; | ||
| 218 | return $self->{'_population'}->[rand( @{$self->{'_population'}} )]; | ||
| 219 | } | ||
| 220 | |||
| 221 | =head2 results() | ||
| 222 | |||
| 223 | Returns results in a hash that contains the best, total time so far | ||
| 224 | and the number of evaluations. | ||
| 225 | |||
| 226 | =cut | ||
| 227 | |||
| 228 | sub results { | ||
| 229 | my $self = shift; | ||
| 230 | my $population_size = scalar @{$self->{'_population'}}; | ||
| 231 | my $last_good_pos = $population_size*(1-$self->{'selection_rate'}); | ||
| 232 | my $results = { best => $self->{'_population'}->[0], | ||
| 233 | median => $self->{'_population'}->[ $population_size / 2], | ||
| 234 | last_good => $self->{'_population'}->[ $last_good_pos ], | ||
| 235 | time => tv_interval( $self->{'_start_time'} ), | ||
| 236 | evaluations => $self->{'_fitness'}->evaluations() }; | ||
| 237 | return $results; | ||
| 238 | |||
| 239 | } | ||
| 240 | |||
| 241 | =head2 evaluated_population() | ||
| 242 | |||
| 243 | Returns the portion of population that has been evaluated (all but the new ones) | ||
| 244 | |||
| 245 | =cut | ||
| 246 | |||
| 247 | sub evaluated_population { | ||
| 248 | my $self = shift; | ||
| 249 | my $population_size = scalar @{$self->{'_population'}}; | ||
| 250 | my $last_good_pos = $population_size*(1-$self->{'selection_rate'}) - 1; | ||
| 251 | return @{$self->{'_population'}}[0..$last_good_pos]; | ||
| 252 | } | ||
| 253 | |||
| 254 | |||
| 255 | =head2 compute_average_distance( $individual ) | ||
| 256 | |||
| 257 | Computes the average hamming distance to the population | ||
| 258 | |||
| 259 | =cut | ||
| 260 | |||
| 261 | sub compute_average_distance { | ||
| 262 | my $self = shift; | ||
| 263 | my $other = shift || croak "No other\n"; | ||
| 264 | my $distance; | ||
| 265 | for my $p ( @{$self->{'_population'}} ) { | ||
| 266 | $distance += hamming( $p->{'_str'}, $other->{'_str'} ); | ||
| 267 | } | ||
| 268 | $distance /= @{$self->{'_population'}}; | ||
| 269 | } | ||
| 270 | |||
| 271 | =head2 compute_min_distance( $individual ) | ||
| 272 | |||
| 273 | Computes the average hamming distance to the population | ||
| 274 | |||
| 275 | =cut | ||
| 276 | |||
| 277 | sub compute_min_distance { | ||
| 278 | my $self = shift; | ||
| 279 | my $other = shift || croak "No other\n"; | ||
| 280 | my $min_distance = length( $self->{'_population'}->[0]->{'_str'} ); | ||
| 281 | for my $p ( @{$self->{'_population'}} ) { | ||
| 282 | my $this_distance = hamming( $p->{'_str'}, $other->{'_str'} ); | ||
| 283 | $min_distance = ( $this_distance < $min_distance )?$this_distance:$min_distance; | ||
| 284 | } | ||
| 285 | return $min_distance; | ||
| 286 | |||
| 287 | } | ||
| 288 | |||
| 289 | =head1 Copyright | ||
| 290 | |||
| 291 | This file is released under the GPL. See the LICENSE file included in this distribution, | ||
| 292 | or go to http://www.fsf.org/licenses/gpl.txt | ||
| 293 | |||
| 294 | =cut | ||
| 295 | |||
| 296 | "Still there?"; | ||