# 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 ### 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.

## 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 [[email protected]]

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]
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];
}
}
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 ## 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) ## Tournament selection

``````
class Population
tournamentSelect: ->
participants = []
# select random participants
for index in [[email protected]]
randomIndex = Math.floor @genomes.length * Math.random()
participants.push @genomes[randomIndex]
# rank participants
participants = _.sortBy participants, (genome)->genome.cost()
participants
``````
``````
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;
};
``````

## Crossover

Not so sexy at all ## 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 ;)) It turns this into...

## Mutation

...this... ## 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. ## Next Generation Code

``````
for index in [[email protected]] by 2
# Perform a tournament selection
a = @tournamentSelect()
b = @tournamentSelect()

# perform a crossover
children = a.crossover b, @mixingRatio
a = children
b = children

# 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;
b = children;
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

## thanks Questions?