关键词: 图着色, 均衡加权图着色问题, 局部搜索, 混合进化算法

Abstract: Given an undirected graph G and a number of colors k,the graph k-coloring problem(GCP) refers to assigning one of k colors to each vertex in G such that any two adjacent vertices receive different colors.Balanced resource allocation is to distribute resources as evenly as possible to each participant,aiming to achieve fair utilization of resources and reasonable sharing of tasks.Aiming at the situation that the traditional graph coloring problem cannot solve the balanced resource allocation,a new variant of the graph coloring problem,the balanced weighted graph coloring problem,is proposed,whose goal is to find a legal coloring that minimizes the standard deviation of the sum of the weights of each color class.A HEA-TLS algorithm that combines two local searches into an evolutionary algorithm is proposed to find an optimal solution to this problem.The novelty-based local search aims to find a legitimate solution.The purpose of the local search for improving the equilibrium of the solution is to improve the equilibrium of the solution based on the legitimate solution.A balanced weight crossover is designed in the evolutionary algorithm,which can adaptively select the color classes to be passed to the offspring according to the changes in the weights of the parent color classes,to produce a more balanced coloring solution through genetic evolution of the population.In a comparative evaluation using the generalized solver CPLEX on the DIMACS graph,HEA-TLS achieves almost optimal results in all tests,va-lidating the effectiveness of the proposed method.

Key words: Graph coloring, Balanced weighted graph coloring problem, Local search, Hybrid evolutionary algorithm