#!/usr/bin/env perl # Brief and dirty attempt to solve a system of simultaneous equations (2) # using Genetic Algorithms in particular CPAN module # Algorithm::Evolutionary # Perl module for performing paradigm-free evolutionary algorithms # by J. J. Merelo, jmerelo (at) geneura.ugr.es # (parts of my program were copied from manpage) # # The toy problem here is to find INTEGER solutions to the system of equations y-x=2 and y-2x=11 # wrt x and y. # Our 2 genes are 'x' and 'y'. We encode these as 8-bit integers # 7+1sign bit. The algorithm will mutate/crossover etc the bit string of each member of # the population. Then it will evaluate how well the genes of each member of the population # solve the problem at hand. This is called the fitness. The fittest genes survive and the # rest are discarded, with some probability. # Author: bliako # Date: 16/04/2018 use strict; use warnings; use Algorithm::Evolutionary::Experiment; use Algorithm::Evolutionary::Op::Easy; use Algorithm::Evolutionary::Op::Bitflip; use Algorithm::Evolutionary::Op::Crossover; my \$num_genes = 2; my \$fitness = sub { my \$individual = shift; my \$genes = chromosome2genes(\$individual->Chrom()); return calculate_discrepancy(\$genes); }; my \$m = Algorithm::Evolutionary::Op::Bitflip->new(2); # flip this number of bits randomly my \$c = Algorithm::Evolutionary::Op::Crossover->new(2); # crossover with 2 points # every iteration applies the above operations to the population along with a fitness function # and selection rate (prob of good genes to survive, lower means more "bad" genes enter the next generation) my \$ez = new Algorithm::Evolutionary::Op::Easy \$fitness, 0.4, [\$m,\$c]; my \$popSize = 500; # population size, each individual in this pop has a chromosome which consists of 2 genes my \$indiType = 'BitString'; # the chromosome is a sequence of bits as a string my \$indiSize = 8*\$num_genes; # 8 bits per gene my \$e = new Algorithm::Evolutionary::Experiment \$popSize, \$indiType, \$indiSize, \$ez; my \$populationRef; my \$previous_fitness = 0; my (\$current_fitness, \$best); while(1){ \$populationRef = \$e->go(); \$best = \$populationRef->[0]; print "Best so far: ", \$best->asString(), " (", individual2string(\$best),")\n"; \$current_fitness = \$best->Fitness(); if( \$current_fitness == 0 ){ print "bingo!\n"; last } #if( (\$previous_fitness - \$current_fitness) == 0 ){ last } \$previous_fitness = \$current_fitness; } print "\nI tried to solve the system of equations: y-x=2 and y-2x=11. The solution should be x=3, y=5\n"; print "Final solution found: ".individual2string(\$best)."\n"; exit(0); sub individual2string { my \$individual = \$_[0]; my \$genes = chromosome2genes(\$individual->Chrom()); my \$fit = calculate_discrepancy(\$genes); return genes2string(\$genes) . " -> discrepancy=" . \$fit } # interpret an array of genes wrt our problem, i.e. an x and a y sub genes2string { my \$genes = \$_[0]; return "x=".\$genes->[0].", y=".\$genes->[1]; } # convert a huge bit string into an array of genes # the array to place the genes in is given sub chromosome2genes { my \$achromosome = \$_[0]; # chromosome bit string containing all genes as 10101 my @retgenes = (0)x\$num_genes; # convert a chromosome which consists of genes which consist of bits(alleles) # into a set of numbers to be applied to our problem. # each chromosome below consists of 2 genes which consist of 8 bits (1sign+7) # these 8bits are interpreted as integers in +-127 range (which is enough for our problem # however if solution involved bigger numbers we need to increase range/bits) my \$i=0; while( \$achromosome =~ /([01])([01]{7})/g ){ my \$sig = \$1 eq '1' ? -1 : 1; my \$g2 = \$2; # Here is how a sequence of 8bits is converted to integers. 1st bit is sign. # I am sure there is a better way using pack. my \$g = 0; my \$j = 1; map { \$g += \$_*\$j; \$j*=2; } split(//, \$g2); \$g *= \$sig; \$retgenes[\$i++] = \$g; #print "\$g2->num=\$g\n"; } return \@retgenes } sub calculate_discrepancy { my \$genes = \$_[0]; # Our problem is to solve the simultaneous equation: y-x=2 and y-2x=11 # where genes[0] -> y, genes[1]->x my \$e1 = \$genes->[0] - \$genes->[1] - 2; my \$e2 = \$genes->[0] + 2*\$genes->[1] - 11; # we calculate discrepancy but we need to return fitness: return -(\$e1*\$e1 + \$e2*\$e2); }