#!/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 happen 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{\$value}) {\$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->{left},\$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_fitness) {\$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_fitness && \$population[\$person_b]->{'fitness'} < \$min_fitness && \$person_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'}) = &crossover(\$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_fitness) {\$person_a = int(rand(\$size));} my(\$child_a) = {}; #print "MA : " . &string_tree(\$population[\$person_a]->{'tree'}) . "\n"; (\$child_a->{'tree'}) = (&mutation(\$population[\$person_a]->{'tree'})); #print "MA1 : " . &string_tree(\$child_a->{'tree'}) . "\n"; push(@children,\$child_a); \$children_size++; } } \$generation++; @population = @children; } } }