My question concerns genetic algorithm searching along bit strings.
- $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?
- What is the expected proportion of the total possibility space (which equals $2^l$) that is explored in $G$ generations?
- What is the expected size of the subset of strings that have ever existed in the population during a simulation that last $G$ generations?
- 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$