|
AI::Genetic - A pure Perl genetic algorithm implementation. |
AI::Genetic - A pure Perl genetic algorithm implementation.
use AI::Genetic;
my $ga = new AI::Genetic(
-fitness => sub { rand },
-genes => [qw/geneA geneB geneC/],
-population => 500,
-crossover => 0.9,
-mutation => 0.01,
);
This module implements a Genetic Algorithm (GA) in pure Perl. Other Perl modules that achieve the same thing (perhaps better, perhaps worse) do exist. Please check CPAN. I mainly wrote this module to satisfy my own needs, and to learn something about GAs along the way.
I will not go into the details of GAs here, but here are the bare basics. Plenty of information can be found on the web.
In a GA, a population of individuals compete for survival. Each individual is designated by a set of genes that defines its behaviour. Individuals that perform better (as defined by the fitness function) have a higher chance of mating with other individuals. When two individuals mate, they swap some of their genes, resulting in an individual that has properties from both of its ``parents''. Every now and then, a mutation occurs where some gene randomly changes value, resulting in a different individual.
A GA implementation runs for a discrete number of time steps call generations. During each generation, the following happens:
Here are the public methods.
genes() and score() methods to get the genes and the
scores of the individuals. Please
check the AI::Genetic::Individual manpage for details.
There are two ways to specify the gene pool to the GA. For lack of imagination, I call them LIST and LOL. They do not mix. So please use one or the other.
-genes => [qw/geneA geneB geneC geneD .../]
The catch here is that genes are binary, so they can assume either an ON or an OFF value. Genes that are off will not be present in an individuals genome.
You can specify an initial population of LIST individuals using the -init option as follows:
-init => [
[qw/geneA geneC geneD/],
[qw/geneB geneC/],
]
This defines two individuals: the first has genes geneA, geneC and geneD; and the second has two genes: geneB and geneC.
-genes => [
[qw/geneA 0 1 2 3 4],
[qw/geneB a b c d e],
....
]
In this example, geneA is allowed to have any of the values 0, 1, 2, 3 or 4. Similarly, geneB can have only one of the values to its right. In this case, all genes will be present in each individual, but the gene will have a value chosen from its respective list.
Pleas note: for now, you have to specify all the values that a gene can take. Perhaps in the future I will support specifying a range of values instead, but not now :)
You can specify an initial population of LOL individuals using the -init option as follows:
-init => [
{
geneA =E<gt> 1,
geneB =E<gt> 'b',
geneC =E<gt> 5,
}
]
This defines one individual with the genes having the specified values. Note here that you have to specify values for ALL genes. This is necessary and failing to do so will create warnings/errors at run-time.
I am aware that many crossover techniques exist. I have chosen only one that suited my needs. Basically, fit individuals are paired up randomly. Whether mating actually occurs depends on the crossover rate defined by the -crossover option.
For LIST individuals (see GENES), the genes of both parents are inspected. Genes shared by both parents have a higher chance of being passed on. Genes present in only one parent have a 50% chance of making it to the child. Genes in neither parent can not pass on to the child. Based on this, genes are randomly selected for the child. Note that under this scheme, the number of genes in both parents need NOT be equal to each other, or to the number of genes in the child. Note also that this might result in a child with no genes, in which case it is assumed that the parent individuals did not mate at all.
For LOL individuals (see GENES), both parents have all the genes, but with potentially different values. Here, the child individual will have all the genes, and the value of each gene is randomly chosen among the two values of the parents'.
If you require a different crossover technique, please let me know.
Again, I'm aware of the many mutation techniques out there. Again, I have chosen something simple that suits my needs.
For LIST individuals (see GENES), each individual has a list of the ON genes only. Iterating through this list, the mutation probability determines whether this gene is to be mutated or not. If so, then another gene is chosen from the original list of all possible genes, and replaces the current gene. Note that duplicate genes are not allowed. If a gene is to be replaced by another one that is already in the genome, then no mutation occurs.
For LOL individuals (see GENES), all genes are present in each individual. Iterating through all the genes, the mutation probability determines whether the gene is to mutate or not. If so, then a new value is chosen from the original list of possible values.
Again, if you require a different mutation technique, please let me know.
AI::Genetic expects the fitness function to be an anonymous subroutine, defined by the user. It is used during selection to calculate a fitness value for each individual. The higher the value, the more fit the individual. The arguments to this subroutine depend on the type of genome used. The result is expected to be a scalar number, that defines the fitness of the individual.
For LIST individuals (see GENES), the input arguments to the fitness function will be a list of the ON genes of the individual.
For LOL individuals (see GENES), the input argument to the fitness function will be an anonymous hash. The keys of this hash are the the genes, and the values are the values of the genes. At this point, AI::Genetic passes the same reference that it is storing inside of it. So, if you modify the gene within the fitness function subroutine, it will affect the actual individual. Please be careful.
You tell me :)
This module is still in early beta mode. So please send any bugs or feature requests to me (See AUTHOR).
Either the usual:
perl Makefile.PL
make
make install
or just stick it somewhere in @INC where perl can find it. It's in pure Perl.
Ala Qumsieh aqumsieh@cpan.org
This module is distributed under the same terms as Perl itself.
|
AI::Genetic - A pure Perl genetic algorithm implementation. |