限制颜色数的图着色---遗传算法

要解决的问题： 只用3种颜色完成图着色，使得冲突的边数最少。实际意义为，将3种PSS分配分配给各小区，使得冲突最少。

数据集： 邻区关系矩阵

#include "iostream" #include "fstream" #include "vector" #include "queue" #include "algorithm" #include "ctime" #include "set" #include "cstdlib" using namespace std; #define POPSIZE 50 //种群规模 #define MAXGENS 1000 //进化代数 #define PXOVER 0.8 //杂交概率 #define PMUTATION 0.15 //变异概率 #define PSELECT 0.85 const int N = 120; //结点数量 vector<int> G[N]; //邻接表 int cur_best; int generation; int x[N]; void Xover(int one, int two); struct Entity { set<int> gen[3]; //一个染色方案，即顶点集合的一种3-划分 int fitness; //适应度，为冲突边数 bool operator < (Entity node) const //按适应度从小到大排序 { return fitness > node.fitness; } int getFit() { int fit = 0; set<int>::iterator it; for(int i=0; i<3; i++) for(it=gen[i].begin(); it != gen[i].end(); it++) for(int v=0; v<G[(*it)].size(); v++) if(gen[i].count(G[*it][v])) /*如果当前结点与其邻接点在同一个划分中，则冲突*/ fit++; return fit; } }; Entity population[POPSIZE + 1]; //种群 Entity newpopulation[POPSIZE + 1]; //新种群 priority_queue<Entity> q; int num() { int edge = 0; for(int i=0; i<N; i++) for(int j=0; j<G[i].size(); j++) if(x[i]==x[G[i][j]]) edge++; return edge; } //返回arr[3]中最小数的下标 int minIndex(int arr[3]) { int min = arr[0]<arr[1] ? arr[0] : arr[1]<arr[2] ? arr[1] : arr[2]; for(int i=0; i<3; i++) if(arr[i] == min) return i; } //随机数产生函数 [low, high) double randval(double low, double high) { double val; val = ((double)(rand()%RAND_MAX)/(double)RAND_MAX)*(high - low) + low; return val; } //读入邻接矩阵，并转换为邻接表 void read() { ifstream fin; fin.open("t1.txt"); int i, j, g; for(i=0; i<N; i++) { for(j=0; j<N; j++) { fin >> g; if(g == 1) G[i].push_back(j); } } fin.close(); } void swap(int* p, int* q) { int tmp = *p; *p = *q; *q = tmp; } void shuffle(int *arr, int n) { int i; for(i=0; i<n; i++) { int idx = rand() % (i + 1); //选取互换的位置 swap(&arr[idx], &arr[i]); } } //种群初始化 void init() { read(); //读入文件 int num[N]; int i, j; for(i=0; i<N; i++) num[i] = i; int conflict[3]; for(i=0; i<POPSIZE; i++) //产生POPSIZE个排列 { shuffle(num, N); for(j=0; j<N; j++) { memset(conflict, 0, sizeof(conflict)); int u = num[j]; //当前顶点 for(int k=0; k<3; k++) //第k个划分 { for(int v=0; v<G[u].size(); v++) //G[u][v]为当前顶点的邻接点 if(population[i].gen[k].count(G[u][v])) conflict[k]++; } int min = minIndex(conflict); population[i].gen[min].insert(u); } } population[POPSIZE].fitness = N * N; } //取得每个个体的适应度 void evaluate(void) { for(int i=0; i<POPSIZE; i++) { population[i].fitness = population[i].getFit(); } } //保存遗传后的最佳个体 void keep_the_best() { int mem; cur_best = 0; set<int>::iterator it; //保存最佳个体的索引 for (mem = 0; mem < POPSIZE; mem++) { if (population[mem].fitness < population[POPSIZE].fitness) { cur_best = mem; population[POPSIZE].fitness = population[mem].fitness; } } //一旦找到种群的最佳个体就拷贝 for(int i=0; i<3; i++) { population[POPSIZE].gen[i].clear(); for(it=population[cur_best].gen[i].begin(); it!=population[cur_best].gen[i].end(); it++) population[POPSIZE].gen[i].insert(*it); } } //杂交函数：选择两个个体杂交 void crossover(void) { int mem, one; int first = 0; double x; for (mem = 0; mem < POPSIZE; ++mem) { x = randval(0, 1); if (x < PXOVER) { ++first; if (first % 2 == 0) //mem与one杂交 { Xover(one, mem); } else one = mem; } } } //交叉 void Xover(int one, int two) { int i; set<int>::iterator it; Entity X; for(i=0; i<3; i++) { for(it=population[one].gen[i].begin(); it!=population[one].gen[i].end(); it++) { if(population[two].gen[i].count(*it)) //交集 { X.gen[i].insert(*it); } } } //将剩余顶点随机插入3个划分中 for(i=0; i<N; i++) { if(!X.gen[0].count(i) && !X.gen[1].count(i) && !X.gen[2].count(i)) { double r = randval(0, 3); if(r<1) X.gen[0].insert(i); else if(r<2) X.gen[1].insert(i); else X.gen[2].insert(i); } } X.fitness = X.getFit(); q.push(X); } //变异函数，随机选择某一个体，并改变其中某一顶点所属划分 void mutate(void) { for (int i = 0; i < POPSIZE; i++) { double r1 = randval(0, 1); //随机选择变异个体 if(r1 < PMUTATION) { int r2 = rand()%N; //随机选择变异个体中的某个顶点 int r3 = rand()%3; //随机选择放到某个划分中 for(int j=0; j<3; j++) { if(population[i].gen[j].count(r2)) { population[i].gen[j].erase(r2); break; } } population[i].gen[r3].insert(r2); } } } //搜寻杰出个体函数：找出最好和最坏的个体。 //如果某代的最好个体比前一代的最好个体要坏，那么后者将会取代当前种群的最坏个体 void elitist() { int i; double best, worst; //最好和最坏个体的适应度值 int best_index, worst_index; //最好和最坏个体的索引 best = population[0].fitness; worst = population[0].fitness; for (i = 0; i < POPSIZE - 1; ++i) { if(population[i].fitness < population[i+1].fitness) { if (population[i].fitness <= best) //fitness越小，说明冲突的边数越少，适应性越好 { best = population[i].fitness; best_index = i; } if (population[i+1].fitness >= worst) { worst = population[i+1].fitness; worst_index = i + 1; } } else { if (population[i].fitness >= worst) { worst = population[i].fitness; worst_index = i; } if (population[i+1].fitness <= best) { best = population[i+1].fitness; best_index = i + 1; } } } //如果新种群中的最好个体比前一代的最好个体要强的话，那么就把新种群的最好个体拷贝出来。 //否则就用前一代的最好个体取代这次的最坏个体 ] set<int>::iterator it; if (best <= population[POPSIZE].fitness) { for(int i=0; i<3; i++) { population[POPSIZE].gen[i].clear(); for(it=population[best_index].gen[i].begin(); it!=population[best_index].gen[i].end(); it++) population[POPSIZE].gen[i].insert(*it); } population[POPSIZE].fitness = population[best_index].fitness; } else { for(int i=0; i<3; i++) { population[worst_index].gen[i].clear(); for(it=population[POPSIZE].gen[i].begin(); it!=population[POPSIZE].gen[i].end(); it++) population[worst_index].gen[i].insert(*it); } population[worst_index].fitness = population[POPSIZE].fitness; } } //选择函数，保证优秀的个体得以生存 void select(void) { int i; for(i=0; i<POPSIZE; i++) { q.push(population[i]); } i = 0; while(i < POPSIZE) { Entity node = q.top(); q.pop(); double p = randval(0, 1); if(p < PSELECT) { population[i] = node; } i++; } //清空优先队列 while(!q.empty()) q.pop(); } ofstream fout; //报告模拟进展情况 void report() { fout << "第" << generation << "代："; fout << "最优值为" << population[POPSIZE].fitness << endl; } int main() { srand(time(NULL)); fout.open("log.txt"); generation = 0; init(); evaluate(); //评价函数，可以由用户自定义，该函数取得每个基因的适应度 keep_the_best(); //保存每次遗传后的最佳基因 cout << "进化中(1000代，大约4分钟)...："; while(generation < MAXGENS) { cout << generation << " "; generation++; select(); //选择函数：用于最大化合并杰出模型的标准比例选择，保证最优秀的个体得以生存 crossover(); //杂交函数：选择两个个体来杂交，这里用单点杂交 mutate(); //变异函数：被该函数选中后会使得某一变量被一个随机的值所取代 report(); //报告模拟进展情况 evaluate(); //评价函数，可以由用户自定义，该函数取得每个基因的适应度 elitist(); //搜寻杰出个体函数：找出最好和最坏的个体。如果某代的最好个体比前一代的最好个体要坏，那么后者将会取代当前种群的最坏个体 } cout << "\n着色情况：" << endl; set<int>::iterator it; fout << "着色情况：" << endl; for(int i=0; i<3; i++) { for(it = population[POPSIZE].gen[i].begin(); it != population[POPSIZE].gen[i].end(); it++) { cout << (*it) << " "; fout << (*it) << " "; x[*it] = i+1; } cout << endl << endl; fout << endl << endl; } for(i=0; i<N; i++) cout << x[i] << " "; cout << endl; cout << "冲突边数：" << num() << endl; cout << "Time used = " << (double)clock()/CLOCKS_PER_SEC << "s\n"; //时间以秒为单位 fout << "Time used = " << (double)clock()/CLOCKS_PER_SEC << "s\n"; //时间以秒为单位 return 0; }

参考文献： 韩丽霞. 自然启发的优化算法及其应用研究[D]. 陕西：西安电子科技大学，2009.