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

298 阅读 0 评论 197 点赞

我是靠谱客的博主义气诺言，最近开发中收集的这篇文章主要介绍限制颜色数的图着色---遗传算法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

要解决的问题：
只用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 << "sn";
//时间以秒为单位
fout << "Time used = " << (double)clock()/CLOCKS_PER_SEC << "sn";
//时间以秒为单位
return 0;
}