Newer
Older
- Année : `M1 IWOCS`
- Matière: `IA`
- Date : `25/05/2019`
| Nom | Prénom | numéro étudiant |
| -------------- | ------- | --------------- |
| `Eichelberger` | `Yoann` | `20143326` |
### Executer le programme
Le programme néccessite au moins `Java 8` et `Maven`.
Depuis la racine du projet taper :
mvn compile
Pour lancer avec l'algorithme génétique ou le recuit simulé :
mvn exec:java -Dexec.mainClass="ai.App" -Dexec.args="genetic"
mvn exec:java -Dexec.mainClass="ai.App" -Dexec.args="annealing"
Les algorithmes génétiques appartiennent à la classe des algorithmes dit évolutionnaires, ce sont des métaheuristiques ayant pour but de trouver des solutions dans un temps raisonnable.
Nous cherchons à appliquer cet algorithme au problème NReines. Le but étant dans notre cas d'obtenir une reine par ligne et par colonne d'un échiquier sans que ses dernières ne soit en prise avec une autre reine. Concrétement, sur un échiquier de taille 8x8, 8 reines devront être placées.
Pour faire fonctionner l'algorithme, il va falloir initialement générer une population d'individus. Chaque individu doit représenter un échiquier avec un placement de reines pseudo "aléatoire".
### Modélisation de l'échiquier
Chaque échiquier est modélisé dans le programme sur des tableaux de N colonnes. L'indice de la colonne faisant référence à une ligne sur l'échiquier et sa valeur à une colonne. (exemple : `[2,0,3,1]`)
```
| | |X| |
|X| | | |
| | | |X|
| |X| | |
```
Cette représentation exclus d'office le placement de deux reines sur la même ligne. Quant aux colonnes, il suffit de faire attention de ne pas placer deux fois la même valeur dans notre tableau.
### Intégration de l'algorithme génétique
Mon intégration se veut la plus générique possible en partant du principe que l'algorithme génétique doit pouvoir fonctionner en dehors du problème des NReines. C'est pourquoi une couche d'abstraction a été créée permettant au développeur de ne surcharger que les fonctions :
- de création d'individu
- de croissement
- de mutation
L'algorithme passe par plusieurs phases qui ont chacune été réfléchis pour tirer un maximum des performances de l'algorithme.
#### Selection
Dans cette phrase, des individus vont être sélectionnées par paires afin d'être ensuite croisée et de générer un enfant possédant les gênes des deux parents.
Il est possible de choisir le selecteur grâce à l'interface `SelectionOperation`, mais pour le problème des NReines, c'est celui de la roue de la forture qui a été utilisé.
Pour améliorer les performances lors de l'exécution, j'ai choisi d'appliquer une phase construction de la roue avant la sélection afin de réduire la complexité de la recherche. Une recherche par dichotomie est effectuée ce qui lui donne une compléxité `O(log n)`.
#### Croissement
Cet opérateur va consister à mêler les gênes de deux individus afin d'en générer un nouveau plus ou moins évolué.
Pour son implémentation, j'ai choisi de copier le génome d'un des parents, puis de n'appliquer qu'un gêne de l'autre parent. Cette opération est rapide et donne les meilleurs résultats vis-à-vis d'autres méthodes de croissement que j'ai pu essayer.
#### Mutation
La mutation a pour rôle de rajouter de la variété dans une population et ainsi éviter de se retrouver coincé dans des extremum locaux.
Dans le problème des NReines, il s'agit tout simplement d'intervertir deux gênes.
### Résultats
L'algorithme pouvant être paramètré, que ce soit pour le nombre d'individus initial, la taille des échiquiers, le pourcentage de mutations sur les enfants, le pourcentage d'individus récupérés de la génération précédente et même l'algorithme de selection des parents, il est compliqué d'avoir un paramétrage pouvant fonctionner sur l'ensemble des tailles d'échiquier.
A force de test, voici la configuration qui a le mieux fonctionner sur le problème des NReines globalement :
| Paramètre | valeur |
| :---------------- | :------------------------- |
| Population | 10 000 |
| Algo. Selection | Roue de la forture biaisée |
| Mutation enfants | 0% |
| Les plus aptes | 15% |
| Les moins aptes | 5% |
| Nouveau individus | 1% |
| Enfants | 79% |
Les résultats en temps d'exécution montrent que des solutions sont trouvées sans tomber dans d'extremum locaux lorsque l'échiquier a moins de 60 reines. Au delà, des pics se forment et montre une difficulté à trouver des solutions dans la population. Ce qui implique un très grand nombre de générations, cela peut arriver si une population se met à tendre vers un individu d'un extremum local.
Comme le montre le graphe ci-dessus, lorsqu'une population se développe sur plusieurs générations, dans un cas normal d'évolution, une diversité croissante d'individus apparait. En moyenne, des individus deviennent de plus en plus aptes à être une solution mais on observe aussi une divergence entre la courbe des meilleurs et des pires individus, ce qui permet l'exploration d'un maximum de branches pouvant mener à un bon résultat.
Néamoins, il peut arriver qu'une population tend vers un individu, le plus apte à générer une potentielle solution mais qui en fin de compte tire l'ensemble des individus vers un extremum local, ce qui a pour conséquence de faire perdre de la diversité à la population et donc d'empêcher la génération d'une potentielle solution.
C'est le cas pour cette génération pour un échiquier de 200 reines, les individus les plus aptes ont dû mal à améliorer la qualité de leur descendance même après plus de 900 générations.
Pour palier à ce problème les mutations des enfants être une solution sur de très grands échiquiers. Mais il pourrait aussi y avoir un opérateur d'inversement afin de privilégier les individus les moins aptes lorsque la qualité moyenne de la population dépasse un certain seuil.
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
L'algorithme du recuit simulé a une approche totalement différentes de l'algorithme génétique. Dans le cas du simulé nous allons partir d'un individu lambda et allons nous déplacer dans l'arbre des solutions avec une certaine marge afin de ne pas rester dans un extremum local. Contrairement à l'algorithme génétique qui lui va partir d'un grand échantillon d'individus lambdas et va développer un grand nombre de chemins tout en privilégiant statistiquement les plus aptes.
Comme montré sur le graphe ci-dessus, les performances à l'exécution du recuit simulé sont très élevés par rapport à l'algorithme génétique. Cela s'explique par le fait de ne devoir développer qu'un seul individu pour essayer de le guider vers une solution. Dans l'idée ça marche très bien mais il y a quand même un problème, la marge de manoeuvre du recuit simulé est très limité et si à un moment donné un individu est un extremum local dans un ensemble d'extremum locaux, le recuit simulé ne pourra pas trouver la solution car incapable de revenir drastiquement en arrière.
# Résolution du problème avec A*
Nous voulons désormais résoudre le problème avec l'algorithme A*. Il va donc falloir faire une représentation du système de résolution ainsi qu'appliquer une heuristique au problème.
## Représentation du triplet
Pour représenter un échiquier, sa représentation sera la même que pour l'algorithme génétique, soit de la forme d'un tableau ayant pour indice les lignes et pour valeurs les colonnes de l'échiquier.
Soit `T = (I,O,B)` :
- `I` : ensemble des états initiaux.
- `O` : ensemble des opérateurs de permutation.
- `B` : ensemble des états finaux.
Pour orienter la recherche, il faudra appliquer une fonction `enPrise()` sur chaque noeud afin de connaitre leur `fitness`. Dans notre cas, on ne souhaite pas avoir de reines en prises donc l'objectif sera d'atteindre 0.
Pour un exemple avec 4 reines :
> `I = {[1,2,3,4]}`
Echiquier disposant les pièces en diagonales.
> `O = {permutation(reine_1, reine_2)}`
Opération de permutation de deux reines.
> `P = {[2,0,3,1]}`
Solutions pour le N donné.
## Heuristique
* `h(noeud) = cout + distance entre le noeud et la fin`
* `h(noeud) = noeud.cout + noeud.enPrise`
On ajoute le coût du noeud avec le nombre de reines en prise.