liushuiqingqing.cpp

基于距离的免疫遗传算法

#include"string.h"
#include"stdio.h"
#include"stdlib.h"
#include"time.h"
#include"math.h"
#include"fstream.h"
#define nodenum  20
#define treenumber 10 
#define opetreenum 16
#define maxgen 5
typedef struct WEIGHT
{
	int lweight;
	int rweight;
}  TW;
typedef struct TREENODE
{
	int element;
	TW  weight;
	struct TREENODE * lchild;
	struct TREENODE * rchild;
}  treenode;
typedef struct COMPARERES//假设比对的距离值记录在这样的结构里面
{
	int nodenum01;
	int nodenum02;
	int comvalue;
}  compareres;
typedef struct NODEDISTANCE//叶子节点的路径长度保存在这样的结构里面
{
	int nodenum1;
	int nodenum2;
	int nodedis;
}  distance;
treenode * treeorder[treenumber];//保存群体
treenode * opetreeord[opetreenum];//保存操作以后的群体
compareres  compointer[(nodenum*(nodenum-1))/2];//保存距离的数组
distance  nodedis[(nodenum*(nodenum-1))/2];
int leafnum[nodenum];//保存一棵树中的叶子节点
int nodeorder[nodenum];//节点顺序
int samenode[nodenum];//寻找相同节点是保存节点值
double iniaff[treenumber];
int readcomvalue();
int initial();
int rndnode0();
int rndnode1();
int rndtree();
int outfile(treenode * root);
treenode * createtree(int ,int );
treenode * findfather(treenode  * , treenode * );
treenode * findnode(treenode * ,int );
treenode * specific();
int group();
treenode * cross();
treenode * exchange();
int findleaf(treenode * );
int freetree(treenode * );
int branchlength(treenode * ,treenode * ,treenode * );
int routelength(treenode * );
double iniaffinity(treenode * );
int outputtree(treenode *);
double findmaxaff();
double affinity(treenode * );
treenode * findleft(treenode * );
int deletenode(treenode * root,treenode * );
int select();
int changroup();
treenode * varytree(treenode * ,treenode * );
treenode * copytree(treenode * );
int calweight(treenode *);
int CALWEIGHT();
int calaff();
int keepspe();
int deltree();
int crossope();
int changeope();
int relspace();
int main()
{
	int i;
	i=0;
	initial();
	readcomvalue();
	group();
	while(i<maxgen)
	{
		CALWEIGHT();//赋权值
        calaff();//计算亲和力
	    keepspe();//保存个体
	    deltree();//删除原来的树，释放空间
        crossope();//交叉操作
        changeope();//变异操作
        select();//选择保存
	    relspace();//释放空间
	    i=i+1;
	}
    calweight(treeorder[treenumber-1]);
   	outfile(treeorder[treenumber-1]);
    return 0;
}
int initial()//初始化数组
{
	int i;
	for(i=0;i<nodenum;i++)
		leafnum[i]=-1;
	for(i=0;i<nodenum;i++)
	{
		nodeorder[i]=i;
	}
    for(i=0;i<((nodenum*(nodenum-1))/2);i++)
	{
		nodedis[i].nodenum1=0;
		nodedis[i].nodenum2=0;
		nodedis[i].nodedis=0;
	}
	for(i=0;i<nodenum;i++)
	{
		samenode[i]=-1;
	}
	return 0;
}
int readcomvalue()//读取距离值
{
	int i;
	int j;
	int n;
	int m;
    FILE * fp;
	n=0;
	m=0;
	if((fp=fopen("juli.txt","r"))==NULL)
	{
		printf("%s\n","cannot open the file");

	}
	for(i=0;i<(nodenum-1);i++)
	{
		for(j=i+1;j<nodenum;j++)
		{
				compointer[n].nodenum01=i;
				compointer[n].nodenum02=j;
				//printf("%s","please input the comvalue between  ");
				//printf("%d",i);
				//printf("%s","  and  ");
				//printf("%d\n",j);
				//scanf("%d",&m);
		        fscanf(fp,"%d",&m);
				compointer[n].comvalue=m;
				n=n+1;
		}
	}
	fclose(fp);
	
	return 0;
}
int rndnode0()//随机函数2
{
    int i;
	int j;
	int n;
	long * p;
	p=(long *)malloc(sizeof(long));
	time(p);
	srand((*p));
	for(n=0;n<100;n++)
	{
		for(i=0;i<99999;i++)
		{
			j=rand();
			srand(j);
		}
	}
	i=(int)(((int)(nodenum/2)*rand()/(RAND_MAX+1.0)));
	return i;
}
int rndnode1()//随机函数0
{
    int i;
	int j;
	int n;
	long * p;
	p=(long *)malloc(sizeof(long));
	time(p);
	srand((*p));
	for(n=0;n<100;n++)
	{
		for(i=0;i<99999;i++)
		{
			j=rand();
			srand(j);
		}
	}
	i=(int)((nodenum*rand())/(RAND_MAX+1.0));
	return i;
}
int rndtree()//随机函数1
{
    int i;
	int j;
	int n;
	long * p;
	p=(long *)malloc(sizeof(long));
	time(p);
	srand((*p));
	for(n=0;n<100;n++)
	{
		for(i=0;i<99999;i++)
		{
			j=rand();
			srand(j);
		}
	}
	i=(int)((treenumber*rand()/(RAND_MAX+1.0)));
	return i;
}
treenode * createtree(int i)
{
	treenode * root;
	if(i>=nodenum)
		return NULL;
	root=(treenode *)malloc(sizeof(treenode));
	root->element=nodeorder[i];
	root->lchild=createtree(2*i+1);
	root->rchild=createtree(2*i+2);
	return root;
}
treenode * findfather(treenode  * root, treenode * p)//返回以root为根的节点p的父亲节点
{  
	treenode * s;
	treenode * r;
	s=root;
	if(s==NULL || s==p)
		return NULL;
	if(s->lchild==p || s->rchild==p)
		return s;
	if((r=findfather(s->lchild,p))!=NULL)
		return r;
	else 
		return(r=findfather(s->rchild,p));
}
treenode * findnode(treenode * rooti,int i)//寻找以rooti为根并且节点值为i的节点
{
	treenode * p;
	p=(treenode *)malloc(sizeof(treenode));
	p=rooti;
	if(p!=NULL)
	{
	if(p->element==i)
	{
		return p;
	}
	else 
		if((findnode(p->lchild,i))!=NULL)
		{
			return (findnode(p->lchild,i));
		}
		else
		{
			return (findnode(p->rchild,i));
		}
	}
	return NULL;
}
treenode * specific0()//产生个体
{
	int i;
	int j;
	treenode * root;
	treenode * p;
	root=createtree(0);
	i=rndnode1();
	p=findnode(root,i);
	j=p->element;
	p->element=root->element;
	root->element=j;
	return root;
}
treenode * specific1()
{
	int i;
	int j;
	int a;
	treenode * root;
	treenode * p;
	treenode * q;
	root=createtree(0);
	i=rndnode0();
	j=rndnode1();
	if(i==j)
	{
		i=rndnode0();
		j=rndnode1();
	}
	p=findnode(root,i);
	q=findnode(root,j);
	a=p->element;
	p->element=q->element;
	q->element=a;
	return root;

}
int group()//产生初始群体
{
	int i;
	for(i=0;i<(int)(treenumber/2);i++)
	{
		treeorder[i]=specific1();
	}
	for(i=(int)(treenumber/2);i<treenumber;i++)
	{
		treeorder[i]=specific0();
	}
	return 0;
}
int branchlength(treenode * root,treenode * p,treenode * q)//计算以root为根的叶子节点p和q的路径长度
{
	int branchnum;
	int i;
	int j;
	int a;
	int b;
	int n;
	treenode * s;
	treenode * r;
	s=findfather(root,p);//s是p的父亲
	r=findfather(root,q);
	i=0;
	j=0;
	a=0;
	b=0;
	n=0;
	branchnum=0;
	if(root==NULL)
	{
		printf("%s","the tree is null");
		printf("\n");
		return 0;
	}
	if(p==NULL || q==NULL)
	{
		printf("%s","p or q is null");
		printf("\n");
		return 0;
	}
	if(p==q)
	{
		return 0;
	}
	while(p!=root)//i是p的深度
	{
		i=i+1;
		p=findfather(root,p);
	}
	while(q!=root)
	{
		j=j+1;
		q=findfather(root,q);
	}
	if(i==j)
	{
		if(s==r)
		{
			a=a+1;
			b=b+1;
			branchnum=a+b;
			return branchnum;
		}
		else
		{
			a=a+1;
			b=b+1;
			while(s!=r)
			{
				a=a+1;
				b=b+1;
				s=findfather(root,s);
				r=findfather(root,r);
			}
			branchnum=a+b;
			return branchnum;
		}
	}
	else
	{
			if(i>j)
			{
				a=a+1;
				b=b+1;
				for(n=0;n<(i-j);n++)
				{
					a=a+1;
					s=findfather(root,s);
				}
                while(s!=r)
				{
					a=a+1;
					b=b+1;
					s=findfather(root,s);
					r=findfather(root,r);
				}
				branchnum=a+b;
				return branchnum;
			}
			else
				if(i<j)
				{
					a=a+1;
					b=b+1;
					for(n=0;n<(j-i);n++)
					{
						b=b+1;
						r=findfather(root,r);
					}
					while(s!=r)
					{
						a=a+1;
						b=b+1;
						s=findfather(root,s);
						r=findfather(root,r);
					}
					branchnum=a+b;
					return branchnum;
				}
	}
	return 0;
}
int findleaf(treenode * root)//寻找以root为根的叶子节点
{
	if(root->lchild==NULL && root->rchild==NULL)
		leafnum[root->element]=root->element;
	if(root->lchild!=NULL && root->rchild!=NULL)
	{
		findleaf(root->lchild);
		findleaf(root->rchild);
	}
	if(root->lchild!=NULL && root->rchild==NULL)		
		findleaf(root->lchild);
	else if(root->rchild!=NULL && root->lchild==NULL)
		findleaf(root->rchild);
	return 0;
}
int routelength(treenode * root)//计算以root为根的树的叶子节点的路径长度
{
    int i;
	int j;
	int n;
	i=0;
	j=0;
	n=0;
	treenode * s;
	treenode * r;
	findleaf(root);
	for(i=0;i<(nodenum-1);i++)
	{
		if(leafnum[i]==-1)
			continue;
		for(j=i+1;j<nodenum;j++)
		{
			if(leafnum[j]==-1)
				continue;
			s=findnode(root,i);
			r=findnode(root,j);
			nodedis[n].nodenum1=i;
			nodedis[n].nodenum2=j;
			nodedis[n].nodedis=branchlength(root,s,r);
			n=n+1;
		}
	}
	return 0;
}

double iniaffinity(treenode * root)//计算以root为根的树的原始适应度
{
	double f;
	double der[(nodenum*(nodenum-1))/2];
	double mul[(nodenum*(nodenum-1))/2];
	int i;
	int j;
	int n;
	n=0;
	for(i=0;i<((nodenum*(nodenum-1))/2);i++)
	{
		der[i]=0.0;
		mul[i]=0.0;
	}
	f=0.0;
	routelength(root);
	for(i=0;i<((nodenum*(nodenum-1))/2);i++)
	{
		for(j=0;j<((nodenum*(nodenum-1))/2);j++)
		{
		if(compointer[i].nodenum01==nodedis[j].nodenum1 && compointer[i].nodenum02==nodedis[j].nodenum2)
		{
			der[n]=compointer[i].comvalue-nodedis[j].nodedis;
			mul[n]=compointer[i].comvalue*compointer[i].comvalue;
			n=n+1;
		}
		}
	}
	for(i=0;i<n;i++)
	{
		f=f+(der[i]*der[i])/mul[i];
	}
	for(i=0;i<nodenum;i++)
	{
		leafnum[i]=-1;
	}
	return f;

}
double findmaxaff()//寻找最大原始适应度，如果适应度小于0，则变为0
{
	int i;
	int j;
	double maxaff;
	double m;
	double peraff[treenumber];
	for(i=0;i<treenumber;i++)
	{