blib/script/rectangle-coverage.pl untested

filter: Statementstmt 0.0% 0 / 106 Branchbran 0.0% 0 / 4 Conditioncond 0.0% 0 / 17 MC/DCmcdc 0.0% 0 / 9 Subroutinesub 0.0% 0 / 11 Podpod 0.0% 0 / 5 totaltotal 0.0% 0 / 152 CC 3 SCAR 11.7
CC
3
Cov
0%
start
6.0
generation
6.0
create_and_pack
2.0
CRAP 3.2
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