Thèse (M.Sc.)--Université Laval, 2006. / Bibliogr.: f. [75]-80. Publié aussi en version électronique dans la Collection Mémoires et thèses électroniques.

Thèse de doctorat : Informatique : Tours : 2008. / Titre provenant de l'écran-titre.

Dans cette thèse nous proposons un outil d’aide à la décision multicritère qui permet aux décideurs de sélectionner un scénario optimal dans un graphe de projet qui contient toutes les alternatives de choix de conception et de réalisation d’un nouveau système, tout en tenant compte des risques inhérents aux choix réalisés. Le modèle du graphe est construit en considérant toutes les décisions collaboratives des différents acteurs impliqués dans le projet. Cet outil d’aide à la décision est basé principalement sur les techniques de l’optimisation combinatoire. En effet, nous avons choisi de travailler avec la métaheuristique ACO (algorithme d’optimisation par colonies de fourmis) vu sa capacité à fournir des solutions optimales dans un temps raisonnable. Les objectifs à minimiser sont le coût global du projet, sa durée totale de réalisation et l’incertitude sur ces critères (coût, durée). La modélisation des incertitudes a été abordée suivant deux approches différentes. La première approche consiste à modéliser l’incertitude en utilisant des intervalles simples et en la considérant comme un objectif à part entière à optimiser avec le coût et la durée. Quant à la deuxième approche, elle permet de modéliser l’incertitude sur les objectifs du projet (coût, durée) sous formes de distributions de probabilités. L’outil d’optimisation proposé dans la thèse fait partie d’un processus intégré et plus global qui se base sur les standards industriels (processus d’ingénierie système et de management de projet) qui sont largement connus et utilisés dans les entreprises. Ainsi, le travail développé dans cette thèse constitue un vrai guide pour les industriels dans leurs processus de conception et de réalisation des systèmes complexes innovants dans le domaine d’ingénierie système.

Utilisée à la fois pour l'apprentissage et l'exploitation des vecteurs conceptuels, l'analyse sémantique de texte est centrale à nos recherches. L'amélioration qualitative du processus d'analyse entraîne celle des vecteurs. En retour, cette meilleure pertinence a un effet positif sur l'analyse. Parmi les différentes voies à explorer pour obtenir ce cercle vertueux, l'une des pistes les plus intéressantes semble être la découverte puis l'exploitation des relations lexicales entre les mots du texte. Ces relations, parmi lesquelles la synonymie, l'antonymie, l'hyperonymie, la bonification ou l'intensification, sont modélisables sous la forme de fonctions lexicales. Énoncées essentiellement dans un cadre de production par Igor Mel'čuk, nous cherchons, dans cette thèse, à les adapter à un cadre d'analyse. Nous introduisons ici deux classes de Fonctions Lexicales d'Analyse. Les premières, les FLA de construction permettent de fabriquer un vecteur conceptuel à partir des informations lexicales disponibles. Les secondes, les FLA d'évaluation permettent de mesurer la pertinence d'une relation lexicale entre plusieurs termes. Ces dernières sont modélisables grâce à des informations thématiques (vecteurs conceptuels) et/ou grâce à des informations lexicales (relations symboliques entre les objets lexicaux).<br /><br />Les informations lexicales sont issues de la base lexicale sémantique dont nous introduisons l'architecture à trois niveaux d'objets lexicaux (item lexical, acception, lexie). Elles sont matérialisées sous la forme de Relations Lexicales Valuées qui traduisent la probabilité d'existence de la relation entre les objets. L'utilité de ces relations a pu être mis en évidence pour l'analyse sémantique grâce à l'utilisation du paradigme des algorithmes à fourmis. Le modèle introduit dans cette thèse, utilise à la fois les vecteurs conceptuels et les relations du réseau lexical pour résoudre une partie des problèmes posés lors d'une analyse sémantique.<br /><br />Tous nos outils ont été implémentés en Java. Ils reposent sur Blexisma (Base LEXIcale Sémantique Multi-Agent) une architecture multi-agent élaborée au cours de cette thèse dont l'objectif est d'intégrer tout élément lui permettant de créer, d'améliorer et d'exploiter une ou plusieurs Bases Lexicales Sémantiques. Les expériences menées ont montré la faisabilité de cette approche, sa pertinence en termes d'amélioration globale de l'analyse et ouvert des perspectives de recherches fort intéressantes.

La recherche proposée est orientée vers l'étude de descriptions verbales d'itinéraires dans le but de géolocaliser des itinéraires décrits au sein de systèmes géo-référencés, avec une application à un contexte de course d'orientation dans un environnement naturel. Il s'agit explicitement de faire un lien conceptuel, structurel et logique entre une description verbale d'itinéraire et une représentation spatialisée. Une étude des descriptions verbales d'itinéraire produites lors d'expériences de course d'orientation a permis de définir une modélisation formelle par extraction des informations statiques et dynamiques d'un itinéraire décrit. La représentation logique dérivée s'appuie sur un modèle de graphe où les entités de référence sont les repères et les actions de déplacement. Elle permet en particulier une confrontation avec les démarches usuelles de qualification d'itinéraires en milieu urbain. Cette modélisation sert ensuite de support à une proposition d'algorithme de recherche et de géolocalisation d'itinéraire développée à partir des principes des algorithmes de colonies de fourmis. La démarche de recherche est validée par un prototype expérimental qui combine une modélisation d'itinéraire avec une recherche de parcours optimal. Ce prototype est illustré par une série de tests expérimentaux et des études de performance.

Dans cette thèse, nous nous intéressons à l'étude des capacités de la méta heuristique d'optimisation par colonie de fourmis (Ant Colony Optimization - ACO) pour résoudre des problèmes d'optimisation combinatoire multi-objectif. Dans ce cadre, nous avons proposé une taxonomie des algorithmes ACO proposés dans la littérature pour résoudre des problèmes de ce type. Nous avons mené, par la suite, une étude expérimentale de différentes stratégies phéromonales pour le cas du problème du sac à dos multidimensionnel mono-objectif. Enfin,nous avons proposé un algorithme ACO générique pour résoudre des problèmes d'optimisation multi-objectif. Cet algorithme est paramétré par le nombre de colonies de fourmis et le nombre de structures de phéromone considérées. Il permet de tester et de comparer, dans un même cadre,plusieurs approches. Nous avons proposé six variantes de cet algorithme dont trois présentent de nouvelles approches et trois autres reprennent des approches existantes. Nous avons appliqué et comparé ces variantes au problème du sac à dos multidimensionnel multi-objectif

Tableau d’honneur de la Faculté des études supérieures et postdoctorales, 2010-2011 / Comment utiliser la théorie de la recherche et la planification de chemins pour formuler et résoudre un problème de détection dans le contexte de la recherche et sauvetage en milieu terrestre considérant des aspects pratiques tels que les contraintes de visibilité découlant du terrain? Pour répondre à cette question, nous présentons une nouvelle formulation introduisant les contraintes de visibilité du chercheur (le problème de planification du chemin optimal du chercheur avec visibilité ou OSPV). De plus, nous présentons une extension multicritère du problème. Dans un premier temps, l'efficacité du plan de recherche est quantifiée par la probabilité de retrouver l'objet recherché; un programme en nombres entiers mixte est comparé à Ant Search, notre adaptation de l'optimisation par colonies de fourmis. Ensuite, l'extension multicritère intègre les aspects de sécurité du chercheur et de complexité du plan; Ant Search est alors étendu pour introduire Pareto Ant Search et Lexicographie Ant Search.

Dans ce travail, nous considérons un système multi-états série-parallèle dont les composantes sont sujettes à des réparations minimales et à des actions de maintenance préventive imparfaite. Le système peut avoir différents niveaux de performance, allant d'un fonctionnement parfait à une défaillance complète. Les composantes peuvent être en opération ou hors d'usage. La fiabilité d'un système multi-états est définie par sa probabilité de satisfaction d'une demande donnée. La fiabilité de chaque composante est caractérisée par sa fonction de hasard. Chaque action de maintenance préventive conduit à une réduction de l'âge effectif de l'équipement. Elle est caractérisée par son coefficient de réduction d'âge et par son coût. L'objectif consiste à planifier des actions de maintenance préventive pendant la durée de vie du système multi- états, de façon à minimiser le coût total moyen de maintenance, sous une contrainte de fiabilité. Il s'agit d'un problème d'optimisation combinatoire qui a été auparavant formulé et résolu par les algorithmes génétiques dans [47]. Dans ce travail, ce problème est résolu en utilisant une méthode heuristique basée sur le méta-heuristique des colonies de fourmis. Inspirée par les études sur le comportement des fournis réelles, cette méthode possède plusieurs caractéristiques intéressantes et constitue une approche intéressante pour résoudre les problèmes d'optimisation de la fiabilité. Une technique à base de la fonction de génération universelle est implémentée pour évaluer la fiabilité du système multi-états. En combinant la technique de la fonction de génération universelle et l'optimisation par colonies de fourmis, l'algorithme proposé permet d'obtenir efficacement une séquence quasi-optimale des actions de maintenance. L'approche développée et testée dans ce travail constitue une alternative intéressante pour la résolution du problème d'optimisation de la maintenance préventive imparfaite pour les systèmes multi-états. Des exemples numériques de la détermination de plans quasi-optimaux de maintenance préventive sont également présentés. / In this work, we consider a series-parallel multi-state System composed of elements subjected to minimal repair and imperfect preventive maintenance actions. The System has a range of performance levels from perfect functioning to complete failure. Components may experience two possible states: good and failed. Multi-state System reliability is defined as the System ability to satisfy given demand. The reliability of each element is characterized by its hazard function. Each preventive maintenance action may affect the effective age of equipment, and is characterized by its age reduction coefficient and cost. The objective is to determine a minimal average cost plan of preventive maintenance actions during multi-state System lifetime, under the constraint of providing a required level of System reliability. This is a combinatorial optimization problem which has been previously formulated and solved by genetic algorithms in [47]. In this work, this problem is solved by using a heuristic based on ant colony meta-heuristic. Inspired by studies on the behaviour of real ants, this method has many interesting characteristics and approaches for solving reliability optimization problems. A universal generating function technique is implemented to evaluate System reliability. By combining the use of the universal generating function technique and ant colony optimization, the proposed algorithm obtains efficiently quasi-optimal sequence of maintenance actions. The approach developed and tested in this work constitutes an interesting alternative approach to solve the imperfect preventive maintenance problem for multi-state Systems. Numerical examples of the determination of quasi-optimal preventive maintenance plans are also presented.

Dans le cadre de cette thèse, nous nous sommes intéressés à la mise en œuvre d'algorithmes auto-adaptatifs d'Intelligence Collective pour la résolution de problèmes d'optimisation modélisés dans un langage de Programmation par contraintes (PPC). Nous avons porté une attention particulière à la famille d'algorithmes de type " Ant Colony Optimization " (ACO). Nous avons développé trois contributions, à savoir : (1) Intégration des algorithmes de type ACO dans un langage de programmation par contraintes pour la résolution de problèmes de satisfaction de contraintes; (2) Proposition d'un algorithme hybride et générique où ACO est couplé à une approche complète pour résoudre des problèmes d'optimisation combinatoires (3) Proposition d'une stratégie capable d'adapter dynamiquement les paramètres de ACO.

Cette thèse s’intéresse à une problématique ayant de nombreuses applications pratiques, à savoir la comparaison automatique d’objets et l’évaluation de la similarité. Lorsque les objets sont modélisés par des graphes, ce problème de comparaison automatique d’objets se ramène à un problème d’appariement de graphes, c’est-à-dire, chercher une mise en correspondance entre les sommets des graphes permettant de retrouver le plus grand nombre de caractéristiques communes. Différentes classes existent allant de la plus restrictive à la plus générale. Dans la plus restrictive isomorphisme de (sous-) graphes, il s’agit de chercher un appariement exact entre les sommets des graphes de manière à prouver que les deux graphes possèdent une structure identique ou que l’un d’eux est inclus dans l’autre, un sommet étant apparié avec au plus un sommet. Dans la plus générale (appariement multivoque), l’objectif n’est plus de trouver un appariement exact mais le meilleur appariement, c’est-à-dire, celui qui préserve un maximum de sommets et d’arcs, un sommet pouvant être apparié à un ensemble de sommets. Nous nous intéressons au problème de la recherche du meilleur appariement multivoque, ce problème étant plus général que les problèmes d’appariement restrictifs. Sa résolution est clairement un défi tant par la difficulté du problème que par l’importance de ses applications. Pour relever ce défi, nous proposons d’étudier les capacités de l’optimisation par colonies de fourmis (ACO). Notre étude est menée dans deux contextes : un contexte statique, où le problème est figé, et un contexte dynamique, où les graphes à comparer, les contraintes à respecter ainsi que les critères définissant la qualité des appariements changent régulièrement de sorte que la solution doit être dynamiquement adaptée. Un premier objectif, de cette thèse, est de proposer l’algorithme ACO générique pour la résolution des problèmes d’appariement de graphes. Plusieurs points clés sont étudiés dans cet algorithme, à savoir : l’influence des paramètres sur la qualité des solutions construites, l’influence de la stratégie phéromonale et du facteur heuristique, et l’hybridation avec une technique de recherche locale. Un deuxième objectif est de proposer un algorithme ACO générique pour résoudre des problèmes d’optimisation dynamiques. L’algorithme proposé est appliqué et expérimenté à quelques problèmes dynamiques, à savoir : l’appariement de graphes, le problème du sac à dos multidimensionnel, et le voyageur de commerce / The thesis addresses the problematic of comparing objects and similarity measuring. If objects are described by graphs, so that measuring objects similarity turns into determining graph similarity, i.e., matching graph vertices to identify their common features and their differences. Different classes of graph matching have been proposed going on the most restrictive ones to the most general. In restrictive graph matching (graph or sub-graph isomorphism), the objective is to show graph equivalence or inclusion, a vertex in a graph may be matched with one vertex at most on the other graph. In general graph matching (multivalent matching), the goal is not yet to find an “exact” matching (a matching which preserves all vertices and edges), but to look for a “best” matching (a matching which preserves a maximum number of vertices and edges), a vertex in one graph may be matched with a set of vertices in the other graph. In our work, we consider the problem of searching the best multivalent matching which is a NP-hard optimization problem. More precisely, we propose to investigate the ability if the ant colony optimization meta-heuristic (ACO). Two cases are considered in our study: the static case where the problem remains invariant through time and the dynamic case where graphs to compare constrained to satisfy and the criterions defining matching quality may change over the time, so that solutions must be dynamically adapted to the changes. A first goal of this thesis is to propose a generic ACO algorithm for solving graph matching problems. Different key points, like the pheromonal strategy to be used, the heuristic factor and the use of a local search procedure, are studied. A second goal of this work is to propose a generic ACO algorithm for solving dynamic optimization problems. The proposed algorithm will be applied and experimentally studied on three different dynamic problems: graph matching problem, multi-dimensional knapsack problem and the travelling salesman problem