The Genetic Algorithm - Explained

Paradigm of Evolution

Every organism contains an array of traits - called DNA, when 2 parents mate they produce a child containing a mixture of their DNA. Depending on how well those traits work together to help the child survive so that he may reproduce, will determine if those traits will pass into future generation. Rarely a random trait enters a child's DNA that was not inherited from the parents, we call this mutation. If the mutation is beneficial, the organism will survive long enough to carry the mutation over to future generations. So the cycle continues, after many generations we continue to optimize the population by "mixing and matching", "trial and error" of  DNA.

Introduction

Genetic Algorithms are used to find optimal solution by method of evolution-inspired search and optimization; Generally used in problems where linear/brute-force searches are not viable in terms of time, such as – Travelling Salesman Problem, Timetable Scheduling, Finding Neural Network Weights, Sudoku, Trees(data-structure) etc..  The first requirement is an encoding scheme suitable for representing individuals, second requirement being a evaluation function for representing the fitness of an individual.

Encoding Scheme

DNA of an individual is represented by an array. Bit-arrays being the most dynamic. Here are a few encoding scheme examples :

Notes: Research indicates Gray Coding being more efficient in terms of binary encoding. Trees can be array encoded, will add graphic shortly.

The Genetic Process

Below is a flow diagram of the Genetic Algorithm, we will be doing a step by step walk-through of this process.

Step 1 : Initialize the Population

The population is initialized by randomly generating a collection of DNA samples. The size of the population depends on the size of the problems search space, and the computational time it takes to evaluate each individual. Most of the time you will be dealing in population counts of about 50 up-to a 1000.

Type DNA = Array of Boolean
Block InitializePopulation() Returns Population
  NewPopulation is array of DNA;
  Loop i=0 to PopulationCount
    Population[i]=GenerateRandomDNA();
  EndLoop
  return Population;
EndBlock

Block GenerateRandomDNA() Returns DNA
  Variable NewDNA is DNA
  Loop i=0 to LengthOf(NewDNA)
    NewDNA[i]=GetRandomBooleanValue;
  EndLoop
  Return newDNA;
EndBlock

Step 2: Evaluate Chromosomes

The evaluation function determines the fitness of an individual. This is the most important part to the Genetic algorithm, if this function is flawed, the algorithm will not produce results. The evaluation function should not return a Boolean(true/false) value, it has to be a comparable result. If individuals are able to be sorted from fittest to weakest, it is a viable evaluation function. For evaluating distances between cities you may return the total distance traveled as a fitness score. For a classifier you can return the number of correct classifications. You could use probability as a score assignment, of how likely an individual is a solution.

Step 3: Select Fittest Individual(s)

Selection is where we will be choosing the parents for mating. Selection happens for each child in the new population. There are three type of parent selection methods, Fitness Proportionate Selection, Tournament Selection, and Truncation Selection. A viable option is to carry over selected individuals to the next generation.

Fitness Proportionate Selection: Also known as Roulette wheel selection, is a method of selecting individuals based on its probability of being selected. Sort the population from weakest to fittest, generate a random number within the range of the sum of the populations fitness, iterating through the sorted population, summing each individuals score up until it either equals the random number, or is greater than the random number. That individual is then selected as a parent. This method can take a long time to produce results and is used for maximizing a function.

Block GetSumOfPopulationFitness(Population is ListOfDNA) Returns Integer
  Variable FitnessSum is Integer = 0;
  Loop i=0 to Population.Count
    FitnessSum = FitnessSum + Population[i].Fitness;
  NextLoop
  return FitnessSum;
EndBlock

Block FitnessSelection(Population is ListOfDNA) Returns PopulationIndex
  Variable SortedPopulation is Population;
  Variable RandomNumber is Integer;
  Variable FitnessSum is Integer;
  Variable Sum is Integer;
  SortedPopulation = Population.Sort(Ascending);
  FitnessSum=GetSumOfPopulationFitness;
  RandomNumber=Random(0...FitnessSum);
  Loop i=0 to SortedPopulation.Count
    Sum = Sum + SortedPopulation[i].Fitness;
    If (Sum >= RandomNumber) Then
  Return i; // Will end Loop as well
  NextLoop
EndBlock

Tournament Selection: Selecting the top performer to carry over to the next generation, and to mate with the rest of the population.

Truncation Selection: Choose a percentage of fittest individuals to mate with the population or amongst each other. Carrying over selected individuals is optional.

Crossover Selected DNA

Once you have your selected individual(s) also known as the parents, we need to mix and match their DNA to produce a new population of children. We call this process Crossover. When using fitness proportionate Selection, you will select a new parent for every individual in the population. Tournament Selection, You mate the selected parent with every individual in the population. Truncation selection, you could randomly select from the winning group, or use fitness proportionate selection on the winning list to mate with every individual in the population. There are 3 ways to crossover two DNA arrays. 1 point crossover, 2 point crossover, random crossover.

Mutate population

Mutation allows the algorithm to introduce diversity into the population, expanding the opportunity to search unexplored areas in the search space for fitter solutions. Mutation is implemented by giving each element in the DNA array a probability of 2-5% of being randomly altered. The mutation procedure is called for every child.

Block MutateDNA(paramDNA is DNA) Returns DNA
  Variable MutatedDNA is array of boolean
  Loop i=0 to LengthOf(paramDNA)
    If (Random(0..100) > 98) then
      MutatedDNA[i]=GetRandomBoolean;
    else
      MutatedDNA[i]=paramDNA[i];
  NextLoop
  Return mutatedDNA;
EndBlock

What Next?

After the generating a new generation, we go back to the evaluation step.

When to Stop

After the Evaluation step, we can either stop; from finding the most optimal solution, generation is not progressing(evolving) in fitness, or where time is a factor.

Note: Example algorithm is on its way. This is only a draft, and will be improved.

Thank you for Reading, Comments welcome.
Joseph Armstrong