parallel-processing - 串行繁殖遗传算法的并行化

Question

我已经实现了一种遗传算法，它使用基于 Regularized Evolution for Image Classifier Architecture Search 中描述的方法的繁殖方法。 .
描述再现方法的最小伪代码:

num_steps = 1e1000
step = 0

1. while step < total_steps:
    1a. winner, loser = tournament_selection(population)
    1b. offspring = mutate(winner)
    1c. replace loser with offspring
    1d. step++

作者在 1提到上面的循环是通过将上面的循环分布在多个工作人员上来并行化的。他们还提到在 released source 中给出了完整的实现。 ，但链接的代码不包含相关的并行化部分。
我无法理解如何并行化这种特定的繁殖方法:父选择步骤 (1a) 取决于种群的当前状态。
一些注意事项:

这种方法比在当前状态下对整个种群应用选择+变异的 Vanilla 复制方法效果更好，并且很容易并行化。

我已经就这一点写信给主要作者，但没有得到回应。

Answer 1

你可以想象一个如下的并行化方案(有 n 个 worker ):

num_steps = 1000
num_cycles = num_steps / n

cycle = 0
while cycle < num_cycles:
  children = []
  for i in range(n):
    children.append(start_worker(current_pop))
  for i in range(n):
    current_population.remove(oldest)
  current_population.append(children)
  cycle += 1

start_worker(pop):
  winner, loser = tournament_selection(population)
  offspring = mutate(winner)
  offspring.fitness = compute_fitness(offspring)
  return offspring

这样，在每一步您都会创建 n 个锦标赛并生成 n 个子项。我认为并行化会很有效，因为计算成本通常存在于 compute_fitness() 方法中。
使用此方法，您将减少选择压力，因为从当前种群中生成了更多子代。这种影响可以通过增加锦标赛的规模来平衡。
比较有和没有这种并行化方案的玩具问题的优化性能可能会很有趣。