NAME

Algorithm::Evolve::Util - Some useful utility functions for use in evolutionary algorithms.

SYNOPSIS

    use Algorithm::Evolve::Util ':str';
    use Algorithm::Evolve::Util ':arr';

SYNTAX

At the moment, this module only provides string- and array-mangling utilities. They can be imported with the use arguments ':str' and ':arr' respectively.

In the following descriptions, a gene refers to either a string or an array reference. A position in the gene refers to a single character for string genes and an array element for array genes.

str_crossover( $string1, $string2 [, $N ] )

arr_crossover( \@array1, \@array2 [, $N ] )

Returns a random N-point crossover between the two given genes. $N defaults to 2. The two inputs should be the same length, although this is not enforced. $N must be also less than the size of the genes.

If you are unfamiliar with the crossover operation, it works like this: Lay down the two genes on top of each other. Pick N positions at random, and cut both genes at each position. Now swap every other pair of segments, and tape the genes back up. So one possible 2-point crossover on the string genes aaaaaa and bbbbbb would produce the two genes abbaaa and baabbb (the two "cuts" here were after the 1st and 3rd positions).

str_agreement( $string1, $string2 )

arr_agreement( \@array1, \@array2 )

Returns the number of positions in which the two genes agree. Does not enforce that they have the same size, even though the result is somewhat meaningless in that case.

String gene comparison is done in a non-unicode-friendly way. To override this and use a (slower) unicode-friendly string comparison, set $Algorithm::Evolve::Util::UNICODE_STRINGS to a true value.

In array genes, the comparison of individual elements is done with eq.

Note that this is the Hamming metric, and not the edit distance metric. Edit distance may be an interesting fitness to use as well. There are at least two modules (Text::Levenshtein and Text::LevenshteinXS) that I know of which calculate the edit distance of two strings.

str_mutate( $string1 [, $num [, \@alphabet ]] )

arr_mutate( \@array1 [, $num [, \@alphabet ]] )

Returns a random mutation of the gene according to the given alphabet (defaulting to {0,1}). If $num is less than 1, it performs probabilistic mutation, with each position having a $num probability of being mutated. If $num is greater than or equal to 1, it performs N-point mutation: exactly $num positions are chosen at random and mutated. $num defaults to 1. A convenient rule of thumb is start with a mutation rate of 1/gene_length.

A mutation will always change the character in question: an 'a' will never be chosen to replace an existing 'a' in a mutation. The following identity holds for N-point mutations:

  str_agreement( str_mutate($some_string, $n, \@alph), $some_string )
    == length($some_string) - $n;

The alphabet for a string gene should consist of only single characters unless you know what you're doing. Conceivably, you can implement an 'add' and 'remove' mutation by using an alphabet that contains strings with length != 1. But this seems a little hackish to me. For array genes, the alphabet can be just about anything meaningful to you.

str_random( $size [, \@alphabet ] )

arr_random( $size [, \@alphabet ] )

Returns a random gene of the given size over the given alphabet, defaulting to {0,1}.

SEE ALSO

Algorithm::Evolve

StringEvolver.pm in the examples/ directory uses the utilities in Algorithm::Evolve::Util to implement a completely generic simple string evolver critter class in very few lines of code.

AUTHOR

Algorithm::Evolve is written by Mike Rosulek <mike@mikero.com>. Feel free to contact me with comments, questions, patches, or whatever.

COPYRIGHT

Copyright (c) 2003 Mike Rosulek. All rights reserved. This module is free software; you can redistribute it and/or modify it under the same terms as Perl itself.