摘要： 现有典型的分布式算法在解决大规模图形着色问题时，必须维持节点间的通信连接，在邻接节点增长时效率和可求解规模下降明显。为此，将多代理技术平台下的图像着色问题转换为博弈模型，采用自适应学习算法，逐步优化代理自身状态行为以达到系统的最优状态，即纳什均衡点。实验结果表明，较现有的分布式算法，该算法不但具有更高的求解效率，能够解决更大规模的图形着色问题，而且对邻接节点规模变化的适应能力进一步提高。

关键词: 分布式算法, 纳什均衡, 图形着色, 多代理, 自适应学习算法

Abstract: While solving the large-scale graph-coloring problems, the existing distributed algorithms require that the node must be connectable. The growth of the neighbor-nodes brings negative effect on both algorithm efficiency and the solvable scale. So a new algorithm is proposed. The graph-coloring problem is converted to the game problem on the multi-Agent platform. Using the adaptive learning algorithm, each Agent optimizes its own state to maximize system’s utility which is the Nash equilibrium. Empirical evaluation shows that the new method has higher efficiency, better immunity to the growth of neighbors and can deal with larger scale problems than existing distributed algorithms.

Key words: distributed algorithm, Nash equilibrium, graph-coloring, multi-Agent, adaptive leaning algorithm

中图分类号: 

• TP301