Mike Rosulek > Algorithm-Evolve > Algorithm::Evolve::Util
Module Version: 0.03

# 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}.

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.