📄 面向对象的模拟退火编程技术.cpp
字号:
//***********引入库函数
#include "iostream.h"
#include "math.h"
#include "stdlib.h"
#include "iomanip.h"
#include "time.h"
#include "fstream.h"
//*************定义常量
const int TRUE=1;
const int FALSE=0;
const int MarkovLengh=10000; //最大外循环
const int MaxInnerLoop=10000; //每一温度，若连续maxinnterloop次逗没有改进，则降温
const int MaxOuterLoop=60; //最大无改进降温次数，作为模拟退火停止条件
const double CO=0.1; //初始温度为：co*J，J:表示K均值聚类聚类结果准则函数值
const double DeclineRate=0.95; //温度下降速率，t=t*DeclineRate
const long MAX=100000;
const int AcceptRate=0.25; //接受邻域和产生的邻域的比值过大，则强迫降温
const double ForceDecline=0.9; //如果监测到温度过高，则要加大降温频率
//************定义全局变量
int DataNum; //聚类样本数目
int Dimension; //样本维数
int K; //分类数
double *DataSet; //指向浮点型的指针
int HALT=0;
int Row=3;
//***************************************************************
// 类 GETDATA： 设定全局变量，维数，样本数，和类别数等 ***
// 随机生成样本或手工输入样本的类 ***
//***************************************************************
class GETDATA{
public:
GETDATA();
void Display();
void Initial();
void Input();
double FRand(double,double);
double rand1,rand2; //随机数的高低值
};
GETDATA::GETDATA()
{
int i,j;
Dimension=2;
DataNum=50;
K=4;
DataSet=new double[Dimension*DataNum];
for(i=0;i<DataNum;i++)
{
for(j=0;j<Dimension;j++)
DataSet[i*Dimension+j]=(((double)rand()/(double)RAND_MAX)*100);
}
}
//*****************显示当前待聚类的样本(维数，个数，类别数等)
void GETDATA::Display()
{
int i,j;
cout<<" 当前样本集如下:"<<endl<<" {"<<endl;
for(i=0;i<DataNum;i++)
{
cout<<" [";
for(j=0;j<Dimension;j++)
{
cout<<" "<<setw(8)<<DataSet[i*Dimension+j];
}
cout<<" ] ";
if((i+1)%Row==0)
cout<<endl;
}
cout<<endl<<" }"<<endl;
cout<<endl<<" 以上实数样本集由计算机在1---100之间随机产，其中："<<endl;
cout<<endl<<" 样本维数 Dimension= "<<Dimension<<endl;
cout<<" 样本数 DataNum= "<<DataNum<<endl;
cout<<" 类别数 K= "<<K<<endl;
}
//****************输入待聚类样本，包括维数，个数，类别数等
void GETDATA::Input()
{
char flag;
int i,j;
double s=0;
cout<<endl<<" 请依次输入: 维数 样本数目 类别数"<<endl;
cout<<endl<<" 维数 Dimension: ";
cin>>Dimension;
cout<<endl<<" 样本数目 DataNum: ";
cin>>DataNum;
cout<<endl<<" 类别数 K：";
cin>>K;
cout<<endl<<" 随机生成数据输入R 人工输入按B: "<<endl; delete[]DataSet;
DataSet=new double[Dimension*DataNum];
cin>>flag;
if(flag=='R'||flag=='r')
{
cout<<" 输入随机数生成范围(最小值和最大值):"
<<endl<<" 最小值：";
cin>>rand1;
cout<<endl<<" 最大值：";
cin>>rand2;
for(i=0;i<DataNum;i++)
{
for(j=0;j<Dimension;j++)
DataSet[i*Dimension+j]=FRand(rand1,rand2);
}
}
else
if(flag=='H'||flag=='h')
{
for(i=0;i<DataNum;i++)
{
cout<<endl<<" 请输入第"<<i+1<<" 个样本的"<<Dimension<<" 个分量";
for(j=0;j<Dimension;j++)
cin>>DataSet[i*Dimension+j];
}
}
else
cout<<endl<<" 非法数据！ ";
}
//****************初始化聚类样本
void GETDATA::Initial()
{
char ch;
GETDATA::Display();
cout<<endl<<" 重新录入样本输入A 开始聚类B: ";
cin>>ch;
while(!(ch=='A'||ch=='a')&&!(ch=='B'||ch=='b'))
{
cout<<endl<<" 重新录入样本输入A 开始聚类B: ";
cin>>ch;
}
if(ch=='A'||ch=='a')
GETDATA::Input();
}
double GETDATA::FRand(double rand1,double rand2)
{
return rand1+(double)(((double)rand()/(double)RAND_MAX)*(rand2-rand1));
}
//***********************************************************
// 类SSA: 模拟退火算法的实现 ***
// 功能：根据设定的K,DataNum,Dimension等聚类 ***
//***********************************************************
class SAA
{
public:
struct DataType
{
double *data;
int father;
double *uncle;
};
struct ClusterType
{
double *center;
int sonnum;
};
SAA();
void Initialize();
void KMeans();
void SA( );
void DisPlay();
void GetDataset(DataType *p1,double *p2,int datanum,int dim);
void GetValue(double *str1,double *str2,int dim);
int FindFather(double *p,int k);
double SquareDistance(double *str1,double *str2,int dim);
int Compare(double *p1,double *p2,int dim);
void NewCenterPlus(ClusterType *p1,int t,double *p2,int dim);
void NewCenterReduce(ClusterType *p1,int t,double *p2,int dim);
double MaxFunc();
void Generate(DataType *p1,ClusterType *c1);
double Compare(DataType *p1,ClusterType *c1,DataType *p2,ClusterType *c2);
void CopyStatus(DataType *p1,ClusterType *c1,DataType *p2,ClusterType *c2);
int SecondFather(DataType *p,int t,int k);
double AimFunction(DataType *q,ClusterType *c);
double FRand(double ,double);
void KMeans1();
protected:
double Temp;
//double CO;
//double DeclineRate;
//int MarkovLengh;
//int MaxInnerLoop;
//int MaxOuterLoop;
double AimFunc;
DataType *DataMember, *KResult,*CurrentStatus,*NewStatus;
ClusterType * ClusterMember,*NewCluster,*CurrentCluster;
}; //end of class SAA
//************建立构造函数，初始化保护成员
SAA::SAA()
{
int i;
// DeclineRate=(double)0.9;
// MarkovLengh=1000;
// MaxInnerLoop=200;
// MaxOuterLoop=10;
// CO=1;
DataMember=new DataType[DataNum];
ClusterMember=new ClusterType[K];
for(i=0;i<DataNum;i++)
{
DataMember[i].data=new double[Dimension];
DataMember[i].uncle=new double[K];
}
for(i=0;i<K;i++)
ClusterMember[i].center=new double[Dimension];
GetDataset(DataMember,DataSet,DataNum,Dimension);
}//endSAA
//****************初始化参数，及开始搜索状态
void SAA::Initialize( )
{
//K-均值聚类法建立退火聚类的初始状态
// KMeans();
}
//*******************k-均值法进行聚类
//************接口：数据，数量，维数，类别
void SAA::KMeans()
{
int i,j,M=1;
int pa,pb,fa;
ClusterType *OldCluster;
//初始化聚类中心
OldCluster=new ClusterType[K];
for(i=0;i<K;i++)
{
// cout<<endl<<i+1<<"中心：";
GetValue(ClusterMember[i].center,DataMember[i].data,Dimension);
ClusterMember[i].sonnum=1;
OldCluster[i].center=new double[Dimension];
GetValue(OldCluster[i].center,ClusterMember[i].center,Dimension);
}
for(i=0;i<DataNum;i++)
{
// cout<<endl<<i+1<<": "<<ClusterMember[0].center[0]<<" "<<ClusterMember[1].center[0]<<" son: "<<ClusterMember[0].sonnum;
for(j=0;j<K;j++)
{
DataMember[i].uncle[j]=SquareDistance(DataMember[i].data,ClusterMember[j].center,Dimension);
// cout<<" "<<i+1<<"->"<<j+1<<": "<<DataMember[i].uncle[j]; //"类中心 "<<ClusterMember[j].center[0]<<": "<<DataMember[i].uncle[j]<<" ";
}
pa=DataMember[i].father=FindFather(DataMember[i].uncle,K);
if(i>=K)
{
// cout<<endl<<pa<<" 类样本数："<<ClusterMember[pa].sonnum;
ClusterMember[pa].sonnum+=1;
// cout<<endl<<pa<<" 类样本数："<<ClusterMember[pa].sonnum;
NewCenterPlus(ClusterMember,pa,DataMember[i].data,Dimension);
// cout<<endl<<i+1<<"->"<<pa+1<<"类 :"<<ClusterMember[pa].center[0];
GetValue(OldCluster[pa].center,ClusterMember[pa].center,Dimension);
}
}
//开始聚类，直到聚类中心不再发生变化。××逐个修改法××
while(!HALT)
{
//一次聚类循环：1.重新归类；2.修改类中心
for(i=0;i<DataNum;i++)
{
// cout<<endl;
for(j=0;j<K;j++)
{
// cout<<" D "<<DataMember[i].data[0]<<" "<<ClusterMember[j].center[0]<<" ";
DataMember[i].uncle[j]=SquareDistance(DataMember[i].data,ClusterMember[j].center,Dimension);
// cout<<DataMember[i].data[0]<<"->"<<ClusterMember[0l].center[0]<<" : "<<DataMember[i].uncle[0]<<endl;
// cout<<i+1<<"->"<<j+1<<" "<<DataMember[i].uncle[j];
}
fa=DataMember[i].father;
if(fa!=FindFather(DataMember[i].uncle,K)&&ClusterMember[fa].sonnum>1)
{
pa=DataMember[i].father;
ClusterMember[pa].sonnum-=1;
pb=DataMember[i].father=FindFather(DataMember[i].uncle,K);
ClusterMember[pb].sonnum+=1;
NewCenterReduce(ClusterMember,pa,DataMember[i].data,Dimension);
NewCenterPlus(ClusterMember,pb,DataMember[i].data,Dimension);
/* cout<<endl<<"*********************"<<M<<" 次聚类：*****************"; //聚一次类输出一次结果
cout<<endl<<DataMember[i].data[0]<<" in "<<pa+1<<"类 -> "<<pb+1<<"类: ";
for(t=0;t<K;t++)
{
cout<<endl<<" 第 "<<t+1 <<"类中心: "<<ClusterMember[t].center[0]<<" 样本个数："<<ClusterMember[t].sonnum;
}
DisPlay();
M=M+1;
*/
}
}//endfor
//判断聚类是否完成，HALT=1,停止聚类
HALT=0;
for(j=0;j<K;j++)
if(Compare(OldCluster[j].center,ClusterMember[j].center,Dimension))
break;
if(j==K)
HALT=1;
for(j=0;j<K;j++)
GetValue(OldCluster[j].center,ClusterMember[j].center,Dimension);
}//endwhile
}//end of KMeans
void SAA::KMeans1()
{
int i,j,M=1;
int pa,pb,fa;
ClusterType *OldCluster;
//初始化聚类中心
OldCluster=new ClusterType[K];
for(i=0;i<K;i++)
OldCluster[i].center=new double[Dimension];
for(j=0;j<K;j++)
GetValue(OldCluster[j].center,ClusterMember[j].center,Dimension);
//开始聚类，直到聚类中心不再发生变化。××逐个修改法××
while(!HALT)
{
//一次聚类循环：1.重新归类；2.修改类中心
for(i=0;i<DataNum;i++)
{
for(j=0;j<K;j++)
DataMember[i].uncle[j]=SquareDistance(DataMember[i].data,ClusterMember[j].center,Dimension);
fa=DataMember[i].father;
if(fa!=FindFather(DataMember[i].uncle,K)&&ClusterMember[fa].sonnum>1)
{
pa=DataMember[i].father;
ClusterMember[pa].sonnum-=1;
pb=DataMember[i].father=FindFather(DataMember[i].uncle,K);
ClusterMember[pb].sonnum+=1;
NewCenterReduce(ClusterMember,pa,DataMember[i].data,Dimension);
NewCenterPlus(ClusterMember,pb,DataMember[i].data,Dimension);
}
}//endfor
//判断聚类是否完成，HALT=1,停止聚类
HALT=0;
for(j=0;j<K;j++)
if(Compare(OldCluster[j].center,ClusterMember[j].center,Dimension))
break;
if(j==K)
HALT=1;
for(j=0;j<K;j++)
GetValue(OldCluster[j].center,ClusterMember[j].center,Dimension);
}//endwhile
}
//几个经常需要调用的小函数
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -