Genetic Algorithms

This week I will be explaining what are genetic algorithms, how they work and what role they play in the world. It is pretty interesting stuff so I highly recommend sticking around to find out more.

What are Genetic Algorithms?

Genetic algorithms are a form of guided random search techniques which is part of the evolutionary branch. These algorithms use genes that contain chromosomes in which these genes are allowed to evolve to find the best solution.

Not these kinds of jeans (source: http://atrending.net/)

Natural Selection

Let’s have a look at the concepts for natural selection.

In the environment that we are building, resources and limited and so each of our agents/organisms/genes will be struggling for their own existence. This is determined by, our famous friend by now, the fitness function. This will determine how successful the particular gene is able to adapt to it’s environment. If the gene is successful and has a good fitness rating then, depending on implementation, that gene is more likely to be selected to pass on their genes to the next generation.

When looking at the method of how natural selection works, some may be thinking that this sounds like ‘survival of the fittest’, and they are right! We are trying to find the best genes to find the best solution, but there must be variance otherwise we might end up in a local minimum.

When should this be used?

These types of techniques should only be used for specifically nasty problems. These problems typically include a search space that is too large in which taking a parallel approach makes the most amount if sense.

Let’s talk about genes

In a program that uses genetic algorithms, there are many many genes used to find a solution to a problem. These genes contain chromosomes which have a small amount of data with them.

The chromosomes within the genes can be any of the following:

  • Bit strings
  • Real numbers
  • Lists of rules
  • Really, they can be any data structure

How do these algorithms work?

There are two core functions for which these algorithms function: mutate and crossover. They both vary in method and show different aspects of genetic algorithms.

These functions work differently is the order of the data in the chromosome matters. If the order doesn’t matter then items can be swapped, shifted, flipped and incremented at any point in the chromosome. If the order does matter then the data chromosome, when being mutated or crossed over, will have a slightly different method.

Mutation

Let’s start with mutation.

Mutation happens upon an individual gene and can be applied at a particular position in the chromosome. This can either be bit flipping at that position or swapping two random positions in the chromosome. Mutation can be seen as the adaptation of a particular gene.

Example – Bit flipping (Order doesn’t matter)
We have a set of bits:
001000

One of these positions are then randomly chosen:
0010[0]0

And the bit is flipped:
0010[1]0

Leaving us with a mutated chromosome:
001010

Example – Position Swapping (Order matters)
We have a set of integers:
123456

Two of these positions are then randomly chosen:
12[3]4[5]6

And these numbers are swapped:
12[5]4[3]6

Leaving us with a mutated chromosome:
125436

Crossover

Crossovers are essentially the breeding part of this so that the two genes can share their chromosomes to create new genes. This method is best used when sharing chromosomes of the fittest genes so better solutions can be found.

You can find you are able to have many different points of crossover but the ones I’ll be talking about today will be single and double point crossover.

Single Point Crossover Example
We will start with 2 different genes and their chromosomes:
(P1) 012345 (P2) 543210

A random point is selected to split the chromosomes into two:
random_point = 3
(P1) 0123|45 (P2) 5432|10

The genes then share parts of their chromosomes from the partition to their children:
(P1) (0123)|(45) (P2) [5432]|[10]
(C1) (0123)|[10] (C2) [5432]|(45)

And now we have two new chromosomes:
(P1) 012345 (P2) 543210
(C1) 012310 (C2) 543245

Double Point Crossover Example
We will start with 2 different genes and their chromosomes:
(P1) 012345 (P2) 543210

A random point is selected to split the chromosomes into two:
random_points = 1,3
(P1) 01|23|45 (P2) 54|32|10

The genes then share parts of their chromosomes that are within the partition to their children:
(P1) (01)|(23)|(45) (P2) [54]|[32]|[10]
(C1) (01)|[32]|(45) (C2) [54]|(23)|[10]

And now we have two new chromosomes:
(P1) 012345 (P2) 543210
(C1) 013245 (C2) 542310

Just like mutation, crossover have a couple of different variations and are affected by order. If you would like to see how single and double crossover work when order matter, then take a look at my implementation of genetic algorithms below.

Are there any applications for this?

Genetic algorithms have been used in several areas within industry, but the main ones are:

  • Optimisation
  • Timetabling
  • Pattern Recognition
  • Routing

My Implementation

Download my implementation

Source

  1. Jeans image source
Share this post:
RSS
Follow by Email
Facebook
Google+
http://mattrclark.com/2016/11/genetic-algorithms/
YouTube31
YouTube
LinkedIn

2 thoughts on “Genetic Algorithms

Leave a Reply

Your email address will not be published. Required fields are marked *