gak.rar_K.

2010年全国硕士研究生入学考试初试成绩查询结果 2010年2月23日星期二 12:20:36 姓名 严学智 考生编号 101120000000234 证件号码 142625198701190433 政治理论 59 外国语 29 业务课一 64 业务课二 61 总分 213 #include <stdlib.h> #include <time.h> #include <math.h> #include <iostream> #include <vector> #include <algorithm> #include <sstream> #include <fstream> using namespace std; #define NI 150 #define NA 4 #define K 3 #define PopNum 30 #define PC 0.5 #define GeneNum 50 #define ED 0.01 typedef struct { double p[NA]; double distance[K]; //每个实例对象与各聚类中心的距离 }Point; Point instance[NI]; typedef struct { Point clustercenter[K]; double fitness; //适应值越小说明个体越好 }Pop; vector<Pop> pop; vector<Pop> oldpop; vector<int> cluster[K]; void ReadFile() { fstream fin("iris.data"); int i; int j; string line; double word; for(i = 0; getline(fin,line) && i < NI; i++) { istringstream stream(line); for(j = 0; stream >> word && j < NA; j++) { instance[i].p[j] = word; } } } void InitPop() { int i; int j; int popnum; int num; Pop temp; vector<int> vt; int random ; srand(time(NULL)); for(popnum = 0; popnum < PopNum; popnum++) { num = 0; for(i = 0; num < K; i++) { random = rand()%NI; if( find(vt.begin(),vt.end(),random) == vt.end() ) { vt.push_back(random); num++; } } sort(vt.begin(),vt.end()); for(i = 0; i < K; i++) { for(j = 0; j < NA; j++) { temp.clustercenter[i].p[j] = instance[vt[i]].p[j]; } } temp.fitness = 0; pop.push_back(temp); vt.clear(); } } void CopyPop() { int i; oldpop.clear(); for(i=0; i<pop.size(); i++) { oldpop.push_back(pop[i]); } } void PrintPop() { int i; int j; int k; for(i=0; i<PopNum; i++) { cout << " 个体 " << i << " : " ; /* 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); } } 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; int j; for(i=0; i<NI; i++) { for(j=0; j<K; j++) { instance[i].distance[j] = EuclidDistance(i,j,p); } } } void Cluster(int p) { int i; int j; int index; double min; for(i = 0; i < K; i++) { cluster[i].clear(); } for(i = 0; i < NI; 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].push_back(i); } /****计算种群中个体适应值****/ pop[p].fitness = 0; for(i = 0; i<K; i++) { for(j=0; j<cluster[i].size(); j++) { pop[p].fitness += pow(instance[cluster[i][j]].distance[i],2); } } } void EvaluatePop() { int i ; for(i=0; i<PopNum; i++) { CalcuateDistance(i); // 计算各实体到聚类中心的距离 Cluster(i); // 将各实体依据距离分配到各聚类中，并计算出适应度fitness } } void TourSelect() { int i; int j; int num; int random; int index; double min; vector<int> vt; vector<Pop> temp; for(i=0; i<PopNum; i++) { num = 0; vt.clear(); for(j=0; num<5; j++) //竞赛规模为 5 { random = rand()%PopNum; if( find(vt.begin(),vt.end(),random) == vt.end() ) { vt.push_back(random); num++; } } sort(vt.begin(),vt.end()); min = pop[vt[0]].fitness; index = vt[0]; for(j=1; j<5; j++) { if(pop[vt[j]].fitness < min) { index = vt[j]; min = pop[vt[j]].fitness; } } temp.push_back(pop[index]); } pop.clear(); for(i=0; i<temp.size(); i++) { pop.push_back(temp[i]); } } void CrossOver() // 采用N点交叉 N=K-1 { int i; int j; int k; //int randp; vector<Pop> temp; Pop individual_fst; Pop individual_snd; random_shuffle(pop.begin(),pop.end()); double pc ; int t1; int t2; int tmp; for(i=0; i < PopNum ; i+=2) { pc = rand()/RAND_MAX; 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++) { individual_fst.clustercenter[j].p[k] = pop[t1].clustercenter[j].p[k]; individual_snd.clustercenter[j].p[k] = pop[t2].clustercenter[j].p[k]; } } individual_fst.fitness = 0; individual_snd.fitness = 0; temp.push_back(individual_fst); temp.push_back(individual_snd); } else { temp.push_back(pop[i]); temp.push_back(pop[i+1]); } } pop.clear(); for(i=0; i<temp.size(); i++) { pop.push_back(temp[i]); } temp.clear(); } void UpdataClusterCenter(int p) { int i; int j; int k; double sum; for(i=0; i<K; i++) { for(j=0; j<NA; j++) { sum = 0; for(k = 0; k<cluster[i].size(); k++) { sum += instance[cluster[i][k]].p[j]; } pop[p].clustercenter[i].p[j] = sum/cluster[i].size(); } } } void Mutate() { int i ; for(i=0; i<PopNum; i++) { CalcuateDistance(i); // 计算各实体到聚类中心的距离 Cluster(i); // 将各实体依据距离分配到各聚类中 UpdataClusterCenter(i); //更新聚类中心坐标 } } bool cmp(const Pop &p1, const Pop &p2) { return p1.fitness < p2.fitness; } void CrossEliteSelect() { int i; for(i=0; i<oldpop.size(); i++) { pop.push_back(oldpop[i]); } sort(pop.begin(),pop.end(),cmp); pop.erase(pop.begin()+PopNum,pop.end()); } void NextGeneration() { CopyPop(); TourSelect(); CrossOver(); Mutate(); EvaluatePop(); CrossEliteSelect(); } int main() { int i; int j; double diff_value = 1; double sum ; double avg; ReadFile(); InitPop(); EvaluatePop(); for(i=0; i<GeneNum && diff_value > ED; i++) //达到最大迭代次数或方差和小于ED则程序结束 { diff_value = 0; sum = 0; avg = 0; cout << "第" << i << "代" << endl; NextGeneration(); for(j=0; j<PopNum; j++) { sum += pop[j].fitness; } avg = sum/PopNum; for(j=0; j<PopNum; j++) { diff_value += pow( (pop[j].fitness - avg),2 ); } } PrintPop(); system("pause"); return 1; }