genmsrch.cpp

一个在vc++环境中实现的遗传算法

//头文件:		GenMSrch.hpp
//目的:			为遗传算法提供基类,该基类将评价函数值直接作为适合度,采用
//				新个体直接替换老个体的整体再生法,在搜索过程中,采用多目标法
//语言:			VC++ 6.0
//时间:			1999年11月~2000年1月
//作者:			刘康
//环境:			Win32
//注意:			EvalVal(INDIVIDUAL&)应由用户类覆盖,以提供正确的评价函数.
////////////////////////////////////////////////////////////////////////////

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

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

GenMSrch::GenMSrch(int n, int gl):Genetic(n,gl)
{
	VRProb = .2;
	SProb = .5;
}

GenMSrch::~GenMSrch()
{

}

//交叉再生方法
void GenMSrch::GenCross()
{
	if(CurrentChild>=ChildrenNum-1) return;
	int parent1 = ParentSelect();		//选择双亲1
	int *indSort = new int[IndNumber];
	int *indDis = new int[IndNumber];
	for(int st=0; st<IndNumber; st++)	//计算其它个体与双亲1的距离
	{
		indDis[st] = VisualDis(parent1,st);
		indSort[st] = st;
	}
	for(st=0; st<IndNumber-1; st++)		//将其他个体按距离排序
	{
		int mDis = st;
		for(int sst=st+1; sst<IndNumber; sst++)
			if(indDis[sst]<indDis[mDis]) mDis = sst;
		int tmp = indSort[st];
		indSort[st] = indSort[mDis];
		indSort[mDis] = tmp;
		tmp = indDis[st];
		indDis[st] = indDis[mDis];
		indDis[mDis] = tmp;
	}
	double *index = new double[IndNumber];//个体总适合度数组
	index[0] = Individual[indSort[0]].Fit;
	for(st=1; st<IndNumber; st++)		//按与双亲1距离计算个体总适合度
		index[st] = Individual[indSort[st]].Fit+index[st-1];
	int len = (int)((rand()/(double)RAND_MAX)*IndNumber*VRProb);
	if(len<1) len = 1;					//计算距离内个体个数
	int parent2;
	if(rand()/(double)RAND_MAX<=SProb)	//近亲结婚
	{
		parent2 = Wheel(index+1,len);	//滚轮选择,排除双亲1
		parent2 = indSort[parent2];
	}
	else								//远亲结婚
	{
		parent2 = Wheel(index+len,IndNumber-len);//滚轮选择
		parent2 = indSort[parent2];
	}
	delete []indSort;
	delete []indDis;
	delete []index;
	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;
}

//可视距离函数
int GenMSrch::VisualDis(int P1,int P2)
{
	int sLong = 0;
	for(int i=1; i<=Individual[P1].Chrom.GetLen(); i++)
		if(Individual[P1].Chrom.GetInt(i,i)!=Individual[P2].Chrom.GetInt(i,i))
			sLong++;
	return sLong;
}