基于多目标优化的图的强可区别染色算法研究

发布时间：2018-05-15 11:47

本文选题：生成树 + 生成图　；参考：《兰州交通大学》2017年硕士论文

【摘要】：图论中的一个经典难题——图染色问题,属于图论的一个分支,也是科学计算与工程设计中的基本问题。现实世界中有很多问题都可以转化为图的问题来解决,例如比赛安排问题、网络通信问题、排课表问题、物资存储问题、无线通讯频道分配,印刷电路板设计及变址寄存器数目分配等等,这些问题的解决都涉及到图的染色理论,所以染色问题是图论中极具研究意义的领域之一。随着现实世界中交通运输、计算机网络通信、军事、生产管理等实际问题需求的发展,以及经典智能优化算法所存在的不足以及局限性的演变,我们对快速而准确地实现染色结果并将其应用于实际的需求也逐步增大。图的强可区别染色问题是一种多条件约束染色,是在可区别全染色的基础之上再增加约束条件,使得色集合的包含元素更多,共包括两种染色概念:邻点强可区别全染色、点强可区别全染色。目前在已公开发表的文献中对强可区别全染色的研究仅局限于圈图、轮图、完全图、树等特殊图,而对于一般随机图的强可区别染色研究尚无可行的解决方法。本文结合多目标优化的研究思想,设计了基于多目标优化的强可区别染色算法,算法通过设定多个子目标函数逐步寻优,使其最终的目标函数得到Pareto最优解,实现局部最优化到整体最优化的过程。同时文中还设计实现了有限点以内所有生成树算法以及所有简单连通图生成算法,为各类染色算法的研究及结果集测试奠定基础。本文的主要工作如下:(1)介绍了图论以及图染色理论的基本概念、多目标优化问题的相关概念、遗传算法的基本思想以及应用于解决正常边染色的算法执行过程,同时对其优缺点进行分析总结。(2)给出了两类随机图生成算法,第一类是输入顶点数目依照规则随机连边生成随机简单连通图算法;第二类是基于生成树生成有限点数内所有伪非同构图算法,因此第二类算法又包含了生成树算法;两种随机图生成算法为后续一系列染色算法的结果集测试、统计以及相关引理、猜想的证明提供基础研究数据,为各种染色算法的研究奠定良好的基础。(3)设计并实现了基于多目标优化的图的邻点强可区别全染色算法、基于多目标优化的图的点强可区别全染色算法,同时设计了两类正常边染色算法、顶点染色算法、色集合调整算法等一系列子算法。强可区别全染色算法的最终目的是要确保顶点的色集合不同,色集合除了顶点颜色,顶点与其关联边颜色之外还加入了相邻顶点的颜色,所以色集合调整的难度变得更大。所以本文设计了更详细的的强色集调整规则,以及相应的过程评估函数来及时生成新的预染色组,从而更快速地搜索到最优解,在不提高算法时间复杂度的情况下,提高算法的运行效率。(4)测试结果集为7个点以内所有的伪非同构图,15个顶点以内的特殊图、14个顶点以内的所有生成树以及1000个点以内部分随机连通图;并通过大量实验结果集的分析,给出了若干有意义的结论及猜想。
[Abstract]:A classic problem in graph theory, graph dyeing problem, belongs to a branch of graph theory, and it is also a basic problem in scientific computing and engineering design. There are many problems in the real world that can be transformed into graphs, such as competition arrangement, network communication, scheduling, material storage, and wireless communication channels. Distribution, printed circuit board design and the number allocation of variable address registers and so on. The solution of these problems involves the theory of graph dyeing, so the problem of dyeing is one of the most important fields in the graph theory. With the real world traffic, computer network communication, military, production management and other practical problems, and the classic The shortcomings of the intelligent optimization algorithm and the evolution of its limitations, we have gradually increased the demand for fast and accurate implementation of the dyeing results and applied it to actual conditions. There are more elements, including two kinds of coloring concepts: strong distinguishable full coloring from adjacent points, and strong distinguishable total coloring. In the published literature, the study of strongly distinguishable total coloring is limited to special graphs, such as circle graph, wheel diagram, complete graph, tree and so on, but there is no feasible solution for the strong distinguishable dyeing of general random graphs. In this paper, based on the research idea of multi-objective optimization, a strong distinguishable dyeing algorithm based on multi-objective optimization is designed. The algorithm is optimized by setting multiple sub objective functions, and the final objective function is obtained by Pareto optimal solution to achieve the path of local optimization to the overall optimization. The main work of this paper is as follows: (1) the basic concepts of graph theory and graph coloring theory, the related concepts of multi-objective optimization problem, the basic idea of the relic algorithm and the application to solve the normal dyeing are introduced. The advantages and disadvantages of color algorithm are analyzed and analyzed. (2) two classes of random graph generation algorithms are given. The first class is the number of the input vertices to generate random simple connected graphs in accordance with regular random edges; the second class is based on the generation tree to generate the pseudo non isomorphic graph algorithm in the finite number of points, so the second kind of algorithm also contains the algorithm. The algorithm of spanning tree is used. Two random graph generation algorithms are tested for the result set of a series of successive dyeing algorithms, statistics and related lemma, and the proof of conjecture provides basic research data, which lays a good foundation for the study of all kinds of dyeing algorithms. (3) design and implement a strong distinguishable full coloring algorithm based on multi-objective optimization. At the same time, a series of sub algorithms, such as two normal edge coloring algorithms, vertex coloring algorithms and color set adjustment algorithms, are designed based on the multi-objective optimization. The final purpose of the strong distinguishable total coloring algorithm is to ensure that the color set of the vertex is different, the color set is the vertex color, the vertex and its associated edge. In addition to the color of adjacent vertices, it is more difficult to adjust the color set, so this paper designs a more detailed rule of the strong color set adjustment, and the corresponding process evaluation function to generate a new pre dyed group in time, so that the optimal solution can be searched more quickly, without improving the time complexity of the algorithm. The running efficiency of the high algorithm. (4) the test result set is all the pseudo non isomorphic graphs within 7 points, the special graphs within 15 vertices, all the spanning trees within the 14 vertices and the partial random connected graphs within 1000 points, and some meaningful conclusions and conjectures are given through the analysis of a large number of experimental results set.

【学位授予单位】：兰州交通大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP18;O157.5

【参考文献】