The n-city problem and other probabilistic optimisation problems.

这篇论文的目的是设计和分析概率强化学习优化算法，这些算法的灵感来自于现实生活中的现象，比如蚂蚁找到巢穴和食物来源之间的最短路径，或者一种叫做绒泡菌的黏液霉菌能够“计算”出几个食物来源之间的最佳运输网络。最新技术：蚁群优化计算机科学的一个完整分支，被称为蚁群优化（ACO）——参见Dorigo和Stutzle的《蚁群优化》一书——灵感来自于蚂蚁能够在没有通信手段的情况下找到最短路径，除了它们背后的信息素。计算机科学家通过强化学习算法模拟了这种自然现象，他们设计的算法可以解决困难的优化问题，比如找到网络中两个节点之间的最短路径。在一系列的两篇论文中，Kious， Mailler和Schapira介绍了蚂蚁寻找巢穴和食物来源之间最短路径这一现象的第一个概率模型。他们能够展示这些模型的严格结果：例如，在他们所谓的“循环擦除蚂蚁过程”中，蚂蚁确实找到了串联并行图中两个节点之间的最短路径。博士论文的主题：寻找最佳运输网络的模型绒泡菌是一种能够找到“最佳运输网络”的黏菌（参见Tero等人在2010年1月的《科学》杂志上发表的《生物启发自适应网络设计规则》）。就像蚂蚁寻找最短路径一样，人们相信这种现象可以用强化学习来建模。这篇博士论文的目的是为这种现象设计一个概率模型，并证明它确实能找到“最优”的运输网络。在这个方向上的第一个尝试是将Kious， Mailler和Schapira的蚂蚁过程推广到一个具有两个以上特殊节点的模型：巢穴和食物来源将被任意数量的“城市”取代；“蚂蚁”的目标是找到这些城市之间的最佳交通网络。博士论文的第一个目标的两个主要挑战是：1-蚂蚁过程已经很难严格分析（Kious等人只获得部分结果），我们预计这种推广将更加复杂，2-“最佳”运输网络的定义并不是唯一的。第二次尝试将是从PDE文献中设计一个概率版本的平均场版本：参见由Bonifaci， Mehlhorn和Varma编写的绒泡菌可以计算最短路径。然后，有趣的是，1-表明这种概率算法确实返回（一些）最优运输网络，2-将该算法与Kious等人的“多城市”蚂蚁过程进行比较。

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.