---
# System prepended metadata

title: '[TC3] TD1 IAT - Algo Génétique'
tags: [IAT, TC3, S2]

---

# [TC3] TD1 IAT - Algo Génétique
###### tags: `IAT`, `S2`, `TC3`

[Sujet PDF](https://moodle.insa-lyon.fr/pluginfile.php/198168/mod_folder/content/0/TD-AG.pdf?forcedownload=1)

## Problème du voyageur de commerce (TSP)

Problèmes analogues dans le domaine des télécoms.

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

1) Solution : liste ordonnée des villes visitée/liste ordonnée de sommets du graphe où tous les sommets doivent être présents une seule fois
Cycle => le dernier élément de la liste doit correspondre au premier, cela veut dire n+1 éléments

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

2) Combien de solutions existent-il si graphe complet ?
On a n! solutions : n premiers choix, n-1 second choix, ... 
On divise par deux, car un cycle peut être lu dans un sens ou dans l'autre, ces cycles sont equivalents.

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

3) Donner la fonction de coût d'une solution _c_
Somme des poids des arretes du cycle.
![](https://i.imgur.com/lgWk1Mf.png)

On peut mettre des coûts infinis sur les arrêtes qui n'existent pas si le grpahe n'est pas complet. 

## Selection, croisement, mutation

1) **Représentation minimale**
Tableau de k lignes et n colonnes
![](https://i.imgur.com/tHTjHCy.png)

2) **Comment selectionner les meilleurs solutions**
* on peut utiliser un seuil adaptatif -> garder un certain nombre de valeurs O(n) -> linéaire, let's goooo
* julien bracon propose une pile FIFO (c'est un peu chelou, OSI comprends pas masse) => similaire à algo de tri O(k*m)
* Attention à pas être trop élitiste dès le début, on risque de garder que des extremums locaux et de passer à côté des solutions optimales.

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

**Roue biaisée**
Methode de la ~z~roulette 
![](https://i.imgur.com/kk7XlrL.png)
![](https://i.imgur.com/U0jUsWc.png)
![](https://i.imgur.com/T60FwOk.png)

3) **Comment effectuer des mutations ?**
On inverse deux valeurs aléatoirement. Il faut veiller à inverser 2 valeurs pour garder la validité de la solution.
![](https://i.imgur.com/ENAuOvf.png)
![](https://i.imgur.com/aITaJxM.png)
