1
$\begingroup$

What is the impact of using a:

  • low crossover rate

  • high crossover rate

  • low mutation rate

  • high mutation rate

$\endgroup$
2
$\begingroup$

The crossover rate, $p_c \in [0, 1]$, is a hyper-parameter that controls the rate at which solutions are subjected to crossover. So, the higher $p_c$, the more crossovers you perform, so the more diversity (in terms of solutions/chromosomes) you may introduce in the population. Typical values of $p_c$ are in the range $[0.5, 1.0]$. For example, in this simple implementation, I used $p_c = 0.8$. In this case, I manually searched for this value (and it didn't take me much time to make the GA find the solution I was looking for), but in other cases/problems you may need to perform some hyper-parameter optimization (e.g. with grid search).

The mutation rate, $p_m \in [0, 1]$ (also a hyper-parameter) controls the rate at which you mutate single chromosomes or the genes of single chromosomes. For example, if you have a binary chromosome of $n$ bits, you could flip the $i$th bit with probability $p_m$, for all $i$ independently. Mutation can prevent premature convergence, but, if $p_m$ is very high, the genetic algorithm becomes a random search, so the value of $p_m$ is typically not high. This paper (which you probably should read because it contains more information about the mutation and crossover operations, although it is a bit old) states that typical values are in the range $[0.005, 0.05]$, but, in this implementation, I used $p_m = 0.5$.

So, in general, higher values of these rates promote exploration at the expense of exploitation. In this sense, this is similar to the $\epsilon$ in the $\epsilon$-greedy behaviour policy in Q-learning (a famous reinforcement learning algorithm).

However, note that each of these operations may undo the other operation. For instance, let's suppose that we have the binary chromosomes $p_1 = [0, 1, 0]$ and $p_2 = [0, 0, 1]$, which we can combine by replacing (with probability $p_c$) the bit at position $i$ of $p_1$ with the bit of the chromosome $p_2$ at the same position $i$. So, after the crossover, you could get the children $c_1 = [0, 0, 0]$ and $c_2 = [0, 1, 1]$. If you perform a mutation by flipping the bits, then you could end up with the same chromosomes as the original ones, that's also one of the reasons why you may not want to have a very high mutation rate. So, it's not completely true that, the higher the mutation rate, the more you explore, because you can end up with the same solutions as before, so you have not explored anything.

You could also have an adaptive value for these parameters. See e.g. this paper for an example of such an adaptive schedule.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.