Genetic algorithm: What is the expected number of strings that are explored?

Question

My question concerns genetic algorithm searching along bit strings.

Given:

• $N$ = population size
• $l$ = length of bit strings
• $p_c$ = probability that a single crossover occur (double crossover never occur)
• $p_m$ = probability for a given bit that a mutation occur

$w(x)$, the fitness function is equal to the number of 1 in the strings. Therefore, the fitness can take any integer value between 0 and $l$ (the length of the strings).

My question is (three ways of formulating the same question):

• What is the expected total number of possibilities explored in $G$ generations?

or

• What is the expected proportion of the total possibility space (which equals $2^l$) that is explored in $G$ generations?

or

• What is the expected size of the subset of strings that have ever existed in the population during a simulation that last $G$ generations?

Secondary questions:

• How does the frequency distribution - of the total number of possibilities explored in $G$ generation - looks like?
  • is it a normal (Gauss) distribution?
  • Is it skewed?
  • ...

---

I don't quite know how complex is my question. Here are two assumptions that one would like to consider in order to ease the problem.

• one might want to assume that the population at start is not randomly drawn from the possibility space. He could assume that the whole population is made of identical strings (only one instance). For example, the string 000000000 (which length equals $l$).

• one might want to assume that $p_c = 0$

Answer 1

As I pointed out in the comments, the primary feature of interest for understanding how a genetic algorithm (or evolution, even) explores the fitness landscape is the fitness function. In this case, you specified an extremely simple fitness function with no epistasis. This was a standard assumption for analytical tractability when biology first started out (i.e. most analyses that have Fisher somewhere in the name probably assume no epistasis), but it is seen as less reasonable now. Hence, if your goal was to gain biological intuition, this question will not provide it. Since landscape with epistasis have qualitatively different dynamics.

Finally, you don't specify a selection function, so to give you a heuristic answer I will assume one that has strong selection.

First note, that at any given time, the number of genotypes you explore is bounded above by the trivial bound of $GN$. To start building a better bound, lets look at Wilf & Evans (2010) that analyzed a no-epistasis model under strong selection is a sexual population (i.e. with recombination). They showed, that it converges to equilibrium (the all $1$s string in your case) in $\Theta(\log l)$ (they actually showed a tighter characterization with a careful analysis of radix-sort, but I will leave that exploration upto you) generations (I think we have to assume that $N \in \omega(l)$). Thus, you will reach the peak very quickly.

On the way to the peak, you will explore $O(N \log l)$ genotypes. In fact, if the selection strength is very high, then we can assume that the population remains close-to monomorphic in terms of the phenotype specified as "number of ones in the genome" although polymorphic in terms of the genotype. This can give us a bound of about $O(l^2 \log l)$.

Once you reach the peak, strong selection will keep you there, and any mutants will go extinct after each generation. This means that from there on out, the population will just stay at the string $1^l$ with transient (single-generation) mutants of Hamming-distance one.

This gives us a pretty ridiculous bound $\min (O(GN), O(l^2 \log l))$. In other words, as long as you look at generations $G \in \Omega(\log l)$ you will only end up sampling an exponentially small fraction of the genome space $O(\frac{l^2 \log l}{2^l})$.

Answer 2

Unless the search space is small, the probability of hitting a genome that already has appeared can be neglected. In that case, all you need to do is to compute how many new individuals are created each generation.