1.9 Résultats expérimentaux
Les sections suivantes présentent l'application de
notre méthode sur plusieurs problèmes : un problème
d'optimisation combinatoire (le problème du Voyageur de Commerce), un
problème de satisfaction de contraintes pratique (le problème
d'Emploi du Temps de Garde d'Infirmières) et plusieurs problèmes
de satisfaction de contraintes (le problème du Sac-à-dos
Multidimensionnel, le problème du Carré Magique et le
problème de Coloration de Graphes).
1.9.1 Application au problème du Voyageur de
Commerce
La première application de notre méthode se fait
dans le cadre d'un problème d'optimisation combinatoire. Le
problème choisi est le problème du Voyageur de Commerce. Ce
problème présente l'avantage de fournir rapidement un nombre
important de solutions. Le but du problème est de trouver un circuit de
longueur minimal passant par n villes. Chaque ville doit être
visitée une et une seule fois.
Nous utilisons un schéma de branchement naïf dans
lequel chaque noeud est associé à une ville i et chaque
noeud fils correspond à la ville j visitée
immédiatement après i. Nous associons alors un poids
wij à chaque arc (i, j)
égal à la valeur de la meilleure solution trouvée dans
l'ensemble des sous-arbres explorés. Ce poids est mis à jour
à chaque fois qu'une solution de coût inférieur est
trouvée pour le même arc (i, j). Le
schéma de branchement consiste à choisir les arcs candidats dans
l'ordre croissant des poids. Le schéma ainsi présenté
décrit une politique de branchement fixe sur les variables (chaque noeud
du niveau k correspond à fixer une valeur à la variable
xk indiquant quel arc est emprunté à la position
k) tandis que l'ordre des valeurs est déterminé par la
méthode DLS. Les poids associés aux arcs sont initialisés
par une phase d'apprentissage. Cette phase consiste en une
génération aléatoire de chemins dans l'arbre de recherche.
Le nombre de chemins aléatoires est fixé à
n2, où n est le nombre de ville. Les
résultats montrent une réduction importante de la taille de
l'arbre de recherche, ainsi que du temps d'exécution, comparé
à une méthode de Profondeur en Premier (Depth First
Search).
Le tableau 1.1 présente nos résultats sur un
ensemble de 60 instances de problème de Voyageur de Commerce. Les
instances utilisées sont des instances générées
aléatoirement avec un nombre de villes allant de 10 à 22. Les
villes sont situées aléatoirement dans un carré de 100 par
100. 5 instances sont générées par nombre de villes. Les
instances de Problème de Voyageur de Commerce sur lesquelles notre
méthode est appliquée sont des instances de très petites
tailles par rapport à l'état de l'art (les dernières
méthodes par séparation et génération de coupes
sont capables de résoudre des instances de très grandes tailles,
comme une instance comprenant les 24978 villes de Suède), mais
permettent d'évaluer notre méthode. Les résultats
présentent le temps d'exécution moyen (en secondes) et le nombre
de noeuds, sur l'ensemble des instances.
|
Depth First Search
|
DLS
|
DLS avec apprentissage
|
|
Nombre de noeuds Temps exécution (in sec)
|
6,089,428
57
|
4,790,007
45
|
3,258,450
30
|
TABLE 1.1 - Résultats
expérimentaux pour plusieurs méthodes appliquées au
problème du Voyageur de Commerce
| 
