1.cpp

基本遗传算法

#define MAX 10000.0

#include <iostream.h>
#include <malloc.h>
#include <stdlib.h>
#include <math.h>

//定义一个个体的结构体变量
struct individual
{
	char chrom[16];     // 染色体,用字符串来表示
	double fitness;     // 个体适应度
	double varible1;    // 个体对应的变量1值
	double varible2;    // 个体对应的变量2值
	int xsite1;         // 交叉位置1
	int xsite2;         // 交叉位置2
};

//定义一个最佳个体的结构体变量
struct bestever
{
	char chrom[16];     // 最佳个体染色体,用字符串来表示
	double fitness;     // 最佳个体适应度
	double varible1;    // 最佳个体对应的变量值
	double varible2;    // 个体对应的变量2值
	int generation;     // 最佳个体生成代
};

//定义一个表示一个染色体中交叉位置的结构体变量
struct CrossPos
{
	int xsite1;
	int xsite2;
};

/*定义一些在程序中需要用到的全局变量*/

individual * oldpop;    // 当前代种群
individual * newpop;    // 新一代种群
bestever bestfit;       // 最佳个体
double sumfitness;      // 种群中个体适应度累加值
double max;             // 种群中个体最大适应度
double avg;             // 种群中个体平均适应度
double min;             // 种群中个体最小适应度
float pcross;           // 交叉概率
float pmutation;        // 变异概率
int popsize;            // 种群大小
int lchrom=16;          // 染色体长度固定，为16个字节
int chromsize=2;        // 存储一个染色体所需要的字节数
int gen=0;              // 当前世代数,刚开始应该是0，代表初始种群
int maxgen;             // 最大世代数
int run;                // 当前运行次数
int maxruns;            // 总运行次数
int nmutation;          // 当前代变异发生次数
int ncross;             // 当前代交叉发生次数

///////////////////////////////////////

/*随机数发生器使用的变量*/
double oldrand[55];
int jrand;

void initdata()
{  // 键盘输入遗传算法参数
   cout<<"请输入种群大小(20-100)："<<endl;
   cin>>popsize;

   if((popsize%2)!=0)
   {  // 将种群大小设置为偶数
	  popsize++;
   }

   cout<<"请输入最大世代数(100-300):"<<endl;
   cin>>maxgen;

   cout<<"请输入交叉率(0.2-0.9):"<<endl;
   cin>>pcross;

   cout<<"请输入变异率(0.01-0.1):"<<endl;
   cin>>pmutation;
}

void initmalloc()
{  // 分配给全局数据结构空间 

   // 分配给当前代和新一代种群内存空间
   oldpop=(struct individual *)malloc(popsize*sizeof(struct individual));
   newpop=(struct individual *)malloc(popsize*sizeof(struct individual));
}

void objfunc(individual * unit)
{   // 计算初始适应度值
    
	// 初始化两个自变量的值
	unit->varible1=0.0;
	unit->varible2=0.0;

	// 一个中间变量值，用来求出自变量的值
    double temp=0.0;

	// 循环变量
	int i,j;

	// 首先，要把两个自变量从染色体字符串分离出来

	// 计算自变量1
    for(i=0,j=7;i<8;i++,j--)
	{
		char cbit=unit->chrom[i];
		if(cbit=='1')
		{
			temp+=pow(2.0,j);
		}
	}

	unit->varible1=-2.048+temp*4.096/(pow(2.0,8)-1);

    // 将temp清0
    temp=0.0;

	// 计算自变量2
	for(i=8,j=7;i<16;i++,j--)
	{
		char cbit=unit->chrom[i];
		if(cbit=='1')
		{
			temp+=pow(2.0,j);
		}
	}

	unit->varible2=-2.048+temp*4.096/(pow(2.0,8)-1);

	// 计算染色体的自适应值

	double x1=unit->varible1;
	double x2=unit->varible2;

	unit->fitness=100*(x1*x1-x2)*(x1*x1-x2)+(1-x1)*(1-x1);
}

void advance_random()
{  // 产生55个随机数
   int j1;
   double new_random;
   for(j1=0;j1<24;j1++)
   {
	   new_random=oldrand[j1]-oldrand[j1+31];
	   if(new_random<0.0) new_random=new_random+1.0;
	   oldrand[j1]=new_random;
   }

   for(j1=24;j1<55;j1++)
   {
	   new_random=oldrand[j1]-oldrand[j1-24];
	   if(new_random<0.0) new_random=new_random+1.0;
	   oldrand[j1]=new_random;
   }
}

float randomperc()
{  // 产生[0,1]之间的一个随机数
   jrand++;
   if(jrand>=55)
   {
	   jrand=1;
	   advance_random();
   }
   return (float)oldrand[jrand];
}

void initpop()
{  // 初始化种群

   // 循环变量
   int i,j;

   // 将每个个体的染色体以及个体的交叉位置均初始化为0
   for(i=0;i<popsize;i++)
   {
	   for(j=0;j<16;j++)
	   {
		   oldpop[i].chrom[j]='0';
	   }

	   oldpop[i].xsite1=0;
	   oldpop[i].xsite2=8;
   }

   // 接收随机函数返回值
   double temp=0.0;

   // 利用随机函数完成初始化种群工作
   for(i=0;i<popsize;i++)
   {
	   for(j=0;j<lchrom;j++)
	   {
		   if(randomperc()>=0.5)
		   {
			   oldpop[i].chrom[j]='1';
		   }
	   }

	   objfunc(&(oldpop[i]));  //计算初始适应度值
   }
}

void statistics(individual * oldpop)
{  // 统计计算结果
   
   // 循环变量
   int i,j;

   // 一些初始化工作
   sumfitness=0.0;
   min=oldpop[0].fitness;
   max=oldpop[0].fitness;

   // 计算最大、最小和累计适应度
   for(i=0;i<popsize;i++)
   {
	   sumfitness+=oldpop[i].fitness;
	   if(oldpop[i].fitness>max)   max=oldpop[i].fitness;
	   if(oldpop[i].fitness<min)   min=oldpop[i].fitness;

	   // 计算最佳个体的相应参数，并假定
	   // 取得最小值的个体为最佳个体
	   if(oldpop[i].fitness<bestfit.fitness)
	   {
		   // 传递染色体的字符串变量
		   for(j=0;j<16;j++)
		   {
			   bestfit.chrom[j]=oldpop[i].chrom[j];
		   }

		   bestfit.fitness=oldpop[i].fitness;
		   bestfit.varible1=oldpop[i].varible1;
		   bestfit.varible2=oldpop[i].varible2;
		   bestfit.generation=gen;
	   }
   }

   // 计算平均适应度值
   avg=sumfitness/popsize;
}

void warmup_random(float random_seed)
{   // 初始化随机数发生器
	int j1,ii;
    double new_random,prev_random;

	oldrand[54]=random_seed;
	new_random=0.000000001;
	prev_random=random_seed;
	for(j1=1;j1<=54;j1++)
	{
		ii=(21*j1)%24;
		oldrand[ii]=new_random;
		new_random=prev_random-new_random;
		if(new_random<0.0) new_random=new_random+1.0;
		prev_random=oldrand[ii];
	}
	advance_random();
	advance_random();
	advance_random();
	jrand=0;
}

void randomize()
{   //设定随机数种子并初始化随机数发生器
	float randomseed;
	int j1;
	for(j1=0;j1<55;j1++)
		oldrand[j1]=0.0;
	jrand=0;
	cout<<"请输入一个随机数种子(0,1):"<<endl;
	cin>>randomseed;
	warmup_random(randomseed);
}

void initialize()
{  // 遗传算法初始化
   initdata();  // 键盘输入遗传算法参数

   initmalloc(); // 分配给全局数据结构空间 

   randomize();  // 初始化随机数发生器

   // 初始化全局计数变量和一些数值
   nmutation=0;   // 初始化当前代变异发生次数为0
   ncross=0;      // 初始化当前代交叉发生次数为0
   bestfit.fitness=MAX;  //初始化最佳个体适应值
   bestfit.generation=0; //初始化最佳个体生成代

   // 初始化种群
   initpop();

   // 统计计算结果
   statistics(oldpop);

}

int rnd(int low,int high)
{  // 在整数low和high之间产生一个随机整数
   int i;
   if(low>=high)
	   i=low;
   else
   {
	   i=int((randomperc()*(high-low+1))+low);
	   if(i>high)  i=high;
   }
   return i;
}

int select()
{  // 赌轮选择
   return int(randomperc()*(popsize-1));
}

CrossPos crossover(char * parent1,char * parent2,
			  char * child1,char * child2)
{   // 由两个父个体交叉产生两个子个体

	// 循环变量
	int i;

	// 标识进行交叉的位置
	CrossPos jcross;

	// 用赌轮法判断是否进行进行交叉
	if(randomperc()<=pcross)
	{   // 若进行交叉运算

		// 随机产生个体中的两个交叉位置
		jcross.xsite1=rnd(1,7);
		jcross.xsite2=rnd(9,15);
        
		// 更新交叉次数
		ncross++;

		// 按照交叉位置进行交叉运算并产生子代

		// 更新子代1和2的染色体
		for(i=0;i<16;i++)
		{
			if(i<jcross.xsite1)
			{
				child1[i]=parent1[i];
				child2[i]=parent2[i];
			}
			else if(i>=jcross.xsite1 && i<=7)
			{
				child1[i]=parent2[i];
				child2[i]=parent1[i];
			}
			else if(i>7 && i<jcross.xsite2)
			{
				child1[i]=parent1[i];
				child2[i]=parent2[i];
			}
			else 
			{
				child1[i]=parent2[i];
				child2[i]=parent1[i];
			}
		}
	}
	else
	{   // 如果没有进行交叉运算
		for(i=0;i<16;i++)
		{   // 保持原样
			child1[i]=parent1[i];
			child2[i]=parent2[i];
		}
		// 此时交叉位置固定
		jcross.xsite1=0;
		jcross.xsite2=8;
	}
	return jcross;
}

void mutation(char * child)
{  // 变异操作

   // 循环变量
   int i;

   bool flag=false;

   for(i=0;i<16;i++)
   {   // 判断染色体中每一位是否发生变异

	   if(randomperc()<=pmutation)
	   {   // 若发生变异
		   if(child[i]='0')   child[i]='1';
		   else    child[i]='0';
		   flag=true;
	   }
   }
   if(true==flag)  nmutation++;
}

void preselect()
{  // 每代运算前进行预选
   int i;
   sumfitness=0.0;
   for(i=0;i<popsize;i++)
	   sumfitness+=oldpop[i].fitness;
}

void generation()
{  // 产生新的一代
   
   // 标识要进行交叉运算的两个个体的序号
   int mate1,mate2;

   // 每代运算前进行预选
   preselect();

   // 标识要进行交叉运算的位置
   CrossPos jcross;

   // 循环变量
   int i=0;

   do
   {
	   // 挑选交叉配对
	   mate1=select();
	   mate2=select();
       // 交叉和变异
	   jcross=crossover(oldpop[mate1].chrom,oldpop[mate2].chrom,
		   newpop[i].chrom,newpop[i+1].chrom);

	   mutation(newpop[i].chrom);
	   mutation(newpop[i+1].chrom);

	   // 解码，计算适应度
       objfunc(&(newpop[i]));

	   objfunc(&(newpop[i+1]));

	   // 记录交叉位置
	   newpop[i].xsite1=jcross.xsite1;
	   newpop[i].xsite2=jcross.xsite2;

       newpop[i+1].xsite1=jcross.xsite1;
	   newpop[i+1].xsite2=jcross.xsite2;

	   i=i+2;
   }
   while(i<(popsize-1));
}

void report()
{   // 输出新一代统计数据
	cout<<"第"<<gen<<"代统计："<<endl;
	cout<<"总交叉次数＝"<<ncross<<",";
	cout<<"总变异次数＝"<<nmutation<<endl;
	cout<<"最小适应度:"<<min<<"最大适应度："<<max<<"平均适应度:"<<avg<<endl;
	cout<<"迄今发现最佳个体＝>所在代数:"<<bestfit.generation;
	cout<<"最佳个体的适应度:"<<bestfit.fitness;
	cout<<"最佳个体对应的变量值："<<bestfit.varible1<<"  "<<bestfit.varible2;
	cout<<endl;
}

void freeall()
{   // 释放动态申请的内存空间
    free(oldpop);
	free(newpop);
}

void main()
{   // 主函数
	cout<<"/***************欢迎进入基本遗传算法系统：***************/"<<endl;
    cout<<"/*本例子中，测试函数是："<<endl;
	cout<<"F=100(x1*x1-x2)(x1*x1-x2)+(1-x1)(1-x1)"<<endl;
	cout<<"/*自变量范围：-2.048=<x1<=2.048,-2.048=<x2<=2.048"<<endl;
	cout<<"问题是：求函数的最小值问题!"<<endl;
	cout<<"请输入一些参数："<<endl;

    cout<<"请输入遗传算法执行次数(1-10)："<<endl;
    cin>>maxruns;

	// 一个用于交换的变量
    individual * temp;

	for(run=1;run<=maxruns;run++)
	{
		initialize(); // 遗传算法初始化
        for(gen=1;gen<=maxgen;gen++)
		{
			cout<<"第"<<run<<"/"<<maxruns<<"次运行：当前代为";
			cout<<gen<<"共"<<maxgen<<"代"<<endl;

			// 产生新的一代
			generation();

			// 计算新的一代的统计数据
			statistics(newpop);

			// 输出新一代统计数据
			report();

			// 交换
			temp=oldpop;
			oldpop=newpop;
			newpop=temp;
		}
		freeall();
		gen=0;
	}
}