sga.cpp

描述一种算法——遗传算法

///////////////////////////////////////////////////////////////////////////////////
/////********************随机数发生器*************************///
void advance_random()//产生55个随机数
{
	int j1;
	double new_random;
	for(j1=0;j1<24;j1++)
	{
		new_random=oldrand[j1]-oldrand[j1+31];
		if(new_random<0.0) new_random+=1.0;
		oldrand[j1]=new_random;
	}
	for(j1=24;j1<55;j1++)
	{
		new_random=oldrand[j1]-oldrand[j1-24];
		if(new_random<0.0) new_random+=1.0;
		oldrand[j1]=new_random;
	}
}
int flip(float prob)//以一定的概率产生0，1
{
	if(randomperc()<=prob)
		return 1;
	else 
		return 0;
}
void randomize()//设定随机数种子并初始化随机数发生器
{
	float randomseed;
	int j1;
	for(j1=0;j1<=54;j1++)
		oldrand[j1]=0.0;
	jrand=0;
	do
	{
//		setcolor(9);
//		setbkcolor(15);
		printf("随机数种子[0-1]：");
		scanf("%f",&randomseed);
	}while((randomseed<0.0)||(randomseed>1.0));
	warmup_random(randomseed);
}
double randomnormaldeviate()//产生随机标准差
{
	double t,rndx1;
	if(rndcalcflag)
	{
		rndx1=sqrt(-2.0*log((double)randomperc()));
		t=6.2831853072*(double)randomperc();
		rndx1=rndx1*sin(t);
	}
	else
	{
		rndcalcflag=1;
		return rndx1;
	}
}
float randomperc()//产生[0，1]之间的一个随机数
{
//	srand((unsigned)time(NULL));
//	rand();
//
//	float rnd=(float)rand()/RAND_MAX;
//	return rnd;
	
	jrand++;
	if(jrand>=55)
	{
		jrand=1;
		advance_random();
	}
	return ((float)oldrand[jrand]);

}
int rnd(int low,int high)//在整数low,high之间产生一随机整数
{
	int i;
	if(low>=high) i=low;
	else
	{
		i=(randomperc()*(high-low+1))+low;
		if(i>high) i=high;
	}
	return i;
}
void warmup_random(float random_seed)//初始华随机数发生器
{
	int j1,ii;
	double new_random;
	double prev_random=INITRANDOM;
	oldrand[54]=random_seed;
	new_random=1/pow(10,10);
	for(j1=1;j1<=54;j1++)
	{
		ii=(21*j1)%54;
		oldrand[ii]=new_random;
		new_random=prev_random-new_random;
		if(new_random<0.0)new_random+=1.0;
		prev_random=oldrand[ii];

	}
	advance_random();
	advance_random();
	advance_random();
}
/**********************************************************************************
/*************************************************/
//initpop() 产生初始化种群设计的函数
/**************************************************/
void initpop()
{
	int j,j1,k,stop;
	unsigned mask=1;
	for(j=0;j<popsize;j++)
	{
		for(k=0;k<chromsize;k++)
		{
			oldpop[j].chrom[k]=0;
			if(k==(chromsize-1))
			{
				stop=lchrom-(k*(8*sizeof(unsigned)));
			}
			else
				stop=8*sizeof(unsigned);
			for(j1=1;j1<=stop;j1++)
			{
				oldpop[j].chrom[k]=oldpop[j].chrom[k]<<1;
				if(flip(0.5))
					oldpop[j].chrom[k]=oldpop[j].chrom[k]|mask;
			}
		}

		oldpop[j].parent[0]=0;	//初始化父个体信息
		oldpop[j].parent[1]=0;
		oldpop[j].xsite=0;
		objfunc(&(oldpop[j]));	//计算初始适应度
	}
}

/*************************************************/
//objfunc() 解码和适应度计算函数，用来计算适应度函数值
//个体适应度函数：
//	critter.fitness=critter.varible*sin(10*pi*critter.varible)+2
/**************************************************/
void objfunc(struct individual *critter)
{
	unsigned mask=1;
	unsigned bitpos;
	unsigned tp;
	double bitpow;
	int j,k,stop;
	critter->varible=0.0;
	for(k=0;k<chromsize;k++)
	{
		if(k==(chromsize-1))
			stop=lchrom-(k*(8*sizeof(unsigned)));
		else
			stop=8*sizeof(unsigned);
		tp=critter->chrom[k];
		for(j=0;j<stop;j++)
		{
			bitpos=j+(8*sizeof(unsigned))*k;
			if((tp&mask)==1)
			{
				bitpow=pow(2.0,(double)bitpos);
				critter->varible=critter->varible+bitpow;
			}
			tp=tp>>1;
		}

	}
	critter->varible=MINVARIABLE+critter->varible*(MAXVARIABLE-MINVARIABLE)/(pow(2.0,(double)lchrom)-1);
	critter->fitness=critter->varible*sin(critter->varible*10*atan(1)*4)+2.0;
}
/*************************************************/
//遗传操作设计函数
//preselect() 选择遗传操作----轮盘赌选择设计，返回种群中被选择的个体编号；
/**************************************************/
void preselect()
{
	int j;
	sumfitness=0;
	for(j=0;j<popsize;j++)
	{
		sumfitness+=oldpop[j].fitness;
	}
}
/*************************************************/
//遗传操作设计函数
//select() 选择遗传操作----轮盘赌选择设计，返回种群中被选择的个体编号；

/**************************************************/
int select()
{
	float sum,pick;
	int i;
	pick=randomperc();
	sum=0;
	if((sumfitness!=0))
	{
		for(i=0;(sum<pick)&&(i<popsize);i++)
		{
			sum+=oldpop[i].fitness/sumfitness;
		}
	}
	else
		i=rnd(1,popsize);
	return(i-1);
}


/*************************************************/
//遗传操作设计函数
//crossover() 交叉遗传操作----单点交叉操作设计，由两个父个体交叉产生两个子个体
//	返回交叉点位置
/**************************************************/
int crossover(unsigned *parent1,unsigned *parent2,unsigned *child1,unsigned *child2)
{
	int j,jcross,k;
	unsigned mask,temp;
	if(flip(pcross))
	{
		jcross=rnd(1,(lchrom-1));
		ncross++;
		for(k=1;k<=chromsize;k++)
		{
			if(jcross>=(k*(8*sizeof(unsigned))))	
			{
				child1[k-1]=parent1[k-1];
				child2[k-1]=parent2[k-1];
			}
			else
				if((jcross<(k*(8*sizeof(unsigned))))&&(jcross>((k*-1)*(8*sizeof(unsigned)))))
				{
					mask=1;
					for(j=1;j<=(jcross-1-((k-1)*(8*sizeof(unsigned))));j++)
					{
						temp=1;
						mask=mask<<1;
						mask=mask|temp;
					}
					child1[k-1]=(parent1[k-1]&mask)|(parent2[k-2]&(~mask));
					child2[k-1]=(parent1[k-1]&(~mask))|(parent2[k-2]&mask);
				}
				else
				{
					child1[k-1]=parent2[k-1];
					child2[k-1]=parent1[k-1];					
				}

		}
	}
	else
	{
		for(k=0;k<chromsize;k++)
		{
			child1[k]=parent1[k];
			child2[k]=parent2[k];
		}
		jcross=0;
	}
	return jcross;
}

/*************************************************/
//遗传操作设计函数
//mutation() 变异遗传操作----按照变异概率pmutation确定个体child的编码位是否发生操作，
//		若某编码位发生变异，则该编码翻转
//	
/**************************************************/
void mutation(unsigned *child)
{
	int j,k,stop;
	unsigned mask,temp=1;
	for(k=0;k<chromsize;k++)
	{
		mask=0;
		if(k==(chromsize-1))
			stop=lchrom-(k*(8*sizeof(unsigned)));
		else
			stop=8*sizeof(unsigned);
		for(j=0;j<stop;j++)
		{
			if(flip(pmutation))
			{
				mask|=(temp<<j);
				nmutation++;
			}
		}
		child[k]=child[k]^mask;
	}
}

/*************************************************/
//遗传操作设计函数
//generation() 世代进化过程遗传操作----模拟世代进化过程，以种群处理对象实现世代内的三
//		种遗传操作：在当前种群中用select函数选择两个个体-->
//				对两个个提按交叉概率实行可行的交叉操作和变异操作-->
//				对个体解码、计算适应度、记录亲自信息数据，生成新个体
/**************************************************/
void generation()
{
	int mate1,mate2,jcross,j=0;
	preselect();
	//选择，交叉，变异	
	do
	{
	//挑选交叉配对
		mate1=select();
		mate2=select();
	//交叉和变异
		jcross=crossover(oldpop[mate1].chrom,oldpop[mate2].chrom,newpop[j].chrom,newpop[j+1].chrom);
		mutation(newpop[j].chrom);
		mutation(newpop[j+1].chrom);
	//解码，计算适应度
		objfunc(&(newpop[j]));
	//记录亲代关系和交叉位置
		newpop[j].parent[0]=mate1+1;
		newpop[j].xsite=jcross;
		newpop[j].parent[1]=mate2+1;
		objfunc(&(newpop[j+1]));
		newpop[j+1].parent[0]=mate1+1;
		newpop[j+1].xsite=jcross;
		newpop[j+1].parent[1]=mate2+1;
		j+=2;
	}while(j<(popsize-1));
}
/*********************************************/
/////////////////主函数///////////////////////
/////////////////主函数///////////////////////
/***********************************************/
int main(int argc,char *argv[])
{
	struct individual *temp;
//	FILE *fopen();
//	void title();
//	char *malloc();
	if((outfp=fopen("test.txt","w"))==NULL)
	{
		fprintf(stderr,"Cannot open output file %s\n",argv[1]);
		exit(-1);
	}
//	g_init();
//	setcolor(9);
//	setbkcolor(15);
	title();
	printf("输入遗传算法执行的次数（1-5）");
	scanf("%d",&maxruns);
	for(run =1;run<=maxruns;run++)
	{
		initialize();
		for(gen=0;gen<maxgen;gen++)
		{
			fprintf(outfp,"\n第%d/%d次运行：当前代为%d,共%d代\n",run,maxruns,gen,maxgen);
		//产生新一代
			generation();
		//计算新一代种群的适应度统计
			statistics(newpop);
		//输出新一代统计的数据
			report();
			temp=oldpop;
			oldpop=newpop;
			newpop=temp;
		}
		freeall();
	}
	return 0;

}