mpitsp.cpp

使用MPI编写一个并行程序

#include <math.h>
#include <iostream.h>
#include <stdlib.h>
#include <mpi.h>
#include <time.h>

int const node_num = 9;
int const group_size = 20;
int const limit = 100;
double mutate_prob = 0.3;
int seed=0;
//#define node_num  5
//#define group_size 10
struct group_member 
{
	int order[node_num+1];   //首元素记录回路的路径长度，1为起始结点
	group_member *pointer;
};

int m_distance[node_num][node_num] = 
{{0,32,67,65,45,56,89,65,23},
{56,0,54,37,79,34,23,55,43},
{45,43,0,87,34,24,31,53,65},
{43,45,23,0,89,33,45,76,43},
{56,54,98,37,0,22,13,45,65},
{22,44,54,34,56,0,44,22,45},
{44,22,13,56,83,23,0,64,33},
{44,44,32,14,56,44,34,0,65},
{33,11,24,55,65,35,64,22,0}};




/*产生随机数*/
int randomInt(int low, int high) {
	int result;
	srand((unsigned)time(0)+(seed++));//srand()函数产生一个以当前时间开始的随机种子 
	result=rand();
    return result%(high-low+1)+low;
}

/*交换数组中的两个元素*/
void swap_array(int i,int j,int a[]) {
//	cout<<"swap begins!"<<endl;
//    cout<<"array is "<<a[0]<<","<<a[1]<<","<<a[2]<<","<<a[3]<<","<<a[4]<<","<<a[5]<<","<<a[6]<<","<<a[7]<<","<<a[8]<<","<<a[9]<<endl;
	int temp = a[i];
	a[i] = a[j];
	a[j] = temp;
}


/*计算某一种解决方案的总开销*/
int sum_weight(int a[]) {
	int sum=0;
	int n1;
	int n2;
	for(int i=1;i<node_num;i++) {
		n1=a[i];
		n2=a[i+1];
		sum+=m_distance[n1][n2];
	}
	sum=sum+m_distance[node_num][1];
	return sum;

}

/*随机产生一个种群*/
group_member* init_group(int n,group_member* head) {
	group_member *temp = new group_member;
	group_member *pre;
	for(int i=1;i<=node_num;i++) {
		temp->order[i] = i;
	}
	int r1 = randomInt(2,node_num);
	int r2 = randomInt(2,node_num);
	swap_array(r1,r2,temp->order);
	head = temp;
	pre = temp;
	temp->order[0] = sum_weight(temp->order);

	for(int k=1;k<n;k++) {
		temp = new group_member;
		for(int j=1;j<=node_num;j++) {
			temp->order[j] = pre->order[j];
		}
		r1 = randomInt(2,node_num);
	    r2 = randomInt(2,node_num);

		swap_array(r1,r2,temp->order);
		pre->pointer = temp;
		pre = temp;
		if(k==n-1){
			temp->pointer=NULL;
//			tail = temp;
		}
		temp->order[0] = sum_weight(temp->order);
	}
	return head;

	
}
/*将种群中的所有个体按路径长短排序,采用选择排序的方法*/
group_member* selection_sort(group_member* head) {
	group_member *p,*q,*r,*s,*t;
	p=r=head;
	while(p->pointer!=NULL){
		s=q=p->pointer;
		while(q!=NULL) {
			if(p->order[0]>q->order[0]){
				if(p->pointer==q) {
					if(p==head) {
						p->pointer=q->pointer;
						q->pointer=p;

						t=p;
						p=q;
						q=t;

						head=p;
						r=p;
						s=q;
						q=q->pointer;
					}
					else {
						p->pointer=q->pointer;
						q->pointer=p;
						r->pointer=q;

						t=p;
						p=q;
						q=t;

						s=q;
						q=q->pointer;
					}
				}
				else {
					if(p==head) {
						t=q->pointer;
						q->pointer=p->pointer;
						p->pointer=t;

						s->pointer=p;

						t=p;
						p=q;
						q=t;

						s=q;
						q=q->pointer;

						head=p;
					}
					else {
						t=q->pointer;
						q->pointer=p->pointer;
						p->pointer=t;

						r->pointer=q;
						s->pointer=p;

						t=p;
						p=q;
						q=t;

						s=q;
						q=q->pointer;

					}
				}
			}
			else {
				s=q;
				q=q->pointer;
			}
		}
		r=p;
		p=p->pointer;
	}
	return head;
}
/*找到链表的尾部*/
group_member* find_tail(group_member* head)
{
//	int count = group_size-1;
	group_member *p,*q;
	p=head;
	while(p) {
		q=p;
		p=p->pointer;
	}
	return q;
}


/*删除种群中路径长度最大的两个个体，即链表中的最后两个结点*/
void delete_member(group_member* head)
{
	group_member *p,*q;
	int count = group_size-1;
	p=head;
	while(count) {
		p=p->pointer;
		count--;
	}
	q=p->pointer;
	delete q->pointer;
	delete q;
	p->pointer=NULL;
//	tail = p;
}

/*显示种群中的所有个体*/
void display_group(group_member* head)
{
	group_member *p;
	p = head;
	while(p) {
		for(int h=0;h<=node_num;h++) {
			cout<<p->order[h]<<",";
		}
		cout<<endl;
		p=p->pointer;
	}
}


/*交叉进化*/
int crossover(int par1[],int par2[],int child1[],int child2[])
{
	int div1 = node_num/3+1;
	int div2 = div1 + node_num/3;
	int index_par1=1;
    int index_par2=1;
	int index_chd1=1;
	int index_chd2=1;
	int k=div1;
	int flag1 = 0;        //结点是否已经在子个体1中出现
	int flag2 = 0;        //结点是否已经在子个体2中出现

	for(int i=div1;i<div2;i++) {
		child1[i] = par1[i];
		child2[i] = par2[i];
	}

	while(index_par1<=node_num&&index_par2<=node_num) {
		for(k=div1;k<div2;k++){
			if(child1[k]==par2[index_par2]) {
//				cout<<par2[index_par2]<<" already exists in child1!"<<endl;
				flag1 = 1;
			}
			if(child2[k]==par1[index_par1]) {
//				cout<<par1[index_par1]<<" already exists in child2!"<<endl;
				flag2 = 1;
			}
		}
		if(!flag1) {
//			cout<<par2[index_par2] <<" not in child1!"<<endl;
			child1[index_chd1]=par2[index_par2];
			while(child1[index_chd1]>=0) 
				index_chd1++;
		}
		if(!flag2) {
//			cout<<par1[index_par1] <<" not in child2!"<<endl;
			child2[index_chd2]=par1[index_par1];
			while(child2[index_chd2]>=0)
				index_chd2++;
		}
		flag1=0;
		flag2=0;
		index_par1++;
		index_par2++;
	}
	return 0;

}

/*突变*/
int mutate(int a[])
{
	int div1 = randomInt(2,node_num/2);
	int div2 = randomInt(node_num/2+1,node_num);
//	cout<<"div1 is "<<div1<<endl;
//	cout<<"div2 is "<<div2<<endl;
	for(int i=div1,j=div2-1;i<j;i++,j--) {
//		cout<<"mutate swap begins!"<<endl;
		swap_array(i,j,a);
//		cout<<"swap "<<a[i]<<" "<<a[j]<<endl;
	}
//	cout<<"result of mutate is "<<a[0]<<","<<a[1]<<","<<a[2]<<","<<a[3]<<","<<a[4]<<","<<a[5]<<","<<a[6]<<","<<a[7]<<","<<a[8]<<","<<a[9]<<endl;
	return 0;
}

/*将个体添加到链表尾部*/
void append_to_group(group_member *member,group_member* head)
{
	group_member *p,*q;
	q=find_tail(head);
	p=q;
	p->pointer = member;
//	tail = member;
	member->pointer=NULL;
}


int main(int argc, char* argv[]) 
{
	int start,end,runtime;
	int myid,numprocs;
//	int i,j,t,slave;
	MPI_Request  request ;
//	MPI_Status   status ;
	int dest,source;
	int bestpath = 1;

	start = clock();
	MPI_Init(&argc,&argv);
	MPI_Comm_size(MPI_COMM_WORLD,&numprocs);
	MPI_Comm_rank(MPI_COMM_WORLD,&myid);
	
	cout<<"Process "<<myid<<" begins!"<<endl;
	group_member *head=NULL,*tail=NULL;
	int best[node_num+1];
	head=init_group(group_size,head);
	head=selection_sort(head);
//	display_group(head);
	int generation_num=0;
	int par1_num,par2_num;
	int count = 0;
	int mutate_num = int(group_size*mutate_prob);
	int new_mut;
	group_member *par1,*par2,*chd1,*chd2,*temp1,*temp2,*temp3;
	while(generation_num<limit)
	{
//		cout<<"generation "<<generation_num+1<<endl;
		chd1 = new group_member;
	    chd2 = new group_member;
		par1_num = randomInt(1,group_size);
		par2_num = randomInt(1,group_size);
//		cout<<"par1_num is "<<par1_num<<endl;
//		cout<<"par2_num is "<<par2_num<<endl;
		temp1=head;
		temp2=head;
		for(int i=0;i<par1_num-1;i++)
		{
 			temp1=temp1->pointer;
		}
		for(int j=0;j<par2_num-1;j++)
		{
			temp2=temp2->pointer;
		}
		par1=temp1;
		par2=temp2;
//		for(int k=0;k<=node_num;k++) {
//			cout<<par1->order[k]<<",";
//		}
		
//		temp3 = tail;
		crossover(par1->order,par2->order,chd1->order,chd2->order);
		chd1->order[0]=sum_weight(chd1->order);
		chd2->order[0]=sum_weight(chd2->order);
		append_to_group(chd1,head);
		append_to_group(chd2,head);
//		selection_sort();	
		
		
//		display_group();
		
//		cout<<"mutation "<<generation_num+1<<" begins!"<<endl;
//		cout<<"mutate number is "<<mutate_num<<endl;
		for(int mut=0;mut<mutate_num;mut++)
		{
			temp3=head;
			new_mut = randomInt(1,group_size);
//			cout<<"mutation number is "<<new_mut<<endl;
			for(int m=0;m<new_mut;m++)
			{
	    		temp3=temp3->pointer;
			}
			mutate(temp3->order);
			temp3->order[0]=sum_weight(temp3->order);
		}
		 
		if((generation_num+1)%10==0)
		{
//			cout<<"head is ";
			for(int snd=0;snd<numprocs;snd++)
			{
				MPI_Send(head->order,node_num+1,MPI_INT,snd,bestpath,MPI_COMM_WORLD);
//				cout<<head->order[0]<<endl;
			}
			for(int rev=0;rev<numprocs;rev++)
			{
				MPI_Recv(best,node_num+1,MPI_INT,rev,bestpath,MPI_COMM_WORLD,0);
//				cout<<"Process"<<myid<<" receives bestpath from Process"<<rev<<"!"<<endl;
				group_member *receive = new group_member;

//				cout<<"receive path is ";
				for(int assgn=0;assgn<=node_num;assgn++)
				{
					receive->order[assgn]=best[assgn];
//					cout<<best[assgn]<<",";
					
				}
//				cout<<endl;
				receive->pointer=NULL;
				tail->pointer=receive;
				tail=receive;
			}
		}
		 
	       	head=selection_sort(head);
	    	delete_member(head);
//	    	display_group(head);
	    	tail=find_tail(head);
	    	generation_num++;
		}
	end=clock();
	

		if(myid>=0&&generation_num==limit)
		{
			cout<<"The best path is: ";
			for(int dis=0;dis<=node_num;dis++)
			{
				cout<<head->order[dis]<<",";
			}
			cout<<endl;
		}
		MPI_Finalize();
		runtime = end-start;
//		cout<<"runtime is "<<runtime<<endl;
		

	return 0;

}