GeneLisa - A Genetic Approach to Recreate a MasterPiece ~ Prabod's Blog

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.

See a Demo

Pseudocode of GA

[Start] Generate random population of n chromosomes (suitable solutions for the problem)
[Fitness] Evaluate the fitness f(x) of each chromosome x in the population
[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
[Replace] Use new generated population for a further run of algorithm
[Test] If the end condition is satisfied, stop, and return the best solution in current population
[Loop] Go to step 2

Encoding of Chromosome

There are 4 ways to encode a chromosome

Binary Encoding
Permutation Encoding
Value Encoding
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 raw randomPopulation.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 raw fitness.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 raw selection.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 raw crossover.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