% vim:textwidth=80:
\documentclass[a4paper,11pt]{report}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\usepackage[french]{babel}

% change les marges (trop grosses par défaut)
\usepackage{vmargin}
\setmarginsrb{2.5cm}{2cm}{2.5cm}{2cm}{0cm}{0cm}{0cm}{0cm}

\author{Yoann \textsc{Guillot}}
\title{Rapport de projet d'Intelligence Artificielle\\Le voyageur de commerce}
\date{}

\begin{document}
\maketitle
\chapter*{Introduction}
Le problème du voyageur de commerce est un problème bien connu, car il est d'une
grande complexité.\\

Petit rappel du problème :

Nous avons N villes, dans chacune desquelles un voyageur de commerce doit passer
une fois et une seule, avant de revenir à son point de départ. Les distances
entre les villes sont connues. Le problème consiste à trouver le chemin le moins
long satisfaisant ces conditions. Il existe des variantes où le coût du
déplacement n'est pas sa longueur, mais sa durée, ou son coût financier ; dans
tous les cas, il s'agit de minimiser le coût total du trajet en connaissant le
coût d'une ville à l'autre (le coût d'un trajet n'est pas forcément identique
dans un sens et dans l'autre).\\

Ce problème est NP-complet : l'existence d'un algorithme de complexité
polynomiale résolvant le problème reste inconnue. Un rapide calcul de la
complexité du problème donne O($n!$) où $n$ est le nombre de villes.

C'est donc un problème difficile. En supposant qu'il faut 1 $\mathrm
\mu$s pour évaluer une possibilité, le tableau suivant donne la durée nécessaire pour
résoudre le problème en fonction du nombre de villes, en essayant simplement
tous les chemins possibles :

\begin{center}
\begin{tabular}{|c|r|}
\hline
5 & 12 $\mathrm{\mu}$s \\
\hline
10 & 0.18 ms \\
\hline
15 & 12 heures \\
\hline
20 & 1928 ans \\
\hline
25 & 9.8 milliards d'années \\
\hline
\end{tabular}
\end{center}

\chapter*{Le problème}
Le problème considéré ici consiste à trouver un chemin de longueur minimale
entre $n$ villes, placées à la main (à la souris) ; le coût d'un trajet est la
distance entre les deux villes. On ne cherche pas à résoudre le problème de
manière déterministe (on ne trouvera généralement pas la solution optimale),
mais on cherche à évaluer une méthode particulière de résolution approchée du
problème.\\

Cette solution approché est calculée grâce à un algorithme basé sur le
comportement d'un élastique.

On part d'une forme géométrique régulière, centrée sur le barycentre des villes,
de rayon paramétrable.

Cette forme évolue ensuite, chaque point d'ancrage de celle-ci étant attiré par
ses voisins (d'où l'analogie avec l'élastique), et en même temps par les villes
que l'on cherche à relier. Il s'agit de trouver les paramètres d'attraction
donnant les meilleurs résultats.\\

Deux choses importantes sont à noter sur cette approche :
\begin{itemize}
\item Tout d'abord, cette technique calcule un chemin, dont la longueur sera
normalement proche de celle du cycle optimal, mais le chemin trouvé \emph{ne
passe pas} par les villes du problème. Il conviendra donc d'adapter la solution
trouvée à une solution réelle, en modifiant à la main le chemin renvoyé.
\item Ensuite cette variante du problème n'utilise pas de chemins prédéfinis, on
considère que le voyageur peut aller de n'importe quelle ville à n'importe
quelle autre.
\end{itemize}

\chapter*{Implémentation}
Pour le code j'ai choisi d'utiliser le langage C++, et Qt pour l'interface
graphique. Ce langage permet de créer rapidement des interfaces agréables, et
dispose de facilités pour les dessins qui seront utiles dans la réalisation du
projet.\\

L'interface se compose d'un panneau vierge, où aura lieu le placement des villes et la
visualisation des itinéraires trouvés par l'algorithme ; et d'un panneau de
controle, où l'on peut définir les différents paramètres de l'algorithme, et
lancer celui-ci.\\

La classe principale utilisée par le programme est la classe Elastique.
Celle-ci comporte comme membre principal :
\begin{verbatim}
void shrink(double a, double b, double k);
\end{verbatim}

Cette fonction applique la formule suivante à chaque point de l'élastique ($pts$
est le tableau contenant tous les points, $i$ est l'indice du point courant)
$$
pts_i = pts_i + \beta \frac{pts_{i-1} - pts_i + pts_{i+1} - pts_i}{2} + \alpha \sum_{j}
\omega_{ij} (ville_j - pts_i)
$$
La partie importante de l'algorithme est dans la définition même de $\omega_{ij}$ :
$$
\omega_{ij} = \frac{f(|ville_j-pts_i|)}{\sum_{p} f(|ville_j-pts_p|)}
$$
avec
$$
f(x) = e^{-\frac{x^2}{2k^2}}
$$

\smallskip
Etudions les différentes composantes de $pts_i$ :\\

On voit tout d'abord que le point à l'itération se base sur la position du point
courant.\\

La partie avec $\beta$ fait en sorte que chaque point soit attiré par ses deux
voisins directs. Avec $\beta = 0.5$ on obtient qu'a chaque itération le point se
déplace au niveau du milieu du segment formé par ces deux voisins.\\

\newpage
La partie avec $\alpha$ est la plus intéressante : on voit que le point est
attiré par chaque ville, avec un coefficient qui dépend à la fois de $k$ (plus $k$
est grand, plus l'éloignement de la ville diminue son attraction), mais aussi de
l'attraction exercée par la ville sur tous les points de l'élastique.

Ceci à donc pour effet qu'une ville déjà proche d'un ou plusieurs points de
l'élastique attirera beaucoup moins les autres points de l'élastique, et c'est
ce qui explique que l'élastique ``aille chercher'' les points qui sont éloignés
de lui.\\

Le déroulement du programme consiste donc à :
\begin{enumerate}
\item Placer les villes correspondant au problème.
\item Initialiser les paramètres de l'algorithme.
\item Initialiser l'élastique (par exemple sous forme d'un polygone régulier).
\item Itérer les appels à la fonction {\texttt shrink()} en
diminuant graduellement la température.
\item Eventuellement réajuster les paramètres, et recommencer.\\
\end{enumerate}

La diminution de la température à pour effet de déplacer, au début de
l'algorithme, de grandes parties de l'élastique vers les grands groupes de
villes, puis au fur et à mesure des itérations, chaque partie de l'élastique
devient de plus en plus attirée par les villes qui en sont proche.

Ceci est vérifiable en appliquant l'algorithme sur des villes regroupées en deux
paquets bien distincts : l'élastique va commencer au milieu entre les groupes,
puis s'étirer pour attendre chacun, et au fur et à mesure va se rapprocher des
villes individuellement.\\

Le programme maintient 2 listes globales : la liste des villes, qui est une
liste de \textbf{Point}, et la liste des élastiques déjà calculés.

Un élastique est un tableau de Points, dont les coordonnées sont stockées de
manière interne sous le format {\texttt doubles} ce qui permet des calculs en
virgule flottante, l'affichage utilise une valeur arrondie de ces coordonnées ;
ainsi les calculs sont plus précis.

Chacun dispose de méthodes pour s'afficher à l'écran : un \textbf{Point} est
représenté sous forme d'une croix, un élastique est une suite de lignes, générées
à la demande.\\

La classe \textbf{Point} est munie des opérateurs classiques, tels que
l'addition de deux \textbf{Point}s, ainsi que la multiplication par un scalaire,
ce qui permet un code moins encombré.

Une définition efficace des {\texttt constructeurs} de la classe \textbf{Elastique}
donne également un code plus clair : on peut créer directement la figure géométrique
régulière qui sert de point de départ à l'algorithme, en passant les bons
paramètres (centre, rayon, nombre de points) ; ou on peut créer une copie d'un
élastique préexistant, ce qui est utilisé dans la boucle principale de l'algorithme.

En effet on ne peut pas créer un élastique unique et le réduire graduellement, car
alors on n'obtiendrait pas l'affichage souhaité : il faut partir de l'élastique
initial, et à chaque itération \emph{copier} l'élastique précédent avant de lui
appliquer la transformation {\texttt shrink()}.

Ceci permet de conserver l'``historique'' des déformations, et rend bien
l'affichage souhaité ; de plus si on le souhaite on peut ne garder que certains
élastiques, le dernier étant le plus intéressant.\\

L'effacement de l'affichage est obtenu par la simple réinitialisation des listes
globales, en effet le {\texttt destructeur} des classes \textbf{Point} et
\textbf{Elastique} fait en sorte d'effacer la représentation de chaque instance
(si elle était dessinée) de l'affichage.

\chapter*{Utilisation}
Le placement des villes se fait en passant en mode d'insertion. Pour passer dans
ce mode, cliquer sur le bouton libellé ``\textbf{Placement}''. Ceci réinitialise
l'affichage, ensuite chaque clic sur la zone de dessin rajoute une ville sous le
curseur. Le programme interdit de placer une ville sur un emplacement déjà
occupé. Une fois toutes les villes placées, recliquer sur le bouton (dont le
libellé à changé en ``\textbf{Terminé}'') pour mettre fin au mode de placement.\\

Les paramètres peuvent ensuite être définis (on peut aussi bien garder les
valeurs par défaut qui conviennent assez bien en général). Les différents
paramètres sont :
\begin{itemize}
\item[\textbf A] Le paramètre alpha lié à l'attraction des points de l'élastique par les
villes.
\item[\textbf B] Le paramètre beta, lié à l'attraction de chaque point de l'élastique
par chacun de ses voisins. Ce paramètre doit normalement rester entre 0 et 1,
sinon le point déplacé aura tendance à dépasser le milieu du segment formé par
ses deux voisins, ce qui n'est pas souhaité pour la convergence de l'algorithme.
\item[\textbf K] C'est la ``température'' au début de l'algorithme. Ce paramètre
détermine le ``rayon d'attraction'' dans lequel les villes vont attirer les points
de l'élastique.
\item[\textbf xK] C'est le coefficient par lequel est multiplié $k$ à chaque
itération. Sa valeur devrait rester entre $1$ (strictement) et $0.97$.
\item[\textbf M] C'est le multiplicateur utilisé pour calculer le nombre de points sur
l'élastique par rapport au nombre de villes sur la carte. Quand les villes sont
très nombreuses, il est conseillé de diminuer cette valeur pour réduire les
temps de calcul.
\item[\textbf xR] C'est le multiplicateur utilisé pour le calcul du rayon du polygone
initial, par rapport à la distance moyenne entre le barycentre des villes et
chaque ville. Un petit rayon produit souvent de meilleurs résultats.
\end{itemize}

Ensuite pour lancer l'algorithme cliquer sur ``\textbf{Démarrer}''.
On peut alors suivre l'évolution de l'élastique sur l'affichage. Le programme
effectue 200 itérations, et affiche l'élastique en utilisant un dégradé de bleu
foncé à bleu clair pour les dernières itération.\\

Ce mode d'affichage devenant rapidement illisible, j'ai ajouté le bouton 
``\textbf{Solution}'' qui permet une fois l'algorithme terminé de ne conserver
sur l'affichage que les villes et la dernière configuration de l'élastique,
afin de pouvoir apprécier les résultats de l'algorithme.

\chapter*{Résultats}
\'Etant donné la nature du problème, l'évaluation des résultats est très
subjective. En effet, on ne dispose pas de référence, donc on peut seulement
jauger ``à l'\oe il'' du chemin trouvé -- d'autant plus que celui-ci ne passe pas
par les villes du problème, il faut donc de toute façon retoucher le résultat.\\

Expérimentalement, on constate que cet algorithme trouve de bonnes solutions,
sauf dans certaines configurations particulières, ou le chemin optimal ne
ressemble pas du tout à un cercle, comme par exemple une configuration en ``S''
ou zigzags, dans ce cas l'algorithme tend vers une structure plutot étoilée, qui
n'est certainement pas optimale, car elle présente de nombreux ``sauts'' entre
des lignes parallèles, qui ne sont pas nécessaires et allongent le chemin ;
cependant ces cas de figures sont très particuliers et peuvent être résolus à la
main.\\

Comme dit plus haut, l'élastique \emph{tend} seulement vers les villes du
problème, mais le passage de l'élastique dans sa position finale à une solution
admissible est très simple dans tous les tests que j'ai effectué ; en effet pour
chaque ville on distingue une ``pointe'' de l'élastique qui désigne de manière
non équivoque la ville à placer ; sauf dans deux cas :
\begin{itemize}
\item Dans le cas où un groupement de villes n'est pas détaillé par
l'algorithme. Dans ce cas il s'agit d'une faiblesse de l'implémentation.
Cette situation serait évitée par un plus
grand nombre d'itérations. Le problème survient quand un groupement isolé de
villes du graphe est atteint tardivement par une partie de l'élastique : dans
ce cas la partie en question de l'élastique n'a pas le ``temps'' de se
diversifier en s'approchant de chaque ville du groupement, car la température
est trop basse à ce moment (il faudrait peut-être envisager de diminuer la température
différemment suivant la position sur l'élastique)
\item Le deuxième cas est quand l'élastique se replie sur lui-même, ce qui
aboutit à un croisement. Si une ville se trouve dans la région du croisement, on
ne sait a priori pas à quel brin de l'élastique l'assigner. Mais en pratique
ceci importe peu, car soit on voit vers quel brin il est plus optimal de le
mettre, soit l'assignement à l'un ou l'autre des brins est indifférent car il
produit quasiment le même allongement de l'élastique.
\end{itemize}

\chapter*{Conclusion}
Ainsi on constate que cet algorithme donne rapidement de bons résultats,
dans quasiment toutes les situations. On pourrait éventuellement envisager de le coupler
à un mécanisme de variation automatique des paramètres afin de trouver ceux les
mieux adaptés à une situation donnée.

La partie la plus difficile est sans doute le passage de la solution trouvée à
une solution admissible, mais ceci n'est pas très compliqué, quitte à relancer
l'algorithme localement en cas d'ambiguïté.
\end{document}
