串行复制遗传算法的并行化

Question

我已经实现了一种遗传算法，该算法使用基于 Regularized Evolution for Image Classifier Architecture Search 中描述的方法的繁殖方法。

最小pseudo-code描述复制方法：

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 mention that the loop above is parallelized by distributing the loop above over multiple workers. They also mention that the full implementation is given in the released source中的作者，但是链接的代码不包含相关的并行化部分。

我无法理解如何并行化这种特定的繁殖方法：parent 选择步骤 (1a) 取决于种群的当前状态。

一些注意事项：

这种方法比香草繁殖方法效果更好，香草繁殖方法将选择+变异应用于当前状态下的整个种群，并且很容易并行化。
关于这一点，我已经写信给主要作者，但没有得到回复。

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 children。我认为并行化是有效的，因为计算成本通常存在于 compute_fitness() 方法中。

使用这种方法，您可以减少选择压力，因为更多 children 是从当前种群中产生的。这种影响可以通过增加锦标赛的规模来平衡。

比较使用和不使用这种并行化方案在玩具问题上的优化性能可能很有趣。

串行复制遗传算法的并行化

Parallelization of a serial reproduction genetic algorithm

parallel-processing

genetic-algorithm

evolutionary-algorithm