快速进化算法突变：突变 n 个随机基因而不是评估每个基因
Fast Evolutionary Algorithm Mutation: Mutating n random genes instead of evaluating every gene
我正在尝试优化我的遗传算法的代码。 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 适应性？这些方法的结果有何不同？
感谢您的帮助。
复杂性是由于对随机的多次调用：您正在为每个基因调用它。
你的第二个例子做同样的事情，但这次它们都是在同一个函数中调用的。
大幅提高性能的一种方法是减少随机调用的数量。为此，您可以使用一些数学来预先知道基因组将接收多少突变，公式如下
P(L, n, p) # probability of modifying n-times a genome of size L with a succes p (here p is 1/L)
P(L, n, p) = binomial(n, L) * p**n * (1-p)**(L-n)
如果您对数学不太熟悉，这里有一个 python 函数可以为您做到这一点：
def binomial(n, k):
if 0 <= k <= n:
ntok = ktok = 1
for t in range(1, min(k, n - k) + 1):
ntok *= n; ktok *= t; n -= 1
return ntok // ktok
else: return 0
def P(L, n, p): return binomial(L, n) * p**n * (1-p)**(L-n)
现在您可以 pre-compute 并将其保存在列表中：
proba = [P(L, i, 1/L) for i in range(0, L+1)]
此外，我会建议部分求和，以便于随机使用
probaS = [sum(proba[:k]) for k in range(0, L+1)] + [1]
现在你可以只生成一个随机数，你将直接知道这个基因组需要多少个突变：
r = random()
i = 0
while r > probaS[i]: i += 1
在循环结束时，i-1 会告诉你需要多少个突变。
现在你只需要 select 随机 i-1 基因组的不同部分就可以了！您从 L 次随机调用变为平均只有 2 或 3 次。
在我进行的基本测试中，L=50 和 100,000 个基因组的时间复杂度从 5.74 秒变为 196 毫秒，因此快了大约 30 倍。
我的回答有点技术性，如有不明之处欢迎随时提问。
首先：矢量化
当您的索引是整数时，使用字典毫无意义 - 查找整数索引总是比使用 hash-table 更快。您也可以使用 numpy 对其进行矢量化 - 使您的 self.dna 成为一个 numpy 数组而不是列表或字典，这可能会带来 10 倍到 100 倍的加速。
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 在第二种情况下也会更改其副本。您可以通过在第二个示例中的 for-loop 之前插入 self.dna = self.dna.copy() 来解决此问题。
在第一个示例中，您的基因突变可能超过 num_mutations 次。虽然您的第一种方法平均有 num_mutations 个突变，但您的交叉函数可以利用它有时更大的事实，这可能会将更多样化的基因贡献到池中。理想情况下，您的适应度函数能够丢弃不良排列，同时利用可能使池多样化的更多样化的候选人。
此外，分块变异往往会产生更快但更糟糕的结果。因为突变在整个基因中没有平滑地同质化，所以某个块可能会发生突变，从而扭曲池的适应度，并可能被不成比例地挑选出来。由于突变未均质化，因此您可能会错过通过突变可能对适应性影响不大的其他基因完成的工作。这是使用指数适应度函数的最大陷阱之一，如果您这样做的话，因为这会使这种差异成指数形式。如果你要对基因的随机选择进行均质化，这个可能更合适的基因会对解决方案 space 搜索做出更加多样化的贡献。有几种方法可以轻松解决这个问题，例如如果种群中有足够的基因，则强制最适合的解决方案与其他池成员一起繁殖而不进行基因替换。
我正在尝试优化我的遗传算法的代码。 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 适应性？这些方法的结果有何不同？
感谢您的帮助。
复杂性是由于对随机的多次调用：您正在为每个基因调用它。
你的第二个例子做同样的事情，但这次它们都是在同一个函数中调用的。
大幅提高性能的一种方法是减少随机调用的数量。为此，您可以使用一些数学来预先知道基因组将接收多少突变，公式如下
P(L, n, p) # probability of modifying n-times a genome of size L with a succes p (here p is 1/L)
P(L, n, p) = binomial(n, L) * p**n * (1-p)**(L-n)
如果您对数学不太熟悉，这里有一个 python 函数可以为您做到这一点：
def binomial(n, k):
if 0 <= k <= n:
ntok = ktok = 1
for t in range(1, min(k, n - k) + 1):
ntok *= n; ktok *= t; n -= 1
return ntok // ktok
else: return 0
def P(L, n, p): return binomial(L, n) * p**n * (1-p)**(L-n)
现在您可以 pre-compute 并将其保存在列表中：
proba = [P(L, i, 1/L) for i in range(0, L+1)]
此外，我会建议部分求和，以便于随机使用
probaS = [sum(proba[:k]) for k in range(0, L+1)] + [1]
现在你可以只生成一个随机数，你将直接知道这个基因组需要多少个突变：
r = random()
i = 0
while r > probaS[i]: i += 1
在循环结束时，i-1 会告诉你需要多少个突变。
现在你只需要 select 随机 i-1 基因组的不同部分就可以了！您从 L 次随机调用变为平均只有 2 或 3 次。
在我进行的基本测试中，L=50 和 100,000 个基因组的时间复杂度从 5.74 秒变为 196 毫秒，因此快了大约 30 倍。
我的回答有点技术性，如有不明之处欢迎随时提问。
首先：矢量化
当您的索引是整数时，使用字典毫无意义 - 查找整数索引总是比使用 hash-table 更快。您也可以使用 numpy 对其进行矢量化 - 使您的 self.dna 成为一个 numpy 数组而不是列表或字典，这可能会带来 10 倍到 100 倍的加速。
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 在第二种情况下也会更改其副本。您可以通过在第二个示例中的 for-loop 之前插入 self.dna = self.dna.copy() 来解决此问题。
在第一个示例中，您的基因突变可能超过 num_mutations 次。虽然您的第一种方法平均有 num_mutations 个突变，但您的交叉函数可以利用它有时更大的事实，这可能会将更多样化的基因贡献到池中。理想情况下，您的适应度函数能够丢弃不良排列，同时利用可能使池多样化的更多样化的候选人。
此外，分块变异往往会产生更快但更糟糕的结果。因为突变在整个基因中没有平滑地同质化，所以某个块可能会发生突变，从而扭曲池的适应度，并可能被不成比例地挑选出来。由于突变未均质化，因此您可能会错过通过突变可能对适应性影响不大的其他基因完成的工作。这是使用指数适应度函数的最大陷阱之一，如果您这样做的话，因为这会使这种差异成指数形式。如果你要对基因的随机选择进行均质化，这个可能更合适的基因会对解决方案 space 搜索做出更加多样化的贡献。有几种方法可以轻松解决这个问题，例如如果种群中有足够的基因，则强制最适合的解决方案与其他池成员一起繁殖而不进行基因替换。