Depuis que j'ai découvert les algorithmes génétiques, je tombe régulièrement sur de courtes vidéos montrant leurs résultats dans des jeux vidéos. Dans cet article, j'ai voulu essayer de construire, étape par étape, un outil capable de faire la même chose. Il s'agit donc d'une expérimentation qui a pour but de découvrir le sujet, et non d'un projet finalisé et optimisé. Bonne lecture !
Un développeur pour les gouverner tous
Vous avez la flemme de passer des heures à vous entraîner sur des jeux vidéo pour éclater les scores de vos meilleurs potes ? Mais vous ne voulez pas non plus les laisser se vanter de leur nouveaux records sans pouvoir faire mieux qu'eux... J'ai peut être une solution pour vous !
Que diriez-vous de simuler une armée de dizaines de simulations de joueurs qui s'entraîneront à votre place, sans que vous n'ayez rien à faire, jusqu'à devenir capable de compléter les plus mythiques des jeux rétros ?
Certes, cette proposition peut vous paraître étrange, mais laissez-moi vous guider dans ce voyage au cœur des algorithmes génétiques.
Nul besoin d'être un expert pour venir à bout de quelques bons jeux rétros, il suffit simplement d'avoir les bons outils. Alors lancez votre environnement préféré, et laissez vous guider tout au long de l'article.
Au revoir Steam, ici c'est le retour d'Atari
Avant toute chose, il nous faut un jeu... Vous en avez sûrement déjà bien trop d'installés sur votre ordinateur, mais pour commencer, mieux vaut avoir un jeu avec lequel on peut facilement interagir avec notre langage favori (ici, le python). C'est ici que l'on va faire appel à un allié de taille : Gym !
Il s'agit d'un toolkit, proposé par openAI, qui permet d'accéder à des environnements diverses spécialement prévus pour entraîner des algorithmes qui doivent apprendre eux même à résoudre diverses tâches, tel qu'apprendre à jouer à un jeu.
Gym nous propose notamment une ludotech Atari ! Parfait pour commencer ! Vous pouvez donc ouvrir votre console, lancer votre environnement, et taper
pip install gymLes bases de gym :
Gym va nous donner accès à plein d'environnements et un ensemble d'informations les concernant (le flux d'image, l'état de la RAM de la console simulée, etc.). Il suffit de charger l'environnement souhaité à l'aide de son nom :
import gym
env = gym.make('Enduro-ram-v0')Cet environnement dispose de différentes fonctions qui permettent d'interagir avec :
-
env.reset: Relance une partie et de retourne les informations initiales du jeu, -
env.step: Lance l'étape suivante de la partie en cours et retourne les informations liées, -
env.render: Affiche l'état du jeu à l'instant donné, -
env.action_space.sample: Retourne aléatoirement une des actions possibles du jeu.
À partir de ces différentes fonctions, on peut lancer un jeu qui va jouer aléatoirement sur un nombre de cycles choisis :
import gym
env = gym.make('Enduro-ram-v0')
observation = env.reset()
for _ in range(1000):
env.render()
action = env.action_space.sample()
_ = env.step(action)
env.close()env.step retourne en réalité plein d'informations utiles, que nous utiliserons petit à petit au fil de l'article. La première est l'état de la RAM de la console, d'une capacité de 128 bytes, soit 128 entiers compris entre 0 et 255.C'est l'information de base que notre algorithme va utiliser pour déterminer quelle action réaliser au cours du jeu. Mais pour ce faire, commençons par doter notre simulation d'un véritable cerveau !
La recette d'un réseau de neurones
Le cerveau de notre simulation sera un simple réseau de neurones. C'est-à-dire, pour simplifier, un ensemble de neurones regroupés par couches, où chaque neurone est lié à ceux de la couche suivante et précédente par des axes. Sur ces axes on trouve des poids qui vont modifier comment le réseau se comporte.
Des données envoyées à un réseau de neurones vont le “traverser” et seront transformées à l'aide de ses poids afin de nous donner un résultat dont le format dépendra de notre réseau.
Si on change les poids, alors pour les mêmes données, le résultat pourra être différent.
Keras, des réseaux de neurones sans se nouer le cerveaux
Ne fuyez pas ! Si ce n'est pas clair, ce n'est pas grave, dites vous simplement qu'on va donner à un réseau des données (qui seront donc l'état de la RAM de notre jeu) et que le réseau nous retournera un résultat (une action à réaliser). Et pour construire tout ça, pas de prise de tête, on va utiliser la librairie Keras.
La classe suivante construit un simple réseau de neurones avec Keras, en fonction de quelques paramètres simples : les dimensions de nos données, la taille du résultat souhaité, et le nombre de neurones par couches (à l'aide d'une liste).
En plus de ces paramètres, elle dispose de deux méthodes : une pour connaître le nombre de poids de notre réseau et une pour modifier ces mêmes poids.
from keras import Sequential
from keras.layers import Dense
class NeuralNetwork:
def __init__(self, layers_shape: int, input_shape: list, output_shape: int):
if type(layers_shape) is not list:
layers_shape = [layers_shape]
self.model = Sequential()
self.model.add(Dense(layers_shape.pop(), input_dim=input_shape, activation='relu'))
for layer in layers_shape:
self.model.add(Dense(layer, activation='relu'))
self.model.add(Dense(output_shape, activation='softmax'))
def get_number_of_model_param(self):
"""Retourne le nombre de paramètre du modèle"""
return self.model.count_params()
def set_model_param(self, param):
"""Remplace les paramètres du modèle par ceux souhaités"""
index_param = 0
for layer in self.model.layers:
nb_param_layer = layer.count_params()
nb_bias = layer.get_weights()[1].shape[0]
nb_param_layer = nb_param_layer - nb_bias
new_weights = param[index_param:index_param+nb_param_layer].reshape(layer.get_weights()[0].shape)
index_param += nb_param_layer
new_bias = param[index_param:index_param+nb_bias]
layer.set_weights([new_weights, new_bias])
index_param += nb_biasÀ la recherche du cerveau optimal
On dispose à présent d'un cerveau disponible pour jouer, capable, à partir d'une configuration représentée par des poids, de nous donner une action à réaliser en fonction d'un input.
L'objectif va maintenant être de trouver le cerveau optimal pour jouer à notre jeu. Une solution serait de tester un maximum de configurations possibles jusqu'à en trouver les meilleures. Mais il y en a une infinité. Chaque poids peut prendre n'importe quelle valeur numérique, et un simple réseau de neurones représente déjà des milliers de poids.
On va préférer une solution capable d'explorer les configurations possibles, de garder les plus efficaces, et de tenter de les améliorer petit à petit pour maximiser nos performances en répétant l'opération plusieurs fois.
Une telle méthode, on la retrouve déjà dans la nature, il s'agit de la sélection naturelle, et on va s'en inspirer en implémentant un algorithme génétique.
Avant de parler Technique, parlons Biologie
D'après nos cours de biologie, si l'on s'en souvient encore, l'évolution se base sur quelques concepts de base que l'on peut simplifier ainsi :
- Un individu est caractérisé par un ensemble de traits qui peuvent le distinguer des autres (taille, couleur des cheveux, groupe sanguin, ...),
- Ces traits peuvent être transmis à sa descendance lors des reproductions,
- Certains traits sont avantageux pour la survie et augmentent donc les chances de reproduction,
- Un trait avantageux, donc transmis plus souvent car permettant plus de reproduction, va être de plus en plus présent au cours des générations (il est sélectionné),
- L'apparition de nouveaux traits, qu'ils soient avantageux ou non, provient de mutations d'un individu.
À partir de ces trois concepts : la reproduction, la mutation et la sélection, on obtient petit à petit des individus de plus en plus adaptés à un environnement donné.
De la biologie au numérique
Avec les algorithmes génétiques, on va reprendre les trois concepts précédents et les intégrer à notre problématique.
Et pour les utiliser, on va se baser sur un génome (un ADN), qui va permettre de représenter chacun de nos individus. Il nous permettra de gérer :
- Les reproductions : en mixant les génomes de deux individus pour en produire un nouveau,
- Les mutations : en modifiant aléatoirement un génome.
Ce génome doit ensuite permettre de paramétrer un réseau de neurones. Nous allons donc faire au plus simple et utiliser comme génome la liste des poids utilisés par notre réseau de neurones.
Pour la sélection, il nous manque une valeur (appelée fitness) permettant de de savoir si un individu est adapté à son environnement, donc s'il est doué au jeu sélectionné.
Là encore, Gym va nous simplifier la tâche. En effet, la fonction
env.step nous retourne aussi une valeur de récompense sous forme d'un nombre qui permet de juger de l'action effectuée. On pourra se baser sur cette valeur pour sélectionner nos individus.De Darwin à développeur python
Pour représenter ce génome, nous allons utiliser des numpy arrays. Numpy est une librairie python de manipulation d'array, très pratique et compatible avec Keras.
import numpy as npComme pour le réseau de neurones, on va créer une petite classe qui va nous abstraire le fonctionnement de l'algorithme génétique, mais cette fois pas de lib, on va programmer tout ça nous-mêmes !
class Genetics():
def __init__(self,
population_len=30,
population_turnover=15,
genome_len=10000,
mutation_rate=0.1):
"""Constructeur pour notre algorithme génétique
Parameters
----------
population_len : int, optional
taille de la population, 30 par défaut
population_turnover : int, optional
nombre d'individus remplacés lors de la sélection, 15 par défaut
genome_len : int, optional
taille du génome utilisé, 10000 par défaut
mutation_rate : float, optional
probabilité qu'un gène soit modifié lors de l'étape de mutation d'un individu, 0.1 par défaut
"""
self.population_len = population_len
self.genome_len = genome_len
self.mutation_rate = mutation_rate
self.population_turnover = population_turnover
# Initialisation de la population aléatoirement
self.population = np.random.randn(self.population_len, self.genome_len)
# Variables utilisé pour stocker les cinq meilleurs individus et leur score
self.best_five = self.population[:5].copy()
self.best_five_fitness = np.zeros(5)Voilà pour le constructeur, on va maintenant s'attaquer aux différentes méthodes utiles :
La reproduction de la population :
def _reproduce_population(self):
nb_survivor = self.population.shape[0] # Nombre d'individus après sélection
# Sélection aléatoire de couples de parents dans la population
index_first_parent = np.random.choice(nb_survivor, size=nb_survivor, replace=False)
index_second_parent = np.random.choice(nb_survivor, size=nb_survivor, replace=False)
first_parent = self.population[index_first_parent]
second_parent = self.population[index_second_parent]
# Pour chaque couple, on mixe les génomes en les coupant en un point de crossover alétoire
crossover_points = np.random.randint(self.genome_len, size=nb_survivor)
kids = np.zeros((nb_survivor, self.genome_len))
for i in range(nb_survivor):
kids[i, :crossover_points[i]] = first_parent[i, :crossover_points[i]]
kids[i, crossover_points[i]:] = second_parent[i, crossover_points[i]:]
# Sélection aléatoire des enfants nécessaires pour compléter la population
missing = self.population_len - nb_survivor
kids_keep_index = np.random.choice(nb_survivor, size=missing, replace=False)
self.population = np.concatenate((self.population, kids[kids_keep_index]))La mutation de la population :
def _mutate_population(self):
# On créer un masque pour identifier les gènes à muter
mask = np.random.binomial(1, self.mutation_rate, size=self.population.shape) == 1
# On remplace les gènes "mutants" par des valeurs aléatoires
mutation = np.random.randn(*self.population.shape)
self.population[mask] = mutation[mask]La sélection des individus
Ici la fitness (score permettant de juger un individu), aura déjà été initialisée dans la fonction suivante.
def _select_survivors(self):
sum_fitness = self.fitness.sum()
if sum_fitness > 0:
# On transforme la fitness en probabilités (leur somme doit etre égale à 1)
survival_probability = self.fitness / self.fitness.sum()
else:
survival_probability = None
# On selectionne les survivants en tirant au sort à l'aide de leur probabilité de survie
survivor_index = np.random.choice(self.population.shape[0],
size=self.population_len - self.population_turnover,
replace=False,
p=survival_probability)
self.population = self.population[survivor_index]L'exécution d'un cycle de la population (une génération)
def run_cycle(self, fitness):
# On utilise exp pour favoriser les individus à fitness élevée
# L'ajout du random évite d'avoir des probabilités de 0 aux individus
self.fitness = np.exp(fitness) + np.random.random(len(fitness))/100
# On intègre à nouveau à la population les cinq meilleurs
self.fitness = np.concatenate((self.fitness, self.best_five_fitness))
self.population = np.concatenate((self.population, self.best_five))
# On met à jour les cinq meilleurs individus
best_index = self.fitness.argsort()[-5:]
self.best_five_fitness = self.fitness[best_index]
self.best_five = self.population[best_index, :].copy()
# On exécute la sélection, reproduction et mutation
self._select_survivors()
self._reproduce_population()
self._mutate_population()
return self.population3 … 2 … 1 … Evoluez !
Nous disposons maintenant de toutes les briques nécessaires, un environnement de jeu, un réseau de neurones pour choisir une action à réaliser à chaque étape du jeu et un algorithme génétique pour sélectionner nos meilleurs joueurs au fil de multiples générations. Il ne reste plus qu'à combiner toutes ces briques pour finaliser ce petit projet :
game = "Enduro-ram-v0"
game_data_len = 128
network_layer_shape = [64]
env = gym.make(game) # Création de l'environnement de jeu
action_space = env.action_space.n # Nombre des actions possible
# Initialisation du réseau de neurones
neural_network = NeuralNetwork(network_layer_shape, game_data_len, action_space)
genome_shape = neural_network.get_number_of_model_param() # Nombre de poids du réseau
# Initialisation de l'alogithme génétique
algo_genetique = Genetics(genome_len=genome_shape)
# On lance 100 générations
for i in range(100):
all_fitness = [] # Liste des fitness des individus
# Pour chaque individu de la population, on lance une partie
for individu in algo_genetique.population:
# Mise à jour des poids du réseau avec le génome de l'individu
neural_network.set_model_param(individu)
observation = env.reset() # On relance le jeu
game_reward = 0
for game_cycle in range(1000): # On lance le jeu pour "1000 étapes"
# On prédit l'action à réaliser
action = neural_network.model.predict_classes(observation.reshape(1, 128))[0]
observation, reward, done, info = env.step(action)
game_reward += reward
if done: # Si la partie est terminée, on passe à l'individu suivant
break
all_fitness.append(game_reward)
print("cycle ", str(i))
# On lance un nouveau cycle (génération) de l'algorithme génétique
fitness_population = np.asarray(all_fitness)
_ = algo_genetique.run_cycle(fitness_population)Que l'apprentissage commence !
Voilà, vous avez votre algorithme génétique qui va faire muter des individus afin de produire un réseau de neurones capable de battre votre jeu favoris. Il ne vous reste plus qu'à lancer votre algorithme et attendre que l'entraînement de votre population se termine.
Vous pourrez ensuite utiliser ce petit bout de code pour voir les exploits de votre meilleur individu !
neural_network.set_model_param(algo_genetique.best_five[4,:])
observation = env.reset()
for game_cycle in range(10000):
env.render()
action = neural_network.model.predict_classes(observation.reshape(1,128))[0]
observation, reward, done, info = env.step(action)
if done:
break
env.close()Merci beaucoup d'avoir lu jusqu'ici, j'espère que ce petit retour d'expérience autour des algorithmes génétiques vous aura intéressé !
N'hésitez pas à manipuler le code, il est loin d'être optimal. Beaucoup de paramètres influencent l'apprentissage : taille de population, taux de mutation, mais vous pouvez aussi changer les méthodes de sélection ou de reproduction par exemple... N'hésitez pas à expérimenter avec ces algorithmes aux possibilités infinies !
Bonne journée à vous
