# 导入所需库importnetworkxasnximportmatplotlib.pyplotaspltimportnumpyasnpclassGraphColoringProblem:
def__init__(self,graph,hardConstraintPenalty):
# 初始化实例变量self.graph=graphself.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        """returnnx.number_of_nodes(self.graph)
defgetCost(self,colorArrangement):
"""       计算给定颜色组合的总成本        """returnself.hardConstraintPenalty*self.getViolationsCount(colorArrangement) +self.getNumberOfColors(colorArrangement)
defgetViolationsCount(self,colorArrangement):
"""        计算给定颜色排列中违反颜色的次数        """iflen(colorArrangement) !=self.__len__():
raiseValueError("size of color arrangement should be equal to ", self.__len__())
violations=0# 遍历每对节点，查找它们之间是否存在链接并使用相同的颜色foriinrange(len(colorArrangement)):
forjinrange(i+1,len(colorArrangement)):
ifself.adjMatrix[i,j]:
ifcolorArrangement[i] ==colorArrangement[j]:
violations+=1returnviolationsdefgetNumberOfColors(self, colorArrangement):
"""        计算给定颜色排列使用的颜色数量        """returnlen(set(colorArrangement))
defplotGraph(self, colorArrangement):
"""        绘制具有根据给定颜色排列进行着色的图        """iflen(colorArrangement) !=self.__len__():
raiseValueError("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= []
foriinrange(self.__len__()):
color=colors[colorList.index(colorArrangement[i])]
colorMap.append(color)
# 对相应节点进行着色nx.draw_kamada_kawai(self.graph,node_color=colorMap,with_labels=True)
returnplt

fromdeapimportbasefromdeapimportcreatorfromdeapimporttoolsimportrandomimportnumpyasnpfrommatplotlibimportpyplotaspltimportseabornassnsimportnetworkxasnx

HARD_CONSTRAINT_PENALTY=10

POPULATION_SIZE=100P_CROSSOVER=0.9P_MUTATION=0.1MAX_GENERATIONS=100HALL_OF_FAME_SIZE=10MAX_COLORS=10

gcp=GraphColoringProblem(nx.petersen_graph(),HARD_CONSTRAINT_PENALTY)

creator.create("FitnessMin",base.Fitness,weights=(-1.0,))

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)

defgetCost(individual):
returngcp.getCost(individual),
toolbox.register("evaluate",getCost)

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))

# 名人堂成员数量HALL_OF_FAME_SIZE=30defeaSimpleWithElitism(population,
toolbox,
cxpb,
mutpb,
ngen,
stats=None,
halloffame=None,
verbose=__debug__):
"""    使用halloffame来实现精英机制。 包含在名人堂麦中的个体被直接注入下一代，并且不受选择，交叉和突变的遗传算子的影响。    """logbook=tools.Logbook()#用于监控算法运行，和统计数据logbook.header= ['gen','nevals'] + (stats.fieldsifstatselse [])
# 计算个体适应度invalid_ind= [indforindinpopulationifnotind.fitness.valid]
fitnesses=toolbox.map(toolbox.evaluate,invalid_ind)
forind,fitinzip(invalid_ind,fitnesses):
ind.fitness.values=fitifhalloffameisNone:
raiseValueError("halloffame parameter must not be empty!")
#更新名人堂成员halloffame.update(population)
hof_size=len(halloffame.items) ifhalloffame.itemselse0record=stats.compile(population) ifstatselse {}
logbook.record(gen=0,nevals=len(invalid_ind),**record)
ifverbose:
print(logbook.stream)
#开始遗传流程forgeninrange(1,ngen+1):
#选择个体数目=种群个体数-名人堂成员数offspring=toolbox.select(population,len(population) -hof_size)
#种群更新到下一代offspring=algorithms.varAnd(offspring,toolbox,cxpb,mutpb)
#计算个体适应度invalid_ind= [indforindinoffspringifnotind.fitness.valid]
fitnesses=toolbox.map(toolbox.evaluate,invalid_ind)
forind,fitinzip(invalid_ind,fitnesses):
ind.fitness.values=fit#将名人堂成员添加到当前代offspring.extend(halloffame.items)
#更新名人堂halloffame.update(offspring)
#使用当前代替换种群population[:] =offspring#将当前统计信息附加到日志record=stats.compile(population) ifstatselse {}
logbook.record(gen=gen,nevals=len(invalid_ind),**record)
ifverbose:
print(logbook.stream)
returnpopulation,logbook

defmain():
# 创建初始种群population=toolbox.populationCreator(n=POPULATION_SIZE)
# 定义监听统计数据stats=tools.Statistics(lambdaind: 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()

gcp=GraphColoringProblem(nx.mycielski_graph(6), HARD_CONSTRAINT_PENALTY)

--BestIndividual=  [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]
--BestFitness=7.0Numberofcolors=7Numberofviolations=0Cost=7

MAX_COLORS=6

MAX_COLORS=5

--BestIndividual=  [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]
--BestFitness=15.0Numberofcolors=5Numberofviolations=1Cost=15