Genetic Algorithms

a.k.a. Playing God...ehrm...Darwin


Jan Monschke

@thedeftone

github.com/janmonschke

made with reveal.js <3

What's it about?

A problem-solving technique that works like natural evolution. Literally!

Biologist B-Bingo:

  • Population
  • Genetic Drift
  • Mutation
  • Genome
  • Survival of the fittest

http://forgif.me/system/image/1866/image.gif

How biologists see it

Srsly, it's not as complicated as it sounds

Example: Travelling Salesman Problem

It fits great for a GA-example because it's a NP-hard problem!

A salesman has to find the shortest way that connects a set of cities. The salesman is only allowed to visit each city once. It doesn't matter where the salesman starts. In the end, the salesman has to return to the starting point again.

In other words

http://imgs.xkcd.com/comics/travelling_salesman_problem.png

Genetic Algorithm Skeleton

  1. Generate a random population of genomes
  2. Rank the genomes according to their fitness
  3. Select / Mate / Mutate population
  4. repeatFrom(2) unless solution.isGood()

Let's dive into the code

1) Random Population

class Population
  genomes: []

  constructor: (@populationSize, @maxGenerationCount) ->
    @genomes.push new Genome() for i in [0...@populationSize]

class Genome
  values: []

  constructor: (@values = @initial()) ->

  initial: ->
    # cities represented as numbers from 0-14
    # [0,3,4] means the route 0 -> 3 -> 4 -> 0
    return [RANDOMARRAY FROM [0-14]]
            

var Genome, Population;

Population = (function() {
  Population.prototype.genomes = [];
})();

Genome = (function() {

  Genome.prototype.values = [];

  function Genome(values) {
    this.values = values != null ? values : this.initial();
  }

  Genome.prototype.inital = function(){
    return [RANDOMARRAY FROM [0-14]]
  }
})();
					 

Ranking

Which solutions are good?

  1. A Genome's fitness is needed to compare them
  2. Fitness as in: "How close to the goal am I?"
  3. In our case: Fitness = Sum of all paths
  4. Since in our case a lower fitness means, a solution is better, we'll call it cost

Calculating the cost and ranking


class Genome
  cost: ->
    cost = 0
    for city, index in @values
      # A,B,C: A->B
      if index+1 < @values.length
        cost += distances[city][@values[index+1]]
      else
        # A,B,C: C->A
        cost += distances[city][@values[0]]
    cost

class Population
  rank: ->
    @genomes = _.sortBy @genomes, (genome) -> genome.cost()
            

Genome.prototype.cost = function() {
  var city, cost, index, _i, _len, _ref;
  cost = 0;
  _ref = this.values;
  for (index = _i = 0, _len = _ref.length; _i < _len; index = ++_i) {
    city = _ref[index];
    if (index + 1 < this.values.length) {
      cost += distances[city][this.values[index + 1]];
    } else {
      cost += distances[city][this.values[0]];
    }
  }
  return cost;
};

Population.prototype.rank = function() {
  return this.genomes = _.sortBy(this.genomes, function(genome) {
    return genome.cost();
  });
};
           

Wrap-up

What do we have now?

  1. Genomes with random arrays
  2. We can calculate a cost from that
  3. The Population is sorted
  4. The fun ist just about to come ;)

A tale about birds and bees

http://static.fjcdn.com/pictures/Birds+and+Bees_028d03_3949321.jpg

The Next Generation

  1. Select two Genomes
  2. We're scientists, so we skip all the family and relationship stuff
  3. Create two offsprings via crossover
  4. Mutate these two offsprings
  5. Add them to the next generation

Selection

The method of selectioning depends heavily on the problem. Find it out by trial & error.

  1. Simple Selection -> Select neighbor Genome
  2. Tournament Selection -> Select x random Genomes and pick the best of them
  3. Roulette Selection -> Chance of being picked depends on fitness (the fitter-> higher chance)

Why don't we just select the best solutions?

It is important to keep variety in the population or otherwise we may not find the optimal solution. (aka a local maximum)

http://betterceo.com/wp-content/uploads/2011/09/Local-Maximum0021.png

Tournament selection


class Population
  tournamentSelect: ->
    participants = []
    # select random participants
    for index in [0..@tournamentParticipants]
      randomIndex = Math.floor @genomes.length * Math.random()
      participants.push @genomes[randomIndex]
    # rank participants
    participants = _.sortBy participants, (genome)->genome.cost()
    participants[0]
            

Population.prototype.tournamentSelect = function() {
  var index, participants, randomIndex, _i, _ref;
  participants = [];
  for (index = _i = 0, _ref = this.tournamentParticipants; 0 <= _ref ? _i <= _ref : _i >= _ref; index = 0 <= _ref ? ++_i : --_i) {
    randomIndex = Math.floor(this.genomes.length * Math.random());
    participants.push(this.genomes[randomIndex]);
  }
  participants = _.sortBy(participants, function(genome) {
    return genome.cost();
  });
  return participants[0];
};
           

Crossover

Not so sexy at all

http://www.tc.bham.ac.uk/~roy/Images/crossover.gif

Crossover

  1. Not so easy for the TSP
  2. Genomes can easily become invalid by slicing
  3. Needs extra validation
  4. There are papers on it

Mutation

Needed to keep variety (we talked about it ;))

http://upload.wikimedia.org/wikipedia/commons/thumb/e/e9/Goldfish3.jpg/300px-Goldfish3.jpg

It turns this into...

Mutation

...this...

http://cubcarson.files.wordpress.com/2011/04/simpsons-fish.jpg?w=343

Mutation

...by doing this:

[1,3,2,0]
genome.mutate()
[2,3,1,0]

Le mutation code


Class Genome
  mutate: ->
    indexA = @getRandomIndex @values
    indexB = @getRandomIndex @values
    buff = @values[indexA]
    @values[indexA] = @values[indexB]
    @values[indexB] = buff
            

Genome.prototype.mutate = function() {
  var buff, indexA, indexB;
  indexA = this.getRandomIndex(this.values);
  indexB = this.getRandomIndex(this.values);
  buff = this.values[indexA];
  this.values[indexA] = this.values[indexB];
  return this.values[indexB] = buff;
};
           

Elitism

The x best Genomes are directly transferred to the next generation.

http://i3.kym-cdn.com/entries/icons/original/000/006/550/feel-like-a-sir-template.jpg

Next Generation Code


for index in [0...@genomes.length-skip] by 2
  # Perform a tournament selection
  a = @tournamentSelect()
  b = @tournamentSelect()

  # perform a crossover
  children = a.crossover b, @mixingRatio
  a = children[0]
  b = children[1]

  # mutate the genomes
  a.mutate() if Math.random() < @mutationChance
  b.mutate() if Math.random() < @mutationChance

  # add the new genomes to the next generation
  nextGeneration.push a
  nextGeneration.push b
        

Next Generation Code


for (index = _i = 0, _ref = this.genomes.length - skip; _i < _ref; index = _i += 2) {
  a = this.tournamentSelect();
  b = this.tournamentSelect();

  children = a.crossover(b, this.mixingRatio);
  a = children[0];
  b = children[1];
  if (Math.random() < this.mutationChance) {
    a.mutate();
  }
  if (Math.random() < this.mutationChance) {
    b.mutate();
  }
  nextGeneration.push(a);
  nextGeneration.push(b);
}
        

When does it stop?

Again, this highly depends on the problem

  1. After a max number of generations
  2. When a certain goal has been reached
  3. When the best solution hasn't changed in x generations

Demo time

Click me for a demo

What is it useful for?

thanks

http://picsfunnypics.com/images/funny13.jpg

Questions?

Further Readings