Quotients of Markov chains and asymptotic properties of the stationary distribution of the Markov chain associated to an evolutionary algorithm
Quotients of Markov chains and asymptotic properties of the stationary distribution of the Markov chain associated to an evolutionary algorithm
复制标题
与进化算法相关的马尔可夫链的商和马尔可夫链平稳分布的渐近性质
DOI：
--
复制
发表时间：
2008
影响因子：
2.6
通讯作者：
L. Schmitt
中科院分区：
文献类型：
--
作者：
B. Mitavskiy;J. Rowe;A. Wright;L. Schmitt
在这项工作中，提出了一种通过使用合适的商结构来分析模拟进化算法的马尔可夫链的方法。马尔可夫链的商这一概念在进化计算文献中经常被称为“粗粒化”。我们将讨论关于状态空间上任意等价关系的不可约马尔可夫链的商的构造。商链的平稳分布与原始链的平稳分布是“一致的”。尽管商链的转移概率取决于原始链的平稳分布，但我们仍然可以利用商结构来推导原始链的平稳分布的一些相关性质。作为一个应用，我们将建立不等式，描述当突变率趋近于0时，模拟进化算法的马尔可夫链的平稳分布在均匀群体上的集中速度。还讨论了进一步的应用。与商构造方法相关的结果之一是对作者之前的会议论文[Mitavskiy等人（2006年），《模拟进化与学习，SEAL 2006会议录，计算机科学讲义第4247卷，施普林格出版社，第726 - 733页]中相应结果的重大改进。本文的相关结论都相应地得到了加强。
In this work, a method is presented for analysis of Markov chains modeling evolutionary algorithms through use of a suitable quotient construction. Such a notion of quotient of a Markov chain is frequently referred to as “coarse graining” in the evolutionary computation literature. We shall discuss the construction of a quotient of an irreducible Markov chain with respect to an arbitrary equivalence relation on the state space. The stationary distribution of the quotient chain is “coherent” with the stationary distribution of the original chain. Although the transition probabilities of the quotient chain depend on the stationary distribution of the original chain, we can still exploit the quotient construction to deduce some relevant properties of the stationary distribution of the original chain. As one application, we shall establish inequalities that describe how fast the stationary distribution of Markov chains modeling evolutionary algorithms concentrates on the uniform populations as the mutation rate converges to 0. Further applications are discussed. One of the results related to the quotient construction method is a significant improvement of the corresponding result of the authors’ previous conference paper [Mitavskiy et al. (2006) In: Simulated Evolution and Learning, Proceedings of SEAL 2006, Lecture Notes in Computer Science v. 4247, Springer Verlag, pp 726–733]. This papers implications are all strengthened accordingly.