« blib/lib/Algorithm/Evolutionary/Fitness/wP_Peaks.pm
↑ Summary
lib/Algorithm/Evolutionary/Hash_Wheel.pm »
| 1 | #!/usr/bin/env perl | ||
| 2 | |||
| 3 | =head1 NAME | ||
| 4 | |||
| 5 | rectangle-coverage.pl - Find the dot maximally covered by (random) rectangles | ||
| 6 | |||
| 7 | =head1 SYNOPSIS | ||
| 8 | |||
| 9 | You might have to do | ||
| 10 | |||
| 11 | prompt% cpanm --installdeps . | ||
| 12 | |||
| 13 | first, since that module is not installed by default with L<Algorithm::Evolutionary>. Use C<sudo> if appropriate. | ||
| 14 | |||
| 15 | prompt% ./rectangle-coverage.pl <number-of-rectangles> <arena-side> <bits-per-coordinate> <population> <number of generations> <selection rate> | ||
| 16 | |||
| 17 | Or | ||
| 18 | |||
| 19 | prompt% ./rectangle-coverage.pl | ||
| 20 | |||
| 21 | And change variable values from the user interface | ||
| 22 | |||
| 23 | =head1 DESCRIPTION | ||
| 24 | |||
| 25 | A demo that combines the L<Algorithm::Evolutionary::Op::Easy> module | ||
| 26 | with L<Tk> to create a visual demo of the evolutionary | ||
| 27 | algorithm. It generates randomly a number of rectangles, and shows | ||
| 28 | how the population evolves to find the solution. The best point is | ||
| 29 | shown in darkening yellow color, the rest of the population in | ||
| 30 | green. | ||
| 31 | |||
| 32 | Use "Start" to start the algorithm after setting the variables, and | ||
| 33 | then Finish to stop the EA, Exit to close the window. | ||
| 34 | |||
| 35 | Default values are as follows | ||
| 36 | |||
| 37 | =over | ||
| 38 | |||
| 39 | =item * | ||
| 40 | |||
| 41 | I<number of rectangles>: 300 | ||
| 42 | |||
| 43 | =item * | ||
| 44 | |||
| 45 | I<arena-side>: 10 This is independent from the number of pixels, set | ||
| 46 | by default to 600x600. | ||
| 47 | |||
| 48 | =item * | ||
| 49 | |||
| 50 | I<bits-per-coordinate>: 32 (this is the chromosome length divided by two; | ||
| 51 | there are two "genes") | ||
| 52 | |||
| 53 | =item * | ||
| 54 | |||
| 55 | I<population size>: 64 | ||
| 56 | |||
| 57 | =item * | ||
| 58 | |||
| 59 | I<number of generations>: 200 | ||
| 60 | |||
| 61 | =item * | ||
| 62 | |||
| 63 | 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. | ||
| 64 | |||
| 65 | =back | ||
| 66 | |||
| 67 | This program also demonstrates the use of caches in the fitness | ||
| 68 | evaluation, so be careful if you use too many bits or too many | ||
| 69 | generations, check out memory usage. | ||
| 70 | |||
| 71 | Console output shows the number of generations, the winning chromosome, and | ||
| 72 | fitness. After finishing, it outputs time, cache ratio and some other | ||
| 73 | things. | ||
| 74 | |||
| 75 | =cut | ||
| 76 | |||
| 77 | use Tk; | ||
| 78 | use strict; | ||
| 79 | use warnings; | ||
| 80 | |||
| 81 | use Algorithm::RectanglesContainingDot; | ||
| 82 | |||
| 83 | use lib qw(lib ../lib); | ||
| 84 | use Algorithm::Evolutionary qw( Individual::BitString Op::Easy | ||
| 85 | Op::Bitflip Op::Crossover ); | ||
| 86 | |||
| 87 | |||
| 88 | my $width = 600; | ||
| 89 | my $height = 500; | ||
| 90 | |||
| 91 | # Create MainWindow and configure: | ||
| 92 | my $mw = MainWindow->new; | ||
| 93 | $mw->configure( -width=>$width, -height=>$width ); | ||
| 94 | $mw->resizable( 0, 0 ); # not resizable in any direction | ||
| 95 | |||
| 96 | my $num_rects = shift || 300; | ||
| 97 | my $arena_side = shift || 10; | ||
| 98 | |||
| 99 | my $bits = shift || 32; | ||
| 100 | my $pop_size = shift || 64; #Population size | ||
| 101 | my $number_of_generations = shift || 200; #Max number of generations | ||
| 102 | my $selection_rate = shift || 0.2; | ||
| 103 | my $scale_x = $arena_side/$width; | ||
| 104 | my $scale_y = $arena_side/$height; | ||
| 105 | |||
| 106 | my $alg = Algorithm::RectanglesContainingDot->new; | ||
| 107 | my $fitness; | ||
| 108 | my $generation; | ||
| 109 | my @pop; | ||
| 110 | # Start Evolutionary Algorithm | ||
| 111 | my $contador=0; | ||
| 112 | my $dot_size = 6; | ||
| 113 | my $mini_dot_size = $dot_size/2; | ||
| 114 | my @dot_population; | ||
| 115 | |||
| 116 | # Create and configure the widgets | ||
| 117 | my $f = $mw->Frame(-relief => 'groove', | ||
| 118 | -bd => 2)->pack(-side => 'top', | ||
| 119 | -fill => 'x'); | ||
| 120 | |||
| 121 | for my $v ( qw( num_rects arena_side bits pop_size number_of_generations selection_rate ) ){ | ||
| 122 | create_and_pack( $f, $v ); | ||
| 123 | } | ||
| 124 | |||
| 125 | my $canvas = $mw->Canvas( -cursor=>"crosshair", -background=>"white", | ||
| 126 | -width=>$width, -height=>$height )->pack; | ||
| 127 | $mw->Button( -text => 'Start', | ||
| 128 | -command => \&start, | ||
| 129 | )->pack( -side => 'left', | ||
| 130 | -expand => 1); | ||
| 131 | $mw->Button( -text => 'End', | ||
| 132 | -command => \&finished, | ||
| 133 | )->pack( -side => 'left', | ||
| 134 | -expand => 1 ); | ||
| 135 | $mw->Button( -text => 'Exit', | ||
| 136 | -command => sub { exit(0);}, | ||
| 137 | )->pack( -side => 'left', | ||
| 138 | -expand => 1 ); | ||
| 139 | |||
| 140 | $mw->eventAdd('<<Gen>>' => '<Control-Shift-G>'); # Improbable combination | ||
| 141 | $mw->eventAdd('<<Fin>>' => '<Control-C>'); | ||
| 142 | $mw->bind('<<Gen>>' => \&generation); | ||
| 143 | $mw->bind('<<Fin>>' => \&finished ); | ||
| 144 | |||
| 145 | |||
| 146 | sub create_and_pack { | ||
| 147 | my $frame = shift; | ||
| 148 | my $var = shift; | ||
| 149 | my $f = $frame->Frame(); | ||
| 150 | my $label = $f->Label(-text => $var )->pack(-side => 'left'); | ||
| 151 | my $entry = $f->Entry( -textvariable => eval '\$'.$var )->pack(-side => 'right' ); | ||
| 152 | $f->pack(); | ||
| 153 | } | ||
| 154 | |||
| 155 | sub start { | ||
| 156 | #Generate random rectangles | ||
| 157 | for my $i (0 .. $num_rects) { | ||
| 158 | |||
| 159 | my $x_0 = rand( $arena_side ); | ||
| 160 | my $y_0 = rand( $arena_side); | ||
| 161 | my $side_x = rand( $arena_side - $x_0 ); | ||
| 162 | my $side_y = rand($arena_side-$y_0); | ||
| 163 | $alg->add_rectangle("rectangle_$i", $x_0, $y_0, | ||
| 164 | $x_0+$side_x, $x_0+$side_y ); | ||
| 165 | my $val = 255*$i/$num_rects; | ||
| 166 | my $color = sprintf( "#%02x%02x%02x", $val, $val, $val ); | ||
| 167 | $canvas->createRectangle( $x_0/$scale_x, $y_0/$scale_y, | ||
| 168 | $side_x/$scale_x, $side_y/$scale_y, | ||
| 169 | -outline =>$color ); | ||
| 170 | } | ||
| 171 | |||
| 172 | #Declare fitness function | ||
| 173 | $fitness = sub { | ||
| 174 | my $individual = shift; | ||
| 175 | my ( $dot_x, $dot_y ) = $individual->decode($bits/2,0, $arena_side); | ||
| 176 | my @contained_in = $alg->rectangles_containing_dot($dot_x, $dot_y); | ||
| 177 | return scalar @contained_in; | ||
| 178 | }; | ||
| 179 | |||
| 180 | |||
| 181 | |||
| 182 | #----------------------------------------------------------# | ||
| 183 | #Initial population | ||
| 184 | #Creamos $pop_size individuos | ||
| 185 | for ( 0..$pop_size ) { | ||
| 186 | my $indi = Algorithm::Evolutionary::Individual::BitString->new( $bits ); | ||
| 187 | push( @pop, $indi ); | ||
| 188 | } | ||
| 189 | |||
| 190 | #----------------------------------------------------------# | ||
| 191 | # Variation operators | ||
| 192 | my $m = Algorithm::Evolutionary::Op::Bitflip->new; # Rate = 1 | ||
| 193 | my $c = Algorithm::Evolutionary::Op::Crossover->new(2, 9 ); # Rate = 9 | ||
| 194 | |||
| 195 | #----------------------------------------------------------# | ||
| 196 | #Usamos estos operadores para definir una generación del algoritmo. Lo cual | ||
| 197 | # no es realmente necesario ya que este algoritmo define ambos operadores por | ||
| 198 | # defecto. Los parámetros son la función de fitness, la tasa de selección y los | ||
| 199 | # operadores de variación. | ||
| 200 | $generation = Algorithm::Evolutionary::Op::Easy->new( $fitness , $selection_rate , [$m, $c] ) ; | ||
| 201 | |||
| 202 | |||
| 203 | #----------------------------------------------------------# | ||
| 204 | for ( @pop ) { | ||
| 205 | if ( !defined $_->Fitness() ) { | ||
| 206 | my $this_fitness = $fitness->($_); | ||
| 207 | $_->Fitness( $this_fitness ); | ||
| 208 | } | ||
| 209 | } | ||
| 210 | |||
| 211 | #Start the music | ||
| 212 | $mw->eventGenerate( '<<Gen>>', -when => 'tail' ); | ||
| 213 | } | ||
| 214 | |||
| 215 | sub as_point { | ||
| 216 | my $individual = shift || die "Nobody here!n"; | ||
| 217 | my @point = $individual->decode($bits/2,0, $arena_side); | ||
| 218 | return ($point[0]/$scale_x, $point[1]/$scale_y); | ||
| 219 | } | ||
| 220 | |||
| 221 | sub generation { | ||
| 222 | while (@dot_population) { | ||
| 223 | $canvas->delete( shift @dot_population ); | ||
| 224 | } | ||
| 225 | $generation->apply( \@pop ); | ||
| 226 | print "Pop size $#pop\n"; | ||
| 227 | |||
| 228 | my $val = 255*$contador/$number_of_generations; | ||
| 229 | my $color = sprintf( "#%02x%02x00", 255-$val, 255-$val ); | ||
| 230 | my ($point_x, $point_y) = as_point( $pop[0] ); | ||
| 231 | print "$contador : ", $pop[0]->asString(), ", Color $color\n\tDecodes to $point_x, $point_y\n" ; | ||
| 232 | $contador++; | ||
| 233 | |||
| 234 | $canvas->createOval($point_x-$dot_size, $point_y-$dot_size, | ||
| 235 | $point_x+$dot_size, $point_y+$dot_size, | ||
| 236 | -fill => $color ); | ||
| 237 | |||
| 238 | for my $p ( @pop ) { | ||
| 239 | my @point = as_point( $p ); | ||
| 240 | push @dot_population,$canvas->createOval($point[0]-$mini_dot_size, $point[1]-$mini_dot_size, | ||
| 241 | $point[0]+$mini_dot_size, $point[1]+$mini_dot_size, | ||
| 242 | -fill => "#00ff00" ); | ||
| 243 | } | ||
| 244 | $canvas->update(); | ||
| 245 | if ( ($contador < $number_of_generations) | ||
| 246 | && ($pop[0]->Fitness() < $num_rects)) { | ||
| 247 | $mw->eventGenerate( '<<Gen>>', -when => 'tail' ); | ||
| 248 | } else { | ||
| 249 | $mw->eventGenerate( '<<Fin>>' ); | ||
| 250 | } | ||
| 251 | } | ||
| 252 | |||
| 253 | |||
| 254 | sub finished { | ||
| 255 | #----------------------------------------------------------# | ||
| 256 | #leemos el mejor resultado | ||
| 257 | |||
| 258 | #Mostramos los resultados obtenidos | ||
| 259 | print "Best is:\n\t ",$pop[0]->asString()," Fitness: ",$pop[0]->Fitness(),"\n"; | ||
| 260 | } | ||
| 261 | |||
| 262 | MainLoop; | ||
| 263 | =head1 SEE ALSO | ||
| 264 | |||
| 265 | |||
| 266 | First, you should obviously check | ||
| 267 | L<Algorithm::Evolutionary::Op::Easy>, and then these other classes. | ||
| 268 | |||
| 269 | =over 4 | ||
| 270 | |||
| 271 | =item * | ||
| 272 | |||
| 273 | L<Algorithm::Evolutionary::Op::Base>. | ||
| 274 | |||
| 275 | =item * | ||
| 276 | |||
| 277 | L<Algorithm::Evolutionary::Individual::Base>. | ||
| 278 | |||
| 279 | =item * | ||
| 280 | |||
| 281 | L<Algorithm::Evolutionary::Fitness::Base>. | ||
| 282 | |||
| 283 | =back | ||
| 284 | |||
| 285 | L<Tk> is a prerrequisite for this program, as well as | ||
| 286 | L<Algorithm::RectanglesContainingDot>. Obviously, | ||
| 287 | L<Algorithm::Evolutionary> should be installed too, just in case | ||
| 288 | you got this independently. | ||
| 289 | |||
| 290 | =head1 AUTHOR | ||
| 291 | |||
| 292 | J. J. Merelo, C<jj (at) merelo.net> | ||
| 293 | |||
| 294 | =cut | ||
| 295 | |||
| 296 | =head1 Copyright | ||
| 297 | |||
| 298 | This file is released under the GPL. See the LICENSE file included in this distribution, | ||
| 299 | or go to http://www.fsf.org/licenses/gpl.txt | ||
| 300 | |||
| 301 | CVS Info: $Date: 2012/12/08 10:12:37 $ | ||
| 302 | $Header: /media/Backup/Repos/opeal/opeal/Algorithm-Evolutionary/scripts/rectangle-coverage.pl,v 3.5 2012/12/08 10:12:37 jmerelo Exp $ | ||
| 303 | $Author: jmerelo $ | ||
| 304 | $Revision: 3.5 $ | ||
| 305 | |||
| 306 | =cut | ||
| 307 |