heredity.cpp

遗传算法

//    沈硕  自动化五班  3004203132
#include <iostream.h>
#include <stdlib.h>
#include <time.h> 
#include <stdio.h>
#include <math.h>
#include <iomanip.h>

#define Whole_Num 128	//全体种群的个数
#define Code_Num 7		//码值的位数
#define Select_Num 26	//并行计算时，每次选取的种群数
#define Vary_Num 500 //变异率1/Vary_Num

//**************************************************************************
//计算适配值用的函数g(x)=x^2-5*x
int fun( unsigned int x)
{
	return x*x-5*x+10;	// g(x)+10 保证适配值为正
}
//**************************************************************************
//个体类，包含种群中每个应具有的特性：
//赋值，编码，译码，计算适配值
class Single
{
public:
	unsigned int X_num;		//个体的数值
	unsigned int X_code;	//个体的码值，设为public成员，交叉时便于修改
	unsigned int X_match;	//个体的适配值
//计算适配值的函数
	void Xfun_match()	
	{
		X_num=X_code;	//译码
						//由于本实验种群的特殊性--样本是[0,127],所以设置编码值=数值
		X_match=fun(X_num);	//b=10,保证适配值为正，返回适配值
	}
};
//**************************************************************************
//遗传算法类，包含必要的算法
//复制，交叉（包含变异0.001），优选（通过适配值比较），结果判断
class Holland
{
public:
	Single Select[Select_Num];	//并行计算用的初始种群

	unsigned int Select_help[Select_Num];	//并行计算用的辅助数组,保存码值
	unsigned int sel_init[Select_Num];	//初始化时：保存生成 初始种群码值 的随机数组
	unsigned int copy_time[Select_Num];	//记录对应种群中个体的 复制次数
	float copy_ma[Select_Num];	//保存期望的复制数的百分数（%）

	unsigned int max,jmax,varage;	//保存最大适配值,对应的变量值和平均适配值

	int vary;		//记录总的交叉的位数，适时vary=0变异
	int flag[3];	//变异标志位flag[0]=1,发生变异；
					//保存：运算在第 flag[1] 组的交差时，在第 flag[2] 位发生过元素变异
//构造函数，初始化变异率1/vary------------------------------------------------
	Holland()
	{
		vary=Vary_Num;
		flag[0]=0;
		max=jmax=0;
	}

//产生初始种群-----------------------------------------------------------------
	void Get_select()
	{
		//生成20个随机数存入sel_init[]
		int y;
		srand( (unsigned)time( NULL ) );//srand()函数产生一个以当前时间开始的随机种子 
		for (int i=0;i<Select_Num;i++) 
		{
			//生成Select_Num个[0,Whole_Num-1]之间的随机数
			y=rand();
			sel_init[i]= y%Whole_Num;	
		}
		//初始化种群的编码
		for ( i=0;i<Select_Num;i++) 
			Select[i].X_code=sel_init[i];
	}

//选择--------------------------------------------------------------------------
	//对选取的种群的适配值进行计算，处理，以便优选得到复制次数
	void Get_matched()
	{
		float copy_sum=0;		//保存适配值的和
		Select[0].Xfun_match();
		max=Select[0].X_match;
		jmax=Select[0].X_num;
		for(int i=0;i<Select_Num;i++)
		{
			//计算适配值，及适配值和
			Select[i].Xfun_match();
			copy_sum+=Select[i].X_match;

			//计算最大适配值，和对应的个体数值
			if(Select[i].X_match>max)
			{
				max=Select[i].X_match;
				jmax=Select[i].X_num;
			}
		}
		varage=(unsigned int)copy_sum/Select_Num;//计算平均适配值
		//计算期望的复制数(%)
		for( i=0;i<Select_Num;i++)				
			copy_ma[i]=Select[i].X_match/copy_sum*100;
	}

//复制--------------------------------------------------------------------- 
	//轮盘赌实现
	void Get_copy()
	{
		for(int i=0;i<Select_Num;i++)
			copy_time[i]=0;	//初始化
		srand( (unsigned)time( NULL ) );//srand()函数产生一个以当前时间开始的随机种子 	
		int k;
		for( i=0;i<Select_Num;i++)
		{	
			k=rand();//生成随机数
			k=k%100;//看随机数在轮盘的那个扇区
			float amid=0,bmid=0;
			for(int j=0;j<Select_Num;j++)
			{
				bmid=bmid+copy_ma[j];//扇区左界限
				amid=bmid-copy_ma[j];//扇区右界限

				if(k>amid&&k<=bmid)
				{
					copy_time[j]=copy_time[j]+1;	//对应码值的复制次数
					Select_help[i]=Select[j].X_code;	//复制码值
				}
			}			
		}
	}
//交叉-----------------------------------------------------------------------
	//中间计算函数，实现两位串a，b；在指定位置c处交叉
	void two_cross(unsigned int &a,unsigned int &b,unsigned int c)
	{
		unsigned int xa,xb,xm1,xm2;
		unsigned int yc,ym1,ym2;
		yc=0xffffffff;	//yc中存1111...1
		yc=yc<<c;		//左移后yc中为11...100...0,0的个数为c

		ym1=yc;		//yc中1和0的分界点即为交叉点
		ym2=~yc;

		xa=a;
		xb=b;

		xm1=xa&ym1;	//保存位串a的交叉点之 前 的各位
		xm2=xb&ym2;	//保存位串b的交叉点之 后 的各位
		a=xm1|xm2;

		xm1=xa&ym2;	//保存位串a的交叉点之 后 的各位
		xm2=xb&ym1;	//保存位串b的交叉点之 前 的各位
		b=xm1|xm2;
	}
	//---------------------------------------------------------------------
	//交叉函数
	void Get_cross()
	{
		int y;
		srand( (unsigned)time( NULL ) );//srand()函数产生一个以当前时间开始的随机种子 
		for(int i=0;i<Select_Num;i++)
		{
			y=rand();
			y=y%Select_Num;
			unsigned int a;
			//根据随机数重新排列Select_help[],达到两两随机配对的目的
			a=Select_help[y];
			Select_help[y]=Select_help[i];
			Select_help[i]=a;			
		}
		//-----------------------------------------------------------------
		//随机地选择交叉点，价差产生新位串
		unsigned int cross[Select_Num/2];	//保存生成 交叉位置值 的随机数组			
		int ymid;	//生成交叉位置值 的随机数组
		for ( i=0;i<Select_Num/2;i++) 
		{
			ymid=rand();
			cross[i]=ymid%(Code_Num-1);
		}
		//-----------------------------------------------------------------
		//种群数组的元素首尾配对，实现交叉
		for ( i=0;i<Select_Num/2;i++) 
		{
			//调用交叉函数
			two_cross(Select_help[i],Select_help[Select_Num-i-1],cross[i]);
			vary=vary-Code_Num-Code_Num;
			//-------------------------------------------------------------
			if(vary<=(2*Code_Num))	//变异
			{
				vary=vary%Code_Num;
				flag[0]=1;
				flag[1]=i+1;	//保存变异组
				flag[2]=vary+1;	//保存变异位
				unsigned int a,b;
				a=int(pow(2,vary+1)-pow(2,vary));//将要变异的位为1，其他位为0
				
				b=Select_help[i];	//逐位异或后，变异位取反，实现变异
				Select_help[i]=b^a;
				vary+=Vary_Num;		//恢复变异计数器值
			}
		}
	}

//结果处理：转移编码计算结果-----------------------------------------------
	void Get_result()
	{
		for( int i=0;i<Select_Num;i++)
			Select[i].X_code=Select_help[i];
	}

//输出显示函数-------------------------------------------------------------
	void Get_print()
	{
		cout<<"\n选择新种群的相关计算:\n";
		cout<<"个体的X 值:\t";
		for(int i=0;i<Select_Num;i++)
			cout<<Select[i].X_code<<'\t';

		cout<<"\n个体适配值:\t";
		for( i=0;i<Select_Num;i++)
			cout<<Select[i].X_match<<'\t';

		cout<<"\n期望复制数:\t";
		for( i=0;i<Select_Num;i++)
			cout<<setprecision(4)<<copy_ma[i]<<'	';

		cout<<"\n实际复制数:\t";
		for( i=0;i<Select_Num;i++)
			cout<<copy_time[i]<<'	';

		cout<<"\n当前平均适配值："<<varage;
		cout<<"\n当前最大适配值："<<max;
		cout<<"\t对应的变量值:"<<jmax;
	}
	//----------------------------------------------------------------------
	void Get_print2()
	{
		if(flag[0])
		{
			cout<<"\n本次运算在第 "<<flag[1]<<" 组的交差时";
			cout<<"在第 "<<flag[2]<<" 位发生过元素变异"<<endl;
		
			flag[0]=0;
			cout<<'\t'<<endl;
		}
	}
	
};

//**************************************************************************
//遗传算法计算主函数：
void main()
{
	Holland x;	//生成遗传算法类
	int c=200;	//设定迭代次数

	x.Get_select ();	//产生初始总群
	do{
		x.Get_matched ();	//选择
		x.Get_copy ();		//复制
		x.Get_print();
		x.Get_cross ();		//交叉
		x.Get_print2();		//显示是否变异
		x.Get_result ();	//转移结果
		c--;
		cout<<"\n迭代次数："<<200-c<<endl;
	}while(c);

	cout<<"程序设计者：自动化五班 沈硕 3004203132"<<endl;
}