pso.cpp

粒子群算法与遗传算法用于优化的问题求解,可以解决一些

		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 x=0;x<sequence_number;x++)		//计算所生成的alignment比较结果，即适应度
		for(int y=1;y<sequence_number;y++)
			if(x<y)
			{
				for(int p=0;p<chromosize+min_sequence_length;p++)
				{
					if(alignment[x][p]==alignment[y][p])
						continue;
					if((alignment[x][p]=='-')||(alignment[y][p]=='-'))
						sum+=1.00;
					else if((alignment[x][p]=='a')&&(alignment[y][p]=='g'))
							sum+=0.45;
					else if((alignment[x][p]=='g')&&(alignment[y][p]=='a'))
							sum+=0.45;
					else if((alignment[x][p]=='u')&&(alignment[y][p]=='c'))
							sum+=0.45;
					else if((alignment[x][p]=='c')&&(alignment[y][p]=='u'))
							sum+=0.45;
					else	sum+=0.77;
				}
			}
	
	critter->fitness=sum;
	
	delete[] array;

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

void  initpop()       //随即初始化种群
{
	int j,k,h ;//,min_j;
	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]);//给染色体赋予随机序列	
				//!!!!!!!!!!!!!!!!!!!!!!!!add for pso
				oldpop[j].speed[k+h] = maxv * randomperc();//初始化染色体各维速度。
				if(randomperc()>0.5)
					oldpop[j].speed[k+h]= -oldpop[j].speed[k+h];
				oldpop[j].lbestp[k+h]=oldpop[j].chromosome[k+h];//初始化染色体最好位置。
				//!!!!!!!!!!!!!!!!!!!!!!!!add for pso
			}
			h+=chromosize-(sequence_length[i]-min_sequence_length);			
		}	
		fitness(&(oldpop[j]));		//计算初始种群的适应度
	
		//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!add for pso
		oldpop[j].lbestfit = oldpop[j].fitness;
	}
//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
}
//初始化速度，位置的最小值和最大值。
void initpso()
{
	maxx = (max_sequence_length);
	minx = 0 ;
	maxv = (float)(max_sequence_length)/10;
	minv = -(float)(max_sequence_length)/10;
}

void initialize()
{
	initmalloc();		//分配全局数据结构空间
	optimal_indivi->fitness=65535;		//初始化一些全局数据
	best_cycle=0;
	best_gen=0;
	initpso(); 
	initpop();		//初始化种群并计算适应度	    
}


void combination(struct individual *critter2,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]=critter2->chromosome[n];
//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!modified 2005,10,29
//for 第2部分
	for(i=rnd_gen1,h=rnd_gen2;i<=rnd_gen2,h>=rnd_gen1;i++,h--)//反转两个基因间的染色体序列
	{
		temper->chromosome[i]=critter2->chromosome[h];
	}

	fitness(temper);		//计算反转后的染色体的适应度

//modified by william 2005-10-23
//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
	if(temper->fitness<critter2->fitness)	//假如适应度降低了 就生成新的染色体序列
	{
		for(int s=0;s<chromo_length;s++)
			midpop[a].chromosome[s]=temper->chromosome[s];
		midpop[a].fitness=temper->fitness;
	}
	
	else 
	{
		for(int s=0;s<chromo_length;s++)	//否则保持原先的染色体序列
			midpop[a].chromosome[s]=critter2->chromosome[s];
		midpop[a].fitness=critter2->fitness;
	}
	
//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

}

void freeall()           //释放内存空间
{
	for(int i=0;i<popsize;i++)
	{
		delete[]oldpop[i].chromosome;
			delete[]oldpopz3[i].chromosome;
			delete[]oldpopz4[i].chromosome;
		
		delete[]newpop[i].chromosome;

		delete[]midpop[i].chromosome;
	}
	delete[]oldpop;
	delete[]oldpopz3;
	delete[]oldpopz4;

	delete[]newpop;
	delete[]midpop;
	delete[]optimal_indivi->chromosome;

	delete[]oldpopz1->chromosome;
	delete[]oldpopz2->chromosome;
	delete[]pz->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;

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


void change(struct individual *critter4)	//变异算子操作
{
	int rnd_gen1;
	int rnd_gen2;
	int rnd_gen3;	
	do			//产生染色体中随机的三个位置，相互不同
	{
		rnd_gen1=rnd(0,chromo_length-1);
		rnd_gen2=rnd(0,chromo_length-1);
		rnd_gen3=rnd(0,chromo_length-1);
	}
	while((rnd_gen1!=rnd_gen2)&&(rnd_gen1!=rnd_gen3)&&(rnd_gen2!=rnd_gen3));
	critter4->chromosome[rnd_gen1]=rnd(0,max_sequence_length);		//对这三个随机位置赋予随机值
	critter4->chromosome[rnd_gen2]=rnd(0,max_sequence_length);
	critter4->chromosome[rnd_gen3]=rnd(0,max_sequence_length);
}

int select()   //轮盘赌选择算法
{
	double total,pick;
	int i;
	pick=randomperc();
	total=0.0;
	
	for(i=0;(total<=pick)&&(i<popsize);i++)
		total+=newpop[i].fitness/sumfitness;	
	return (i-1);
}
//!!!!!!!!!!!!!!!!!!!!!!!!run at the begin of main function and ga function
void begin()
{
	inputdata();
	//time1=(double)clock();		//程序开始的时间
	for(int k=0;k<sequence_number;k++)					//确定各个sequence的长度
	{
		//sequence_length[k]=sizeof(sequence[k])-1;
		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();
	initreport();
}
//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

void GA()
{
	double time1,time2,time_best;	
	double midfitness;			//保存适应度中间值
	int h;
	int already_optimal=0;	//最佳染色体出现了几代相同了
	int rnd_change,rnd_com;		//变异算子和组合算子所操作的染色体序号（0－popsize）
	int change_num,com_number,select_num;//已经进行了多少次变异算子和组合算子操作
	double cur_bestfitness=65535;		//当前最佳适应值
	double Pm;//变异概率
	double Pc;//选择概率
	time1=(double)clock();		//程序开始的时间
	
	//begin();
//	for(cycle=0;cycle<2;cycle++)	
	
	for(cycle=0;cycle<GLs;cycle++)	//开始进化周期
	{
		//	for(gen=0;gen<2;gen++)
		
	for(gen=0;gen<GEG;gen++)		//开始一个周期的代数
		{
			change_num=0;
			com_number=0;
			Pm=0.02;
			Pc=0.8;

			//组合算子操作，组合概率为Pc
			rnd_com=rnd(0,popsize-1);
			while(com_number<popsize*Pc)		//当组合概率还未达到Pc时
			{
				combination(&(oldpop[rnd_com]),rnd_com);		//进行组合算子操作
				
				com_number++;
				oldpop[rnd_com].fitness=65535;		//登记该染色体已经进行了组合操作，避免下次再选择它做组合算子

				do		//选择另一个染色体进行组合算子操作
				{
					rnd_com=rnd(0,popsize-1);
				}
				while(oldpop[rnd_com].fitness==65535);
			}
				
			for(int v=0;v<popsize;v++)		//对其余未进行组合算子操作的染色体 全部进入下一步操作
				if(oldpop[v].fitness!=65535)
				{
					for(int u=0;u<chromo_length;u++)
						midpop[v].chromosome[u]=oldpop[v].chromosome[u];
					midpop[v].fitness=oldpop[v].fitness;
				}

			//计算所有染色体的适应度之和
			sumfitness=0.0;