antclusteralogrithm.cpp

一个关于蚁群聚类的程序希望对大家有用

// AntClusterAlogrithm.cpp: implementation of the CAntClusterAlogrithm class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "AntClusting.h"
#include "AntClusterAlogrithm.h"
#include "math.h"
#include "Ant.h"
#include "ArrayData.h"
#include "lqueue.h"
#include "LList.h"
///////////////////


/////////////////////



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

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

extern DataObject  *dataObj;
extern CArrayData * m_pAd;

CAntClusterAlogrithm::CAntClusterAlogrithm()
{
	 m_dDist = 0;
     m_nXSize = 0;    //// grid space size x=y=sqrt(9*N_objects)
     m_nYSize = 0;
	 m_dPickK=0;
	 m_dDropK=0;
	 m_dSimilar=0;
	 m_nACADataNum=0;
	 m_nACAPropNum=0;
	
}

CAntClusterAlogrithm::~CAntClusterAlogrithm()
{

}

void CAntClusterAlogrithm::InitDataObject()
{
	m_nACADataNum=m_pAd->GetDataNum(); 
	m_nACAPropNum=m_pAd->GetPropNum ();
	m_nXSize = (int)(sqrt(9*(int)m_nACADataNum));    //// grid space size x=y=sqrt(9*N_objects)
	m_nYSize = m_nXSize;

}

int CAntClusterAlogrithm::ClassifyData()
{
/*
	int clusterNo = 0;
	double tempDist = 0;
	m_dDist=m_dR;
	for(int i=0;i<m_nACADataNum;i++)
	{
		if (dataObj[i].clusterNo == 0)
		{
			bool createNewCluster = true;
			for(int j=i+1;j<m_nACADataNum;j++)
			{
				tempDist = sqrt((dataObj[j].x-dataObj[i].x)*(dataObj[j].x-dataObj[i].x)
					+(dataObj[j].y-dataObj[i].y)*(dataObj[j].y-dataObj[i].y));
				if(tempDist<m_dDist)
				{
					if(createNewCluster==true)
					{
						clusterNo++;
						dataObj[i].clusterNo = clusterNo;
						dataObj[j].clusterNo = clusterNo;
						createNewCluster = false;
					}
					else
					{
						dataObj[j].clusterNo = clusterNo;
					}
				}
			}
		}
	}
	
//*/

//	/*
	int clusterNo = 0;
	double tempDist = 0;
/////////////////////////////////////////////////////	m_dDist=5;
    srand((unsigned)time(NULL));
	int randData= rand()%m_nACADataNum;
	LQueue<int> ClassiedQue;              //存放已分类数据队列
	LList<int> ClassingList;              //存放待分类数据链表

	while(ClassingList.rightLength()<m_nACADataNum )   ///初始化
	{  
		 if(!ClassingList.Locate(randData))  ClassingList.append(randData); 
         randData= rand()%m_nACADataNum;
	}    
   
   
	while(!ClassingList.is_empty())
    {
		int nQueData=0;
		
		bool is_newQue=true;
		bool bGetNewData=false;
	   	ClassingList.setStart();
        ClassingList.remove(nQueData);
			
        ClassiedQue.clear(); 
		ClassiedQue.enqueue(nQueData);
       
		while(ClassiedQue.length()!=0)
		{
			
			ClassiedQue.frontValue(nQueData);
            ClassingList.setStart();
           
			while(ClassingList.rightLength()>0)
			{    
				int  nListData=0;
		        ClassingList.getValue(nListData);
			    tempDist = sqrt(pow(dataObj[nQueData].x-dataObj[nListData].x,2)+
					            pow(dataObj[nQueData].y-dataObj[nListData].y,2));
			  	if(tempDist<m_dDist)
				{
				     ClassiedQue.enqueue(nListData);	
					 ClassingList.remove(nListData);
				     bGetNewData=true;
					 
				}
                else ClassingList.next(); 
			}
           
			
			if(is_newQue&&bGetNewData==false) dataObj[nQueData].clusterNo=0;
			else if(is_newQue&&bGetNewData==true)
            { 
				clusterNo++;
				is_newQue=false;
                dataObj[nQueData].clusterNo=clusterNo ;
			}
			else dataObj[nQueData].clusterNo=clusterNo ;
			
            ClassiedQue.dequeue(nQueData); 
		}
			  
	}
		
   return clusterNo;
  }



double CAntClusterAlogrithm::CalcuSimilar(CAnt *m_pAnt)
{

	CString show,showTemp;
	show=showTemp="";
	double temp=0,distance=0;
	double dDistTemp=0;	
	double similar=0,tempsimilar=0;
	m_dSimilar=0;
    int i,j;
	switch(m_nACASimilarityFun){
	
	case 0:
	for(i=0;i<m_nACADataNum;i++)
	{   
		dDistTemp=0;
		distance = sqrt(pow(m_pAnt->m_dAntX-(dataObj+i)->x,2)
		            	+pow(m_pAnt->m_dAntY-(dataObj+i)->y,2));
		if(distance<=m_dR&&distance!=0)
		{   
		   for(j=0;j<m_nACAPropNum;j++)
		   dDistTemp+=pow(*(m_pAnt->m_pfAntPropArray+j)-*((dataObj+i)->m_pfa+j),2);
	
		   tempsimilar +=(1-sqrt(dDistTemp)/m_dAlpha);
		}
		
	}

	
	////////////////////////////////////
/*
	showTemp.Format("%f         ",tempsimilar);
    show+=showTemp;
//*/
  ////////////////////////////////////////////

	
	tempsimilar/=3.14159265358579*pow(m_dR,2);
	if(tempsimilar>0) m_dSimilar=tempsimilar;
	else   m_dSimilar=0;
/*

	showTemp.Format("%f",m_dSimilar);
	show+=showTemp;
    WriteLog(show);
//*/
    break;

	case 1:
		
///*
	for( i=0;i<m_nACADataNum;i++)
	{		
		distance = sqrt(pow(m_pAnt->m_dAntX-(dataObj+i)->x,2)
			+pow(m_pAnt->m_dAntY-(dataObj+i)->y,2));
		if(distance<=m_dR)
		{
           dDistTemp=0;
           for(j=0;j<m_nACAPropNum;j++)
		   dDistTemp+=sqrt(pow((*(m_pAnt->m_pfAntPropArray+j)-*((dataObj+i)->m_pfa+j)),2));
	  			if(	dDistTemp<1||dDistTemp>3)
				tempsimilar=0;
			else
			{
				temp =-((dDistTemp-2)*(dDistTemp-2)*11.5129);
				tempsimilar = pow(2.7183,temp);
			}
			similar += tempsimilar;
		}
	}
	m_dSimilar=similar/(3.14159*pow(m_dR,2));
/*	
	showTemp.Format("similar:%f         ",similar);
	show+=showTemp;
	showTemp.Format("m_dSimilar:%f",m_dSimilar);
	show+=showTemp;
    WriteLog(show);
//*/	
	  break;
	}

//*/
/*
		int DATANUMBER = dataobjarray->GetSize();
		DataObject tempdata;
		
		for(int i=0;i<DATANUMBER;i++)
		{
			tempdata=dataobjarray->GetAt(i);
			distance = sqrt((antX-tempdata.x)*(antX-tempdata.x)
				+(antY-tempdata.y)*(antY-tempdata.y));
			if(distance<r||distance==r)
			{
				Gpoint gpts[2];
				gpts[0].x = dataProperty1;
				gpts[0].y = dataProperty2;
				gpts[1].x = tempdata.property1;
				gpts[1].y = tempdata.property2;
				dist1 = MgsCalculateDistance(2, gpts);
				//			dist1 = sqrt((dataProperty1-dataobjarray->GetAt(i).property1)*(dataProperty1-dataobjarray->GetAt(i).property1)
				//				+(dataProperty2-dataobjarray->GetAt(i).property2)*(dataProperty2-dataobjarray->GetAt(i).property2));
				if(dist1<0.3||dist1>0.5)
					tempsimilar=0;
				else
				{
					temp =-((dist1-0.4)*(dist1-0.4)/0.0088);
					tempsimilar = pow(2.7183,temp);
				}
				similar += tempsimilar;
			}
		}
		similar/=3.14159*pow(r,2);
		//	if(similar<0)  similar=0;
		//*/

		return m_dSimilar;
}

double CAntClusterAlogrithm::CalcuDropProb(double similar)
{
/*	                                               ////运用分段函数
double dropProb;          
	if(_similar<=0)
		dropProb = 0;
	else if(_similar< 1/k)
		dropProb = k*_similar;
	else
		dropProb = 1;
	
	return dropProb;
*/
/*                                               ////运用LF改进模型
	double dropProb=0;          
	if(_similar>=1.0)
		dropProb=1.0;
	else
		dropProb=pow(_similar,4);
	
	return dropProb;
*/
/*                                                ////运用sigmoid 函数
     double dropProb=0;
     dropProb=1/(1+exp(-1*k*_similar));
     return dropProb;
*/

/*	
                                                  ////运用Deneubourg基本模型
	double dropProb=0; 
	double k2=0.2;
    dropProb=pow((_similar/(k2+_similar)),2);
	return dropProb;
*/
/*                                               /////运用LF基本模型*/

  double dropProb; 
  switch(m_nACASimilarityFun){
	  
  case 0:
  if(similar<m_dDropK)
		dropProb=2*similar;
	else
		dropProb=1;
   break;
  
  case 1:
	  if(similar<m_dDropK)
		  dropProb=20*similar;
	  else
		  dropProb=1;
	  break;
  }
  	return dropProb;
}

double CAntClusterAlogrithm::CalcuPickProb(double similar)
{
/*	                                           ////运用分段函数

  double pickProb=0;                              
	if(_similar<=0.0)
		pickProb = 1;
	else if(_similar<= 1/k)
		pickProb = 1-k*_similar;
	else
		pickProb = 0;
	
	return pickProb;
*/ 
/*
  double pickProb=0;                             ////运用sigmoid 函数
  pickProb=1/(1+exp(k*similar));
  return pickProb;
*/

///*                                             ////运用LF/Deneubourg基本模型
 double pickProb=0;
  pickProb=pow((m_dPickK/(m_dPickK+similar)),2);
 return pickProb;
// */ 

}


UINT CAntClusterAlogrithm::AntThreadProc(DataObject* _dataObj)
{
    
	CString ShowStrTemp = "";
	CString ShowStr = "";
    UINT postionChangeDataNum=0;
	int nLoopNum=0;


/*    if (alogrithm == NULL ||
        !alogrithm->IsKindOf(RUNTIME_CLASS(CAntClusterAlogrithm)))
    return 1;   // if pObject is not valid
*/   
     int nMovedNum=0;
     int randDataPosition;
	 double similar,pickProb,dropProb,randProb;
     srand((unsigned)time(NULL));
//	 criticalSection.Lock();	
 	 
	 randDataPosition = rand()%m_nACADataNum;
  
/*	 while(_dataObj[randDataPosition].isUsed)
	 {
		 randDataPosition = rand()%DATANUMBER;
	 }
*/
	 CAnt *m_pAnt;                      ////在主算法中生成蚂蚁类
	 m_pAnt=new CAnt(_dataObj+randDataPosition,randDataPosition,m_nACAPropNum);
//	 criticalSection.Unlock();
     for(UINT i=1;i<=m_nMaxCycNum;i++)
	 {
		ShowStr.Empty();
	    similar=CalcuSimilar(m_pAnt);     //计算蚂蚁所背负的数据对象与周围数据对象之间的相似性
		randProb =(double)(rand()%100)/100;
		


		//////////////////////////////////////////////////////////////////
     	ShowStrTemp.Format(_T("similar: %f   randProb: %f"),similar,randProb);
        ShowStr+=ShowStrTemp;
		////////////////////////////////////////////////////////////
             

	    if (!m_pAnt->m_bIsLoad)
		  {
			  pickProb = CalcuPickProb(similar);       /////计算蚂蚁的拾起概率



			  ///////////////////////////////////////
               ShowStrTemp.Format("  PickProb:%f",pickProb);
			   ShowStr+=ShowStrTemp;
			  /////////////////////////////////////////
			  
			   
			   
			   
			   if(pickProb<randProb)                 
			  {
			   // _dataObj[ant._dataPosition].isUsed = false;
		       // criticalSection.Lock();
				  randDataPosition = rand()%m_nACADataNum;
	///*
				  if(nMovedNum>m_nACADataNum)
				  {
					  for(int x=0;x<m_nACADataNum;x++)
				       dataObj[x].isMoved=FALSE;
				  }
				  while(_dataObj[randDataPosition].isMoved)
				  {
					   randDataPosition = rand()%m_nACADataNum;
				  }
	//*/			 
				  m_pAnt->SetAnt(&_dataObj[randDataPosition],randDataPosition);  ////如果不拾起数据对象，则重新赋给蚂蚁一个新的数据对象,即用新
				                                                               ////对象的属性来设置蚂蚁属性；
		    //	  criticalSection.Unlock();
			  }
/*1*/        else                                                     
			  {                                                            
				  m_pAnt->m_bIsLoad = true;
///////
				  nLoopNum=0;
				  
///////
	     		  float newx=m_nXSize*(float)(rand()%100)/100;   
                  float newy=m_nYSize*(float)(rand()%100)/100;
				  m_pAnt->AntChangePosition(newx,newy);          ////若拾起数据对象则移动蚂蚁到一个新位置；
			   }
		  }
		  else
		  {
/*2*/		  dropProb = CalcuDropProb(similar);               //////计算蚂蚁的放下概率
              
				  
			  /////////////////////////////////////////
			  ShowStrTemp.Format(_T("  DropProb: %f"),dropProb);
			  ShowStr+=ShowStrTemp;
			  /////////////////////////////////////////
					  
			  
			  if(dropProb>randProb)
			  {
/*4*/   		  m_pAnt->m_bIsLoad = false;
				  _dataObj[m_pAnt->m_nDataPosition].x = m_pAnt->m_dAntX;
				  _dataObj[m_pAnt->m_nDataPosition].y = m_pAnt->m_dAntY;

				  //_dataObj[ant._dataPosition].isUsed = false;
				  _dataObj[m_pAnt->m_nDataPosition].isMoved = true;
				  nMovedNum++;
				  
		//		  criticalSection.Lock();
				  postionChangeDataNum++;
				  randDataPosition = rand()%m_nACADataNum;
			/*	  while(_dataObj[randDataPosition].isUsed)
				  {
					   randDataPosition = rand()%DATANUMBER;
				  }   */
		          m_pAnt->SetAnt(&_dataObj[randDataPosition],randDataPosition); 
		  //	  criticalSection.Unlock();
			  }
/*3*/	      else
			  {   
                  nLoopNum++;
				  if(nLoopNum<200)
				  {  
					  float newx=m_nXSize*(float)(rand()%100)/100;   
                      float newy=m_nYSize*(float)(rand()%100)/100;
				      m_pAnt->AntChangePosition(newx,newy);}          ////移动蚂蚁到一个新位置；
				  else
				  {  
					  m_pAnt->m_bIsLoad = false;
				      _dataObj[m_pAnt->m_nDataPosition].x = m_pAnt->m_dAntX;
				      _dataObj[m_pAnt->m_nDataPosition].y = m_pAnt->m_dAntY;
				      _dataObj[m_pAnt->m_nDataPosition].isMoved = true;
				  	  nMovedNum++;
				      randDataPosition = rand()%m_nACADataNum;
		              m_pAnt->SetAnt(&_dataObj[randDataPosition],randDataPosition); 
				  }
			  }
		  }

	
		  
		  /////////////////////////////////////////////
//    WriteLog(ShowStr);
		  ///////////////////////////////

	  

	  }

    return postionChangeDataNum;   // thread completed successfully
}

void CAntClusterAlogrithm::getpara(double alpha,int antnum,double pickk,
			             double dropk,double r,UINT maxcycnum,
						 float dist,int SimilarityFun)
{  m_dAlpha=alpha;
   m_nAntNumber=antnum;
   m_dPickK=pickk;
   m_dDropK=dropk;
   m_dR=r;
   m_nMaxCycNum=maxcycnum;
   m_dDist=dist;
   m_nACASimilarityFun=SimilarityFun;
}