Efficient Mutation for Genetic Algorithms

In the next couple of posts I'm going to investigate some ways of implementing mutation in a Genetic Algorithm (or really, any Evolutionary Algorithm). Lets start off with some well known and used ones, and lead more interesting ones (that are probably common knowledge, but I've not seen used) for later posts).

The naive and most general way to implement mutation is to generate a number in [0, 1] for each location in each individual in the population, and mutate the location if the number is less then some preset parameter (the probability of mutation). This is general in the sense that no matter the content of each location, this will tell you whether or not to perform some form of mutation operation on it. Notice that while this will certainly work on a bit vector, it may be very slow, as for a population of size m with individuals having n bits we need m*n random numbers.

Another technique I've seen is to simple find the expected number of mutations, and change that many locations. This involves generating exactly that number of random locations (probability of mutation times number of locations) and mutating only those locations. This is also general in the same sense, but it does not seem morally correct. With the first method there is a chance that no mutations will occur, and a chance that every single location will mutate. The chances are small, but the point of mutation is small random change, and I just don't feel right making it so deterministic, despite the increased performance (assuming a small mutation rate and a large number of locations). To be honest I was a little appalled the first time I saw this used. You can make it slightly better by making those changes over the whole population, as each individual will experience closer to the random probability of mutation. For example a population of size 1000 with individuals length 100 and probability of mutation 0.001 (0.1 percent) we get 1000*100*0.001 = 100 mutations spread over the while population, meaning we need only generate 100 locations to mutate by generating numbers between 0 and n*m. We can also randomly choose individuals and randomly choose locations in those individuals, so we need 200 random numbers.

Okay, that was the two most common, simplest ways to do mutation. I can think of only two other ways, and I will go over those soon.