图着色
问题描述
在图论中，图是对象的结构化集合，用于表示对象对之间的关系。对象在图中表示为顶点（或节点），而一对对象之间的关系使用边表示：
图是非常有用的对象，因为它们可以用于表示大量的现实生活中的结构、模式和关系，例如社交网络，电网布局，网站结构，计算机网络，原子结构等等。
图着色任务可以简单概括为：为图中的每个节点分配一种颜色，并保证相连接的节点对不会使用相同的颜色，下图显示了争取着色的图示例：
在图着色问题中，我们通常希望使用尽可能少的颜色。例如，在上图中，可以使用三种颜色正确地对所示图进行着色。但是不可能仅使用两种颜色对其进行正确着色。从图论的角度而言，这意味着该图的色数（chromatic number）为3。
应用
许多现实生活中的问题都可以转化为图表示，并可以抽象为图着色问题。例如，为学生安排课程或为员工安排班次可以转换为图，其中相邻节点表示导致冲突的班级或班次。导致冲突的原因可能是同时上课的班级或连续的班次。由于此冲突，将同一个人分配给两个班级（或两个班次）将导致时间表无效。如果每种颜色代表不同的人，则将不同的颜色分配给相邻节点将解决冲突。同样，N皇后问题可以表示为图着色问题，其中图中的每个节点都代表棋盘上的正方形，而每对处于同一行、列或对角线的棋子通过边连接。其他相关应用包括对无线电台的频率分配，交通信号灯定时等等。
解的表示形式
可以使用整数列表表示图着色问题的解，其中每个整数代表一种颜色，而列表的每个元素都与图的节点之一匹配。
假设图中有10个节点，因此可以为每个节点分配0到9之间的索引。然后，使用10个元素的列表表示该图的节点颜色。例如：
(0, 2, 1, 3, 1, 2, 0, 3, 3, 0)
1. 使用了四种颜色，分别由整数0、1、2、3表示。
2. 第一、第七和第十个节点用第一种颜色着色。
3. 第三和第五节点用第二种颜色着色。
4. 第二和第六节点用第三种颜色着色。
5. 第四、第八和第九节点用第四颜色着色。
为了评估解决方案，需要遍历每对相连接的节点，并检查它们是否共享相同的颜色。将着色问题转换为违反颜色约束的问题，目标是将违反次数最小化，直到其为零，以实现图的正确着色。
同时还试图将使用的颜色数量减到最少。如果已知最小颜色数，我们可以使用与已知颜色数一样多的整数值。但是，多数情况下我们并没有此先验知识，一种解决方法是首先对使用的颜色数量进行估计。如果使用此数字找到合适的解决方案，则可以减少该数字，然后重试。如果未找到解决方案，则可以增加数量，然后重试直到找到能够找到解决方案的最小数量。可以通过使用软约束和硬约束来更快找到最小值。
图着色问题中的约束条件
首先定义硬约束和软约束：
1. 硬约束：为获得有效解而必须遵守的约束
2. 软约束：为获得最佳解而尽可能遵守的约束
在图着色问题中，颜色分配要求（其中两个相连接的节点不能具有相同颜色）是一个硬约束。必须将违反此约束的次数最小化为零，以获得有效的解。
将使用的颜色数量最小化作为一种软约束。我们希望最小化此数字，但不以违反硬约束为代价。
以高于估计值的颜色数开始算法流程，并使色数最小化，直到——理想情况下——达到实际的最小颜色数。通过创建成本函数来实现此方法，其中硬约束违反的成本大于违反软约束的成本。将总成本用作要最小化的适应度函数。
利用python实现问题创建
为了封装图形着色问题，创建名为 GraphColoringProblem 的 Python 类。
为了实现该类，需要利用 NetworkX 库，该库可以进行图的创建，处理和绘制。使用NetworkX 类的实例作为需要着色的图。除了可以从头开始创建图之外，还可以利用该库中预定义的图。
GraphColoringProblem 类的构造函数接受要着色的图形作为参数。此外，它接受hardConstraintPenalty 参数，该参数表示违反硬约束的惩罚因子。
# 导入所需库 import networkx as nx import matplotlib.pyplot as plt import numpy as np class GraphColoringProblem: def __init__(self,graph,hardConstraintPenalty): # 初始化实例变量 self.graph = graph self.hardConstraintPenalty = hardConstraintPenalty # 创建图节点的列表 self.nodeList = list(self.graph.nodes) # 创建图的邻接矩阵 self.adjMatrix = nx.adjacency_matrix(graph).todense() def __len__(self): """ :return: the number of nodes in the graph """ return nx.number_of_nodes(self.graph) def getCost(self,colorArrangement): """ 计算给定颜色组合的总成本 """ return self.hardConstraintPenalty * self.getViolationsCount(colorArrangement) + self.getNumberOfColors(colorArrangement) def getViolationsCount(self,colorArrangement): """ 计算给定颜色排列中违反颜色的次数 """ if len(colorArrangement) != self.__len__(): raise ValueError("size of color arrangement should be equal to ", self.__len__()) violations = 0 # 遍历每对节点，查找它们之间是否存在链接并使用相同的颜色 for i in range(len(colorArrangement)): for j in range(i + 1,len(colorArrangement)): if self.adjMatrix[i,j]: if colorArrangement[i] == colorArrangement[j]: violations += 1 return violations def getNumberOfColors(self, colorArrangement): """ 计算给定颜色排列使用的颜色数量 """ return len(set(colorArrangement)) def plotGraph(self, colorArrangement): """ 绘制具有根据给定颜色排列进行着色的图 """ if len(colorArrangement) != self.__len__(): raise ValueError("size of color list should be equal to ",self.__len__()) # 创建唯一色列表 colorList = list(set(colorArrangement)) # 创建实际颜色列表 colors = plt.cm.rainbow(np.linspace(0,1,len(colorList))) # 遍历节点，并根据颜色组合分配颜色 colorMap = [] for i in range(self.__len__()): color = colors[colorList.index(colorArrangement[i])] colorMap.append(color) # 对相应节点进行着色 nx.draw_kamada_kawai(self.graph,node_color=colorMap,with_labels=True) return plt
遗传算法解决图着色问题
常量及遗传算子定义
1. 导入所需库
from deap import base from deap import creator from deap import tools import random import numpy as np from matplotlib import pyplot as plt import seaborn as sns import networkx as nx
2. 硬约束惩罚因子
HARD_CONSTRAINT_PENALTY = 103. 基因算法常量
POPULATION_SIZE = 100 P_CROSSOVER = 0.9 P_MUTATION = 0.1 MAX_GENERATIONS = 100 HALL_OF_FAME_SIZE = 10 MAX_COLORS = 10
4. 实例化图着色问题，该实例具有要解决的所需NetworkX图，以及hardConstraintPenalty的所需值
gcp = GraphColoringProblem(nx.petersen_graph(),HARD_CONSTRAINT_PENALTY)5. 定义最小化适应度策略
creator.create("FitnessMin",base.Fitness,weights=(-1.0,))6. .由于解由代表参与颜色的整数值列表表示，因此需要定义一个随机生成器，该生成器将创建介于0和颜色数减1之间的整数。每个整数代表一种颜色。然后，定义解（个体）创建器，该创建器将生成随机整数的列表，列表的长度与给定图的长度匹配。最后，定义创建整个群体的运算符：
creator.create("Individual",list,fitness=creator.FitnessMin) toolbox = base.Toolbox() toolbox.register("Integers",random.randint,0,MAX_COLORS - 1) toolbox.register("individualCreator",tools.initRepeat,creator.Individual,toolbox.Integers,len(gcp)) toolbox.register("populationCreator",tools.initRepeat,list,toolbox.individualCreator)
7. 通过调用GraphColoringProblem类的getCost()方法，将适应度评估函数设置为计算解的违反颜色数和使用的颜色数量
def getCost(individual): return gcp.getCost(individual), toolbox.register("evaluate",getCost)
8. 定义遗传算子
toolbox.register("select",tools.selTournament,tournsize=2) toolbox.register("mate",tools.cxTwoPoint) # mutUniformInt运算符，将给定的整数更改为允许范围内的另一个随机生成的整数 toolbox.register("mutate",tools.mutUniformInt,low=0,up=MAX_COLORS - 1,indpb=1.0/len(gcp))
使用精英主义策略
使用名人堂可以用来保留进化过程中种群中曾经存在的最佳个体，并不会由于选择，交叉或变异而失去了它们，HallOfFame类在tools模块中实现。
将Halloffame对象用于实现精英主义。 Halloffame对象中包含的个体被直接注入下一代，并且不受选择，交叉和突变的遗传算子的影响
# 名人堂成员数量 HALL_OF_FAME_SIZE = 30 def eaSimpleWithElitism(population, toolbox, cxpb, mutpb, ngen, stats=None, halloffame=None, verbose=__debug__): """ 使用halloffame来实现精英机制。 包含在名人堂麦中的个体被直接注入下一代，并且不受选择，交叉和突变的遗传算子的影响。 """ logbook = tools.Logbook()#用于监控算法运行，和统计数据 logbook.header = ['gen','nevals'] + (stats.fields if stats else []) # 计算个体适应度 invalid_ind = [ind for ind in population if not ind.fitness.valid] fitnesses = toolbox.map(toolbox.evaluate,invalid_ind) for ind,fit in zip(invalid_ind,fitnesses): ind.fitness.values = fit if halloffame is None: raise ValueError("halloffame parameter must not be empty!") #更新名人堂成员 halloffame.update(population) hof_size = len(halloffame.items) if halloffame.items else 0 record = stats.compile(population) if stats else {} logbook.record(gen=0,nevals=len(invalid_ind),**record) if verbose: print(logbook.stream) #开始遗传流程 for gen in range(1,ngen + 1): #选择个体数目=种群个体数-名人堂成员数 offspring = toolbox.select(population,len(population) - hof_size) #种群更新到下一代 offspring = algorithms.varAnd(offspring,toolbox,cxpb,mutpb) #计算个体适应度 invalid_ind = [ind for ind in offspring if not ind.fitness.valid] fitnesses = toolbox.map(toolbox.evaluate,invalid_ind) for ind,fit in zip(invalid_ind,fitnesses): ind.fitness.values = fit #将名人堂成员添加到当前代 offspring.extend(halloffame.items) #更新名人堂 halloffame.update(offspring) #使用当前代替换种群 population[:] = offspring #将当前统计信息附加到日志 record = stats.compile(population) if stats else {} logbook.record(gen=gen,nevals=len(invalid_ind),**record) if verbose: print(logbook.stream) return population,logbook
遗传流程
def main(): # 创建初始种群 population = toolbox.populationCreator(n=POPULATION_SIZE) # 定义监听统计数据 stats = tools.Statistics(lambda ind: ind.fitness.values) stats.register("min",np.min) stats.register("avg",np.mean) # 实例化名人堂类 hof = tools.HallOfFame(HALL_OF_FAME_SIZE) # 执行遗传流程 population, logbook = eaSimpleWithElitism(population, toolbox, cxpb=P_CROSSOVER, mutpb=P_MUTATION, ngen=MAX_GENERATIONS, stats=stats, halloffame=hof, verbose=True) # 打印算法找到的最优解 best = hof.items[0] print("-- Best Individual = ",best) print("-- Best Fitness = ",best.fitness.values[0]) print() print("Number of colors = ",gcp.getNumberOfColors(best)) print("Number of violations = ",gcp.getViolationsCount(best)) print("Cost = ",gcp.getCost(best)) # 绘制最优解 plt.figure(1) gcp.plotGraph(best) # 提取监听的统计结果 minFitnessValues,meanFitnessValues = logbook.select("min","avg") # 绘制统计结果 plt.figure(2) sns.set_style("whitegrid") plt.plot(minFitnessValues, color='red') plt.plot(meanFitnessValues, color='green') plt.xlabel('Generation') plt.ylabel('Min / Average Fitness') plt.title('Min and Average fitness over Generations') plt.show()
结果与分析
运行程序：
if __name__ == "__main__": main()
打印最佳解的相关信息：
-- Best Individual = [0, 8, 3, 0, 3, 8, 0, 0, 3, 8] -- Best Fitness = 3.0 Number of colors = 3 Number of violations = 0 Cost = 3
由于此图较为简单因此算法找到的最佳解就是本问题包含的最优解。
最小适应度和平均适应度的变化：
使用不同图测试算法效果
使用复杂图进行测试
gcp = GraphColoringProblem(nx.mycielski_graph(6), HARD_CONSTRAINT_PENALTY)打印出算法找到的最优解
-- Best Individual = [3, 6, 4, 4, 2, 3, 5, 4, 0, 6, 2, 1, 5, 0, 0, 1, 1, 6, 4, 4, 5, 1, 2, 1, 2, 3, 0, 5, 3, 6, 0, 5, 5, 2, 1, 0, 0, 1, 1, 3, 6, 1, 5, 1, 1, 3, 4] -- Best Fitness = 7.0 Number of colors = 7 Number of violations = 0 Cost = 7
由于知道该图的色数为6，因此尽管没有违反硬约束，是有效解但并不是最佳解。如果我们事先不知道着色数怎么办？一种解决方法是更改遗传算法的参数。例如，增加种群数量（可能还有HOF数量）或增加世代数。另一种方法是重新开始相同的搜索，但是减少颜色数量。由于该算法找到了具有7种颜色的解决方案，因此可以将最大颜色数减少为6种，并查看算法是否仍然可以找到有效的解决方案：
MAX_COLORS = 6MAX_COLORS = 6 时打印结果
-- Best Individual = [0, 2, 0, 3, 4, 4, 5, 3, 5, 4, 0, 0, 1, 1, 3, 1, 1, 1, 1, 1, 1, 0, 4, 4, 2, 0, 2, 4, 5, 4, 5, 5, 2, 0, 0, 2, 3, 2, 2, 5, 5, 5, 5, 2, 0, 4, 1] -- Best Fitness = 6.0 Number of colors = 6 Number of violations = 0
最小适应度和平均适应度的变化：
当我们将颜色的数量从10减少到6时，搜索空间将大大减少——在这种情况下，将从 1047 减少到 647 （因为图中有47个节点）——因此该算法更有可能找到最佳解，即使世代数和人口规模并未改变。因此，虽然算法的第一次运行可以使我们更接近最优解，但是最好不断减少颜色的数量，直到算法找不到更好的解决方案为止。
如果尝试将颜色的最大数量减少到5种，将始终存在至少遇到一种违反硬约束的情况。
MAX_COLORS = 5MAX_COLORS = 5时打印结果
-- Best Individual = [1, 0, 1, 3, 2, 2, 2, 3, 3, 2, 1, 2, 0, 3, 4, 0, 2, 3, 3, 0, 2, 0, 1, 1, 4, 1, 4, 2, 2, 4, 4, 4, 2, 4, 4, 0, 4, 4, 0, 2, 4, 4, 4, 4, 0, 1, 3] -- Best Fitness = 15.0 Number of colors = 5 Number of violations = 1 Cost = 15