Jan Monschke

made with reveal.js <3

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

Biologist B-Bingo:

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

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.

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

```
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]]
}
})();
```

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

```
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();
});
};
```

- Genomes with random arrays
- We can calculate a cost from that
- The Population is sorted
- The fun ist just about to come ;)

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

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

- Simple Selection -> Select neighbor Genome
- Tournament Selection -> Select x random Genomes and pick the best of them
- 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)

```
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];
};
```

Not so sexy at all

- Not so easy for the TSP
- Genomes can easily become invalid by slicing
- Needs extra validation
- There are papers on it

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

It turns this into...

...this...

...by doing this:

`[1,3,2,0]`

`genome.mutate()`

`[2,3,1,0]`

```
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;
};
```

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

```
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
```

```
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);
}
```

Again, this highly depends on the problem

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

- Finding the optimal mix of parameters for an algorithm
- Find the most efficient structure for a chair
- Timetabling / Scheduling

Questions?