AI-Genetic-Pro
view release on metacpan or search on metacpan
NAME
AI::Genetic::Pro - Efficient genetic algorithms for professional
purpose with support for multiprocessing.
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');
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. AI::Genetic::Pro was inspired by
AI::Genetic, so it is in most cases compatible (there are some
changes). Additionally 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 AI::Genetic.
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 (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: native) instead of packing chromosomes into single
scalar. However you have to remember about expensive memory use in
that case.
Memory
Attention! You cannot preserve more chromosomes than exist in your
population.
-variable_length
This defines whether variable-length chromosomes are turned on
(default off) and a which types of mutation are allowed. See below.
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
level 1
Feature is active, but chromosomes can varies 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
level 2
Feature is active and chromosomes can varies on the left side and
on the right side; unwanted values/genes on the left side are
replaced with 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->as_array($chromosome)) can have 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 undef or space,
just use as_array_def_only and as_string_def_only instead of
as_array and as_string.
-parents
This defines how many parents should be used in a crossover.
-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:
RouletteBasic
Each individual/chromosome can be selected with probability
proportional to its fitness.
Roulette
First the best individuals/chromosomes are selected. From this
collection parents are selected with probability poportional to
their fitness.
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.
-selection => [ 'RouletteDistribution', 'uniform' ]
Standard uniform distribution. No additional parameters are
needed.
-selection => [ 'RouletteDistribution', 'normal', $av, $sd ]
Normal distribution, where $av is average (default: size of
population /2) and $$sd is standard deviation (default: size of
population).
-selection => [ 'RouletteDistribution', 'beta', $aa, $bb ]
Beta distribution. The density of the beta is:
X^($aa - 1) * (1 - X)^($bb - 1) / B($aa , $bb) for 0 < X < 1.
$aa and $bb are set by default to number of parents.
Argument restrictions: Both $aa and $bb must not be less than
1.0E-37.
-selection => [ 'RouletteDistribution', 'binomial' ]
Binomial distribution. No additional parameters are needed.
-selection => [ 'RouletteDistribution', 'chi_square', $df ]
Chi-square distribution with $df degrees of freedom. $df by
default is set to size of population.
-selection => [ 'RouletteDistribution', 'exponential', $av ]
Exponential distribution, where $av is average . $av by default
is set to size of population.
-selection => [ 'RouletteDistribution', 'poisson', $mu ]
Poisson distribution, where $mu is mean. $mu by default is set
to size of population.
Distribution
Chromosomes/individuals are selected with specified distribution.
See below.
-selection => [ 'Distribution', 'uniform' ]
Standard uniform distribution. No additional parameters are
needed.
-selection => [ 'Distribution', 'normal', $av, $sd ]
Normal distribution, where $av is average (default: size of
population /2) and $$sd is standard deviation (default: size of
population).
-selection => [ 'Distribution', 'beta', $aa, $bb ]
Beta distribution. The density of the beta is:
X^($aa - 1) * (1 - X)^($bb - 1) / B($aa , $bb) for 0 < X < 1.
$aa and $bb are set by default to number of parents.
Argument restrictions: Both $aa and $bb must not be less than
1.0E-37.
-selection => [ 'Distribution', 'binomial' ]
Binomial distribution. No additional parameters are needed.
-selection => [ 'Distribution', 'chi_square', $df ]
Chi-square distribution with $df degrees of freedom. $df by
default is set to size of population.
-selection => [ 'Distribution', 'exponential', $av ]
Exponential distribution, where $av is average . $av by default
is set to size of population.
-selection => [ 'Distribution', 'poisson', $mu ]
Poisson distribution, where $mu is mean. $mu by default is set
to size of population.
-strategy
This defines the astrategy of crossover operation. It expects an
array reference listed below:
-strategy => [ $type, @params ]
where type is one of:
PointsSimple
Simple crossover in one or many points. The best
chromosomes/individuals are selected for the new generation. For
example:
-strategy => [ 'PointsSimple', $n ]
where $n is the number of points for crossing.
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 $n is the number of points for crossing.
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 $n is number of points for crossing.
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 $n is the number of points for crossing.
Distribution
In distribution crossover parents are crossed in points selected
with the specified distribution. See below.
-strategy => [ 'Distribution', 'uniform' ]
Standard uniform distribution. No additional parameters are
needed.
-strategy => [ 'Distribution', 'normal', $av, $sd ]
Normal distribution, where $av is average (default: number of
parents/2) and $sd is standard deviation (default: number of
parents).
-strategy => [ 'Distribution', 'beta', $aa, $bb ]
Beta distribution. The density of the beta is:
X^($aa - 1) * (1 - X)^($bb - 1) / B($aa , $bb) for 0 < X < 1.
$aa and $bb are set by default to the number of parents.
Argument restrictions: Both $aa and $bb must not be less than
1.0E-37.
-strategy => [ 'Distribution', 'binomial' ]
Binomial distribution. No additional parameters are needed.
-strategy => [ 'Distribution', 'chi_square', $df ]
Chi-squared distribution with $df degrees of freedom. $df by
default is set to the number of parents.
-strategy => [ 'Distribution', 'exponential', $av ]
Exponential distribution, where $av is average . $av by default
is set to the number of parents.
-strategy => [ 'Distribution', 'poisson', $mu ]
Poisson distribution, where $mu is mean. $mu by default is set
to the number of parents.
PMX
PMX method defined by Goldberg and Lingle in 1985. Parameters:
none.
OX
OX method defined by Davis (?) in 1985. Parameters: none.
-cache
This defines whether a cache should be used. Allowed values are 1
or 0 (default: 0).
-history
This defines whether history should be collected. Allowed values
are 1 or 0 (default: 0).
-native
This defines whether native arrays should be used instead of
packing each chromosome into signle scalar. Turning this option can
give you speed up, but much more memory will be used. Allowed
values are 1 or 0 (default: 0).
-mce
This defines whether Many-Core Engine (MCE) should be used during
processing. This can give you significant speed up on many-core/CPU
systems, but it'll increase memory consumption. Allowed values are
1 or 0 (default: 0).
-workers
This option has any meaning only if MCE is turned on. This defines
how many process will be used during processing. Default will be
used one proces per core (most efficient).
-strict
This defines if the check for modifying chromosomes in a
user-defined fitness function is active. Directly modifying
chromosomes is not allowed and it is a highway to big trouble. This
mode should be used only for testing, because it is slow.
$ga->inject($chromosomes)
Inject new, user defined, chromosomes into the current population.
See example below:
# example for bitvector
my $chromosomes = [
[ 1, 1, 0, 1, 0, 1 ],
[ 0, 0, 0, 1, 0, 1 ],
[ 0, 1, 0, 1, 0, 0 ],
...
];
my @remove = qw(1 2 3 9 12);
for my $idx (sort { $b <=> $a } @remove){
splice @{$ga->chromosomes}, $idx, 1;
}
$ga->population($population)
Set/get size of the population. This defines the size of the
population, i.e. how many chromosomes to simultaneously exist at each
generation.
$ga->indType()
Get type of individuals/chromosomes. Currently supported types are:
bitvector
Chromosomes will be just bitvectors. See documentation of new
method.
listvector
Chromosomes will be lists of specified values. See documentation of
new method.
rangevector
Chromosomes will be lists of values from specified range. See
documentation of new method.
combination
Chromosomes will be unique lists of specified values. This is used
for example in the Traveling Salesman Problem. See the
documentation of the new method.
In example:
my $type = $ga->type();
$ga->type()
Alias for indType.
$ga->crossProb()
This method is used to query and set the crossover rate.
$ga->crossover()
Alias for crossProb.
$ga->mutProb()
This method is used to query and set the mutation rate.
$ga->mutation()
Alias for mutProb.
$ga->parents($parents)
Set/get number of parents in a crossover.
$ga->init($args)
This method initializes the population with random
individuals/chromosomes. It MUST be called before any call to
evolve(). It expects one argument, which depends on the type of
individuals/chromosomes:
bitvector
For bitvectors, the argument is simply the length of the bitvector.
$ga->init(10);
This initializes a population where each individual/chromosome has
10 genes.
listvector
For listvectors, 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 possible string
values that the corresponding gene can assume.
$ga->init([
[qw/red blue green/],
[qw/big medium small/],
[qw/very_fat fat fit thin very_thin/],
]);
This initializes a population where each individual/chromosome has
3 genes and each gene can assume one of the given values.
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.
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:
( run in 0.392 second using v1.01-cache-2.11-cpan-1dc43b0fbd2 )