maxfx.cpp

关于遗传算法的源码

#include"includeFile.h"

class Individual	//个体类：包含了该个体的编码信息，解码信息，以及交叉操作、变异操作等
{
public:
	Individual(int value);
	Individual();
	~Individual();
	int	  Fitness();//返回该个体的适应度值
	void  Cross(Individual &Ind);//和另一个个体Ind进行对半交叉
	void  Aberrance();//变异操作
	void  Replicate(Individual &BeRep);
	void  SetNumBeRe(int i);
	int   GetNumBeRe();
    Individual(const Individual &Ind);
	Individual & operator = (const Individual &Ind);
//private:
    bitset<BITLENGTH> *Bit;
	volatile int NumBeRe;//期望被复制的次数
};



class GA //实现遗传算法的类，
{
public:
	GA(vector<Individual>& VecInd);//直接把初始个体传过来，
	int GetMaxFit();
	int GetLoopNum();
private:
	int AveFit;			//平均适应度
	int SumFit;			//适应度之和
	int NumBeRe[BASELEN];//分别用来保存每一个个体期望被复制次数
	int MaxFit;			 //最大适应度
	int Count;			 //用来表示还存活的个体数
	int LoopNum;
};


//VecInd.push_back(test);

/*void MakeBaseSet(Individual set[])
{
	int i;
	srand( (unsigned)time( NULL ) );
	for(i=0;i<BASELEN;i++)
	{
		set[i] = new Individual(rand()%32);//随机产生一个0-32之间的数放入初始种群中
	}
}
*/


void main()
{
	srand( (unsigned)time( NULL ) );
//	Individual Set[BASELEN];//={Individual(1),Individual(28),Individual(8),Individual(19),};
	int i;

	Individual *test;
	vector<Individual> VecInd;//定义一个以Individual为对象的向量容器
	/*for(i=0;i<BASELEN;i++)		//初始化向量容器，并且初始化每个个体的基因（即Bit）
	{
		test = new Individual(rand()%32);
		assert(test!=NULL);
	//	Assert(test!=NULL);
		VecInd.push_back(*test);
		delete test;
		test =NULL;
	//	cout<<VecInd.at(i).Fitness()<<endl;
		cout<<VecInd.at(i).Bit->to_ulong()<<endl;
//		VecInd.push_back(Set[i]);
	//	cout<<VecInd.at(i).Fitness()<<endl;
		

	}*/

	test = new Individual(28);
	VecInd.push_back(*test);
	delete test;

	test = new Individual(24);
	VecInd.push_back(*test);
	delete test;

	test = new Individual(13);
	VecInd.push_back(*test);
	delete test;

	test = new Individual(3);
	VecInd.push_back(*test);
	delete test;
/*	test = new Individual(7);
	VecInd.push_back(*test);
	cout<<VecInd.at(i).Fitness()<<endl;
	delete test;
*/


/*	vector<Individual>::iterator IteInd;
	IteInd = VecInd.begin();
	while(IteInd!=VecInd.end())
	{
		cout<<IteInd->Fitness()<<endl;
		IteInd++;
	}*/
	
	//测试拷贝构造函数和赋值函数用
/*	Individual a(19),b;
	cout<<a.Fitness()<<endl;
	cout<<b.Fitness()<<endl;
	b=a;
	cout<<a.Fitness()<<endl;
	Individual c(b);
	cout<<c.Fitness()<<endl;
	system("pause");
	*/
	/*for(i=0;i<BASELEN;i++)
	{
		cout<<VecInd.at(i).Fitness()<<endl;
	}*/



/*	Set[1]=new bitset<BITLENGTH>(5);
	int i;
	i=Set[1]->to_ulong();
	cout<<i<<endl;
	MakeBaseSet(Set);
	i=Set[0]->to_ulong();
	cout<<i<<endl;
	Set[2]=new bitset<BITLENGTH>(*Set[1]);
	i=Set[2]->to_ulong();
	cout<<i<<endl;
*/
//	MakeBaseSet(Set);




	GA ga(VecInd);
	cout<<ga.GetMaxFit()<<endl;
	cout<<ga.GetLoopNum()<<endl;
	
	
}





//Individual类的实现
Individual::Individual(int value)
{
	Bit=new bitset<BITLENGTH>(value);
	assert(Bit != NULL);
	NumBeRe=1;
}
Individual::Individual()
{
	Bit = new bitset<BITLENGTH>(rand()%32);
	assert(Bit != NULL);
	NumBeRe=1;
}

Individual::Individual(const Individual &Ind)//拷贝构造函数
{
	int len;
	len = Ind.Bit->size();
	Bit = new  bitset<BITLENGTH>;
	assert(Bit != NULL);
	for(int i=0;i<len;i++)
	{
		Bit->set(i,Ind.Bit->at(i));
	}
	NumBeRe=1;
	/*if(Bit!=NULL)
	{
		delete Bit;
		Bit = new bitset<BITLENGTH>(Ind.Bit->to_ulong());
	}
	else
	{
		Bit = new bitset<BITLENGTH>(Ind.Bit->to_ulong());
	}*/
}

Individual& Individual::operator = (const Individual &Ind)
{
	int len;
	len = Ind.Bit->size();
	for(int i=0;i<len;i++)
	{
		Bit->set(i,Ind.Bit->at(i));
	}
	return *this;
}


Individual::~Individual()
{
	delete Bit;
}

int Individual::Fitness()
{
	int x;
	x=Bit->to_ulong();
	return -x*x+31*x+10;
}

void Individual::Cross(Individual &Ind)
{
	bool temp[BITLENGTH];//交换对应位时，用来做中间变量
	int i;
	i=0;
	while(i<(BITLENGTH/2))
	{
		temp[i]=(*Bit)[i];
		i++;
	}
	i=0;
	while(i<(BITLENGTH/2))
	{
		Bit->set(i,(*Ind.Bit)[i]);
		Ind.Bit->set(i,temp[i]);
		i++;
	}
}

void Individual::Aberrance()
{

}

void Individual::Replicate(Individual &BeRep)
{
	int len;
	len = BeRep.Bit->size();
	for(int i=0;i<len;i++)
	{
		Bit->set(i,BeRep.Bit->at(i));
	}
	
}


void Individual::SetNumBeRe(int i)
{
	NumBeRe = i;
}

int Individual::GetNumBeRe()
{
	return NumBeRe;
}

GA::GA(vector<Individual>& VecInd)
{
	//对每个个体计算其适应度，并且把这一代和上一代进行比较看是否结束算法
	//然后计算出适应度值和，适应度平均值，然后计算其复制次数；
	vector<Individual>::iterator IteInd = VecInd.begin(),iteTemp;
	int i;
	int flag=0;
	int temp;
	int n=10;
	float f,m,t;
	MaxFit=-65535;
	Count = BASELEN;
	LoopNum = 0;
	//从这里开始循环
	while(n>0)
	{
		LoopNum++;
		n--;
		temp = -65535;//把MaxFit的初值设成最小
		for(IteInd = VecInd.begin(),SumFit=0;IteInd != VecInd.end();IteInd++)	//计算适应度
		{
			if(IteInd->GetNumBeRe() != 0)//只有没有被淘汰的个体才被计算适应度
			{
				SumFit+=IteInd->Fitness();
				if( temp < IteInd->Fitness() )
				{
					temp = IteInd->Fitness();
				}
				else
				{
				}
			}
			else
			{
			}
		}
		m=MaxFit;
		t=temp;
		f=(m-t)/m;
		f=f>0?f:f*(-1);
		if(f<0.001)//判断是否结束遗传算法
		{
			flag=1;		//是的话，就置标志位为1
			MaxFit = MaxFit>temp?MaxFit:temp;
		}
		else
		{
			MaxFit = MaxFit>temp?MaxFit:temp;
		}

		//总适应度除以存活的个体数，然后四舍五入得到平均适应度
		AveFit = (int) (SumFit/VecInd.size()+0.5);
	
		//计算每个个体的期望复制次数
		for(IteInd = VecInd.begin();IteInd != VecInd.end();IteInd++)
		{
			m = IteInd->Fitness();  //用浮点数来保存适应度，和平均适应度，以便计算期望复制次数
			t = AveFit;

			//设置个体的期望被复制次数
			IteInd->SetNumBeRe( (int) (m/t+0.5));
			if(IteInd->GetNumBeRe() == 0)
			{
				iteTemp = IteInd-1;
				//注意这里可能出问题，删除IteInd所指的元素后IteInd又指向哪里了呢？
				VecInd.erase(IteInd);	
				IteInd = iteTemp;
			}
			else
			{
			}
		//	Count=Count-1+NumBeRe[i];//Count-(1-NumBeRe[i])用来计算还存活的个体
		}

		//开始复制，凡是NumBeRe=0（即期望复制次数为0）的都被淘汰，它的资源被新复制的个体占用
		for(IteInd = VecInd.begin();IteInd != VecInd.end();IteInd++)
		{
			if(IteInd->GetNumBeRe() > 1)//期望复制次数为1的个体不采取任何操作
			{
				/*int j=0,nbr=NumBeRe[i];
				while(j<BASELEN&&nbr>1)//搜寻应该被淘汰的个体，然后占用它的资源
				{
					if(NumBeRe[j]==0)
					{
						Base[j].Replicate(Base[i]);
						nbr--;
						NumBeRe[j]=1;//表示已经复制过了
						j++;
					}
					else
					{
						j++;
					}
				}*/


				//如果期望被复制此数大于1，则开始复制，直接调用拷贝构造函数
				Individual *temp;
				while(IteInd->GetNumBeRe()>1)
				{
					temp = new Individual(IteInd->Bit->to_ulong());
					assert(temp != NULL);
					VecInd.push_back(*temp);
					delete temp;
					temp = NULL;
					IteInd->SetNumBeRe( (IteInd->GetNumBeRe())-1);
				}
			}
			else
			{
			}
		}

		//开始交叉
		int CrossLen = VecInd.size()/2;//交叉距离，就是说相隔CrossLen长度的个体相互交叉
		vector<Individual>::iterator inteTemp;
		inteTemp = VecInd.begin()+CrossLen;
		for(IteInd = VecInd.begin();IteInd != inteTemp;IteInd++)
		{
			/*if(NumBeRe[i]!=0&&NumBeRe[i+CrossLen]!=0)//只有没有被淘汰的个体才进行交叉
			{
				Base[i].Cross( Base[i+CrossLen] );
			}
			else
			{
			}*/

			IteInd->Cross(*(IteInd+CrossLen));
		}
		


	}
}

int GA::GetMaxFit()
{
	return MaxFit;
}

int GA::GetLoopNum()
{
	return LoopNum;
}