Verteilen GA-Algorithmus mit OpenMPI

Question

Ich bin neu mit OpenMPI arbeiten ... Ich baute einen GA-Algorithmus (C++) eine n-te Variable Gleichung zu lösen und jetzt versuche ich, ihre Leistung zu verbessern, indem OpenMPI parallelisiert werden.

Die Codestruktur geht wie folgt:

int main(int argc, char *argv[]){ 
    int i=1; 
    int print=0; 
    int fitness_check; 

    if (argc < 2) print=1; 


    //initialize rand parameter 
    srand(time(0)); 
    //start counting clock 
    auto start_time = std::chrono::high_resolution_clock::now(); 
    //start GA 
    population *pop=new population(); 
    pop->calcPopFitness(); 
    pop->popSort(); 

    fitness_check=pop->getElement(0).getFitness(); 
    while(pop->getElement(0).getFitness()!=0){ 
     pop->evolvePop(); 

     pop->calcPopFitness(); 

     pop->popSort(); 


     if(fitness_check<(pop->getElement(0).getFitness())){ 
      cout<<"Error in elitism\n"; 
      cout<<"---------------------------\nPrinting after sort...\n"; 
      pop->printPopulation(); 
      cout<<"\n-------------------------------------------\n"; 
      exit(1); 
     }else{ 
      if(fitness_check>(pop->getElement(0).getFitness())) 
       fitness_check=(pop->getElement(0).getFitness()); 
     } 
     if(print==1)cout<<"\nBest string fit in ("+to_string(i)+") iteration: "+string(pop->getElement(0).getString())+"\n"; 
     i++; 
    } 
    if(print==1)cout<<"\nGA algorithms work!\n"; 
    //end of GA algorithm and stop counting time 
    auto end_time = std::chrono::high_resolution_clock::now(); 
    auto time = end_time - start_time; 
    if(print==1)std::cout << "It took " << 
    std::chrono::duration_cast<std::chrono::milliseconds>(time).count() << " milliseconds to run.\n"; 
    writeFile(pop->getElement(0).getValues(), to_string(std::chrono::duration_cast<std::chrono::milliseconds>(time).count())); 
    pop->cleanup(); 
    delete pop; 
    return 0; 
} 

Meine Klassen sind:

class chromossome{ 
    private: 
     int * values; 


    public: 
     unsigned int fitness; 
     //constructor 
     chromossome(); 
     chromossome(int *vector); 
     void deleteVector(); 

     bool operator<(const chromossome& other) const { 
      return fitness < other.fitness; 
     } 
     unsigned int getFitness(); 
     int* getValues(); 
     void calcFitness(); 
     void setGene(int i, int gene); 
     int getGene(int i); 
     //int constgetGene(int i) const; 
     void mutate(); 
     string getString() const; 
}; 

und

class population{ 
    private: 
     int population_size; 
     vector<chromossome> ChromoPopulation; 
    public: 
     population(); 
     population(bool newIteration); 
     int getSize(); 
     void printPopulation(); 
     void removeChromossome(); 
     chromossome getElement(int position); 
     void calcPopFitness(); 
     void popSort(); 
     void addChromossome(chromossome individual); 
     chromossome *tournamentSelection(); 
     chromossome* crossover(chromossome a, chromossome b); 
     void mutate(); 
     chromossome * cloneChromossome(chromossome c); 
     vector<chromossome> getList(); 
     void evolvePop(); 
     void cleanup(); 
}; 

Als erster Ansatz, den ich nur versucht, mich das die verteilen Fitness-Funktion, so dass jeder Prozess die Fitness eines Teils der Bevölkerung berechnet. Ich dachte, dies entweder durch Passieren Indizes erreicht werden kann, um die Berechnungen in einem Bereich durchführt (dies würde erfordern, dass jeder Prozess Zugriff auf die gleiche Bevölkerung hat) oder durch die Bevölkerung Elemente zu senden.

Mein Ziel ist es dann, diese Berechnungen mit großen Populationen und einer großen Anzahl von Variablen durchzuführen.

Kann mir jemand sagen, was der beste Ansatz ist, und, wenn möglich, geben Sie mir einige Code-Beispiele? Ich habe eine Woche lang mit diesem zu kämpfen und keine Fortschritte bisher in dieser Angelegenheit ...

Vielen Dank im Voraus gemacht habe ... jede Hilfe ist eine große Hilfe.

Answer 1

Sie können einen Blick auf unsere Implementierung eines Genetic Programming Variante mit MPI haben:

https://github.com/mihaioltean/evolve-tsp-heuristics/tree/master/train/mpi

Unser Ziel Heuristik für das TSP Problem zu trainieren, aber das viel Zeit in Anspruch nimmt, so dass wir entschied sich, MPI zu verwenden, um auf mehreren Computern zu laufen. Wir verwendeten auch Threads innerhalb des gleichen Prozessors, um den MPI-Overhead zu reduzieren.

Wir haben unsere (Super-) Bevölkerung in mehrere Populationen und am Ende jeder Generation geteilt tauschen wir einige Personen zwischen Populationen (siehe MPI_Send/Recv Teil).