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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
#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 << "sn";
//时间以秒为单位
fout << "Time used = " << (double)clock()/CLOCKS_PER_SEC << "sn";
//时间以秒为单位
return 0;
}