view release on metacpan or  search on metacpan

lib/Algorithm/Evolutionary/Hash_Wheel.pm  view on Meta::CPAN

use strict;
use warnings;

=head1 NAME

Algorithm::Evolutionary::Hash_Wheel - Random selector of things depending on probabilities

=head1 SYNOPSIS

    my $wheel = new Algorithm::Evolutionary::Hash_Wheel( \%probs );
    print $wheel->spin(); #Returns an element according to probabilities;

=head1 DESCRIPTION

Creates a "roulette wheel" for spinning and selecting stuff. It will
be used in several places; mainly in the
L<Algorithm::Evolutionary::Op::CanonicalGA>. It's similar to
L<Algorithm::Evolutionary::Wheel>, but with a hash instead of an
array. Probably should unify both..

=head1 METHODS

=cut

package Algorithm::Evolutionary::Hash_Wheel;
use Carp;

our ($VERSION) = ( '$Revision: 1.2 $ ' =~ / (\d+\.\d+)/ ) ;

=head2 new( $probabilities_hashref )

Creates a new roulette wheel. Takes a hashref, which uses as keys the
objects to be returned by the roulette wheel, and as values the ones
that are going to be used

=cut

sub new {
  my $class = shift;
  my $probs_hashref = shift || die "No probabilities hash";

  my %probs = %$probs_hashref;
  my $self = { _accProbs => [] };
  
  my $acc = 0;
  for ( sort keys %probs ) { $acc += $probs{$_};}
  for ( sort keys %probs ) { $probs{$_} /= $acc;} #Normalizes array

  #Now creates the accumulated array, putting the accumulated
  #probability in the first element arrayref element, and the object
  #in the second
  my $aux = 0;  
  for ( sort keys %probs ) {
	push @{$self->{_accProbs}}, [$probs{$_} + $aux,$_ ];
	$aux += $probs{$_};
  }

  bless $self, $class;
  return $self;
}

=head2 spin()

Returns a single individual whose probability is related to its fitness
TODO: should return many, probably

=cut

sub spin {
  my $self = shift;
  my $i = 0;
  my $rand = rand();
  while ( $self->{_accProbs}[$i]->[0] < $rand ) { $i++ };
  return $self->{_accProbs}[$i]->[1];