遗传k-means 基于遗传算法的k-means

#include<iostream> #include<stdlib.h> #include<math.h> #include<time.h> #include<sstream> #include<fstream> using namespace std; #define PS 150 #define NA 4 #define K 3 #define PopNum 30 #define SelectNum1 5 #define SelectNum2 10 #define DPopNum 60 #define PC 0.5 #define GeneNum 50 #define ED 0.0000001 int xxx; typedef struct { double p[NA]; double distance[K]; }Point; Point instance[PS]; typedef struct { Point clustercenter[K]; double fitness; }Pop; Pop pop[PopNum]; Pop oldpop[PopNum]; Pop sumpop[DPopNum]; int cluster[K][PS]; int clusternum[K]; double innerdistance[PopNum]; //double interdistance[PopNum]; void input()//读入待聚类数据 { fstream fin("iris.data"); int i; int j; string line; double word; for(i=0;getline(fin,line)&&i<PS;i++) { istringstream stream(line); for(j=0;stream>>word&&j<NA;j++) { instance[i].p[j]=word; } } } int find(int a[],int n,int b) { int ii; for(ii=0;ii<n;ii++) if(a[ii]==b) return 1; return 0; } void sort(int a[],int n)//冒泡排序 { int temp; int i,j; for(i=0;i<n;i++) for(j=0;j<n-i-1;j++) { if(a[j]>a[j+1]) { temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } } } void popsort(Pop pp[],int n)//从大到小 { Pop temp; int i,j; for(i=0;i<n;i++) for(j=0;j<n-i-1;j++) { if(pp[j].fitness<pp[j+1].fitness) { temp=pp[j]; pp[j]=pp[j+1]; pp[j+1]=temp; } } } void clear(Pop po[]) { int i,j,k; for(i=0;i<PopNum;i++) { po[i].fitness=0; for(j=0;j<K;j++) { for(k=0;k<NA;k++) po[i].clustercenter[j].p[k]=0; for(k=0;k<K;k++) po[i].clustercenter[j].distance[k]=0; } } } void initpop()//随机初始化 { int i,j; int num=0; int random; int popnum; int rt[K]; srand(time(NULL)); for(popnum=0;popnum<PopNum;popnum++) { num=0; for(;num<K;) { random=rand()%PS; if(!find(rt,num,random)) { rt[num]=random; num++; } } sort(rt,K); for(i=0;i<K;i++) for(j=0;j<NA;j++) { pop[popnum].clustercenter[i].p[j]=instance[rt[i]].p[j]; //cout<<pop[popnum].clustercenter[i].p[j]<<" "; } pop[popnum].fitness=0; //cout<<endl; } } void copypop() { int i; for(i=0;i<PopNum;i++) { oldpop[i]=pop[i]; } } void printfpop() { int i,j,k; for(i=0;i<PopNum;i++) { cout<<"个体"<<i+1<<" :"; for(j=0;j<K;j++) { cout<<"("; for(k=0;k<NA;k++) { cout<<pop[i].clustercenter[j].p[k]<<" "; } cout<<") "; } printf(" 准则函数值为：%4.5f\n",pop[i].fitness); //printf(" 类内距离为：%4.5f\n",innerdistance[i]); } } double eucliddistance(int x,int y,int z) { int i; double distance=0; for(i=0;i<NA;i++) { distance+=pow((instance[x].p[i]-pop[z].clustercenter[y].p[i]),2); } distance=sqrt(distance); return distance; } void calcuatedistance(int p) { int i,j; for(i=0;i<PS;i++) for(j=0;j<K;j++) { instance[i].distance[j]=eucliddistance(i,j,p); } } void Cluster(int p) { int i,j,k; double min; int index; for(k=0;k<K;k++) clusternum[k]=0; for(i=0;i<PS;i++) { index=0; min=instance[i].distance[0]; for(j=1;j<K;j++) { if(instance[i].distance[j]<min) { min=instance[i].distance[j]; index=j; } } cluster[index][clusternum[index]++]=i; } pop[p].fitness=0; innerdistance[p]=0.0; for(i=0;i<K;i++) { for(j=0;j<clusternum[i];j++) innerdistance[p]+=pow(instance[cluster[i][j]].distance[i],2); //pop[p].fitness+=pow(instance[cluster[i][j]].distance[i],2); pop[p].fitness=1/(1+innerdistance[p]); } } void evaluatepop() { int i; for(i=0;i<PopNum;i++) { calcuatedistance(i); Cluster(i); } } void tourselect() //???? { int i,j,k; int tt=5; int rr=15; int num; int random; int index; double max; int rt[5]; int tr[15]; Pop temp[PopNum]; int tempnum=0; popsort(pop,PopNum); for(i=0;i<PopNum;i++) { for(k=0;k<tt;k++) rt[k]=-1; num=0; for(;num<tt;) { random=rand()%PopNum; if(!find(rt,num,random)) rt[num++]=random; } sort(rt,tt); max=pop[rt[0]].fitness; index=rt[0]; for(j=1;j<5;j++) { if(pop[rt[j]].fitness>max) { max=pop[rt[j]].fitness; index=rt[j]; } } temp[tempnum]=pop[index]; tempnum++; } clear(pop); for(k=0;k<PopNum;k++) { pop[k]=temp[k]; } } void crossover() { int i,j,k; int t1,t2,tmp; double pc; Pop temp[PopNum]; Pop indivival1; Pop indivival2; //randshuffle(pop); for(i=0;i<PopNum;i+=2) { pc=(rand()%1000)/1000.0; if(pc<PC) { t1=i; t2=i+1; for(j=0;j<K;j++) { if(j%2==1) { tmp=t1; t1=t2; t2=tmp; } for(k=0;k<NA;k++) { indivival1.clustercenter[j].p[k]=pop[t1].clustercenter[j].p[k]; indivival2.clustercenter[j].p[k]=pop[t2].clustercenter[j].p[k]; } } indivival1.fitness=0; indivival2.fitness=0; temp[i]=indivival1; temp[i+1]=indivival2; } else { temp[i]=pop[i]; temp[i+1]=pop[i+1]; } } clear(pop); for(i=0;i<PopNum;i++) { pop[i]=temp[i]; pop[i].fitness=0; } clear(temp); } void updataclustercenter(int p) { int i,j,k; double sum; for(i=0;i<K;i++) { for(j=0;j<NA;j++) { sum=0; for(k=0;k<clusternum[i];k++) { sum+=instance[cluster[i][k]].p[j]; } pop[p].clustercenter[i].p[j]=sum/clusternum[i]; } } } void mutate() { int i; for(i=0;i<PopNum;i++) { calcuatedistance(i); Cluster(i); updataclustercenter(i); } } int cmp(const Pop &p1,const Pop &p2) { return p1.fitness<p2.fitness; } void crosseliteselect() { int i; for(i=0;i<PopNum;i++) { sumpop[i]=oldpop[i]; } for(i=PopNum;i<DPopNum;i++) { sumpop[i]=pop[i-PopNum]; } popsort(sumpop,DPopNum); clear(pop); clear(oldpop); for(i=0;i<PopNum;i++) { pop[i]=sumpop[i]; } } void nextgeneration() { copypop(); tourselect(); crossover(); mutate(); evaluatepop(); crosseliteselect(); } int main() { int i,j,k; double judgeend=1; double sum; double avg; input(); initpop(); evaluatepop(); cout<<"第"<<0<<"代："<<endl; printfpop(); for(i=0;(i<GeneNum)&&(judgeend>ED);i++) { judgeend=0; sum=0; avg=0; nextgeneration(); cou