Newer
Older
# Algorithme génétique
- Année : M1 IWOCS
- Matière: IA
- Compte-rendu : n°1
- Date : 25/05/2019
| Nom | Prénom | numéro étudiant |
| ------------ | ------ | --------------- |
| Eichelberger | Yoann | 20143326 |
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])
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.
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 graphes suivants sont les résults pour un échiquiers de 40 reines.
Lorsqu'une population se développe sur plusieurs génération, dans un cas normal d'évolution, une diversité croissante d'individus apparait comme nous le montre le graphe ci-dessous. 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.
Temps d'éxecution : 2-3 secondes
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.
Temps d'éxecution : ???
### Executer le programme
Le programme néccessite au moins `Java 8` et `Maven`.
Depuis la racine du projet taper :
mvn compile
mvn exec:java -Dexec.mainClass="ai.App"