« lib/Algorithm/Evolutionary/Wheel.pm
↑ Summary
blib/lib/Algorithm/Evolutionary/Op/TreeMutation.pm »
| 1 | use strict; | ||
| 2 | use warnings; | ||
| 3 | |||
| 4 | =head1 NAME | ||
| 5 | |||
| 6 | Algorithm::Evolutionary::Op::Canonical_GA_NN - Canonical Genetic | ||
| 7 | Algorithm that does not rank population | ||
| 8 | |||
| 9 | =head1 SYNOPSIS | ||
| 10 | |||
| 11 | # Straightforward instance, with all defaults (except for fitness function) | ||
| 12 | my $algo = new Algorithm::Evolutionary::Op::Canonical_GA_NN; | ||
| 13 | |||
| 14 | #Define an easy single-generation algorithm with predefined mutation and crossover | ||
| 15 | my $m = new Algorithm::Evolutionary::Op::Bitflip; #Changes a single bit | ||
| 16 | my $c = new Algorithm::Evolutionary::Op::QuadXOver; #Classical 2-point crossover | ||
| 17 | my $generation = new Algorithm::Evolutionary::Op::Canonical_GA_NN( 0.2, [$m, $c] ); | ||
| 18 | |||
| 19 | my $generation = new Algorithm::Evolutionary::Op::Canonical_GA_NN( undef , [$m, $c] ); # Defaults to 0.4 | ||
| 20 | |||
| 21 | =head1 Base Class | ||
| 22 | |||
| 23 | L<Algorithm::Evolutionary::Op::Base|Algorithm::Evolutionary::Op::Base> | ||
| 24 | |||
| 25 | =head1 DESCRIPTION | ||
| 26 | |||
| 27 | The canonical classical genetic algorithm evolves a population of | ||
| 28 | bitstrings until they reach the optimum fitness. It performs mutation | ||
| 29 | on the bitstrings by flipping a single bit, crossover interchanges a | ||
| 30 | part of the two parents. | ||
| 31 | |||
| 32 | The first operator should be unary (a la mutation) and the second | ||
| 33 | binary (a la crossover) they will be applied in turn to couples of the | ||
| 34 | population. | ||
| 35 | |||
| 36 | This is a fast version of the canonical GA, useful for large | ||
| 37 | populations, since it avoids the expensive rank operation. Roulette | ||
| 38 | wheel selection, still, is kind of slow. | ||
| 39 | |||
| 40 | =head1 METHODS | ||
| 41 | |||
| 42 | =cut | ||
| 43 | |||
| 44 | package Algorithm::Evolutionary::Op::Canonical_GA_NN; | ||
| 45 | |||
| 46 | use lib qw(../../..); | ||
| 47 | |||
| 48 | our $VERSION = "3.6"; | ||
| 49 | |||
| 50 | use Carp; | ||
| 51 | |||
| 52 | use Algorithm::Evolutionary qw(Wheel | ||
| 53 | Op::Bitflip | ||
| 54 | Op::QuadXOver ); | ||
| 55 | |||
| 56 | use base 'Algorithm::Evolutionary::Op::Easy'; | ||
| 57 | |||
| 58 | # Class-wide constants | ||
| 59 | our $APPLIESTO = 'ARRAY'; | ||
| 60 | our $ARITY = 1; | ||
| 61 | |||
| 62 | =head2 new( [ $selection_rate][,$operators_ref_to_array] ) | ||
| 63 | |||
| 64 | Creates an algorithm, with the usual operators. Includes a default | ||
| 65 | mutation and crossover, in case they are not passed as parameters. The | ||
| 66 | first element in the array ref should be an unary, and the second a | ||
| 67 | binary operator. This binary operator must accept parameters by | ||
| 68 | reference, not value; it will modify them. For the time being, just | ||
| 69 | L<Algorithm::Evolutionary::Op::QuadXOver> works that way. | ||
| 70 | |||
| 71 | =cut | ||
| 72 | |||
| 73 | sub new { | ||
| 74 | my $class = shift; | ||
| 75 | my $self = {}; | ||
| 76 | $self->{'_selrate'} = shift || 0.4; | ||
| 77 | if ( @_ ) { | ||
| 78 | $self->{_ops} = shift; | ||
| 79 | } else { | ||
| 80 | #Create mutation and crossover | ||
| 81 | my $mutation = new Algorithm::Evolutionary::Op::Bitflip; | ||
| 82 | push( @{$self->{_ops}}, $mutation ); | ||
| 83 | my $xover = new Algorithm::Evolutionary::Op::QuadXOver 2; | ||
| 84 | push( @{$self->{_ops}}, $xover ); | ||
| 85 | } | ||
| 86 | bless $self, $class; | ||
| 87 | return $self; | ||
| 88 | |||
| 89 | } | ||
| 90 | |||
| 91 | =head2 apply( $population) | ||
| 92 | |||
| 93 | Applies a single generation of the algorithm to the population; checks | ||
| 94 | that it receives a ref-to-array as input, croaks if it does not. This | ||
| 95 | population should be already evaluated. Returns a new population for | ||
| 96 | next generation, unsorted. | ||
| 97 | |||
| 98 | =cut | ||
| 99 | |||
| 100 | sub apply ($) { | ||
| 101 | my $self = shift; | ||
| 102 | my $pop = shift || croak "No population here"; | ||
| 103 | croak "Incorrect type ".(ref $pop) if ref( $pop ) ne $APPLIESTO; | ||
| 104 | |||
| 105 | my @newPop; | ||
| 106 | @$pop = sort { $b->{_fitness} <=> $a->{_fitness} } @$pop; | ||
| 107 | my @rates = map( $_->Fitness(), @$pop ); | ||
| 108 | |||
| 109 | #Creates a roulette wheel from the op priorities. Theoretically, | ||
| 110 | #they might have changed | ||
| 111 | my $popWheel= new Algorithm::Evolutionary::Wheel @rates; | ||
| 112 | my $popSize = scalar @$pop; | ||
| 113 | my @ops = @{$self->{_ops}}; | ||
| 114 | for ( my $i = 0; $i < $popSize*(1-$self->{'_selrate'})/2; $i ++ ) { | ||
| 115 | my @selected = $popWheel->spin(2); | ||
| 116 | my @clones; | ||
| 117 | # This should be a mutation-like op which does not modify arg | ||
| 118 | for my $c (0..1) { | ||
| 119 | $clones[$c] = $ops[0]->apply( $pop->[$selected[$c]] ); | ||
| 120 | } | ||
| 121 | |||
| 122 | $ops[1]->apply( @clones ); #This should be a | ||
| 123 | #crossover-like op | ||
| 124 | push @newPop, @clones; | ||
| 125 | } | ||
| 126 | #Re-sort | ||
| 127 | @{$pop}[$popSize*$self->{_selrate}..$popSize-1] = @newPop; | ||
| 128 | } | ||
| 129 | |||
| 130 | |||
| 131 | =head1 SEE ALSO | ||
| 132 | |||
| 133 | =over 4 | ||
| 134 | |||
| 135 | =item L<Algorithm::Evolutionary::Op::Easy> | ||
| 136 | |||
| 137 | =item L<Algorithm::Evolutionary::Wheel> | ||
| 138 | |||
| 139 | =item L<Algorithm::Evolutionary::Fitness::Base> | ||
| 140 | |||
| 141 | =item Of course, L<Algorithm::Evolutionary::Fitness::CanonicalGA> | ||
| 142 | |||
| 143 | =back | ||
| 144 | |||
| 145 | You will also find a | ||
| 146 | L<canonical-genetic-algorithm.pl> example within this | ||
| 147 | bundle. Check it out for usage examples | ||
| 148 | |||
| 149 | =head1 Copyright | ||
| 150 | |||
| 151 | This file is released under the GPL. See the LICENSE file included in this distribution, | ||
| 152 | or go to http://www.fsf.org/licenses/gpl.txt | ||
| 153 | |||
| 154 | =cut | ||
| 155 | |||
| 156 | "The truth is out there"; |