遗传算法:较高的突变率导致较低的运行时间

Question

我实施了一种遗传算法来解决增强的旅行商问题(边缘的权重随着时间的推移而变化).目前我正在评估我的模拟的不同参数,我偶然发现了一个我无法向自己解释的相关性:

突变率越高,运行时间越短.就个人而言,我会假设相反,因为更高的突变率会产生更多的操作.(25%的突变率比5%快12%)

突变率为8%(5%优于10%,25%表现最差(0%除外)),效果最佳.适应值越低越好.

迭代计数由生成参数设置,在所有测试用例中设置为10.000.

每个测试用例执行10次.

我在变异中的实现(在python中)看起来像这样:

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

p 是突变率

突变看起来像这样

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

为什么更高的突变率会导致更快的执行时间？

编辑:我实际上在我的Raspberry Pi上运行了相同的测试(速度慢了9倍),结果相同:

Answer 1

每个突变周期 i都有提供可接受解决方案的概率p _i，评估一个周期所需的时间_为Ti。p _i和T _i都随着突变率的增加而增加。因此，算法的预期运行时间是找到答案所需的预期周期数的总和Σ p _i T _{i 。}较高的突变率会增加每项的大小，但会减少要求和的项的数量。有一个最佳突变率可以最小化这个总和。