As per your suggestions, the following is the updated code, but as of now it gives me an error of "Out of memory!" after running for a while. It might that I am testing it out on a school system with several people online, or that I am just using too much memory with $hashes. I will let you know the results when I get home.
#!/usr/bin/perl
use strict;
use warnings;
#possible values the node of a tree can be
my(@node_values) = ("a1","a0","d0","d1","d2","d3","AND","OR","NOT");
#probability of one of the following next genereation functions will h
+appen
my(@prob) = (10, #Reproduction
95, #Crossover
5);#Mutation
#the minimum fitness a person must have to be considered for any nexy
+genereation functions
my($min_fitness) = 10;
#defines the possible values for the truth table
my(%range) = ();
#will generate a logic equation and place it in a tree format
#it is done recursively to a certain depth (defined in level)
#this is called for intializing a population
sub generate_tree() {
my( $node, $level) = @_;
unless($node) {
$node = {};
$node->{left} = undef;
$node->{right} = undef;
$node->{op} = 0;
}
if($level > 0) {
my($op) = @node_values[int(rand($#node_values))];
if($op eq "AND") {
&generate_tree($node->{left}, $level-1 );
&generate_tree($node->{right}, $level-1 );
}
if($op eq "OR") {
&generate_tree($node->{left}, $level-1 );
&generate_tree($node->{right}, $level-1 );
}
if($op eq "NOT") {
&generate_tree($level-1, $node->{left});
$node->{right} = undef;
}
$node->{op} = $op;
}
if($level == 0) {
$node = {};
$node->{left} = undef;
$node->{right} = undef;
$node->{op} = (@node_values[int(rand(6))]);
}
$_[0] = $node;
return;
}
#converts a decimal number to a binary string
#used to generate values for range
sub dec2bin {
my $str = unpack("B32", pack("N", shift));
$str =~ s/^0+(?=\d)//; # otherwise you'll get leading zeros
return substr($str, -6);
}
#this initializes a population of possible solutions at a certain size
sub initialize() {
my($size) = shift;
my(@people) = {};
print "Intial String:\n";
for(my $i = 0; $i < $size; $i++) {
$people[$i]{'fitness'} = 0;
&generate_tree($people[$i]->{'tree'}, int(rand(6))+1 );
print &string_tree($people[$i]->{'tree'}) . "\n";
}
#the following generates the truth table
#the equation be looked for needs to match
for(my $i = 0; $i < 64; $i++) {
my $value = &dec2bin($i);
my($a0,$a1,$d0,$d1,$d2,$d3) = split(//,$value);
$range{$value} = 0;
if($a0 eq "0" && $a1 eq "0" && $d0 eq "1") {$range{$value} = 1
+;}
if($a0 eq "1" && $a1 eq "0" && $d1 eq "1") {$range{$value} = 1
+;}
if($a0 eq "0" && $a1 eq "1" && $d2 eq "1") {$range{$value} = 1
+;}
if($a0 eq "1" && $a1 eq "1" && $d3 eq "1") {$range{$value} = 1
+;}
}
return(@people);
}
#takes a tree and evaluates it into an actual logical equation
sub eval_tree() {
my($tree) = shift;
my($value) = shift;
if($tree->{op} eq "AND") {return(&eval_tree($tree->{left},$value)
+& &eval_tree($tree->{right}, $value));}
if($tree->{op} eq "OR") {return(&eval_tree($tree->{left},$value) |
+ &eval_tree($tree->{right}, $value));}
if($tree->{op} eq "NOT") {return(!(&eval_tree($tree->{left},$value
+)));}
if($tree->{op} eq "a0") {return(substr($value,0));}
if($tree->{op} eq "a1") {return(substr($value,1));}
if($tree->{op} eq "d0") {return(substr($value,2));}
if($tree->{op} eq "d1") {return(substr($value,3));}
if($tree->{op} eq "d2") {return(substr($value,4));}
if($tree->{op} eq "d3") {return(substr($value,5));}
}
sub calc_fitness() {
my(@people) = @_;
for(my $i = 0; $i < $#people; $i++) {
$people[$i]{'fitness'} = 0;
foreach my $value (keys %range) {
if(&eval_tree($people[$i]{'tree'}, $value) == $range{$valu
+e}) {$people[$i]{'fitness'}++;}
}
}
return(@people);
}
#takes a tree and converts it into a string
sub string_tree() {
my($tree) = shift;
my($value) = shift;
if($tree->{op} eq "AND") {return("(" . &string_tree($tree->{left},
+$value) . " AND " . &string_tree($tree->{right}, $value) . ")");}
if($tree->{op} eq "OR") {return("(" . &string_tree($tree->{left},$
+value) . " OR " . &string_tree($tree->{right}, $value) . ")");}
if($tree->{op} eq "NOT") {return("(NOT " . (&string_tree($tree->{l
+eft},$value)) . ")");}
if($tree->{op} eq "a0") {return("a0");}
if($tree->{op} eq "a1") {return("a1");}
if($tree->{op} eq "d0") {return("d0");}
if($tree->{op} eq "d1") {return("d1");}
if($tree->{op} eq "d2") {return("d2");}
if($tree->{op} eq "d3") {return("d3");}
}
sub found_solution() {
my(@people) = @_;
for(my $i = 0; $i < $#people; $i++) {
if($people[$i]->{'fitness'} == 64) {
print "Solution Found:\n";
print &string_tree($people[$i]->{'tree'});
return(1);
}
}
return(0);
}
sub get_random_node() {
my($tree) = shift;
my($prob) = int(rand(100));
if($prob < 40 && defined ($tree->{left})) {return(get_random_node(
+$tree->{left}));}
if($prob > 60 && defined ($tree->{right})) {return(get_random_node
+($tree->{right}));}
return($tree);
}
sub replace_node() {
my($tree,$a,$b) = @_;
if($tree == $a) {
$tree = $b;
} else{
if(defined($tree->{left})) {&replace_node($tree->{left},$a,$b)
+;}
if(defined($tree->{right})) {&replace_node($tree->{right},$a,$
+b);}
}
$_[0] = $tree;
return;
}
sub crossover() {
my($tree_a, $tree_b) = @_;
my($node_a) = &get_random_node($tree_a);
my($node_b) = &get_random_node($tree_b);
&replace_node($tree_a, $node_a, $node_b);
&replace_node($tree_b, $node_b, $node_a);
return($tree_a, $tree_b);
}
sub mutation() {
my($tree) = shift;
my($node_a) = &get_random_node($tree);
my($node_b) = {};
&generate_tree($node_b, int(rand(3))+1 );
&replace_node($tree, $node_a, $node_b);
return($tree);
}
for(my $size = 100; $size < 101; $size++) {
print "Size: $size\n";
my(@population) = &initialize($size);
my($generation) = 0;
my $quit = 0;
while($quit == 0){
@population = &calc_fitness(@population);
if(&found_solution(@population)) {
print "\tFinal Generation: $generation\n";
$quit = 1;
} else{
my(@children) = ();
my($children_size) = 0;
while($children_size < $size) {
my($choice) = int(rand(100) + 1);
if(($choice >= 1) && ($choice <= $prob[0])) {
#Reproduction
my($person_a) = int(rand($size));
while($population[$person_a]->{'fitness'} < $min_f
+itness) {$person_a = int(rand($size));}
push(@children,$population[$person_a]);
$children_size++;
}
if(($choice > $prob[0]) && ($choice <= $prob[1])) {
#Crossover
my($person_a)= int(rand($size));
my($person_b)= int(rand($size));
while($population[$person_a]->{'fitness'} < $min_f
+itness && $population[$person_b]->{'fitness'} < $min_fitness && $pers
+on_a != $person_b) {
$person_a = int(rand($size));
$person_b = int(rand($size));
}
my($child_a, $child_b) = {};
#print "A : " . &string_tree($population[$person_a
+]->{'tree'}) . "\n";
($child_a->{'tree'},$child_b->{'tree'}) = &crossov
+er($population[$person_a]->{'tree'},$population[$person_b]->{'tree'})
+;
#print "CA : " . &string_tree($child_a->{'tree'})
+. "\n";
push(@children,$child_a);
push(@children,$child_b);
$children_size+=2;
}
if(($choice > $prob[1]) && ($choice <= 100)) {
#Mutations
my($person_a) = int(rand($size));
while($population[$person_a]->{'fitness'} < $min_f
+itness) {$person_a = int(rand($size));}
my($child_a) = {};
#print "MA : " . &string_tree($population[$person_
+a]->{'tree'}) . "\n";
($child_a->{'tree'}) = (&mutation($population[$per
+son_a]->{'tree'}));
#print "MA1 : " . &string_tree($child_a->{'tree'})
+ . "\n";
push(@children,$child_a);
$children_size++;
}
}
$generation++;
@population = @children;
}
}
}
Thanks for the help.
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.