A cellular learning automata-based algorithm for solving the vertex coloring problem
A cellular learning automata-based algorithm for solving the vertex coloring problem
复制标题
DOI：
10.1016/j.eswa.2011.01.098
复制
发表时间：
2011-08
期刊：
影响因子：
--
通讯作者：
J. A. Torkestani;M. Meybodi
中科院分区：
文献类型：
--
作者：
J. A. Torkestani;M. Meybodi
顶点着色问题是一个组合优化问题，其中为图的每个顶点分配一种颜色，使得没有两个相邻的顶点具有相同的颜色。元胞学习自动机是元胞自动机和学习自动机相结合的一种有效的概率学习模型。不规则细胞学习自动机（ICLA）是细胞学习自动机的一种推广，它消除了传统细胞学习自动机中矩形网格结构的限制。本文提出了一种基于ICLA的顶点着色问题的近似最优解算法。所提出的着色算法是一个完全分布式的算法，其中每个顶点选择它的最佳颜色完全基于其相邻顶点所选择的颜色。计算了该算法在任意图中求顶点着色问题的11-n阶最优解的时间复杂度。为了显示我们提出的算法优于现有的方法，仿真实验已经进行。实验结果表明，该算法在所需颜色数和算法运行时间方面优于其他算法。
Vertex coloring problem is a combinatorial optimization problem in which a color is assigned to each vertex of the graph such that no two adjacent vertices have the same color. Cellular learning automata (CLA) is an effective probabilistic learning model combining cellular automata and learning automata. Irregular cellular learning automata (ICLA) is a generalization of cellular learning automata in which the restriction of rectangular grid structure in traditional CLA is removed. In this paper, an ICLA-based algorithm is proposed for finding a near optimal solution of the vertex coloring problem. The proposed coloring algorithm is a fully distributed algorithm in which each vertex chooses its optimal color based solely on the colors selected by its adjacent vertices. The time complexity of the proposed algorithm is computed for finding a 11-ϵ optimal solution of the vertex coloring problem in an arbitrary graph. To show the superiority of our proposed algorithm over the existing methods, simulation experiments have been conducted. The obtained results show that the proposed algorithm outperforms the others in terms of the required number of colors and running time of algorithm.