# TD 4-bis -- Introduction a l'Intelligence Artificielle et à la Theorie des Jeux

###### tags `TD` `M1 S1` `IA`
[Sommaire](/8Sa-Z4QBS1ep0xPwtzigJA)
> [time= 16 oct 2020]

[TOC]

## Exercice 3 -- Problème des 6 reines, approche locale
### Enoncé
Résoudre le problème des 6 reines par l’algorithme de recherche locale (le problème consiste à placer 6 reines sur un échiquier 6x6 sans que deux d’entre elles ne se menacent mutuellement), en tenant compte du fait qu’il y a exactement une reine par colonne. On commence avec les reines placées comme dans la la figure ci-dessous. On utilise comme fonction d’utilité le nombre de paires de reines qui s’attaquent mutuellement. Dans la situation de départ il y a 9 paires de reines qui s’attaquent mutuellement. On choisit de deplacer une reine vers la case qui permet de réduire le plus possible ce nombre.


### Réponse

[4, 2, 3, 4, 3, 4] -> 9
 *  *  *  *  *  *
 *  *  *  *  *  *
 *  o  *  *  *  *
 *  *  o  *  o  *
 o  *  *  o  *  o
 *  *  *  *  *  *

[4, 2, 3, 5, 3, 4] -> 3
 *  *  *  *  *  *
 *  *  *  *  *  *
 *  o  *  *  *  *
 *  *  o  *  o  *
 o  *  *  *  *  o
 *  *  *  o  *  *
 
[4, 2, 1, 5, 3, 4] -> 2
 *  *  o  *  *  *
 *  *  *  *  *  *
 *  o  *  *  *  *
 *  *  *  *  o  *
 o  *  *  *  *  o
 *  *  *  o  *  *
 
 [4, 2, 1, 5, 3, 4] -> 0
 *  *  o  *  *  *
 *  *  *  *  *  o
 *  o  *  *  *  *
 *  *  *  *  o  *
 o  *  *  *  *  *
 *  *  *  o  *  *

## Exercice 4 -- Problème du voyageur de commerce
### Enoncé
On considère le problème du voyageur de commerce pour un graphe complet. On suppose que les villes sont numérotées de 1 à n. Le problème est de trouver le tour (circuit qui visite toutes les villes une fois) le plus court.
Nous allons utiliser le codage suivant : On écrit un tour comme une suite des n villes. On combine
deux tours en les coupant de manière aléatoire, au même endroit, et en recollant les morceaux.
Exemple:

Les mutations sont obtenues en inversant deux villes dans le tour. Est-ce que ce codage permet d’appliquer l’algorithme génétique ? Comment résoudre les problèmes qui se posent ?

### Réponse
Non car on passe par la meme ville, or on ne veux pas cela.
On remplace tout les doublons par un des elément manquants.01
Pour la mutation on faut une permutation.

## Exercice 5 -- jeux de carte
### Enoncé
Vous disposez de 10 cartes numérotées de 1 à 10. Vous devez choisir une façon de diviser celles-ci en 2 piles de telle sorte que la somme des numéros des cartes de la première pile soit aussi proche que possible de 36 et que le produit des numéros des cartes restantes soit aussi proche que possible de 360. Chaque carte pouvant être soit dans P1, soit dans P2, il y a 1024 façons de les trier. Quelle est la meilleure?
* Trouvez un encodage pour l’ensemble de ces solutions.
* Trouvez une fonction permettant d’évaluer la qualité d’une solution.
* Décrivez une implantation d’un algorithme génétique basés sur les deux points précédents, dans les grandes lignes.

### Réponse
#### Codage:
On fait un vecteur de taille 10.\
On met le numéro de la pile dans chaque cellule.\
ex:\
`[0, 1, 0, 1, 1, 1, 0, 0, 0, 1]`

#### fonction fitness

# on cherche a miniser la fitness_func
def fitness_func(codage):
    sum_r = 0
    prod_r = 1
    for i, elm in enumerate(1, codage):
        if elm == 0:
            sum_r += i
        else:
            prod_r *= i
    return abs(sum_r - 36) + abs(prod_r - 360)

#### implémentation
Pour le croisement:\
On coupe a un endroit par hazard et on choisit au hazard si on echange la fin le début ou la fin.
(comme d'habitude)

Pour les mutation:\
On change un des chiffres (0->1 et inversement).

Le meilleur enfant est celui qui à la fonction fitness la plus basse.