restricted:opti-c-tp1 [WiKi informatique]

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.
==== TP1 ====

Le TP sera écrit en Python. Pour l’affichage de la carte et du chemin proposé, on utilisera la librairie {{https://matplotlib.org/|matplotlib}}.

<code python>
import numpy as np
import matplotlib.pyplot as plt
import random
</code>

<note important> **NB :**

  * permutation d’une liste d’entiers : 
<code python>
  np.random.permutation(range(n))
</code>
  * copie de liste : 
<code python>
  copie_de_l = list(l)
</code>
→ important pour déterminer la liste des voisins
</note>

=== Problème du voyageur de commerce === 
Un voyageur de commerce doit visiter $n$ villes au cours de sa tournée numérotées $0,...,n-1$. Ces villes sont définies par leurs coordonnées géographiques $(x_i,y_i)$. Un parcours consiste à affecter un ordre à chaque ville :
  * ordre $i \rightarrow s(i) ∈ 0..n-1$
sous la contrainte que chaque ville doit être visitée une fois et une seule.
(autrement dit, $s$ est une permutation de $(0,...,n-1)$ => $n!$ solutions).
Le coût d’une solution s est :
$$J(s) = \sum_{i=0}^{n-2} d(s(i),s(i+1)) + d(s(n-1), s(0))$$
avec:
$$d(s(i), s(j)) = \sqrt{(x_{s(i)} - x_{s(j)})^2 + (y_{s(i)} - y_{s(j)})^2}$$

Le problème d’optimisation consiste à //minimiser// la distance totale.

=== Résolution par optimisation stochastique ===
Le but est d’écrire une librairie Python permettant de résoudre le problème du voyageur de commerce. 

Un problème de voyageur de commerce sera décrit sous la forme d’une liste de villes avec leurs coordonnées géographiques.

<note tip>
Pour simplifier, on peut tirer les coordonnées de toutes les villes au hasard entre 0 et 1 pour les abcisses et les ordonnées
</note>

Une solution s sera définie come une permutation de la liste des n premiers entiers
 
Ecrire une fonction qui affiche graphiquement la solution courante (comme une série de segments reliant les points dans l'ordre parcouru).

Implémentez ensuite plusieurs méthodes de résolution. Vous devez impérativement implémenter 
  * la Méthode de Monte Carlo 
  * et la Méthode glouton. 

Pensez en particulier écrire les fonctions suivantes:

  * ''randomVoisin(s)'' : fonction qui retourne un voisin de la solution s pris au hasard
  * ''tousLesVoisins(s)'' : fonction qui retourne la liste de tous les voisins de s
  * ''argmin_J(s)'' : fonction qui retourne le voisin de s qui minimise la fonction J.

<note tip>
  * Le voisin d'une solution s est obtenu en permutant deux éléments de s
  * L'ensemble des voisins de s est l'ensemble des permutations de deux éléments possibles à partir de s. 
</note>
 
Puis vous implementerez au choix :
  * méthode tabou (hyperparamètre K) 
  * la méthode du recuit simulé (hypermaramètres $\beta_0$ et ε)


=== Tableau comparatif === 
Une fois vos méthodes testées, vous devez indiquer pour chaque méthode la longueur du chemin trouvé pour n = 10, n = 20, n = 40, n = 80 et n = 160, ainsi que le temps de calcul nécessaire pour obtenir la solution.

Vous afficherez graphiquement les différents chemins trouvés.   

=== Rappels ===

**Monte Carlo :**
<code>
données : N
J* ← + infini
pour i de 1 à N:
    tirer un parcours s au hasard 
    si J(s) < J* alors:
        J* ← J
        s* ← s
</code>


**Glouton :**
<code>
données : s
J* ← +infini
tant que J(s) < J*:
    J* <-- J(s)
    s <-- argmin_J(s)
</code>

**Glouton aléatoire :**
<code>
données : s
J* <-- +infini
Pour i de 1 à N:
    choisir au hasard s’ voisin de s
    si J(s’) < J(s) alors:
        J* <-- J
        s <-- s’
</code>

**Tabou :**
<code>
données : s,K
J* ← +infini
tabou ← []
Pour i de 1 à N:
     si J(s) < J* :
          J* ← J(s)
          s* ← s
     ajouter s à la fin de tabou
     supprimer le premier élément de tabou si |tabou| > K     
     s ← argmin_J(s,tabou)
</code>


**Recuit :**
<code>
données : s, beta_0, eps 
beta <--- beta_0
Pour i de 1 à N:
    choisir au hasard s’ voisin de s
    si J(s’) < J(s) alors:
        ACCEPTER
    sinon :
        p = exp(-beta * (J(s’)-J(s)))
        x <-- tirage_uniforme sur [0,1]
        si x < p alors:
            ACCEPTER
        sinon:
            REFUSER
    si ACCEPTER:
        s <-- s’
    beta <-- (1+eps) * beta
</code>