Soutenance mémoire
Les algorithmes génétiques
Contexte
Avec une évolution exponentielle dans le temps, les SI (Systèmes d’Informations) sont devenus plus complexes et plus hétérogènes en raison de la diversité des besoins, des exigences des clients, et de la grande masse d’information stockée et manipulée par les internautes. Les infrastructures publiques et privées du secteur informatique sont de plus en plus multiplateformes, multifournisseurs et distribuées à grande échelle. Dans une telle situation, nombreux sont les professionnels de l’informatique qui considèrent que l’interopérabilité est un aspect aussi important que la sécurité et la fiabilité pour la gestion de leurs SI et leurs environnements de fonctionnement. Assurer l’interopérabilité est l’une des clés de succès de développement et d’intégration des grands systèmes d’information. Cet objectif présente le noyau des travaux de recherches dédiés à l’amélioration des architectures, des plateformes et des technologies de développement des systèmes d’information depuis les méthodes cartésiennes jusqu’aux architectures orientées services, plus connue avec l’abréviation SOA(Service Oriented Architecture).Ces dernières présentent actuellement la vision architecturelle des SI modernes. SOA est un style architectural qui permet de construire des solutions d’entreprises basées sur les services. Au début, sa mise en place a été basée sur les technologies et les middlewares conçus pour le modèle « objets distribués » comme CORBA, RMI et DCOM. Cependant, chacune de ces technologies proposent sa propre infrastructure, ce qui impose une forte liaison entre les services fournis et leurs consommateurs.
En plus de l’urbanisation de son SI interne, l’entreprise d’aujourd’hui a besoin d’une ouverture vers son environnement économique pour accomplir des échanges interentreprises avec ses partenaires par le biais d’Internet (B2B : Business to Business), et répondre le plus rapidement possible aux besoins de ses clients (B2C : Business to Consumer). Actuellement, les solutions EAI (pour Enterprise Applications Integration) sont orientées vers les processus métiers et les échanges interentreprises. Elles prennent en compte les nouveaux modèles économiques créés et promus par Internet et ses technologies (TCP/IP, SMTP, HTTP, FTP, XML, etc.). De plus, les progiciels de gestion intégrés de la deuxième génération apportent une quantité de nouveaux modules organisés autour de la SOA.C’est dans ce contexte que les services web sont apparus pour mettre en place cette architecture. A la différence des technologies précédentes, les services web proposent une architecture par composants qui permet à une application de faire l’usage d’une fonctionnalité située dans une autre application. Cependant, cette solution repose sur l’ubiquité de l’infrastructure d’Internet alors que les autres architectures reposent chacune sur sa propre infrastructure. L’interopérabilité est donc une caractéristique intrinsèque aux services web parce qu’ils sont basés sur des technologies Web dérivées du fameux standard XML.
Depuis la naissance du paradigme des services web en l’an 2000, ils sont été considérés comme une révolution pour le Web. En effet, avec les trois premières technologies de base :SOAP (Simple Object Access Protocol),UDDI (Universal Description Directory and Integration) et WSDL (Web services Description Language), les services web ont connu un grand succès grâce au haut degré d’interopérabilité fourni par les standards. Les services web sont présentés comme le meilleur moyen pour concrétiser la SOA (Service Oriented Architecture)et pour mettre en place le paradigme SOC (Services Oriented Computing). Cependant, les services web possèdent aussi des inconvénients. En effet, il se peut qu’un client ait des besoins spécifiques qui ne sont rendus par aucun service web. A cause de l’élargissement d’internet, il est rare pour un consommateur de découvrir un service web qui réponde à ses besoins. Pour cette raison, plusieurs services peuvent interagir et échanger dynamiquement des informations. L’objectif de cette interaction est l’accomplissement d’un but complexe non concevable par un seul service web. Cette agrégation des compétences pour réaliser un but commun est connue par « composition des services web ».
Principe de base d’un AG standard
Un AG standard nécessite en premier le codage de l’ensemble des paramètres du problème d’optimisation en une chaîne de longueur finie. Le principe d’un AG est simple, il s’agit de simuler l’évolution d’une population d’individus jusqu’à un critère d’arrêt. On commence par générer une population initiale d’individus (solutions) de façon aléatoire. Puis, à chaque génération, des individus sont sélectionnés, cette sélection est effectuée à partir d’une fonction objectif appelée fonction d’adaptation. Puis, les opérateurs de croisement et de mutation sont appliqués et une nouvelle population est créée. Ce processus est itéré jusqu’à un critère d’arrêt. Le critère le plus couramment utilisé est le nombre maximal de générations que l’on désire effectuer. La Figure 1.1 présente le principe de l’AG standard. L’AG débute par la génération d’une population initiale et l’évaluation de la fonction d’adaptation de tous les individus qui composent cette première population. Puis, des individus sont sélectionnés aléatoirement pour la reproduction selon le principe de la survie du plus adapté. Ensuite, des individus « enfants » (ou les descendants) sont générés en appliquant les deux opérateurs génétiques suivants : le croisement et la mutation. Ces enfants sont placés dans une nouvelle population P(t) et vont se substituer, en tout ou en partie, à la population de la génération précédente. De nouvelles populations d’individus vont ensuite se succéder, d’une génération (t) à la génération (t+1), chaque génération représentant une itération jusqu’à l’atteinte du critère d’arrêt. L’AG présenté ci-dessus est dit générationnel car tous les individus enfants générés sont placés dans une population et vont remplacer entièrement la population des individus parents.
Avantages et limites des AG’s
Un des grands avantages des algorithmes génétiques est qu’ils autorisent la prise en compte de plusieurs critères simultanément, et qu’ils parviennent à trouver de bonnes solutions sur des problèmes très complexes. L’avantage principal des algorithmes génétiques par rapport aux autres techniques d’optimisation combinatoire consiste en une combinaison de l’exploration de l’espace de recherche, et de l’exploitation des meilleures solutions disponibles à un moment donné. Ils doivent simplement déterminer entre deux solutions quelle est la meilleure, afin d’opérer leurs sélections. Leur utilisation se développe dans des domaines aussi divers que l’économie, la bioinformatique ou la vérification formelle. L’inconvénient majeur des algorithmes génétiques est le coût d’exécution important par rapport à d’autres méta-heuristiques. Les algorithmes génétiques nécessitent de nombreux calculs, en particulier au niveau de la fonction d’évaluation. Mais avec les capacités calculatoires des ordinateurs récents, ce problème a perdu de son importance. D’un autre côté, l’ajustement d’un algorithme génétique est délicat : des paramètres comme la taille de la population ou le taux de mutation sont parfois difficiles à déterminer.
Or le succès de l’évolution en dépend et plusieurs essais sont donc nécessaires, ce qui limite encore l’efficacité de l’algorithme. Néanmoins, la limite la plus importante des algorithmes génétiques est celle des optima locaux. En effet, lorsqu’une population évolue, il se peut que certains individus, qui à un instant occupent une place importante au sein de cette population, deviennent majoritaires. À ce moment, il se peut que la population converge vers cet individu et s’écarte ainsi d’individus plus intéressants mais trop éloignés de l’individu vers lequel on converge. Il faut mentionner également le caractère indéterministe des algorithmes génétiques. Comme les opérateurs génétiques utilisent des facteurs aléatoires, un algorithme génétique peut se comporter différemment pour des paramètres et populations identiques. Afin d’évaluer correctement l’algorithme, il faut l’exécuter plusieurs fois et analyser statistiquement les résultats.
|
Table des matières
Introduction Générale
Contexte
Problématique
Contribution
Organisation du mémoire
Chapitre1 Les Algorithmes Génétiques
1.1 Introduction
1.2 Algorithmes génétiques : définition
1.3 Principe de base d’un AG standard
1.4 Les concepts de base
1.4.1 Les opérateurs génétiques
1.4.2 Codage
1.5 Paramètres d’un AG
1.6 Avantages et limites des AG’s
1.7 Conclusion
Chapitre2 Architecture Orientée Services et Services Web
2.1 Introduction
2.2 Architecture Orientées Services
2.2.1 Concepts de base
2.2.2 Architecture Orientées Services : définition
2.2.3 Pile architecturale des SOA
2.2.4 Collaboration dans une architecture orientée services
2.2.5 Les rôles dans une architecture orientée services
2.3 Les services web
2.3.1 Définition
2.3.2 Caractéristiques des services web
2.3.3 Architecture des services Web
2.3.4 Cycle de vie d’un service web
2.3.5 Les langages et protocoles utilisés par les services web
2.3.6 Avantages et inconvénients des services web
2.4 Conclusion
Chapitre3 Les Services Web Sémantiques
3.1 Introduction
3.2 Présentation et objectifs des services web sémantiques
3.3 Classification et présentation des approches
3.3.1 Langages de description sémantique
3.3.2 Annotation des langages existants
3.4 Conclusion
Chapitre4 Etat de l’art de la Composition des Services Web
4.1 Introduction
4.2 Définitions et types de composition de services Web
4.2.1 Définitions
4.2.2 Types de composition de services Web
4.3 Langages de composition de services web
4.3.1 BPEL4WS (Business Process Execution Language for Web Services)
4.3.2 WS-CDL (Web Services Choreography Description Language)
4.4 Les différentes approches de la composition automatique
4.4.1 Le Workflow
4.4.2 La planification
4.4.3 Automates et Réseaux de Pétri
4.5 Synthèse des travaux de recherche
4.6 Etude comparative des approches de composition/découverte
4.7 Conclusion
Chapitre5 Composition Automatique de Services Web Sémantiques à base des AG
5.1 Introduction
5.2 Architecture de composition proposée
5.3 Le modèle sémantique (Modèle fonctionnel)
5.3.1 Représentation conceptuelle
5.3.2 Calcul de degré de similarité sémantique d’un service composite
5.4 Modèle Qualité de Service (Modèle non fonctionnel)
5.4.1 Critères de qualité des services web élémentaires
5.4.2 Critères de qualité d’un service composite
5.4.3 Calcul de la valeur QoS agrégée d’un service composite
5.4.4 Les contraintes globales non fonctionnelles
5.5 Formalisation du problème
5.6 L’Algorithme Génétique
5.6.1 Les paramètres de l’AG
5.6.2 Pseudo code de l’AG
5.7 Conclusion
Chapitre6 Implémentation et Expérimentations
6.1 Introduction
6.2 Présentation des outils technologiques utilisés
6.3 Présentation de la base des services web et l’ontologie OWL
6.4 Description du prototype
6.5 Expérimentations
6.6 Conclusion
Conclusion Générale et Perspectives
Références Bibliographiques
Télécharger le rapport complet
