liushuiqingqing.cpp

基于距离的免疫遗传算法

		peraff[i]=0;
	}
	for(i=0;i<treenumber;i++)
	{
		m=iniaffinity(treeorder[i]);
		if(m<0.0)
			peraff[i]=0.0;
		else if(m>=0.0)
			peraff[i]=m;
	}
	for(i=0;i<(treenumber-1);i++)
	{
		for(j=i+1;j<treenumber;j++)
		{
			if(peraff[i]>=peraff[j])
			{
				m=peraff[i];
				peraff[i]=peraff[j];
				peraff[j]=m;
			}
		}
	}
	maxaff=peraff[treenumber-1];
	return maxaff;
} 
double affinity(treenode * root)//计算以root为根的树的亲和力
{
	double aff;
	double max;
	double treeaff;
	max=findmaxaff();
	treeaff=iniaffinity(root);
	aff=(1.5-treeaff/max)*100;
	return aff;
}
/*int outputtree(treenode * root)//输出以root为根的树，这里用的是前根遍历
{
	int j;
	j=0;
	treenode * p;
	treenode * q;
	p=root;
	if(p!=NULL)
	{
		if(p->lchild==NULL && p->rchild==NULL)
		{
			printf("%d",p->element);
		}
		else
		{
			printf("%d",p->element);
			printf("%c",'(');
			printf("%c",'[');
			q=p->lchild;
			if(q!=NULL)
			{	
				for(j=0;j<(nodenum*(nodenum-1))/2;j++)
				{
					if(compointer[j].nodenum01==p->element && compointer[j].nodenum02==q->element)
					{
						printf("%d",compointer[j].comvalue);
					}
					else
						if(compointer[j].nodenum01==q->element && compointer[j].nodenum02==p->element)
						{
							printf("%d",compointer[j].comvalue);
						}
				}
			}
			printf("%c",']');
			outputtree(p->lchild);
			printf("%c",',');
            printf("%c",'[');
			q=p->rchild;
			if(q!=NULL)
			{	
				for(j=0;j<(nodenum*(nodenum-1))/2;j++)
				{
					if(compointer[j].nodenum01==p->element && compointer[j].nodenum02==q->element)
					{
						printf("%d",compointer[j].comvalue);
					}
					else
						if(compointer[j].nodenum01==q->element && compointer[j].nodenum02==p->element)
						{
							printf("%d",compointer[j].comvalue);
						}
				}
			}
			printf("%c",']');
			outputtree(p->rchild);
			printf("%c",')');
		}
	}
	return 0;
}*/
treenode * copytree(treenode * root)
{
	treenode * newlchild;
	treenode * newrchild;
	treenode * newroot;
	if(root==NULL)
	{
		newroot=NULL;
		return newroot;
	}
	if(root->lchild!=NULL)
	{
		newlchild=copytree(root->lchild);
	}
	else
	{
		newlchild=NULL;
	}
	if(root->rchild!=NULL)
	{
		newrchild=copytree(root->rchild);
	}
	else
	{
		newrchild=NULL;
	}
	newroot=(treenode *)malloc(sizeof(treenode));
	newroot->element=root->element;
	newroot->lchild=newlchild;
	newroot->rchild=newrchild;
	return newroot;
}
int freetree(treenode * root)//删除以root为根的树
{
	
     if(root!=NULL)
	{
		if(root->lchild==NULL && root->rchild==NULL)
		{

			free(root);
		}		

	}		
	 else
	 {	
		 freetree(root->lchild);
		 freetree(root->rchild);
	 }
	

		return 0;
}
int calweight(treenode * root)//计算以root为根的树的权值
{
	int i;
	treenode * p;
	p=root;
	if(p!=NULL)
	{
		if(p->lchild==NULL && p->rchild==NULL)
		{
			p->weight.lweight=0;
			p->weight.rweight=0;
		}
	if(p->lchild!=NULL && p->rchild==NULL)
	{
		for(i=0;i<((nodenum*(nodenum-1))/2);i++)
		{
			if(compointer[i].nodenum01==p->element && compointer[i].nodenum02==p->lchild->element)
			{
				p->weight.lweight=compointer[i].comvalue;
			}
			else
			{
				if(compointer[i].nodenum01==p->lchild->element && compointer[i].nodenum02==p->element)
				{
					p->weight.lweight=compointer[i].comvalue;
				}
			}
		}
	}
	else
	{
		p->weight.lweight=0;
	}
	
	if(p->rchild!=NULL && p->lchild==NULL)
	{
		for(i=0;i<((nodenum*(nodenum-1))/2);i++)
		{
			if(compointer[i].nodenum01==p->element && compointer[i].nodenum02==p->rchild->element)
			{
				p->weight.rweight=compointer[i].comvalue;
			}
			else
			{
				if(compointer[i].nodenum01==p->rchild->element && compointer[i].nodenum02==p->element)
				{
					p->weight.rweight=compointer[i].comvalue;
				}
			}
		}
	}
	else
	{
		p->weight.rweight=0;
	}
	if(p->lchild!=NULL && p->rchild!=NULL)
	{
		for(i=0;i<((nodenum*(nodenum-1))/2);i++)
		{
			if(compointer[i].nodenum01==p->element && compointer[i].nodenum02==p->lchild->element)
			{
				p->weight.lweight=compointer[i].comvalue;
			}
			else
			{
				if(compointer[i].nodenum01==p->lchild->element && compointer[i].nodenum02==p->element)
				{
					p->weight.lweight=compointer[i].comvalue;
				}
			}
		}
		for(i=0;i<((nodenum*(nodenum-1))/2);i++)
		{
			if(compointer[i].nodenum01==p->element && compointer[i].nodenum02==p->rchild->element)
			{
				p->weight.rweight=compointer[i].comvalue;
			}
			else
			{
				if(compointer[i].nodenum01==p->rchild->element && compointer[i].nodenum02==p->element)
				{
					p->weight.rweight=compointer[i].comvalue;
				}
			}
		}
	}
	}
	else
		return 0;
	calweight(p->lchild);
	calweight(p->rchild);
	return 0;
}
treenode * cross()
{
	treenode * root1;
	treenode * root2;
	treenode * s;
	treenode * t;
	treenode * r;
	int i;
	int j;
	int a;
	int b;
	i=rndnode1();
	j=rndnode1();
	a=rndtree();
	b=rndtree();
	root1=copytree(treeorder[a]);
	root2=copytree(treeorder[b]);
    s=findnode(root1,i);
	t=findnode(root2,j);
	r=s->lchild;
	s->lchild=t->lchild;
	t->lchild=r;
	freetree(root1);
	return root2;
}
treenode * findleft(treenode * root)//返回以root为根的树的最左边节点
{
    treenode * p;
	treenode * r;
	p=root;
	if(p->lchild==NULL && p->rchild!=NULL)
	{
		return p;
	}
	if((*p).lchild==NULL && (*p).rchild==NULL)
		return p;
	else
		return (r=findleft((*p).lchild));
}
int deletenode(treenode * root,treenode * p)//删除以root为根的节点p
{
	treenode * s;
	treenode * r;
	if(p==root)
	{
		return 0;
	}
	s=findfather(root,p);
    if(p->lchild==NULL && p->rchild==NULL)
	{
		if(p==s->lchild)
		{
			s->lchild=NULL;
		}
		else 
		{
			if(p==s->rchild)
			{
				s->rchild=NULL;
			}
		}
	}
	if(p->lchild!=NULL && p->rchild==NULL)
	{
		if(p==s->lchild)
		{
			s->lchild=p->lchild;
		}
		else
		{
			if(p==s->rchild)
			{
				s->rchild=p->lchild;
			}
		}

	}
	if(p->lchild==NULL && p->rchild!=NULL)
	{
		if(p==s->lchild)
		{
			s->lchild=p->rchild;
		}
		else
		{
			if(p==s->rchild)
			{
				s->rchild=p->rchild;
			}
		}
	}
	if(p->lchild!=NULL && p->rchild!=NULL)
	{
		r=findleft(p);
		if(p==s->lchild)
		{
			s->lchild=p->lchild;
			r->lchild=p->rchild;
		}
		else
		{
			if(p==s->rchild)
			{
				s->rchild=p->lchild;
				r->lchild=p->rchild;
			}
		}
	}
	free(p);
	return 0;
}
treenode * exchange()//变异
{
	int i;
	int j;
	treenode * p;
	treenode * q;
	treenode * root;
	j=rndtree();
	i=rndnode1();
	root=copytree(opetreeord[j]);
	while(i==root->element)
	{
		i=rndnode1();
	}
	p=findnode(root,i);
	deletenode(root,p);
	p=(treenode *)malloc(sizeof(treenode));
    q=findleft(root);
	q->lchild=p;
	p->element=i;
	p->lchild=NULL;
	p->rchild=NULL;
	return root;
}
int select()//选择
{
    int i;
	int j;
	double a;
	double temaff0[opetreenum];
	double temaff1[opetreenum];
	for(i=0;i<opetreenum;i++)
	{
		temaff0[i]=0.0;
		temaff1[i]=0.0;
	}
	for(i=0;i<opetreenum;i++)
	{
		temaff0[i]=affinity(opetreeord[i]);
		temaff1[i]=temaff0[i];
	}
    for(i=0;i<(opetreenum-1);i++)
	{
		for(j=i+1;j<opetreenum;j++)
		{
			if(temaff0[i]<=temaff0[j])
			{
				a=temaff0[i];
				temaff0[i]=temaff0[j];
				temaff0[j]=a;
			}
		}
	}
    for(i=0;i<opetreenum;i++)
	{
		for(j=0;j<opetreenum;j++)
		{
			if(temaff0[i]==temaff1[j])
			{
				opetreeord[i]=copytree(opetreeord[j]);
			}
		}
	}
	for(i=0;i<treenumber;i++)
	{
		treeorder[i]=copytree(opetreeord[i]);
	}
	return 0;
}
int CALWEIGHT()
{
	int i;
	for(i=0;i<treenumber;i++)//权值
	
		calweight(treeorder[i]);
	}
	return 0;
}
int calaf
	int i;
	for(i=0;i<treenumber;i++)//计算亲和力
	{
		iniaff[i]=affinity(treeorder[i]);
	}
	return 0;
}
int keepspe()
{
	int i;
	for(i=0;i<treenumber;i++)//保存个体
	{
		opetreeord[i]=copytree(treeorder[i]);
	}
	return 0;
}
int deltree()
{
	int i;
	for(i=0;i<treenumber;i++)
	{
		freetree(treeorder[i]);
	}
	return 0;
}
int crossope()
{
	int i;
	for(i=treenumber;i<(treenumber+(int)((opetreenum-treenumber)/2));i++)//交叉
	{
		opetreeord[i]=cross();
	}
	return 0;
}
int changeope()
{
	int i;
	for(i=(treenumber+(int)((opetreenum-treenumber)/2));i<opetreenum;i++)
	{
		opetreeord[i]=exchange();//变异
	}
	return 0;
}
int relspace()//释放空间
{
	int i;
	for(i=0;i<opetreenum;i++)
	{
		freetree(opetreeord[i]);
	}
	return 0;
}
int outfile(treenode * root)
{
	ofstream out;
	out.open("result.txt");
	treenode * stack[40];
	treenode * ptr,* par;
	int rear=1;
	int front=0;
	stack[0]=root;
	while(front<rear)
	{
		ptr=stack[front++];
		out<<ptr->element<<" ";
		par=findfather(root,ptr);
		if(par!=NULL) 	
		{
			out<<par->element<<" ";
			if(par->lchild==ptr)
			{
				out<<1<<" ";
				out<<par->weight.lweight<<" ";
			}
			else
			{
				out<<2<<" ";
				out<<par->weight.rweight<<" ";
			}
		}
		if(ptr->lchild!=NULL) stack[rear++]=ptr->lchild;
		if(ptr->rchild!=NULL) stack[rear++]=ptr->rchild;
	}
	out.close();
	return 0;
}