Xavier Nayrac

Rubyiste accro au TDD, serial blogger, apprenti data scientist, heureux utilisateur de Vim, accordéoniste.
Si vous vous sentez particulièrement généreux, suivez moi sur Twitter.

Les algorithmes génétiques démystifiés 11

| Comments

Niveau : intermédiaire

La dernière fois on a assuré la sélection à l’aide d’une piscine d’accouplement (je ne me lasse pas de ce terme…). Aujourd’hui, on peut aller au bout de l’algorithme en ajoutant la reproduction.

La reproduction des phrases

Il n’y a rien de nouveau par rapport à l’algorithme précédent, c’est peut-être même plus simple. Voici la méthode crossover, qui permet d’obtenir un enfant:

1
2
3
4
5
def crossover(parent1, parent2)
  point = rand(1..(@search_value.size - 1))
  child = parent1.last[0...point] + parent2.last[point..-1]
  [nil, mutate(child)]
end

Edit du 14 sept 2013 Le code ci-dessus contient une erreur, à la seconde ligne il faut lire: point = rand(1..@search_value.size).

crossover prends deux chromosomes en entrée (les parents). On définit un point de croisement au hasard. On utilise ce point de croisement pour couper les parents en deux parties. Un enfant est produit en concaténant la première partie du premier parent avec la seconde partie du second parent. Enfin on renvoie un chromosome, après avoir passer l’enfant/phrase à la mutation. Voici justement la méthode chargée de la mutation:

1
2
3
4
5
6
def mutate(phrase)
  @search_value.size.times do |index|
    phrase[index] = random_gene if rand < @mutation_rate
  end
  phrase
end

La différence avec l’algorithme précédent est que cette fois chaque gène peut muter. Avantage: on est plus proche du phénomène naturel et on pourrait se retrouver avec un chromosome dont 2 ou 3 gènes sont mutants, ça semble bon pour la diversité génétique. Inconvénient: Générer un nombre aléatoire pour chaque gène peut faire tomber les performances si on a un millier de gènes (ou plus) par chromosome et/ou une population importante. Comme je dis d’habitude: «Si c’est de l’informatique, c’est une histoire de compromis».

On peut maintenant créer une méthode next_generation qui englobe la sélection et la reproduction:

1
2
3
4
5
6
7
8
9
10
def next_generation
  mating_pool = create_mating_pool
  pool_size = mating_pool.size
  @population = []
  @population_size.times do
    parent1 = mating_pool[rand(pool_size)]
    parent2 = mating_pool[rand(pool_size)]
    @population << crossover(parent1, parent2)
  end
end

Je ne vais pas vous faire l’affront d’expliquer cette méthode, vous avez toutes les cartes en main pour la comprendre. Sinon, c’est que j’ai mal fait mon boulot…

Il reste à mettre tout ça ensemble, voici le code complet du programme:

monkey.rb
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
def make_chromosome
  value = ""
  length = @search_value.size
  length.times { value += random_gene }
  [nil, value]
end

def random_gene
  @genes[rand(@genes.size)]
end

def make_population
  population = []
  @population_size.times { population << make_chromosome }
  population
end

def score_population
  evaluate_population
  normalize_population_score
end

def evaluate_population
  @population.map! {|person| [evaluate(person.last), person.last] }
end

def evaluate(phrase)
  score = 0
  phrase.split('').each_with_index do |character, index|
    score += 1 if @search_value[index] == character
  end
  score
end

def normalize_population_score
  total = @population.inject(0) {|sum, person| sum + person.first }
  @population.map! {|person| [person.first.to_f / total * 100, person.last] }
end

def next_generation
  mating_pool = create_mating_pool
  pool_size = mating_pool.size
  @population = []
  @population_size.times do
    parent1 = mating_pool[rand(pool_size)]
    parent2 = mating_pool[rand(pool_size)]
    @population << crossover(parent1, parent2)
  end
end

def create_mating_pool
  mating_pool = []
  @population.each do |person|
    person.first.to_i.times { mating_pool << person }
  end
  mating_pool
end

def crossover(parent1, parent2)
  point = rand(1..@search_value.size)
  child = parent1.last[0...point] + parent2.last[point..-1]
  [nil, mutate(child)]
end

def mutate(phrase)
  @search_value.size.times do |index|
    phrase[index] = random_gene if rand < @mutation_rate
  end
  phrase
end

def solution_found
  found = false
  @population.each do |person|
    found = true if person.last == @search_value
  end
  found
end

@search_value = "Mon royaume pour un cheval"
@genes = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ "
@population_size = 100
@mutation_rate = 0.01
@population = make_population

1000.times do |generation|
  score_population
  puts "Generation: #{generation}"
  @population.each {|i| puts i.inspect }
  exit if solution_found
  next_generation
end

Et voilà le résultat:

[~/genetic]⇒ ruby monkey.rb 
...
Generation: 869
[1.0092854259184496, "Mon royaume pour un chevaB"]
[1.0092854259184496, "Mon royaume pour un chevan"]
[1.0092854259184496, "Mon royaume pour un chevaB"]
...
[1.0496568429551878, "Mon royaume pour un cheval"]
...
[1.0092854259184496, "Mon royaume pour un chevan"]
[1.0092854259184496, "Mon royaume pour un chevaB"]
[0.9689140088817118, "Mon royaume pour un chNvaB"]

La prochaine fois on va améliorer notre méthode de sélection pour tenir compte des chiffres après la virgule.

À demain.

Articles connexes

Commentaires