liegeneticreduct3.cpp

来自「某个实验事编写粗糙集智能信息处理的程序」· C++ 代码 · 共 467 行

// LieGeneticReduct1.cpp : implementation file
//

#include "stdafx.h"

#include "LieGeneticReduct3.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

/////////////////////////////////////////////////////////////////////////////
// CLieGeneticReduct3
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cmath>

CLieGeneticReduct3::CLieGeneticReduct3()
{
	srand((unsigned)time(0));
	mutate_probability=0.1;		//变异概率.
	crossover_probability=0.5;		//交叉概率.
	m_nMaxGen=20;
}

CLieGeneticReduct3::~CLieGeneticReduct3()
{
}

////// InitTable,从CTable继承
//读入文件,初始化相关变量
bool CLieGeneticReduct3::InitTable(CString txtname)
{
	if (! CTable::InitTable(txtname) )
		return false;
	//初始群体规模为 power(
	m_InitNum=pow(2,m_nConAttrNum/2>6?6:m_nConAttrNum/2);
	return true;
}

/*--------------------------------------------------
	创建可辨识矩阵,存入m_matrix中.
	m_matirx 类型见本类声明部分的头部.

----------------------------------------------------*/
bool CLieGeneticReduct3::CreateMatrix()
{
	TRACE("CreateMatrix;\n");
	try
	{
		deleteDup();						//删除重复记录
		CLieBitArray array(m_nConAttrNum);	//一个bitarray
		for(int i=0;i<m_nCount-1;i++)
		{
			if(!m_bObj[i]) continue;		//has been deleted
			for(int j=i+1;j<m_nCount;j++)
			{
				if(!m_bObj[j]) continue;
				array.ClearAll();	//set all bits to '0'
				//	TRACE("object %d,%d :",i,j);
				//  决策不同
				if( m_Record[i][m_nConAttrNum] != m_Record[j][m_nConAttrNum] )
				{
					bool bCollision=true;
					for(int m=0;m<m_nConAttrNum;m++)
						if( m_Record[i][m] != m_Record[j][m] )
						{
							bCollision=false;
							//TRACE(" %d",m);
							array.SetBit(m);
						}
					if(bCollision)		//产生冲突...
					{
						TRACE("collision\n");
						//AfxMessageBox("collision");
						continue;
					}
				}
				else //  the decision  value is equal
					continue;
				
				m_matrix.push_back(array);
			} //end of for
		}	// end of for
	}// end of try
	catch(...)
	{
		return false;
	}
	if(!m_matrix.empty())
	   return true;
	else return false; 
}

/*------------------------------------------------------------
private function
名称: 
	ComputeFitness
功能描述:
	计算 一个约简结果的适应度 (fitness)

参数说明:
	[in] pm 一个排序
返回值:
	double类型, reduct的适应度

------------------------------------------------------------*/
double CLieGeneticReduct3::ComputeFitness(const Permutation &pm)
{
	TRACE("compute fitness;");
	ASSERT( m_nConAttrNum == pm.size());
	double ret;
	CLieBitArray rd(m_nConAttrNum);	//reduction
	rd.SetAll();
	for(int i=0;i<pm.size();i++)
	{
		rd.ClearBit(pm[i]);
		if( RowsCoveredByReductInDescMatrix(rd) == m_matrix.size())
			continue;
		else
			rd.SetBit(pm[i]);
	}

	ret= 1.0/(double)rd.Get1s();//适应度
	TRACE("fitness: %f\n",ret);
	return ret;
}


/*-----------------------------------------------------------
 private function
 名称: 
	RowsCoveredByReductInDescMatrix()
 功能描述:
	获得约简reduct在可辨识矩阵中所覆盖的条数
 参数:
	[in] reduct ,约简结果
 返回值:
	int类型,记录数
 其它:
	m_matrix :类成员,记录可辨识矩阵
------------------------------------------------*/
int CLieGeneticReduct3::RowsCoveredByReductInDescMatrix(const CLieBitArray &reduct)
{
	int rows_covered=0;;
	for( TABLE::const_iterator it_i=m_matrix.begin();it_i!=m_matrix.end();it_i++)
	{
		if ( ((*it_i) & reduct).Get1s()>0) //能覆盖!
			rows_covered++;
	}

	return rows_covered;
	
}

////////////////////////////////////////////
/*
	函数名: InitPopulation
	功能描述:
		随机初始化population(群体,即一个约简集合). 并把
		初始fitness设置为0.0
	参数:
		[in] initnum 初始群体中个体数
	返回值:
		无
*/
void CLieGeneticReduct3::InitPopulation(int initnum)
{
	TRACE("init population;\n");
	TRACE("init population number :%d\n",m_InitNum);
	// num: the number of randam number needed.
	while(initnum--)		//生成m_InitNum个个体,作为初始群体
	{
		int i;
		Permutation tmp;
		for(i=0;i<m_nConAttrNum;i++)
			tmp.push_back(i);

		for(i=0;i<m_nConAttrNum;i++)
		{
			//生成两个位置,进行交叉.
			int pos1=rand() % m_nConAttrNum;	//
			int pos2=rand() % m_nConAttrNum;	//
			int inttmp=tmp[pos1];
			tmp[pos1]=tmp[pos2];
			tmp[pos2]=inttmp;
		//	tmp[pos1]^=tmp[pos2];
		//	tmp[pos2]^=tmp[pos1];
		//	tmp[pos1]^=tmp[pos2];
		}
			
#ifdef _DEBUG
		TRACE("tmp size: %d\n",tmp.size());
		for(int x=0;x<tmp.size();x++)
			TRACE("%d ",tmp[x]);
		TRACE("\n");
#endif
		m_population.push_back( Chromosome_Fitness_Pair(tmp,0.0));
	}
}

/*--------------------------------------------------------

下面的函数供调试使用.
向Output窗口输出.测试各函数的正确性
慎重考虑之前不要使用该接口.

-----------------------------*/

#ifdef _DEBUG
void CLieGeneticReduct3::Output()
{
}
#endif //_DEBUG

bool CLieGeneticReduct3::reduct()
{
	//-----------time count
    double duration;
	CString str;
    clock_t  finish	,start;
	start = clock();
	///-------------end of time count
	try
	{
		if(!CreateMatrix())
		{
			AfxMessageBox("差别矩阵为空,不能进行本算法");
			return false;
		}
	}catch(...)
	{
		return false;
	}
	InitPopulation(m_InitNum);		//初始群体设定
	Population temp_population;
	int times=0;
	do
	{	
#ifdef _DEBUG
		TRACE("on reduct : %d\n",times);
		TRACE(" population nums: %d\n",m_population.size());
//		TRACE(" fist chromosome : %d  fitness: %f\n",m_population.begin()->first.getdata(),m_population.begin()->second);
#endif//_debug

		PerformSelect();
		PerformCrossOver();
		PerformMutate();

	}while(++times <m_nMaxGen);
	
//---------- time count----------
    finish = clock();
	duration = (double)(finish - start) / CLOCKS_PER_SEC;
	str.Format (" 约简运行时间:%f 秒",duration);
	AfxMessageBox(str);  
//--------------end of time count----------

	return true;
}

bool CLieGeneticReduct3::WriteFile(CString name)
{
	//排序
	std::sort(m_population.begin(),m_population.end(),CLieGeneticReduct3::pair_fitness_greater);
//	CLieBitArray& result_bitarray=m_population.begin()->first;

	CLieBitArray result_bitarray(m_nConAttrNum);	//reduction
	result_bitarray.SetAll();
	for(int i=0;i<m_population[0].first.size();i++)
	{
		result_bitarray.ClearBit(m_population[0].first[i]);
		if( RowsCoveredByReductInDescMatrix(result_bitarray) == m_matrix.size())
			continue;
		else
			result_bitarray.SetBit(m_population[0].first[i]);
	}
	ASSERT(result_bitarray.GetBitLength()==m_nConAttrNum);

	for(i=0;i<m_nConAttrNum;/*result_bitarray->GetBitLength()*/i++)
	{
		m_bAttr[i]= static_cast<bool>(result_bitarray[i]);
	}
	return CTable::WriteFile(name);	
}


void CLieGeneticReduct3::PerformSelect()
{
	ASSERT(m_population.size()== m_InitNum);
	int *NF=new int[m_population.size()];
	int i;
	double total=0;
	Population temp_population;	//临时群体
	//计算各个体适应度
	for(i=0;i<m_population.size();i++)
		total+=m_population[i].second=ComputeFitness(m_population[i].first);
	
	//从大到小排序.(按fitness排序)
//	std::sort(m_population.begin(),m_population.end(),CLieGeneticReduct3::pair_fitness_greater);
	
	//NF中存储 对应个体的正规化适应度*1000
	NF[0]=(int)(m_population[0].second/total *1000);
	for(i=1;i<m_InitNum;i++)
		NF[i]=NF[i-1]+(int)(m_population[i].second/total *1000);

	//赌轮法构造新群体
	temp_population=m_population;
	m_population.clear();
	for(i=0;i<m_InitNum;i++)
	{
		int j;
		int randnum=rand()%NF[m_InitNum-1];
		for(j=0;j<m_InitNum-1;j++)
			if( randnum<NF[j]) break;
		//now j is the index of selected indivadual
		m_population.push_back(temp_population[j]);
	}
	delete[] NF;
}

void CLieGeneticReduct3::PerformCrossOver()
{
	
	//m_population的顺序是select的顺序,已经具有随机性.
	//故随机配对省略,从前到后,每两个个体进行配对.
	for(int i=0;i<m_InitNum;i+=2)
	{
					
		#ifdef _DEBUG
			TRACE("before crossover: \n");
			for(int x=0;x<m_population[i+1].first.size();x++)
				TRACE("%d ",m_population[i].first[x]);
			TRACE("\n");
			for(x=0;x<m_population[i+1].first.size();x++)
				TRACE("%d ",m_population[i+1].first[x]);
			TRACE("\n");
		#endif

		//个体i和个体i+1以概率crossover_probability进行交叉
		if( (rand()%1000) > int(1000*crossover_probability) ) 
			continue;
		//crossover position
		// PMX 部分匹配交叉
		int cp=rand() % (m_InitNum-1);
		Permutation tmpBA=m_population[i].first;
		int pos1,pos2;
		int j;
		int length=m_population[i].first.size();
		pos1= rand() % length;
		pos2= rand() % length;

		
		if(pos1>pos2)	//swap if pos1>pos2
		{
			int	tmp=pos1;
			pos1=pos2;
			pos2=tmp;
		}

		TRACE("cross pos: %d,%d\n",pos1,pos2);
		//1.交换.
		for(j=0;j<length;j++)
		{
			if(j <pos1 || j>pos2 ) continue;
			int tmp=m_population[i].first[j];
			m_population[i].first[j]=m_population[i+1].first[j];
			m_population[i+1].first[j]=tmp;
		}

		//2.匹配区域外的重复项
		//  根据映射关系进行交换
///*
		for(j=pos1;j<pos2+1;j++)
		{
			int m;
			for(m=0;m<length;m++)
			{
				if(m>=pos1 && m<=pos2) continue;
				if(m_population[i].first[j] == m_population[i].first[m])
					break;
			}
			if(m<length)	//找到m位置值在交换后重合
			{
				int subs=m_population[i+1].first[j];
				while(1)
				{
					for(int in_i=pos1;in_i<pos2+1;in_i++)
					{
						if(subs == m_population[i].first[in_i])
						{
							subs=m_population[i+1].first[in_i];
							break;
						}
					}
					if(in_i>pos2)	//not find
						break;
				}
				m_population[i].first[m]=subs;
			}
		}

		//
		for(j=pos1;j<pos2+1;j++)
		{
			int m;
			for(m=0;m<length;m++)
			{
				if(m>=pos1 && m<=pos2) continue;
				if(m_population[i+1].first[j] == m_population[i+1].first[m])
					break;
			}
			if(m<length)	//找到m位置值在交换后重合
			{
				int subs=m_population[i].first[j];
				while(1)
				{
					for(int in_i=pos1;in_i<pos2+1;in_i++)
					{
						if(subs == m_population[i+1].first[in_i])
						{
							subs=m_population[i].first[in_i];
							break;
						}
					}
					if(in_i>pos2)	//not find
						break;
				}
				m_population[i+1].first[m]=subs;
			}
		}
		
//*/
		#ifdef _DEBUG
			TRACE("after crossover: \n");
			for(x=0;x<m_population[i].first.size();x++)
				TRACE("%d ",m_population[i].first[x]);
			TRACE("\n");
			for(x=0;x<m_population[i+1].first.size();x++)
				TRACE("%d ",m_population[i+1].first[x]);
			TRACE("\n");
		#endif

	}
}
void CLieGeneticReduct3::PerformMutate()
{
	int i;
	int length=m_population[0].first.size();	//染色体长度
	for(i=0;i<m_InitNum;i++)
	{
		for( int j=0;j<length;j++)
		{
			if( (rand() %1000) >= int(1000*mutate_probability) )
				continue;
			int pos1,pos2;
			pos1=rand()% length;
			pos2=rand()% length;
			int tmp=m_population[i].first[pos1];
			m_population[i].first[pos1]=m_population[i].first[pos2];
			m_population[i].first[pos2]=tmp;
		}
	}
}