时间戳

首页 > 解决方案 > 快速进化算法突变：突变 n 个随机基因而不是评估每个基因

python - 快速进化算法突变：突变 n 个随机基因而不是评估每个基因

问题描述

我正在尝试优化我的遗传算法的代码。DNA 目前是一个字典，用于提高适应度计算的查找速度，但可以轻松更改为 numpy 数组。

突变率应该是 1/L，L 是 DNA 的长度。

此解决方案有效，但速度很慢：

# Iterate through genome, flip a gene with a probability of 1/L
def mutate(self):
      self.dna = dict(
        [(i, flip(self.dna[i])) if random.randint(0,num_genes) < 1 
        else (i, self.dna[i]) for i in range(num_genes)]
        )

这个解决方案的速度大约是原来的两倍，但由于某种原因，它会产生更糟糕的结果：

# Select n number of genes calculated by 1/L, then change n random genes
def mutate(self):
      num_mutations = sum(np.random.choice([0,1], num_genes, p=[(num_genes-1)/num_genes, 1/num_genes]))
      for i in np.random.choice(num_genes-1, num_mutations):
        self.dna[i] = flip(self.dna[i])

据我所知，它们突变了相同数量的基因，并且输出应该是相同的。使用设置的随机种子运行 10 次表明后一种方法会导致更差的适应度结果。

为什么第二种方法会导致更差的 dna 适应性？这些方法的结果有何不同？

感谢您的任何帮助。

标签： pythonnumpygenetic-algorithmmutation

解决方案

首先：矢量化

当您的索引是整数时，使用 dict 是没有意义的 - 查找整数索引总是比使用哈希表快。您也可以使用 numpy 对其进行矢量化 - 使您self.dna的 numpy 数组而不是列表或字典，这可能会提高 10x-100x 的速度。 

def flip(x):  # x is a vector of genes, lets a binary array here
    return ~x
mutation_mask = np.random.rand(n_genes)<1./len(self.dna)
self.dna[mutation_mask] = flip(dna[mutation_mask])

其次：为什么你的两种算法不同：

我不知道，它们看起来应该在统计上是相同的。我能想到的一件事是，在第二种情况下，您正在使用 进行修改self.dna，self.dna[i]=...而不是重新分配self.dna=...，因此在第二种情况下，代码中任何其他具有旧的区域self.dna的副本也会发生更改。self.dna = self.dna.copy()您可以通过在第二个示例中的 for 循环之前插入来解决此问题。

推荐阅读