« 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')
MC/DC0%0/1
shift() || croak('No params here')
shift()
Truth table0%0/2
A
A= shift()
| |||||||||||||||
| 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
| |||||||||||||||
| 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() || ','
MC/DC0%0/1
shift() || ','
shift()
Truth table0%0/2
A
A= shift()
| |||||||||||||||
| 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 ')
MC/DC0%0/1
shift() || croak('Indi to clone missing ')
shift()
Truth table0%0/2
A
A= shift()
| |||||||||||||||
| 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
| |||||||||||||||
| 181 | 0 | ▶ | if ( $options->{primitives}{$node->name()}[0] > 0 ) { #That's the arity | ||||||||||||
|
Branch: 2 branches
| |||||||||||||||
| 182 | 0 | ${$strRef} .= "( "; | |||||||||||||
| 183 | } elsif ( $options->{primitives}{$node->name()}[0] == 0 ){ #Add comma | ||||||||||||||
| 184 | 0 | ▶ | if ($node->right_sister() ) { | ||||||||||||
|
Branch: 1 branch
| |||||||||||||||
| 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
| |||||||||||||||
| 202 | 0 | ${$strRef} .= " ) "; | |||||||||||||
| 203 | 0 | ▶ | if ($node->right_sister() ) { | ||||||||||||
|
Branch: 1 branch
| |||||||||||||||
| 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
| |||||||||||||||
| 263 | 0 | $str = $ar[$#ar]."("; | |||||||||||||
| 264 | 0 | for ( @ar[0..$#ar-1] ) { | |||||||||||||
| 265 | 0 | ▶ | if ( ref $_ eq 'ARRAY' ) { | ||||||||||||
|
Branch: 1 branch
| |||||||||||||||
| 266 | 0 | $str .= lolprint( @$_ ); | |||||||||||||
| 267 | } else { | ||||||||||||||
| 268 | 0 | $str .= $_; | |||||||||||||
| 269 | } | ||||||||||||||
| 270 | 0 | ▶ | $str .= ", " if ($_ != $ar[$#ar-1]); | ||||||||||||
|
Branch: 1 branch
| |||||||||||||||
| 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
MC/DC0%0/1
shift() || 4
shift()
Truth table50%1/2
A
A= shift()
| |||||||||||||||
| 291 | 9 | ▶ | return if $depth == 1; | ||||||||||||
|
Branch: 1 branch
| |||||||||||||||
| 292 | 5 | ▶ | for ( my $i = 0; $i < $self->{_primitives}{$tree->name()}[0]; $i++ ) { | ||||||||||||
|
Branch: 1 branch
| |||||||||||||||
| 293 | 8 | my $primitive; | |||||||||||||
| 294 | 8 | ▶ | if ( $depth > 2 ) { | ||||||||||||
|
Branch: 1 branch
| |||||||||||||||
| 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
| |||||||||||||||
| 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 | ||||||||||||||