genetic1.cpp.txt

用VC++6.0编写的遗传算法源程序

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

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

//////////////////////////////////////////////////////////////////////
// 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)
{
	IndNumber = n;
	GeneLen = gl;
	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;
	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();
}

//个体初始化
bool Genetic::IndInit()
{
	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);
			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;
		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);
}
//按适合度排序索引数组
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)
		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();
}
//准备遗传运算
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];
}