simplega精英旧.txt

该程序为使用了轮盘赌选择方式、单点交叉和基本位变异算子

///////////
////基本遗传算法--Simple Genetic Algorithm(简称SGA)
////采用轮盘赌选择，单点交叉，基本位变异算子，精英策略
////作者:东方志柱   QQ:119227955或170449907
////邮箱：[e-mail]或[e-mail]
////版权所有，仅供参考！
////时间:2006年12月
///////////
#include <iostream>
#include <iomanip>
#include <math.h>
#include <time.h>
#include <stdlib.h>
///////////
using namespace std;
///////////
///////////
const int var=2;                  ///////变量x[0]到x[var-1]的个数
double a[var],b[var];             /////a[i]与b[i]分别表示x[i]的下界和上界
////partchrom[i]表示x[i]对应的染色体长度(i>0)
////注意：partchrom[]里面的数字总和要等于chromsize
int partchromsize[var+1]={0,10,10};
int length[var];                   ///////辅助变量
const int chromsize=20;            ///////染色体长度
int const popsize=80;              ///////种群大小
double pm;                         ///////变异概率
double pc;                         ///////交叉概率
const int maxruns=300;             ///////总运行次数
double averagefit;                 ///////种群平均适应度
double cfitness[popsize];          ///////个体累加适应度
double online=0.0;                 ///////在线性能值
double offline=0.0;                ///////离线性能值
///////////
///////////
struct individual                  ////个体数据结构
{
	unsigned chrom[chromsize];     /////染色体
	double fitness;                /////个体适应度
	double x[var];                 /////个体对应的变量值
};
struct bestindividual              /////最佳个体数据结构
{
	unsigned chrom[chromsize];     /////最佳个体染色体
	double fitness;                /////最佳个体适应度
	double x[var];                 /////最佳个体对应的变量值
	int generation;                /////最佳个体生成代
};
///////////
///////////
struct individual newpop[popsize];          /////新一代种群
struct bestindividual best;                 /////最佳个体
///////////
///////////
void initpop(individual pop[],int numpop,int numchrom);///////随机初始化种群声明
void decode(unsigned arr[],double x[]);     //////解码函数：将arr[]解码给x[var]
double fitfun(double x[]);                  /////适应度函数声明
////////////
void inputdata();                           /////参数输入声明
void statistics(individual pop[],int run);  /////统计种群数据
void selection(individual pop[]);           /////选择算子
void crossover(individual pop[]);           /////交叉算子
void mutation(individual pop[]);            /////变异算子
void output_head();
void output(int run);                       /////输出最佳个体组
///////////
////转换函数：将二进制串arr[]从arr[point]到arr[length-1]开始简单转换成十进制数
double convert(unsigned arr[],int point,int length);
void outputvar(bestindividual best); ////输出变量值函数
//////////
//////////
///转换函数：将二进制串arr[]从arr[point]到arr[length-1]开始简单转换成十进制数
double convert(unsigned arr[],int point=0,int length=chromsize)
{
	double value=0.0;
	for(int i=point;i<point+length;i++)
		value+=arr[i]*pow(2,(length-1+point)-i);
	return (value);
}
/////////
////输出变量值函数
void outputvar(bestindividual best)
{
	if(var==1)
		cout<<"变量值："<<best.x[0];
	else
	{
		cout<<"变量值："<<"("<<best.x[0];
		for(int i=1;i<var;i++)
			cout<<","<<best.x[i];
		cout<<")";
	}
}
//////////
//////////
/////随机初始化种群
void initpop(individual pop[],int numpop=popsize,int numchrom=chromsize)
{
	int i,j;
	///////初始化length[var]
	for(i=0;i<var;i++)
	{
		length[i]=0;
		for(j=0;j<=i;j++)
			length[i]+=partchromsize[j];
	}
	//////初始化种群
	for(i=0;i<numpop;i++)
	{
		for(j=0;j<numchrom;j++)
			pop[i].chrom[j]=rand()%2;
		decode(pop[i].chrom,pop[i].x);
		pop[i].fitness=fitfun(pop[i].x);
	}
}
//////////
/////统计种群数据
void statistics(individual pop[],int run)
{
	int i,index=0;
	double max=pop[0].fitness;
	/////确定pop的最佳个体及其位置
	for(i=1;i<popsize;i++)
	{
		if(pop[i].fitness>max)
		{
			max=pop[i].fitness;
			index=i;
		}
	}
	/////分情况处理
	if(run==0)                        /////第一代情况(n==0)
	{
		/////确定当前代最佳个体
		for(i=0;i<chromsize;i++)
			best.chrom[i]=pop[index].chrom[i];
		best.fitness=pop[index].fitness;
		for(i=0;i<var;i++)
			best.x[i]=pop[index].x[i];
		best.generation=0;
	}
	else                              /////第二代及以上代情况(n>0)
	{
		if(max>best.fitness)     //////新生代最佳个体比上一代好
		{
			for(i=0;i<chromsize;i++)
				best.chrom[i]=pop[index].chrom[i];
			best.fitness=pop[index].fitness;
			for(i=0;i<var;i++)
				best.x[i]=pop[index].x[i];
			best.generation=run;
		}
		else                       //////新生代最佳个体比上一代差
		{
			//////随机替换一个个体
			index=rand()%(popsize);
			for(i=0;i<chromsize;i++)
				pop[index].chrom[i]=best.chrom[i];
			pop[index].fitness=best.fitness;
			for(i=0;i<var;i++)
				pop[index].x[i]=best.x[i];
		}
	}
	/////当前代平均适应度
	averagefit=0.0;
	for(i=0;i<popsize;i++)
		averagefit+=pop[i].fitness/popsize;
	//////////在线和离线性能值计算
	online+=averagefit;
	offline+=best.fitness;
	//////////
	/////相对适应度
	double sum=averagefit*popsize;
	for(i=0;i<popsize;i++)
		cfitness[i]=pop[i].fitness/sum;
	/////计算累加适应度
	for(i=1;i<popsize;i++)
		cfitness[i]=cfitness[i-1]+cfitness[i];
	//////////
}
//////////
/////选择算子
void selection(individual pop[])
{
	int i,index;
	double p;
	struct individual temppop[popsize];
	for(i=0;i<popsize;i++)               /////选择操作
	{
		p=rand()%1000/1000.0;
		index=0;
		while(p>cfitness[index])index++;
		temppop[i]=pop[index];
	}
	for(i=0;i<popsize;i++)pop[i]=temppop[i];
}
//////////
///////交叉算子
void crossover(individual pop[])
{
	int i,j;
	int index[popsize];
	int point,temp;
	double p;
	/////随机选取一对个体
	for(i=0;i<popsize;i++)index[i]=i;	
	for(i=0;i<popsize;i++)
	{
		point=rand()%(popsize-i);
		temp=index[i];
		index[i]=index[point+i];
		index[point+i]=temp;
	}
	/////单点交叉
	for(i=0;i<popsize-1;i+=2)
	{
		p=rand()%1000/1000.0;
		if(p<pc)
		{
			point=rand()%(chromsize-1)+1;
			for(j=point;j<chromsize;j++)
			{
				temp=pop[index[i]].chrom[j];
				pop[index[i]].chrom[j]=pop[index[i+1]].chrom[j];
				pop[index[i+1]].chrom[j]=temp;
			}
		}
	}
}
///////////
//////变异算子
void mutation(struct individual pop[])
{
	int i,j;
	double p=0.0;
	for(i=0;i<popsize;i++)
	{
		////对染色体进行变异
		for(j=0;j<chromsize;j++)
		{
			p=rand()%1000/1000.0;
			if(p<pm)
				pop[i].chrom[j]=(pop[i].chrom[j]==0)?1:0;
		}
		////重新计算变量值
		decode(pop[i].chrom,pop[i].x);
		////重新计算适应度
		pop[i].fitness=fitfun(pop[i].x);
	}
}
//////////
//////////输出函数：输出最佳个体组
void output_head()
{
	cout<<"程序参数及运行结果为："<<endl;
	cout<<"种群大小popsize="<<popsize
		<<" 染色体长度chromsize="<<chromsize
		<<" 总运行次数maxruns="<<maxruns<<endl
		<<" 交叉概率pc="<<pc
		<<" 变异概率pm="<<pm<<endl;
}
void output(int run)
{
	cout<<"run="<<run<<"时的最佳个体信息："<<endl;
	outputvar(best);
	cout<<"最佳个体适应度："<<cout.precision(8)<<(162.9-best.fitness)<<endl;
	cout<<"产生的世代数："<<best.generation<<" "<<"染色体为：";
	for(int i=0;i<chromsize;i++)
		cout<<best.chrom[i];
	cout<<endl<<"在线性能值为："<<online/(run+1)
		<<"离线性能值："<<offline/(run+1)<<endl;
	////////////
}
///////
///////适应度函数:根据需要修改
double fitfun(double x[])
{
	double value=0.0;
	///////需要修改适应度函数在下面改!
	//////六峰值驼背函数函数f(x,y)=(4-2.1*x^2+(x^4)/3)*x^2+x*y+(-4+4*y^2)*y^2
	value=(4-2.1*x[0]*x[0]+x[0]*x[0]*x[0]*x[0]/3)*x[0]*x[0]+x[0]*x[1]+(-4+4*x[1]*x[1])*x[1]*x[1];
	//////
	//////返回染色体适应值
	return (162.9-value);
}
////////
////////
///解码函数:将arr[]解码给x[var]
void decode(unsigned arr[],double x[])
{
	double num=0.0;
	for(int i=1;i<var+1;i++)
	{
		num=convert(arr,length[i-1],partchromsize[i]);
		num=(b[i-1]-a[i-1])*num/(pow(2,partchromsize[i])-1)+a[i-1];
		x[i-1]=num;
	}
}
//////////
////参数输入
void inputdata()
{
	////下面是变量所在区间值：
    a[0]=-3;b[0]=3;
    a[1]=-2;b[1]=2;
	cout<<"请输入变异概率:Pm=";cin>>pm;
	cout<<"请输入交叉概率:Pc=";cin>>pc;
}
//////////
////主函数
//////////
int main()
{
	////unsigned int seeds;
	////cout<<"请输入种子值(随机正整数)";
	////cin>>seeds;
	////srand(seeds);
	srand(time(NULL));
	inputdata();
	double begin=(double)clock()/CLK_TCK;
	initpop(newpop);
	int run=1;
	statistics(newpop,0);
	output_head();
	while(run<maxruns+1)
	{
		selection(newpop);
		crossover(newpop);
		mutation(newpop);
		statistics(newpop,run);
		output(run);
		run++;
	}
	cout<<"运行时间为："<<(double)clock()/CLK_TCK-begin<<"秒!"<<endl;
	return 0;
}