1 results
A weighted random walk model, with application to a genetic algorithm
- Part of
-
- Journal:
- Advances in Applied Probability / Volume 39 / Issue 2 / June 2007
- Published online by Cambridge University Press:
- 01 July 2016, pp. 550-568
- Print publication:
- June 2007
-
- Article
-
- You have access
- Export citation
-
We consider a weighted random walk model defined as follows. An n-step random walk on the integers with distribution Pn is weighted by giving the path S=(S0,…,Sn) a probability proportional to
where the function f is the so-called fitness function. In the case of power-type fitness, we prove the convergence of the renormalized path to a deterministic function with exponential speed. This function is a solution to a variational problem. In the case of the simple symmetric random walk, explicit computations are done. Our result relies on large deviations techniques and Varadhan's integral lemma. We then study an application of this model to mutation-selection dynamics on the integers where a random walk operates the mutation. This dynamics is the infinite-population limit of that of mutation-selection genetic algorithms. We prove that the population grows to ∞ and make explicit its growth speed. This is a toy model for modelling the effect of stronger selection at ∞ for genetic algorithms taking place in a noncompact space.
where the function 