Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Genetic Algorithm: Higher Mutation Rate leads to lower run time

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:

mutation rate - runtime

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.

result - mutation rate

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:

time - mutation on pi

like image 948
Bernd Strehl Avatar asked Mar 23 '16 13:03

Bernd Strehl


1 Answers

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.

like image 168
John Coleman Avatar answered Oct 24 '22 07:10

John Coleman