Soutenance mémoire
Algorithmes d’Optimisation Non Classiques (Métaheuristiques)
XML
XML (eXtensible Markup Language) est un langage « extensible » contenant des « balises » comme HTML8. XML décrit la signification des données codées, indépendamment de la façon de les représenter. Contrairement à HTML dont les balises n’ont pour objet que de définir la présentation du document, XML permet d’inventer à volonté de nouvelles balises pour décrire, de façon arborescente, toutes les informations élémentaires expliquant la signification des données. Son objectif initial est de faciliter l’échange automatisé de contenus entre systèmes d’informations hétérogènes. XML contient aussi un aspect supplémentaire appelé « schéma », qui précise la structure des balises pour qu’un document soit valide. Il est ainsi possible de restreindre les données acceptées dans un document. Un document XML peut contenir d’autres documents XML. Pour éviter toute confusion entre les balises utilisées, chaque document contient un « espace de noms », ce qui rend ainsi les balises uniques à l’intérieur d’un document.
Langage de description WSDL
WSDL (Web Service Description Language) est un langage de la famille XML permettant de décrire les types de données supportées et les fonctions offertes par un Service Web. L‟objectif est de fournir la description, en XML, des services indépendamment de la plateforme et du langage utilisés et sous une forme que des personnes ou des programmes peuvent interpréter. Il est soutenu principalement par Ariba, Intel, IBM et Microsoft [Delacrétaz, 03]. Sa version 1.1 a été proposée en 2001 au W3C pour standardisation, mais elle n‟a pas été approuvée contrairement à la version 2.0 qui est une recommandation officielle depuis 2007. [www3] WSDL a été créé dans le but de fournir une description unifiée des services Web. Il décrit précisément quelles méthodes du service sont accessibles, et quels sont les types de leurs paramètres. Ce qui permet de décharger les utilisateurs des détails techniques de réalisation d‟un appel. Le langage WSDL s‟appuie sur le format XML pour décrire des services réseau sous forme d‟ensembles de noeuds de communication d‟extrémités qui traitent des messages contenant de l‟information sur les données échangées ou sur la procédure par laquelle cet échange est fait.
Algorithmes d’optimisation
Non Classiques (Métaheuristiques) D‟une manière générale, l‟efficacité des méthodes de résolution classiques est malheureusement dépendante d‟un certain nombre d‟hypothèses et de contraintes concernant le problème posé. Dans notre cas d‟étude, ces contraintes sont liées principalement à la forme de la fonction de distribution des données à traiter. Lorsqu‟on veut proposer une nouvelle méthode de résolution de problèmes, il faut souvent une source d‟inspiration. Celle-ci, peut être totalement imaginaire et n‟est pas obligée de faire référence au monde réel, comme par exemple, les méthodes mathématiques abstraites, ou peut au contraire, être issue de la modélisation des systèmes naturels. Il s‟agit dans ce dernier cas, d‟imiter et d‟adapter les concepts du monde des vivants pour la résolution de divers problèmes. Parmi ces derniers, se trouve le problème de l‟organisation, du groupement et de la classification, qui se rencontre souvent chez les animaux et dans les systèmes biologiques. En effet, la source d‟inspiration que constitue la biologie a de plus en plus de succès dans une branche de l‟intelligence artificielle, que l‟on nomme la biomimétique.
Motivation
Pour de nombreux problèmes, il n‟existe pas de solution déterministe qui donne le résultat en un temps raisonnable, et ceci malgré la création d’ordinateurs de plus en plus performants. Pour pallier à ce problème, on a recours à des méthodes dites heuristiques, c‟est-à-dire des méthodes qui fournissent une solution approchée. Toutefois, il faut reproduire le processus sur plusieurs itérations pour tendre vers une solution acceptable. On retrouve parmi ces heuristiques, certains algorithmes qui possèdent un principe générique adaptable et qui s‟applique donc à plusieurs problèmes d‟optimisation. On les appelle des métaheuristiques. La plus courante est la descente stochastique : on part d‟une solution initiale, on la compare à tous ses voisins en conservant à chaque fois le meilleur résultat. L‟optimisation par essaim particulaire, qui dérive de la descente stochastique, entre dans cette famille d’algorithmes. Elle s‟inspire fortement des relations grégaires des oiseaux migrateurs qui doivent parcourir des longues distances et qui doivent donc optimiser leurs déplacements en termes d‟énergie dépensée, comme par exemple la formation en V.
Quelques métaheuristiques pour l’optimisation
Les métaheuristiques sont une famille d’algorithmes stochastiques destinés à la résolution des problèmes d’optimisation. Leur particularité réside dans le fait que celles-ci sont adaptables à un grand nombre de problèmes sans changements majeurs dans leurs algorithmes, d’où le qualificatif méta. Leur capacité à optimiser un problème à partir d’un nombre minimal d‟informations n‟est contre balancée par le fait qu’elles n’offrent aucune garantie quant à l’optimalité de la meilleure solution trouvée. Seule une approximation de l’optimum global est donnée. Cependant, du point de vue de la recherche opérationnelle, ce constat n’est pas forcément un désavantage, étant donné que l’on préférera toujours une approximation de l’optimum global trouvée rapidement qu’une valeur exacte trouvée dans un temps rédhibitoire. Les métaheuristiques sont des méthodes qui ont, en général, un comportement itératif, c’est-à-dire que le même schéma est reproduit un certain nombre de fois au cours de l’optimisation, et qui sont ‟‟directes‟‟, dans le sens où elles ne font pas appel au calcul du gradient de la fonction. Ces méthodes tirent leur efficacité du fait qu’elles sont moins facilement piégeables dans des optima locaux, car elles acceptent, au cours du traitement, des dégradations de la fonction objective et la recherche est souvent menée par une population de points et non un point unique. De plus, de par leur variété et leur capacité à résoudre des problèmes très divers, les métaheuristiques sont assez facilement sujettes à extensions.
Colonies de fourmis Cette approche, due à Dorigo et ses collaborateurs [Colorni,91], s‟efforce de simuler la capacité collective de résolution de certains problèmes, observée chez une colonie de fourmis dont les membres sont pourtant individuellement dotés de facultés très limitées. Les algorithmes de colonies de fourmis sont nés d’une constatation simple : les insectes sociaux, et en particulier les fourmis, résolvent naturellement des problèmes complexes. Un tel comportement est possible car les fourmis communiquent entre elles de manière indirecte par le dépôt de substances chimiques, appelées phéromones, sur le sol. Ce type de communication indirecte est appelé stigmergie. La principale illustration de ce constat est donnée par la Figure (2.1). On voit sur cette figure que, si un obstacle est introduit sur le chemin des fourmis, les fourmis vont, après une phase de recherche, avoir tendance à toutes emprunter le plus court chemin entre le nid et l’obstacle [Goss,89]. Plus le taux de phéromone à un endroit donné est important, plus une fourmi va avoir tendance à être attirée par cette zone. Les fourmis qui sont arrivées le plus rapidement au nid en passant par la source de nourriture sont celles qui ont emprunté la branche la plus courte du trajet. Il en découle donc que la quantité de phéromones sur ce trajet est plus importante que sur le trajet plus long. De ce fait, le plus court chemin a une probabilité plus grande d’être emprunté par les fourmis que les autres chemins et sera donc, à terme, emprunté par toutes les fourmis.
Etat de l’art Plusieurs chercheurs ont créé des modèles interprétant le mouvement des vols d‟oiseaux et des bancs de poissons. Plus particulièrement, Reynolds [Reynolds, 87] et Heppner et al. [Heppner, 90] ont présenté des simulations sur un vol d‟oiseaux. Reynolds était intrigué par l‟aspect esthétique du déplacement des oiseaux en groupe et Heppner, un zoologue, était intéressé à comprendre les règles permettant à un grand nombre d‟oiseaux de voler en groupe : soit de voler sans se heurter, de changer soudainement de direction, de s‟écarter et de se rapprocher de nouveau. Cette étude a grandement inspiré le développement de l‟algorithme PSO. En effet, lors de simulations des modèles mathématiques décrivant les vols d‟oiseaux, Wilson [Wilson, 75] a suggéré que ces types de modèles pourraient très bien s‟appliquer à la recherche de points caractéristiques dans un espace de recherche. Sa réflexion se base sur le fait que, lors de l’installation d’une mangeoire à oiseaux dans une cour, même si aucun oiseau ne l’a jamais visitée, après quelques heures de patience un grand nombre d‟oiseaux viendront y manger. Lors des simulations de Wilson, la volée d‟oiseaux cherchait une mangeoire dans un espace donné et finissait par découvrir son emplacement. En utilisant les algorithmes de modélisation de Heppner [Heppner, 90] et de Reynolds [Reynolds, 87], et en modifiant le modèle mathématique de Wilson [Wilson, 75], Kennedy et Eberhart [Kennedy & Eberhart, 95] ont transformé le tout en un vol d‟oiseaux cherchant la « mangeoire » la plus grosse dans un lot de mangeoires contenues dans une région prédéterminée. L‟algorithme d‟optimisation PSO a ainsi vu le jour.
|
Table des matières
Liste des figures
Liste des tableaux
Introduction Générale
Chapitre 1: Web Services
1.Introduction
2.L‟origine des Services Web
3.Services Web
3.1. Définitions
3.2. Caractéristiques des services web
3.3. Architecture et spécification des services web
3.3.1. Protocole de transport SOAP
3.3.2. Langage de description WSDL
3.3.3. Annuaire UDDI
4.Conclusion
Chapitre 2: Algorithmes d’Optimisation Non Classiques (Métaheuristiques)
1.Introduction
2.Motivation
3.Problème d‟optimisation
3.1. Définition
3.2. Quelques métaheuristiques pour l‟optimisation
3.2.1 Recherche Tabou
3.2.2 Colonies de fourmis
3.2.3. Optimisation par essaim particulaire
4.Algorithme a essaim particulaire
4.1. Etat de l‟art
4.2. Modèle de Reynolds
4.3. Modèle de Kennedy et Eberhart
Conclusion
Chapitre 3: Conception et Implémentation
1.Introduction
2.Sélection des services web
2.1. Qualité des services web
2.2. Critères de qualité de services
2.3. Calcul du qualité du web service composite
2.4. Fonction objective
2.5. Algorithme d‟optimisation
2.5.1. La base de donnée
2.5.2. La configuration de l‟essaim
2.5.3. Les étapes de l‟algorithme
3.Conception de l‟application
3.1. Processus de développement logiciel
3.2. Processus unifié (Unified Process)
3.3. Modélisation avec UML
3.3.1. Diagramme de cas d‟utilisation
3.3.2. Diagramme de séquence
4.Outils et environnement de développement
4.1. Langage JAVA
4.2. Netbeans
4.3. Excel
5.Présentation du prototype
5.1. Présentation de l‟IHM
5.2. Les expérimentations
Conclusion
Conclusion Générale
Références bibliographiques
