liegeneticreduct1.cpp

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

// LieGeneticReduct1.cpp : implementation file
//

#include "stdafx.h"
#include "../rset.h"
#include "LieGeneticReduct1.h"

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

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

CLieGeneticReduct1::CLieGeneticReduct1()
{
	srand((unsigned)time(0));
	mutate_probability=0.05;		//变异概率. 原先为0.1
	crossover_probability=0.7;		//交叉概率. 原先为0.5
	m_nMaxGen=50;//进化代数最大值
}

CLieGeneticReduct1::~CLieGeneticReduct1()
{
}

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

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

----------------------------------------------------*/
bool CLieGeneticReduct1::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;	//has been deleted
				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);//对应位置为1
						}
					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] reduct 一个约简结果
返回值:
	double类型, reduct的适应度

------------------------------------------------------------*/
double CLieGeneticReduct1::ComputeFitness(const CLieBitArray &reduct)
{
	TRACE("compute fitness;");
	ASSERT( m_nConAttrNum == reduct.GetBitLength());

	int _1s=reduct.Get1s();	//约简结果(染色体)中1的个数
	if( _1s == 0)
		return 0;//约简结果为空
//		return 1;
	int rows_covered=RowsCoveredByReductInDescMatrix(reduct);
							//约简结果(染色体)覆盖的记录数
	int rows_total=m_matrix.size();	 
	double ret;
	ret =   ( (double)m_nConAttrNum - _1s)/(double)m_nConAttrNum +
		 (double)rows_covered/ (double)rows_total;//适应度

	if (rows_covered == rows_total)
		ret+= 0.5;

	TRACE(" bitarray: %x",reduct.GetULAt(0));
	TRACE(" num of 1s: %d,rows_covered: %d,rows_total:%d ,ret: %f\n",
		_1s,rows_covered,rows_total,ret);
	return ret;
}


/*-----------------------------------------------------------
 private function
 名称: 
	RowsCoveredByReductInDescMatrix()
 功能描述:
	获得约简reduct在可辨识矩阵中所覆盖的条数
 参数:
	[in] reduct ,约简结果
 返回值:
	int类型,记录数
 其它:
	m_matrix :类成员,记录可辨识矩阵
------------------------------------------------*/
int CLieGeneticReduct1::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 CLieGeneticReduct1::InitPopulation(int initnum)
{
	TRACE("init population;\n");
	TRACE("init population number :%d\n",m_nPopNum);
	// num: the number of randam number needed.
	while(initnum--)		//生成m_nPopNum个个体,作为初始群体
	{
		CLieBitArray array(m_nConAttrNum);
		int num= m_nConAttrNum / 32 + (m_nConAttrNum % 32 != 0);//32是什么意思?
		for(int i=0;i<num;i++)
		{
			unsigned long temp=static_cast<unsigned long> (rand() );
			for(int j=0;j<32 && j<array.GetBitLength();j++)
			{
				if ( 1<< j & temp )
					array.SetBit( j+i*32 );
			}
		}
/*
		for(int i=0;i<array.GetULLength();i++)
		{
			unsigned long temp=static_cast<unsigned long> (rand() );
			array.SetULAt(i,temp);

		}
*/
		m_population.push_back( Chromosome_Fitness_Pair(array,ComputeFitness(array)));
	}
}

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

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

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

#ifdef _DEBUG
void CLieGeneticReduct1::Output()
{
//	InitPopulation(10);
	for( Population::iterator it_i=m_population.begin();it_i!=m_population.end();it_i++)
	  TRACE("indivadul: %x\n",it_i->first.getdata());
}
#endif //_DEBUG

bool CLieGeneticReduct1::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_nPopNum);		//初始群体设定
	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 CLieGeneticReduct1::WriteFile(CString name)
{
	//排序
	std::sort(m_population.begin(),m_population.end(),CLieGeneticReduct1::pair_fitness_greater);
	CLieBitArray& result_bitarray=m_population.begin()->first;

	ASSERT(result_bitarray.GetBitLength()==m_nConAttrNum);

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


void CLieGeneticReduct1::PerformSelect()
{
	ASSERT(m_population.size()== m_nPopNum);
	int *NF=new int[m_population.size()];
	int i;
	double total=0;
	double maxfitness=-1;
	double maxIndex=-1;
	Population temp_population;	//临时群体

	//找到群体中适应度最好的个体，保存下来。
	//若使用最佳个体保存方法进行选择时，需要本个体。

	for(i=0;i<m_population.size();i++)
	{
		total+=m_population[i].second;
		if(maxfitness<m_population[i].second)
		{
			maxfitness=m_population[i].second;
			maxIndex=i;
		}
	}
	
	OptimumChromosome=
	Chromosome_Fitness_Pair(m_population[maxIndex].first,
								maxfitness);


	//NF中存储 对应个体的正规化适应度*1000
	NF[0]=(int)(m_population[0].second/total *1000);
	for(i=1;i<m_population.size();i++)
		NF[i]=NF[i-1]+(int)(m_population[i].second/total *1000);

	//赌轮法构造新群体
	temp_population=m_population;
	m_population.clear();
	for(i=0;i<temp_population.size();i++)
	{
		int j;
		int randnum;
		if(NF[m_nPopNum-1]>0)//适应度有可能为0
		{
			randnum=rand()%NF[m_nPopNum-1];
			for(j=0;j<m_population.size()-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 CLieGeneticReduct1::PerformCrossOver()
{
	//m_population的顺序是select的顺序,已经具有随机性.
	//故随机配对省略,从前到后,每两个个体进行配对.
	for(int i=0;i<m_population.size()-1;i+=2)
	{
		//个体i和个体i+1以概率crossover_probability进行交叉
		if( (rand()%1000) > int(1000*crossover_probability) ) 
			continue;
		//crossover position
		int cp=rand() % (m_population.size()-1);
		CLieBitArray tmpBA=m_population[i].first;
		for(int j=0;j<=cp;j++)
		{
			if(m_population[i+1].first[j])
				m_population[i].first.SetBit(j);
			else
				m_population[i].first.ClearBit(j);

			if(tmpBA[j])
				m_population[i+1].first.SetBit(j);
			else
				m_population[i+1].first.ClearBit(j);
		}

	}
}
void CLieGeneticReduct1::PerformMutate()
{
	int i;
	int minIndex;			//最小适应度索引
	double minFitness=1000; //对应的最小适应度
	for(i=0;i<m_population.size();i++)
	{
		for( int j=0;j<m_population[i].first.GetBitLength();j++)
		{
			if( (rand() %1000) < int(1000*mutate_probability) )
				m_population[i].first.Flip(j);//j位取反
		}
		m_population[i].second=ComputeFitness(m_population[i].first);
		if(minFitness>m_population[i].second)
		{
			minFitness=m_population[i].second;
			minIndex=i;
		}
	}
	//若使用最佳个体保留方法,则
	//mutation完成之后，查看最佳个体是否仍然在群体中，
	//若不在，则把最佳个体加入群体
	for(i=0;i<m_population.size();i++)
	{
		if(m_population[i].first == OptimumChromosome.first)
			return;	//发现最佳个体
	}
	TRACE("保留最佳个体！替换掉个体%d - %f \n",minIndex,minFitness);

	//从大到小排序.(按fitness排序)
//	std::sort(m_population.begin(),m_population.end(),CLieGeneticReduct1::pair_fitness_greater);

	//没有发现最佳个体，则替换适应度最小的个体，
	//以维持群体规模
	
	//m_population.push_back(OptimumChromosome);
	m_population[minIndex]=OptimumChromosome;
}