基于MPI-GA的TSP问题C++代码

基于并行遗传算法的TSP问题C++代码，本代码改编自《Parallel Genetic Algorithms: A Typical MPI Application》，添加了丰富的代码注释。

/*
  MPI based TSP Problem
  
  本代码改编自：Parallel Genetic Algorithms: A Typical MPI Application。 见pga.pdf
  
  由于测试需要添加了Linux的信号处理函数，需要安装有MPICH/openmpi库的Linux系统下编译：
  mpicxx -g pga.cpp -o pga
  
  城市坐标文件：cities.txt
  
  运行：mpirun -n 4 ./pga 
  
  您也可以把Linux信号处理部分的代码注释掉，这样可以在Windows系统的编译（需要安装Windows版MPICH2，或微软的MPI库）
  
*/

#include 
#include 
#include 
#include 
#include 
#include 
#include 

#include 
#include 
#include 
#include 

#include 
using namespace std;

#define POP_SIZE    1000
#define MAX_Gen     3000
#define MUTATIONFACTOR  0.035
#define EXCHANGEPERIOD  10


#define CITYNO    25
#define DATAFILE “cities.txt“  // 城市地理坐标文件

/*
    0.8147    0.7577
    0.9058    0.7431
    0.1270    0.3922
    0.9134    0.6555
    0.6324    0.1712
    0.0975    0.7060
    0.2785    0.0318
    0.5469    0.2769
    0.9575    0.0462
    0.9649    0.0971
    0.1576    0.8235
    0.9706    0.6948
    0.9572    0.3171
    0.4854    0.9502
    0.8003    0.0344
    0.1419    0.4387
    0.4218    0.3816
    0.9157    0.7655
    0.7922    0.7952
    0.9595    0.1869
    0.6557    0.4898
    0.0357    0.4456
    0.8491    0.6463
    0.9340    0.7094
    0.6787    0.7547
*/


typedef struct scity 
{
	float x_coord;   // x
	float y_coord;   // y
} city;

struct 
{
	float value;
	int   index;
} in out;
	

MPI_Datatype MPI_City;
typedef int path[CITYNO];
city cities[CITYNO];


int rank size;

void random_shuffle（path p）;

float Fitness（path p）;

int comparepaths（const void *p1 const void *p2）;

void crossover（path p1 path p2）;

void Do_Crossover（path p1 path p2 path np1 path np2）;

void printpath（path p）;

void mutate（path p）;

void select_crossover_choices（int *p float *fits）;

void random_crossover_choices（int *p float *fits）;

int find_pid_by_name（ char* ProcName vector& pid_x）;


void handler（int sig）
{
		printf（“Get a signal num is %d !\n“ sig）;
		printf（“Ding!Ding!Ding!Ding!Ding! \n“）;\
		
		
		if（0 == rank）
		{
		    //pga并行计算的0号进程，发送给另一个进程solver 一个ALARM信号：
		    
		    //通过进程名获取进程pid
		    vector pid;
            
            int rv = find_pid_by_name（“solver“ pid）;
            if（!rv） 
            {
                 for（int i = 0; i < pid.size（）; i++） 
                 {
                      printf（“pid[%d]=%d\n“ i pid[i]）;  // 如果solver也是MPI并行从小，那么同名的进程可能不止一个。
                      kill（pid[i] SIGALRM）;              // 向名为solver的进程发送一个SIGALRM信号
                      printf（“pga send an alarm to solver %d\n“pid[i]）;	
                 }
            }
        }
        
        
        // 对外发送完信号后，发送给自己一个暂停的信号 
        pid_t pidme = getpid（）;
		kill（19 pidme）;	 
		
		
		sleep（20）; 
		
		kill（18 pidme）;     //睡眠20秒后，开始续算
		
}


int main（int argc char **argv）
{

	city acity;

	int lenc[2];

	MPI_Aint locc[2];
	MPI_Datatype typc[2];
	MPI_Aint baseaddr;

	/

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件        525  2018-06-21 16:37  MPI-GA-TSP\src\cities.txt

     文件     274297  2018-07-31 14:49  MPI-GA-TSP\src\pga

     文件      13873  2018-07-31 16:19  MPI-GA-TSP\src\pga.cpp

     文件     118106  2018-05-07 13:35  MPI-GA-TSP\src\pga.pdf

     目录          0  2018-07-31 16:18  MPI-GA-TSP\src

     目录          0  2018-07-31 16:12  MPI-GA-TSP

----------- ---------  ---------- -----  ----

               406801                    6