ga.cpp

本程序是针对多序列比对问题

	oldpop[popsize-1].chromosome[50]=16;
	oldpop[popsize-1].chromosome[51]=30;
	oldpop[popsize-1].chromosome[52]=0;
	oldpop[popsize-1].chromosome[53]=0;
	oldpop[popsize-1].chromosome[54]=0;
	oldpop[popsize-1].chromosome[55]=11;
	oldpop[popsize-1].chromosome[56]=14;
	oldpop[popsize-1].chromosome[57]=28;
	oldpop[popsize-1].chromosome[58]=0;
	oldpop[popsize-1].chromosome[59]=26;
	oldpop[popsize-1].chromosome[60]=31;
	oldpop[popsize-1].chromosome[61]=14;
	oldpop[popsize-1].chromosome[62]=17;
	oldpop[popsize-1].chromosome[63]=31;
	oldpop[popsize-1].chromosome[64]=0;
	oldpop[popsize-1].chromosome[65]=0;
	oldpop[popsize-1].chromosome[66]=12;
	oldpop[popsize-1].chromosome[67]=15;
	oldpop[popsize-1].chromosome[68]=10;
	oldpop[popsize-1].chromosome[69]=13;
	oldpop[popsize-1].chromosome[70]=38;
	oldpop[popsize-1].chromosome[71]=14;
	oldpop[popsize-1].chromosome[72]=39;
	oldpop[popsize-1].chromosome[73]=0;
	oldpop[popsize-1].chromosome[74]=0;
	oldpop[popsize-1].chromosome[75]=12;
	oldpop[popsize-1].chromosome[76]=15;
	oldpop[popsize-1].chromosome[77]=25;
	oldpop[popsize-1].chromosome[78]=28;
	oldpop[popsize-1].chromosome[79]=0;
	oldpop[popsize-1].chromosome[80]=0;
	oldpop[popsize-1].chromosome[81]=12;
	oldpop[popsize-1].chromosome[82]=15;
	oldpop[popsize-1].chromosome[83]=29;
	oldpop[popsize-1].chromosome[84]=14;
	oldpop[popsize-1].chromosome[85]=17;
	fitness(&(oldpop[popsize-1]));*/
	
	for(j=0;j<popsize;j++)
	{
		h=0;
		for(int i=0;i<sequence_number;i++)
		{	
			for(k=0;k<chromosize-(sequence_length[i]-min_sequence_length);k++)       
				oldpop[j].chromosome[k+h]=rnd(0,sequence_length[i]);//给染色体赋予随机序列					
			h+=chromosize-(sequence_length[i]-min_sequence_length);			
		}	
		fitness(&(oldpop[j]));		//计算初始种群的适应度
	}
}

void initialize()
{
	initmalloc();		//分配全局数据结构空间

	optimal_indivi->fitness=65535;		//初始化一些全局数据
	best_gen=0;
	best_T=T0;
	
	initpop();		//初始化种群并计算适应度
}

void change(struct individual *critter3,int a)		//变异算子操作
{
	int rnd_gen1;
	int rnd_gen2;
	int temp;
	int i,h;

	rnd_gen1=rnd(0,chromo_length-1);		//生成随机的两个所要提取的基因位置
	do
	{
		rnd_gen2=rnd(0,chromo_length-1);		//使得另一个基因位置不同于前一个基因位置
	}
	while(rnd_gen1==rnd_gen2);

	if(rnd_gen1>rnd_gen2)		//使得第一个基因位置rnd_gen1在第二个基因位置rnd_gen2前
	{
		temp=rnd_gen2;
		rnd_gen2=rnd_gen1;
		rnd_gen1=temp;
	}

	for(int n=0;n<chromo_length;n++)
		temper->chromosome[n]=critter3->chromosome[n];

	for(i=rnd_gen1,h=rnd_gen2;i<=rnd_gen2,h>=rnd_gen1;i++,h--)//反转两个基因间的染色体序列
	{
		temper->chromosome[i]=critter3->chromosome[h];
	}

	for(int b=0;b<chromo_length;b++)
		newpop[a].chromosome[b]=temper->chromosome[b];
}

void freeall()           //释放内存空间
{
	for(int i=0;i<popsize;i++)
	{
		delete[]oldpop[i].chromosome;
		delete[]newpop[i].chromosome;		
	}
	delete[]oldpop;
	delete[]newpop;
	delete[]midpop->chromosome;
	delete[]optimal_indivi->chromosome;
	delete[]temper->chromosome;
	//delete temper;
}

void output(struct individual *critter4)
{
	outfile<<"染色体为:"<<endl;
	
	int *array;
	int temp;
	int h=0;
	
	char *alignment[sequence_number];		//定义alignment序列
	
	if((array=new int[chromosize])==NULL)
		cout<<"can't allocate more memory.\n";

	for(int w=0;w<sequence_number;w++)
	{
		if((alignment[w]=new char[chromosize+min_sequence_length])==NULL)
			cout<<"can't allocate more memory.\n";
	}

	for(int i=0;i<sequence_number;i++)
	{
		for(int j=0;j<chromosize-(sequence_length[i]-min_sequence_length);j++)
			array[j]=critter4->chromosome[j+h];	//将染色体片断的值放入临时数组array中
		h+=chromosize-(sequence_length[i]-min_sequence_length);	

		for(int m=chromosize-(sequence_length[i]-min_sequence_length);m>1;m--)		//冒泡排序 使得array数组中的值从小到大排列
			for(int n=0;n<m-1;n++)
				if(array[n]>array[n+1])
				{
					temp=array[n+1];
					array[n+1]=array[n];
					array[n]=temp;
				}
		
		for(int l=0;l<sequence_length[i];l++)		//将sequence中的值放入alignment中
			alignment[i][l]=sequence[i][l];

		for(int k=chromosize-1-(sequence_length[i]-min_sequence_length);k>=0;k--)		//将GAP即'_'插入alignment中
		{
			if(array[k]>(sequence_length[i]+(chromosize-1-(sequence_length[i]-min_sequence_length)-k)))
					alignment[i][sequence_length[i]+(chromosize-1-(sequence_length[i]-min_sequence_length)-k)]='*';
			else
			{
				for(int m=chromosize+min_sequence_length-1;m>array[k];m--)				
					alignment[i][m]=alignment[i][m-1];
				alignment[i][array[k]]='*';
			}
		}

		for(int a=0;a<chromosize+min_sequence_length;a++)
			outfile<<alignment[i][a];
		outfile<<'\n';
	}
	
	outfile<<"适应度为："<<critter4->fitness<<endl;	
	outfile<<endl;

	delete[] array;
	for(int n=0;n<sequence_number;n++)
		delete[] alignment[n];
}

void main()
{
	double time1,time2,time_best;
	
	double cur_bestfitness;		//当前最佳适应值
	double Tk;
	double delta_fitness;
	double min;

	inputdata();
	time1=(double)clock();
	initreport();

	for(int k=0;k<sequence_number;k++)					//确定各个sequence的长度
	{
		if(sequence_length[k]<min_sequence_length)
			min_sequence_length=sequence_length[k];		//确定最短长度
		if(sequence_length[k]>max_sequence_length)
			max_sequence_length=sequence_length[k];		//确定最长长度
	}

	chromo_length=chromosize*sequence_number;
	for(int q=0;q<sequence_number;q++)
	{
		if(sequence_length[q]>min_sequence_length)//确定染色体的应该长度
			chromo_length=chromo_length-(sequence_length[q]-min_sequence_length);	
	}
	
	initialize();

	Tk=T0;
	while(Tk>exp(tem))
	{
		for(gen=0;gen<L;gen++)		//开始一个周期的代数
		{			
			for(int t=0;t<popsize;t++)
			{
				change(&(oldpop[t]),t);
				fitness(&(newpop[t]));
				
				delta_fitness=newpop[t].fitness-oldpop[t].fitness;
				if(1<exp(-delta_fitness/Tk))
					min=1;
				else min=exp(-delta_fitness/Tk);
	
				if(min>randomperc())
					for(int i=0;i<chromo_length;i++)
						oldpop[t].chromosome[i]=newpop[t].chromosome[i];
			}
		
			for(int d=0;d<popsize;d++)
				if(oldpop[d].fitness<optimal_indivi->fitness)	//将最优染色体保存起来
				{
					for(int f=0;f<chromo_length;f++)
						optimal_indivi->chromosome[f]=oldpop[d].chromosome[f];
					optimal_indivi->fitness=oldpop[d].fitness;
					best_T=Tk;
					best_gen=gen;
					time_best=(double)clock();
				}
		}

		cur_bestfitness=65535;
		for(int c=0;c<popsize;c++)
			if(oldpop[c].fitness<cur_bestfitness)
			{
				for(int h=0;h<chromo_length;h++)
					midpop->chromosome[h]=oldpop[c].chromosome[h];
				midpop->fitness=oldpop[c].fitness;
				cur_bestfitness=oldpop[c].fitness;
			}

		outfile<<"温度为"<<Tk<<"时:\n";
		output(midpop);

		Tk=Tk*alpha;
	}

	outfile<<"最佳";
	output(optimal_indivi);
	outfile<<"出现的温度为:"<<best_T<<"  出现在该温度的代数为:"<<best_gen<<endl;
	outfile<<"出现最佳的时间为:"<<(time_best-time1)<<"毫秒.\n";
	
	freeall();

	time2=(double)clock();
	outfile<<"程序运行时间为:"<<(time2-time1)<<"毫秒.\n";

	cout<<"遗传算法结束"<<endl;
}