Dans cette thèse, nous donnons une localisation en espace de la théorie des processus de Feller. Un premier objectif est d’obtenir des résultats simples et précis sur la convergence de processus de Markov. Un second objectif est d’étudier le lien entre les notions de propriété de Feller, problème de martingales et topologie de Skorokhod. Dans un premier temps nous donnons une version localisée de la topologie de Skorokhod. Nous en étudions les notions de compacité et tension. Nous faisons le lien entre les topologies de Skorokhod localisée et non localisée, grâce à la notion de changement de temps. Dans un second temps, à l’aide de la topologie de Skorokhod localisée et du changement de temps, nous étudions les problèmes de martingales. Nous montrons pour des processus l’équivalence entre, d’une part, être solution d’un problème de martingales bien posé, d’autre part, vérifier une version localisée de la propriété de Feller, et enfin, être markovien et continu en loi par rapport à sa condition initiale. Nous caractérisons la convergence en loi pour les solutions de problèmes de martingale en terme de convergence des opérateurs associés et donnons un résultat similaire pour les approximations à temps discret. Pour finir, nous appliquons la théorie des processus localement fellerien à deux exemples. Nous l’appliquons d’abord au processus de type Lévy et obtenons des résultats de convergence pour des processus à temps discret et continu, notamment des méthodes de simulation et schémas d’Euler. Nous appliquons ensuite cette même théorie aux diffusions unidimensionnelles dans des potentiels, nous obtenons des résultats de convergence de diffusions ou marches aléatoires vers des diffusions singulières. Comme conséquences, nous déduisons la convergence de marches aléatoires en milieux aléatoires vers des diffusions en potentiels aléatoires. / In this PhD thesis, we give a space localisation for the theory of Feller processes. A first objective is to obtain simple and precise results on the convergence of Markov processes. A second objective is to study the link between the notions of Feller property, martingale problem and Skorokhod topology. First we give a localised version of the Skorokhod topology. We study the notions of compactness and tightness for this topology. We make the connexion between localised and unlocalised Skorokhod topologies, by using the notion of time change. In a second step, using the localised Skorokhod topology and the time change, we study martingale problems. We show the equivalence between, on the one hand, to be solution of a well-posed martingale problem, on the other hand, to satisfy a localised version of the Feller property, and finally, to be a Markov process weakly continuous with respect to the initial condition. We characterise the weak convergence for solutions of martingale problems in terms of convergence of associated operators and give a similar result for discrete time approximations. Finally, we apply the theory of locally Feller process to some examples. We first apply it to the Lévy-type processes and obtain convergence results for discrete and continuous time processes, including simulation methods and Euler’s schemes. We then apply the same theory to one-dimensional diffusions in a potential and we obtain convergence results of diffusions or random walks towards singular diffusions. As a consequences, we deduce the convergence of random walks in random environment towards diffusions in random potential.

Thèses (Ph.D.)--Université de Sherbrooke (Canada), 1997. / Titre de l'écran-titre (visionné le 20 juin 2006). Publié aussi en version papier.

Les problèmes d’optimisation apparaissent dans presque tous les domaines scientifiques. Cependant, le processus laborieux de conception d’un optimiseur approprié peut demeurer infructueux. La question la plus ambitieuse de l’optimisation est peut-être de savoir comment concevoir des optimiseurs suffisamment flexibles pour s’adapter à un grand nombre de scénarios, tout en atteignant des performances de pointe. Dans ce travail, nous visons donner une réponse potentielle à cette question en étudiant comment faire un méta-apprentissage d’optimiseurs à base de population. Nous motivons et décrivons une modélisation commune pour la plupart des algorithmes basés sur la population, qui présentent des principes d’adaptation générale. Cette structure permet de dériver un cadre de méta-apprentissage basé sur un processus de décision de Markov partiellement observable (POMDP). Notre formulation conceptuelle fournit une méthodologie générale pour apprendre l’algorithme d’optimisation lui-même, présenté comme un problème de méta-apprentissage ou d’apprentissage pour optimiser à l’aide d’ensembles de données d’analyse comparative en boîte noire, pour former des optimiseurs polyvalents efficaces. Nous estimons une fonction d’apprentissage de méta-perte basée sur les performances d’algorithmes stochastiques. Notre analyse expérimentale indique que cette nouvelle fonction de méta-perte encourage l’algorithme appris à être efficace et robuste à une convergence prématurée. En outre, nous montrons que notre approche peut modifier le comportement de recherche d’un algorithme pour s’adapter facilement à un nouveau contexte et être efficace par rapport aux algorithmes de pointe, tels que CMA-ES. / Optimization problems appear in almost any scientific field. However, the laborious process to design a suitable optimizer may lead to an unsuccessful outcome. Perhaps the most ambitious question in optimization is how we can design optimizers that can be flexible enough to adapt to a vast number of scenarios while at the same time reaching state-of-the-art performance. In this work, we aim to give a potential answer to this question by investigating how to metalearn population-based optimizers. We motivate and describe a common structure for most population-based algorithms, which present principles for general adaptation. This structure can derive a meta-learning framework based on a Partially observable Markov decision process (POMDP). Our conceptual formulation provides a general methodology to learn the optimizer algorithm itself, framed as a meta-learning or learning-to-optimize problem using black-box benchmarking datasets to train efficient general-purpose optimizers. We estimate a meta-loss training function based on stochastic algorithms’ performance. Our experimental analysis indicates that this new meta-loss function encourages the learned algorithm to be sample efficient and robust to premature convergence. Besides, we show that our approach can alter an algorithm’s search behavior to fit easily in a new context and be sample efficient compared to state-of-the-art algorithms, such as CMA-ES.

Thèse ou mémoire avec insertion d'articles / L'objectif principal de cette thèse vise à analyser et optimiser les stratégies de la maintenance conditionnelle à adopter, pour les systèmes de production pouvant opérer en mode dégradé. Premièrement, nous commençons par analyser un système de production simple, composé d'une seule machine/composante pour l'étendre ensuite à des systèmes de production plus complexes. La machine est modélisée comme un système à plusieurs états allant du fonctionnement nominal jusqu'à la panne totale et chaque état de fonctionnement dégradé est caractérisé par ses propres taux de production et de produits non conformes, ainsi que par son propre niveau d'effets secondaires comme la quantité émise de dioxyde de carbone et le niveau de consommation de l'énergie. Lorsque l'état de la machine/composante atteint la limite du seuil acceptable, des actions préventives de maintenance sont déployées pour ramener la machine à un niveau de performance supérieur. Dans ce contexte, trois types de configurations sont considérés dans cette thèse: système série sans stocks intermédiaires, système à deux machines/composantes avec un stock intermédiaire et système série/parallèle sans stocks intermédiaires. Dans le premier type de configuration (i.e. système série), l'objectif de l'optimisation est de maximiser le taux de production du système. Les résultats numériques ont montré que, pour que le taux de production soit optimal, la maintenance préventive ne doit pas être optimisé pour chaque machine/composante individuellement, mais plutôt pour l'ensemble du système considéré, et que les actions de maintenance majeures devraient être appliquées aux machines goulot. Dans le deuxième type de configuration (i.e. système à deux machines et un stock intermédiaire), l'objectif de l'optimisation est de minimiser la somme des couts associés à la maintenance, au niveau de l'inventaire, aux produits non conformes et aux effets secondaires causés par la dégradation de la performance des machines, tout en maintenant le taux de production à un niveau élevé. Une méthode d'évaluation analytique est ainsi développée pour évaluer le taux de production. L'effet de la maintenance préventive et du niveau du stock a été analysé et les résultats montrent clairement qu'un cout minimal peut être obtenu lorsque la maintenance préventive est optimisée pour l'ensemble du système considéré. Dans le cas du troisième type de configuration (i.e. système série-parallèle multi-états), un nouveau modèle d'optimisation de la redondance intégrant la maintenance conditionnelle est proposé. L'objectif est de déterminer conjointement la structure du système et les actions de maintenance conditionnelle à un coût minimal, sous des contraintes de disponibilité. Pour estimer la disponibilité du système, un nouveau modèle combinant les chaînes de Markov et la technique de la fonction génératrice des moments universelle est développé. De plus, un algorithme génétique est proposé pour résoudre le problème d'optimisation combinatoire formulé. Les résultats obtenus ont montré que l'intégration des coûts d'exploitation dans le modèle d'optimisation donne de meilleurs résultats par rapport au modèle ne considérant que les coûts de conception et de maintenance. / The main objective of this thesis is to analyze and optimize the condition-based maintenance strategies to be adopted for production systems that can operate in degradation mode. First, we consider a production system composed of one machine/component and then extend it to more complex production systems. The machine is modeled as a multi-state system ranging from perfect functioning to total failure and each degraded operating state is characterized by its own production rate, fraction of nonconforming items produced and level of side effects such as the amount of carbon dioxide emitted and the level of energy consumption. When the last acceptable state of the component/machine is reached, preventive maintenance actions are deployed to bring the machine back to one of the previous higher levels of performance. In this context, three various types of common manufacturing systems are considered in this thesis: a serial system without intermediate buffers, two-machine/component manufacturing system with an intermediate buffer and a serial-parallel system without intermediate buffers. In the first type of configuration (i.e., a serial system), the objective of the optimization is to maximize the production rate of the system. The numerical results showed that the optimal preventive maintenance policies should be selected from the perspective of the whole system and major maintenance actions should be applied to the bottleneck machine of the system. In the second type of configuration (i.e., a system with two machines and an intermediate buffer), the objective of the optimization is to minimize the sum of the costs associated with maintenance, inventory level, nonconforming items and side effects caused by the degradation of machine's performance, while keeping the production rate at a high level. An analytical evaluation method is thus developed to evaluate the production rate. The effect of preventive maintenance and buffer level is analyzed, and the obtained results clearly show that a minimum cost can be reached when preventive maintenance is optimized for the whole system. In the case of the third type of configuration (i.e., a multi-state series-parallel system), a new model integrating condition-based maintenance and redundancy optimization is proposed. The objective is to jointly optimize, under availability constraints, the structure of the system and the conditional maintenance actions at a minimum cost. To estimate the availability of the system, a new model combining Markov chains and the universal moment generating function technique is developed. Moreover, a genetic algorithm is proposed to solve the formulated combinatorial optimization problem. The results obtained showed that the integration of operating costs in the optimization model gives better results, compared to the model considering only design and maintenance costs.

Cette thèse porte sur la modélisation probabiliste, via des processus de Markov, de communautés de joueurs accumulant leurs gains. Cette accumulation de gain s'appelle la richesse du joueur. Dans le premier modèle que nous étudions la richesse représente l'énergie d'une particule biologique. Dans le second modèle la richesse représente le patrimoine financier de l'individu. Les individus s'échangent de la richesse via des jeux stratégiques. L'objectif de cette thèse est de trouver des outils appropriés à ces modèles afin de connaître la distribution des richesses des individus. Dans une première partie, on considère un modèle biologique d'accumulation de richesses : le Dilemme du Prisonnier Démographique. Ce modèle fait intervenir deux types d'espèce : les altruistes, que l'on peut voir comme des proies, et les égoïstes, que l'on peut voir comme des prédateurs. Dans le Dilemme du Prisonnier Démographique (que l'on note DPD), les individus meurent si leur richesse devient négative et peuvent donner naissance si ils sont suffisamment riches. On répond dans ce contexte à la question centrale : " Est ce que les proies peuvent survivre sur du long terme dans un environnement hostile ? / This thesis is about the probabilistic modelisation, via Markov processes, of community of players accumulating their payoff. This payoff is called wealth. In a first model, wealth represents the energy of a biological particle. In a second model, wealth represents the financial wealth of an individual. In both models, individuals exchange wealth via strategic games. The goal of this thesis is to find appropriate tools to these models in order to know the wealth distribution of individuals. In a first part, we consider a biological wealth accumulation model called Demographic Prisoner's Dilemma (denoted DPD). In this model there are two kinds of species : the altruistic ones, that we can see as preys ; and the selfish ones, that we can see as predators. In the DPD, particles dies if their wealth become negative. They can give birth if they are rich enough. This model takes place in the evolutionnary game theory. We answer in this context to the central question : " Can prey survive in long term in an hostile environment ? "

L'objectif principal de cette thèse a été de développer des nouveaux outils mathématiques pour l'étude des phénomènes stochastiques en biologique moléculaire. Les modèles mathématiques pour la dynamique stochastique des réseaux de réactions biochimiques sont basés sur les processus de Markov à sauts. On propose des approximations hybrides pour les processus de Markov à sauts multi-échelles. En utilisant comme argument heuristique un développement limité du générateur du processus à sauts (procédé connu en chimie et en physique sous le nom de développement de Kramers-Moyal) nous identifions plusieurs types d'asymptotiques hybrides : processus déterministes par morceaux et diffusions hybrides. Le développement de Kramers-Moyal permet d'obtenir de manière systématique des modèles hybrides, qui sont simulés par la suite avec des algorithmes adaptés. Les approximations déterministes par morceaux sont étudiées avec des méthodes mathématiques rigoureuses. On montre la convergence faible du processus de Markov à sauts vers deux types de processus déterministes par morceaux : avec et sans sauts dans les variables continues. Les approximations hybrides peuvent être simplifiées davantage en utilisant des méthodes de moyennisation. On propose aussi quelques résultats dans cette direction.

Le premier chapitre est consacré à l'obtention des expressions mathématiques et au développement des outils permettant une approche systématique d'accès aux fonctions de répartition des variables aléatoires, mises en jeu dans un processus markovien homogène. Nous nous intéressons plus particulièrement à l'étude probabiliste des variables aléatoires qui représentent le nombre de transitions entre les états et le temps de séjour dans un ensemble d'états d'un processus markovien. Le second chapitre est consacré à l'application des résultats mathématiques issus du chapitre précédent, à l'évaluation du taux d'arrêt et de l'indisponibilité des structures non-redondantes et redondantes. Dans le troisième et dernier chapitre, nous proposons une méthode d'analyse économique permettant l'étude quantitative de l'influence des principales composantes de coût pendant le cycle d'expoitation du système. Cette méthode utilise le modèle markovien qui représente le comportement du système, les composantes de coût venant se superposer au modèle. Elle est appliquée à l'évaluation de la réduction des coûts d'exploitation apportée par la tolérance aux fautes.

La prise de décision dans un environnement partiellement observable est un sujet d'actualité en intelligence artificielle. Une façon d'aborder ce type de problème est d'utiliser un modèle mathématique. Notamment, les POMDPs (Partially Observable Markov Decision Process) ont fait l'objet de plusieurs recherches au cours des dernières années. Par contre, résoudre un POMDP est un problème très complexe et pour cette raison, le modèle n'a pas été utilisé abondamment. Notre objectif était de continuer les progrès ayant été réalisé lors des dernières années, avec l'espoir que nos travaux de recherches seront un pas de plus vers l'application des POMDPs dans des applications d'envergures. Dans un premier temps, nous avons développé un nouvel algorithme hors-ligne qui, sur des problèmes tests, est plus performant que les meilleurs algorithmes existants. La principale innovation vient du fait qu'il s'agit d'un algorithme stochastique alors que les algorithmes traditionnels sont déterministes. Dans un deuxième temps, nous pouvons également appliquer cet algorithme dans des environnements en-lignes. Lorsque ceux-ci revêtent une certaine particularité, notre algorithme est beaucoup plus performant que la compétition. Finalement, nous avons appliqué une version simplifiée de notre algorithme dans le cadre du projet Combat Identification du RDDC-Valcartier. / Decision making under uncertainty is a popular topic in the field of artificial intelligence. One popular way to attack such problems is by using a sound mathematical model. Notably, Partially Observable Markov Processes (POMDPs) have been the subject of extended researches over the last ten years or so. However, solving a POMDP is a very time-consuming task and for this reason, the model has not been used extensively. Our objective was to continue the tremendous progress that has been made over the last couple of years, with the hope that our work will be a step toward applying POMDPs in large-scale problems. To do so, we combined different ideas in order to produce a new algorithm called SSVI (Stochastic Search Value Iteration). Three major accomplishments were achieved throughout this research work. Firstly, we developed a new offline POMDP algorithm which, on benchmark problems, proved to be more efficient than state of the arts algorithm. The originality of our method comes from the fact that it is a stochastic algorithm, in comparison with the usual determinist algorithms. Secondly, the algorithm we developed can also be applied in a particular type of online environments, in which this algorithm outperforms by a significant margin the competition. Finally, we also applied a basic version of our algorithm in a complex military simulation in the context of the Combat Identification project from DRDC-Valcartier.

Tableau d'honneur de la Faculté des études supérieures et postdoctorales, 2011-2012 / Dans ce mémoire, nous comparons deux modèles de processus probabilistes évoluant dans un environnement continu. Les processus de Markov étiquetés sont des systèmes de transitions pour lesquels l’ensemble des états est non-dénombrable, mais qui évoluent de manière discrète dans le temps. Les mesures de probabilité définies sur l’ensemble des états peuvent avoir un support infini. Les processus hybrides sont une combinaison d’un processus à espace d’états continu qui évolue de manière continue dans le temps et une composante discrète qui intervient pour contrôler l’évolution. Les extensions probabilistes des processus hybrides présentes dans la littérature restreignent le comportement probabiliste à la composante discrète. Nous utilisons deux exemples de systèmes, un avion et un bateau, pour faire ressortir les divergences entre les deux modèles ainsi que leurs limitations, et nous définissons une généralisation qui peut modéliser fidèlement ces exemples. Nous avons également pu montrer, dans un article publié dans un atelier international, comment utiliser, dans le contexte probabiliste, la «substitution d’horloge» et l’«approximation par portrait» qui sont des techniques proposées par Henzinger et al. pour les processus non probabilistes. Ces techniques permettent, sous certaines conditions, de définir un processus probabiliste rectangulaire à partir d’un qui est non rectangulaire, rendant ainsi possible la vérification formelle de toute classe de système hybride probabiliste. / We compare two models of processes involving uncountable space. Labelled Markov processes are probabilistic transition systems that can have uncountably many states, but still make discrete time steps. The probability measures on the state space may have uncountable support and a tool has been developed for verification of such systems. Hybrid processes are a combination of a continuous space process that evolves continuously with time and of a discrete component, such as a controller. Existing extensions of Hybrid processes with probability restrict the probabilistic behavior to the discrete component. We have also shown, in a paper, how to compute for probabilistic hybrid systems, the clock approximation and linear phase-portrait approximation that have been proposed for non probabilistic processes by Henzinger et al. The techniques permit, under some conditions, to define a rectangular probabilistic process from a non rectangular one, hence allowing the model-checking of any class of systems. To highlight the differences between Labelled Markov processes and probabilistic hybrid systems, we use two examples, the ones of a boat and an aircraft, and

Cette thèse porte sur les problèmes de prise de décisions séquentielles sous incertitudes dans un système mono ou multi-agents. Les processus décisionnels de Markov offrent un modèle mathématique permettant à la fois de formaliser et de résoudre de tels problèmes. Il existe de multiple travaux proposant des techniques efficaces pour la résolution des processus décisionnels de Markov. Néanmoins, trois facteurs, dits malédictions, limitent grandement le passage à l'échelle de ces techniques. Le premier facteur, la malédiction de la dimension, est le plus connu. Il lie la complexité des algorithmes au nombre d'états du système dont la croissance est exponentielle en fonction des attributs des états. Le second facteur, la malédiction de l'historique, a été identifié plus récemment. Il lie la complexité des algorithmes à la dimension exponentielle de l'espace des historiques à prendre en compte afin de résoudre le problème. Enfin, le dernier facteur, là malédiction de la distributivité, est identifié dans cette thèse. Il lie la complexité des algorithmes à la contrainte du contrôle distribué d'un système, résultant sur une complexité doublement exponentielle. À travers nos contributions, nous proposons une réponse à chacune des trois malédictions. Nous atténuons à la fois la malédiction de la dimension et la malédiction de l'historique en exploitant les dépendances causales soit entre états soit entre historiques. Suivant cette idée, nous proposons une famille d'algorithmes exacts et approximatifs, nommée programmation dynamique topologique, visant à résoudre les processus décisionnels de Markov complètement ou partiellement observables. Ces algorithmes permettent de réduire considérablement le nombre de mises à jour d'un état ou d'un historique. Ainsi, lorsque les problèmes sont munis d'une structure topologique, la programmation dynamique topologique offre une solution efficace. Pour pallier aux effets de la malédiction de la distributivité, nous avons proposé d'étendre la planification centralisée au cadre du contrôle distribué. Nous proposons une analyse formelle des problèmes de contrôle distribué des processus décisionnels de Markov sous le regard de la planification centralisée. De cette analyse, de nombreux algorithmes de planification centralisée ont vu le jour. Parmi eux, figure point-based incremental pruning (PBIP), l'algorithme approximatif pour la résolution des processus de Markov décentralisés, le plus efficace à ce jour.