AI-Genetic-Pro
view release on metacpan or search on metacpan
lib/AI/Genetic/Pro.pm view on Meta::CPAN
# $add_to_list;
# } @keys;
}else{
my %tmp;
@keys = grep {
my $key = md5_hex( join( q[:], @{ $chromosomes->[ $_ ] } ) );
$tmp{ $key } && 0 or $tmp{ $key } = 1;
} @keys;
}
}
$n = scalar @keys if $n > scalar @keys;
return [ reverse @{$self->chromosomes}[ splice @keys, $#keys - $n + 1, $n ] ];
}
#=======================================================================
sub getFittest { return wantarray ? @{ shift->getFittest_as_arrayref(@_) } : shift @{ shift->getFittest_as_arrayref(@_) }; }
#=======================================================================
sub getAvgFitness {
my ($self) = @_;
my @minmax = minmax values %{$self->_fitness};
my $mean = sum(values %{$self->_fitness}) / scalar values %{$self->_fitness};
return $minmax[1], int($mean), $minmax[0];
}
#=======================================================================
1;
__END__
=head1 NAME
AI::Genetic::Pro - Efficient genetic algorithms for professional purpose with support for multiprocessing.
=head1 SYNOPSIS
use AI::Genetic::Pro;
sub fitness {
my ($ga, $chromosome) = @_;
return oct('0b' . $ga->as_string($chromosome));
}
sub terminate {
my ($ga) = @_;
my $result = oct('0b' . $ga->as_string($ga->getFittest));
return $result == 4294967295 ? 1 : 0;
}
my $ga = AI::Genetic::Pro->new(
-fitness => \&fitness, # fitness function
-terminate => \&terminate, # terminate function
-type => 'bitvector', # type of chromosomes
-population => 1000, # population
-crossover => 0.9, # probab. of crossover
-mutation => 0.01, # probab. of mutation
-parents => 2, # number of parents
-selection => [ 'Roulette' ], # selection strategy
-strategy => [ 'Points', 2 ], # crossover strategy
-cache => 0, # cache results
-history => 1, # remember best results
-preserve => 3, # remember the bests
-variable_length => 1, # turn variable length ON
-mce => 1, # optional MCE support
-workers => 3, # number of workers (MCE)
);
# init population of 32-bit vectors
$ga->init(32);
# evolve 10 generations
$ga->evolve(10);
# best score
print "SCORE: ", $ga->as_value($ga->getFittest), ".\n";
# save evolution path as a chart
$ga->chart(-filename => 'evolution.png');
# save state of GA
$ga->save('genetic.sga');
# load state of GA
$ga->load('genetic.sga');
=head1 DESCRIPTION
This module provides efficient implementation of a genetic algorithm for
professional purpose with support for multiprocessing. It was designed to operate as fast as possible
even on very large populations and big individuals/chromosomes. C<AI::Genetic::Pro>
was inspired by C<AI::Genetic>, so it is in most cases compatible
(there are some changes). Additionally C<AI::Genetic::Pro> isn't a pure Perl solution, so it
doesn't have limitations of its ancestor (such as slow-down in the
case of big populations ( >10000 ) or vectors with more than 33 fields).
If You are looking for a pure Perl solution, consider L<AI::Genetic>.
=over 4
=item Speed
To increase speed XS code is used, however with portability in
mind. This distribution was tested on Windows and Linux platforms
(and should work on any other).
Multicore support is available through Many-Core Engine (C<MCE>).
You can gain the most speed up for big populations or time/CPU consuming
fitness functions, however for small populations and/or simple fitness
function better choice will be single-process version.
You can get even more speed up if you turn on use of native arrays
(parameter: C<native>) instead of packing chromosomes into single scalar.
However you have to remember about expensive memory use in that case.
=item Memory
This module was designed to use as little memory as possible. A population
of size 10000 consisting of 92-bit vectors uses only ~24MB (C<AI::Genetic>
would use about 78MB). However - if you use MCE - there will be bigger
memory consumption. This is consequence of necessity of synchronization
between many processes.
=item Advanced options
To provide more flexibility C<AI::Genetic::Pro> supports many
statistical distributions, such as C<uniform>, C<natural>, C<chi_square>
and others. This feature can be used in selection and/or crossover. See
the documentation below.
=back
=head1 METHODS
=over 4
=item I<$ga>-E<gt>B<new>( %options )
Constructor. It accepts options in hash-value style. See options and
an example below.
=over 8
=item -fitness
This defines a I<fitness> function. It expects a reference to a subroutine.
=item -terminate
This defines a I<terminate> function. It expects a reference to a subroutine.
=item -type
This defines the type of chromosomes. Currently, C<AI::Genetic::Pro> supports four types:
=over 12
=item bitvector
Individuals/chromosomes of this type have genes that are bits. Each gene can be in one of two possible states, on or off.
=item listvector
Each gene of a "listvector" individual/chromosome can assume one string value from a specified list of possible string values.
=item rangevector
Each gene of a "rangevector" individual/chromosome can assume one integer
value from a range of possible integer values. Note that only integers
are supported. The user can always transform any desired fractional values
by multiplying and dividing by an appropriate power of 10.
=item combination
Each gene of a "combination" individual/chromosome can assume one string value from a specified list of possible string values. B<All genes are unique.>
=back
=item -population
This defines the size of the population, i.e. how many chromosomes
simultaneously exist at each generation.
=item -crossover
This defines the crossover rate. The fairest results are achieved with
crossover rate ~0.95.
=item -mutation
This defines the mutation rate. The fairest results are achieved with mutation
rate ~0.01.
=item -preserve
This defines injection of the bests chromosomes into a next generation. It causes a little slow down, however (very often) much better results are achieved. You can specify, how many chromosomes will be preserved, i.e.
-preserve => 1, # only one chromosome will be preserved
# or
-preserve => 9, # 9 chromosomes will be preserved
# and so on...
Attention! You cannot preserve more chromosomes than exist in your population.
=item -variable_length
This defines whether variable-length chromosomes are turned on (default off)
and a which types of mutation are allowed. See below.
=over 8
=item level 0
Feature is inactive (default). Example:
-variable_length => 0
# chromosomes (i.e. bitvectors)
0 1 0 0 1 1 0 1 1 1 0 1 0 1
0 0 1 1 0 1 1 1 1 0 0 1 1 0
0 1 1 1 0 1 0 0 1 1 0 1 1 1
0 1 0 0 1 1 0 1 1 1 1 0 1 0
# ...and so on
=item level 1
Feature is active, but chromosomes can varies B<only on the right side>, Example:
-variable_length => 1
# chromosomes (i.e. bitvectors)
0 1 0 0 1 1 0 1 1 1
0 0 1 1 0 1 1 1 1
0 1 1 1 0 1 0 0 1 1 0 1 1 1
0 1 0 0 1 1 0 1 1 1
# ...and so on
=item level 2
Feature is active and chromosomes can varies B<on the left side and on
the right side>; unwanted values/genes on the left side are replaced with C<undef>, ie.
-variable_length => 2
# chromosomes (i.e. bitvectors)
x x x 0 1 1 0 1 1 1
x x x x 0 1 1 1 1
x 1 1 1 0 1 0 0 1 1 0 1 1 1
0 1 0 0 1 1 0 1 1 1
# where 'x' means 'undef'
# ...and so on
In this situation returned chromosomes in an array context ($ga-E<gt>as_array($chromosome))
can have B<undef> values on the left side (only). In a scalar context each
undefined value is replaced with a single space. If You don't want to see
any C<undef> or space, just use C<as_array_def_only> and C<as_string_def_only>
instead of C<as_array> and C<as_string>.
=back
=item -parents
This defines how many parents should be used in a crossover.
=item -selection
This defines how individuals/chromosomes are selected to crossover. It expects an array reference listed below:
-selection => [ $type, @params ]
where type is one of:
=over 8
=item B<RouletteBasic>
Each individual/chromosome can be selected with probability proportional to its fitness.
=item B<Roulette>
First the best individuals/chromosomes are selected. From this collection
parents are selected with probability poportional to their fitness.
=item B<RouletteDistribution>
Each individual/chromosome has a portion of roulette wheel proportional to its
fitness. Selection is done with the specified distribution. Supported
distributions and parameters are listed below.
=over 12
=item C<-selection =E<gt> [ 'RouletteDistribution', 'uniform' ]>
Standard uniform distribution. No additional parameters are needed.
=item C<-selection =E<gt> [ 'RouletteDistribution', 'normal', $av, $sd ]>
Normal distribution, where C<$av> is average (default: size of population /2) and $C<$sd> is standard deviation (default: size of population).
=item C<-selection =E<gt> [ 'RouletteDistribution', 'beta', $aa, $bb ]>
I<Beta> distribution. The density of the beta is:
X^($aa - 1) * (1 - X)^($bb - 1) / B($aa , $bb) for 0 < X < 1.
C<$aa> and C<$bb> are set by default to number of parents.
B<Argument restrictions:> Both $aa and $bb must not be less than 1.0E-37.
=item C<-selection =E<gt> [ 'RouletteDistribution', 'binomial' ]>
Binomial distribution. No additional parameters are needed.
=item C<-selection =E<gt> [ 'RouletteDistribution', 'chi_square', $df ]>
Chi-square distribution with C<$df> degrees of freedom. C<$df> by default is set to size of population.
=item C<-selection =E<gt> [ 'RouletteDistribution', 'exponential', $av ]>
Exponential distribution, where C<$av> is average . C<$av> by default is set to size of population.
=item C<-selection =E<gt> [ 'RouletteDistribution', 'poisson', $mu ]>
Poisson distribution, where C<$mu> is mean. C<$mu> by default is set to size of population.
=back
=item B<Distribution>
Chromosomes/individuals are selected with specified distribution. See below.
=over 12
=item C<-selection =E<gt> [ 'Distribution', 'uniform' ]>
Standard uniform distribution. No additional parameters are needed.
=item C<-selection =E<gt> [ 'Distribution', 'normal', $av, $sd ]>
Normal distribution, where C<$av> is average (default: size of population /2) and $C<$sd> is standard deviation (default: size of population).
=item C<-selection =E<gt> [ 'Distribution', 'beta', $aa, $bb ]>
I<Beta> distribution. The density of the beta is:
X^($aa - 1) * (1 - X)^($bb - 1) / B($aa , $bb) for 0 < X < 1.
C<$aa> and C<$bb> are set by default to number of parents.
B<Argument restrictions:> Both $aa and $bb must not be less than 1.0E-37.
=item C<-selection =E<gt> [ 'Distribution', 'binomial' ]>
Binomial distribution. No additional parameters are needed.
=item C<-selection =E<gt> [ 'Distribution', 'chi_square', $df ]>
Chi-square distribution with C<$df> degrees of freedom. C<$df> by default is set to size of population.
=item C<-selection =E<gt> [ 'Distribution', 'exponential', $av ]>
Exponential distribution, where C<$av> is average . C<$av> by default is set to size of population.
=item C<-selection =E<gt> [ 'Distribution', 'poisson', $mu ]>
Poisson distribution, where C<$mu> is mean. C<$mu> by default is set to size of population.
=back
=back
=item -strategy
This defines the astrategy of crossover operation. It expects an array
reference listed below:
-strategy => [ $type, @params ]
where type is one of:
=over 4
=item PointsSimple
Simple crossover in one or many points. The best chromosomes/individuals are
selected for the new generation. For example:
-strategy => [ 'PointsSimple', $n ]
where C<$n> is the number of points for crossing.
=item PointsBasic
Crossover in one or many points. In basic crossover selected parents are
crossed and one (randomly-chosen) child is moved to the new generation. For
example:
-strategy => [ 'PointsBasic', $n ]
where C<$n> is the number of points for crossing.
=item Points
Crossover in one or many points. In normal crossover selected parents are crossed and the best child is moved to the new generation. For example:
-strategy => [ 'Points', $n ]
where C<$n> is number of points for crossing.
=item PointsAdvenced
Crossover in one or many points. After crossover the best
chromosomes/individuals from all parents and chidren are selected for the new
generation. For example:
-strategy => [ 'PointsAdvanced', $n ]
where C<$n> is the number of points for crossing.
=item Distribution
In I<distribution> crossover parents are crossed in points selected with the
specified distribution. See below.
=over 8
=item C<-strategy =E<gt> [ 'Distribution', 'uniform' ]>
Standard uniform distribution. No additional parameters are needed.
=item C<-strategy =E<gt> [ 'Distribution', 'normal', $av, $sd ]>
Normal distribution, where C<$av> is average (default: number of parents/2) and C<$sd> is standard deviation (default: number of parents).
=item C<-strategy =E<gt> [ 'Distribution', 'beta', $aa, $bb ]>
I<Beta> distribution. The density of the beta is:
X^($aa - 1) * (1 - X)^($bb - 1) / B($aa , $bb) for 0 < X < 1.
C<$aa> and C<$bb> are set by default to the number of parents.
B<Argument restrictions:> Both $aa and $bb must not be less than 1.0E-37.
=item C<-strategy =E<gt> [ 'Distribution', 'binomial' ]>
Binomial distribution. No additional parameters are needed.
=item C<-strategy =E<gt> [ 'Distribution', 'chi_square', $df ]>
Chi-squared distribution with C<$df> degrees of freedom. C<$df> by default is set to the number of parents.
=item C<-strategy =E<gt> [ 'Distribution', 'exponential', $av ]>
Exponential distribution, where C<$av> is average . C<$av> by default is set to the number of parents.
=item C<-strategy =E<gt> [ 'Distribution', 'poisson', $mu ]>
Poisson distribution, where C<$mu> is mean. C<$mu> by default is set to the number of parents.
=back
=item PMX
PMX method defined by Goldberg and Lingle in 1985. Parameters: I<none>.
=item OX
OX method defined by Davis (?) in 1985. Parameters: I<none>.
=back
lib/AI/Genetic/Pro.pm view on Meta::CPAN
This initializes a population where each individual/chromosome has 3 genes and each gene can assume one of the given values.
=item B<rangevector>
For rangevectors, the argument is an anonymous list of lists. The number of sub-lists is equal to the number of genes of each individual/chromosome. Each sub-list defines the minimum and maximum integer values that the corresponding gene can assume.
$ga->init([
[1, 5],
[0, 20],
[4, 9],
]);
This initializes a population where each individual/chromosome has 3 genes and each gene can assume an integer within the corresponding range.
=item B<combination>
For combination, the argument is an anonymous list of possible values of gene.
$ga->init( [ 'a', 'b', 'c' ] );
This initializes a population where each chromosome has 3 genes and each gene
is a unique combination of 'a', 'b' and 'c'. For example genes looks something
like that:
[ 'a', 'b', 'c' ] # gene 1
[ 'c', 'a', 'b' ] # gene 2
[ 'b', 'c', 'a' ] # gene 3
# ...and so on...
=back
=item I<$ga>-E<gt>B<evolve>($n)
This method causes the GA to evolve the population for the specified number of
generations. If its argument is 0 or C<undef> GA will evolve the population to
infinity unless a C<terminate> function is specified.
=item I<$ga>-E<gt>B<getHistory>()
Get history of the evolution. It is in a format listed below:
[
# gen0 gen1 gen2 ... # generations
[ max0, max1, max2, ... ], # max values
[ mean, mean1, mean2, ... ], # mean values
[ min0, min1, min2, ... ], # min values
]
=item I<$ga>-E<gt>B<getAvgFitness>()
Get I<max>, I<mean> and I<min> score of the current generation. In example:
my ($max, $mean, $min) = $ga->getAvgFitness();
=item I<$ga>-E<gt>B<getFittest>($n, $unique)
This function returns a list of the fittest chromosomes from the current
population. You can specify how many chromosomes should be returned and if
the returned chromosomes should be unique. See example below.
# only one - the best
my ($best) = $ga->getFittest;
# or 5 bests chromosomes, NOT unique
my @bests = $ga->getFittest(5);
# or 7 bests and UNIQUE chromosomes
my @bests = $ga->getFittest(7, 1);
If you want to get a large number of chromosomes, try to use the
C<getFittest_as_arrayref> function instead (for efficiency).
=item I<$ga>-E<gt>B<getFittest_as_arrayref>($n, $unique)
This function is very similar to C<getFittest>, but it returns a reference
to an array instead of a list.
=item I<$ga>-E<gt>B<generation>()
Get the number of the current generation.
=item I<$ga>-E<gt>B<people>()
Returns an anonymous list of individuals/chromosomes of the current population.
B<IMPORTANT:> the actual array reference used by the C<AI::Genetic::Pro>
object is returned, so any changes to it will be reflected in I<$ga>.
=item I<$ga>-E<gt>B<chromosomes>()
Alias for C<people>.
=item I<$ga>-E<gt>B<chart>(%options)
Generate a chart describing changes of min, mean, and max scores in your
population. To satisfy your needs, you can pass the following options:
=over 4
=item -filename
File to save a chart in (B<obligatory>).
=item -title
Title of a chart (default: I<Evolution>).
=item -x_label
X label (default: I<Generations>).
=item -y_label
Y label (default: I<Value>).
=item -format
Format of values, like C<sprintf> (default: I<'%.2f'>).
=item -legend1
Description of min line (default: I<Min value>).
=item -legend2
Description of min line (default: I<Mean value>).
=item -legend3
( run in 1.642 second using v1.01-cache-2.11-cpan-39bf76dae61 )