# Algorithme génétique

- Année : M1 IWOCS
- Matière: IA
- Compte-rendu : n°1
- Date : 25/05/2019

## Auteur

| 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.

## Application au problème des N-Reines

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 le 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.

### Implémentation


### Résultats

![Genetic trace](/data/genetic_trace.png)
![Genetic local extremum trace](data/genetic_trace_fail.png)

### Comparaison avec le recuit similé

![Annealing trace](/data/annealing_trace.png)