ga.cpp

有时间约束的车辆数优化的C程序（遗传算法）

		stNew1->iXSite2=pos2;
		stNew2->iXSite1=pos1;
		stNew2->iXSite2=pos2;
	}
	return OK;
}
/*******************************************************************/
/* 函数名：  OrderedCrossover(stOld1,stOld2,stNew1,stNew2)         */
/* 参  数：  stOld1,stOld2:参加交叉的旧个体                        */
/*           stNew1,stNew2:运算之后的旧个体                        */
/* 返回值：  Ok-1,NO-0                                             */
/* 功  能：  顺序交叉产生新个体                                    */
/*******************************************************************/
int OrderedCrossover(struct individual *stOld1,struct individual *stOld2,
					 struct individual *stNew1,struct individual *stNew2)
{
	int i=0,j=0,k;
	int *iTemp;
	int pos1,pos2;
	double p;

	CopyStruct(stOld1,stNew1);
	CopyStruct(stOld2,stNew2);
	p=Randomize(0,10000)/10000.0;
	if(p<dPCross){
		if((iTemp=(int*)calloc(iChromLong+1,sizeof(int)))==NULL){
			return NO;
		}
		for(i=0; i<iChromLong; i++) iTemp[i]='\0';//初始化临时变量
		pos1=Randomize(0,iChromLong-1);
		pos2=Randomize(0,iChromLong-1);
		while(pos1==pos2){
			pos2=Randomize(0,iChromLong-1);
		}
		if(pos2<pos1){
			k=pos2;
			pos2=pos1;
			pos1=k;
		}
		for(i=pos1+1; i<=pos2; i++){//个体1中与个体2映射段相同的基因置空
			for(j=0; j<iChromLong; j++){
				if(stNew1->iChrom[j]==stOld2->iChrom[i]) break;
			}
			stNew1->iChrom[j]=-1;
		}
		j=0;
		i=pos2;
		do{//把非空的基因排列到临时数组中
			i++;
			if(stNew1->iChrom[i%iChromLong]!=-1){
				iTemp[j]=stNew1->iChrom[i%iChromLong];
				j++;
			}
		}while(i%iChromLong!=pos2);
		for(i=pos1+1; i<pos2+1; i++){//把个体2的交换部分放到临时数组后面
			iTemp[j]=stOld2->iChrom[i];
			j++;
		}
		iTemp[j]='\0';
		i=pos2+1;
		for(j=0; j<iChromLong; j++){//把临时数组中数据写回个体1
			stNew1->iChrom[i%iChromLong]=iTemp[j];
			i++;
		}
		stNew1->iChrom[iChromLong]='\0';

		for(i=pos1+1; i<=pos2; i++){//个体2中与个体1映射段相同的基因置空
			for(j=0; j<iChromLong; j++){
				if(stNew2->iChrom[j]==stOld1->iChrom[i]) break;
			}
			stNew2->iChrom[j]=-1;
		}
		j=0;
		i=pos2;
		do{//把非空的基因排列到临时数组中
			i++;
			if(stNew2->iChrom[i%iChromLong]!=-1){
				iTemp[j]=stNew2->iChrom[i%iChromLong];
				j++;
			}
		}while(i%iChromLong!=pos2);
		for(i=pos1+1; i<=pos2; i++){//把个体1的交换部分放到临时数组后面
			iTemp[j]=stOld1->iChrom[i];
			j++;
		}
		iTemp[j]='\0';
		i=pos2+1;
		for(j=0; j<iChromLong; j++){//把临时数组中数据写回个体1
			stNew2->iChrom[i%iChromLong]=iTemp[j];
			i++;
		}
		stNew2->iChrom[iChromLong]='\0';
		stNew1->iXSite1=pos1;
		stNew1->iXSite2=pos2;
		stNew2->iXSite1=pos1;
		stNew2->iXSite2=pos2;
		free(iTemp);
	}
	return OK;
}

/*******************************************************************/
/* 函数名：  CycleCrossover(stOld1,stOld2,stNew1,stNew2)           */
/* 参  数：  stOld1,stOld2:参加交叉的旧个体                        */
/*           stNew1,stNew2:运算之后的旧个体                        */
/* 返回值：  Ok-1,NO-0                                             */
/* 功  能：  顺序交叉产生新个体                                    */
/*******************************************************************/
int CycleCrossover(struct individual *stOld1,struct individual *stOld2,
				   struct individual *stNew1,struct individual *stNew2)
{
	int i=0,k=0;
	double p;
	
	p=Randomize(0,10000)/10000.0;
	if(p<dPCross){
		for(i=0; i<iChromLong; i++){
			stNew1->iChrom[i]=-1;
			stNew2->iChrom[i]=-1;
		}
		stNew1->iChrom[i]='\0';
		stNew2->iChrom[i]='\0';
		k=0;
		do{
			stNew1->iChrom[k]=stOld1->iChrom[k];
			for(i=0; i<iChromLong; i++){
				if(stOld1->iChrom[i]==stOld2->iChrom[k]){
					k=i;
					break;
				}
			}
		}while(k!=0);
		for(i=0; i<iChromLong; i++){
			if(stNew1->iChrom[i]==-1){
				stNew1->iChrom[i]=stOld2->iChrom[i];
			}
		}
		k=0;
		do{
			stNew2->iChrom[k]=stOld2->iChrom[k];
			for(i=0; i<iChromLong; i++){
				if(stOld2->iChrom[i]==stOld1->iChrom[k]){
					k=i;
					break;
				}
			}
		}while(k!=0);
		for(i=0; i<iChromLong; i++){
			if(stNew2->iChrom[i]==-1){
				stNew2->iChrom[i]=stOld1->iChrom[i];
			}
		}
		stNew1->iXSite1=0;
		stNew1->iXSite2=0;
		stNew2->iXSite1=0;
		stNew2->iXSite2=0;
	}
	else{
		CopyStruct(stOld1,stNew1);
		CopyStruct(stOld2,stNew2);
	}
	return OK;
}

/*******************************************************************/
/* 函数名：  CrossoverOperator(stOld1,stOld2,stNew1,stNew2,iFlag)  */
/* 参  数：  stOld1,stOld2:参加交叉的旧个体                        */
/*           stOld1,stOld2:运算之后的旧个体                        */
/*           iFlag:1-PMX,2-OX,3-CX                                 */
/* 返回值：  Ok-1,NO-0                                             */
/* 功  能：  交叉操作产生新个体                                    */
/*******************************************************************/
int CrossoverOperator(struct individual *stOld1,struct individual *stOld2,
				      struct individual *stNew1,struct individual *stNew2,
					  int iFlag)
{
	switch(iFlag){
	case 1:
		PartiallyMatchedCrossover(stOld1,stOld2,stNew1,stNew2);
		break;
	case 2:
		OrderedCrossover(stOld1,stOld2,stNew1,stNew2);
		break;
	case 3:
		CycleCrossover(stOld1,stOld2,stNew1,stNew2);
		break;
	default:
		return NO;
	}
	return OK;
}

/*******************************************************************/
/* 函数名：  GenerationCalculate(iCrossFlag,iMutationFlag)         */
/* 参  数：  iCrossFlag:   参加交叉的旧个体                        */
/*           iMutationFlag:运算之后的旧个体                        */
/* 返回值：  错误代码                                              */
/* 功  能：  进行一次选择、交叉、变异运算                          */
/*******************************************************************/
int GenerationCalculate(int iCrossFlag, int iMutationFlag)
{
	int k=0,mate1,mate2;

	do{
		/* 选择操作 */
		mate1=SelectionOperator();
		mate2=SelectionOperator();//&&&&&
		/* 交叉操作 */
		if(CrossoverOperator(stOldPopulation+mate1,stOldPopulation+mate2,
			stNewPopulation+k,stNewPopulation+k+1,iCrossFlag)==NO){
			return ERR_GA_CROS;
		}
		stNewPopulation[k].iParent[0]=mate1;
		stNewPopulation[k].iParent[1]=mate2;
		stNewPopulation[k+1].iParent[0]=mate1;
		stNewPopulation[k+1].iParent[1]=mate2;
		stNewPopulation[k].iGeneration=iGeneration;
		stNewPopulation[k+1].iGeneration=iGeneration;
		/* 变异操作 */
		/*if(MutationOperator(stNewPopulation+k,iMutationFlag)==NO){
			return ERR_GA_MUTA;
		}
		if(MutationOperator(stNewPopulation+k+1,iMutationFlag)==NO){
			return ERR_GA_MUTA;
		}*/
		/* 计算适应度值 */
		if(CalculateFitnessValue(stNewPopulation+k)==NO){
			return ERR_GA_CALC;
		}
		if(CalculateFitnessValue(stNewPopulation+k+1)==NO){
			return ERR_GA_CALC;
		}
		/* 用模拟退火算法作为变异操作 */
		if(SimulatedAnnealing(stNewPopulation+k)==NO){
			return ERR_GA_SANN;
		}
		if(SimulatedAnnealing(stNewPopulation+k+1)==NULL){
			return ERR_GA_SANN;
		}
		k+=2;
	}while(k<iPopSize-1);
	return OK;
}

/*******************************************************************/
/* 函数名：  GenerationCalculate(iXFlag,iMFlag)                    */
/* 参  数：  iXFlag:   交叉算子标识                                */
/*           iMFlag:   变异算子标识                                */
/* 返回值：  错误代码                                              */
/* 功  能：  进行一轮计算，同一参数下计算iMaxRuns次                */
/*******************************************************************/
int GeneticSimulatedAnnealing(int iXFlag, int iMFlag)
{
	int k=0,i=0,j=0;
	int ret;
	int iNewMinPos,iNewMaxPos;

	for(k=1; k<=iMaxRuns; k++){
		if(InitiateVMemory()==NO){//动态分配空间
			return ERR_GA_MEMO;
		}
		if(GetData()==NO){//获取计算数据
			return ERR_GA_DATA;
		}
		//TestData();
		if(CreatePopulation()==NO){//创建初始群体
			return ERR_GA_POPU;
		}
		iGeneration=0;
		iRun+=1;//记录当前运行次数
		/*$$fprintf(outfp,"\n\n================第 %d / %d 次===============================\n",
			iRun,iMaxRuns);*/
		for(i=0; i<iMaxGen; i++){
			/* 求最佳个体，计算累计、平均、最大、最小适应度 */
			Statistics();
			/* 报告当前代的统计数据 */
			ReportData();
			/*记录当前的世代数 */
			iGeneration+=1;
			/* 遗传计算 */
			ret=GenerationCalculate(iXFlag, iMFlag);
			if(ret!=OK) return ret;
			stOldMin.dFitness=stOldPopulation[0].dFitness;
			stNewMax.dFitness=stNewPopulation[0].dFitness;
			stNewMin.dFitness=stNewPopulation[0].dFitness;
			for(j=0; j<iPopSize; j++){
				if(stOldPopulation[j].dFitness<stOldMin.dFitness)
					CopyStruct(stOldPopulation+j,&stOldMin);
				if(stNewPopulation[j].dFitness<stNewMin.dFitness)
					iNewMinPos=j;
				if(stNewPopulation[j].dFitness>stNewMax.dFitness)
					iNewMaxPos=j;
			}
			if(stNewPopulation[iNewMinPos].dFitness>stOldMin.dFitness){
				CopyStruct(&stOldMin,stOldPopulation+iNewMaxPos);
				//fprintf(stderr,"\tiNewMaxPos=%d,fitness1=[%f],fitness2=[%f]\n",
				//	iNewMaxPos,stOldMin.dFitness,stOldPopulation[iNewMaxPos].dFitness);
			}
		}
		/* 求最佳个体，计算累计、平均、最大、最小适应度 */
		Statistics();
		/* 报告遗传计算后的统计数据 */
		//$$fprintf(outfp,"====================================================\n");
		ReportData();
		/*$$for(j=0; j<iPopSize; j++){
			fprintf(outfp,"F=[%f]\t",stOldPopulation[j].dFitness);
		}
		fprintf(outfp,"\n====================================================\n");*/
		_flushall();
		FreeVMemory();
	}
	return OK;
}/*在注释中有符号$$的是为了便于统计而注释掉的*/

/*******************************************************************/
/* 函数名：  GenerationCalculate(iXFlag,iMFlag)                    */
/* 参  数：  iXFlag:   交叉算子标识                                */
/*           iMFlag:   变异算子标识                                */
/* 返回值：  错误代码                                              */
/* 功  能：  进行一轮计算，同一参数下计算iMaxRuns次                */
/*******************************************************************/
/*int ReportData()
{
	int k;
	fprintf(outfp,"第%d / %d次，第%d / %d代：车辆数：[%d]\n",
		iRun,iMaxRuns,iGeneration,iMaxGen,stBestFit.iCarNum);
	fprintf(outfp,"MaxFit=%f,\tMinFit=%f,\tAvgFit=%f\n",dMaxFitness,stBestFit.dFitness,dAvgFitness);
	for(k=0; k<iChromLong; k++){
		fprintf(outfp,"[%d],",stBestFit.iChrom[k]);
	}
	fputc('\n',outfp);
	for(k=0; k<stBestFit.iCarNum; k++){
		fprintf(outfp,"(%d),",stBestFit.iLineStartPos[k]);
	}
	fputc('\n',outfp);
	return OK;
}*/

/* 这是为了便于统计而重新写的报告函数 */
int ReportData()
{
	int k;
	fprintf(outfp,"%2d,%2d,%3d,%3d,%2d,%9.6f,%9.6f,%9.6f",
		iMaxRuns,iRun,iMaxGen,iGeneration,stBestFit.iCarNum,
		dMaxFitness,stBestFit.dFitness,dAvgFitness);
	//fprintf(outfp,"MaxFit=%f,\tMinFit=%f,\tAvgFit=%f\n",dMaxFitness,stBestFit.dFitness,dAvgFitness);
	for(k=0; k<iChromLong; k++){
		fprintf(outfp,",");
		fprintf(outfp,"[%2d]",stBestFit.iChrom[k]);
	}
	//fputc('\n',outfp);
	for(k=0; k<stBestFit.iCarNum; k++){
		fprintf(outfp,",");
		fprintf(outfp,"(%2d)",stBestFit.iLineStartPos[k]);
	}
	fputc('\n',outfp);
	return OK;
}

int main(int argc,char *argv[])    /*  主程序  */
{
	int ret;
	clock_t cTick;

	if(argc<6){
		fprintf(stderr,"parameter error,Use:ga outfile parameterfile datafile iXflag iMflag\n");
		exit(-1);
	}
	strcpy(filePara,argv[2]);
	strcpy(fileData,argv[3]);
	if((outfp=fopen(argv[1],"w"))==NULL){
		fprintf(stderr,"\nCannot open file %s! \n",argv[1]);
		exit(-1);
	}
	srand((int)time(NULL));
	if((ret=GetParameterValue())==NO){
		fprintf(stderr,"\nread GA's parameter error!");
		exit(-1);
	}
	//TestPara();
	ret=GeneticSimulatedAnnealing(atoi(argv[4]), atoi(argv[5]));
	if(ret==NO){
		fprintf(stderr,"\nCannot run GeneticSimulatedAnnealing!");
		exit(-1);
	}
	
	cTick=clock();
	fprintf(outfp,"run time = %d\n",cTick/CLK_TCK);
	_flushall();
	fclose(outfp);

	return OK;
}