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


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


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.


3) Donner la fonction de coût d'une solution _c_
Somme des poids des arretes du cycle.

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

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.


**Roue biaisée**
Methode de la ~z~roulette

3) **Comment effectuer des mutations ?**
On inverse deux valeurs aléatoirement. Il faut veiller à inverser 2 valeurs pour garder la validité de la solution.