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

La modélisation de phénomènes biologiques qui impliquent un très grand nombre d'unités pose toujours un défi. De nombreux modèles présentent une vision globale de la dynamique moyenne du phénomène sous la forme d'un système d'équations différentielles ordinaires. C'est le cas notamment du modèle de Wilson-Cowan, qui décrit l'activité qui se propage dans un réseau de neurones biologiques. Une limite importante de ce modèle est qu'il néglige d'éventuelles corrélations entre les états de différents neurones. L'objectif premier de ce mémoire est ainsi de le généraliser afin de décrire de telles corrélations. On veut aussi mieux en comprendre les fondements mathématiques et les liens qu'il a avec des modèles semblables utilisés en épidémiologie et en écologie. Pour s'attaquer à ce problème, on construit une chaîne de Markov en temps continu qui décrit l'évolution des états des nœuds d'un graphe, et qui peut ainsi modéliser un phénomène biologique d'un point de vue microscopique. Étant donné le très grand nombre de nœuds que comporte le graphe, ce modèle microscopique est difficile à analyser. À partir du processus stochastique, on obtient alors par un moyennage un système d'équations différentielles ordinaires afin de décrire la dynamique sur le graphe d'un point de vue macroscopique. Deux applications de cette méthode sont alors présentées : l'une en épidémiologie et l'autre en neurosciences. On se concentre particulièrement sur l'application en neurosciences, qui permet de décrire la dynamique d'un réseau de neurones biologiques et de généraliser le modèle de Wilson-Cowan. En effet, on arrive à proposer deux nouveaux systèmes qui sont des extensions de ce modèle, puisqu'elles permettent de considérer des corrélations entre les états de différents neurones. On présente finalement un exemple dans lequel le comportement dynamique de l'une de ces extensions est plus près du comportement du processus stochastique que celui du modèle de Wilson-Cowan. / Modeling biological phenomena that involve a very large number of individual units is always a challenge. In this context, many models consist in a system of ordinary differential equations that gives an overview of the mean dynamics of a phenomenon. Among these is the Wilson-Cowan model, which describes the activity of a biological neural network. An important weakness of this model is that it neglects all possible correlations between the states of different neurons. The main goal of this thesis is to generalize Wilson-Cowan's model to describe such correlations. We also seek to get a better understanding of its mathematical foundations, as well as its links with other models used in epidemiology and ecology. To tackle this problem, we construct a continuous-time Markov chain to describe the evolution of the states of the nodes of a large graph. Such a process can then model a biological phenomenon from a microscopic point of view. Since the size of the graph is very large, this microscopic model is hard to analyze. Hence, from the stochastic process, we use an averaging method to obtain a system of ordinary differential equations which describes the dynamics on the graph from a macroscopic point of view. We show two applications of this method : one in epidemiology and the other in neuroscience. We focus on the application in neuroscience, which leads to a description of the dynamics a biological neural network and generalizes Wilson-Cowan's model. Indeed, we introduce two new systems which are extensions of this model since they can describe correlations between the states of different neurons. Finally, we present an example where the behavior of the stochastic process is closer to the dynamical behavior of one of the extensions than that of Wilson-Cowan's model.