ga.cpp

利用遗传算法搜索函数最优解的c++源程序

#include <math.h>
#include <iostream.h>
#include <iomanip.h>


/////////////////////////////////////////////////
//静态变量定义(产生随机数专用)
static int inextp,iff,inext;
static double ma[57];

//////////////////////////////////////////////////
struct individual             //定义个体
{
	unsigned   chrom[5];      //个体拥有的染色体
	double     fitness;       //个体适应度
	double     varible;   //个体对应的变量值
	int        xsite;     //交叉位置
    int        parent[1];     //父个体
	int        *utinity;      //特定数据指针变量
};

struct  bestever
{
	unsigned    chrom[5];     //最佳个体染色体
	double      fitness;      //最佳个体适应度
	double      varible;  //最佳个体对应的变量值
	int         generation;   //最佳个体生成代
};

/////////////////////////////////////////////////////////
struct  individual  oldpop[20];    //当前代种群
struct  individual  newpop[20];    //新一代种群

struct  bestever    bestfit;   //最佳个体
double  sumfitness;            //种群中个体适应度累计
double  max;                   //种群中个体最大适应值
double  avg;                   //种群中个体平均适应值
double  min;                   //种群中个体最小适应值 
float   pcross;                //交叉率    
float   pmutation;             //变异率       
int     popsize;               //种群大小     
int     lchrom;                //染色体长度    
int     chromsize;             //存储一染色体所需字节数       
int     gen;                   //当前世代 
int     maxgen;                //最大世代数    
int     run;                   //当前运行次数 
int     maxruns;               //总运行次数
int     ncross;                //总交叉次数
int     nmutation;             //总变异次数
int     idum=-1;               //随机数系数
//////////////////////////////////////////////////////////////////
//函数定义
void     initpop();                         
double   ran3(int& idum);                
void     objfunc(struct individual *);          
int      select();                           
int      rnd(int low,int high); 
int      crossover(unsigned *parent1,unsigned *parent2,unsigned *child1,unsigned *child2);
void     mutation(unsigned *child);      //变异操作   
void     generation();                   //生成下一代 
void     sumfit();                       //种群适应度求和
void     statistics(struct individual *pop);   
/////////////////////////////////////////////////////////////////// 
void initialize()        //遗传算法初始化 
{
	//输入种群个体总数
    //cout<<"输入种群个体总数popsize(20～100)"<<"\n";
	//cin>>popsize;
    popsize=20;
	if(popsize%2!=0)
	{
		popsize++;
		cout<<"popsize已设为偶数";
	}

	//输入染色体长度
	//cout<<"输入染色体长度lchrom(8～40)";
	//cin>>lchrom;
    lchrom=78;
	//确定染色体的字节长度 
    chromsize = (lchrom/(8*sizeof(unsigned)));
    if(lchrom%(8*sizeof(unsigned))) 
	{
		chromsize++;
	}

	//输入最大世代数
	//cout<<"输入最大世代数maxgen(100～300)";
	//cin>>maxgen;
    maxgen=300;

	//输入交叉率和变异率
	//cout<<"输入交叉率pcross(0.2～0.9)";
	//cin>>pcross;
    pcross=0.8;

	//cout<<"输入变异率pmutation(0.01～0.1)";
	//cin>>pmutation;
    pmutation=0.05;

	//初始化全局计数变量和一些数值
    nmutation = 0;
    ncross = 0;
    bestfit.fitness = 0.0;
    bestfit.generation = 0;

	//初始化种群，并统计计算结果
    initpop();
}

void  initpop()          //随机化初始种群
{
	int        i,j,k=0,stop=0;
	unsigned int mask=1; 
	for(i=0;i<popsize;i++)         //个体染色体初始化
	{
		for(j=0;j<chromsize;j++)
		{
			oldpop[i].chrom[j]=0;
			if(j==(chromsize-1))
			{
				stop=lchrom-(j*(8*sizeof(unsigned)));
			}
			else
			{
				stop=8*sizeof(unsigned);
			}
			for(k=1;k<=stop;k++)
			{
				oldpop[i].chrom[j]=oldpop[i].chrom[j]<<1;
				if(ran3(idum)<=0.5)
				{
					oldpop[i].chrom[j]=oldpop[i].chrom[j]|mask;
				}
			}
		}
		oldpop[i].parent[0]=0;        //初始化父个体信息
		oldpop[i].parent[1]=0;
		oldpop[i].xsite=0;
		objfunc(&(oldpop[i]));        //计算个体适应度
	}
} 


/////////////////////////////////////////////////////////////
//计算适应度                       
void objfunc(struct individual *critter)            // 计算适应度函数值
{ 
	unsigned mask=1;
	unsigned bitpos;
	unsigned tp;
	double   pow(),bitpow;
	int j,k,stop;
	critter->varible=0.0;
	for(k=0;k<chromsize;k++)
	{
		if(k==(chromsize-1))
		{
			stop=lchrom-(k*(8*sizeof(unsigned)));
		}
		else
		{
			stop=k*(8*sizeof(unsigned));
		}
		tp=critter->chrom[k];
		for(j=0;j<stop;j++)
		{
			bitpos=j+(8*sizeof(unsigned))*k;
			if((tp&mask)==1)
			{
				bitpow=powl(2.0,(double)bitpos);
				critter->varible=critter->varible+bitpow;
			}
			tp=tp>>1;
		}
	}
	critter->varible=-1+3*critter->varible/(powl(2.0,(double)lchrom)-1);
	critter->fitness=critter->varible*sin(critter->varible*10*atan(1)*4)+2.0;
}


int select()              //新个体选择程序
{
	double sum,pick;
	int i;
	pick=ran3(idum);
	sum=0;
	if(sumfitness!=0)
	{
		for(i=0;(sum<pick)&&(i<popsize);i++)
		{
			sum+=oldpop[i].fitness/sumfitness;
		}
	}
	else
	{
		i=int(ran3(idum)*double(popsize));
	}
	return(i-1);
}


//由两个父个体产生两个子个体
int crossover(unsigned *parent1,unsigned *parent2,unsigned *child1,unsigned *child2)
{
	int j,k;
	unsigned jcross;
	unsigned mask,temp;
	if(ran3(idum)<=pcross)         //产生随机数小于交叉率时执行交叉操作
	{
		jcross=rnd(1,lchrom-1); //交叉位置在1～l-1之间
		ncross++;
		for(k=1;k<=chromsize;k++)
		{
			if(jcross>=(k*(8*sizeof(unsigned))))
			{
				child1[k-1]=parent1[k-1];
				child2[k-1]=parent2[k-1];
			}
			else
			{
				if((jcross<(k*8*sizeof(unsigned)))&&(jcross>((k-1)*8*sizeof(unsigned))))
				{
					mask=1;
					for(j=1;j<=(int)(jcross-1-(k-1)*(8*sizeof(unsigned)));j++)
					{
						temp=1;
						mask=mask<<1;
						mask=mask|temp;
					}
					child1[k-1]=((parent1[k-1])&mask)|((parent2[k-1])&(~mask));
					child2[k-1]=((parent1[k-1])&(~mask))|((parent2[k-1])&mask);
				}
				else
				{
				    child1[k-1]=parent2[k-1];
				    child2[k-1]=parent1[k-1];
				}
			}
		}
	}
	else
	{
		for(k=0;k<chromsize;k++)
		{
		    child1[k]=parent1[k];
		    child2[k]=parent2[k];
		}
		jcross=0;
	}
	return(jcross);
}

void mutation(unsigned * child)    //变异操作
{
	int j,k,stop;
	unsigned mask,temp=1;
	for(k=0;k<chromsize;k++)
	{
		mask=0;
		if(k==chromsize-1)
		{
			stop=lchrom-(k*(8*sizeof(unsigned)));
		}
		else
		{
			stop=8*sizeof(unsigned);
		}
		for(j=0;j<stop;j++)
		{
			if(ran3(idum)<=pmutation)
			{
				mask=mask|(temp<<j);
				nmutation++;
				child[k]=(child[k])^(mask);
			} 
		}		
	}
}

void generation()
{
	int mate1,mate2,jcross,j=0;
	sumfit();
	do
	{
		mate1=select();
		mate2=select();
		jcross=crossover(oldpop[mate1].chrom,oldpop[mate2].chrom,newpop[j].chrom,newpop[j+1].chrom);
		mutation(newpop[j].chrom);
		mutation(newpop[j+1].chrom);
		objfunc(&(newpop[j]));
		newpop[j].parent[0]=mate1+1;
		newpop[j].xsite=jcross;
		newpop[j].parent[1]=mate2+1;
		objfunc(&(newpop[j+1]));
		newpop[j+1].parent[0]=mate1+1;
		newpop[j+1].xsite=jcross;
		newpop[j+1].parent[1]=mate2+1;
		j=j+2;
	}while(j<(popsize-1));
}


void sumfit()
{
	int j=0;
	sumfitness=0;
	for(j=0;j<popsize;j++)
	{
		sumfitness=sumfitness+oldpop[j].fitness;
	}
}

void main()  //主程序
{	
	struct individual temp[20];
	//cout<<"输入遗传算法执行次数(1～5)"<<endl;
	//cin>>maxruns;
    maxruns=10;
	max=0;
	for(run=1;run<=maxruns;run++)
	{
		initialize();
		for(gen=0;gen<maxgen;gen++)
		{
			generation();
			for(int i=0;i<20;i++)
			{
				temp[i]=oldpop[i];
			    oldpop[i]=newpop[i];
			    newpop[i]=temp[i];
			    if(max<oldpop[i].fitness)
				{
                    max=oldpop[i].fitness;					
				}
			}
		}
	}
	for(int i=0;i<20;i++)
	{							
	     cout<<oldpop[i].fitness<<"\n";
	}
	cout<<"max="<<max<<"\n";
}


/////随机数生成器////////////////////////

double ran3(int& idum)
{
	double mk,b,fac,mj;
	int i,ii,k,mbig,mz;
	long mseed;
	mbig =1000000000;
	mseed=161803398;
	mz=0;
	fac=0.000000001;
	if((idum<0)||(iff==0))
	{
		iff=1;
		mj=mseed-fabs(idum);
		mj=mj-mbig*int(mj/mbig);
		ma[56]=mj;
		mk=1;
		for(i=1;i<=54;i++)
		{
			ii=(21*i)-55*int((21.0*i)/55.0);
			ma[ii]=mk;
			mk=mj-mk;
			if(mk<mz)
			{
				mk=mk+mbig;
				mj=ma[ii];
			}
		}
		for(k=1;k<=4;k++)
		{
			for(i=1;i<=55;i++)
			{
				ma[i]=ma[i]-ma[1+i+30-55*int((i+30)/55)];
				if(ma[i]<mz)
				{
					ma[i]=ma[i]+mbig;
				}
			}
		}
		inext=0;
		inextp=31;
		idum=1;
	}
	inext=inext+1;
	if(inext==56)
	{
		inext=1;	
	}
	inextp=inextp+1;
	if(inextp==56)
	{
		inextp=1;
	}
	mj=ma[inext]-ma[inextp];
	if(mj<mz)
	{
		mj=mj+mbig;
	}
	ma[inext]=mj;
	b=mj*fac;
	return b;
}

int rnd(int low,int high)
{
	int i;
	double temp;
	temp=ran3(idum);
	i=(int)temp*(high-low+1);
    if(i<low)
	{
		i=low;
	}
	if(i>high)
	{
		i=high;
	}
	return i;
}