Boris Mitavskiy, Jonathan Rowe and Chris Cannings
The purpose of this paper is to establish a version of a theorem that originated from population genetics and has been later adopted in evolutionary computation theory that will…
Abstract
Purpose
The purpose of this paper is to establish a version of a theorem that originated from population genetics and has been later adopted in evolutionary computation theory that will lead to novel Monte‐Carlo sampling algorithms that provably increase the AI potential.
Design/methodology/approach
In the current paper the authors set up a mathematical framework, state and prove a version of a Geiringer‐like theorem that is very well‐suited for the development of Mote‐Carlo sampling algorithms to cope with randomness and incomplete information to make decisions.
Findings
This work establishes an important theoretical link between classical population genetics, evolutionary computation theory and model free reinforcement learning methodology. Not only may the theory explain the success of the currently existing Monte‐Carlo tree sampling methodology, but it also leads to the development of novel Monte‐Carlo sampling techniques guided by rigorous mathematical foundation.
Practical implications
The theoretical foundations established in the current work provide guidance for the design of powerful Monte‐Carlo sampling algorithms in model free reinforcement learning, to tackle numerous problems in computational intelligence.
Originality/value
Establishing a Geiringer‐like theorem with non‐homologous recombination was a long‐standing open problem in evolutionary computation theory. Apart from overcoming this challenge, in a mathematically elegant fashion and establishing a rather general and powerful version of the theorem, this work leads directly to the development of novel provably powerful algorithms for decision making in the environment involving randomness, hidden or incomplete information.
Details
Keywords
Boris Mitavskiy, Jonathan Rowe and Chris Cannings
A variety of phenomena such as world wide web, social or business networks, interactions are modelled by various kinds of networks (such as the scale free or preferential…
Abstract
Purpose
A variety of phenomena such as world wide web, social or business networks, interactions are modelled by various kinds of networks (such as the scale free or preferential attachment networks). However, due to the model‐specific requirements one may want to rewire the network to optimize the communication among the various nodes while not overloading the number of channels (i.e. preserving the number of edges). The purpose of this paper is to present a formal framework for this problem and to examine a family of local search strategies to cope with it.
Design/methodology/approach
This is mostly theoretical work. The authors use rigorous mathematical framework to set‐up the model and then we prove some interesting theorems about it which pertain to various local search algorithms that work by rerouting the network.
Findings
This paper proves that in cases when every pair of nodes is sampled with non‐zero probability then the algorithm is ergodic in the sense that it samples every possible network on the specified set of nodes and having a specified number of edges with nonzero probability. Incidentally, the ergodicity result led to the construction of a class of algorithms for sampling graphs with a specified number of edges over a specified set of nodes uniformly at random and opened some other challenging and important questions for future considerations.
Originality/value
The measure‐theoretic framework presented in the current paper is original and rather general. It allows one to obtain new points of view on the problem.