均衡加权图着色问题与启发式算法  

Balanced Weighted Graph Coloring Problem and Its Heuristic Algorithms

作　　者：欧开明 江华 OU Kaiming;JIANG Hua(School of Software,Yunnan University,Kunming 650504,China)

机构地区：[1]云南大学软件学院,昆明650504

出　　处：《计算机科学》2024年第S02期39-45,共7页Computer Science

基　　金：国家自然科学基金(62162066)。

摘　　要：给定一个无向图G和一个颜色数k,图的k着色问题(GCP)指给G中的每个顶点分配k种颜色中的一种,使得任意相邻的两个顶点获得不同的颜色。均衡资源分配是将资源尽可能均匀地分配给各个参与者,旨在实现资源的公平利用和任务的合理分担。针对传统的图着色问题无法解决均衡资源分配的情况,提出了图着色问题的一个新变种——均衡加权图着色问题,其目标是寻找合法的着色使得每种颜色类的权值和的标准差最小。提出了一种将两种局部搜索结合到进化算法中的HEA-TLS算法来寻找该问题的最优解。基于新颖性的局部搜索的目的是寻找到一个合法解。改善解均衡性的局部搜索的目的是在合法解的基础上,改善解的均衡性。进化算法中设计了一个均衡权值交叉,可以根据父代颜色类权值的变化自适应地选择传递给子代的颜色类,通过种群的遗传进化来产生更加均衡的着色解。在DIMACS图上使用通用求解器CPLEX进行对比评估,HEA-TLS在所有测试中取得了几乎最优的结果,验证了所提方法的有效性。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,validating the effectiveness of the proposed method.

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

分 类 号：TP301[自动化与计算机技术—计算机系统结构]