lib/Algorithm/Evolutionary/Individual/Tree.pm

filter: Statementstmt 45.3% 59 / 130 Branchbran 35.7% 10 / 28 Conditioncond 12.5% 1 / 8 MC/DCmcdc 0.0% 0 / 4 Subroutinesub 55.0% 11 / 20 Podpod 100% 14 / 14 totaltotal 46.5% 95 / 204 CC 21 SCAR 24.2
CC
21
Cov
42%
nodePrint
30.0
lolprint
30.0
set
12.0
CRAP 11.3
« blib/lib/Algorithm/Evolutionary/Fitness/Trap.pm ↑ Summary blib/lib/Algorithm/Evolutionary/Fitness/Knapsack.pm »
1 2 ▶use strict; #-*-cperl-*-
Subroutine BEGIN: called CC=1 SCAR=0.0
2 2 ▶use warnings;
Subroutine BEGIN: called CC=1 SCAR=0.0
3  
4 =head1 NAME
5  
6 Tree - A Direct Acyclic Graph, or tree, useful for Genetic Programming-Style stuff
7  
8 =head1 SYNOPSIS
9  
10 use Algorithm::Evolutionary::Individual::Tree;
11 #Hash with primitives, arity, and range for constants that multiply it
12  
13 my $primitives = { sum => [2, -1, 1],
14 multiply => [2, -1, 1],
15 substract => [2, -1, 1],
16 divide => [2, -1, 1],
17 x => [0, -10, 10],
18 y => [0, -10, 10] };
19  
20 my $indi = new Algorithm::Evolutionary::Individual::Tree $primitives, 5 ; # Build random tree with knwo primitives
21 # and depth up to 5
22  
23 my $indi5 = $indi->clone(); #Creates a copy of the individual
24  
25 print $indi3->asString(); #Prints the individual
26 print $indi3->asXML() #Prints it as XML. See L<XML> for more info on this
27  
28 =head1 Base Class
29  
30 L<Algorithm::Evolutionary::Individual::Base|Algorithm::Evolutionary::Individual::Base>
31  
32 =head1 DESCRIPTION
33  
34 Tree-like individual for genetic programming. Uses direct acyclic graphs
35 as representation for trees, which is very convenient. This class has
36 not been tested extensively, so it might not work.
37  
38 =cut
39  
40 package Algorithm::Evolutionary::Individual::Tree;
41  
42 2 ▶use Carp;
Subroutine BEGIN: called CC=1 SCAR=0.0
43 2 ▶use Exporter;
Subroutine BEGIN: called CC=1 SCAR=0.0
44  
45 2 our ($VERSION) = ( '$Revision: 3.1 $ ' =~ / (\d+\.\d+)/ );
46  
47 2 ▶use Tree::DAG_Node;
Subroutine BEGIN: called CC=1 SCAR=0.0
48  
49 2 ▶use Algorithm::Evolutionary::Individual::Base;
Subroutine BEGIN: called CC=1 SCAR=0.0
50  
51 2 our @ISA = qw (Algorithm::Evolutionary::Individual::Base);
52  
53 =head1 METHODS
54  
55 =head2 new( $primitives, $depth, $fitness )
56  
57 Creates a new tree using a primitives hashref, max depth, and a
58 ref-to-fitness
59  
60 =cut
61  
62 1 ▶sub new {
Subroutine new: called CC=1 SCAR=0.0
Pod documented
63 1 my $class = shift;
64 1 my $self = {_primitives => shift,
65 _depth => shift,
66 _fitness => undef };
67 1 my @keys = keys %{$self->{_primitives}};
68 1 $self->{_keys} = \@keys;
69 1 bless $self, $class;
70 1 $self->randomize();
71 1 return $self;
72 }
73  
74 =head2 set
75  
76 Sets values of an individual; takes a hash as input
77  
78 =cut
79  
80 0 ▶sub set {
Subroutine set: not called CC=3 SCAR=24.8
Pod documented
81 0 my $self = shift;
82 0 ▶ my $hash = shift || croak "No params here";
Condition0%0/2
shift() || croak('No params here')
l!l
00
MC/DC0%0/1
shift() || croak('No params here')
shift()
Truth table0%0/2
A
A= shift()
Aresult
11
00
83 0 for ( keys %{$hash} ) {
84 0 $self->{"_$_"} = $hash->{$_};
85 }
86 0 $self->{_tree} = undef;
87 0 $self->{_fitness} = undef;
88 }
89  
90 =head2 randomize
91  
92 Assigns random values to the elements
93  
94 =cut
95  
96 1 ▶sub randomize {
Subroutine randomize: called CC=2 SCAR=6.9
Pod documented
97 1 my $self = shift;
98 1 $self->{_tree} = Tree::DAG_Node->new();
99 1 my $name;
100 do {
101 2 $name = $self->{'_keys'}[rand( @{$self->{'_keys'}} - 1 )];
102 1 ▶ } until $self->{'_primitives'}{$name}[0] > 1; #0 is arity
Branch: 1 branch
BranchTrueFalseTotal
$self->{"_primitives"}{$name}[0] > 1 or do { do { $name = $self->{"_keys"}[rand @{$self->{"_keys"};} - 1] } } 1 1 2
103 #Compute random constant
104 my $ct = $self->{'_primitives'}{$name}[1]
105 1 + rand( $self->{'_primitives'}{$name}[2] - $self->{'_primitives'}{$name}[1]);
106 1 $self->{'_tree'}->name( $name ); #Root node
107 1 $self->{'_tree'}->attributes( { constant => $ct} );
108 1 $self->growSubTree( $self->{'_tree'}, $self->{_depth} );
109 }
110  
111  
112 =head2 fromString
113  
114 Probably useless, in this case. To be evolved.
115  
116 =cut
117  
118 0 ▶sub fromString {
Subroutine fromString: not called CC=2 SCAR=17.9
Pod documented
119 0 my $class = shift;
120 0 my $str = shift;
121 0 ▶ my $sep = shift || ",";
Condition0%0/2
shift() || ','
l!l
00
MC/DC0%0/1
shift() || ','
shift()
Truth table0%0/2
A
A= shift()
Aresult
11
00
122 0 my $self = { _array => split( $sep, $str ),
123 _fitness => undef };
124 0 bless $self, $class;
125 0 return $self;
126 }
127  
128 =head2 clone
129  
130 Similar to a copy ctor: creates a new individual from another one
131  
132 =cut
133  
134 0 ▶sub clone {
Subroutine clone: not called CC=2 SCAR=17.9
Pod documented
135 0 ▶ my $indi = shift || croak "Indi to clone missing ";
Condition0%0/2
shift() || croak('Indi to clone missing ')
l!l
00
MC/DC0%0/1
shift() || croak('Indi to clone missing ')
shift()
Truth table0%0/2
A
A= shift()
Aresult
11
00
136 my $self = { _fitness => undef,
137 0 _depth => $indi->{_depth} };
138 0 %{$self->{_primitives}} = %{$indi->{_primitives}};
139 0 @{$self->{_keys}} = @{$indi->{_keys}};
140 0 $self->{_tree} = $indi->{_tree}->copy_tree();
141 0 bless $self, __PACKAGE__;
142 0 return $self;
143 }
144  
145  
146 =head2 asString
147  
148 Prints it
149  
150 =cut
151  
152 0 ▶sub asString {
Subroutine asString: not called CC=1 SCAR=6.9
Pod documented
153 0 my $self = shift;
154 #my $lol = $self->{_tree}->tree_to_lol();
155 # my $str = lolprint( @$lol );
156 # $str .= " -> ";
157 # if ( defined $self->{_fitness} ) {
158 # $str .=$self->{_fitness};
159 # }
160 0 my $node = $self->{_tree};
161 0 my $str;
162 $node->walk_down( { callback => \&nodePrint,
163 callbackback => \&closeParens,
164 str => \$str,
165 0 primitives => $self->{_primitives}} );
166 # print $self->{_tree}->tree_to_lol_notation();
167 0 return $str;
168 }
169  
170 =head2 nodePrint
171  
172 Prints a node
173  
174 =cut
175  
176 0 ▶sub nodePrint {
Subroutine nodePrint: not called CC=5 SCAR=34.0
Pod documented
177 0 my $node = shift;
178 0 my $options = shift;
179 0 my $strRef = $options->{str};
180 0 ▶ ${$strRef} .= ($node->attributes()->{constant}?($node->attributes()->{constant}. "*"):""). $node->name();
Branch: 1 branch
BranchTrueFalseTotal
$node->attributes->{'constant'} ? : 0 0 0
181 0 ▶ if ( $options->{primitives}{$node->name()}[0] > 0 ) { #That's the arity
Branch: 2 branches
BranchTrueFalseTotal
if ($options->{'primitives'}{$node->name}[0] > 0) { } 0 0 0
elsif ($options->{'primitives'}{$node->name}[0] == 0) { } 0 0 0
182 0 ${$strRef} .= "( ";
183 } elsif ( $options->{primitives}{$node->name()}[0] == 0 ){ #Add comma
184 0 ▶ if ($node->right_sister() ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($node->right_sister) 0 0 0
185 0 ${$strRef} .= ", ";
186 }
187 }
188
189 }
190  
191 =head2 closeParens
192  
193 Internal subrutine: closes node parenthesis
194  
195 =cut
196  
197 0 ▶sub closeParens {
Subroutine closeParens: not called CC=3 SCAR=24.8
Pod documented
198 0 my $node = shift;
199 0 my $options = shift;
200 0 my $strRef = $options->{str};
201 0 ▶ if ( $options->{primitives}{$node->name()}[0] > 0 ) { #That's the arity
Branch: 1 branch
BranchTrueFalseTotal
if ($options->{"primitives"}{$node->name}[0] > 0) 0 0 0
202 0 ${$strRef} .= " ) ";
203 0 ▶ if ($node->right_sister() ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($node->right_sister) 0 0 0
204 0 ${$strRef} .= ", ";
205 }
206 }
207
208 }
209  
210  
211 =head2 Atom
212  
213 Returns the tree, which is atomic by itself. Cannot be used as lvalue
214  
215 =cut
216  
217 1 ▶sub Atom {
Subroutine Atom: called CC=1 SCAR=0.0
Pod documented
218 1 my $self = shift;
219 1 return $self->{'_tree'};
220 }
221  
222 =head2 asXML
223  
224 Prints it as XML. It prints the tree as String, which does not mean
225 you will be able to get it back from this form. It's done just for
226 compatibity, reading from this format will be available. In the future.
227  
228 =cut
229  
230 0 ▶sub asXML {
Subroutine asXML: not called CC=1 SCAR=6.9
Pod documented
231 0 my $self = shift;
232 0 my $str = $self->SUPER::asXML();
233 # my $str2 = ">\n<atom><![CDATA[".$self->asString()."]]></atom> ";
234 0 my $str2 = ">\n<atom><![CDATA[dummy root node]]></atom> ";
235 0 $str =~ s/\/>/$str2/e ;
236 0 return $str.$str2."\n</indi>";
237 }
238  
239  
240 =head2 addAtom
241  
242 Dummy sub
243  
244 =cut
245  
246 0 ▶sub addAtom {
Subroutine addAtom: not called CC=1 SCAR=6.9
Pod documented
247 0 my $self = shift;
248 0 $self->{_tree} = Tree::DAG_Node->new();
249 0 $self->{'_tree'}->name( "dummy root node" ); #Root node
250 0 $self->{'_tree'}->attributes( { constant => 0 } );
251 }
252  
253 =head2 lolprint
254  
255 Print the list of lists that composes the tree, using prefix notation
256  
257 =cut
258  
259 0 ▶sub lolprint {
Subroutine lolprint: not called CC=5 SCAR=34.0
Pod documented
260 0 my @ar = @_;
261 0 my $str;
262 0 ▶ if ( $#ar > 0 ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($#ar > 0) { } 0 0 0
263 0 $str = $ar[$#ar]."(";
264 0 for ( @ar[0..$#ar-1] ) {
265 0 ▶ if ( ref $_ eq 'ARRAY' ) {
Branch: 1 branch
BranchTrueFalseTotal
if (ref $_ eq 'ARRAY') { } 0 0 0
266 0 $str .= lolprint( @$_ );
267 } else {
268 0 $str .= $_;
269 }
270 0 ▶ $str .= ", " if ($_ != $ar[$#ar-1]);
Branch: 1 branch
BranchTrueFalseTotal
if $_ != $ar[$#ar - 1] 0 0 0
271 }
272 0 $str .= " )";
273  
274 } else {
275 0 $str = $ar[0];
276 }
277 0 return $str;
278 }
279  
280 =head2 growSubTree
281  
282 Grows a random tree, with primitives as indicated, and a certain depth. Depth
283 defaults to 4
284  
285 =cut
286  
287 9 ▶sub growSubTree {
Subroutine growSubTree: called CC=6 SCAR=17.9
Pod documented
288 9 my $self = shift;
289 9 my $tree = shift;
290 9 ▶ my $depth = shift || 4;
Condition50%1/2
shift() || 4
l!l
90
MC/DC0%0/1
shift() || 4
shift()
Truth table50%1/2
A
A= shift()
Aresult
11
00
291 9 ▶ return if $depth == 1;
Branch: 1 branch
BranchTrueFalseTotal
if $depth == 1 4 5 9
292 5 ▶ for ( my $i = 0; $i < $self->{_primitives}{$tree->name()}[0]; $i++ ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i < $self->{"_primitives"}{$tree->name}[0]) 8 5 13
293 8 my $primitive;
294 8 ▶ if ( $depth > 2 ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($depth > 2) { } 4 4 8
295 4 $primitive = $self->{_keys}[rand( @{$self->{_keys}} )];
296 } else {
297 do {
298 18 $primitive = $self->{_keys}[rand( @{$self->{_keys}} )];
299 4 ▶ } until $self->{_primitives}{$primitive}[0] == 0;
Branch: 1 branch
BranchTrueFalseTotal
$self->{"_primitives"}{$primitive}[0] == 0 or do { do { $primitive = $self->{"_keys"}[rand @{$self->{"_keys"};}] } } 4 14 18
300 }
301 8 my $shiquiya = $tree->new_daughter();
302 #Generate constant
303 my $ct = $self->{_primitives}{$primitive}[1]
304 8 + rand( $self->{_primitives}{$primitive}[2] - $self->{_primitives}{$primitive}[1]);
305 8 $shiquiya->name($primitive);
306 8 $shiquiya->attributes( { constant => $ct} );
307 8 $self->growSubTree( $shiquiya, $depth-1);
308 }
309 }
310  
311 =head2 size()
312  
313 Returns 1, since it's got only 1 Atom
314  
315 =cut
316  
317 3 ▶sub size {
Subroutine size: called CC=1 SCAR=0.0
Pod documented
318 3 my $self = shift;
319 3 return 1;
320 }
321  
322 =head1 Copyright
323
324 This file is released under the GPL. See the LICENSE file included in this distribution,
325 or go to http://www.fsf.org/licenses/gpl.txt
326  
327 CVS Info: $Date: 2009/07/28 11:30:56 $
328 $Header: /media/Backup/Repos/opeal/opeal/Algorithm-Evolutionary/lib/Algorithm/Evolutionary/Individual/Tree.pm,v 3.1 2009/07/28 11:30:56 jmerelo Exp $
329 $Author: jmerelo $
330 $Revision: 3.1 $
331 $Name $
332  
333 =cut
« blib/lib/Algorithm/Evolutionary/Fitness/Trap.pm ↑ Summary blib/lib/Algorithm/Evolutionary/Fitness/Knapsack.pm »