---
# System prepended metadata

title: '[TC2] TD1 - IAT'
tags: [IAT, TC2, S2]

---

# [TC2] TD1 - IAT
###### tags: `IAT`, `S2`, `TC2`
---
_TD avec OSI_ le TD est enregisté par le prof [TD](https://moodle.insa-lyon.fr/mod/folder/view.php?id=85255)
##

## Probleme du voyageur de commerce (TSP)

### Q1. 
 - Solution est un cycle élémentaire {a~1~,a~2~,...,a~n~,a~n+1~}
 - Solution est composée de n arrêtes
 - Chaque sommet (ou ville) n'apparait qu'une et une seule fois, sauf a~n+1~=a~1~

### Q2. 

Il y a $\frac{(n-1)!}{2}$ solutions candidates car on peut commencer de n'importe quel sommet. On commence par 1, puis on a (n-1) solution, puis on passe sur une, et il reste (n-2) solutions, etc. Donc 1*(n-1)*(n-2)*... jusqu'à ce que rentre chez lui (sommet de départ, avec un parcours de n arrêtes). Or le parcours de ce cycle peut être fait dans les deux sens (graphe non orienté). Donc on divise par 2 le nombre total de solutions, car une moitié est égale à l'autre. Donc (n-1)! / 2 au total. 

complexité : O(n!) un algo de brut force (recherche exhaustive des cas) un peu de la merde.


### Q3.
![](https://i.imgur.com/JPGvdQN.png)

Soit c la solution candidate. La fonction de cout est la somme de la valeur des arrêtes ( ici cout de 1? ). On a un cout en O(n!)


## Etape 2 
![](https://i.imgur.com/s6u1xjq.png)
> rappel d'algo genetique 

### Q1.

Un tableau de k lignes et n colonnes =  k solutions * n villes

### Q2.

plus petit cout?

C'est cher de faire un tri. En prenant que les m premiers, on se limite dans la diversité et on risque de passer à côté de quelque chose.

On fait attention aussi à ne pas tomber dans le piège du minimum local en venant prendre que les meilleures strictement. 

On récupere l'élitisme (la meilleure ou les x 1eres meilleures) puis on fait un tirage par roulette biaisée. 

**Mais Jamy, c'est quoi une roulette biaisée ?**
![](https://i.imgur.com/uJPGo5R.png)
> Principe de la roulette biaisée


![](https://i.imgur.com/VKE1Sji.png)

_Hé ba c'est comme au casino, tu as une chance de tout perdre_

Comment on fait ? 
 - un générateur de nombre pseudo aléatoire
 - ![](https://i.imgur.com/RHgbrMK.png)
![](https://i.imgur.com/bXVsi6X.png)


![](https://i.imgur.com/rrlpGrc.png)

### Q3.
*c'est un cours de biologie*

On ne peut pas faire une permuation sur une partie  pour ne pas baise nos resultat.

On swap une valeur au hasard

![](https://i.imgur.com/yWPnnwH.png)

### Q4.

![](https://i.imgur.com/cSekaAJ.png)
![](https://i.imgur.com/aITaJxM.png)
![](https://i.imgur.com/GkhBADq.png)


## Etape 3 : On fait joujoue avec l'outil


apt install jdk ou apt install open-jdk
sur windows avec chocolatey choco install jdk8 ou jdk11 ou encore openjdk
Y a pas besoin d'exec si tu as la JMV et donc le JDK

C'est boooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo

![](https://i.imgur.com/vsPHIMA.png)

### Q2.

1ere exec 
![](https://i.imgur.com/E7UfrgS.png)

Apres que la solution n'évolue plus
![](https://i.imgur.com/X009gzO.png)

Taille de population de 100
![](https://i.imgur.com/TLA13mG.png)

Taille de population de 500
![](https://i.imgur.com/SJYZYGW.png)

### Q3.
 Ca fait des trucs, c'est plus lent en CPA mais je ne sais pas pourquoi






































































