| 1 | #!/usr/local/bin/perl | ||
| 2 | |||
| 3 | =head1 NAME | ||
| 4 | |||
| 5 | canonical-genetic-algorithm.pl - Canonical Genetic Algorithm on a simple fitness function | ||
| 6 | |||
| 7 | =head1 SYNOPSIS | ||
| 8 | |||
| 9 | prompt% ./canonical-genetic-algorithm.pl <bits> <block size> <population> <number of generations> <selection rate> | ||
| 10 | |||
| 11 | |||
| 12 | =head1 DESCRIPTION | ||
| 13 | |||
| 14 | A canonical GA uses mutation, crossover, binary representation, and | ||
| 15 | roulette wheel selection. Here mainly for reference, and so that | ||
| 16 | you can peruse to start your own programs. | ||
| 17 | |||
| 18 | In this case, we are optimizing the Royal Road function, | ||
| 19 | L<http://web.cecs.pdx.edu/~mm/handbook-of-ec-rr.pdf>. By default, | ||
| 20 | these values are used: | ||
| 21 | |||
| 22 | =over | ||
| 23 | |||
| 24 | =item * | ||
| 25 | |||
| 26 | I<number of bits>: 64 (this is the chromosome length) | ||
| 27 | |||
| 28 | =item * | ||
| 29 | |||
| 30 | I<size of block>: 4 (RR goes by blocks) | ||
| 31 | |||
| 32 | =item * | ||
| 33 | |||
| 34 | I<population size>: 256 | ||
| 35 | |||
| 36 | =item * | ||
| 37 | |||
| 38 | I<number of generations>: 200 (could end before, if solution is | ||
| 39 | found) | ||
| 40 | |||
| 41 | =item * | ||
| 42 | |||
| 43 | I<selection rate>: 20% (will be replaced each generation); this means it's a steady state algorithm, which only changes a part of the population each generation. | ||
| 44 | |||
| 45 | =back | ||
| 46 | |||
| 47 | This program also demonstrates the use of caches in the fitness | ||
| 48 | evaluation, so be careful if you use too many bits or too many | ||
| 49 | generations, check the memory. | ||
| 50 | |||
| 51 | Output shows the number of generations, the winning chromosome, and | ||
| 52 | fitness. After finishing, it outputs time, cache ratio and some other | ||
| 53 | things. | ||
| 54 | |||
| 55 | =cut | ||
| 56 | |||
| 57 | use warnings; | ||
| 58 | use strict; | ||
| 59 | |||
| 60 | use Time::HiRes qw( gettimeofday tv_interval); #for benchmarking | ||
| 61 | |||
| 62 | use lib qw(lib ../lib); | ||
| 63 | #Importing all neded modules using the short POE-ish version | ||
| 64 | use Algorithm::Evolutionary qw( Individual::BitString Op::Creator | ||
| 65 | Op::CanonicalGA Op::Bitflip | ||
| 66 | Op::Crossover Fitness::Royal_Road); | ||
| 67 | use Algorithm::Evolutionary::Utils qw(entropy consensus); | ||
| 68 | |||
| 69 | #----------------------------------------------------------# | ||
| 70 | my $bits = shift || 64; | ||
| 71 | my $block_size = shift || 4; | ||
| 72 | my $pop_size = shift || 256; #Population size | ||
| 73 | my $numGens = shift || 200; #Max number of generations | ||
| 74 | my $selection_rate = shift || 0.2; | ||
| 75 | |||
| 76 | |||
| 77 | #----------------------------------------------------------# | ||
| 78 | #Initial population | ||
| 79 | my @pop; | ||
| 80 | my $creator = new Algorithm::Evolutionary::Op::Creator( $pop_size, 'BitString', { length => $bits }); | ||
| 81 | $creator->apply( \@pop ); #Generates population | ||
| 82 | |||
| 83 | #----------------------------------------------------------# | ||
| 84 | # Variation operators | ||
| 85 | my $m = Algorithm::Evolutionary::Op::Bitflip->new( 1 ); | ||
| 86 | my $c = Algorithm::Evolutionary::Op::Crossover->new(2, 4); | ||
| 87 | |||
| 88 | # Fitness function: create it and evaluate | ||
| 89 | my $rr = new Algorithm::Evolutionary::Fitness::Royal_Road( $block_size ); | ||
| 90 | map( $_->evaluate( $rr ), @pop ); | ||
| 91 | |||
| 92 | #----------------------------------------------------------# | ||
| 93 | #Usamos estos operadores para definir una generación del algoritmo. Lo cual | ||
| 94 | # no es realmente necesario ya que este algoritmo define ambos operadores por | ||
| 95 | # defecto. Los parámetros son la función de fitness, la tasa de selección y los | ||
| 96 | # operadores de variación. | ||
| 97 | my $generation = Algorithm::Evolutionary::Op::CanonicalGA->new( $rr , $selection_rate , [$m, $c] ) ; | ||
| 98 | |||
| 99 | #Time, counter and do the do | ||
| 100 | my $inicioTiempo = [gettimeofday()]; | ||
| 101 | my $contador=0; | ||
| 102 | do { | ||
| 103 | $generation->apply( \@pop ); | ||
| 104 | print "$contador : ", $pop[0]->asString(), "\n" ; | ||
| 105 | $contador++; | ||
| 106 | } while( ($contador < $numGens) | ||
| 107 | && ($pop[0]->Fitness() < $bits)); | ||
| 108 | |||
| 109 | |||
| 110 | #----------------------------------------------------------# | ||
| 111 | # Show best | ||
| 112 | print "Best is:\n\t ",$pop[0]->asString()," Fitness: ",$pop[0]->Fitness(),"\n"; | ||
| 113 | |||
| 114 | print "\n\n\tTime: ", tv_interval( $inicioTiempo ) , "\n"; | ||
| 115 | |||
| 116 | print "\n\tEvaluations: ", $rr->evaluations(), "\n"; | ||
| 117 | |||
| 118 | print "\n\tCache size ratio: ", $rr->cached_evals()/$rr->evaluations(), "\n"; | ||
| 119 | |||
| 120 | =head1 SEE ALSO | ||
| 121 | |||
| 122 | |||
| 123 | First, you should obviously check | ||
| 124 | L<Algorithm::Evolutionary::Op::CanonicalGA>, and then these other classes. | ||
| 125 | |||
| 126 | =over 4 | ||
| 127 | |||
| 128 | =item * | ||
| 129 | |||
| 130 | L<Algorithm::Evolutionary::Op::Base>. | ||
| 131 | |||
| 132 | =item * | ||
| 133 | |||
| 134 | L<Algorithm::Evolutionary::Individual::Base>. | ||
| 135 | |||
| 136 | =item * | ||
| 137 | |||
| 138 | L<Algorithm::Evolutionary::Fitness::Base>. | ||
| 139 | |||
| 140 | =item * | ||
| 141 | |||
| 142 | L<Algorithm::Evolutionary::Experiment>. | ||
| 143 | |||
| 144 | =item * | ||
| 145 | |||
| 146 | L<XML> | ||
| 147 | |||
| 148 | =back | ||
| 149 | |||
| 150 | =head1 AUTHOR | ||
| 151 | |||
| 152 | J. J. Merelo, C<jj (at) merelo.net> | ||
| 153 | |||
| 154 | =cut | ||
| 155 | |||
| 156 | =head1 Copyright | ||
| 157 | |||
| 158 | This file is released under the GPL. See the LICENSE file included in this distribution, | ||
| 159 | or go to http://www.fsf.org/licenses/gpl.txt | ||
| 160 | |||
| 161 | CVS Info: $Date: 2009/07/30 07:48:48 $ | ||
| 162 | $Header: /media/Backup/Repos/opeal/opeal/Algorithm-Evolutionary/scripts/canonical-genetic-algorithm.pl,v 3.1 2009/07/30 07:48:48 jmerelo Exp $ | ||
| 163 | $Author: jmerelo $ | ||
| 164 | $Revision: 3.1 $ | ||
| 165 | |||
| 166 | |||
| 167 | =cut |