使用 OpenMPI 分发 GA 算法

Question

我是 OpenMPI 的新手...我构建了一个 GA 算法 (c++) 来求解第 n 个变量方程，现在我正尝试通过使用 OpenMPI 并行化来提高其性能。

代码结构如下：

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;
}

我的类是：

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;
};

和

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();
};

作为第一种方法，我只是尝试分配适应度函数，以便每个进程计算一部分群体的适应度。我认为这可以通过传递索引以在一个范围内执行计算（这将要求每个进程都可以访问相同的人口）或通过发送人口元素来实现。

void population::calcPopFitness(){
    for_each(ChromoPopulation.begin(), ChromoPopulation.end(), [=]( chromossome & n)
        {n.calcFitness();});
    return;
}

void chromossome::calcFitness(){
    int result=0;
    for(int i=0; i<NUMBERVARIABLES; i++){
        result+=values[i]*(i+1);
    }
    result-=1024;
    fitness=result;
    return;
}

然后我的目标是使用大量人口和大量变量执行此计算。

谁能告诉我最好的方法是什么，如果可能的话给我一些代码示例？我已经为此苦苦挣扎了一个星期，到目前为止在这件事上没有取得任何进展......

提前致谢...任何帮助都是巨大的帮助。

Answer 1

您可以查看我们使用 MPI 实现的遗传编程变体：

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

我们的目的是针对 TSP 问题训练启发式算法，但这需要花费大量时间，因此我们决定在多台计算机上使用 MPI 运行。我们还在同一处理器内使用线程来减少 MPI 开销。

我们将（超）种群分成多个种群，在每一代的末尾，我们在种群之间交换一些个体（参见 MPI_Send/Recv 部分）。

使用 OpenMPI 分发 GA 算法

Distribute GA Algorithm with OpenMPI

c++

algorithm

openmpi

genetic-algorithm