pgacsp.cpp

This a parallel genetic algorithm for a biinfomatics problem CSP

// pgascp.cpp : Defines the entry point for the console application.
//

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <pvm3.h>

#ifdef _WIN32
#include <windows.h>
#else
#include <unistd.h> 
#include <sys/utsname.h>
#endif

#ifndef __int64
#define __int64 long long
#endif

#ifndef _CPLUSPLUS
#define bool int
#define false 0
#define true 1
#endif
//you can control debug info output here...
#define DEBUG_OUT


//--------GA TYPE-----------------


//---------------input parameters----------------------------------
//MAX_BUFFER define the max length of a src string.
#define CPU_HZ 1000000
#define MAX_BUFFER 5000   //这个是结果comonstring的最大长度
#define MAX_SRC_LEN 50  //最多的src个数
#define MAX_SRC_SINGLE_LEN 1024 //单个源的最大长度
#define MAX_INT_VALUE 0x7fffffff
#define MAX_CHARSET 26

char OrgSrc[MAX_SRC_LEN][MAX_SRC_SINGLE_LEN] = {"AGTCGACGATAGACGAGCTT","ACGTAATGCATGACGTGCCT","AGATTTAGCTCCCCCATGCT","GCCACCCGCTACCCGTGTCG","ACTGCATGCCTCGTGATGCA","AGCTCTGACCCGCTACCGTG","AGGCCTCGCCTGTGCATCAG","AACGATCCCTAGCACGATGC","ATGCTCGCCGCTAGCCTTCG","GTACCGTCGCTCGCTACGTC"};
int srcCount = 10;
char* Src[MAX_SRC_LEN];

int CloseStringLen = 20;
char WordBook[] = "GACT";//字典串,src串中只能有这些字符
int WordBookSize = 4;//修改字典的时候也要修改这里
int WS[MAX_SRC_SINGLE_LEN][MAX_SRC_SINGLE_LEN];	
int Match=1,Miss=0,GapCost=0;
double bestSmallF = -1;

char gResult[MAX_BUFFER];
char ResultCommonString[MAX_BUFFER];
char Buffer[MAX_BUFFER];
int MinResultLen;
//-----use in GA--------
//POPU_SIZE must be even.
#define POPU_SIZE 10
#define MACHINE_SIZE 5
#define MUTATION_P 0.6f
#define ISLAND_MOVE 100


int MyTID;
int ParentTID;

__int64 GetCycleCount()
{
	//call RDTSC
#ifdef _MSC_VER 
	__asm _emit 0x0F
	__asm _emit 0x31
#else
	struct timeval tp; 
	gettimeofday(&tp,NULL); 
    return 1000000*tp.tv_sec + tp.tv_usec;
#endif
}

//make a rand int list which length is nLength.
//if nLength = 9,the rand list may be {3,4,6,5,2,7,8,0,1}

int IntRangeRand(int maxValue)
{
	return ((int)rand())%maxValue;
}



void GetRandIntList(int* pIntList,int nLength)
{
	//I have a good idea to optmize here~,just make a rand num in [1,nLength!].
	int i;
	int swapPos1,swapPos2;
	int temp;
	for(i=0;i<nLength;i++)
	{
		pIntList[i] = i;
	}
	//rand cross this list
	for(i=0;i<nLength;i++)
	{
		swapPos1 = IntRangeRand(nLength);
		swapPos2 = IntRangeRand(nLength);
		temp = pIntList[swapPos1];
		pIntList[swapPos1] = pIntList[swapPos2];
		pIntList[swapPos2] = temp;
	}
	
}


int Watermansmith(char* StringPtn,char* StringTxt)
{
	int i,j,score;
	int LengthA,LengthB;
	int HiScore = -2;
	LengthA = strlen(StringPtn);
	LengthB = strlen(StringTxt);

	/*score table*/ 

	for(i = 1; i <= LengthA; ++i) { 	// all values of StringPtn

		for(j = 1; j <= LengthB; ++j) {	// all values of StringTxt
			score = 0;

			// if MATCH
			if(StringPtn[i-1] == StringTxt[j-1]) 
			{		
				score = (WS[i-1][j-1] + Match);	//score = diagonal + match score
			}



			if(score < ((WS[i-1][j]) - GapCost )) {	    //if the above has a greater value 

				score = (WS[i-1][j]) - GapCost ;		//set score as the above

			}



			if(score < ((WS[i][j-1]) - GapCost )) {	   //if the left has the highest value

				score = (WS[i][j-1]) - GapCost ;      //set score as the left

			}		

			if(score <= 0) {
				score = 0;
			}


			// if MISSMATCH
			if(StringPtn[i-1] != StringTxt[j-1]) {		//if not the same

				if(score < (WS[i-1][j-1] - Miss)) {	//score = diagonal + match score
					score = WS[i-1][j-1] - Miss;
				}
			}


			if(score < ((WS[i-1][j]) - GapCost )) {	   

				score = (WS[i-1][j]) - GapCost ;	

			}



			if(score < ((WS[i][j-1]) - GapCost )) 
			{	
				score = (WS[i][j-1]) - GapCost;  
			}		

			if(score < 0)
			{
				score = 0;
			}			


			WS[i][j] = score;	// Set the score to WS(i,j)
			if(WS[i][j] > HiScore) 
			{
				HiScore = WS[i][j];
			}
		}
	}

	return HiScore;
}




//------------------Some RAND functions---------------------------
double RangeRand(double minValue,double maxValue)
{
	 return (((double) rand() / (double) RAND_MAX) * (maxValue-minValue) + minValue);
}

//this rand function is optimize than double RangeRand.,but it will not be used in continuous. 


void GetRandString(char* pString,int nLength)
{
	
	int i,wordPos;
	
	for(i=0;i<nLength;i++)
	{
		wordPos = IntRangeRand(WordBookSize);
		pString[i] = WordBook[wordPos]; 
	}
	pString[nLength] = 0;
	
}

//----------------------GA---------------------
void printGene(char Gene[])
{
	printf("%s",Gene);
}

struct Individual
{
	char Gene[MAX_SRC_SINGLE_LEN];
	double F;
	double P;
};

struct Population
{
	struct Individual Individuals[POPU_SIZE]; 
};

double BestFitness=0;

double Fitness(struct Individual* pIndividual)
{
	int i,len;
	int f;
	
	double smallF = 8000;
	for(i=0;i<srcCount;i++)
	{
		f = Watermansmith(pIndividual->Gene,OrgSrc[i]);
		if(f < smallF)
		{
			smallF = f;
		}
	}

	if(smallF > bestSmallF)
	{
		//copy to result..
		bestSmallF = smallF;
		strcpy(gResult,pIndividual->Gene); 
	}
	return (double)smallF;
}



void InitFirstPopulation(struct Population* pPopulation,int nLen)
{
	int i;
	for(i=0;i<POPU_SIZE;i++)
	{
		GetRandString(pPopulation->Individuals[i].Gene,nLen); 
#ifdef DEBUG_OUT
		printf("Init individual :");
		printGene(pPopulation->Individuals[i].Gene); 
		printf("\n");
#endif
	}
}

void GetPopulationFitness(struct Population* pPopu)
{
	int i;
	double TotalF;
	TotalF = 0.0f;
	for(i=0;i<POPU_SIZE;i++)
	{
		pPopu->Individuals[i].F = Fitness(&(pPopu->Individuals[i]));
		TotalF += pPopu->Individuals[i].F;
	}
	for(i=0;i<POPU_SIZE;i++)
	{
		pPopu->Individuals[i].P =(double) pPopu->Individuals[i].F / (double)TotalF;
	}

}

void SelectIndividualToParentUseP(struct Population* pThePopu,struct Population* pParentPopu)
{
	int i,j;
	double p;
	double iterp=0;
	
	//if we want to save best M individual,we change here.

	for(i=0;i<POPU_SIZE;i++)
	{
		//here is fruit machine casino
		p = RangeRand(0.0f,1.0f);
		j=0;
		while(iterp<p)
		{
			iterp+=pThePopu->Individuals[j].P;
			j++;
		}
		if(j>POPU_SIZE-1) j=POPU_SIZE-1;
		pParentPopu->Individuals[i] = pThePopu->Individuals[j];
	}
}
void Mutation(struct Individual* pIndividual)
{
	int i;
	int temp;
	int posLeft,posRight;
	int len;
	len = strlen(pIndividual->Gene);
	if(RangeRand(0,1.0f) <= MUTATION_P)
	{
		posLeft=IntRangeRand(len-1);
		do
		{ 
			posRight=IntRangeRand(len-1);
		} while (posLeft==posRight);
		temp = pIndividual->Gene[posLeft];
		pIndividual->Gene[posLeft] =  pIndividual->Gene[posRight];
		pIndividual->Gene[posRight] = temp;
	}
}

void CrossOver(struct Individual* pMother,struct Individual* pFather,struct Individual* pSon,struct Individual* pDaught)
{
	//static GeneCopyed = 0;
	int i,j,k;
	int divPosLeft=0,divPosRight=0;
	int len;
	len =  strlen(pMother->Gene);
	divPosLeft = IntRangeRand(len - 1);

	//copy father's gene to son;mother's gene to daught.

	for(i=0;i<divPosLeft;++i)
	{
		pDaught->Gene[i] = pMother->Gene[i];
		pSon->Gene[i] = pFather->Gene[i];  
		
	}

	//copy father's gene to daught,copy mother's gene to son.

	for(j=divPosLeft;j<len;j++)
	{
		pSon->Gene[j] = pMother->Gene[j];
		pDaught->Gene[j] = pFather->Gene[j];  
	}
	

	Mutation(pSon);
	Mutation(pDaught);
	
#ifdef DEBUG_OUT
	//printf parent and children.
	printf("Father is:");
	printGene(pFather->Gene);
	printf("\n");

	printf("Mother is:");
	printGene(pMother->Gene);
	printf("\n");

	printf("Son is:");
	printGene(pSon->Gene);
	printf("\n");

	printf("Daught is:");
	printGene(pDaught->Gene);
	printf("\n\n");
	//system("pause");
#endif
	
}


bool IsGAOver(int nGeneration)
{
	if(nGeneration > 2000)
		return true;
	return false;
}

int GetBestFitness(struct Population* pPopu)
{
	int i;
	int bestNum;
	double bestF = 0;
	for(i=0;i<POPU_SIZE;++i)
	{
		if(pPopu->Individuals[i].F > bestF)
		{
			bestF = pPopu->Individuals[i].F;
			bestNum = i;
		}
	}
	return bestNum;
}

int GetWorstFitness(struct Population* pPopu)
{
	int i;
	int worstNum;
	double worstF = 500000;
	for(i=0;i<POPU_SIZE;++i)
	{
		if(pPopu->Individuals[i].F <  worstF)
		{
			worstF = pPopu->Individuals[i].F;
			worstNum = i;
		}
	}
	return worstNum;
}

void CopyGene(char geneDest[],char geneSrc[],int nLen)
{
	int i;
	for(i=0;i<nLen;++i)
	{
		geneDest[i] = geneSrc[i];
	}
	geneDest[nLen] = 0;
}



void GAWorker()
{
	struct Population thisPopu;
	struct Population parentPopu;
	int ParentPosList[MAX_SRC_LEN];
	int i=0;
	int j=0;
	double d;
	int generation=0;
	int popuLen = CloseStringLen;
	int myProcID,destProcID,srcProcID;
	double bestF=0,worstF=0;

	char GeneSend[MAX_SRC_SINGLE_LEN];
	char GeneRecv[MAX_SRC_SINGLE_LEN];
	
	int msgTag = 3;
	// Join a PGASCS process group.
	myProcID = pvm_joingroup("PGACSP");
	printf("Before Join/n");
	//pvm_freezegroup("PGASCS",MACHINE_SIZE - 1);

	pvm_barrier("PGACSP",MACHINE_SIZE - 1);

	printf("Join! myProcID = %d mytid = %d\n",myProcID,MyTID);
	
	
		//slave: Get mastertid,dest_t_id,src_t_id
	srcProcID  = pvm_gettid("PGACSP", myProcID - 1);
	destProcID = pvm_gettid("PGACSP", myProcID + 1);
	if( myProcID == 0 ) 
		srcProcID = pvm_gettid("PGACSP", MACHINE_SIZE-2);
	if( myProcID == MACHINE_SIZE - 2 ) 
		destProcID = pvm_gettid("PGACSP", 0);
	
	//slave: begin GA
	InitFirstPopulation(&thisPopu,CloseStringLen);
	while(!IsGAOver(generation))
	{
		//get fitness of population
		GetPopulationFitness(&thisPopu);
		
		//select.
		SelectIndividualToParentUseP(&thisPopu,&parentPopu);

		//This is a ISLAND-RING.we begin individual transference begin a special island.
		if(generation > 0 && generation % ISLAND_MOVE ==0)
		{
			CopyGene(GeneSend,parentPopu.Individuals[GetBestFitness(&parentPopu)].Gene,CloseStringLen);  	
			
			if(myProcID == 0)
			{
				//the first send before recv.
				pvm_initsend( PvmDataDefault );
				pvm_pkstr(GeneSend);
				pvm_send( destProcID, msgTag);
#ifdef DEBUG_OUT
				printf("proc %d send individual to proc %d\n",myProcID,destProcID);
#endif
				pvm_recv( srcProcID, msgTag );
				pvm_upkstr(GeneRecv);
				CopyGene(parentPopu.Individuals[GetWorstFitness(&parentPopu)].Gene,GeneRecv,CloseStringLen);
#ifdef DEBUG_OUT
				printf("proc %d recv individual from proc %d\n",myProcID,srcProcID);
#endif
			}
			else
			{
				//other recv before send.
				pvm_recv( srcProcID, msgTag );
				pvm_upkstr(GeneRecv);
				CopyGene(parentPopu.Individuals[GetWorstFitness(&parentPopu)].Gene,GeneRecv,CloseStringLen);
#ifdef DEBUG_OUT
				printf("proc %d recv individual from proc %d\n",myProcID,srcProcID);
				
#endif		
				pvm_initsend( PvmDataDefault );
				pvm_pkstr(GeneSend);
				pvm_send( destProcID, msgTag);
#ifdef DEBUG_OUT
				printf("proc %d send individual to proc %d\n",myProcID,destProcID);
#endif
			}
		}


#ifdef DEBUG_OUT
		for(i=0;i<POPU_SIZE;++i)
		{
			printf("This individual :");
			printGene(thisPopu.Individuals[i].Gene); 
			printf("\n");
		}
		for(i=0;i<POPU_SIZE;++i)
		{
			printf("Select individual :");
			printGene(parentPopu.Individuals[i].Gene); 
			printf("\n");
		}
#endif
		//cross and make child...
		//get rand parents.
		GetRandIntList(ParentPosList,POPU_SIZE);
		for(i=0;i<POPU_SIZE / 2;++i)
		{
			CrossOver(&(parentPopu.Individuals[ParentPosList[2*i]]),&(parentPopu.Individuals[ParentPosList[2*i+1]]),
				          &(thisPopu.Individuals[2*i]),&(thisPopu.Individuals[2*i+1]));
		}
		
		generation++;
	}
	//send my best individual to master.
	pvm_initsend( PvmDataDefault );
	pvm_pkstr(gResult);
	pvm_send(ParentTID, msgTag );
	pvm_initsend( PvmDataDefault );
	pvm_pkdouble(&bestSmallF,1,1);
	pvm_send(ParentTID, 4 );
	pvm_lvgroup( "PGACSP" );
	printf("Task in Group PGACSP %d (tid=%d) finish,send best close string to master.",myProcID,MyTID);
}

void GAMaster()
{
    int rc;                                 /* return code for function calls */
    int *children;							/* pointer to array to hold children's tids */
	//master: recv all slave's best individual.Printf best of them.
	int i;
	double bestScore = -1;
	double recvScore;
	char ResultRecv[MAX_BUFFER];

	children = (int*) malloc(MACHINE_SIZE * sizeof(int));

    //master: Begin all slave task.
	printf("Will Spawn...");
    rc = pvm_spawn("pgacsp", (char**)0, 0, "LINUXSPARC",MACHINE_SIZE - 1, children + 1);

	printf("SPAWN!");
    if (rc < (MACHINE_SIZE-1))
    {

      printf("There was a problem starting the slaves!\n");
      printf("%d slaves were started.\n", rc);
      exit(EXIT_FAILURE);
    }
	printf("Start %d child!\n",rc);


	
	for(i=1;i<MACHINE_SIZE - 1;i++)
	{
		pvm_recv( children[i], 3 );
		pvm_upkstr(ResultRecv);
		pvm_recv( children[i],4);
		pvm_upkdouble(&recvScore,1,1);
		
		if(recvScore > bestScore)
		{
			strcpy(gResult,ResultRecv);
			bestScore = recvScore;
		}
	}
	printf("Close String(GA) is :%s,smallest score is %f\n",gResult,bestScore);
    free(children);
}

//-----------------------------------------------
int main(int argc, char* argv[])
{
	
	
	printf("Begin a task...\n");
srand(time(NULL));
	MyTID = pvm_mytid();
	if (MyTID < 0)
	{
		pvm_perror("unable to start pvm");
		exit(EXIT_FAILURE);
	}
	printf("This is %d\n",MyTID);
	ParentTID = pvm_parent();   
	if (ParentTID == PvmNoParent)
	{
		printf("I am father!\n");
		GAMaster();
	}
	else
	{
		printf("I am child!\n");
		GAWorker();
	}
	pvm_exit();
	system("pause");

	return 0;
}