Système de classeurs

Un système de classeurs (Learning Classifier System ou LCS en anglais) est un système d'apprentissage automatique utilisant l'apprentissage par renforcement et les algorithmes génétiques. Ils ont été introduits par Holland en 1977 et développé par Goldberg en 1989

Principe général

Un système de classeurs (aussi appelé classifiers) est composé d'une base de règles, appelée classeur, associés à un poids. Chaque règle est composée d'une partie condition et d'une partie action.

Le classeur commence par être initialisé (aléatoirement ou non).

Pour exécuter un système de classeur, on sélectionne l'ensemble des règles applicables pour la situation en cours et l'on effectue un tirage aléatoire proportionnel aux poids de chaque règle. Si l'action est mauvaise, on diminue le poids de la règle ayant été sélectionnée. Si au contraire elle a été bénéfique, on augmente ce poids.

L'apprentissage consiste à exécuter un algorithme génétique qui va produire d'autres classeurs avec des règles différentes.

Il existe plusieurs types de système de classeurs. On pourra par exemple citer :

• Type Michigan : L'algorithme génétique est exécuté sur une population de règles.
• Type Pittsburgh : L'algorithme génétique est exécuté avec des individus représentant un classeur complet et non plus seulement chaque règle.
• ZCS
• XCS
• ACS
• Système de classeurs flous

Exemple simple

Cet exemple présente un système de classeurs de type Michigan très simple. Considérons un environnement constitué de cases pouvant être remplies ou vides. Un robot évoluant dans cet environnement peut se déplacer sur une des cases adjacentes si celle-ci est vide.

Visualisation d'un état de l'environnement

Numérotation des cases adjacentes au robot

En numérotant les cases entourant le robot de 1 à 8 (par exemple en partant de la case en haut à gauche et en tournant dans le sens des aiguilles d'une montre), on peut écrire une condition de huit éléments binaires (0 ou 1), où le ième élément représente si la ième case adjacente est pleine ou vide.

Par exemple, la condition 01000000 est vraie si le robot n'a qu'une seule case remplie autour de lui (la case au "dessus", voir figure).

Admettons maintenant un caractère supplémentaire « # » étant une sorte de joker dans la condition. Par exemple : #1#0#0#0 est vrai si la case du dessus est remplie, si les cases de droite, gauche et du dessous sont vides, et quels que soient les états des cases en diagonales.

Numérotons de 1 à 8 les actions possibles, le chiffre correspondant à la case sur laquelle le robot doit se déplacer.

Initialisons maintenant le classeur :

Condition → Action (Poids)

• #0###### → 2 (0.5)
• #1#0#1## → 3 (0.2)
• 0#11#0## → 8 (0.4)
• 0#00#0## → 5 (0.3)
• #1#0#0## → 2 (0.9)
• ...

Dans l'exemple représenté sur le schéma, on sélectionne l'ensemble des règles applicables. Admettons que nous en ayons 2 :

• 0#00#0## → 5 (0.3) (Règle 1)
• #1#0#0## → 2 (0.9) (Règle 2)

Nous en sélectionnons maintenant une, avec une probabilité proportionnelle à leur poids:

$P(R1)={\frac {0.3}{0.3+0.9}}=0.25$

$P(R2)={\frac {0.9}{0.3+0.9}}=0.75$

Admettons que la Règle 2 soit sélectionnée. Dans ce cas, le robot effectuera l'action d'aller sur la case 2 qui est remplie. Cette action n'est pas permise par l'environnement. La règle 2 sera donc "punie", c'est-à-dire que l'on va diminuer son poids.

Pour améliorer le comportement du robot, le principe va ensuite être de modifier les règles du classeur (ou même produire d'autres classeur), par un algorithme génétique.

Exemples: Nous prenons 2 règles du classeur qui sont assez bien notées afin de les "croiser" :

• #1#0#1## → 3 (0.2)
• 0#11#0## → 8 (0.4)

En les croisant, nous produisons 2 autres règles qui viendront remplacer leurs parents ou d'autres règles moins performantes.

Par exemple:

• 0#10#1## → 8 (0.2)
• #1#1#0## → 3 (0.4)

Ces actions sont ensuite exécutées jusqu'à ce que le comportement du système (ici le robot) convienne.