Divide and Conquer

The Genetic Algorithm.

General (sequential) genetic algorithm

population = created randomly;
Evaluate(population);
for (gen = 0; gen < MAX; gen++) {
  new_population = empty;
  for (i=0; i<pop_size; i = i+2)
    parent1=Select(population, fitness);
    parent2= Select(population, fitness);
    Crossover(parent1, parent2, child1, child2);
    Mutation(child1);
    Mutation(child2);
    Insert(new_population, child1);
    Insert(new_population, child2);
  }
  Evaluate(population);
  population = new_population;
}

Easy Parallel GA
The master process or thread is performing most of the operations involved in running the algorithm. The only part that is done in parallel is the evaluation of the fitness value for each chromosome. In this model, each slave process or thread is assigned one chromosome, computes its fitness value idependently, then sends the result back to the master. It is used when the computation of the fitness function takes significantly more time than the rest of the operations.

Evaluate_master() {
  for (i=1; i<np; i++)
    Send(population[i], i);
  F[0]=Fitness(population[0]);
  for (i=1; i<np; i++)
    Recv(F[i], i);
}

Evaluation_slave() {
  Recv(chromosome, 0);
  f = Fitness(chromosome);
  Send(f, 0);
}

Nested (parallel) genetic algorithm
The population is divided into a number of subpopulations based on the number of processes or threads. Each process evolves its own subpopulation independently. To avoid issues of loss of biodiversity and convergence to a local optimum that can occur due to a smaller population size, the processes exchange a number of chromosomes periodically, selected based on the value of the fitness. This is called migration.

Master_Slave()
{
  pop_size = pop_size / nb_proc;
  population = generate initial population by random;
  for (gen = 0; gen < MAX; gen++) {
    new_population = empty;
    for (i=0; i<pop_size; i = i+2)
      parent1=Select(population, fitness);
      parent2= Select(population, fitness);
      Crossover(parent1, parent2, child1, child2);
      Mutation(child1);
      Mutation(child2);
      Insert(new_population, child1);
      Insert(new_population, child2);
    }
    population = new_population;
    if (gen % step == step – 1)
      Exchange_individuals();
  }
}

An example of exchange individuals function

Exchange_individuals()
{
  my_data = best individual;
  Ring_communicate(my_data);
  my_data = second_to_best individual;
  Ring_communicate(my_data);
}

Process_data(prev_individual, my_population)
{
  //Replace a random local individual with the new one.
  my_population[random_place] = prev_individual;
}