Genetic algorithms in random environments: two examples

• 成果类型: Article
• 署名作者: Bérard, J
• 署名单位: Universite Claude Bernard Lyon 1
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051
• DOI: 10.1007/s00440-004-0419-y
• 发表日期: 2005
• 页码: 123-140
• 关键词: random-walks; CONVERGENCE

摘要

We study the asymptotic behavior of two mutation-selection genetic algorithms in random environments. First, the state space is a supercritical Galton-Watson tree conditioned upon non-extinction and the objective function is the distance from the root. In the second case, the state space is a regular tree and the objective function is a sample of a tree-indexed random walk. We prove that, after n steps, the algorithms find the maximum possible value of the objective function up to a finite random constant.