genetic.cpp

这是一个用C++编写的

//头文件:		Genetic.hpp
//目的:			为遗传算法提供基类,该基类将评价函数值直接作为适合度,采用
//				新个体直接替换老个体的整体再生法
//语言:			VC++ 6.0
//注意:			EvalVal(INDIVIDUAL&)应由用户类覆盖,以提供正确的评价函数.
//////////////////////////////////////////////////////////////////////

#include <stdlib.h>
#include "Genetic.hpp"
#include <string.h>

long BadCount;//错解次数
long count ;//迭代次数
double BestVal;//最优解的适应值
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

Genetic::Genetic()
{
	IndNumber = 0;
	GeneLen = 0;
	Elitism = ELITISM;
	Cross = ONE_POINT;
	Parameter = GEN_FIXED;
	OperatorFit[0]=60;  OperatorFit[1]=OperatorFit[0]+40;
	OperatorStart[0] = 70; OperatorStart[1] = 30;
	OperatorEnd[0] = 50; OperatorEnd[1] = 50;
	CrossProb = 0.8;
	MutProb = 0.01;
	ElitismProb = 0.1;
	CurrentChild = 0;
	ChildrenNum = IndNumber;
	Individual = 0;
	Children = 0;
	IndIndex = 0;
	FitIndex = 0;
	Communication = NULL;
}
Genetic::Genetic(int n, int gl)//n为染色体个数，gl为长度
{
	IndNumber = n;
	GeneLen = gl;
	Elitism = ELITISM; //精英方法标志
						//精英方法参数-NONE:无精英,ELITISM:有精英
	Cross = ONE_POINT; //交叉方法标志,
						//交叉方法参数-ONE_POINT:一点交叉,TWO_POINT:两点交叉,UNIFORM_CROSS:均匀交叉
	Parameter = GEN_INTERPOLATION;//参数方法标志
						//变异参数方法-GEN_FIXED:参数固定,INTEPOLATION:参数插值
	//	double OperatorFit[2];		//算子适合度数组:交叉算子,变异算子
	OperatorFit[0]=60;  OperatorFit[1]=OperatorFit[0]+40;
	//	double OperatorStart[2];	//初始算子适合度,用于算子插值
	OperatorStart[0] = 70; OperatorStart[1] = 30;
	//	double OperatorStart[2];	//终止算子适合度,用于算子插值
	OperatorEnd[0] = 50; OperatorEnd[1] = 50;
	CrossProb = 0.8/*0.8*/;//交叉率0.4~0.99
	MutProb = 0.08/*0.01*/;//变异率0.01~0.1
	ElitismProb = 0.1;//精英比率
	CurrentChild = 0;//当前再生亲子数
	ChildrenNum/*一代再生亲子数 */= IndNumber;
	IndInit();
	Communication = NULL;
}
Genetic::Genetic(Genetic& g)
{
	Elitism = g.Elitism;
	Cross = g.Cross;
	Parameter = g.Parameter;
	OperatorFit[0] = g.OperatorFit[0];
	OperatorFit[1] = g.OperatorFit[1];
	OperatorStart[0] = g.OperatorStart[0];
	OperatorStart[1] = g.OperatorStart[1];
	OperatorEnd[0] = g.OperatorEnd[0];
	OperatorEnd[1] = g.OperatorEnd[1];
	CrossProb = g.CrossProb;
	MutProb = g.MutProb;
	IndNumber = g.IndNumber;
	GeneLen = g.GeneLen;
	CurrentChild = g.CurrentChild;
	ChildrenNum = g.ChildrenNum;
	ElitismProb = g.ElitismProb;
	Communication = g.Communication;
	IndInit();
	for(int i=0; i<IndNumber; i++)
	{
		Individual[i].Chrom = g.Individual[i].Chrom;
		Individual[i].Fit = g.Individual[i].Fit;
		Individual[i].Val = g.Individual[i].Val;
		FitIndex[i] = g.FitIndex[i];
		IndIndex[i] = g.IndIndex[i];
	}
}

Genetic::~Genetic()
{
	if(Individual) delete []Individual;
	if(Children) delete []Children;
	if(IndIndex) delete []IndIndex;
	if(FitIndex) delete []FitIndex;
}

//设置个体数和个体长度，程序运行第一步初始化
void Genetic::SetNumLen(int IndN, int GLen)
{
	if(Individual) delete []Individual;
	if(Children) delete []Children;
	if(IndIndex) delete []IndIndex;
	if(FitIndex) delete []FitIndex;
	IndNumber = IndN;
	GeneLen = GLen;//二进制数位数
	ChildrenNum = IndNumber;
	IndInit();
}

// struct INDIVIDUAL {			//定义个体结构
// 	Chromosome Chrom;		//个体染色体
// 	double Fit;				//个体适合度
// 	double Val;				//个体评价函数值
// 	};

//个体初始化
bool Genetic::IndInit()//indNuber为染色体个数
{
	Individual = new INDIVIDUAL[IndNumber]; //个体数组指针
	Children = new INDIVIDUAL[IndNumber];	//子群数组指针
	IndIndex = new int[IndNumber];  //个体适合度索引数组指针,按评价函数值高低存储个体号
	FitIndex = new double[IndNumber]; //总适合度数组
	if(Individual && Children && IndIndex && FitIndex) 
	{
		for(int i=0; i<IndNumber; i++)
		{
			Individual[i].Chrom.SetLen(GeneLen);//SetLen设置染色体长度,即二进制位数
			Children[i].Chrom.SetLen(GeneLen);
			IndIndex[i] = i;
		}
		return true;
	}
	else return false;
}
//计算总适合度，所有个体合适度之和？？
void Genetic::CalFitIndex()
{
	double allfit = 0;
	for(int i=0; i<IndNumber; i++)
	{
		allfit += Individual[i].Fit-Individual[IndIndex[IndNumber-1]].Fit;
	//	int *IndIndex;				//个体适合度索引数组,按评价函数值高低存储个体号
		FitIndex[i] = allfit;
	}
}
//设置交叉变异适合度
void Genetic::SetOperator(double c, double m)
{
	OperatorFit[0] = c;
	OperatorFit[1] = OperatorFit[0]+m;
}
//设置标志集
void Genetic::SetFlags(CROSS_METHOD c, ELITISM_METHOD e, PARAMETER_METHOD p)
{
	Cross = c;
	Elitism = e;
	Parameter = p;
}
//设置交叉率和变异率
void Genetic::SetProbability(double c, double m)
{
	CrossProb = c;
	MutProb = m;
}
//获得第i个个体基因字串
const char* Genetic::GetGeneStr(int i)
{
	return Individual[i].Chrom.GetGeneStr();
}
//计算所有个体适合度
void Genetic::AllFit()
{
	for(int i=0; i<IndNumber; i++)
		GetFit(i);
}
//个体适合度计算
double Genetic::GetFit(int i)
{
	Individual[i].Fit = Individual[i].Val;
	return Individual[i].Fit;
}
//计算所有个体评价函数值
void Genetic::AllVal()
{
	for(int i=0; i<IndNumber; i++)
		GetVal(i);
}
//计算个体评价函数值
double Genetic::GetVal(int i)
{
	return EvalVal(Individual[i]);
}
//滚轮选择方法
int Genetic::Wheel(double* index, int len)
{
	double random = (rand()/(double)RAND_MAX)*index[len-1];
	int i = 0;
	while(random>index[i] && i<len-1) i++;
	return i;
}
//双亲选择方法
int Genetic::ParentSelect()
{
	return Wheel(FitIndex,IndNumber);//轮赌盘选择
}

// 按适合度排序索引数组//zr更改为从小到大排列
// void Genetic::IndexSort()
// {
// 	for(int i=0; i<IndNumber; i++)
// 	{
// 		int min = i;
// 		for(int j=i; j<IndNumber; j++)
// 			if(Individual[IndIndex[min]].Val>Individual[IndIndex[j]].Val)
// 				min = j;
// 		int t = IndIndex[min];
// 		IndIndex[min] = IndIndex[i];
// 		IndIndex[i] = t;
// 	}
// }

//按适合度排序索引数组
void Genetic::IndexSort()
{
	for(int i=0; i<IndNumber; i++)
	{
		int max = i;
		for(int j=i; j<IndNumber; j++)
			if(Individual[IndIndex[max]].Val<Individual[IndIndex[j]].Val)
				max = j;
			int t = IndIndex[max];
			IndIndex[max] = IndIndex[i];
			IndIndex[i] = t;
	}
}

//算子选择方法:0-交叉算子,1-变异算子
int Genetic::OperatorSelect()
{
	return Wheel(OperatorFit,2);
}
//变异再生方法
void Genetic::GenMutation()
{
	if(CurrentChild>=ChildrenNum) return;
	int parent = ParentSelect();
	Children[CurrentChild].Chrom = Individual[parent].Chrom.Mutation(MutProb);
	CurrentChild++;
}
//交叉再生方法
void Genetic::GenCross()
{
	if(CurrentChild>=ChildrenNum-1) return;
	int parent1 = ParentSelect();
	int parent2 = ParentSelect();
	if((rand()/(double)RAND_MAX)<CrossProb)
	{
		if(Cross == ONE_POINT)
			Individual[parent1].Chrom.OneCross(Individual[parent2].Chrom,
											   Children[CurrentChild].Chrom,
											   Children[CurrentChild+1].Chrom);
		else if(Cross == TWO_POINT)
			Individual[parent1].Chrom.TwoCross(Individual[parent2].Chrom,
											   Children[CurrentChild].Chrom,
											   Children[CurrentChild+1].Chrom);
		else
			Individual[parent1].Chrom.UniCross(Individual[parent2].Chrom,
											   Children[CurrentChild].Chrom,
											   Children[CurrentChild+1].Chrom);
	}
	else
	{
		Children[CurrentChild].Chrom = Individual[parent1].Chrom;
		Children[CurrentChild+1].Chrom = Individual[parent2].Chrom;
	}
	CurrentChild += 2;
}
//精英方法
void Genetic::GenElitism()
{
	int elitismNum = int(ChildrenNum*ElitismProb);
	if(elitismNum <1) elitismNum = 1;
	if(CurrentChild+elitismNum>IndNumber)
		elitismNum = IndNumber-CurrentChild;
	for(int i=CurrentChild; i<CurrentChild+elitismNum; i++)
		Children[i].Chrom = Individual[IndIndex[i]].Chrom;
	CurrentChild += elitismNum;
}
//产生新一代
void Genetic::Generation()
{
	CurrentChild = 0;
	if(Elitism==ELITISM) GenElitism();
	while(CurrentChild < ChildrenNum-1)
	{
		if(OperatorSelect()==1 || CurrentChild>=ChildrenNum-1)
			GenMutation();
		else
			GenCross();
	}
	INDIVIDUAL *tmpInd;
	tmpInd = Individual;
	Individual = Children;
	Children = tmpInd;
//	for(int i=0; i<ChildrenNum; i++)
//		Individual[IndIndex[IndNumber-i-1]].Chrom = Children[i].Chrom;
	Prepare();
}
//运行遗传算法 ,按最大迭代次数运行
const char* Genetic::Run(unsigned long gn)//返回字符串形式最佳基因个体
{
	Prepare();
	double OperatorStep = 0;
	if(Parameter == GEN_INTERPOLATION)//变异参数方法-GEN_FIXED:参数固定,INTEPOLATION:参数插值
		OperatorStep = (OperatorEnd[0]-OperatorStart[0])/gn;//初始算子适合度,用于算子插值
	for(unsigned long generator=0; generator<gn; generator++)
	{
		if(Parameter == GEN_INTERPOLATION)
			OperatorFit[0] += OperatorStep;
		Generation();//产生新一代
		if(Communication!=NULL)
			Communication(Individual[IndIndex[0]].Chrom.GetGeneStr(),
				Individual[IndIndex[0]].Fit,
				Individual[IndIndex[0]].Val);
	}
	return Individual[IndIndex[0]].Chrom.GetGeneStr();
}
//运行遗传算法 ,按最优个体适合度不更新次数
const char* Genetic::RunFitN(unsigned long gn)//返回字符串形式最佳基因个体
{
	Prepare();
	double OperatorStep = 0;

	if(Parameter == GEN_INTERPOLATION)//变异参数方法-GEN_FIXED:参数固定,INTEPOLATION:参数插值
		OperatorStep = (OperatorEnd[0]-OperatorStart[0])/gn;//初始算子适合度,用于算子插值

	double FitBest =0;
	unsigned long nNoCharge = 0;
	do 
	{
		if(Parameter == GEN_INTERPOLATION)
			OperatorFit[0] += OperatorStep;
		Generation();//产生新一代
		count++;//统计程序运行一次的迭代次数
		if(Communication!=NULL)
			Communication(Individual[IndIndex[0]].Chrom.GetGeneStr(),
			Individual[IndIndex[0]].Fit,
			Individual[IndIndex[0]].Val);
		if (Individual[IndIndex[0]].Val > FitBest)
		{
			FitBest = Individual[IndIndex[0]].Val;
			nNoCharge = 0;
		}
		if (Individual[IndIndex[0]].Val == FitBest)
		{
			nNoCharge++;
		}
	} while(nNoCharge < gn);

	BestVal = Individual[IndIndex[0]].Val;//最优解的适应值

	//检查是否收敛于正确解
	char* RightAn = "00000000001000000000000000000000";
	bool bYN = true;//标志位
	if (strcmp(Individual[IndIndex[0]].Chrom.GetGeneStr(), RightAn) !=0 )
	{
		BadCount++;
	}

	return Individual[IndIndex[0]].Chrom.GetGeneStr();
}
//准备遗传运算  @@@@@@@@@@@
void Genetic::Prepare()
{
	AllVal();//计算所有个体评价函数值
	IndexSort();//按适合度排序索引数组
	AllFit(); //计算所有个体适合度
	CalFitIndex();//计算总适合度
}
//设置初始算子适合度
void Genetic::SetOptStartEnd(double s1,double e1,double s2,double e2)
{
	OperatorStart[0] = s1;
	OperatorStart[1] = s2;
	OperatorEnd[0] = e1;
	OperatorEnd[1] = e2;
	OperatorFit[0] = OperatorStart[0];
	OperatorFit[1] = OperatorStart[0]+OperatorEnd[0];
}