Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Chapitre 5. – Application au domaine du tourisme Mémoire de Thèse Page 103 Dans

Chapitre 5. – Application au domaine du tourisme Mémoire de Thèse Page 103 Dans la partie non dépendante du domaine, sont considérées des caractéristiques de l'utilisateur qui vont contraindre de manière plus ou moins forte les propositions. Ainsi, elle contient sous forme de paires attribut- valeur : - la position géographique de l'utilisateur; - la tolérance de l'utilisateur sur la dispersion géographique des offres; - le nombre de jours du séjour; - le type d'hébergement désiré si besoin ; - la date du séjour. Un exemple de partie non dépendante du profil d'un utilisateur peut être: , , , , , Basée sur cette modélisation de l'utilisateur et la couche sémantique, la couche intelligence dont l'implémentation est expliquée dans la partie suivante peut fournir des recommandations à l'utilisateur. 3 IMPLEMENTATION DE LA COUCHE INTELLIGENCE Dans la couche intelligence, les différents algorithmes utilisés pour proposer des recommandations aux utilisateurs sont implémentés. Dans le mécanisme de proposition d’une combinaison, deux phases se distinguent: la phase de projection et la phase de recherche combinatoire. La phase de projection ne considère que la partie dépendante du domaine des profils utilisateurs. Pour chaque utilisateur, cette phase engendre un vecteur montrant ses intérêts sur chaque individu du modèle de domaine sous forme de poids (voir Chapitre 3 pour plus de détails). Elle est suivie par une phase de recherche combinatoire. Cette dernière consiste à rechercher une combinaison des individus du modèle de domaine pondérés, issus de la phase précédente. Cette section décrit la partie combinatoire, car celle-ci est particulière à l'application touristique à réaliser. Pour cette phase combinatoire, plusieurs mécanismes sont à définir pour obtenir une recommandation touristique suivant la formalisation du problème posé dans le chapitre 4. Tout d’abord, il est nécessaire de définir le pattern et les sous-patterns de combinaison contraignant la combinaison d’items à fournir à l’utilisateur. Cela fait l’objet d’une première partie. Puis, la partie suivante explique l’attribution des tolérances de dispersion à ces patterns. Ensuite, l’algorithme de recherche combinatoire basé sur le recuit simulé est exposé, suivi de quelques benchmarks de comparaison de performances suivant la fonction de pertinence (voir chapitre 4). L’algorithme basé sur le recuit simulé est comparé à un algorithme Hill-Climbing. Enfin, une dernière partie détaille l’utilisation d’un algorithme multi-objectif pour réaliser cette recherche combinatoire. Ce dernier algorithme n’est pas utilisé pour l’application mobile finale présentée dans le chapitre 6, mais peut être intéressant pour une future application ne demandant pas une réponse quasi temps réel. 3.1 CONSTRUCTION DYNAMIQUE DU PATTERN Avant toute chose, la phase de recherche combinatoire détermine quel sera le pattern de combinaison à proposer. Pour cela, le pattern d'une combinaison est construit de base comme ceci : De plus, des sous-patterns de combinaison sont définis (les indices permettent de situer les éléments du pattern utilisés par les sous-patterns): Page 104 Romain Picot-Clémente Différentes informations issues de la partie non dépendante du domaine du profil utilisateur vont être ensuite considérées pour modifier ce pattern. Le pattern est construit dynamiquement. En premier lieu, le type d'hébergement peut être modifié suivant le désir de l'utilisateur spécifié dans son profil. Par exemple, il peut être contraint au type Hôtel (concept fils du concept Hébergement dans l'ontologie de domaine), générant les patterns suivants : Puis, le nombre de jours du séjour va définir le nombre d'offres à proposer dans une combinaison. Si le nombre de jours est égal à 1, le pattern initial n'est pas changé. Sinon, les activités et restaurants vont être dupliqués pour chaque jour supplémentaire. Seul l'hébergement reste unique. Ainsi, soit , le nombre de jours du séjour, . La taille du pattern est définie comme ceci: Par exemple, si on considère un séjour de 3 jours, le pattern de la combinaison sera constitué de 16 objets et construit comme suit: Les sous-patterns de combinaison seront : De ce fait, le nombre de jours et le type d'hébergement agissent sur la forme de la combinaison à fournir à l'utilisateur. À présent, il est nécessaire d'attribuer des tolérances de dispersion à ces patterns. La partie suivante explique le principe d'attribution des tolérances. 3.2 ATTRIBUTION DES TOLERANCES DE DISPERSION Comme vu dans le chapitre 4, à chaque pattern et sous-patterns de combinaison doit être attribuée une tolérance de dispersion. Pour ce faire, nous utilisons la tolérance de l'utilisateur sur la dispersion des offres exprimée en Km dans son profil. Cette dernière est traduite en degré pour correspondre à l’expression de la longitude et latitude de chaque item. Puis, elle est attribuée à la tolérance de dispersion du pattern de combinaison. Pour les sous-patterns de combinaison, les tolérances de dispersion associées sont proportionnelles à la tolérance de dispersion du pattern de combinaison. Chapitre 5. – Application au domaine du tourisme Mémoire de Thèse Page 105 Soit un utilisateur dont la tolérance de dispersion traduite en degré vaut dans son profil utilisateur. En considérant les patterns de l’exemple précédent, la tolérance de dispersion pour le pattern de combinaison pour cet utilisateur est et les tolérances de dispersion pour les sous-patterns sont : La faible proportion appliquée à la tolérance de dispersion entre le deuxième restaurant de chaque jour et l'hébergement est justifiée par le fait qu'il est souhaitable que le système de recommandation propose un restaurant proche de l'hébergement pour la soirée. Cette notion de proximité est subjective, c'est pourquoi elle dépend de la tolérance de dispersion de l'utilisateur. 3.3 ALGORITHME DE RECHERCHE COMBINATOIRE BASE SUR LE RECUIT SIMULE En se basant sur le pattern (le terme pattern générique englobe le pattern de combinaison et les sous-patterns) et les tolérances de dispersion, une métaheuristique peut alors se charger de rechercher la combinaison optimale d'items du domaine, par maximisation de la fonction de pertinence. Nous utilisons un algorithme basé sur le recuit simulé pour chercher la combinaison optimale. Cet algorithme a la capacité de converger vers une bonne solution, ou la meilleure solution en un temps raisonnable pour une application quasi temps réel. Il a été prouvé dans (Geman & Geman, 1984) que le recuit simulé convergeait vers l'optimum global si le refroidissement était suffisamment lent (voir le Chapitre 4 pour plus de détail). L'algorithme du recuit simulé possède de grandes similitudes avec l'algorithme Hill-Climbing. Voici un rappel de ce en quoi consiste ce dernier : - On commence tout d’abord par trouver une solution au problème, une première combinaison, on calcule alors son énergie (inverse de la fonction de pertinence). - Ensuite, on transforme légèrement la solution et on calcule la nouvelle énergie. Si cette dernière est inférieure à la précédente alors on prend cette nouvelle combinaison comme solution courante, sinon on garde l’ancienne. - On continue ainsi jusqu’à ne plus pouvoir générer de nouvelle combinaison ayant une énergie inférieure à la combinaison courante. Le principal problème de cette méthode réside dans le fait qu’il y a une grande probabilité pour tomber dans un minimum local, c’est-à-dire une combinaison qui, tout en n’ayant pas l’énergie minimale, sera telle qu’aucune légère transformation ne permettra d’obtenir une combinaison avec une meilleure énergie. C’est à ce niveau que la technique du recuit simulé se distingue, elle permet en effet de sortir de certains minima locaux. La méthode consiste à introduire une erreur volontaire pour sortir de ces minima en acceptant, de temps en temps (avec une certaine probabilité), une combinaison de moins bonne qualité. Son acceptation sera déterminée aléatoirement en tenant compte de la différence entre les énergies et d'un paramètre appelé température. Ce dernier permet de prendre en compte le fait que plus le processus d’optimisation est avancé, moins il est prêt à accepter une solution plus coûteuse. L'algorithme fonctionne comme suit. Au départ, il choisit une combinaison initiale aléatoire d'items suivant le pattern défini précédemment. Cette combinaison a une énergie , appelée énergie initiale. Page 106 Romain Picot-Clémente L'énergie d'une combinaison valide est l'inverse de la fonction de pertinence appliquée à cette combinaison: Il s'agit alors de minimiser l'énergie. Plus l'énergie est basse, meilleure est la combinaison. Une variable T, appelée température, décroît par palier au cours du temps. A chaque niveau de température, un certain nombre de modifications aléatoires sont testées sur la combinaison courante. Lorsque ce nombre de modifications est atteint, on dit que le système est à l'état d'équilibre. Un coût est associé à chaque modification; il est défini comme la différence entre l'énergie de la combinaison après et avant la modification. Un coût négatif signifie que l'énergie courante a une énergie plus petite que la précédente (qui est donc meilleure par définition), elle est alors gardée. Au contraire, un coût positif représente une « mauvaise » modification. Néanmoins, elle peut être gardée à une certaine probabilité (taux d'acceptation ) qui dépend du niveau de température courante et du coût. Plus la température est grande, plus la probabilité l'est aussi. Ainsi, au cours du temps, le nombre de changements autorisé diminue dû à la décroissance de la température, jusqu'à ce qu'il n'y ait plus aucune modification acceptable. Au final, on dit que le système est gelé, et la combinaison courante devient la combinaison finale à présenter à l'utilisateur. uploads/Voyage/ 103-pdfsam-these-a-picot-clemente-romain-2011.pdf