proj2_fun1_parallel.c

Parallel Processing Message Passing Genetic Algorithms

//
#include "mpi.h"
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <time.h>

#define M_NUM 40//the number of migration
#define POPULATION M_NUM*10//population size for each node

#define SOLUTION_BITS 63
#define VARIABLES_BITS 21
#define G_OK 10
#define POOL 10//the number of Pool we want to use

#define G_NUM 1000//generation size
#define K_G_NUM 100//after k generation do migration



int termination_condition = 0;
double start_t;
double end_t;
double communication_time=0;

double total_time=0;
float maxmin,maxmax;
float maxOfAll=0;

float subsum[POPULATION];

float sum;
char gene[POPULATION][SOLUTION_BITS];//

int generation_num=0;
int generation_OK=0;//


//print all the gene
void printgeneall()
{
	int i,j;
	for(i=0;i<POPULATION;i++)
	{
		printf("gene[%i] =",i);
		for(j=0;j<SOLUTION_BITS;j++)
		{
			printf("%c",gene[i][j]);
		}
		printf("\n");
	}
}

//print a line of gene
void printgene(int i)
{
	int j;
	printf("gene[%i] =",i);
	for(j=0;j<SOLUTION_BITS;j++)
	{
		printf("%c",gene[i][j]);
	}
	printf("\n");
  
}

//
//initialize population
void initializePopulation()
{
	int i,j,bit0_1;
	for(j=0;j<POPULATION;j++)
	{
		for(i=0;i<SOLUTION_BITS;i++) 
		{ 
			//
			
			bit0_1=(int)(floor((rand()/(RAND_MAX+1.0))*2)); 

			if(bit0_1==0)
				gene[j][i]='0';
			else
				gene[j][i]='1';
			
		} 
	}
}//end of initializePopulation()



void evaluatePopulation()
{
	float xyz;
	int i,j;
	float x[POPULATION],y[POPULATION],z[POPULATION];
	//
	
	for(i=0;i<POPULATION;i++)
	{
		//printgene(i);
		x[i]=0;
		for(j = 1;j < VARIABLES_BITS;   j ++)   
		{   
			
			if(gene[i][j]=='1')
			{
				x[i]=x[i]+(int)(pow(2,(VARIABLES_BITS-1-j)));
			}
		} 
		//
		if(gene[i][0]=='1')
			x[i]=0-x[i];
		//printf("x[%i]=%f ,",i,x[i]);
		y[i]=0;
		for(j = VARIABLES_BITS+1;j < 2*VARIABLES_BITS;   j ++)   
		{   
			
			if(gene[i][j]=='1')
			{
				y[i]=y[i]+(int)(pow(2,(2*VARIABLES_BITS-1-j)));
			}
		} 
		if(gene[i][VARIABLES_BITS]=='1')
			y[i]=0-y[i];
		//printf("y[%i]=%f ,",i,y[i]);
		z[i]=0;
		for(j = 2*VARIABLES_BITS+1;j < 3*VARIABLES_BITS;   j ++)   
		{   
			
			if(gene[i][j]=='1')
			{
				z[i]=z[i]+(int)(pow(2,(3*VARIABLES_BITS-1-j)));
			}
		} 
		if(gene[i][2*VARIABLES_BITS]=='1')
			z[i]=0-z[i];
		//printf("z[%i]=%f",i,z[i]);

		subsum[i]=0-x[i]*x[i]+1000000*x[i]-y[i]*y[i]-40000*x[i]-z[i]*z[i];
		//printf("subsum[%i]=%f\n",i,subsum[i]);
		sum+=subsum[i];
	}
	//printf("sum=%f",sum);
	
	

}

//check fitness of population
int check(int i)
{	
	float a = (rand()/(RAND_MAX+1.0))*sum;
	if(subsum[i]<sum/POPULATION)
	{
		return 0;
	}
	
	if(a<subsum[i])
		return 1;
	return 0;

}

void selectParents()
{	
	int i = 0,pParents,j ;
	char gene1[POPULATION][SOLUTION_BITS];
	while (i<POPULATION)
	{
		pParents = (int)(floor((rand()/(RAND_MAX+1.0))*POPULATION));
		if(check(pParents))
		{
			for( j =0;j<SOLUTION_BITS;j++)
			{
				gene1[i][j]=gene[pParents][j];
			}
			i++;	
		}
	}
	for (i=0;i<POPULATION;i++)
	{
		//printf("choice gene[%i]",i);
		for(j =0;j<SOLUTION_BITS;j++)
			{
				gene[i][j]=gene1[i][j];
				//printf("%c",gene[i][j]);
			}
		//printf("\n");
	}
	
}

//
void crossOver()
{	
	int i,b,j;
	float c;
	char temp;
	for (i=0;i<POPULATION;i=i+2)
	{ 
		c = rand()/(RAND_MAX+1.0);
		if (c<0.7)
		{ 
			b = (int)(floor((rand()/(RAND_MAX+1.0))*SOLUTION_BITS));
			for ( j=0;j<b;j++)
			{
				temp=gene[i][j];
				gene[i][j]=gene[i+1][j];
				gene[i+1][j]=temp;
			}
		}
	}
}

void mutation()
{	
	int i,j;
	float a1;
	for ( i=0;i<POPULATION;i++)
	{
		for ( j=0;j<SOLUTION_BITS;j++)
		{
			a1 = rand()/(RAND_MAX+1.0);
			if (a1<0.03)
			{	
				if(gene[i][j]=='1')
				{
					gene[i][j]='0';
				}
				else gene[i][j]='1';
			}		
		}
	}
			
}

float maxofG()
{
	float max = subsum[0];
	int i;
	for(i=1;i<POPULATION;i++)
	{
		if(max<subsum[i])
				max=subsum[i];
	}
	return max;
		
}

int termination_conditions()
{
	
	//max=maxofG();
	if(generation_OK>=G_OK)
		return 1;
	else if(generation_num>G_NUM)
		return 1;
	else
		return 0;
}

//in order to easier to compare with sequential algorithm 
//just make the termination condition easier to see the communication cost
int termination_conditions2()
{
	if(generation_num>G_NUM)
		return 1;
	else
		return 0;
}

void migrationto(int dest)
{
	int i,j;
	char buff[M_NUM][SOLUTION_BITS];
	for(j=0;j<M_NUM;j++)
	{
		for(i=0;i<SOLUTION_BITS;i++)
		{
			buff[j][i]=gene[j][i];
			
		}
	}
	start_t=MPI_Wtime();
	MPI_Send(buff, M_NUM, MPI_CHAR, dest, 0, MPI_COMM_WORLD);
	communication_time=communication_time+MPI_Wtime()-start_t;
}
void migrationfrom(int source)
{
	MPI_Status stat; 
	int i,j;
	char buff[M_NUM][SOLUTION_BITS];
	start_t=MPI_Wtime();
	MPI_Recv(buff, M_NUM, MPI_CHAR, source, 0, MPI_COMM_WORLD, &stat);
	communication_time=communication_time+MPI_Wtime()-start_t;
	for(j=0;j<M_NUM;j++)
	{
		for(i=0;i<SOLUTION_BITS;i++)
		{
			gene[POPULATION-1-j][i]=buff[j][i];
			
		}
	}
	

}

void updatecondition()
{
		float maxtemp;
		maxtemp=maxofG();
		if(maxtemp>0)
		{
			if(maxmin>maxtemp)
			{
				maxmin=maxtemp;
			}
			if(maxmax<maxtemp)
			{
				maxmax=maxtemp;
			}
			
			if((maxmax-maxmin)<(0.05*maxmax))
			{
				generation_OK++;
			}
			else
			{
				maxmin=maxtemp;
				maxmax=maxtemp;
				generation_OK=0;
			}
		}
}

int main(int argc, char **argv)
{
	char idstr[32];
	char buff[SOLUTION_BITS];
	float maxOfTemp;
	float infopass[1];
//	float MPI_maxOfTemp[1];
	int numprocs;
	int myid;
	int i,j;
	int k;
    double start_t1,start_t_all,compute_time;
	
	MPI_Status stat; 
	MPI_Init(&argc,&argv); 
	MPI_Comm_size(MPI_COMM_WORLD,&numprocs); 
	MPI_Comm_rank(MPI_COMM_WORLD,&myid);

	
	if(numprocs==1)
	{
		printf("please choose more nodes to run this parallel algorithm");
	}
	else
	{
		if(myid==0)
		{
			printf("the population for each node is %d\n",POPULATION);
			printf("the number of migration for each time is %d\n",M_NUM);
			
			printf("the number of generation for each node is %d\n",G_NUM);
			printf("after %d generation do migration\n",K_G_NUM);
			
			
		}

		start_t_all=MPI_Wtime();//each node's compute time start
		
		//use with rand() to get randam number
		srand( (unsigned)time( NULL ) );

		initializePopulation(POPULATION);
		//printgeneall();
		evaluatePopulation();
		//need to use if change termination condition.
		//maxmin=maxofG();
		//maxmax=maxofG();
		
		maxOfTemp=maxofG();
		if(maxOfTemp>maxOfAll)
		{
			maxOfAll=maxOfTemp;
		}
		while(!termination_conditions2())
		{
			
			generation_num++;
			selectParents();
			crossOver();
			mutation();
			//start migration
			if(generation_num%K_G_NUM==0)
			{
				
				if(myid!=(numprocs-1))
				{
					
					migrationto(myid+1);//send message
		
				}
				else
				{
					
					migrationto(0);//send message
					
				}

				if(myid==0)
				{
					
					migrationfrom(numprocs-1);//receive message
					
				}
				else
				{
					
					migrationfrom(myid-1);//receive message
					
				}
			//end of migration
				
			}
			//

			evaluatePopulation();
			maxOfTemp=maxofG();
			if(maxOfTemp>maxOfAll)
			{
				maxOfAll=maxOfTemp;
			}

			//update termination_conditions(in order to consider more about the communication cost the condition changes)
			//updatecondition()  
			

		}//End of while(!termination_conditions())
		
		
		
		

		if(myid!=0)
		{
			infopass[0]=maxOfAll;
			start_t=MPI_Wtime();
			MPI_Send(infopass, 1, MPI_FLOAT, 0, 0, MPI_COMM_WORLD);
			communication_time=communication_time+MPI_Wtime()-start_t;
			compute_time=compute_time+MPI_Wtime()-start_t_all;//each node's compute time end
			//printf("        node %d compute time=%f\n",myid,compute_time-communication_time);
			//printf("++++++++node %d : communication_time=%f\n",myid,communication_time);
			
		}
		else
		{	//
			//receive all other max value from other nodes and choose the largest.
			
			
			for(i=1;i<numprocs;i++)
			{
				
				start_t=MPI_Wtime();
				MPI_Recv(infopass, 1, MPI_FLOAT, i, 0, MPI_COMM_WORLD, &stat);
				communication_time=communication_time+MPI_Wtime()-start_t;
				
				//printf("Data from node %d received\n",i);
				maxOfTemp=infopass[0];
				total_time+=infopass[1];
				if(maxOfTemp>maxOfAll)
				{
					maxOfAll=maxOfTemp;
				}
			}
			
			total_time+=MPI_Wtime()-start_t_all;
			printf("master node is finished getting the result\n",myid);
			printf("   max = %f\n",maxOfAll);
			printf("master node's communication_time=%f\n",communication_time);
			
			printf("total_time=%f\n",total_time);
		}
	}
		
		
	
	MPI_Finalize();
}