简单遗传算法

#include<stdio.h>
#include<stdlib.h> 
#include<math.h>
#include<time.h> 

#define M 50				//种群数量
#define LEN 20				//编码长度
#define xmin -1				//下限
#define xmax 2				//上限
#define MMAX (int)pow(2,LEN)//编码长度相应的最大二进制数
#define PI 3.1415926
#define PC 0.8				//交叉概率
#define PM 0.005			//变异概率

struct Node
{
	int num,MyBinary[LEN];	//num是相应二进制编码的整数值。MyBinary存放二进制编码
	double Myfitness;		//Myfitness是适应度
	double Myfitsum;		//Myfitsum是适应度占整体适应度的百分比，然后从第一个个体往后累加，主要用于选择操作
}Nownode[M],Nextnode[M];	//本代群体和下一代群体

int nodeindex[M];			//交叉时随机配对，存放配对的群体下标

double fx(double x)			//被优化函数
{
	double y;
	y=x*sin(3*PI*x)+2;
	//y=6-pow(x+6,2);
	//y=sin(0.7*x)/x;
	return y;
}

int randn(int temp)//产生0~MMAX之间的随机整数
{
	return (int)(1.0*rand()/RAND_MAX*temp+0.5);
}

double double2double(struct Node node)//把相应的二进制数转化为相应区间的double数
{
	return xmin+node.num*(xmax-xmin)/(pow(2,LEN)-1);
}

int calfitness()	//计算适应度
{
	int i;
	double temp,minfitness;//minfitness作用是假设出现负的适应度，就做相应的变化
	for(i=0;i<M;i++)
	{
		temp=double2double(Nownode[i]);
		Nownode[i].Myfitness=fx(temp);
		if(i==0)
		{
			minfitness=Nownode[i].Myfitness;//i=0时。先给minfitness赋初值
		}
		if(minfitness>Nownode[i].Myfitness)
		{
			minfitness=Nownode[i].Myfitness;
		}
	}
	if(minfitness<0)//假设有负的适应度值，就把所以的适应度都加上一个数，使适应度全都为正数
	{
		for(i=0;i<M;i++)
		{
			Nownode[i].Myfitness+=-minfitness;
		}
	}
	Nownode[0].Myfitsum=Nownode[0].Myfitness;
	for(i=1;i<M;i++)
	{
		Nownode[i].Myfitsum=Nownode[i].Myfitness+Nownode[i-1].Myfitsum;//每个Myfitsum都是自己的适应度加上前一个的Myfitsum
	}
	for(i=0;i<M;i++)
	{
		Nownode[i].Myfitsum=Nownode[i].Myfitsum/Nownode[M-1].Myfitsum;//每个Myfitsum除以全部适应度之和，使Myfitsum为0~1之间
	}
	return 0;
}

int initpopulation()//初始化种群
{
	int i,j,temp;
	for(i=0;i<M;i++)
	{
		temp=randn(MMAX);	//产生0~MMAX之间的随机整数值
		Nownode[i].num=temp;
		//printf("%d
",temp);
		for(j=LEN-1;j>=0;j--)
		{
			Nownode[i].MyBinary[j]=temp%2;//给MyBinary赋值
			temp=temp/2;
		}
	}
	calfitness();//计算适应度
	return 0;
}

int assignment(struct Node *node1,struct Node *node2)//两个个体之间赋值操作，所以这里必须使用指针，
{
	int j;
	for(j=0;j<LEN;j++)
	{
		node1->MyBinary[j]=node2->MyBinary[j];
	}
	node1->num=node2->num;
	return 0;
}

int copypopulation()//选择(复制)操作
{
	int i,num=0;
	double temp;
	while(num<M)
	{
		temp=1.0*rand()/RAND_MAX;//随机生成一个0~1之间的数
		for(i=1;i<M;i++)
		{
			if(temp>=Nownode[i-1].Myfitsum&&temp<=Nownode[i].Myfitsum)
			{
				//Nextnode[num++]=Nownode[i];
				assignment(&Nextnode[num++],&Nownode[i]);//假设满足条件就赋值给下一代
				break;
			}
		}
	}
	for(i=0;i<M;i++)
	{
		//Nownode[i]=Nextnode[i];
		assignment(&Nownode[i],&Nextnode[i]);//更新本代个体
	}
	calfitness();//计算适应度
	return 0;
}

int isrepeat(int temp,int num)//交叉时要随机分组，防止出现反复的两个数。此函数检測是否下标反复
{
	int i;
	for(i=0;i<num;i++)
	{
		if(nodeindex[i]==temp)
			return 1;
	}
	return 0;
}

int bin2int(struct Node *node)//把相应的编码转化为整数值
{
	int j,num=0;;
	for(j=0;j<LEN;j++)
	{
		num+=(int)(pow(2,LEN-1-j)*(node->MyBinary[j]));
	}
	node->num=num;
	return num;
}

int crossposition(struct Node *node1,struct Node *node2,int p)//交叉操作，交叉点为p,參数必须是指针
{
	int j,temp;
	for(j=LEN-1;j>=LEN-1-p;j--)
	{
		temp=node1->MyBinary[j];
		node1->MyBinary[j]=node2->MyBinary[j];//交换两个个体的编码
		node2->MyBinary[j]=temp;
	}
	bin2int(node1);//交叉完毕后更新num值
	bin2int(node2);
	return 1;
}


int crossover()
{
	int i,temp;
	double pc_temp;
	for(i=0;i<M;i++)
	{
		do
		{
			temp=rand()%M;
		} while(isrepeat(temp,i));
		
		nodeindex[i]=temp;//首先产生了交叉的下标
	}
	for(i=0;i<M;i=i+2)
	{
		temp=rand()%(LEN-1);
		pc_temp=1.0*rand()/RAND_MAX;
		if(pc_temp<=PC)//满足交叉条件就交叉
		{
			crossposition(&Nownode[nodeindex[i]],&Nownode[nodeindex[i+1]],temp);
		}		
	}
	calfitness();//计算适应度
	return 1;
}

int mutation()//变异操作
{
	int i,j;
	double pm_temp;
	for(i=0;i<M;i++)
	{
		for(j=0;j<LEN;j++)
		{
			pm_temp=1.0*rand()/RAND_MAX;
			if(pm_temp<=PM)//满足变异概率就进行变异操作
			{
				Nownode[i].MyBinary[j]=(Nownode[i].MyBinary[j]==0)?1:0;
			}
		}
		bin2int(&Nownode[i]);//更新个体的num值
	}
	calfitness();//计算适应度
	return 1;
}


int findmaxfit()//找到适应度最大的个体
{
	int i,index=0;
	double temp=0;
	for(i=0;i<M;i++)
	{
		if(temp<Nownode[i].Myfitness)
		{
			index=i;
			temp=Nownode[i].Myfitness;
		}
	}
	return index;
}

int displaynode()
{
	int i,j;
	printf("

下标	num值	x值	        编码		Myfitness	Myfitsum
");
	for(i=0;i<M;i++)
	{
		printf("第%d个	%d	%.3lf	",i,Nownode[i].num,double2double(Nownode[i]));
		for(j=0;j<LEN;j++)
		{
			printf("%d",Nownode[i].MyBinary[j]);
		}
		printf("	%.3lf		%.3lf
",Nownode[i].Myfitness,Nownode[i].Myfitsum);
	}
	return 1;
}

int main()
{
	int T=0,index,j;
	srand(time(NULL));
	initpopulation();//初始化群体
	printf("初始群体:
");
	displaynode();
	while(T++<=50)
	{
		//printf("第%d代:
",T);
		copypopulation();
		//printf("复制之后:
");	
		//displaynode();
		crossover();
		//printf("交叉之后:
");	
		//displaynode();
		mutation();	
		//printf("变异之后:
");	
		//displaynode();
	}	
	printf("最后一代群体:
");
	displaynode();
	index=findmaxfit();
	printf("

下标	num值	x值	        编码		最大适应度值	函数最大值
");
	printf("第%d个	%d	%.3lf	",index,Nownode[index].num,double2double(Nownode[index]));
	for(j=0;j<LEN;j++)
	{
		printf("%d",Nownode[index].MyBinary[j]);
	}
	printf("	%.3f		%.3f

",Nownode[index].Myfitness,fx(double2double(Nownode[index])));
	return 0;
}