## GeneLisa - A Genetic Approach to Recreate a MasterPiece According to MathWorks.com Genetic Algorithm is defined as
A genetic algorithm (GA) is a method for solving both constrained and unconstrained optimization problems based on a natural selection process that mimics biological evolution. The algorithm repeatedly modifies a population of individual solutions. At each step, the genetic algorithm randomly selects individuals from the current population and uses them as parents to produce the children for the next generation. Over successive generations, the population "evolves" toward an optimal solution.

When I was surfing through the Internet,I came across Roger Johansson's blog. He did this amazing thing with genetic algorithms. He recreated a masterpiece drawing from using just 50 polygons. You can read about it by going to the link provided.
I wanted to play around with Genetic Algorithms from a long time. I decided to do a Javascript Implementation of this concept.I was able to do it to some extent.I will guide you through the code.

#### Pseudocode of GA

1. [Start] Generate random population of n chromosomes (suitable solutions for the problem)
2. [Fitness] Evaluate the fitness f(x) of each chromosome x in the population
3. [New population] Create a new population by repeating following steps until the new population is complete
1. [Selection] Select two parent chromosomes from a population according to their fitness (the better fitness, the bigger chance to be selected)
2. [Crossover] With a crossover probability crossover the parents to form a new offspring (children). If no crossover was performed, offspring is an exact copy of parents.
3. [Mutation] With a mutation probability mutate new offspring at each locus (position in chromosome).
4. [Accepting] Place new offspring in a new population
4. [Replace] Use new generated population for a further run of algorithm
5. [Test] If the end condition is satisfied, stop, and return the best solution in current population
6. [Loop] Go to step 2

#### Encoding of Chromosome

There are 4 ways to encode a chromosome
1. Binary Encoding
2. Permutation Encoding
3. Value Encoding
4. Tree Encoding
I have used value encoding to encode this chromosome.
CHROMOSOME = [RED, GREEN, BLUE, ALPHA , X1, Y1, X2, Y2, ...]
With this Chromosome we generate a random population for the initial Generation
 /** * Generate random DNA for the Initial Generation * Value Encoding is used for DNA encoding * DNA = [RED, GREEN, BLUE, ALPHA, X1, Y1, X2, Y2, ...] * */ randomGenes(){ var bString = []; for (var i = 0; i < this.chromoSize; i+= this.geneSize){ /** * Generate RGBA * */ bString.push( Math.random(), // R Math.random(), // G Math.random(), // B Math.max(Math.random() * Math.random(), 0.2) //A ); /** * Generate random (x,y) for vertices * */ var X = Math.random(); var Y = Math.random(); for (var j = 0; j < this.vertices ; j++){ bString.push( X + Math.random() - 0.5, Y + Math.random() - 0.5 ); } } this.valueString = bString; }
view rawrandomPopulation.js hosted with ❤ by GitHub

#### Fitness Function

Fitness Function is the most important part of a Genetic Algorithm. Success of your whole algorithm is based on this function.
For this specific occasion I have defined my fitness function
as follows
FITNESS = 1 - (Square of pixel difference between chromosome and reference Image)/( Resolution of the Image * count(RGBA) * Number of Possible Values)
 /** * Fitness Function * fitness = 1 - (Square of pixel difference between chromosome and reference Image) * ____________________________________________________________________ * ( Resolution of the Image * count(RGBA) * Number of Possible Values) * * This fitness function stays inside [0,1] * */ fitness(width,height){ //Draw the Chromosome First this.draw(this.ctx,width,height); var fit = 0; var imagedata = this.ctx.getImageData(0,0,width,height).data; for (var i = 0; i < workingData.length;i++){ var dist = workingData[i] - imagedata[i]; fit += dist * dist; } this.fitnessValue = 1 - fit / (75 * 75 * 4 * 256 * 256); return this.fitnessValue; } }
view rawfitness.js hosted with ❤ by GitHub

#### Breed New Generation

##### Selection
I have used a greedy approach to fasten up the process. Usually selection is done through Roulette Wheel selection.
Here I select a percentage with the best fitness then breed them with randomly selected chromosomes from the population.
 /** * Breed a New Generation of Chromosomes * */ function breed() { var totalFitness = 0; var fittest; var fit=0; /** * Calculate fitness of each and every chromosome * */ for(var j = 0 ; j < population.length ; j++){ var temp = population[j].fitness(75,75,goal); if (temp >= fit){ fit = temp; fittest = population[j];// Fittest Chromosome in a Generation } totalFitness += temp; } /** * Sort the Generation * */ population = population.sort(function(a, b) { return b.fitnessValue - a.fitnessValue; }); var newPopulation = []; /** * Select the Chromosomes with best fitnesses * */ var selectCount = Math.floor(population.length * CROSSOVER_RATE); /** * Number of Chromosomes that needed to be crossed with the each of the Chosen Chromosome * */ var randCount = Math.ceil(1 / CROSSOVER_RATE); /** * Select two parents and breed * */ for (var i = 0; i < selectCount; i++) { for (var h = 0; h < randCount; h++) { var parent = i; while (parent == i) { parent = (Math.random() * selectCount) >> 0; } /** * Breed * */ var crossed = crossover(population[i], population[parent], CROSSOVER_RATE, GENE_SIZE, CHROME_SIZE); newPopulation.push(crossed); } } }
view rawselection.js hosted with ❤ by GitHub
##### Crossover
When two chromosomes passed to the crossover function, it evenly choose one parent to inherit from. Then if mutation is possible, mutate and creates the new Child.
 /** * Cross two Chromosomes and produce a child Chromosome * */ function crossover(chromosome1,chromosome2,rate,geneSize,chromoSize) { var rand = Math.random(); // Random value for check crossover chance if (rand < rate){ var vString = []; for (var i =0; i< chromoSize; i += geneSize){ for(var j = 0; j < geneSize; j++){ /** * Evenly Choose a Parent for breeding*/ var inheritedGene = (Math.random() < 0.5) ? chromosome1 : chromosome2; var dna = inheritedGene.valueString[i+j]; var randnum = Math.random(); // Random Number for Mutation chance if (randnum < MUTATION_RATE){ /** * Mutate by some Amount*/ dna += Math.random() * MUTATE_AMOUNT * 2 - MUTATE_AMOUNT; } if (dna < 0) dna = 0; if (dna > 1) dna = 1; vString.push(dna); } } return new Chromosome(vString,geneSize,chromoSize); } /** * If No chance for crossover. Return one of the parent Chromosome*/ return (Math.random() < 0.5) ? chromosome1 : chromosome2; }
view rawcrossover.js hosted with ❤ by GitHub
Likewise when the whole process generated the same amount that a population have, that new population replaces the old population and continue till the condition satisfies
##### Some of the results from my simulation                 Reference Image 