Блог

Я реализовал генетический алгоритм, который использует метод воспроизведения, основанный на методе, описанном в разделе «Регуляризованная эволюция», для поиска архитектуры классификатора изображений.

Минимальный псевдокод,описывающий метод воспроизведения:

 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 упоминают, что описанный выше цикл распараллеливается путем распределения цикла выше по нескольким работникам. Они также упоминают, что полная реализация приведена в выпущенном исходном коде, но связанный код не содержит соответствующей части распараллеливания.

Я не понимаю, как можно распараллелить этот конкретный метод размножения: этап отбора родителей (1a) зависит от текущего состояния популяции.

Несколько заметок:

1. Этот метод работает лучше, чем метод размножения ванили, который применяет отбор мутацию ко всей популяции в ее текущем состоянии и легко распараллеливается.
2. Я написал главному автору по этому поводу, но не получил ответа.

Вы можете представить схему распараллеливания следующим образом (с n работниками):

 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 ().

Используя этот метод, вы снизите давление на отбор, поскольку из текущей популяции будет создано больше детей. Этот эффект можно было бы уравновесить, увеличив размер турнира.

Было бы интересно сравнить производительность оптимизации в игрушечной задаче с этой схемой распараллеливания и без нее.