Complex Web request resolution by semantic Web service composition and multi-objecive optimization
Institution:
Le HavreDisciplines:
Directors:
Abstract EN:
Electronic commerce is a new form of trade that takes increasingly important in various elds, such as tourism, transport, etc. With the spread of the Internet and telecommunication systems, users become more demanding and want to express and get answers to more complex requests, including multiple functionalities, conditions, constraints and objectives. Most complex requests including multiple functionalities cannot usually be answered by one single Web service. As multiple services are needed, the problem is then to nd good combinations using the available services but also to select the best ones according to user constraints and to the objectives expressed in the request. This thesis contributes to resolving this issue by focusing on the problem of semantic Web service composition and optimization to answer such requests. We provide some formalization of the problem and its elements : request, services and composition. While Web services are described semantically using the W3C OWL-S ontology, we design a compatible ontology for the semantic description of the request, which we name OWL-CR. For the automatic design of service composition satisfying a request, we propose a new model for the representation of semantic Web service composition and an algorithm that builds compositions based on this model. This latter supports any kind of composition structure and allows the execution of the compositions. Depending on the existence of dependencies between functionalities of the request, it can take two dierent forms. If the functionalities are independent or in the case of one-to-one dependencies only, the set of compositions answering the request is modeled as a multi-layer graph. In the specic case of global dependencies, it is modeled as a set of clusters, to avoid the combinatory problem induced by the dependencies when building the compositions with a graph. When the composition model is a graph, the problem of composition optimization is dened as a multi-objective shortest path problem and and exact approach, such as Martins'algorithm that we implemented, can be used to determine a subset of the Pareto front. Genetic Algorithms can be used in the case of global dependencies, when the composition model is a cluster set. In this case, the set of solutions cannot be dened apriori and the use of such algorithms is suitable to improve the quality of the responses to approximate optimal solutions. We experiment with the NSGA2 and SPEA2 approaches, known in the literature to provide the best results in terms of diversity of solutions and optimality level, and we show that they provide an acceptable solution. In our prototype, we have implemented our algorithm for building compositions and useful/pertinent optimization methods. The use case concerns tourism scenarios. The resulting compositions contain services fullling all request functionalities, considering the request conditions and constraints. When only the sequence structures are considered, the proposed algorithm of composition design has linear complexity in term of available services. Otherwise, it has cubic complexity, but considering all structures of composition provides a richer space of solutions.
Abstract FR:
Le commerce électronique est une forme nouvelle de commerce qui prend de plus en plus d'importance dans diérents domaines, comme le tourisme, le transport, etc. Avec la généralisation d'Internet et des systèmes de télécommunication, les utilisateurs deviennent plus exigeants et souhaitent pouvoir exprimer et obtenir des réponses à des requêtes plus complexes, contenant de multiples fonctionnalités, des conditions, des contraintes et des objectifs. Techniquement, la réponse à de telles requêtes est di cilement fournie par un seul service, mais plutôt par une combinaison de services. Le problème est alors de trouver les bonnes combinaisons en utilisant les services disponibles, mais aussi de sélectionner les meilleures d'entre elles en fonction des contraintes et des objectifs exprimés dans la requête. Cette thèse a pour ambition de contribuer à résoudre ce problème en se focalisant sur la composition de services Web sémantiques et l'optimisation de la réponse à une requête complexe. Nous formalisons le problème ainsi que ses éléments: requête, services et composition. Alors que les services Web sont décrits sémantiquement en utilisant le standard OWL-S, nous présentons une ontologie compatible pour la description sémantique de la requête, que nous nommons OWL-CR. Pour la conception automatique de la composition de services qui satisfait une requête, nous proposons un nouveau modèle pour la représentation de la composition de services Web sémantiques et un algorithme qui construit des compositions basées sur ce modèle. Ce dernier prend en charge n'importe quel type de structure de la composition et permet l'exécution des compositions. Selon l'existence de dépendances entre les fonctionnalités de la requête, il peut prendre deux formes diérentes. Dans le cas de fonctionnalités dépendantes une à une ou indépendantes, l'ensemble des compositions répondant à la requête est modélisé comme un graphe multicouches. Dans le cas spécique d'une dépendance globale, l'ensemble des compositions est modélisé comme un ensemble de grappes an d'éviter l'explosion combinatoire induite par les dépendances lors de la construction du graphe de composition. Lorsque le modèle de composition est un graphe, le problème d'optimisation de la composition est déni comme un problème de recherche de plus court chemin multi-objectif et une approche exacte, comme l'algorithme de Martins que nous avons implémenté, peut être utilisée pour déterminer un sous-ensemble du front de Pareto. Les algorithmes génétiques peuvent être utilisés lorsque le modèle de composition est un ensemble de grappes, car l'ensemble des solutions ne peut pas être déni à priori et l'utilisation de tels algorithmes est nécessaire, an d'améliorer la qualité des réponses pour se rapprocher des solutions optimales. Nous expérimentons les approches NSGA2 et SPEA2, connues dans la littérature pour fournir les meilleurs résultats en termes de diversité des solutions et de niveau d'optimalité, et nous montrons qu'elles fournissent une solution acceptable. L'algorithme de composition couplé aux méthodes d'optimisation précitées à été évalué sur un scénario de composition dun voyage touristique. Les compositions obtenues contiennent des services répondant à toutes les fonctionnalités de la requête, et tiennent compte des conditions, contraintes et objectifs. Lorsque seules les structures de type séquence sont considérées, l'algorithme de conception des compositions a une complexité linéaire en fonction de services disponibles. Lorsque toutes les structures possibles sont considérées, il a une complexité cubique, mais cette prise en compte fournir un espace de solutions plus riche.