chrom.cpp

利用一个较为成熟的遗传算法基础类库（作者:刘康）

//头文件:		Chrom.hpp
//目的:			为染色体提供基类
//语言:			VC++ 6.0
//时间:			1999年6月~2000年1月
//作者:			刘康
//环境:			Win32
//////////////////////////////////////////////////////////////////////

#include <stdlib.h>
#include <iostream.h>
#include <time.h>
#include <math.h>
#include "chrom.hpp"

//染色体初始化种子初始化
unsigned Chromosome::Seed = 0;

int Chromosome::totalCrossNum = 0;
int Chromosome::totalMutaNum = 0;

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

//构造函数
Chromosome::Chromosome()
{
	GeneLen = 0;
	Gene = NULL;
	geneStr = NULL;
}
Chromosome::Chromosome(int l)
{
	GeneLen = l;
	geneStr = new char[GeneLen+1];
	Init();
}

Chromosome::Chromosome(int l, int ones)
{
	GeneLen = l;
	geneStr = new char[GeneLen+1];
	Init(ones);
	fixedOne=true;
}

Chromosome::Chromosome(const Chromosome &c)
{
	ChromNum = c.ChromNum;
	GeneLen = c.GeneLen;
	Gene = new OneChmType[ChromNum];
	geneStr = new char[GeneLen+1];
	for(int i=0; i<ChromNum; i++)
		Gene[i] = c.Gene[i];
}

//析构函数
Chromosome::~Chromosome()
{
	if(Gene) delete []Gene;
	if(geneStr) delete[]geneStr;
}

/////////////////////////////////////////////////////////////////////
//私有函数
/////////////////////////////////////////////////////////////////////

//染色体初始化
void Chromosome::Init()
{
	ChromNum = GeneLen/(sizeof(OneChmType)*8)+1;
	Gene = new OneChmType[ChromNum];
	for(int i=0; i<ChromNum; i++)	Gene[i] ^= Gene[i];
	if(!Seed) Seed = (unsigned)time(NULL);
	srand(Seed);
	Seed = Seed+(unsigned)time(NULL);
	for(i=0; i<GeneLen; i++)
	{
		int cNum = i/(sizeof(OneChmType)*8);
		if(rand()>=RAND_MAX/2) 
		{
			Gene[cNum] <<= 1;
			Gene[cNum] |= 0x1; //set 1
		}
		else Gene[cNum] <<= 1; //set 0
	}
}

//染色体初始化，可设定1的个数
void Chromosome::Init(int ones)		
{
	ChromNum = GeneLen/(sizeof(OneChmType)*8)+1;
	Gene = new OneChmType[ChromNum];
	for(int i=0; i<ChromNum; i++)	Gene[i] ^= Gene[i]; //set 0 to all
	if(!Seed) Seed = (unsigned)time(NULL);
	srand(Seed);
	Seed = Seed+(unsigned)time(NULL);

	//设置指定个数的1
	int pos,pos_num,pos_bit;
	for(i=0; i<ones;)
	{
		pos=(int)((float)rand()/RAND_MAX*(GeneLen-1)+.5);
		pos_num=pos/(sizeof(OneChmType)*8);
		pos_bit=pos-pos_num*(sizeof(OneChmType)*8);	

 		if(Gene[pos_num]&(0x01<<pos_bit)) continue;

		Gene[pos_num]|=(0x01<<pos_bit); //set 1
		i++;
	}
}

/////////////////////////////////////////////////////////////////////
//公有函数
/////////////////////////////////////////////////////////////////////

//设置染色体长度
void Chromosome::SetLen(int l)
{
	if(Gene) delete []Gene;
	GeneLen = l;
	if(geneStr) delete []geneStr;
	geneStr = new char[GeneLen+1];
	Init();
}

//设置染色体长度和1的个数
void Chromosome::SetLen(int l, int ones)
{
	if(Gene) delete []Gene;
	GeneLen = l;
	if(geneStr) delete []geneStr;
	geneStr = new char[GeneLen+1];
	Init(ones);
}

//返回字符串形式基因
/*
......
7,6,5,4
3,2,1,0
*/
const char* Chromosome::GetGeneStr()
{
	for(int i=0; i<GeneLen; i++)
	{
		int cNum = i/(sizeof(OneChmType)*8);
		int bit = i-cNum*(sizeof(OneChmType)*8);
		__int64 tmp = 0x1;
		tmp <<= bit;
		if(Gene[cNum] & tmp) geneStr[GeneLen-1-i] = '1';
		else geneStr[GeneLen-1-i] = '0';
	}
	geneStr[GeneLen] = '\0';
	return geneStr;
}

//返回i1位到i2位的整型值,包含i1,i2位
unsigned __int64 Chromosome::GetInt(int i1, int i2)
{
	if((i2-i1)<0 || (i2-i1)>=64 || i1<1) return -1;
	unsigned __int64 tmp=0;
	for(int i=i2-1; i>=i1-1; i--)
	{
		int cNum = i/(sizeof(OneChmType)*8);		//i位所在组
		int bits = i-cNum*(sizeof(OneChmType)*8);	//组内偏移
		OneChmType bit = (0x1<<bits);
		if(Gene[cNum]&bit)
		{
			tmp <<= 1;
			tmp |= 0x1;
		}
		else
			tmp <<= 1;
	}
	return tmp;
}

//=号重载函数
Chromosome& Chromosome::operator = (const Chromosome &c)
{
	if(Gene) delete []Gene;
	GeneLen = c.GeneLen;
	ChromNum = c.ChromNum;
	Gene = new OneChmType[ChromNum];
	for(int i=0; i<ChromNum; i++) Gene[i] = c.Gene[i];
	return *this;
}

//==号重载
bool Chromosome::operator == (const Chromosome &c)
{
	if(GeneLen!=c.GeneLen) return false;
	for(int i=0; i<ChromNum; i++)
		if(Gene[i] != c.Gene[i]) return false;
	return true;
}

//位变异函数
Chromosome Chromosome::Mutation(double prob)
{
	Chromosome temp(*this);
	if(fixedOne){//保持1的个数不变
		for(int i=0; i<GeneLen; i++)
		{
			int cNum = i/(sizeof(OneChmType)*8);		//所在组
			int bit = i-cNum*(sizeof(OneChmType)*8);	//组内偏移
			OneChmType bits = (0x1<<bit);
			if(((double)rand()/RAND_MAX)<prob){//需要变异
				int one,two;
				int one_num,two_num,one_bit,two_bit;
				one=i;
				one_num=one/(sizeof(OneChmType)*8);
				one_bit=one-one_num*(sizeof(OneChmType)*8);

				two=one;
				while(++two<GeneLen){
					two_num=two/(sizeof(OneChmType)*8);
					two_bit=two-two_num*(sizeof(OneChmType)*8);
					if(  (((temp.Gene[one_num]>>one_bit)^(temp.Gene[two_num]>>two_bit))&0x01)==1  )
						break;
				}
				
				if(two<GeneLen){//一次变异两位，保持1的个数不变
					OneChmType bits = (0x1<<one_bit);
					temp.Gene[one_num] ^= bits;
					bits = (0x1<<two_bit);
					temp.Gene[two_num] ^= bits;
					//cout<<".";
				}
				totalMutaNum++;
			}
		}
		/*		
		if(((double)rand()/RAND_MAX)<prob){
			int one,two;
			int one_num,two_num,one_bit,two_bit;
			one=(int)((float)rand()/RAND_MAX*(GeneLen-1)+.5);
			one_num=one/(sizeof(OneChmType)*8);
			one_bit=one-one_num*(sizeof(OneChmType)*8);

			two=one;
			while(++two<GeneLen){
				two_num=two/(sizeof(OneChmType)*8);
				two_bit=two-two_num*(sizeof(OneChmType)*8);
				if(  (((temp.Gene[one_num]>>one_bit)^(temp.Gene[two_num]>>two_bit))&0x01)==1  )
					break;
			}
			
			if(two<GeneLen){
				OneChmType bits = (0x1<<one_bit);
				temp.Gene[one_num] ^= bits;
				bits = (0x1<<two_bit);
				temp.Gene[two_num] ^= bits;
			}
		}
		*/
	}else{
	
		for(int i=0; i<GeneLen; i++)
		{
			int cNum = i/(sizeof(OneChmType)*8);		//所在组
			int bit = i-cNum*(sizeof(OneChmType)*8);	//组内偏移
			OneChmType bits = (0x1<<bit);
			if(((double)rand()/RAND_MAX)<prob){
				temp.Gene[cNum] ^= bits;
			}
		}
	}
	return temp;
}

//两性繁殖函数,一点交叉算子
bool Chromosome::OneCross(Chromosome& lover, Chromosome& chld1, Chromosome& chld2)
{
	if(GeneLen != lover.GeneLen) return false;
	int bits, bit;
	bits = (int)((float)rand()/RAND_MAX*(GeneLen-1)+.5);	//产生交叉点
	int cNum = bits/(sizeof(OneChmType)*8);		//交叉点所在的数组下标
	bit = bits-cNum*(sizeof(OneChmType)*8);		//交叉点数组内叉点
	OneChmType high, low;
	high = 0xffffffffffffffff<<bit;			//交叉点数组运算
	low = ~high;
	chld1.GeneLen = GeneLen;	chld1.Gene[cNum] = 0;
	chld2.GeneLen = GeneLen;	chld2.Gene[cNum] = 0;
	chld1.Gene[cNum] = (Gene[cNum]&high)+(lover.Gene[cNum]&low);
	chld2.Gene[cNum] = (lover.Gene[cNum]&high)+(Gene[cNum]&low);

	//修正的1点交叉，交换交叉点以后的所有位
	for(int i=cNum+1; i<ChromNum; i++)				//保持交叉点左边不变
	{
		chld1.Gene[i] = Gene[i];
		chld2.Gene[i] = lover.Gene[i];
	}
	for(i=0; i<cNum; i++)				//交换交叉点右边所有位
	{
		chld1.Gene[i] = lover.Gene[i];
		chld2.Gene[i] = Gene[i];
	}
	return true;
}

//两性繁殖,两点交叉算子
bool Chromosome::TwoCross(Chromosome &lover, Chromosome &chld1, Chromosome &chld2)
{
	if(GeneLen != lover.GeneLen) return false;
	int bit1, bit2, bitt;
	bit1 = (int)((float)rand()/RAND_MAX*(GeneLen-1)+.5);	//产生交叉点1,2
	bit2 = (int)((float)rand()/RAND_MAX*(GeneLen-1)+.5);
	if(bit1 > bit2) {
		bitt = bit1;
		bit1 = bit2;
		bit2 = bitt;
	}
	int cNum1 = bit1/(sizeof(OneChmType)*8);	//交叉点1,2数组下标
	int cNum2 = bit2/(sizeof(OneChmType)*8);

	//修正的2点交叉，交换两个交叉点之间的所有位
	for(int i=0; i<ChromNum; i++)		//其它组运算
	{
		if(i<cNum1 || i>cNum2)			// 1,2点两边保持不变
		{
			chld1.Gene[i] = Gene[i];
			chld2.Gene[i] = lover.Gene[i];
		}
		else if(i!=cNum1 && i!=cNum2)	// 1,2点中间交换
		{
			chld1.Gene[i] = lover.Gene[i];
			chld2.Gene[i] = Gene[i];
		}
	}
	//两个交叉数组运算
	int bbit1 = bit1-cNum1*(sizeof(OneChmType)*8);	// 1,2交叉数组内叉点
	int bbit2 = bit2-cNum2*(sizeof(OneChmType)*8);
	chld1.Gene[cNum1] = Gene[cNum1];		//交叉点1运算
	chld2.Gene[cNum1] = lover.Gene[cNum1];
	OneChmType bits;
	bits = 0xfffffffffffffff<<bbit1;
	//保持交叉点左边不变，交换右边的位
	chld1.Gene[cNum1] = (chld2.Gene[cNum1]&bits) | (Gene[cNum1]&~bits);
	chld2.Gene[cNum1] = (chld1.Gene[cNum1]&bits) | (lover.Gene[cNum1]&~bits);
	if(cNum1!=cNum2)						//交叉点2运算
	{
		//考虑到两个交叉点在一个组的情况，保持一致，便于处理
		chld1.Gene[cNum2] = lover.Gene[cNum2];
		chld2.Gene[cNum2] = Gene[cNum2];
	}
	bits = 0xfffffffffffffff<<bbit2;
	//交换交叉点左边的所有位，右边的保持不变
	chld1.Gene[cNum2] = (Gene[cNum2]&bits) | (chld1.Gene[cNum2]&~bits);
	chld2.Gene[cNum2] = (lover.Gene[cNum2]&bits) | (chld2.Gene[cNum2]&~bits);
	return true;
}

//两性繁殖,均匀交叉算子
bool Chromosome::UniCross(Chromosome& lover,Chromosome& chld1, Chromosome& chld2)
{
	if(GeneLen != lover.GeneLen) return false;
	OneChmType bit;
	for(int i=0; i<GeneLen; i++)
	{
		int cNum = i/(sizeof(OneChmType)*8);
		if((i-cNum*(sizeof(OneChmType)*8))==0) bit = 0x1;
		if(((float)rand()/RAND_MAX)>.5)
		{
			chld1.Gene[cNum] |= (this->Gene[cNum] & bit);
			chld2.Gene[cNum] |= (lover.Gene[cNum] & bit);
		}
		else
		{
			chld1.Gene[cNum] |= (lover.Gene[cNum] & bit);
			chld2.Gene[cNum] |= (this->Gene[cNum] & bit);
		}
		bit <<= 1;
	}
	return true;
}

//自我交叉算子(Self crossover)
bool Chromosome::SelfCross(Chromosome& chld)
{
	int crossBits,one,two;
	int one_num,two_num,one_bit,two_bit;
	int tmp1,tmp2;

	totalCrossNum++;

	for(int i=0; i<ChromNum; i++)		
	{
		chld.Gene[i] = Gene[i];
	}
	
	crossBits=(int)((float)rand()/RAND_MAX*(GeneLen/3)+.5);
	for (i=0;i<crossBits;i++){
		do{
			one=(int)((float)rand()/RAND_MAX*(GeneLen-1)+.5);
			two=(int)((float)rand()/RAND_MAX*(GeneLen-1)+.5);
		}while(one==two);

		one_num=one/(sizeof(OneChmType)*8);
		one_bit=one-one_num*(sizeof(OneChmType)*8);	
		two_num=two/(sizeof(OneChmType)*8);
		two_bit=two-two_num*(sizeof(OneChmType)*8);	

		tmp1=chld.Gene[one_num]&(0x01<<one_bit);
		tmp2=chld.Gene[two_num]&(0x01<<two_bit);
		if(tmp1==0)
			chld.Gene[two_num]&=(~(0x01<<two_bit)); //set 0
		else
			chld.Gene[two_num]|=(0x01<<two_bit); //set 1
		if(tmp2==0)
			chld.Gene[one_num]&=(~(0x01<<one_bit)); //set 0
		else
			chld.Gene[one_num]|=(0x01<<one_bit); //set 1
	}
	
	
/*
	int left1,left2,right1,right2,length;
	while(1){
		length=(int)((float)rand()/RAND_MAX*(GeneLen/2)+.5);	//产生交叉段长度
		left1 = (int)((float)rand()/RAND_MAX*(GeneLen-1)+.5);	//产生第一个交叉段头
		right2 = (int)((float)rand()/RAND_MAX*(GeneLen-1)+.5);  //产生第二个交叉段尾
		if(right2-left1 > length*2) 
			break;
	}
	right1=left1+length-1;
	left2=right2-length+1;

	//定义临时交换空间
	OneChmType *tmp1=new OneChmType[length/sizeof(OneChmType)+1];
	OneChmType *tmp2=new OneChmType[length/sizeof(OneChmType)+1];
	//第一个段拷贝到临时空间
	int begin;
	int left1_num = left1/(sizeof(OneChmType)*8);
	int right1_num = right1/(sizeof(OneChmType)*8);
	int left1_bit = left1-left1_num*(sizeof(OneChmType)*8);	
	int right1_bit = right1-right1_num*(sizeof(OneChmType)*8);
	for(int i=left1_num,j=0;i<=right1_num;i++,j++){
		tmp1[j]=Gene[i];
	}

	//第二个段拷贝到临时空间
	int left2_num = left2/(sizeof(OneChmType)*8);
	int right2_num = right2/(sizeof(OneChmType)*8);
	int left2_bit = left2-left2_num*(sizeof(OneChmType)*8);	
	int right2_bit = right2-right2_num*(sizeof(OneChmType)*8);

	for(i=0; i<ChromNum; i++)		//其它组运算
	{
		if(i<left1_num || i>right2_num || (i>right1_num)&&(i<left2_num))			
		{
			chld.Gene[i] = Gene[i];
		}
	}
		
	delete tmp1[];
	delete tmp2[];
*/	
	return true;
}