The n-city problem and other probabilistic optimisation problems.

点击翻译按钮获取中文摘要

The aim of this thesis is to design and analyse probabilistic reinforcement-learning optimisation algorithms inspired by real-life phenomena such as ants finding the shortest path between their nest and a source of food, or a slime mold called physarum being able to ``compute'' optimal transport networks between several sources of food.State of the Art: Ant Colony OptimisationA whole branch of computer science, called Ant Colony Optimisation (ACO) - see the book ACO of Dorigo and Stutzle - is inspired by the phenomenon of ants being able to find shortest paths with no means of communication besides the pheromones they lay behind them. This natural phenomenon is modelled by computer scientists by reinforcement-learning algorithms, and the algorithms they have designed can solve difficult optimisation problems such as finding the shortest paths between two nodes in a network.In a series of two papers, Kious, Mailler and Schapira have introduced the first probabilistic model for this phenomenon of ants finding the shortest paths between their nest and a source of food. They are able to show rigorous results about these models: eg, in what they call the ``loop-erased ants process'', the ants do indeed find the shortest paths between two nodes in a series-parallel graph.Subject of the PhD thesis: a model for finding optimal transport networksThe physarum is a slime mold capable of finding ``optimal transport networks'' (see Rules for Biologically Inspired Adaptive Network Design, by Tero et al, Science, January 2010). Just as ants finding shortest paths, it is believed that this phenomenon can be modelled using reinforcement-learning. The aim of this PhD thesis is to design a probabilistic model for this phenomenon and prove that it indeed finds ``optimal'' transport networks.The first attempt in this direction will be to generalise the ant process of Kious, Mailler and Schapira to a model with more than two special nodes: the nest and the source of food will be replaced by an arbitrary number of ``cities''; the aim of the ``ants'' will be to find the optimal transport network between these cities. The two main challenges of this first objective of the PhD thesis are: 1- the ants process is already difficult to analyse rigorously (Kious et al only obtain partial results) and we expect this generalisation to be even more intricate, and 2- the definition of an ``optimal'' transport network is not unique.The second attempt will be to design a probabilistic version of a mean-field version from the PDE literature: see Physarum Can Compute Shortest Paths, by Bonifaci, Mehlhorn, and Varma. It will then be interesting to 1- show that this probabilistic algorithm indeed return (some) optimal transport network, and 2- compare this algorithm to the ``multi-city'' version of the ants process of Kious et al.