Genetic Algorithm - Crossover and MPI

[mylove9739]

Hello everyone,

i got stuck when i was trying to convert my code to MPI and Crossover solution. My problem is about the Crossover is too hard for me to understand and more difficult to implement all of those solution to MPI. If anyone could give me hint, or example, or any related document. I will included my code below for everyone to see.

Thank you very much

#include <string> 
#include <cstdlib> 
#include <iostream> 
#include <cassert> 
#include <algorithm> 
#include <vector> 
  
std::string allowed_chars = " ABCDEFGHIJKLMNOPQRSTUVWXYZ"; 

class selection 
{ 
public:
  static int fitness(std::string candidate) 
  { 
    assert(target.length() == candidate.length()); 
  
    int fitness_so_far = 0; 
  
    for (int i = 0; i < target.length(); ++i) 
    { 
      int target_pos = allowed_chars.find(target[i]); 
      int candidate_pos = allowed_chars.find(candidate[i]); 
      int diff = std::abs(target_pos - candidate_pos); 
      fitness_so_far -= std::min(diff, int(allowed_chars.length()) - diff); 
    } 
  
    return fitness_so_far; 
  } 
  
  // get the target string length 
  static int target_length() { return target.length(); } 
private: 
  static std::string target; 
}; 
  
std::string selection::target = "METHINKS IT IS LIKE A WEASEL";

void move_char(char& c, int distance) 
{ 
  while (distance < 0) 
    distance += allowed_chars.length(); 
  int char_pos = allowed_chars.find(c); 
  c = allowed_chars[(char_pos + distance) % allowed_chars.length()]; 
} 

std::string mutate(std::string parent, double mutation_rate) 
{ 
  for (int i = 0; i < parent.length(); ++i) 
    if (std::rand()/(RAND_MAX + 1.0) < mutation_rate) 
    { 
      int distance = std::rand() % 3 + 1; 
      if(std::rand()%2 == 0) 
 move_char(parent[i], distance); 
      else 
        move_char(parent[i], -distance); 
    } 
  return parent; 
}
bool less_fit(std::string const& s1, std::string const& s2) 
{ 
  return selection::fitness(s1) < selection::fitness(s2); 
} 
  
int main() 
{ 
  int const C = 100; 
  
  std::srand(time(0)); 
  
  std::string parent; 
  for (int i = 0; i < selection::target_length(); ++i) 
  { 
    parent += allowed_chars[std::rand() % allowed_chars.length()]; 
  } 
  
  int const initial_fitness = selection::fitness(parent); 
  
  for(int fitness = initial_fitness; 
      fitness < 0; 
      fitness = selection::fitness(parent)) 
  { 
    std::cout << parent << ": " << fitness << "\n"; 
    double const mutation_rate = 0.02 + (0.9*fitness)/initial_fitness; 
    typedef std::vector<std::string> childvec; 
    childvec childs; 
    childs.reserve(C+1); 
  
    childs.push_back(parent); 
    for (int i = 0; i < C; ++i) 
      childs.push_back(mutate(parent, mutation_rate)); 
  
    parent = *std::max_element(childs.begin(), childs.end(), less_fit); 
  } 
  std::cout << "final string: " << parent << "\n"; 
}

[VictorN]

What is "Crossover"?
What is "MPI"?

[mylove9739]

What is "Crossover"?
What is "MPI"?

Hi,
thanks for reply,

Crossover is one of the set of Genetic Algorithm. As in my code, it's represent the Mutation technique
MPI is one of parallel technique in programming

please prefer the following links for more info

https://en.wikipedia.org/wiki/Crosso...tic_algorithm)
https://computing.llnl.gov/tutorials/mpi/

thanks

[monarch_dodra]

MPI is Message Passing Interface. It's a way of doing "multithreading" where threads communicate by sending messages to each other. Usually, these threads do not share any memory at all, which means that an MPI program could even run on clusters of multiple computers.

No idea what Crossover is.

[mylove9739]

MPI is Message Passing Interface. It's a way of doing "multithreading" where threads communicate by sending messages to each other. Usually, these threads do not share any memory at all, which means that an MPI program could even run on clusters of multiple computers.

No idea what Crossover is.

Half of the ideas is right. However, MPI is not about multi-threading. It's about a program can create and run as multiple process on the CPU. As can be seen when we run with the command

mpirun -n #process <source> 
#process: the number of process will be use to run the program. Note that, the process must be >= 2.

This is different from Multi-threading because in this MPI, a process is running only 1 thread. By the theory, 1 process can be contain 1 or more thread on the actual CPU. That's why it said that MPI is Parallel, because it allow program to run on multiple process, but not actual multiple thread (not really sure),

Crossover is one of algorithm belong to Genetic Algorithm family. Well, you can prefer my link
https://en.wikipedia.org/wiki/Crosso...tic_algorithm)

[TheGreatCthulhu]

Well, crossover is something inspired by a process of chromosomal crossover that happens in nature; basically two chromosomes recombine by exchanging segments. The idea is adapted for genetic programming as another way to introduce variability.

mylove9739, can you explain in more detail what is it that you have trouble understanding? In essence, to do a crossover, you need more then one parent chromosome (parent std::string in your case, if I'm not mistaken). Then you randomly pick up a point to cut them (both at the same point), and exchange the parts.

[daylight18]

take a look at cplusplus algorithm analysis for c++ code snippets