Genetic Algorithm: Higher Mutation Rate leads to lower run time

Question

I implemented a genetic algorithm to solve an enhanced Traveling Salesman Problem (the weight of the edges changes with the time of the day). Currently I'm evaluating the different parameters of my simulation and I stumbled upon a correlation I can't explain to myself:

A higher mutation rate leads to a lower run time. Personally I would assume the contrary, since a higher mutation rate produces more operations. (25% Mutation Rate is 12% faster than 5%)

The best results are achieved by a mutation rate of 8% (5% is better than 10% and 25% performs worst (except 0%)) A lower fitness value ist better.

The iteration count is set by the generation parameter which is set to 10.000 in all test cases.

Each test case is executed 10 times.

My implementation (in python) of the mutation looks like this:

def mutate(self,p):
    for i in self.inhabitants:
        r = random()
        if r <= p:
            i.mutate()

p is the mutation rate

The mutation looks like this

def mutate(self):
    r1 = randint(0,self.locations.size()-1)
    r2 = randint(0,self.locations.size()-1)
    self.locations.swap(r1,r2)

Why does a higher mutation rate lead to faster execution time?

Edit: I actually ran the same tests on my Raspberry Pi (which is 9 times slower) and it results in the same outcome:

Sheepshearing

Less run time means less operations being performed (generally speaking). Higher "p" will lead to "i.mutate()" being called more often. Does "i.mutate()" change the "self.inhabitants" variable? Could you show the code for that function? (or a minimum working example if possible) – Offload

Also could you try to create a local copy of self.inhabitants in the function mutate, and loop the copy instead? – Offload

@Offload I added the code for the mutation. I don't understand what you mean with loop the copy. – Sheepshearing

The mutation function does not do anything to self.inhabitants apparently: By local I mean "local = self.inhabitants" and than "for i in local: ...". Also when and where do you change the value for self.inhabitants? – Offload

Why do you think it doesn't do anything? It swaps two locations. If nothing would happen, we would see no difference in the result/fitness. – Sheepshearing

I meant that nothing happens to "self.inhabitants" variable (more or less individuals). Or if it does it's not obvious from the "mutate" function. My suspicion is that somehow during your mutate methods you are reducing the size of your population (self.inhabitants). That's why I advised you to create a local copy for the loop. So if self.inhabitants is changed you'll still have the local copy working fully. – Offload

How are you doing the timing? This might be an artifact due to something like how the interpreter is doing its allocations. An interesting experiment would be to reverse the order in which you are testing the mutation rates -- time the higher rates before you time the lower rates. – Hygienics

@Offload If I would reduce the population size (which is set to 10) I would have noticed very fast, because the algorithm crashes (It cannot find two parents, etc.) @JohnColeman I use start_time = time.time() before I run the simulation and stop it with t = (time.time() - start_time) - that's a gread idea, I'm going to try this as soon as my current tests stop. – Sheepshearing

I haven't seen your entire algorithm but I wouldn't be too sure. In any case another alternative is to make a global counter for the loop. The counter starts at 0 when you start your script a is never reinitialized. Update the counter inside the loop. See how many times the counter was used for each test. – Offload

@Offload I tested your proposal in another way: In each iteration I checked if the population size is still the same, and it actually stays the same, so there are no inhabitants that are removed. – Sheepshearing

@Offload I also set up a counter. Regardless of the mutation rate it's 10.000 at the end. (with 10.000 generations) – Sheepshearing

Where did you update the counter? It should depend on the number of inhabitants as well as the number of generations. The time is being spent in something and calling i.mutate() can't be faster than doing nothing. – Offload

@Offload I now set up a counter that counts the mutations. And it is as expected ~5 times higher with mutation rate 5 times higher. Maybe there's something other. The next thing I'll try is to reverse the test order. – Sheepshearing

Perhaps the evaluation function takes longer to evaluate in some cases than others and that this is what you are seeing. Perhaps you can profile runs with different parameters and see what part of the code is taking up the extra cpu cycles for the smaller mutation rates. See docs.python.org/2/library/profile.html – Hygienics

Answer 1

It is impossible to know without seeing your full code, but the following seems plausible:

When the mutation rate is lower then, after a few generations, the population becomes much more homogenous than it does when the mutation rate is higher. Underneath the assumption that you are using some variation of roulette wheel sampling, a more homogeneous population means that each "spin" of the roulette wheel takes on average longer than when you have a more varied population (where relatively few members will dominate the distribution of fitnesses and hence tend to be selected after scanning over fewer members of the population).

To be more certain, you could use a profiling tool such as cProfile to see exactly where those CPU cycles are going.

Hygienics

Answer 2

Each cycle i of mutations has a probability p_i of providing an acceptable solution, and the time it takes to evaluate a cycle is T_i. Both p_i and T_i increase with the mutation rate. The expected running time of your algorithm is thus a sum Σ p_iT_i over the expected number of cycles required to find the answer. A higher mutation rate increases the size of each term, but decreases the number of terms to sum. There is an optimal mutation rate that minimizes this sum.

Widgeon

Could be, that I don't understand the answer fully, but the expected number of cycles doesn't decrease since it's determined by the generation parameter, which states how many times crossover and mutation is performed. – Sheepshearing

@Widgeon how do you know mutation decreases the number of terms to sum? I'm not seeing anything pointing to that. – Offload

Ah, I missed that the generation count was fixed; I was assuming there was a threshold for determining when a solution was good enough. – Widgeon

I think he's changing the self.inhabitants somewhere along his mutate functions making the initial loop shorter. But I'm not sure if that's the purpose of the algorithm. If it is that is the explanation, otherwise this could be a bug in the procedure. – Offload