liegeneticreduct2.cpp
来自「某个实验事编写粗糙集智能信息处理的程序」· C++ 代码 · 共 504 行
CPP
504 行
// LieGeneticReduct1.cpp : implementation file
//
#include "stdafx.h"
#include "LieGeneticReduct2.h"
#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif
/////////////////////////////////////////////////////////////////////////////
// CLieGeneticReduct2
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cmath>
CLieGeneticReduct2::CLieGeneticReduct2()
{
srand((unsigned)time(0));
mutate_probability=0.1; //变异概率. 原为0.05
crossover_probability=0.5; //交叉概率.原为0.7,根据论文修改
m_nMaxGen=20;
}
CLieGeneticReduct2::~CLieGeneticReduct2()
{
}
////// InitTable,从CTable继承
//读入文件,初始化相关变量
bool CLieGeneticReduct2::InitTable(CString txtname)
{
if (! CTable::InitTable(txtname) )
return false;
// if (m_nConAttrNum<=5)
// m_nPopNum=4;
// else
// m_nPopNum=10;
//初始群体规模为 power( 其中pow(a,b)为计算a的b次方 属性个数大于6时取6,否则取原值
m_nPopNum=pow(2,m_nConAttrNum/2>6?6:m_nConAttrNum/2);
return true;
}
/*--------------------------------------------------
创建可辨识矩阵,存入m_matrix中.
m_matirx 类型见本类声明部分的头部.
----------------------------------------------------*/
bool CLieGeneticReduct2::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 CLieGeneticReduct2::ComputeFitness(const Permutation &pm)
{
TRACE("compute fitness;");
ASSERT( m_nConAttrNum == pm.size());
double ret;
CLieBitArray rd(m_nConAttrNum); //reduction
for(int i=0;i<pm.size();i++)
{
rd.SetBit(pm[i]);
if( RowsCoveredByReductInDescMatrix(rd) == m_matrix.size())
break;
}
ret= 1.0/(double)rd.Get1s();
TRACE("fitness: %f\n",ret);
return ret;
}
/*-----------------------------------------------------------
private function
名称:
RowsCoveredByReductInDescMatrix()
功能描述:
获得约简reduct在可辨识矩阵中所覆盖的条数
参数:
[in] reduct ,约简结果
返回值:
int类型,记录数
其它:
m_matrix :类成员,记录可辨识矩阵
------------------------------------------------*/
int CLieGeneticReduct2::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 CLieGeneticReduct2::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个个体,作为初始群体
{
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,ComputeFitness(tmp)));
}
}
/*--------------------------------------------------------
下面的函数供调试使用.
向Output窗口输出.测试各函数的正确性
慎重考虑之前不要使用该接口.
-----------------------------*/
#ifdef _DEBUG
void CLieGeneticReduct2::Output()
{
}
#endif //_DEBUG
bool CLieGeneticReduct2::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 CLieGeneticReduct2::WriteFile(CString name)
{
//排序
std::sort(m_population.begin(),m_population.end(),CLieGeneticReduct2::pair_fitness_greater);
// CLieBitArray& result_bitarray=m_population.begin()->first;
CLieBitArray result_bitarray(m_nConAttrNum); //reduction
result_bitarray.ClearAll();
int i;
for(i=0;i<m_population[0].first.size();i++)
{
result_bitarray.SetBit(m_population[0].first[i]);
if( RowsCoveredByReductInDescMatrix(result_bitarray) == m_matrix.size())
break;
}
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 CLieGeneticReduct2::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);
//从大到小排序.(按fitness排序)
// std::sort(m_population.begin(),m_population.end(),CLieGeneticReduct1::pair_fitness_greater);
//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=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 CLieGeneticReduct2::PerformCrossOver()
{
//m_population的顺序是select的顺序,已经具有随机性.
//故随机配对省略,从前到后,每两个个体进行配对.
for(int i=0;i<m_nPopNum;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_nPopNum-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
{//使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;//满足j在pos1和pos2之间
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;//对pos1,pos2区间内的不予处理
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;
}
}//end for(j)
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
}//end for(i)
}
void CLieGeneticReduct2::PerformMutate()
{//变异操作
int i;
int length=m_population[0].first.size(); //染色体长度
double minFitness=1000;
int minIndex;
for(i=0;i<m_nPopNum;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;
}
//计算fitness
//并且找出最差fitness
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);
//没有发现最佳个体，则替换适应度最小的个体，
//以维持群体规模
//m_population.push_back(OptimumChromosome);
m_population[minIndex]=OptimumChromosome;
}⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?