图形着色问题的分布式势博弈算法  

Distributed Potential Game Method for Graph Coloring Problem

作　　者：杨光[1] 蔚承建[1] 王开[2] 胡恒恺[1] 

机构地区：[1]南京工业大学电子与信息工程学院 [2]东南大学信息科学与工程学院

出　　处：《计算机工程》2012年第23期181-184,189,共5页Computer Engineering

基　　金：国家自然科学基金资助项目(60972165);教育部博士点基金资助项目(20100092120012;20090092120012);江苏省自然科学基金资助项目(BK2011060;BK2010240);南京市政府海外留学基金资助项目(ZBW302001)

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

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

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