WOW !! MUCH LOVE ! SO WORLD PEACE !
Fond bitcoin pour l'amélioration du site: 1memzGeKS7CB3ECNkzSn2qHwxU6NZoJ8o
  Dogecoin (tips/pourboires): DCLoo9Dd4qECqpMLurdgGnaoqbftj16Nvp


Home | Publier un mémoire | Une page au hasard

 > 

Techniques hybrides de recherche exacte et approchée: application à  des problèmes de transport

( Télécharger le fichier original )
par Boris BONTOUX
Université d'Avignon et des pays de Vaucluse - Doctorat spécialité informatique 2008
  

précédent sommaire suivant

Bitcoin is a swarm of cyber hornets serving the goddess of wisdom, feeding on the fire of truth, exponentially growing ever smarter, faster, and stronger behind a wall of encrypted energy

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

précédent sommaire suivant






Bitcoin is a swarm of cyber hornets serving the goddess of wisdom, feeding on the fire of truth, exponentially growing ever smarter, faster, and stronger behind a wall of encrypted energy








"I don't believe we shall ever have a good money again before we take the thing out of the hand of governments. We can't take it violently, out of the hands of governments, all we can do is by some sly roundabout way introduce something that they can't stop ..."   Friedrich Hayek (1899-1992) en 1984